Fw: [plt-scheme] Check for function equality?

From: Jos Koot (jos.koot at telefonica.net)
Date: Thu Feb 19 17:59:22 EST 2009

----- Original Message ----- 
From: "Jos Koot" <jos.koot at telefonica.net>
To: "dave yrueta" <dyrueta at gmail.com>
Sent: Thursday, February 19, 2009 11:53 PM
Subject: Re: [plt-scheme] Check for function equality?

> Around 1900 mathematiciens thought mathematics was complete and 
> consistent, meaning that they thought that every statement could be proven 
> to be either true or false. A program was set up to write down all of 
> mathematics (Russel program) Already early in the execution of the program 
> Russel himself found out that mathematics is not both complete and 
> consistent. You just hit the same question: how do we determine when two 
> things are the same? For numbers and strings and symbols (in Scheme) there 
> are (several) predicates that answer this question. But NOT for 
> procedures. It is impossible to make a general and always working 
> predicate for equality of procedures/functions (even when without side 
> effects). As Matthew Flatt and Matthias Felleisen already pointed out, 
> this has to do with the halting problem, a very fundamental theoreme on 
> what can and what cannot be computed (in general) There are limitations on 
> what we can program. A general and thrustworthy predicate on equality of 
> functions is beyond the limit. The addition "general" is essential here. 
> Of course we can make predicates that may in some cases give the right 
> answer. But since it is impossible to make a predicate that ALWAYS gives 
> the right answer, we had better forget about such a predicate. This is 
> related to the halting problem in the sense that an attempt to make an 
> equality predicate that never answers wrong, is bound to give no answer at 
> all in some cases (that is it will continue to compute forever, possibly 
> consuming more and more memory).
> Jos
> ----- Original Message ----- 
> From: "dave yrueta" <dyrueta at gmail.com>
> To: <plt-scheme at list.cs.brown.edu>
> Sent: Thursday, February 19, 2009 10:43 PM
> Subject: [plt-scheme] Check for function equality?
>> Hi All --
>> Is there a Scheme function similar to "check-expect" that tests for
>> equality between functions?
>> Example:
>> ;23.3.2
>> ;g-fives-closed : N -> number
>> ;non-recursive version of g-fives
>> ;(check-expect (g-fives-closed 3) 375)
>> (define (g-fives-closed n)
>>  (* 3 (expt 5 n)))
>> ;23.3.4
>> ;geometric-series : number number -> (number -> number)
>> ;consumes two numbers start and s, produces a function representing
>> the geometric series whose starting point is start and whose factor is
>> s
>> (define (geometric-series start s)
>>  (local ((define (local-g-series n)
>>            (* start (expt s n))))
>>    local-g-series))
>> (define g-fives-closed-test (geometric-series 3 5))
>> ;test 1 = test passes
>> (check-expect (g-fives-closed-test 3) (g-fives-closed 3))
>> ;test 2 = test fails
>> (check-expect g-fives-closed-test g-fives-closed)
>> As far as I can tell, "g-fives-closed-test" and "g-fives-closed"
>> differ in name only. I ran the same test with eq? and equal? and
>> received the same results.  Any way to test for this kind of equality?
>> Thanks,
>> Dave Yrueta
>> _________________________________________________
>>  For list-related administrative tasks:
>>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme

Posted on the users mailing list.