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

Vimal j.vimal at gmail.com
Mon Sep 3 14:47:53 EDT 2007


Hi
In my Paradigms of Programming course, my professor presents this piece of code:

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

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)
do
(* Nothing *)
end

But I would also like to consider an option of proving that its
impossible, under the given constraints... Any thoughts?

Vimal


More information about the Haskell-Cafe mailing list