Why not allow empty code blocks?

[Steven D'Aprano]

On Wednesday 03 August 2016 05:22, Paul Rubin wrote:

>> The Halting Problem is easily solved for Bloop languages: they always
>> halt.
> 
> If Bloop is powerful enough to "solve the halting problem" as you
> describe, that gives it capabilities that Turing-complete languages
> lack.  (Of course it also loses some capabilities).

It only solves it in the sense that it isn't capable of looping forever, so 
there's never a question of whether or not a Bloop program will halt: they all 
do. It doesn't have any capabilities that Floop lacks: Floop can solve any 
problem that Bloop can solve, plus problems that Bloop cannot.

In a sense, it's a less extreme version of this:

Me: "I have here a computer which is immune to all computer viruses, malware 
and hostile code, now and in the future!"

You: "That's great! Turn it on so we can see how it works."

Me: "Oh, it doesn't turn on. There's no power supply. That was the only way I 
could guarantee it wouldn't execute malware: by making sure it couldn't execute 
*anything*."

While I suppose it is true that a computer that doesn't run is still a 
computer, its an abuse of language to say that it has capabilities that running 
computers lack:

- unhackable
- immune to all viruses
- unaffected by power surges
- data storage is 100% reliable, never lose data again
- instantaneous log-off and shutdown

:-)


Floop can certainly give a *partial* solution to the Halting Problem:

- if the code is runnable using Bloop, then it definitely halts;
- if the code is runnable using Floop, then ... maybe it halts?

A sufficiently clever Floop program might be able to analyse Floop code and 
recognise many common cases of non-terminating loops. For example, the Floop 
equivalent of:

while True:
    pass

is clearly non-terminating. There's no mystery about being able to detect that. 
But not all code is that straight-forward.


> Some of the
> advantages of Turing-incomplete languages (plus why they are less
> constraining than it might sound) are discussed here:
> 
>    http://www.jucs.org/doi?doi=10.3217/jucs-010-07-0751
> 
>> But as we've seen, syntax can make a HUGE difference to power in the
>> sense of expressiveness, maintainability of code, readability,
>> efficiency of the programmer, and even efficiency of the
>> interpreter. Conway's Game of Life is Turing Complete. Would you
>> rather use Python, or Game of Life? BrainF*ck or Javascript?
> 
> That's completely different than Python vs Scheme, where you can
> basically transliterate Python to Scheme by converting indentation
> structure into parentheses and a few other things like that.

I wouldn't say "completely different".

Since GoL, Python, BrainF*uck and Javascript are all Turing Complete, there 
must be a way to convert a program in any one to any of the others. One obvious 
way to do this is to (for example) write a Javascript interpreter in BrainF*ck. 
That demonstrates that anything Javascript can do, BrainF*ck can do too.

Of course, going the other way (BrainF*ck interpreter written in Javascript) is 
considerably easier :-)

Python is sometimes described as a Lisp with more sensible syntax, so its not 
surprising that it is relatively simple to translate Python to Lisp and visa 
versa. It would be harder to translate (say) COBOL code to (say) Smalltalk. But 
it is always the case that any program for a Turing Complete language can be 
translated into a program for any other Turing Complete language.

It might be *really really really difficult*, inefficient and slow, but its 
always possible.

What's *not* possible is to take any Floop program and translate it into Bloop. 
There are things Floop can do that Bloop cannot -- Bloop is not Turing 
Complete, but Floop is.



-- 
Steve