Equality of functions?

[abvgdeika]

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...

[edgar-rft]

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

[abvgdeika]

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?

[edgar-rft]

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

[Goheeca]

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.

[Paul]

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))...

[Goheeca]

Yeah, for this sorcery I would pick up ACL2.

[abvgdeika]

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.

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))...

[sylwester]

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 #+))


[abvgdeika]

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.