[Haskell-cafe] Re: [Off topic] Proving an impossibility

[Tillmann Rendel]

Vimal wrote:
> Ah, yes, it is possible in this case, but you have used an extra variable.
> It is okay, but our professor doesnt want to put emphasis on
> Computability here (or maybe I dont realize it), but the point is: Are
> such programming constructs really necessary in a programming
> language? i.e. Is Breakl, goto, falling through switch/case
> statements, necessary in a language?

If your (or your professor's) question is not about computabily, but 
about expressivenes, what's the point of asking for a proof? In a 
turing-complete language, everything should be expressible :)

Sensible questions may include: how easy is it to express a language 
feature using only other language features? (local or global 
transformation needed, code blowup, mechanical transformation or 
rewrite-from-scratch?)

> This also brings another point. What if there are N loops like this,
> and there is no break statement available in your language? You would
> have to use N conditional variables, and would make mainting the code
> a horrible thing to do.

I disagree. You would have to introduce a temporary variable for every 
breakable loop, an assignment to the approbiate variable for every break 
and a lot of tests of temporary variables to skip parts of the loop 
body. Since breaks can only occur withing the loop body, and each break 
only breaks the innermost loop, all of these temporary variables can 
share the same name and shadow each other in the case of nested loops. 
by reserving a approbiate name (like "done") for this variable by 
convention.

Reading such code, you can just just resugar the code by reading "if not 
done then", "done := true" and "let var done = false in while ..." as 
primitives.

This is a local transformation, the code blowup is linear and it is 
possible to do it mechanically. I therefore consider the break statement 
as easily emulated by temporary variables.

On the other hand, the obvious next step would be to provide actual 
names for these three uses of the "done"-variable, either by using 
whatever abstraction means provided by the language, or by adding 
syntactic sugar. In Haskell, we would simply define an approbiate monad 
to hide the "if not done then"-parts in the bind operation and reuse the 
existing syntactic sugar for monadic expressions.

   Tillmann