Functions as data
Andy Venikov
I'm still trying to grapple with the lisp's "functions as data" concept.
I've been reading some blogs and I found this one:
http://www.lurklurk.org/cpp_clos.html
I think it's a very good article. Unfortunately, I'm having problems
with some lisp code under the "function objects" item.
The author is trying to show how you can return a raw list that later
may be interpreted as a function call. Here's the relevant code:
(defun f (op i)
(funcall op i))
(defun addn (n)
(list 'lambda '(x) (list '+ 'n n)))
;;This is supposed to evaluate to 10
(f (addn 3) 7)
Now, the problem is that neither SBCL no CLISP would accept this.
Maybe there's just a syntax error. But I couldn't fix it.
But even if the syntax error could be fixed, here's what
I'm really baffled at: the return from (addn 3) will return an S
expression (lambda (x) (+ n 3)). This s-expression needs to be evaluated
before f can treat it as a function. Right? It feels like a call to
"eval" is missing somewhere. I re-wrote it like this:
(f (eval (addn 3)) 7)
And it seems to work. But now I'm afraid that I'm missing something
important. The call to eval (as I understand) will basically invoke the
interpreter (or compiler for compiled code) to interpret (or compile)
S-expression (lambda (x) (+ n 3)). But in author's original code, it
looks like that S-expression can be understood directly, without
interpreter's (or compiler's) help. If that were true, it would be truly
amazing and I'd have to change some of my world-concepts ...
So, what gives?
Thanks,
Andy.
vanekl
CL-USER> (lisp-implementation-type)
"Clozure Common Lisp"
CL-USER> (lisp-implementation-version)
"Version 1.6-dev-r14370M-trunk (LinuxX8632)"
CL-USER> (defun ff (op i)
(funcall op i))
FF
CL-USER> (defun addn (n)
(lambda (x) (+ x n)))
ADDN
CL-USER> (ff 'addn 7)
#<COMPILED-LEXICAL-CLOSURE (:INTERNAL ADDN) #x1A7E72BE>
CL-USER> (ff (addn 3) 7)
10
Andy Venikov
<snip>
>> (defun f (op i)
>> (funcall op i))
>>
>> (defun addn (n)
>> (list 'lambda '(x) (list '+ 'n n)))
>>
>> ;;This is supposed to evaluate to 10
>> (f (addn 3) 7)
<snip>
> CL-USER> (lisp-implementation-type)
> "Clozure Common Lisp"
> CL-USER> (lisp-implementation-version)
> "Version 1.6-dev-r14370M-trunk (LinuxX8632)"
> CL-USER> (defun ff (op i)
> (funcall op i))
> FF
> CL-USER> (defun addn (n)
> (lambda (x) (+ x n)))
> ADDN
> CL-USER> (ff 'addn 7)
> #<COMPILED-LEXICAL-CLOSURE (:INTERNAL ADDN) #x1A7E72BE>
> CL-USER> (ff (addn 3) 7)
> 10
But isn't this code different from the original?
In your case function ff returns the result of evaluating S-expression
(lambda (x) (+ x n)) which will be a function-form. In the original
version, addn was returning the S-expression unevaluated. Someone has to
evaluate it to construct a function object, right?
Thanks,
Andy.
vanekl
Yes, you're right, the code is a bit different. Instead of evaluating
a function, it's trying to evaluate a CONS (list).
So, instead of creating a function, create a list:
CL-USER> (defun addn (n)
;; (lambda (x) (+ x n)))
(list 'lambda '(x) (list '+ 'x n)))
ADDN
CL-USER> (ff 'addn 7)
(LAMBDA (X) (+ X 7))
CL-USER> (ff (addn 3) 7)
; Evaluation aborted on #<TYPE-ERROR #x1A7B00F6>.
CL-USER> (type-of (addn 3))
CONS
CL-USER> (ff (coerce (addn 3) 'function) 7)
10
Now it works, after coercing the list to a function.
vanekl
Or you could make it a little more elegant and rewrite 'ff':
CL-USER> (defun ff (op i)
(funcall (if (typep op 'function)
op
(coerce op 'function))
i))
FF
Andy Venikov
<snip>
>> But isn't this code different from the original?
>> In your case function ff returns the result of evaluating S-expression
>> (lambda (x) (+ x n)) which will be a function-form. In the original
>> version, addn was returning the S-expression unevaluated. Someone has to
>> evaluate it to construct a function object, right?
>>
>> Thanks,
>> Andy.
>
> Yes, you're right, the code is a bit different. Instead of evaluating
> a function, it's trying to evaluate a CONS (list).
>
> So, instead of creating a function, create a list:
> CL-USER> (defun addn (n)
> ;; (lambda (x) (+ x n)))
> (list 'lambda '(x) (list '+ 'x n)))
> ADDN
> CL-USER> (ff 'addn 7)
> (LAMBDA (X) (+ X 7))
> CL-USER> (ff (addn 3) 7)
> ; Evaluation aborted on #<TYPE-ERROR #x1A7B00F6>.
> CL-USER> (type-of (addn 3))
> CONS
> CL-USER> (ff (coerce (addn 3) 'function) 7)
> 10
>
> Now it works, after coercing the list to a function.
Thanks for the reply.
Interesting, will "coercing" invoke an eval?
vanekl
No, it just changes a list into something that can be evaluated by
'funcall'.
'funcall' is where most of the heavy lifting (evaluation) is being
performed.
Andy Venikov
Oh, I see. So basically funcall will have to interpret the S-expression
as a function (or invoke a compiler in the compiled code)?
Does it mean that one should be careful with it if performance matters?
vanekl
No, funcall is very fast. It's roughly as fast as making any other
function call.
Paul Donnelly
> (defun f (op i)
> (funcall op i))
>
> (defun addn (n)
> (list 'lambda '(x) (list '+ 'n n)))
>
> ;;This is supposed to evaluate to 10
> (f (addn 3) 7)
As far as I can tell, the author got confused and wrote non-conforming
code.
(defun addn (n)
(lambda (x) (+ x n)))
(funcall (addn 3) 3)
seems more reasonable to me.
Pascal J. Bourguignon
> On 10/25/2010 7:25 PM, vanekl wrote:
>> On Oct 25, 7:23 pm, Andy Venikov<swojchelo...@gmail.com> wrote:
>>> On 10/25/2010 7:14 PM, vanekl wrote:
>>> <snip>
>>>> Now it works, after coercing the list to a function.
>>>
>>> Thanks for the reply.
>>> Interesting, will "coercing" invoke an eval?
>>
>> No, it just changes a list into something that can be evaluated by
>> 'funcall'.
>> 'funcall' is where most of the heavy lifting (evaluation) is being
>> performed.
>
> Oh, I see. So basically funcall will have to interpret the
> S-expression as a function (or invoke a compiler in the compiled
> code)?
> Does it mean that one should be careful with it if performance matters?
FUNCALL calls the function, using APPLY.
APPLY may just jump to the function code if it's compiled to native code,
or run byte-code virtual machine interpreter if it's compiled to bytecode,
or run the interpreter if the function is to be interpreted.
COERCE may call COMPILE to generate a compiled version of the function,
or may just implement the minimal-compilation specified, or may defer it
to the interpreter.
So in terms of performance, when using COERCE, the repartition depends
entirely on the implementation.
If you know that your implementation has a compiler (they almost all of
them have one), then you could use COMPILE instead of COERCE, to ensure
an early compilation.
And of course, if you don't call repeatitively your function, it might
be better to interpreter it than to have the overhead of compiling it.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Pascal J. Bourguignon
In old lisps, and eg. in emacs lisp, it is possible to funcall a list
starting with lambda.
In emacs:
(eval '(funcall '(lambda () (insert "Hello!\n"))))
Hello!
nil
Paul Donnelly
Out of curiousity, are there any Common Lisps that provide this?
Pascal J. Bourguignon
A Common Lisp _implementation_ could provide this feature as an
extension.
But:
(eval '(funcall '(lambda () ...)))
are not conformant Common Lisp forms.
Of the four implementations I have on my system, only ECL considers the
lambda form to be a function.
[pjb@kuiper :0.0 lisp]$ clall '(eval (quote (funcall (quote (lambda () (+ 1 2))))))'
========================================================================
Clozure Common Lisp Version 1.5 (LinuxX8664)
Evaluation of
(EVAL '(FUNCALL '(LAMBDA NIL (+ 1 2))))
produced nothing on *STANDARD-OUTPUT*
produced nothing on *ERROR-OUTPUT*
produced the following error:
#<TYPE-ERROR #x3020005D3E9D>
(LAMBDA NIL (+ 1 2)) is not of type (OR SYMBOL FUNCTION), and can't be FUNCALLed or APPLYed
produced the following values:
-->
========================================================================
CLISP 2.48 (2009-07-28) (built 3496707691) (memory 3496707846)
Evaluation of
(EVAL '(FUNCALL '(LAMBDA NIL (+ 1 2))))
produced nothing on *STANDARD-OUTPUT*
produced nothing on *ERROR-OUTPUT*
produced the following error:
#<SIMPLE-TYPE-ERROR #x000333FA22D0>
FUNCALL: argument (LAMBDA NIL (+ 1 2)) is not a function.
To get a function in the current environment, write (FUNCTION ...).
To get a function in the global environment, write (COERCE '... 'FUNCTION).
produced the following values:
-->
;;; Loading "/tmp/clall-4611.lisp"
========================================================================
ECL 9.12.3
Evaluation of
(EVAL '(FUNCALL '(LAMBDA () (+ 1 2))))
produced nothing on *STANDARD-OUTPUT*
produced nothing on *ERROR-OUTPUT*
produced no error
produced the following values:
--> 3
; loading system definition from
; /usr/share/common-lisp/systems/asdf-binary-locations.asd into
; #<PACKAGE "ASDF0">
; registering #<SYSTEM ASDF-BINARY-LOCATIONS {1002BFA1B1}> as
; ASDF-BINARY-LOCATIONS
========================================================================
SBCL 1.0.19-gentoo
Evaluation of
(EVAL '(FUNCALL '(LAMBDA () (+ 1 2))))
produced nothing on *STANDARD-OUTPUT*
produced nothing on *ERROR-OUTPUT*
produced the following error:
#<TYPE-ERROR {1002B6CE61}>
The value (LAMBDA () (+ 1 2)) is not of type (OR FUNCTION SYMBOL).
produced the following values:
-->
========================================================================
Tim Bradshaw
>
> Thanks for the reply.
> Interesting, will "coercing" invoke an eval?
sort-of. What it will do is look for either a symbol (in which case it
will return the global function definition) or a list whose first
element is LAMBDA (in which case it will return a lexical closure in
the null environment). The second case can cause arbitrary evaluation
to happen at the time COERCE is called, I am pretty sure (something
like (coerce '(lambda () (load-time-value (progn (print "hi") 1)))) I
think is an example of this).
However, what you are thinking may be that it just evaluates its
argument to get a function, and that's not the case. It happens, now,
to be the case that LAMBDA has a macro definition which means that
(lambda ...) constructs a function, but COERCE doesn't care about that,
and it worked before LAMBDA had this definition, which is a relatively
late addition to CL.
The definition of what it does can be found here:
http://www.lispworks.com/documentation/HyperSpec/Body/f_coerce.htm.
Rob Warnock
+---------------
| Andy Venikov said:
| > Interesting, will "coercing" invoke an eval?
|
| sort-of. What it will do is look for either a symbol (in which case it
| will return the global function definition) or a list whose first
| element is LAMBDA (in which case it will return a lexical closure in
| the null environment). The second case can cause arbitrary evaluation
| to happen at the time COERCE is called, I am pretty sure (something
| like (coerce '(lambda () (load-time-value (progn (print "hi") 1)))) I
| think is an example of this).
Minor nit to avoid confusing OP: the COERCE needs a 2nd arg
of 'FUNCTION here:
cmu> (coerce '(lambda () (load-time-value (progn (print "hi") 1)))
'function)
#<Interpreted Function (LAMBDA () (LOAD-TIME-VALUE #)) {489A2509}>
cmu> (funcall *)
"hi"
1
cmu> (funcall **)
1
cmu>
Note that the second FUNCALL didn't print "hi", since CMUCL
[which I'm using above] actually does very little during the
COERCE [it likewise does very little during the execution of
an interpreted DEFUN], delaying "conversion" [minimal compilation]
of the LAMBDA form to full internal interpreter form until the
first time the function is called. It is during this "conversion"
that the LOAD-TIME-VALUE was evaluated, hence the printing of "hi"
during the first FUNCALL and not the second.
Now let's actually compile it:
cmu> (compile nil ***)
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
"hi"
#<Function "LAMBDA NIL" {489B3021}>
NIL
NIL
cmu> (funcall *)
1
cmu> (funcall **)
1
cmu>
Note that the function is re-converted during full compilation
to native code, hence the printing of "hi" during compilation
and *not* during the first or second FUNCALL of the result.
You may very well get different results [by which I mean when
"hi" gets printed or not] in other CL implementations.
-Rob
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Tim Bradshaw
> You may very well get different results [by which I mean when
> "hi" gets printed or not] in other CL implementations.
Yes, I'm sure that is correct.
Captain Obvious
??>> 'funcall'.
??>> 'funcall' is where most of the heavy lifting (evaluation) is being
??>> performed.
I don't think it is correct...
AV> Oh, I see. So basically funcall will have to interpret the S-expression
AV> as a function (or invoke a compiler in the compiled code)?
No, actually funcall is a very simple operation like CPU's `call`
instruction -- it just tells execution engine to start executing function at
certain address (with certain arguments).
The rest depends on execution engine.
I guess for implementation which work with native code funcall will be
compiled to an instruction like CALL or JMP (with additional handling of
parameters and return values, of course).
And for bytecode interpreter it will do analogous thing...
While it is theoretically possible that implementation uses just-in-time
compilation strategy, it doesn't really mean that funcall itself is
expensive.
Conceptually, you can think that (coerce ... 'function), (compile ...) or
(eval ...) do "the magic" to convert code to function.
How it works in practice depends on implementation.
AV> Does it mean that one should be careful with it if performance
AV> matters?
No, performance overhead is very low -- like an additional indirection
overhead, if any...
If you care about performance maybe it is better to call (compile ...)
instead of (coerce ... 'function).
In some implementations they are equivalent, but in other ones compiled
functions work a lot faster.
Captain Obvious
CO> compiled to an instruction like CALL or JMP (with additional handling
CO> of parameters and return values, of course).
Here's, for example, listings from SBCL:
CL-USER> (defun my-funcall (x)
(declare (optimize (speed 3))
(function x))
(funcall x))
MY-FUNCALL
CL-USER> (disassemble 'my-funcall)
; 0B4C1AA9: 31C9 XOR ECX, ECX ;
no-arg-parsing entry point
; AB: FF75F8 PUSH DWORD PTR [EBP-8]
; AE: FF60FF JMP DWORD PTR [EAX-1]
; B1: 90 NOP
...
So if it knows that parameter x is a function it just does JMP.
If it does not know that it has to call SB-KERNEL:%COERCE-CALLABLE-TO-FUN
first to get address of the function:
; in: LAMBDA NIL
; (FUNCALL X)
; --> SB-C::%FUNCALL THE
; ==>
; (SB-KERNEL:%COERCE-CALLABLE-TO-FUN FUNCTION)
;
; note: unable to
; optimize away possible call to FDEFINITION at runtime
; due to type uncertainty:
; The first argument is a (OR FUNCTION SYMBOL), not a FUNCTION.
; 0B5A6F1F: 8BC2 MOV EAX, EDX ;
no-arg-parsing entry point
; 21: 2407 AND AL, 7
; 23: 3C05 CMP AL, 5
; 25: 7416 JEQ L0
; 27: 81FA0B001001 CMP EDX, 17825803
; 2D: 740E JEQ L0
; 2F: 8BC2 MOV EAX, EDX
; 31: 2407 AND AL, 7
; 33: 3C07 CMP AL, 7
; 35: 752C JNE L2
; 37: 807AF93E CMP BYTE PTR [EDX-7], 62
; 3B: 7526 JNE L2
; 3D: L0: 8BDC MOV EBX, ESP
; 3F: 83EC0C SUB ESP, 12
; 42: 8B05F06E5A0B MOV EAX, [#xB5A6EF0] ;
#<FDEFINITION object for SB-KERNEL:%COERCE-CALLABLE-TO-FUN>
; 48: B904000000 MOV ECX, 4
; 4D: 896BFC MOV [EBX-4], EBP
; 50: 8BEB MOV EBP, EBX
; 52: FF5005 CALL DWORD PTR [EAX+5]
; 55: 7302 JNB L1
; 57: 8BE3 MOV ESP, EBX
; 59: L1: 8BC2 MOV EAX, EDX
; 5B: 31C9 XOR ECX, ECX
; 5D: FF75F8 PUSH DWORD PTR [EBP-8]
; 60: FF60FF JMP DWORD PTR [EAX-1]
And then you see same JMP.
Mark Wooding
> In old lisps, and eg. in emacs lisp, it is possible to funcall a list
> starting with lambda.
This was once true in Common Lisp: CLtL 2.13 says (in a section marked
with change bars):
: A /function/ is anything that may be correctly given to the |funcall|
: or |apply| function, and is to be executed as code when arguments are
: supplied. ... A lambda-expression (a list whose car is the symbol
: |lambda|) may serve as a function.
-- [mdw]