Scheme symbolic equivalence

Question

Hi all.

The platform i'm working with is DrScheme.

I've seen that a pair (a b) [constructed by (cons a b)] is implemented within the language like a procedure that looks like this:

(define (cons a b)
  (lambda(pick)
    (cond ((= pick 1) a)
          ((= pick 2) b))))

and the selectors:

(define (car x) (x 1))
(define (cdr x) (x 2))

Then there are lists, constructed with expression like (cons a (cons b (cons c (cons ...)))).

Now, what i was trying to understand is this (typed on DrScheme's prompt):

> (define l1 '(a b c))
> (define l2 (list 'a 'b 'c))
> l1
(a b c)
> l2
(a b c)
> (eq? l1 l2)
#f

Ok, l2 is just a list (that is, a procedure, ect...) like i've described abode, but... what is l1? A symbol? A sequence of character? And whatever it is, how is it implemented within the language? Thanks!

Answer 1

l1 is also just a list containing the same elements. Note that this also returns #f:

(define l1 '(a b c))
(define l2 '(a b c))
(eq? l1 l2)

While this returns #t:

(define l1 '(a b c))
(define l2 (list 'a 'b 'c))
(equal? l1 l2)

The reason is that eq? checks whether l1 and l2 are references to the same object in memory, while equal? checks whether they have the same contents.

Answer 2

Lists are not atoms, that's the important part here. Symbols though are atoms, that means that when they are the same, they reside in the same memory, they are like numbers and can indeed be seen as pointers. Symbols are not mutable too, a symbol foo is like a number 3.

Lists however are not atoms, two lists, or strings, of vectors with the same contents can very well reside into two different places of memory.

eq? tests on memory location only. eqv? tests in equivalence, what that is is vague and it depends on which implementation, the Scheme standard is fairly liberal with this, it only says that it must at least be a superset of eq? basically. equal? on the other end tests on structural equality and does so recursively, so it's a very expensive operation and that's why symbols are often preferred to strings for identifiers.

(define l1 (list 1 2 3))
(define l2 (list 1 2 3))
(eq? l1 l2) ; ===> #f in most implementations
(equal? l1 l2) ; ===> #t in all implementations
(eqv? l1 l2) ; ===> #t in some implementations
(define l3 (cdr l1))
(define l4 (cdr l1))
(eq? l3 l4) ; ===> #t, this means that they 'share memory', if you change l3 or l4, l1 will change with it, beware. This is how car and cdr work, they do not copy.
(define l6 (cons 1 l4));
(eq? l1 l6) ; ===> #f again, cons does allocate new memory, but the tails may very well share it, s in this case, l6 does share its tail with all lists except l2 here in memory. 

Also, a bit of terminology, cons creates a pair, this is different from a list of two elements, it creates a pair (a . b) the list (a b) is in fact identical to the pair (a . (b . ()))

Also, cons and car and cdr are primitives, the implementation you see below is the demonstration in Structure and Implementation of Computer Programs that shows they aren't strictly needed as them, but having them as primitives dramatically increases performance, so better not re-define your cons, car and cdrs.

Answer 3

> > (define l1 '(a b c))
> > (define l2 (list 'a 'b 'c))
> > l1 (a b c)
> > l2 (a b c)
> > (eq? l1 l2)
> #f

Ok, l2 is just a list (that is, a procedure, ect...) like i've described abode, but... what is l1? A symbol? A sequence of character? And whatever it is, how is it implemented within the language? Thanks!

A definition has the form:

(define <name> <expression>)

At runtime the expression <expression> is evaluated, and the result is a value. That value is stored somewhere in memory. In order to use this value in other calculations, one can use the name <name>. The termininology is that <name> is bound to the value.

The important thing to note is, that the name <name> only appears in your source code. It is not present at runtime. Asking whether the name l1 is a symbol therefore makes no sense.

One possible strategy for a compiler to translate (define <name> <expression>) is as follows (ignoring that Scheme implementations have garbage collection).

1. Reserve a memory cell m for a pointer p
2. Output code that computes the value v of
3. Store the address of the memory cell that contains v in the memory cell m.

Note, that the name <name> does not appear in this list.