[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
>>>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
More information about the Haskell-Cafe
mailing list