On Sat, 07 Oct 2006 10:55:02 +0200, Arne Hanssen wrote:
> Hi, trying to learn this beautifully language I've dived into Paul
> Grahams essay on the Roots of Lisp. There he builds a simple evaluator
> for the original Lisp.
>
> My problem is this function taken from the text:
>
> (eval. '(label firstatom (lambda (x)
> (cond((atom x) x)
> ('t (firstatom (car x)))))
> y)
> '((y ((a b) (c d)))))
>
> It just ends up running in an infinite loop when run in the evaluator.
> Hmm anyone who willing to share some of Lisp's mysteries?
>
> regards
> -arne
Well, the eval. function takes two arguments: the (quoted) expression to
be evaluated and a list (call it alist) made with the pair. function.
Graham's code example at the top of page 10 omits the second argument.
A minimal alist for the firstatom example could be made with
(setf alist (pair. '(firstatom)
'((label firstatom (lambda (x)
(cond ((atom x) x)
('t (firstatom (car x))))))))
which just associates the firstatom function name with the label
expression.
The evaluation then can be done with
(eval. '((label firstatom (lambda (x)
(cond ((atom x) x)
('t (firstatom (car x))))))
y)
'((y ((a b) (c d)))))
alist)
which properly evaluates to A (it does for me).
Hope this helps.
On Sat, 07 Oct 2006 13:24:18 +0200, Henk Koster wrote:
> On Sat, 07 Oct 2006 10:55:02 +0200, Arne Hanssen wrote:
>
>> Hi, trying to learn this beautifully language I've dived into Paul
>> Grahams essay on the Roots of Lisp. There he builds a simple evaluator
>> for the original Lisp.
>>
>> My problem is this function taken from the text:
>>
>> (eval. '(label firstatom (lambda (x)
>> (cond((atom x) x)
>> ('t (firstatom (car x)))))
>> y)
>> '((y ((a b) (c d)))))
>>
>> It just ends up running in an infinite loop when run in the evaluator.
>> Hmm anyone who willing to share some of Lisp's mysteries?
>>
>> regards
>> -arne
>
>
> Well, the eval. function takes two arguments: the (quoted) expression to
> be evaluated and a list (call it alist) made with the pair. function.
> Graham's code example at the top of page 10 omits the second argument.
>
> A minimal alist for the firstatom example could be made with
>
> (setf alist (pair. '(firstatom)
> '((label firstatom (lambda (x)
> (cond ((atom x) x)
> ('t (firstatom (car x))))))))
>
> which just associates the firstatom function name with the label
> expression.
>
> The evaluation then can be done with
>
> (eval. '((label firstatom (lambda (x)
> (cond ((atom x) x)
> ('t (firstatom (car x))))))
> y)
> '((y ((a b) (c d)))))
> alist)
>
> which properly evaluates to A (it does for me).
>
> Hope this helps.
I should also learn how to get indentation right in this editor...
On Sat, 07 Oct 2006 13:24:18 +0200, Henk Koster wrote:
> On Sat, 07 Oct 2006 10:55:02 +0200, Arne Hanssen wrote:
>
>> Hi, trying to learn this beautifully language I've dived into Paul
>> Grahams essay on the Roots of Lisp. There he builds a simple evaluator
>> for the original Lisp.
>>
>> My problem is this function taken from the text:
>>
>> (eval. '(label firstatom (lambda (x)
>> (cond((atom x) x)
>> ('t (firstatom (car x)))))
>> y)
>> '((y ((a b) (c d)))))
>>
>> It just ends up running in an infinite loop when run in the evaluator.
>> Hmm anyone who willing to share some of Lisp's mysteries?
>>
>> regards
>> -arne
>
>
> Well, the eval. function takes two arguments: the (quoted) expression to
> be evaluated and a list (call it alist) made with the pair. function.
> Graham's code example at the top of page 10 omits the second argument.
>
> A minimal alist for the firstatom example could be made with
>
> (setf alist (pair. '(firstatom)
> '((label firstatom (lambda (x)
> (cond ((atom x) x)
> ('t (firstatom (car x))))))))
>
> which just associates the firstatom function name with the label
> expression.
>
> The evaluation then can be done with
>
> (eval. '((label firstatom (lambda (x)
> (cond ((atom x) x)
> ('t (firstatom (car x))))))
> y)
> '((y ((a b) (c d)))))
> alist)
>
> which properly evaluates to A (it does for me).
>
> Hope this helps.
Actually, there is an alist in Graham's example
(y ((a b) (c d)))
but it isn't complete, as it must be augmented with the
(firstatom (label...)) pair.
So, you could
(setf alist (pair. '(y firstatom)
'(((a b) (c d)) (label firstatom (lambda (x)
(cond ((atom x) x)
('t (firstatom (car x)))))))))
and now the evaluation is done with
(eval. '(label firstatom (lambda (x)
(cond ((atom x) x)
('t (firstatom (car x))))))
y)
alist)
which gives A (at least on my box). This is clearer, I think.
Graham's article is interesting, don't you agree?
In article <······························@xs4all.nl>,
Henk Koster <············@xs4all.nl> wrote:
Thanks for the quick replay, but I'm still lost so...:-)
> Well, the eval. function takes two arguments: the (quoted) expression to
> be evaluated and a list (call it alist) made with the pair. function.
The way I read the code the second argument to eval. is
'((y (a b)(c d))), the first being the label expression
During the execution eval. will push the pair you mention onto the
a-list so it later can retrieve it.
From the eval. program:
...
((eq (caar e) 'label)
(eval. (cons (caddar e) (cdr e))
(cons (list. (cadar e) (car e)) a)))
> The evaluation then can be done with
>
> (eval. '((label firstatom (lambda (x)
> (cond ((atom x) x)
> ('t (firstatom (car x))))))
> y)
> '((y ((a b) (c d)))))
> alist)
>
I've tried this one but there is something wrong with the parenthesis?
Sorry for bugging you with my problems.
I've really appreciate what you have done so far
regards
-arne
Arne Hanssen <·················@runbox.cm> writes:
> Hi, trying to learn this beautifully language I've dived into Paul
> Grahams essay on the Roots of Lisp. There he builds a simple evaluator
> for the original Lisp.
>
> My problem is this function taken from the text:
>
> (eval. '(label firstatom (lambda (x)
> (cond((atom x) x)
> ('t (firstatom (car x)))))
> y)
> '((y ((a b) (c d)))))
>
> It just ends up running in an infinite loop when run in the evaluator.
> Hmm anyone who willing to share some of Lisp's mysteries?
[66]> (load"lisp-1960-pg.lisp")
;; Loading file lisp-1960-pg.lisp ...
;; Loaded file lisp-1960-pg.lisp
T
[67]> (eval. '(label firstatom (lambda (x)
(cond((atom x) x)
('t (firstatom (car x)))))
y)
'((y ((a b) (c d)))))
*** - Lisp stack overflow. RESET
[68]> (trace eval.)
WARNING: TRACE: redefining function EVAL. in top-level, was defined in
/a6/users/pjb/src/lisp/encours/lisp-1960-pg.lisp
;; Tracing function EVAL..
(EVAL.)
[69]> (eval. '(label firstatom (lambda (x)
(cond((atom x) x)
('t (firstatom (car x)))))
y)
'((y ((a b) (c d)))))
1. Trace:
(EVAL.
'(LABEL FIRSTATOM (LAMBDA (X) (COND ((ATOM X) X) ('T (FIRSTATOM (CAR X))))) Y)
'((Y ((A B) (C D)))))
*** - Lisp stack overflow. RESET
[70]> (trace evcon. evlis.)
WARNING: TRACE: redefining function EVCON. in top-level, was defined in
/a6/users/pjb/src/lisp/encours/lisp-1960-pg.lisp
;; Tracing function EVCON..
WARNING: TRACE: redefining function EVLIS. in top-level, was defined in
/a6/users/pjb/src/lisp/encours/lisp-1960-pg.lisp
;; Tracing function EVLIS..
(EVCON. EVLIS.)
[71]> (eval. '(label firstatom (lambda (x)
(cond((atom x) x)
('t (firstatom (car x)))))
y)
'((y ((a b) (c d)))))
1. Trace:
(EVAL.
'(LABEL FIRSTATOM (LAMBDA (X) (COND ((ATOM X) X) ('T (FIRSTATOM (CAR X))))) Y)
'((Y ((A B) (C D)))))
*** - Lisp stack overflow. RESET
[72]> (trace assoc. pair.)
WARNING: TRACE: redefining function ASSOC. in top-level, was defined in
/a6/users/pjb/src/lisp/encours/lisp-1960-pg.lisp
;; Tracing function ASSOC..
WARNING: TRACE: redefining function PAIR. in top-level, was defined in
/a6/users/pjb/src/lisp/encours/lisp-1960-pg.lisp
;; Tracing function PAIR..
(ASSOC. PAIR.)
[73]> (eval. '(label firstatom (lambda (x)
(cond((atom x) x)
('t (firstatom (car x)))))
y)
'((y ((a b) (c d)))))
1. Trace:
(EVAL.
'(LABEL FIRSTATOM (LAMBDA (X) (COND ((ATOM X) X) ('T (FIRSTATOM (CAR X))))) Y)
'((Y ((A B) (C D)))))
2. Trace: (ASSOC. 'LABEL '((Y ((A B) (C D)))))
3. Trace: (ASSOC. 'LABEL 'NIL)
4. Trace: (ASSOC. 'LABEL 'NIL)
5. Trace: (ASSOC. 'LABEL 'NIL)
6. Trace: (ASSOC. 'LABEL 'NIL)
7. Trace: (ASSOC. 'LABEL 'NIL)
8. Trace: (ASSOC. 'LABEL 'NIL)
9. Trace: (ASSOC. 'LABEL 'NIL)
10. Trace: (ASSOC. 'LABEL 'NIL)
11. Trace: (ASSOC. 'LABEL 'NIL)
12. Trace: (ASSOC. 'LABEL 'NIL)
13. Trace: (ASSOC. 'LABEL 'NIL)
14. Trace: (ASSOC. 'LABEL 'NIL)
15. Trace: (ASSOC. 'LABEL 'NIL)
** - Continuable Error
PRINT: User break
If you continue (by typing 'continue'): Continue execution
The following restarts are also available:
ABORT :R1 ABORT
Break 1. [74]> :q
[75]>
So the problem is that assoc. misbehaves when the key is not found in
the a-list.
[92]> (defun assoc. (x y)
(cond ((eq (caar y) x) (cadar y))
((null y) (error "Unbound variable: ~A" x))
('t (assoc. x (cdr y)))))
ASSOC.
[93]> (eval. '(label firstatom (lambda (x)
(cond((atom x) x)
('t (firstatom (car x)))))
y)
'((y ((a b) (c d)))))
1. Trace:
(EVAL.
'(LABEL FIRSTATOM (LAMBDA (X) (COND ((ATOM X) X) ('T (FIRSTATOM (CAR X))))) Y)
'((Y ((A B) (C D)))))
*** - Unbound variable: LABEL
The following restarts are available:
ABORT :R1 ABORT
Break 1 [94]>
And now you can see that the problem is that LABEL is not defined
either as a function or a special operator.
LABEL is defined as a symbol that can be used like the symbol LAMBDA
to denode some anonymous literal function. Only the anonymous
function created by LABEL is labelled by a name usable inside that
function, for recursive purposes.
You can see that in the source of EVAL., where LABEL is treated the
same way as LAMBDA, comparing it to the (CAAR E) instead of
the (CAR E) of the other special operators.
You are missing a couple of parentheses:
[100]> (untrace eval. evlis. evcon. assoc. pair.)
(PAIR.)
[101]> (eval. '((label firstatom (lambda (x)
(cond((atom x) x)
('t (firstatom (car x))))))
y)
'((y ((a b) (c d)))))
A
[102]>
Have a look at:
http://www.informatimago.com/develop/lisp/small-cl-pgms/aim-8/
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
In article <··············@thalassa.informatimago.com>,
Pascal Bourguignon <···@informatimago.com> wrote:
> Arne Hanssen <·················@runbox.cm> writes:
>.......
> And now you can see that the problem is that LABEL is not defined
> either as a function or a special operator.
> ....
> You are missing a couple of parentheses:
>
Excellent, thank's for taking your time. I must confessed that I'm
stunned by simpel but beautifully core modell of the languge. But it
takes some time to get those parentheses right :-(
-arne
From: Ken Tilton
Subject: Re: Newbie, Problem following this code from Paul Graham
Date:
Message-ID: <qoSVg.234$QW5.175@newsfe09.lga>
Arne Hanssen wrote:
> In article <··············@thalassa.informatimago.com>,
> Pascal Bourguignon <···@informatimago.com> wrote:
>
>
>>Arne Hanssen <·················@runbox.cm> writes:
>>.......
>>And now you can see that the problem is that LABEL is not defined
>>either as a function or a special operator.
>>....
>>You are missing a couple of parentheses:
>>
>
>
> Excellent, thank's for taking your time. I must confessed that I'm
> stunned by simpel but beautifully core modell of the languge. But it
> takes some time to get those parentheses right :-(
What are you using to edit and run the code?
kt
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
Arne Hanssen <·················@runbox.cm> writes:
> In article <··············@thalassa.informatimago.com>,
> Pascal Bourguignon <···@informatimago.com> wrote:
>
>> Arne Hanssen <·················@runbox.cm> writes:
>>.......
>> And now you can see that the problem is that LABEL is not defined
>> either as a function or a special operator.
>> ....
>> You are missing a couple of parentheses:
>>
>
> Excellent, thank's for taking your time. I must confessed that I'm
> stunned by simpel but beautifully core modell of the languge. But it
> takes some time to get those parentheses right :-(
Well, first note that here we are not discussing Common Lisp, but the
lisp that is implemented by this EVAL. function.
It would be possible to modify this language, to let it accept LABEL
as a special operator that would return the anonymous function:
(eval. '(label firstatom (lambda (x)
(cond((atom x) x)
('t (firstatom (car x))))))
'((y ((a b) (c d)))))
would return a function.
We just need to slightly modify EVAL.:
(defun eval. (e a)
(cond
((atom e) (assoc. e a))
((atom (car e))
(cond
((eq (car e) 'quote) (cadr e))
((eq (car e) 'atom) (atom (eval. (cadr e) a)))
((eq (car e) 'eq) (eq (eval. (cadr e) a)
(eval. (caddr e) a)))
((eq (car e) 'car) (car (eval. (cadr e) a)))
((eq (car e) 'cdr) (cdr (eval. (cadr e) a)))
((eq (car e) 'cons) (cons (eval. (cadr e) a)
(eval. (caddr e) a)))
((eq (car e) 'cond) (evcon. (cdr e) a))
((eq (car e) 'label) e) ; return a label anonymous function.
((eq (car e) 'lambda) e) ; return a lambda anonymous function.
('t (eval. (cons (eval. (car e) a) ; evaluate the car of forms
(cdr e)) ; when it's atomic.
a))))
((eq (caar e) 'label)
(eval. (cons (caddar e) (cdr e))
(cons (list. (cadar e) (car e)) a)))
((eq (caar e) 'lambda)
(eval. (caddar e)
(append. (pair. (cadar e) (evlis. (cdr e) a))
a)))
('t (eval. (cons (eval. (car e) a) ; evaluate the car of forms
(cdr e)) ; when it's a cons.
a))))
[103]> (eval. '(label firstatom (lambda (x)
(cond((atom x) x)
('t (firstatom (car x))))))
'((y ((a b) (c d)))))
(LABEL FIRSTATOM (LAMBDA (X) (COND ((ATOM X) X) ('T (FIRSTATOM (CAR X))))))
[104]> (eval. '((label firstatom (lambda (x)
(cond((atom x) x)
('t (firstatom (car x)))))) y)
'((y ((a b) (c d)))))
A
[105]> (eval. '((car (cdr f)) y)
'((y ((a b) (c d)))
(f ((lambda (x) x) (lambda (x) (car x))))))
(A B)
--
__Pascal Bourguignon__ http://www.informatimago.com/
In a World without Walls and Fences,
who needs Windows and Gates?
On Sat, 07 Oct 2006 20:22:09 +0200, Pascal Bourguignon wrote:
> Arne Hanssen <·················@runbox.cm> writes:
>
>> In article <··············@thalassa.informatimago.com>,
>> Pascal Bourguignon <···@informatimago.com> wrote:
>>
>>> Arne Hanssen <·················@runbox.cm> writes:
>>>.......
>>> And now you can see that the problem is that LABEL is not defined
>>> either as a function or a special operator.
>>> ....
>>> You are missing a couple of parentheses:
>>>
>>
>> Excellent, thank's for taking your time. I must confessed that I'm
>> stunned by simpel but beautifully core modell of the languge. But it
>> takes some time to get those parentheses right :-(
>
> Well, first note that here we are not discussing Common Lisp, but the
> lisp that is implemented by this EVAL. function.
>
> It would be possible to modify this language, to let it accept LABEL
> as a special operator that would return the anonymous function:
>
> (eval. '(label firstatom (lambda (x)
> (cond((atom x) x)
> ('t (firstatom (car x))))))
> '((y ((a b) (c d)))))
>
> would return a function.
>
> We just need to slightly modify EVAL.:
>
> (defun eval. (e a)
> (cond
> ((atom e) (assoc. e a))
> ((atom (car e))
> (cond
> ((eq (car e) 'quote) (cadr e))
> ((eq (car e) 'atom) (atom (eval. (cadr e) a)))
> ((eq (car e) 'eq) (eq (eval. (cadr e) a)
> (eval. (caddr e) a)))
> ((eq (car e) 'car) (car (eval. (cadr e) a)))
> ((eq (car e) 'cdr) (cdr (eval. (cadr e) a)))
> ((eq (car e) 'cons) (cons (eval. (cadr e) a)
> (eval. (caddr e) a)))
> ((eq (car e) 'cond) (evcon. (cdr e) a))
> ((eq (car e) 'label) e) ; return a label anonymous function.
> ((eq (car e) 'lambda) e) ; return a lambda anonymous function.
> ('t (eval. (cons (eval. (car e) a) ; evaluate the car of forms
> (cdr e)) ; when it's atomic.
> a))))
> ((eq (caar e) 'label)
> (eval. (cons (caddar e) (cdr e))
> (cons (list. (cadar e) (car e)) a)))
> ((eq (caar e) 'lambda)
> (eval. (caddar e)
> (append. (pair. (cadar e) (evlis. (cdr e) a))
> a)))
> ('t (eval. (cons (eval. (car e) a) ; evaluate the car of forms
> (cdr e)) ; when it's a cons.
> a))))
>
>
> [103]> (eval. '(label firstatom (lambda (x)
> (cond((atom x) x)
> ('t (firstatom (car x))))))
> '((y ((a b) (c d)))))
> (LABEL FIRSTATOM (LAMBDA (X) (COND ((ATOM X) X) ('T (FIRSTATOM (CAR X))))))
> [104]> (eval. '((label firstatom (lambda (x)
> (cond((atom x) x)
> ('t (firstatom (car x)))))) y)
> '((y ((a b) (c d)))))
> A
>
> [105]> (eval. '((car (cdr f)) y)
> '((y ((a b) (c d)))
> (f ((lambda (x) x) (lambda (x) (car x))))))
> (A B)
The code in Graham's firstatom example is missing something, and there are
several ways to fix it. Easiest in my opinion is to not fix the eval.
function, but to recognize that its second argument is missing an entry
for the key firstatom. So, the whole expression becomes
(eval. '((label firstatom (lambda (x)
(cond ((atom x) x)
('t (firstatom (car x))))))
y)
'((y ((a b) (c d)))
(firstatom (lambda (x)
(cond ((atom x) x)
('t (firstatom (car x))))))))
When I run this in CLISP (together with the dotted-function definitions
earlier in the Graham paper) it evaluates to A, as it should. The heart of
Graham's eval. function is the cond expression with four clauses: a label
expression is first -- by clause 3 -- transformed to a lambda expression,
with the latter then further transformed using clause 4.
(I'm using Graham's *draft* of the paper dated January 18, 2002.)
Henk Koster <············@xs4all.nl> writes:
>> Well, first note that here we are not discussing Common Lisp, but the
>> lisp that is implemented by this EVAL. function.
>>
>> It would be possible to modify this language, to let it accept LABEL
>> as a special operator that would return the anonymous function:
>> [...]
>
> The code in Graham's firstatom example is missing something, and there are
> several ways to fix it. Easiest in my opinion is to not fix the eval.
> function, but to recognize that its second argument is missing an entry
> for the key firstatom. So, the whole expression becomes
>
> (eval. '((label firstatom (lambda (x)
> (cond ((atom x) x)
> ('t (firstatom (car x))))))
> y)
> '((y ((a b) (c d)))
> (firstatom (lambda (x)
> (cond ((atom x) x)
> ('t (firstatom (car x))))))))
>
> When I run this in CLISP (together with the dotted-function definitions
> earlier in the Graham paper) it evaluates to A, as it should. The heart of
> Graham's eval. function is the cond expression with four clauses: a label
> expression is first -- by clause 3 -- transformed to a lambda expression,
> with the latter then further transformed using clause 4.
>
> (I'm using Graham's *draft* of the paper dated January 18, 2002.)
No binding to firstatom is needed, only respect the syntax of LABEL!!!
[154]> (eval. '((label firstatom (lambda (x)
(cond((atom x) x)
('t (firstatom (car x))))))
y)
'((y ((a b) (c d)))))
A
[155]>
This was explained two messages earlier...
--
__Pascal Bourguignon__ http://www.informatimago.com/
ADVISORY: There is an extremely small but nonzero chance that,
through a process known as "tunneling," this product may
spontaneously disappear from its present location and reappear at
any random place in the universe, including your neighbor's
domicile. The manufacturer will not be responsible for any damages
or inconveniences that may result.
On Sun, 08 Oct 2006 15:59:24 +0200, Pascal Bourguignon wrote:
> Henk Koster <············@xs4all.nl> writes:
>>> Well, first note that here we are not discussing Common Lisp, but the
>>> lisp that is implemented by this EVAL. function.
>>>
>>> It would be possible to modify this language, to let it accept LABEL
>>> as a special operator that would return the anonymous function:
>>> [...]
>>
>> The code in Graham's firstatom example is missing something, and there are
>> several ways to fix it. Easiest in my opinion is to not fix the eval.
>> function, but to recognize that its second argument is missing an entry
>> for the key firstatom. So, the whole expression becomes
>>
>> (eval. '((label firstatom (lambda (x)
>> (cond ((atom x) x)
>> ('t (firstatom (car x))))))
>> y)
>> '((y ((a b) (c d)))
>> (firstatom (lambda (x)
>> (cond ((atom x) x)
>> ('t (firstatom (car x))))))))
>>
>> When I run this in CLISP (together with the dotted-function definitions
>> earlier in the Graham paper) it evaluates to A, as it should. The heart of
>> Graham's eval. function is the cond expression with four clauses: a label
>> expression is first -- by clause 3 -- transformed to a lambda expression,
>> with the latter then further transformed using clause 4.
>>
>> (I'm using Graham's *draft* of the paper dated January 18, 2002.)
>
> No binding to firstatom is needed, only respect the syntax of LABEL!!!
>
> [154]> (eval. '((label firstatom (lambda (x)
> (cond((atom x) x)
> ('t (firstatom (car x))))))
> y)
> '((y ((a b) (c d)))))
> A
> [155]>
>
> This was explained two messages earlier...
Yes, of course, these are anonymous functions, I see that now. It would
have been different had defun been used. I've started learning Lisp
recently, so I hope you won't be too annoyed with me...
Henk Koster <············@xs4all.nl> writes:
>> No binding to firstatom is needed, only respect the syntax of LABEL!!!
>>
>> [154]> (eval. '((label firstatom (lambda (x)
>> (cond((atom x) x)
>> ('t (firstatom (car x))))))
>> y)
>> '((y ((a b) (c d)))))
>> A
>> [155]>
>>
>> This was explained two messages earlier...
>
> Yes, of course, these are anonymous functions, I see that now. It would
> have been different had defun been used. I've started learning Lisp
> recently, so I hope you won't be too annoyed with me...
No problem.
LABEL is an old operator, not to be confused with the modern CL:LABELS.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NEW GRAND UNIFIED THEORY DISCLAIMER: The manufacturer may
technically be entitled to claim that this product is
ten-dimensional. However, the consumer is reminded that this
confers no legal rights above and beyond those applicable to
three-dimensional objects, since the seven new dimensions are
"rolled up" into such a small "area" that they cannot be
detected.