Equality of functions?

Discussion of Common Lisp

Equality of functions?

Postby abvgdeika » Sun Oct 14, 2012 12:17 am

Is there any way to compare equality of functions in LISP?
The following example explains what do I mean:
Let us define two functions:
>>>>> (defun next1 (x) (+ x 1) )
and
>>>>> (defun next2 (y) (+ y 1) )
Clearly, they do the same as functions and their formal definitions differ only by the name of
formal variable.
My question: is there a possibility in LISP to recognize that these functions are identical?
A simple test call (equalp next1 next2) results NIL...
To understand LISP, you must first understand LISP.
abvgdeika
 
Posts: 20
Joined: Mon Jun 06, 2011 10:59 pm

Re: Equality of functions?

Postby edgar-rft » Sun Oct 14, 2012 2:24 am

Lisp functions are not math functions. Lisp functions are pieces of interpreted or compiled Lisp code and AFAIK there is no way to compare the math semantics of Lisp function objects other than to write a set of tests and compare the results.

Also note that (equalp next1 next2) does not compare two SYMBOL-FUNCTIONs (the function objects), instead it compares the SYMBOL-VALUEs (the variable values) of the symbols NEXT1 and NEXT2. To compare the function objects of the symbols NEXT1 and NEXT2 you need to write:

Code: Select all
(equalp #'next1 #'next2) => NIL

This also results NIL because EQUALP compares two different SYMBOL-FUNCTION objects, bound to two different Lisp symbols, NEXT1 and NEXT2.

In ANSI-CL, there is FUNCTION-LAMBDA-EXPRESSION, returning the textual definition of a Lisp function object as a list, but only if this information is available at all. With high OPTIMIZE settings a Lisp compiler is free to strip out this information from compiled Lisp function objects, in which case FUNCTION-LAMBDA-EXPRESSION just simply returns NIL.

Here is what happens with SBCL 1.0.59 (and default OPTIMIZE settings):

Code: Select all
CL-USER> (defun next1 (x) (+ x 1))
NEXT1

CL-USER> (defun next2 (y) (+ y 1))
NEXT2

CL-USER> (function-lambda-expression #'next1)
(SB-INT:NAMED-LAMBDA NEXT1
    (X)
  (BLOCK NEXT1 (+ X 1)))
NIL
NEXT1

CL-USER> (function-lambda-expression #'next2)
(SB-INT:NAMED-LAMBDA NEXT2
    (Y)
  (BLOCK NEXT2 (+ Y 1)))
NIL
NEXT2

You see that even if FUNCTION-LAMBDA-EXPRESSION returns useful results, you still need to write some code to find out if the math semantics of the textual function definitions are equal or not. In Lisp, such a program is called a "code walker" (ask Google about it).

- edgar
edgar-rft
 
Posts: 157
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Equality of functions?

Postby abvgdeika » Sun Oct 14, 2012 2:39 am

Thanks for your detailed answer! Your last remark about "code walker" is most helpful, I shall look at it.
As far as I understand your answer, there is no inbuilt standard "code walker" in LISP?
To understand LISP, you must first understand LISP.
abvgdeika
 
Posts: 20
Joined: Mon Jun 06, 2011 10:59 pm

Re: Equality of functions?

Postby edgar-rft » Sun Oct 14, 2012 2:48 am

There is no standard code walker because the return-value of FUNCTION-LAMBDA-EXPRESSION is implementation-dependent and therefore "unreliable" from the ANSI Specification's point of view, but there may be some more useful functions for code introspection bundled with your Common Lisp implementation. See the docs of your Common Lisp implementation (chapters about debugging etc.) before you try to write your own code walker, what is a non-trivial task.

- edgar
edgar-rft
 
Posts: 157
Joined: Fri Aug 06, 2010 6:34 am
Location: Germany

Re: Equality of functions?

Postby Goheeca » Sun Oct 14, 2012 2:59 am

And because the standard doesn't provide a way to get always a body-form and a lambda list therefore you'd must wrap/shadow function-generating functions or macros like defun, lambda, flet, etc. to save information which disappears at creating and even you'd have several issues with closures.
cl-2dsyntax is my attempt to create a Python-like reader. My mirror of CLHS (and the dark themed version).
User avatar
Goheeca
 
Posts: 218
Joined: Thu May 10, 2012 12:54 pm

Re: Equality of functions?

Postby Paul » Sun Oct 14, 2012 5:23 pm

abvgdeika wrote:Thanks for your detailed answer! Your last remark about "code walker" is most helpful, I shall look at it.
As far as I understand your answer, there is no inbuilt standard "code walker" in LISP?


It doesn't matter; you can't tell if two functions do the same thing anyway. You can tell if they're identical code, just switching variable names or something, but what if next2 was, e.g., (defun next2 (x) (/ (+ (* x 2) 2) 2))...
Paul
 
Posts: 106
Joined: Tue Jun 02, 2009 6:00 am

Re: Equality of functions?

Postby Goheeca » Mon Oct 15, 2012 2:49 am

Yeah, for this sorcery I would pick up ACL2.
cl-2dsyntax is my attempt to create a Python-like reader. My mirror of CLHS (and the dark themed version).
User avatar
Goheeca
 
Posts: 218
Joined: Thu May 10, 2012 12:54 pm

Re: Equality of functions?

Postby abvgdeika » Mon Oct 15, 2012 9:26 am

Of course I meant in my question "language equality", i.e. two functions are "language equal" if their lambda-expressions differ only by names of formal variables in the lambda-list and body.
I suspect it is not too difficult to write a "code-walker" which can trace such an equality, and this is a question of programming.
To recognize equality based on application of mathematical laws is of course much more difficult and this is a question of mathematics, not programming.

Paul wrote:
abvgdeika wrote:Thanks for your detailed answer! Your last remark about "code walker" is most helpful, I shall look at it.
As far as I understand your answer, there is no inbuilt standard "code walker" in LISP?


It doesn't matter; you can't tell if two functions do the same thing anyway. You can tell if they're identical code, just switching variable names or something, but what if next2 was, e.g., (defun next2 (x) (/ (+ (* x 2) 2) 2))...
To understand LISP, you must first understand LISP.
abvgdeika
 
Posts: 20
Joined: Mon Jun 06, 2011 10:59 pm

Re: Equality of functions?

Postby sylwester » Mon Oct 15, 2012 1:43 pm

When I'm looking at that I'm thinking stack machine and parameters on stack.
In that case the name of the variable is irellevant but it's order is.

Would you consider these two the same as well?

Code: Select all
(defun add1 (x y) (+ x y)) ;; (clambda 2 (apply #+))

(defun add2 (x y) (+ y x)) ;; (clambda 2 (swap) (apply #+))
I'm the author of two useless languages that uses BF as target machine.
Currently I'm planning a Scheme compiler :p
sylwester
 
Posts: 83
Joined: Mon Jul 11, 2011 2:53 pm

Re: Equality of functions?

Postby abvgdeika » Mon Oct 15, 2012 2:24 pm

sylwester wrote:Would you consider these two the same as well?

Code: Select all
(defun add1 (x y) (+ x y)) ;; (clambda 2 (apply #+))

(defun add2 (x y) (+ y x)) ;; (clambda 2 (swap) (apply #+))


Of course your add1 and add2 are not "language equal", their identity in the real world is based on
commutativity law of arithmetics.
To understand LISP, you must first understand LISP.
abvgdeika
 
Posts: 20
Joined: Mon Jun 06, 2011 10:59 pm


Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 3 guests