I'm learning lisp. I'm working my way through Peter Norvig's
_Paradigms of Artificial Intelligence_. As an exercise I'm
implementing the simple grammar he shows in his second chapter,
and writing tests for it. His code is:
(defun sentence () (append (noun-phrase) (verb-phrase)))
(defun noun-phrase () (append (article) (noun)))
(defun verb-phrase () (append (verb) (noun-phrase)))
(defun article () (one-of '(a the)))
(defun noun () (one-of '(man ball woman table)))
(defun verb () (one-of '(hit took saw liked)))
(defun one-of (choices)
(list (random-elt choices)))
(defun random-elt (choices)
(elt choices (random (length choices))))
I wrote this test for random-elt:
(deftest test-random-elt ()
(let ((items '(alfa bravo charlie delta echo))
(counts (make-hash-table :test #'equal))
(total 0))
; zero out counts...
(dolist (item items)
(setf (gethash item counts) 0))
; generate 50 samples, incrementing counts as we go...
(dotimes (n 50)
(incf (gethash (random-elt items) counts)))
; now confirm that all entries are > 0 and total to 50...
(dolist (item items)
(check (> (gethash item counts) 0))
(incf total (gethash item counts)))
(check (equal total 50))))
And this one for one-of:
(deftest test-one-of ()
(let ((items '(alfa bravo charlie delta echo))
(counts (make-hash-table :test #'equal))
(total 0))
; zero out counts...
(dolist (item items)
(setf (gethash (list item) counts) 0))
; generate 50 samples, incrementing counts as we go...
(dotimes (n 50)
(incf (gethash (one-of items) counts)))
; now confirm that all entries are > 0 and total to 50...
(dolist (item items)
(check (> (gethash (list item) counts) 0))
(incf total (gethash (list item) counts)))
(check (equal total 50))))
And this one for article:
(deftest test-article ()
(let ((items '(a the))
(counts (make-hash-table :test #'equal))
(total 0))
; zero out counts...
(dolist (item items)
(setf (gethash (list item) counts) 0))
; generate 50 times, incrementing counts as we go...
(dotimes (n 50)
(incf (gethash (article) counts)))
; now confirm that all entries are > 0 and total to 50...
(dolist (item items)
(check (> (gethash (list item) counts) 0))
(incf total (gethash (list item) counts)))
(check (equal total 50))))
Obviously, similar tests would follow for noun and verb.
The tests above had a lot of duplication that I wanted to remove.
With some work I changed them to:
(deftest test-random-elt ()
(test-generator
'(alfa bravo charlie delta echo)
#'(lambda (x) (random-elt x))
'(alfa bravo charlie delta echo)))
(deftest test-one-of ()
(test-generator
'( alfa bravo charlie delta echo)
#'(lambda (x) (one-of x))
'((alfa) (bravo) (charlie) (delta) (echo))))
(deftest test-article ()
(test-generator
'()
#'(lambda (x) (article))
'((a) (the))))
which are supported by:
(defun test-generator (inputs processor outputs)
(let ((counts (make-hash-table :test #'equal))
(total 0))
; zero out counts...
(dolist (item outputs)
(setf (gethash item counts) 0))
; generate 50 times, incrementing counts as we go...
(dotimes (n 50)
(incf (gethash (funcall processor inputs) counts)))
; now confirm that all entries are > 0 and total to 50...
(dolist (item outputs)
;(format t "~%~a: ~a" item (gethash item counts))
(check (> (gethash item counts) 0))
(incf total (gethash item counts)))
;(format t "~%")
(check (equal total 50))))
I consider this version a big improvement, but I don't really like
the "literal" closures I'm using in the tests.
I worked a little longer and was able to get to:
(deftest test-random-elt ()
(test-generator
'(alfa bravo charlie delta echo)
'(random-elt inputs)
'(alfa bravo charlie delta echo)))
(deftest test-one-of ()
(test-generator
'( alfa bravo charlie delta echo)
'(one-of inputs)
'((alfa) (bravo) (charlie) (delta) (echo))))
(deftest test-article ()
(test-generator
'()
'(article)
'((a) (the))))
supported by:
(defun test-generator (inputs processor-expression outputs)
(let ((processor
(coerce `(lambda (inputs) ,processor-expression)
'function))
(counts (make-hash-table :test #'equal))
(total 0))
; zero out counts...
(dolist (item outputs)
(setf (gethash item counts) 0))
; generate 50 times, incrementing counts as we go...
(dotimes (n 50)
(incf (gethash (funcall processor inputs) counts)))
; now confirm that all entries are > 0 and total to 50...
(dolist (item outputs)
;(format t "~%~a: ~a" item (gethash item counts))
(check (> (gethash item counts) 0))
(incf total (gethash item counts)))
;(format t "~%")
(check (equal total 50))))
-
This works, and has the benefit of generating the closure "once and
only
once". On the other hand, the processor-expressions I pass in are now
strictly limited to the use of "inputs" as their parameter. So, I
really don't know if this code is good lisp style. What to you think?
I also don't fully understand how to generate closures with code.
My first attempt was:
(processor #'`(lambda (inputs) ,processor-expression))
then I tried:
(processor `#'(lambda (inputs) ,processor-expression))
Finally, I stumbled onto:
(processor (coerce `(lambda (inputs) ,processor-expression)
'function))
I don't understand why I have to use coerce to convert my lambda
expression into a function. I know this indicates some fundamental
misunderstanding of closures and/or lambda expression on my part,
but I don't know what it is.
Thanks for taking the time to read this message, and thanks for
your comments and suggestions
David B. Ellis
······@randallpub.com writes:
> I also don't fully understand how to generate closures with code.
>
> My first attempt was:
>
> (processor #'`(lambda (inputs) ,processor-expression))
>
> then I tried:
>
> (processor `#'(lambda (inputs) ,processor-expression))
>
> Finally, I stumbled onto:
>
> (processor (coerce `(lambda (inputs) ,processor-expression)
> 'function))
>
> I don't understand why I have to use coerce to convert my lambda
> expression into a function. I know this indicates some fundamental
> misunderstanding of closures and/or lambda expression on my part,
> but I don't know what it is.
1- lambda is a mere symbol, used to indicate that a list (data) could be
interpreted as a function (a lambda-expression).
'(lambda (x) (1+ x)) --> (LAMBDA (X) (1+ X))
(cadr '(lambda (x) (1+ x)) --> (X)
Nothing special here, it's a symbol like any other.
Only you can use such lambda expressions as a function:
( (lambda (x) (* x x)) 2 ) --> 4
2- lambda is the name of a macro defined as:
(defmacro lambda (lambda-list &body body)
`(function (lambda ,lambda-list ,@body)))
Therefore when you try to execute what looks like a lambda-expression,
you're actually evaluating the special operator FUNCTION:
(macroexpand '(lambda (x) (* x x))) --> (FUNCTION (LAMBDA (X) (* X X)))
Don't be fooled by the printer,
#'(LAMBDA (X) (* X X)) is really: (FUNCTION (LAMBDA (X) (* X X)))
as you can verify it:
(car '#'(LAMBDA (X) (* X X))) --> FUNCTION
Now, the special operator FUNCTION takes the name of a function (a
symbol) or a list of the form (SETF x) or (LAMBDA ...) a
lambda-expression, and return the function "named" by such a
designator.
(lambda (x) (1+ x)) --> #<CLOSURE :LAMBDA (X) (1+ X)>
Note the difference with the first example where you got a list
instead of a closure object:
'(lambda (x) (1+ x)) --> (LAMBDA (X) (1+ X))
Perhaps it could be seen more clearly when written as:
(quote (lambda (x) (1+ x))) --> (LAMBDA (X) (1+ X))
(lambda (x) (1+ x)) --> #<CLOSURE :LAMBDA (X) (1+ X)>
Now, backquote is a quote. If you don't have any comma inside the
backquoted list, it's strictly equivalent to QUOTE:
`(lambda (x) (1+ x)) --> (LAMBDA (X) (1+ X))
Now, exactly why #'`(lambda ...) doesn't work should be obvious.
#'`(lambda ...) is actually (function `(lambda ...))
and since `(lambda ...) is actually (quote (lambda ...):
#'`(lambda ...) is actually (function (quote (lambda ...)))
but FUNCTION is a special operator that doesn't evaluate its argument,
and (quote (lambda ...)) is not a function designator (not a symbol,
not a list starting with SETF or LAMBDA, nada, it's only a list
starting with QUOTE.
Since you are building at run-time a s-expression eg, a list, in the
form of a lambda-expression, and you want to pass to processor a
function (eg a closure), then you have to convert this list into a
function manually using coerce.
If you had to do this a lot, you could write a #` reader-macro.
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
From: James Graves
Subject: Re: Is this a appropriate use of closures?
Date:
Message-ID: <d1erao$b9c$1@new7.xnet.com>
Cool. I had some vague uncertanties about LAMBDA, but I was not worried
enough about that to form actual questions.
Thank you for your explanation of the different meanings of LAMBDA.
I appreciate it.
James Graves
Ok, let's see if I understand.
>1- lambda is a mere symbol, used to indicate that a list (data) could
be
>interpreted as a function (a lambda-expression). .
>
> '(lambda (x) (1+ x)) --> (LAMBDA (X) (1+ X))
> (cadr '(lambda (x) (1+ x)) --> (X)
I under that a quoted list containing lambda is just data:
(deftest one ()
(check (equal '(lambda (x) (1+ x)) '(lambda (x) (1+ x)))))
0 checks failed, 1 check passed, 1 test.
and that 'x is expanded at read time into (quote x):
(deftest two ()
(check (equal '(lambda (x) (1+ x)) (quote (lambda (x) (1+
x))))))
0 checks failed, 2 checks passed, 2 tests.
I believe that this:
> ( (lambda (x) (* x x)) 2 ) --> 4
involves an expansion of the lambda MACRO. As I understand it eval
macro-expands the (lambda (x) (* x x)) above into
(function (lambda (x) (* x x))) then evaluates the function
special-form, which
returns a closure, which is then APPLYied to the rest of the original
form (2
in this case). That application returns the 4. Is this correct?
so:
(deftest three ()
(check (equal ((lambda (x) (* x x)) 2) 4)))
0 checks failed, 3 checks passed, 3 tests.
I think I'm correct that the lambda MACRO only comes into play when a
lambda expression appears as the CAR of a list to be evaluated. Is
this correct?
Here's a explicit verification of a lambda macro-expansion:
(deftest four ()
(check
(equal (macroexpand '(lambda (x) (+ x 1)))
'(function (lambda (x) (+ x 1))))))
0 checks failed, 4 checks passed, 4 tests.
If I understand what I've read in the standard then the only things
that
can be passed to the function special-form are:
symbols which have a symbol-function associated with them,
(for example, (function +))
lambda expressions,
(like (function (lambda (x) (- x))))
and lists whose car's are setf
(like (function (setf cadr)))
The reason:
(processor #'`(lambda (inputs) ,processor-expression))
could never work is that it's really
(processor (function (quote (lambda (inputs) ...))))
and quote is a special-form, it's none of the three allowable argments
to function.
So, I think I could build my code with something like:
(deftest five ()
(let* ((processor-expr '(one-of input)) ; passed in in original
(processor-lambda-as-list `(lambda (input) ,processor-expr))
(processor (coerce processor-lambda-as-list 'function)))
; processor-lambda-list just contains a list:
(check (equal processor-lambda-as-list
'(lambda (input) (one-of input))))
; but processor is a function:
(check (equal (type-of processor) 'function))))
0 checks failed, 6 checks passed, 5 tests.
That seems to work, so I think my understanding for lambdas and
function is
starting to improve.
So I could change my test to:
(defun test-generator (inputs processor-expression outputs)
(let* ((processor-lambda `(lambda (inputs)
,processor-expression))
(processor (coerce processor-lambda 'function))
(counts (make-hash-table :test #'equal))
(total 0))
; zero out counts...
(dolist (item outputs)
(setf (gethash item counts) 0))
; generate 50 times, incrementing counts as we go...
(dotimes (n 50)
(incf (gethash (funcall processor inputs) counts)))
; now confirm that all entries are > 0 and that they total
50...
(dolist (item outputs)
(format t "~%~a: ~a" item (gethash item counts))
(check (> (gethash item counts) 0))
(incf total (gethash item counts)))
(format t "~%")
(check (equal total 50))))
This test does work, but like jan, I starting to prefer:
(test-generator
'(alfa bravo charlie delta echo)
#'(lambda (inputs) (random-elt inputs))
'(alfa bravo charlie delta echo))
I just wanted to work through this to understand what Pascal said.
Thanks again for your help and comments.
David B. Ellis
From: Kent M Pitman
Subject: Re: Is this a appropriate use of closures?
Date:
Message-ID: <uis3ozmug.fsf@nhplace.com>
······@randallpub.com writes:
> I believe that this:
>
> > ( (lambda (x) (* x x)) 2 ) --> 4
>
> involves an expansion of the lambda MACRO.
No.
> As I understand it eval
> macro-expands the (lambda (x) (* x x)) above into
> (function (lambda (x) (* x x))) then evaluates the function
> special-form, which
> returns a closure, which is then APPLYied to the rest of the original
> form (2
> in this case). That application returns the 4. Is this correct?
No.
First, CL is a Lisp2, not a Lisp1. That is, it has separate namespaces
for Function and Value expressions. In (f x y z), f is functionally
evaluated and x, y, z are "normally" evaluated (or "evaluated for value").
The reason this matters is that while
(f (lambda (x) x))
involves a use of a macro, which expands as
(f (function (lambda (x) x)))
the same is not true for
((lambda (x) (+ x 2)) 2)
In this latter case, ((lambda ...) ...) is a primitive kind of expression,
a compound form called a lambda form. It has a lambda expression at its
car, but that lambda expression is primitively understood--no functional
result [what you're calling a closure] is ever created in that situation
since it would be wasteful, its only purpose being the immediate use and
then disposal of that function.
Note that (lambda (x) (* x x)) never produces a closure since it has no
free variables [at least, none in the value namespace]. It does use * free,
but * is primitively defined in the global environment, so no closure is
required. That's different than
(defun add-some (y) (lambda (x) (+ x y)))
where (funcall (add-some 3) 4) returns 7 because (add-some 3) returns
(lambda (x) (+ x y))
closed over y=3. In that case, because of the free y, you do get a closure.
> so:
>
> (deftest three ()
> (check (equal ((lambda (x) (* x x)) 2) 4)))
>
> 0 checks failed, 3 checks passed, 3 tests.
>
> I think I'm correct that the lambda MACRO only comes into play when a
> lambda expression appears as the CAR of a list to be evaluated. Is
> this correct?
Nope. It only comes into effect when a lambda expression is not in the
car of the expression. that is, for better or worse:
((lambda (x) x) (lambda (x) x))
-------------- --------------
NOT A MACRO MACRO
> Here's a explicit verification of a lambda macro-expansion:
>
> (deftest four ()
> (check
> (equal (macroexpand '(lambda (x) (+ x 1)))
> '(function (lambda (x) (+ x 1))))))
>
> 0 checks failed, 4 checks passed, 4 tests.
That's probably right, but might vary between implementations.
I'd trust more the result of macroexpand-1 than macroexpand.
It's probably the case that FUNCTION is primitive and doesn't
further macroexpand, but I wouldn't bank on it without more careful
thought than I have time for right now.
> If I understand what I've read in the standard then the only things
> that
> can be passed to the function special-form are:
Things are not "passed to" special forms. Special forms are syntax
that are present after any appropriate macro expansion has been done.
(function +) does not pass + to function. Rather, the language recognizes
(function <anything>) as a reference to <anything> in the functional
namespace as part of its primitive understanding of a thing.
That all said, you are right that the only valid holders of the cadr position
in a function special form are:
> symbols which have a symbol-function associated with them,
> (for example, (function +))
>
> lambda expressions,
> (like (function (lambda (x) (- x))))
>
> and lists whose car's are setf
> (like (function (setf cadr)))
That's right.
> The reason:
>
> (processor #'`(lambda (inputs) ,processor-expression))
>
> could never work is that it's really
>
> (processor (function (quote (lambda (inputs) ...))))
>
> and quote is a special-form,
It's not that it IS a special form. It's that it's NOT one of three
recognized kinds of things that can be in a FUNCTION special form.
> it's none of the three allowable argments
> to function.
This part is right. You just got the emphasis wrong.
> So, I think I could build my code with something like:
>
> (deftest five ()
> (let* ((processor-expr '(one-of input)) ; passed in in original
> (processor-lambda-as-list `(lambda (input) ,processor-expr))
> (processor (coerce processor-lambda-as-list 'function)))
>
> ; processor-lambda-list just contains a list:
> (check (equal processor-lambda-as-list
> '(lambda (input) (one-of input))))
>
> ; but processor is a function:
> (check (equal (type-of processor) 'function))))
Yes, although this use of COERCE is a very big hammer. It means your
executable has to have the entire interpreter and/or compiler in it in
order to make sure it can do this transformation at runtime instead of
compile time.
[I stopped here in reading and responding to your message because I've made
the terminology and efficiency points I wanted to make. I have no opinion
on the remainder of the message.]
······@randallpub.com writes:
> Ok, let's see if I understand.
>
>
> >1- lambda is a mere symbol, used to indicate that a list (data) could
> be
> >interpreted as a function (a lambda-expression). .
> >
> > '(lambda (x) (1+ x)) --> (LAMBDA (X) (1+ X))
> > (cadr '(lambda (x) (1+ x)) --> (X)
>
> I under that a quoted list containing lambda is just data:
Yes.
> [...]
> and that 'x is expanded at read time into (quote x):
Yes.
> [...]
> I believe that this:
>
> > ( (lambda (x) (* x x)) 2 ) --> 4
>
> involves an expansion of the lambda MACRO. As I understand it eval
> macro-expands the (lambda (x) (* x x)) above into
> (function (lambda (x) (* x x))) then evaluates the function
> special-form, which
> returns a closure, which is then APPLYied to the rest of the original
> form (2
> in this case). That application returns the 4. Is this correct?
No.
[55]> (defun hook (expander form env)
(format t "Now expanding: ~S~%" form)
(funcall expander form env))
HOOK
[56]> (let ((*macroexpand-hook* (function hook))) ((lambda (x) (print x)) :a))
:A
:A
[57]> (let ((*macroexpand-hook* (function hook)))
((lambda (x) (print x)) (lambda (y) (1+ y))))
Now expanding: (LAMBDA (Y) (1+ Y))
#<CLOSURE :LAMBDA (Y) (1+ Y)>
#<CLOSURE :LAMBDA (Y) (1+ Y)>
[58]>
EVAL understands directly that (lambda ...) in the CAR is a function
and doesn't need to expand the macro LAMBDA for this.
Moreover, a closure is not valid in the CAR of a function call:
[58]> (#.(lambda (x) (print x)) (lambda (y) (1+ y)))
*** - EVAL: #<CLOSURE :LAMBDA (X) (PRINT X)> is not a function name
The following restarts are available:
USE-VALUE :R1 You may input a value to be used instead.
Remember that the CAR of a function call IS NOT evaluated. It's taken
as a name (a "designator").
> I think I'm correct that the lambda MACRO only comes into play when a
> lambda expression appears as the CAR of a list to be evaluated. Is
> this correct?
No, it's the lambda symbol that is used here.
The lambda macro comes into play when lambda appears as the CAR of a
list to be evaluated.
(lambda (x) (* x x)) lambda macro is expanded
and result is evaluated.
(identity (lambda (x) (* x x))) lambda macro is expanded
and result is evaluated to be
passed as argument to IDENTITY.
(function (lambda (x) (* x x))) no macro expansion occurs.
(FUNCTION, like QUOTE doesn't
evaluates its arguments).
The anonymous function is returned.
(quote (lambda (x) (* x x))) no macro expansion occurs.
The list containing the three elements:
lambda, (x) and (* x x) is returned.
((lambda (x) (* x x)) 2) no macro expansion occurs.
(EVAL doesn't need to).
> Here's a explicit verification of a lambda macro-expansion:
>
> (deftest four ()
> (check
> (equal (macroexpand '(lambda (x) (+ x 1)))
> '(function (lambda (x) (+ x 1))))))
>
> 0 checks failed, 4 checks passed, 4 tests.
>
> If I understand what I've read in the standard then the only things
> that
> can be passed to the function special-form are:
>
> symbols which have a symbol-function associated with them,
> (for example, (function +))
>
> lambda expressions,
> (like (function (lambda (x) (- x))))
>
> and lists whose car's are setf
> (like (function (setf cadr)))
>
> The reason:
>
> (processor #'`(lambda (inputs) ,processor-expression))
>
> could never work is that it's really
>
> (processor (function (quote (lambda (inputs) ...))))
>
> and quote is a special-form, it's none of the three allowable argments
> to function.
Yes.
> So, I think I could build my code with something like:
>
> (deftest five ()
> (let* ((processor-expr '(one-of input)) ; passed in in original
> (processor-lambda-as-list `(lambda (input) ,processor-expr))
> (processor (coerce processor-lambda-as-list 'function)))
>
> ; processor-lambda-list just contains a list:
> (check (equal processor-lambda-as-list
> '(lambda (input) (one-of input))))
>
> ; but processor is a function:
> (check (equal (type-of processor) 'function))))
>
> 0 checks failed, 6 checks passed, 5 tests.
>
> That seems to work, so I think my understanding for lambdas and
> function is
> starting to improve.
>
> So I could change my test to:
> (defun test-generator (inputs processor-expression outputs)
> (let* ((processor-lambda `(lambda (inputs)
> ,processor-expression))
> (processor (coerce processor-lambda 'function))
> (counts (make-hash-table :test #'equal))
> (total 0))
>
> ; zero out counts...
> (dolist (item outputs)
> (setf (gethash item counts) 0))
>
> ; generate 50 times, incrementing counts as we go...
> (dotimes (n 50)
> (incf (gethash (funcall processor inputs) counts)))
>
> ; now confirm that all entries are > 0 and that they total
> ; 50...
> (dolist (item outputs)
> (format t "~%~a: ~a" item (gethash item counts))
> (check (> (gethash item counts) 0))
> (incf total (gethash item counts)))
> (format t "~%")
> (check (equal total 50))))
>
> This test does work, but like jan, I starting to prefer:
>
> (test-generator
> '(alfa bravo charlie delta echo)
> #'(lambda (inputs) (random-elt inputs))
> '(alfa bravo charlie delta echo))
>
> I just wanted to work through this to understand what Pascal said.
>
> Thanks again for your help and comments.
>
> David B. Ellis
>
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we. -- Georges W. Bush
From: jan
Subject: Re: Is this a appropriate use of closures?
Date:
Message-ID: <1xaen6kp.fsf@laptop.lan>
······@randallpub.com writes:
> (defun test-generator (inputs processor outputs)
> (let ((counts (make-hash-table :test #'equal))
> (total 0))
> ...
> (dotimes (n 50)
> (incf (gethash (funcall processor inputs) counts)))
> ...
> ))
> (defun test-generator (inputs processor-expression outputs)
> (let ((processor
> (coerce `(lambda (inputs) ,processor-expression)
> 'function))
> (counts (make-hash-table :test #'equal))
> (total 0))
> ...
> (dotimes (n 50)
> (incf (gethash (funcall processor inputs) counts)))
> ...
> ))
> This works, and has the benefit of generating the closure "once and
> only once".
Both definitions generate the closure only once.
> On the other hand, the processor-expressions I pass in are now
> strictly limited to the use of "inputs" as their parameter.
Both definitions of processor require `inputs' as a parameter due to
the use of `funcall'. Compare `funcall' with `apply'.
> So, I really don't know if this code is good lisp style. What to you
> think?
I prefer the first definition. The intention of the code is more
clear.
Here the second argument is clearly a function:
(test-generator
'(alfa bravo charlie delta echo)
#'(lambda (inputs) (random-elt inputs))
'(alfa bravo charlie delta echo))
Whereas here the second argument is just another list:
(test-generator
'(alfa bravo charlie delta echo)
'(random-elt inputs)
'(alfa bravo charlie delta echo))
Also, take note of the difference between (list 'alfa) and '(alfa).
This will become important when writing tests for destructive
functions.
> I also don't fully understand how to generate closures with code.
See Pascal's reply for this.
--
jan