(define (p-cons x y)
(lambda (proc) (proc x y)))
(define (p-car proc)
(proc (lambda (p q) p)))
> (p-car(p-cons "foo" "bar"))
"foo"
How does this piece of code work? This is a "homemade" version of cons and car in scheme. I can't seem to understand why "p-cons" work.
(lambda (proc) (proc x y)))
(proc (lambda (p q) p)))
These two sentences makes no sense to me.
How does (lambda (proc) (proc x y))) make it work as cons?
This works by keeping all relevant state in closure variables. Consider
(define (p-cons x y)
;; "x" and "y" will be "closed over" and their values
;; are later available, whenever someone calls the
;; anonymous lambda function, which we return here:
(lambda (accessor)
;; Call the accessor, and pass all our hidden state
;; along. The accessor will select, whatever it needs,
;; and we simply return, whatever the accessor returned
(apply accessor x y '())))
(define (p-car pseudo-cons)
(apply pseudo-cons
;; Is called by the "pseudo-cons" and receives the
;; full hidden state. Selects from it, what it wants
;; to return (here, the first "field")
(lambda (state-x state-y) state-x)
'()))
(define (p-cdr pseudo-cons)
(apply pseudo-cons
;; Is called by the "pseudo-cons" and receives the
;; full hidden state. Selects from it, what it wants
;; to return (here, the second "field")
(lambda (state-x state-y) state-y)
'()))
Let's inspect things. When we do
(define some-p-cons (p-cons 1 2))
the value of some-p-cons is a procedure, which expects a single argument (of which we will talk later). More to the point, it is a "closure", which is a procedure, that has some hidden state. In our case, this hidden state consists of the x and y parameter values supplied to p-cons. Examples:
(p-cons 1 2) ==> some procedure (hidden state x = 1 and y = 2)
(p-cons 'a 'b) ==> some procedure (hidden state x = a and y = b)
(p-cons "hello" ()) ==> some procedure (hidden state x = "hello" and y = ())
Basically, p-cons acts like a record -- or it would, if there was a way to extract the hidden state somehow (otherwise, it would be a pretty useless record...)
That's where the single argument to the closure (named accessor above) comes into play. The accessor is called with the full hidden closure state (x and y) and selects, which of these values it wants to return. The p-car accessor returns the first (x) value, and the p-cdr accessor returns the second (y) value. Let's walk through this:
A call
(p-cons 1 2)
yields some object
#<closure (lambda (accessor) (accessor x y)) with hidden state x=1, y=2>
(notation made up on the spot). When we apply p-car to it
(p-car #<closure (lambda (accessor) (accessor x y)) with hidden state x=1, y=2>)
what happens is, that p-car will itself call the "pseudo-cons" (it's itself a procedure after all), passing along an accessor function, which selects the appropriate bits of the hidden state. The p-car functions does
(apply #<closure (lambda (accessor) (accessor x y)) with hidden state x=1, y=2>
(lambda (state-x state-y) state-x) ;; anonymous accessor function
())
Now, the ball's back at the "pseudo-cons" closure. It takes all it's hidden state, and passes it on to the accessor:
(apply (lambda (state-x state-y) state-x) ;; anonymous accessor function
x ;; from hidden state, value is 1 in the example
y ;; from hidden state, value is 2 in the example
())
Bear with me, we are almost there... The accessor inspects the bits of state it got, and selects, whatever it wants to return. In the case of the p-car accessor, we want the value of the first field, and thus, that's what we return.
(The apply is not really necessary, but I find it clearer to make them explicit in this exposition)
We can even define a function, which turns our "pseudo conses" into real ones:
(define p-cons->pair (pcons)
(apply pcons cons '()))
Here, we "abuse" the built-in procedure cons as our accessor function, which does not simply select one of its two arguments, but takes both and puts them into a regular scheme pair.
