OSDev.org

When I mentioned python is slow I never made any statement saying that python cannot be fast. It depends on the implementation. It is just that that was the question that brought me into the world of LangDev.

MasterLee wrote:Given an language L1 that is faster as an language L2 in some tasks an slower in other tasks. An language L3 will be faster as booth language if (optimal) translators are available that can translate code in L3 to L1 and L2.

I'm not sure code generation and optimizations are what's being discussed. First of all, given very intelligent compilers, they should be able to output equivalent yet optimal code regardless of language provided they are both Turing-complete---L3 is rendered useless if we start talking about optimal compilers. We mostly want to talk about language capabilities and productivity. The question is whether a good L3 could be designed...

Language support for every possible programming paradigm is not a good idea, as no one likes a bloated language (e.g., C++ doesn't even try that and look how huge it is: the latest C++11 draft, which became FIDS, is 1353 pages long). The other extreme is clearly not good way to go either (e.g., assembly is the most capable but the least productive).

Next, let's remember that we don't (yet) have such intelligent compilers and that we design languages in such a way that they will make it easy for compiler implementors to come up with efficient implementations.

Is your L3 feasible?

given very intelligent compilers

a.k.a. magic

We already have techniques to generate optimal code regardless of situation. Alas, the current ones take forever to compile so they're not practical for anything other than trivial tasks.

Love4Boobies wrote:We already have techniques to generate optimal code regardless of situation. Alas, the current ones take forever to compile so they're not practical for anything other than trivial tasks.

There are no optimal optimizing compilers. This fact can be proved simply because such a compiler would be able to solve the halting problem, which is fundamentally unsolvable for a computer (A proof of this was given by Turing). So the techniques you claim exist don't.

There is no optimum for a program that does not halt. Therefore any valid program that has an optimized solution is finite in execution length, and therefore the optimal solution is finite in size and can be found within finite time by trying all configurations.

Therefore, there exists an algorithm. (And conversely, the halting problem is irrelevant as an argument.)

davidv1992 wrote:

Love4Boobies wrote:We already have techniques to generate optimal code regardless of situation. Alas, the current ones take forever to compile so they're not practical for anything other than trivial tasks.

There are no optimal optimizing compilers. This fact can be proved simply because such a compiler would be able to solve the halting problem, which is fundamentally unsolvable for a computer (A proof of this was given by Turing). So the techniques you claim exist don't.

The halting problem cannot be properly expressed in (Turing-complete) high-level languages either, so the compiler would never have to optimize it.

On an unrelated note, this is more a problem of computability theory rather than engineering. Remember that undecidable problems cannot be correctly solved by one universal algorithm when you're actually dealing with true Turing-complete machines, which computers aren't due to the fact that they can only have a limited amount of memory. Furthermore, remember although there are quite a few classes of problems for which we have proof that they cannot be solved by computers (because they cannot be expressed in the appropriate terms), we have little understanding about how these problems fit in with AI. For example, given a very big and complex ANN, the program might consider the problem in a more abstract way---much like humans do. The biggest issue we will be faced to might be encountering problems that cannot be solved in the axiomatic system we use.

EDIT: Aww, Combuster beat me to it but I wrote so much that I will submit anway

@combuster Agreed.
Actually I cannot think of any program which eventually does not halt apart from but even then there is a way of seeing that programs do not continue in an infinite loop. (wonder what kill is for?) And in any case it is pretty obvious that the program will loop forever.

ACcurrent wrote:@combuster Agreed.
Actually I cannot think of any program which eventually does not halt apart from

Code: Select all

for(;;){...}

but even then there is a way of seeing that programs do not continue in an infinite loop. (wonder what kill is for?) And in any case it is pretty obvious that the program will loop forever.

How about recursion or a regular for loop, based on input from a file, the network, the user, etc? How about programs that are intended to run forever, e.g. event loops in servers?

We were talking about scenarios where the input is readily available. No one can tell whether execution will terminate unless they don't know what the input is...

My post was in response to "I cannot think of any program which eventually does not halt apart from for(;;){...}". In the situations I described, even if you know the input, you cannot in the general case decide whether the program will halt.

Which you should know based on your reference to the halting problem earlier...

If a user passes a faulty file to the program its the user's fault.

If a user passes a faulty file to the program it doesn't mean the program is allowed to hang or blow up. (Especially if it's something important like a server for the DoD )