Search code examples
schemeracketsicpcons

SICP Exercise 2.04

Reading SICP I am now at exercise 2.04, which is a procedural representation of cons, car and cdr, given in the book as follows:

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

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

Note, that for running the code I use racket with the following preamble in my code:

#lang racket
(define (Mb-to-B n) (* n 1024 1024))
(define MAX-BYTES (Mb-to-B 64))
(custodian-limit-memory (current-custodian) MAX-BYTES)

I also tried #lang scheme to no avail.

Here is what I understand:

About cons

  • cons returns a function.
  • This function which will apply another function given as parameter to the two parameters x and y of cons.
  • This means by calling cons we retain the possibility to apply a function to the two parameters and are able to treat them as some unit.

About car

  • car now uses the fact, that we can apply a function to the unit of 2 values given to cons, by giving a function as a parameter to the function, which we get returned from cons.
  • It supplies that function with a lambda expression, which always returns the first of two given values.

Usage

At first I tried the following:

(car (cons 1 2))
(car (cons 2 3))
(car (cons (cons 1 1) (cons 2 2)))
(car (car (cons (cons 1 1) (cons 2 2))))

However, that leads to errors:

:racket -l errortrace -t exercise-2.04-procedural-representation-of-pairs.rkt 
application: not a procedure;
 expected a procedure that can be applied to arguments
  given: 1
  arguments...: [none]
  errortrace...:
   /home/xiaolong/development/LISP/Racket/SICP/exercise-2.04-procedural-representation-of-pairs.rkt:24:6: (p)
   /home/xiaolong/development/LISP/Racket/SICP/exercise-2.04-procedural-representation-of-pairs.rkt:33:0: (car (cons 1 2))
  context...:
   /home/xiaolong/development/LISP/Racket/SICP/exercise-2.04-procedural-representation-of-pairs.rkt: [running body]

I could not understand what was wrong with my code, so I looked up some usage examples in other people's solutions. One is on http://community.schemewiki.org/?sicp-ex-2.4:

(define x (cons 3 4))
(car x)

But to my surprise, it doesn't work! The solution in the wiki seems to be wrong. I get the following error:

application: not a procedure;
 expected a procedure that can be applied to arguments
  given: 3
  arguments...: [none]
  errortrace...:
   /home/xiaolong/development/LISP/Racket/SICP/exercise-2.04-procedural-representation-of-pairs.rkt:24:6: (p)
   /home/xiaolong/development/LISP/Racket/SICP/exercise-2.04-procedural-representation-of-pairs.rkt:42:0: (car x)
  context...:
   /home/xiaolong/development/LISP/Racket/SICP/exercise-2.04-procedural-representation-of-pairs.rkt: [running body]

What am I doing wrong here?

Solution

  • You have an error in your code. Instead of:

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

    you should have written (see the book):

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

    Note that in the last row p is written without parentheses.

    The message: application: not a procedure means that p is not a procedure (it is actually a number), while with the notation (p) you are calling it as a parameterless procedure.