Equality of functions?
Equality of functions?
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...
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.
Re: Equality of functions?
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:
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):
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
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
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
- edgar
Re: Equality of functions?
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?
As far as I understand your answer, there is no inbuilt standard "code walker" in LISP?
To understand LISP, you must first understand LISP.
Re: Equality of functions?
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
Re: Equality of functions?
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). Temporary mirrors of aferomentioned: CLHS and a dark version.
Re: Equality of functions?
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))...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?
Re: Equality of functions?
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). Temporary mirrors of aferomentioned: CLHS and a dark version.
Re: Equality of functions?
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.
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: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))...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?
To understand LISP, you must first understand LISP.
Re: Equality of functions?
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?
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
Currently I'm planning a Scheme compiler :p
Re: Equality of functions?
Of course your add1 and add2 are not "language equal", their identity in the real world is based onsylwester 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 #+))
commutativity law of arithmetics.
To understand LISP, you must first understand LISP.