[Haskell-cafe] Re: [Off topic] Proving an impossibility
rendel at rbg.informatik.tu-darmstadt.de
Tue Sep 4 11:39:38 EDT 2007
> 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
> 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
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
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.
More information about the Haskell-Cafe