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

[Jon Fairbairn]

Miguel <miguelimo38 at yandex.ru> writes:

>>On 9/3/07,Vimal<j.vimal at gmail.com> wrote:
>>>while E do
>>>S
>>>if F then
>>>break
>>>end
>>>T
>>>end
>>>
>>>He then asked us to *prove* that the above programming fragment cannot
>>>
>>>be implemented just using if and while statement, even if S and T can
>>>be duplicated a finite number of times
>>But it IS possible.  Just add a boolean flag:
>
> 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. 

It depends on arbitrary restrictions on what constitutes an
(boolean) expression, something that is anathema to
functional programmers :-) Spot the language:

while if E 
      then S; F
      else False
      fi
do T
od

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

I don't remember needing a goto in Haskell...

-- 
Jón Fairbairn                                 Jon.Fairbairn at cl.cam.ac.uk