[Haskell-cafe] [Off topic] Proving an impossibility
j.vimal at gmail.com
Mon Sep 3 14:47:53 EDT 2007
In my Paradigms of Programming course, my professor presents this piece of code:
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
He also asked us to state our assumptions if any.
1. We have assignment statements (to create a flag and check)
2. The execution of E or F does not affect execution of S or T...
Well, learning Haskell, I quickly realized that even if S and T have
to be expressions and came up with this, assuming that
1. There are boolean operations
2. Boolean expressions are evaluated from Left to Right
3. Boolean expressions can be short-circuited
while E and (S or 1) and F and (T or 1)
(* Nothing *)
But I would also like to consider an option of proving that its
impossible, under the given constraints... Any thoughts?
More information about the Haskell-Cafe