-2

I've read and somewhat understand Use of lambda for cons/car/cdr definition in SICP. My problem is understanding the why behind it. My first problem was staring and staring at

(define (cons x y)
 (lambda (m) (m x y)))

and not understanding how this function actually did any sort of consing. Consing as I learned it from various Lisp/Scheme books is putting stuff in lists, i.e.,

(cons 1 ()) => (1)

how does

(define (cons x y)
 (lambda (m) (m x y)))

do anything like consing? But as the light went on in my head: cons was only sort of a placeholder for the eventual definitions of car and cdr. So car is

 (define (car z)
   (z (lambda (p q) p)))

and it anticipates an incoming z. But what is this z? When I saw this use:

 (car (cons 1 2))

it finally dawned on me that, yes, the cons function in its entirety is z, i.e., we're passing cons to car! How weird!

((lambda (m) (m 1 2)) (lambda (p q) p)) ; and then
((lambda (p q) p) 1 2)

which results in grabbing the first expression since the basic car operation can be thought of as an if statement where the boolean is true, thus, grab the first one.

Yes, all lists can be thought of as cons-ed together expressions, but what have we won by this strangely backward definition? It's as if any initial, stand-alone definition of cons is not germane. It's as if uses of something define that something, as if there's no something until its uses circumscribe it. Is this the primary use of closures? Can someone give me some other examples?

Community
  • 1
  • 1
147pm
  • 2,137
  • 18
  • 28
  • I don't think we can do better than [Oscar's answer](http://stackoverflow.com/a/21769444/1193075). And, you should try the different steps in the REPL to see for yourself. – uselpa Oct 22 '14 at 18:00
  • I understand Oscar. What I don't understand is why, why are we doing this? What uses do such closures offer? Other examples. et cetera, et cetera – 147pm Oct 22 '14 at 20:21
  • Took me a while to get my head around it too. I think this cons/car/cdr definition is used to illustrate that data structures and algorithms can be abstracted away from any specific means of internal representation. Another example is where, using appropriate definitions of zero and the succ and pred functions, you can 'construct' all elementary natural number mathematics (addition, subtraction, multiplication, comparison etc.) without using the languages intrinsic +,-,* operators. It may be inefficient, but it abstracts numbers away from any internal binary representation. – Penguino Oct 22 '14 at 21:04
  • `(1)` and `(1 . ())` are representatilns for what you get when you evaluate `(cons 1 '())` but it's not the actual object stored in memory. It's like `20` and `40` are ok representations for the decimal number `32`, just in different bases. If you were to make your own Scheme implementation how you implement `cons` will dictate how `car`, `cdr` must be implemented as well as how you need to implement both the `read` and `display`. – Sylwester Oct 23 '14 at 11:59

1 Answers1

1

but what have we won by this strangely backward definition?

The point of the exercise is to demonstrate that data structures can be defined completely in terms of functions; that data structures are not necessary as a primitive construct in a language -- if you have functions (that are closures), that's sufficient. This shows the power of functions, and is probably mind-boggling to someone from outside of functional programming.

It's not that in a real project we would actually define data structures this way. It would be more efficient to use language-provided data structure constructs. But it's important to know that we can do it this way. In computer science, it's useful to be able to "reduce" one construct (data structures) into another construct (functions) so that if we prove something about the second construct, it applies to the first one too.

newacct
  • 119,665
  • 29
  • 163
  • 224