Home > Archive > Scheme > September 2006 > need help parsing lambda
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
need help parsing lambda
|
|
| perltcl@yahoo.com 2006-09-13, 4:03 am |
| hi
I need help to mentally parse "lambda".
The following statements just blow my mind away.
It goes recursive, sorta of speak.
Something tells me that maybe it has something to do with referrencing
and de-referrencing operators annialating each other like "*" and "&"
in C.
But I'm not sure. help!
(define (cons x y) (lambda (m) (m x y)))
(define (car z) (z (lambda (p q) p)))
(define (cdr z) (z (lambda (p q) q)))
| |
| perltcl@yahoo.com 2006-09-13, 8:01 am |
|
perltcl@yahoo.com wrote:
> hi
>
> I need help to mentally parse "lambda".
> The following statements just blow my mind away.
> It goes recursive, sorta of speak.
> Something tells me that maybe it has something to do with referrencing
> and de-referrencing operators annialating each other like "*" and "&"
> in C.
> But I'm not sure. help!
>
> (define (cons x y) (lambda (m) (m x y)))
> (define (car z) (z (lambda (p q) p)))
> (define (cdr z) (z (lambda (p q) q)))
I tried to use the substituion rule, but all I get is:
((cons x y) (lambda (p q) p))
( (lambda (m) (m x y)) (lambda (p q) p) )
how does double lambda get "annialated , and only "x" is returned?
| |
| Pascal Bourguignon 2006-09-13, 8:01 am |
| perltcl@yahoo.com writes:
> perltcl@yahoo.com wrote:
>
>
> I tried to use the substituion rule,
On what?
> but all I get is:
> ((cons x y) (lambda (p q) p))
> ( (lambda (m) (m x y)) (lambda (p q) p) )
> how does double lambda get "annialated , and only "x" is returned?
To apply the substitution rule, it might be useful to expand the defines:
(define cons (lambda (x y) (lambda (m) (m x y))))
(define car (lambda (z) (z (lambda (p q) p))))
(define cdr (lambda (z) (z (lambda (p q) q))))
(car (cons 'hello 'world))
--> ((lambda (z) (z (lambda (p q) p)))
((lambda (x y) (lambda (m) (m x y))) 'hello 'world))
--> (((lambda (x y) (lambda (m) (m x y))) 'hello 'world) (lambda (p q) p))
--> ((lambda (m) (m 'hello 'world)) (lambda (p q) p))
--> ((lambda (p q) p) 'hello 'world)
--> 'hello
--
__Pascal Bourguignon__ http://www.informatimago.com/
"I have challenged the entire quality assurance team to a Bat-Leth
contest. They will not concern us again."
| |
| perltcl@yahoo.com 2006-09-13, 8:01 am |
|
Pascal Bourguignon wrote:
> perltcl@yahoo.com writes:
>
>
> On what?
>
>
> To apply the substitution rule, it might be useful to expand the defines:
>
> (define cons (lambda (x y) (lambda (m) (m x y))))
> (define car (lambda (z) (z (lambda (p q) p))))
> (define cdr (lambda (z) (z (lambda (p q) q))))
Ok, your version is even stranger...
>
> (car (cons 'hello 'world))
> --> ((lambda (z) (z (lambda (p q) p)))
> ((lambda (x y) (lambda (m) (m x y))) 'hello 'world))
> --> (((lambda (x y) (lambda (m) (m x y))) 'hello 'world) (lambda (p q) p))
> --> ((lambda (m) (m 'hello 'world)) (lambda (p q) p))
> --> ((lambda (p q) p) 'hello 'world)
The first 2 lines of tranformation don't work, but the last three
worked.
(I cut and paste the code.)
I think all intermediate forms should give the same result.
Anyway, I think I got it figured out, that the interpreter always strip
the last layer of bracket!
Now, a new question becomes, how do I know which step is done at
"compile time" versus "run time"?
> --> 'hello
>
>
>
>
> --
> __Pascal Bourguignon__ http://www.informatimago.com/
>
> "I have challenged the entire quality assurance team to a Bat-Leth
> contest. They will not concern us again."
| |
| Jussi Piitulainen 2006-09-13, 8:01 am |
| perltcl@yahoo.com writes:
> Pascal Bourguignon wrote:
....
>
> Ok, your version is even stranger...
Your (define (cons x y) ...) forms are just a shorthand for
these.
>
>
> The first 2 lines of tranformation don't work, but the last three
> worked.
The "first 2 lines" contain a single expression, which works
just fine. He simply replaced car and cons with their values:
the first line is "(car", the second is "(cons 'hello
'world))", together they are "(car (cons 'hello 'world))".
> I think all intermediate forms should give the same result.
Yes.
> Anyway, I think I got it figured out, that the interpreter
> always strip the last layer of bracket!
I assume you mean the outermost pair, but that is not always
possible. Also, a Scheme interpreter corresponds better to a
different order of reduction.
Here it is not possible:
((car (cons car cdr)) (cons 'hello 'world))
The head form, (car (cons car cdr)), has to be reduced to the
value of car first, and only then there is a call with a lambda
expression as head.
A Scheme-like interpreter would reduce all forms inside the
parentheses as far as possible before trying to reduce the
whole call: it would reduce (cons 'hello 'world) first. It
leads to the same value.
| |
| Pascal Bourguignon 2006-09-13, 8:01 am |
| perltcl@yahoo.com writes:
> Pascal Bourguignon wrote:
>
> Ok, your version is even stranger...
>
>
> The first 2 lines of tranformation don't work, but the last three
> worked.
> (I cut and paste the code.)
Lisp is not a line based programming language. Try python for that.
There are only 4 forms, not 5 lines.
> I think all intermediate forms should give the same result.
They do.
scheme[177]> ((lambda (z) (z (lambda (p q) p)))
((lambda (x y) (lambda (m) (m x y))) 'hello 'world))
hello
scheme[178]> (((lambda (x y) (lambda (m) (m x y))) 'hello 'world) (lambda (p q) p))
hello
scheme[179]> ((lambda (m) (m 'hello 'world)) (lambda (p q) p))
hello
scheme[180]> ((lambda (p q) p) 'hello 'world)
hello
scheme[181]>
To avoid the modification and use of the global environment, you can
also write it as:
scheme[181]> ((lambda (cons car cdr) (car (cons 'hello 'world)))
(lambda (x y) (lambda (m) (m x y)))
(lambda (z) (z (lambda (p q) p)))
(lambda (z) (z (lambda (p q) q))))
hello
> Anyway, I think I got it figured out, that the interpreter always strip
> the last layer of bracket!
> Now, a new question becomes, how do I know which step is done at
> "compile time" versus "run time"?
Normal lisp and scheme implementations don't implement the substitution rule.
The rules of evaluation are specified in CLHS and R5RS.
--
__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.
| |
| perltcl@yahoo.com 2006-09-13, 8:01 am |
|
Jussi Piitulainen wrote:
> perltcl@yahoo.com writes:
> ...
>
> Your (define (cons x y) ...) forms are just a shorthand for
> these.
>
>
> The "first 2 lines" contain a single expression, which works
> just fine. He simply replaced car and cons with their values:
> the first line is "(car", the second is "(cons 'hello
> 'world))", together they are "(car (cons 'hello 'world))".
They don't work simply because the brackets aren't paired.
The first line missing right bracket, while the second line has one
extra right bracket.
Actually, I kinda afraid to look at his version
after I have the textbook version worked out :)
(define (cons x y) (lambda (m) (m x y)))
(define (car z) (z (lambda (p q) p)))
(define (cdr z) (z (lambda (p q) q)))
OK, let's see: (car (cons 1 2))
( (cons 1 2) (lambda (p q) p))
( (lambda (m) (m 1 2)) (lambda (p q) p))
( (lambda (p q) p) 1 2 )
1
>
>
> Yes.
>
What I mean simply is that, I have to mentally think that the last
layer
of brackets "are" the interpreter! And when the interpret exits, it
simply
strip "itself" away. Else, my accounting simply won't work.
(+ 36 100)
136 <-note: interpreter
always strip the last layer of bracket!
+------------------------------------+
V V <-note: think of it
as interpreter brackets
( (lambda (z) (* z (+ z 1))) 3 )
12 <- it works and all
brackets accounted for!
[color=darkred]
>
> I assume you mean the outermost pair, but that is not always
> possible. Also, a Scheme interpreter corresponds better to a
> different order of reduction.
I know the internal working of the interpreter must be very much
"stack" based
and different, so that all the brackets would work out and accounted
for.
But I as a human must have a consistent way of reducing the same code.
Even if the interpreter does not actually use substitution, I have to.
>
> Here it is not possible:
>
> ((car (cons car cdr)) (cons 'hello 'world))
>
> The head form, (car (cons car cdr)), has to be reduced to the
> value of car first, and only then there is a call with a lambda
> expression as head.
>
> A Scheme-like interpreter would reduce all forms inside the
> parentheses as far as possible before trying to reduce the
> whole call: it would reduce (cons 'hello 'world) first. It
> leads to the same value.
| |
| Pascal Bourguignon 2006-09-13, 8:01 am |
| perltcl@yahoo.com writes:
> Jussi Piitulainen wrote:
>
> They don't work simply because the brackets aren't paired.
> The first line missing right bracket, while the second line has one
> extra right bracket.
Try this:
--> ((lambda (z) (z (lambda (p q) p))) ((lambda (x y) (lambda (m) (m x y))) 'hello 'world))
better?
Perhaps you should read a basic tutorial about lisp or scheme,
something that's taught to newbies the first half hour, before trying
to understand lambda and considering an implementation of cons, car
and cdr based on them.
--
__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
| |
| perltcl@yahoo.com 2006-09-13, 7:04 pm |
|
Pascal Bourguignon wrote:
> perltcl@yahoo.com writes:
>
> Try this:
>
> --> ((lambda (z) (z (lambda (p q) p))) ((lambda (x y) (lambda (m) (m x y))) 'hello 'world))
>
> better?
I see, a line wrap misunderstanding :)
>
>
> Perhaps you should read a basic tutorial about lisp or scheme,
> something that's taught to newbies the first half hour, before trying
> to understand lambda and considering an implementation of cons, car
> and cdr based on them.
That's what I'm doing. I just started yesterday.
unfortunately, the first book I find is MIT's textbook.
http://mitpress.mit.edu/sicp/full-t...ook-Z-H-14.html
I'm at chapter two.
I don't like jump ahead and start implementing the interpreter right
away.
The book will probably deal with interpreter issues at chapter five.
>
> --
> __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
| |
| perltcl@yahoo.com 2006-09-13, 7:04 pm |
|
perltcl@yahoo.com wrote:
> Jussi Piitulainen wrote:
>
> They don't work simply because the brackets aren't paired.
> The first line missing right bracket, while the second line has one
> extra right bracket.
>
> Actually, I kinda afraid to look at his version
> after I have the textbook version worked out :)
well, to my horror, the textbook gives a similar example,
one page later:)
Exercise 2.6. In case representing pairs as procedures wasn't
mind-boggling enough, consider that, in a language that can manipulate
procedures, we can get by without numbers (at least insofar as
nonnegative integers are concerned) by implementing 0 and the operation
of adding 1 as
(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
(lambda (f) (lambda (x) (f ((n f) x)))))
****************************************
****************************
Working with 1-bit CPU wan't bad enough eh?
(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "Argument not 0 or 1 -- CONS" m))))
dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))
****************************************
****************************
[color=darkred]
> (define (cons x y) (lambda (m) (m x y)))
> (define (car z) (z (lambda (p q) p)))
> (define (cdr z) (z (lambda (p q) q)))
> OK, let's see: (car (cons 1 2))
> ( (cons 1 2) (lambda (p q) p))
> ( (lambda (m) (m 1 2)) (lambda (p q) p))
> ( (lambda (p q) p) 1 2 )
> 1
>
>
> What I mean simply is that, I have to mentally think that the last
> layer
> of brackets "are" the interpreter! And when the interpret exits, it
> simply
> strip "itself" away. Else, my accounting simply won't work.
>
>
> (+ 36 100)
> 136 <-note: interpreter
> always strip the last layer of bracket!
>
> +------------------------------------+
> V V <-note: think of it
> as interpreter brackets
> ( (lambda (z) (* z (+ z 1))) 3 )
> 12 <- it works and all
> brackets accounted for!
>
>
>
>
> I know the internal working of the interpreter must be very much
> "stack" based
> and different, so that all the brackets would work out and accounted
> for.
> But I as a human must have a consistent way of reducing the same code.
> Even if the interpreter does not actually use substitution, I have to.
>
| |
|
|
|
|
|