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

Jon Fairbairn jon.fairbairn at cl.cam.ac.uk
Tue Sep 4 04:54:57 EDT 2007

Miguel <miguelimo38 at yandex.ru> writes:

>>On 9/3/07,Vimal<j.vimal at gmail.com> wrote:
>>>while E do
>>>if F then
>>>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
do T

> 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

More information about the Haskell-Cafe mailing list