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

[Sterling Clover]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe