Use of lambda for cons/car/cdr definition in SICP

by

This is an interesting way to represent data: as functions. Notice that this
definition of cons returns a lambda which closes over the parameters x
and y, capturing their values inside. Also notice that the returned lambda
receives a function m as a parameter:

;creates a closure that "remembers' 2 values
(define (cons x y)    (lambda (m) (m x y)))
;recieves a cons holding 2 values, returning the 0th value
(define (car z)       (z (lambda (p q) p)))
;recieves a cons holding 2 values, returning the 1st value
(define (cdr z)       (z (lambda (p q) q)))

In the above code z is a closure, the same that was created by cons, and in
the body of the procedure we’re passing it another lambda as parameter,
remember m? it’s just that! the function that it was expecting.

Understanding the above, it’s easy to see how car and cdr work; let’s
dissect how car, cdr is evaluated by the interpreter one step at a time:

; lets say we started with a closure `cons`, passed in to `car`
(car (cons 1 2))

; the definition of `cons` is substituted in to `(cons 1 2)` resulting in:
(car (lambda (m) (m 1 2)))

; substitute `car` with its definition
((lambda (m) (m 1 2)) (lambda (p q) p))

; replace `m` with the passed parameter
((lambda (p q) p) 1 2)

; bind 1 to `p` and 2 to `q`, return p
1

To summarize: cons creates a closure that “remembers’ two values, car
receives that closure and passes it along a function that acts as a selector for
the zeroth value, and cdr acts as a selector for the 1st value. The key
point to understand here is that lambda acts as a
closure.
How cool is this? we only need functions to store and retrieve arbitrary data!

Nested Compositions of car & cdr are defined up to 4 deep in most LISPs. example:

(define caddr (lambda (x) (car (cdr (cdr x)))))

More Related Contents:

  1. DrRacket procedure body help (boolean-odd? x)
  2. Zipping streams using JDK8 with lambda (java.util.stream.Streams.zip)
  3. What is a lambda (function)?
  4. What is the difference between quote and list?
  5. My code signals the error “application: not a procedure” or “call to non procedure”
  6. “application: not a procedure” in binary arithmetic procedures
  7. Which lang packet is proper for SICP in Dr.Racket?
  8. SICP example: Counting change, cannot understand
  9. How to do a powerset in DrRacket?
  10. tail-recursive function appending element to list
  11. Lazy field initialization with lambdas
  12. I got “scheme application not a procedure” in the last recursive calling of a function
  13. Alan Kay’s Eval/Apply Einstein Moment
  14. Using return inside a lambda?
  15. Reference to method of a particular instance in Kotlin
  16. Do Java8 lambdas maintain a reference to their enclosing instance like anonymous classes?
  17. Passing lambda instead of interface
  18. What exactly is a symbol in lisp/scheme?
  19. List comprehension vs. lambda + filter
  20. Why use std::bind over lambdas in C++14?
  21. Using the iterator variable of foreach loop in a lambda expression – why fails?
  22. How can I assign a Func conditionally between lambdas using the conditional ternary operator?
  23. E731 do not assign a lambda expression, use a def
  24. Java 8 chained method reference?
  25. java: Arrays.sort() with lambda expression
  26. Lambda Expression vs Functor in C++
  27. Expression for Type members results in different Expressions (MemberExpression, UnaryExpression)
  28. Purpose of perfect forwarding for Callable argument in invocation expression?
  29. Why does a Java Lambda which throws a Runtime Exception require brackets?
  30. Convert DataTable to Generic List in C#

Leave a Comment