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