Hi all,
I am just getting into Lisp and am fascinated by macros. I read Paul
Graham's ANSI Common Lisp book and have bumped into the following:
According to the book if x evaluates to a which evaluates to 1 and y
evaluates to b which evaluates to 2, then the following backquoted
expression:
``(w ,x ,,y)
should evaluate to
(w a 2).
However if I check this in Clisp:
(setf x 'a y 'b)
(setf a 1 b 2)
``(w ,x ,,y)
the result is (LIST 'W X B)
My question is how do I force Clisp to do 'multiple' evaluation inside
a backquoted expression? (in my example y should first be evaluated to
b, and b to 2). Could someone explain me how this happens or point me
to a document where this is explained in detail?
Thank you,
Balint Erdi
On Feb 25, 10:26 am, "erdibalint" <··········@gmail.com> wrote:
> Hi all,
>
> I am just getting into Lisp and am fascinated by macros. I read Paul
> Graham's ANSI Common Lisp book and have bumped into the following:
>
> According to the book if x evaluates to a which evaluates to 1 and y
> evaluates to b which evaluates to 2, then the following backquoted
> expression:
>
> ``(w ,x ,,y)
>
> should evaluate to
>
> (w a 2).
What Paul Graham is writing here is not strictly true in a pedantic
sense. Backquotes do not evaluate, they expand. Much of the time when
working with backquotes, we think forward to what the evaluation will
be after the right number of rounds.
Evaluation is what is done to the output of the backquote. It is the
same evaluation that would be done to any other expression written in
the same place.
When the expanded backquote is evaluated, as a whole, that is when the
evaluation inside the backquote takes place according to the semantics
of the backquote.
So for instance:
(loop for x below 10 collecting `(= x ,x))
what do you get? The backquote is evaluated ten times, each time with
a different value of X. But it is not expanded ten times; what is
evaluated ten times is the expression that is produced by the
expansion of the backquote.
The backquote is just a code generator which gives you a nice notation
for constructing complicated nested lists. You give a picture of what
you want, with the variant bits annotated with unquotes and splices.
Without backquote, we would write the equivalent:
(loop for x below 10 collecting (list '= x))
The backquote `(x ,x) gets one evaluation round for the same reasons
that (list '= x) also gets one evaluation round.
> However if I check this in Clisp:
>
> (setf x 'a y 'b)
> (setf a 1 b 2)
> ``(w ,x ,,y)
>
> the result is (LIST 'W X B)
Right, because ``(x ,x ,,y) behaves a lot like:
(list 'list ''w 'x y)
When you evaluate that you get
(LIST 'W X B)
This is a doubly-indirected code generation. You're generating code
which generates code which generates a list structure.
That's what you are expressing by backquoting a backquote. By
backquoting the backquote, you are requesting that the evaluation of
the inner backquote should be suppressed---except for constituents
which are doubly unquoted! And that's exactly what happens. Evaluation
of the (expansion of) the inner backquote is suppressed, and so you
get the expansion itself: (LIST 'W X B) where the doubly unquoted ,,y
is reduced to the value of Y as it resolved in the context of the
first evaluation round.
> My question is how do I force Clisp to do 'multiple' evaluation inside
> a backquoted expression?
To recap, there isn't any evaluation done by the backquote, only
expansion (generation of code). All of the evaluation happens when
normal evaluation is applied to the expansion, just like it would be
to any other expression.
There isn't any mode in Common Lisp or CLISP which would cause normal
evaluation to be re-applied to an expression two or more times.
You can arrange for it through a cascade of macro-expansion, as in
macro-generating macros, or request it by explicit use of EVAL.
On Feb 25, 12:24 pm, "Kaz Kylheku" <········@gmail.com> wrote:
> On Feb 25, 10:26 am, "erdibalint" <··········@gmail.com> wrote:
>
> > Hi all,
>
> > I am just getting into Lisp and am fascinated by macros. I read Paul
> > Graham's ANSI Common Lisp book and have bumped into the following:
>
> > According to the book if x evaluates to a which evaluates to 1 and y
> > evaluates to b which evaluates to 2, then the following backquoted
> > expression:
>
> > ``(w ,x ,,y)
>
> > should evaluate to
>
> > (w a 2).
>
> What Paul Graham is writing here is not strictly true in a pedantic
> sense.
And thanks to Andras Simon for pointing out that it isn't at all what
P. G. wrote.
In article <························@s48g2000cws.googlegroups.com>,
"Kaz Kylheku" <········@gmail.com> wrote:
> On Feb 25, 10:26 am, "erdibalint" <··········@gmail.com> wrote:
> > Hi all,
> >
> > I am just getting into Lisp and am fascinated by macros. I read Paul
> > Graham's ANSI Common Lisp book and have bumped into the following:
> >
> > According to the book if x evaluates to a which evaluates to 1 and y
> > evaluates to b which evaluates to 2, then the following backquoted
> > expression:
> >
> > ``(w ,x ,,y)
> >
> > should evaluate to
> >
> > (w a 2).
>
> What Paul Graham is writing here is not strictly true in a pedantic
> sense. Backquotes do not evaluate, they expand. Much of the time when
> working with backquotes, we think forward to what the evaluation will
> be after the right number of rounds.
>
> Evaluation is what is done to the output of the backquote. It is the
> same evaluation that would be done to any other expression written in
> the same place.
>
> When the expanded backquote is evaluated, as a whole, that is when the
> evaluation inside the backquote takes place according to the semantics
> of the backquote.
In particular, backquote is most often used in macro definitions. After
a macro is expanded, the resulting form will be evaluated (or it will be
compiled into code that will perform that evaluation when the function
containing the macro is eventually called). So if you used that
backquote expression in a macro, and then invoked the macro such that
X=>A=>1 and Y=>B=>2, the effect will be as if it had been (w a 2).
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Thank you very much for your quick and thorough answer.
In defense of Paul Graham, taking a second look, he does not use the
word "evaluate" in the context of ``(w ,x ,,y) should evaluate to (w
a 2), it was my fault (thanks to Andr�s for pointing this out). In
fact, this misunderstanding coupled with your excellent explanation
takes me further down the road of a beautiful world (the world of Lisp
and macros) of which I only stand at the beginning but eager to take
the journey. Thank you for helping me on my way :)
B�lint
Kaz Kylheku �rta:
> On Feb 25, 10:26 am, "erdibalint" <··········@gmail.com> wrote:
> > Hi all,
> >
> > I am just getting into Lisp and am fascinated by macros. I read Paul
> > Graham's ANSI Common Lisp book and have bumped into the following:
> >
> > According to the book if x evaluates to a which evaluates to 1 and y
> > evaluates to b which evaluates to 2, then the following backquoted
> > expression:
> >
> > ``(w ,x ,,y)
> >
> > should evaluate to
> >
> > (w a 2).
>
> What Paul Graham is writing here is not strictly true in a pedantic
> sense. Backquotes do not evaluate, they expand. Much of the time when
> working with backquotes, we think forward to what the evaluation will
> be after the right number of rounds.
>
> Evaluation is what is done to the output of the backquote. It is the
> same evaluation that would be done to any other expression written in
> the same place.
>
> When the expanded backquote is evaluated, as a whole, that is when the
> evaluation inside the backquote takes place according to the semantics
> of the backquote.
>
> So for instance:
>
> (loop for x below 10 collecting `(= x ,x))
>
> what do you get? The backquote is evaluated ten times, each time with
> a different value of X. But it is not expanded ten times; what is
> evaluated ten times is the expression that is produced by the
> expansion of the backquote.
>
> The backquote is just a code generator which gives you a nice notation
> for constructing complicated nested lists. You give a picture of what
> you want, with the variant bits annotated with unquotes and splices.
>
> Without backquote, we would write the equivalent:
>
> (loop for x below 10 collecting (list '= x))
>
> The backquote `(x ,x) gets one evaluation round for the same reasons
> that (list '= x) also gets one evaluation round.
>
> > However if I check this in Clisp:
> >
> > (setf x 'a y 'b)
> > (setf a 1 b 2)
> > ``(w ,x ,,y)
> >
> > the result is (LIST 'W X B)
>
> Right, because ``(x ,x ,,y) behaves a lot like:
>
> (list 'list ''w 'x y)
>
> When you evaluate that you get
>
> (LIST 'W X B)
>
> This is a doubly-indirected code generation. You're generating code
> which generates code which generates a list structure.
>
> That's what you are expressing by backquoting a backquote. By
> backquoting the backquote, you are requesting that the evaluation of
> the inner backquote should be suppressed---except for constituents
> which are doubly unquoted! And that's exactly what happens. Evaluation
> of the (expansion of) the inner backquote is suppressed, and so you
> get the expansion itself: (LIST 'W X B) where the doubly unquoted ,,y
> is reduced to the value of Y as it resolved in the context of the
> first evaluation round.
>
> > My question is how do I force Clisp to do 'multiple' evaluation inside
> > a backquoted expression?
>
> To recap, there isn't any evaluation done by the backquote, only
> expansion (generation of code). All of the evaluation happens when
> normal evaluation is applied to the expansion, just like it would be
> to any other expression.
>
> There isn't any mode in Common Lisp or CLISP which would cause normal
> evaluation to be re-applied to an expression two or more times.
>
> You can arrange for it through a cascade of macro-expansion, as in
> macro-generating macros, or request it by explicit use of EVAL.
Ok, so I have a seemingly simple task to accomplish:
A macro has to be defined that takes a number n followed by one or
more expressions,
and returns the value of the nth expression, so:
(let ((n 2))
(nth-expr n (/ 1 0) (+ 1 2) (/ 1 0)))
should return 3.
My attempt:
(defmacro nth-expr (n &body exprs)
(let ((g (gensym)))
`(let ((,g ,n))
(if (> ,g ,(length exprs))
nil
(elt ',exprs (1- ,g))))))
which returns the nth expression, but not its value. So in theory I
should only turn evaluation on inside the last expression in the
defmacro but that leads to other problems. Of course I could always
wrap an eval around that one, so the last line becomes (eval (elt
',exprs (1- ,g))))))) but that seems very unprofessional. But then how
do I do this?
Thank you,
B�lint
Kaz Kylheku �rta:
> On Feb 25, 10:26 am, "erdibalint" <··········@gmail.com> wrote:
> > Hi all,
> >
> > I am just getting into Lisp and am fascinated by macros. I read Paul
> > Graham's ANSI Common Lisp book and have bumped into the following:
> >
> > According to the book if x evaluates to a which evaluates to 1 and y
> > evaluates to b which evaluates to 2, then the following backquoted
> > expression:
> >
> > ``(w ,x ,,y)
> >
> > should evaluate to
> >
> > (w a 2).
>
> What Paul Graham is writing here is not strictly true in a pedantic
> sense. Backquotes do not evaluate, they expand. Much of the time when
> working with backquotes, we think forward to what the evaluation will
> be after the right number of rounds.
>
> Evaluation is what is done to the output of the backquote. It is the
> same evaluation that would be done to any other expression written in
> the same place.
>
> When the expanded backquote is evaluated, as a whole, that is when the
> evaluation inside the backquote takes place according to the semantics
> of the backquote.
>
> So for instance:
>
> (loop for x below 10 collecting `(= x ,x))
>
> what do you get? The backquote is evaluated ten times, each time with
> a different value of X. But it is not expanded ten times; what is
> evaluated ten times is the expression that is produced by the
> expansion of the backquote.
>
> The backquote is just a code generator which gives you a nice notation
> for constructing complicated nested lists. You give a picture of what
> you want, with the variant bits annotated with unquotes and splices.
>
> Without backquote, we would write the equivalent:
>
> (loop for x below 10 collecting (list '= x))
>
> The backquote `(x ,x) gets one evaluation round for the same reasons
> that (list '= x) also gets one evaluation round.
>
> > However if I check this in Clisp:
> >
> > (setf x 'a y 'b)
> > (setf a 1 b 2)
> > ``(w ,x ,,y)
> >
> > the result is (LIST 'W X B)
>
> Right, because ``(x ,x ,,y) behaves a lot like:
>
> (list 'list ''w 'x y)
>
> When you evaluate that you get
>
> (LIST 'W X B)
>
> This is a doubly-indirected code generation. You're generating code
> which generates code which generates a list structure.
>
> That's what you are expressing by backquoting a backquote. By
> backquoting the backquote, you are requesting that the evaluation of
> the inner backquote should be suppressed---except for constituents
> which are doubly unquoted! And that's exactly what happens. Evaluation
> of the (expansion of) the inner backquote is suppressed, and so you
> get the expansion itself: (LIST 'W X B) where the doubly unquoted ,,y
> is reduced to the value of Y as it resolved in the context of the
> first evaluation round.
>
> > My question is how do I force Clisp to do 'multiple' evaluation inside
> > a backquoted expression?
>
> To recap, there isn't any evaluation done by the backquote, only
> expansion (generation of code). All of the evaluation happens when
> normal evaluation is applied to the expansion, just like it would be
> to any other expression.
>
> There isn't any mode in Common Lisp or CLISP which would cause normal
> evaluation to be re-applied to an expression two or more times.
>
> You can arrange for it through a cascade of macro-expansion, as in
> macro-generating macros, or request it by explicit use of EVAL.
On Feb 26, 10:16 am, "erdibalint" <··········@gmail.com> wrote:
> Ok, so I have a seemingly simple task to accomplish:
>
> A macro has to be defined that takes a number n followed by one or
> more expressions,
> and returns the value of the nth expression, so:
Make that: returns the /value(s)/ of the nth expression!
What if N is out of range? Error signaled? NIL?
> (let ((n 2))
> (nth-expr n (/ 1 0) (+ 1 2) (/ 1 0)))
In Common Lisp, we already have:
(prog1 ...) returns the first
(prog2 ...) returns the second
(progn ...) returns the last
But, alas, these are quite different from what you are implementing,
because they evaluate all of the expressions, and differ only in which
one's values they return.
> should return 3.
>
> My attempt:
>
> (defmacro nth-expr (n &body exprs)
> (let ((g (gensym)))
> `(let ((,g ,n))
> (if (> ,g ,(length exprs))
> nil
> (elt ',exprs (1- ,g))))))
One possibility is to compile the form into a case.
(case n
(0 first-expr)
(1 second-expr)
...
(otherwise ...))
The nice thing about this is that the compiler can then perhaps apply
some optimizations that are specific to CASE.
(defmacro nth-expr (n-expr &rest exprs)
`(case ,n-expr
,@(loop for expr in exprs
for i from 0
collect `(,i ,expr))
(otherwise nil)))
> So in theory I
> should only turn evaluation on inside the last expression in the
> defmacro but that leads to other problems.
But in practice there is no such switch.
The problem is not that insufficient evaluation is applied, but rather
that ELT is a function and not a control construct. You are relying on
compiling your construct to ELT, but ELT cannot express it.
You cannot write the code by hand using ELT. If /you/ cannot write it
that way, the macro cannot either.
You turned the expressions into a big literal list. The value of N is
used to pull out the N-th element of the literal using ELT. That
element is a piece of source code, however, which requires evaluation.
There is no way to get that to happen without calling the evaluator,
or dynamically compiling it and calling the resulting function.
> Of course I could always wrap an eval around that one, so the last line becomes (eval (elt
> ',exprs (1- ,g))))))) but that seems very unprofessional. But then how
> do I do this?
The translation to CASE is one way.
Another way is to emit a whole bunch of comparisons. A simple linear
search for instance:
(cond
((eql 0 n) (first-expr ...))
((eql 1 n) (second-expr ...))
...
(t nil)) ;; or however you handle that
A binary search would be better. Suppose there are 8 cases. You'd emit
a tree of IF's along these lines.
(if (< 4 n)
(if (< 2 n)
...
...)
(if (< 7 n)
...
...)))
I'd much rather leave this type of work to the compiler writer dealing
with the CASE construct.
How about roll your own jump table? To do this, you turn each
expression into a function. The translation would look like this:
;; suppose there are 10 exprs
(let ((case-vec (vector (lambda () (first-expr))
(lambda () (second-expr))
...)))
(if (<= 0 n 9) ;; range check
(funcall (aref vector n))
nil))
Of course, the constant 9 would actually be derived from counting the
number of expressions. The macro can do that since it has the source
code to the expressions, and then just insert it as a constant into
the generated code. And would not evaluate the controlling expression
twice but get it into a gensym variable:
(defmacro nth-expr (n-expr &rest exprs)
(let ((vec (gensym "VEC"))
(n (gensym "N")))
`(let ((,vec (vector ,@(loop for expr in exprs
collect `(lambda () ,expr))))
(,n ,n-expr))
(if (<= 0 ,n ,(1- (length exprs)))
(funcall (aref ,vec ,n))
nil))))
So here we are exploiting the lexical closure's ability to control
evaluation, rather than exploiting control constructs like IF, COND or
CASE. By wrapping a code in a closure, we control whether or not that
code is evaluated by calling the closure or not calling the closure.
Since closures are objects, we stick them into a table, and index
directly into it.
Thank you for your brilliant explanation, Kaz. I guess I was a bit
impatient on this one since I wanted so much to get this code to work
but I was heading the wrong way with ELT :)
B�lint
Kaz Kylheku �rta:
> On Feb 26, 10:16 am, "erdibalint" <··········@gmail.com> wrote:
> > Ok, so I have a seemingly simple task to accomplish:
> >
> > A macro has to be defined that takes a number n followed by one or
> > more expressions,
> > and returns the value of the nth expression, so:
>
> Make that: returns the /value(s)/ of the nth expression!
>
> What if N is out of range? Error signaled? NIL?
>
> > (let ((n 2))
> > (nth-expr n (/ 1 0) (+ 1 2) (/ 1 0)))
>
> In Common Lisp, we already have:
>
> (prog1 ...) returns the first
> (prog2 ...) returns the second
> (progn ...) returns the last
>
> But, alas, these are quite different from what you are implementing,
> because they evaluate all of the expressions, and differ only in which
> one's values they return.
>
> > should return 3.
> >
> > My attempt:
> >
> > (defmacro nth-expr (n &body exprs)
> > (let ((g (gensym)))
> > `(let ((,g ,n))
> > (if (> ,g ,(length exprs))
> > nil
> > (elt ',exprs (1- ,g))))))
>
> One possibility is to compile the form into a case.
>
> (case n
> (0 first-expr)
> (1 second-expr)
> ...
> (otherwise ...))
>
> The nice thing about this is that the compiler can then perhaps apply
> some optimizations that are specific to CASE.
>
> (defmacro nth-expr (n-expr &rest exprs)
> `(case ,n-expr
> ,@(loop for expr in exprs
> for i from 0
> collect `(,i ,expr))
> (otherwise nil)))
>
> > So in theory I
> > should only turn evaluation on inside the last expression in the
> > defmacro but that leads to other problems.
>
> But in practice there is no such switch.
>
> The problem is not that insufficient evaluation is applied, but rather
> that ELT is a function and not a control construct. You are relying on
> compiling your construct to ELT, but ELT cannot express it.
>
> You cannot write the code by hand using ELT. If /you/ cannot write it
> that way, the macro cannot either.
>
> You turned the expressions into a big literal list. The value of N is
> used to pull out the N-th element of the literal using ELT. That
> element is a piece of source code, however, which requires evaluation.
> There is no way to get that to happen without calling the evaluator,
> or dynamically compiling it and calling the resulting function.
>
> > Of course I could always wrap an eval around that one, so the last line becomes (eval (elt
> > ',exprs (1- ,g))))))) but that seems very unprofessional. But then how
> > do I do this?
>
> The translation to CASE is one way.
>
> Another way is to emit a whole bunch of comparisons. A simple linear
> search for instance:
>
> (cond
> ((eql 0 n) (first-expr ...))
> ((eql 1 n) (second-expr ...))
> ...
> (t nil)) ;; or however you handle that
>
> A binary search would be better. Suppose there are 8 cases. You'd emit
> a tree of IF's along these lines.
>
> (if (< 4 n)
> (if (< 2 n)
> ...
> ...)
> (if (< 7 n)
> ...
> ...)))
>
> I'd much rather leave this type of work to the compiler writer dealing
> with the CASE construct.
>
> How about roll your own jump table? To do this, you turn each
> expression into a function. The translation would look like this:
>
> ;; suppose there are 10 exprs
>
> (let ((case-vec (vector (lambda () (first-expr))
> (lambda () (second-expr))
> ...)))
> (if (<= 0 n 9) ;; range check
> (funcall (aref vector n))
> nil))
>
> Of course, the constant 9 would actually be derived from counting the
> number of expressions. The macro can do that since it has the source
> code to the expressions, and then just insert it as a constant into
> the generated code. And would not evaluate the controlling expression
> twice but get it into a gensym variable:
>
> (defmacro nth-expr (n-expr &rest exprs)
> (let ((vec (gensym "VEC"))
> (n (gensym "N")))
> `(let ((,vec (vector ,@(loop for expr in exprs
> collect `(lambda () ,expr))))
> (,n ,n-expr))
> (if (<= 0 ,n ,(1- (length exprs)))
> (funcall (aref ,vec ,n))
> nil))))
>
> So here we are exploiting the lexical closure's ability to control
> evaluation, rather than exploiting control constructs like IF, COND or
> CASE. By wrapping a code in a closure, we control whether or not that
> code is evaluated by calling the closure or not calling the closure.
> Since closures are objects, we stick them into a table, and index
> directly into it.
"erdibalint" <··········@gmail.com> writes:
> Ok, so I have a seemingly simple task to accomplish:
>
> A macro has to be defined that takes a number n followed by one or
> more expressions,
> and returns the value of the nth expression, so:
>
> (let ((n 2))
> (nth-expr n (/ 1 0) (+ 1 2) (/ 1 0)))
>
> should return 3.
>
> My attempt:
>
> (defmacro nth-expr (n &body exprs)
> (let ((g (gensym)))
> `(let ((,g ,n))
> (if (> ,g ,(length exprs))
> nil
> (elt ',exprs (1- ,g))))))
>
> which returns the nth expression, but not its value. So in theory I
> should only turn evaluation on inside the last expression in the
> defmacro but that leads to other problems. Of course I could always
> wrap an eval around that one, so the last line becomes (eval (elt
> ',exprs (1- ,g))))))) but that seems very unprofessional. But then how
> do I do this?
For several discussions, see:
http://groups.google.com/groups?q=nth-expr
Basically, you want to find some Lisp syntactic feature that is
structured like a number of possible code paths, and only one is
chosen and evaluated based on the value of a variable. Then expand
your list of exprs into that syntactic feature. There is more than one
of them, and at last two start with the letter "C".
Hold red cellophane over this message to reveal the next hint (may
contain spoilers).
Zach
"erdibalint" <··········@gmail.com> writes:
> Hi all,
>
> I am just getting into Lisp and am fascinated by macros. I read Paul
> Graham's ANSI Common Lisp book and have bumped into the following:
>
> According to the book if x evaluates to a which evaluates to 1 and y
> evaluates to b which evaluates to 2, then the following backquoted
> expression:
>
> ``(w ,x ,,y)
>
> should evaluate to
>
> (w a 2).
No, what he says is: "if we were to evaluate it [where 'it' refers to
the result of evaluating ``(w ,x ,,y), not ``(w ,x ,,y) itself] _in
turn_, we would get (w a 2)" (emphasis mine). Assuming of course we're
looking at the same book :-) This is on p. 400 in mine.
Andras