[plt-scheme] Check for function equality?

From: Marco Morazan (morazanm at gmail.com)
Date: Thu Feb 19 21:08:43 EST 2009

On Thu, Feb 19, 2009 at 6:34 PM, Robby Findler
<robby at eecs.northwestern.edu> wrote:
> One can explain this without resort to Turing machines or other automata!
> Here's how you might do it.
> Imagine you had a function called "halts":
>  ;; halts? : program input -> boolean
>  ;; returns true when the program halts on the given input
>  ;; returns false when the program would fail to halt on the given input
>  ;; always returns something.
> Now consider this function:
>  (define (als-program x)
>    (cond
>      [(halts? x x) (als-program x)]
>      [else 3]))
> and ask what is
>  (als-program als-program).

Well stated for you Dave. I encourage you to answer Robby's question.
After thinking about (als-program als-program), ask yourself what
(halts? als-program als-program) returns. The first time I saw this as
an undergrad, I thought it was sick to resort to such trickery. It
actually is, however, quite elegant. Such a trivial looking function
leads to profound ideas. :-)




Posted on the users mailing list.