performanceschemelispsicp

Why does Scheme use the procedural representation of pairs?


I am reading SICP. It says in 2.1.3:

That is, the operations satisfy the condition that, for any objects x and y, if z is (cons x y) then (car z) is x and (cdr z) is y. ... Here are the definitions:

 (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))

...

The point of exhibiting the procedural representation of pairs is not that our language works this way (Scheme, and Lisp systems in general, implement pairs directly, for efficiency reasons) but that it could work this way. The procedural representation, although obscure, is a perfectly adequate way to represent pairs, since it fulfills the only conditions that pairs need to fulfill.

In C, we may implement "pair" using array which in assembly codes is implemented by allocating one consecutive memory addresses to store data. We can check the array size to ensure it is a pair.

Then why is "procedural representation" more efficient for Scheme?

I have learnt computer architecture. Any answers based on assembly language are welcome.


Solution

  • It's not about efficiency: I don't know of any Scheme implementations that implement pairs this way.

    It's about two things:

    1. Expressive power. Once you have first-class procedures it turns out they can be used to implement all sorts of other things. You can implement pairs using them, if you want. You might start to wonder: is there anything you can't implement using them, if you want to?
    2. Abstraction. The title of that section of SICP is 'Introduction to data abstraction' and it's making the point that what matters is the interface to something, not how its implemented. So long as the interface remains the same, the implementation may not matter that much.

    (The answer to the question in the first point is 'no'.)