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