I hadn't interpreted the "reminding of Knuth" that way. I wouldn't count break as a goto -- what makes goto especially nasty is that the destination isn't indicated by the structure of the source; it could be just anywhere. Break is slightly more structured.

Maybe you might need to take a look at this :-) http://kerneltrap.org/node/553/2131 Linus does get a little serious about Pascal. But I feel that gotos, like pointers is a tool that makes programming easy (in some context, like modeling a simple FSA). So, its better that we take them in a "Use them with Caution" attitude! Okay, "pointers" may not be a nice thing to discuss here :-) I have been a little sluggish in my replies to mails that came here. I forgot to click "Reply All". These are smoe of the missed replies ... ========================================================

But it IS possible. Just add a boolean flag:

done = False while E and not(done) do...

I'll let you work out the rest. Unless I am missing something here... are you not allowed to introduce extra variables? It's a strange thing for your professor to ask, since under reasonable assumptions, anything that is computable can be done only using if and while. goto (which is essentially what break is) is never necessary.

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? 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. ========================================================

Possibly, you are not allowed to change the sequence of machine operations at all. See, if you change "while(A){B}" to "if(A){B};while(A){B}", the sequence is exactly the same; but it's not possible in this case.

Changing the sequence is fine as long as the execution of one doesnt affect another. So, he is trying to bring the idea of functional programming here, to avoid side-effects.

It reminds me of a paper by Knuth, where he states that "goto" statement is necessary; don't remember the title, however.

Thanks for the info! I willl check it out soon! ======================================================== ~Vimal

You get the logic and code blowup problems that require either local variables, breaks, gotos, or continuations because you're working with tests that generate side-effects. Mixing side-effects and tests is going to generate a goto, sure, but if the code was rewritten in a functional style the problems would go away, even in an imperative context. Or even: myFunc E' = if E' do S if not F then do T myFunc E main = do myFunc E of course you could rewrite this in a while loop too although you'd have to use an assignment, but at least still not one with a silly "done" variable. E' = E while(E') S if not F T E' = E endwhile I've actually used this sort of construct plenty of times in imperative languages (putting "fenceposts" in a list generated by an enumerator, etc.) because its clearer and simpler than break. Break isn't as bad as goto, but it can also lead to difficulty reasoning about large functions along the same lines. in Java I often find myself initializing a return value upfront and then setting it according to the logic of the program rather than calling "return" at arbitrary points for the same reason again -- it lets you avoid duplicate cleanup code and reason clearly about the flow of control in your program. Of course, this is what a "finally" block is for, except finally blocks are ugly, while unwindProtect in, say, lisp, is somewhat neater except it breaks with full continuations, which is why, as i understand it with my still limited Haskell-fu, a monadic context that you can enter and exit is the cleanest way to enforce this stuff, and it works precisely because the pure functionality is enforced. Okay, now I'm rambling. Except that I do note, now, that assignment, and I suppose procedures are disallowed as well because the original question was apparently only with regards to "using just the if and while statement" (which I assume would also disallow the logical operators used in the initial post as well). All of which maybe, is just therefore the professor's way to push students to realize that if and while *alone* are insufficiently expressive to generate all possible flow control combinations (i.e. one can't construct an if/while calculus the same way one can construct an S K one). --S

while E do S if F then break end T end

On Sep 4, 2007, at 11:39 AM, Tillmann Rendel wrote:

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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe