schemethe-little-schemer

Is the scope of primitive functions in The Little Schemer incorrect?


Consider the following s-expression:

((lambda (car) (car (quote (a b c)))) cdr)

In most scheme implementations I've tried, this evaluates to (b c) because cdr is passed to the lambda, which names it car, taking precedence over the primitive implementation of car.

The Little Schemer provides an implementation of scheme written in scheme in chapter 10. That implementation returns a for the above expression, which seems incorrect to me.

It's clear why that implementation behaves that way: the names of primitive functions are treated as *const rather than *identifier here. A *const which is not a number or boolean is rendered as a primitive and this is eventually hardwired to the actual primitives.

I believe that the correct implementation would be to have no special detection of primitive names, but rather to create an initial table in the value function that contains an entry mapping the primitive names to the actual primitive implementations.

My question is: is this a bug in The Little Schemer's implementation of scheme? Is this behaviour well specified in scheme, or was it maybe not well specified in 1974 when the book was written?


Solution

  • Is it a bug?

    The question whether it is a bug or not is to establish if the interpreter is supposed to follow Scheme scoping rules. Since you mention the year 1974 it is the year before the first Scheme report was posted, but many of the ideas were probably written about at the time and what was to become Scheme were small interpreters that probably were shared between research students with various subtle differences.

    The little Schemer was originally called The little Lisper and worked under a Lisp later to become Common Lisp. When rewriting it to follow Scheme they tried to keep most of the code from earlier so it is likely the interpreter has different features than Scheme.

    What the RNRS Scheme reports say

    If the interpreter is to conform to the scheme reports it must allow for bindings to shadow the top level bindings. Here is a quote from the R5RS report about Variables, syntactic keywords, and regions

    Every mention of an identifier refers to the binding of the identifier that established the innermost of the regions containing the use. If there is no binding of the identifier whose region contains the use, then the use refers to the binding for the variable in the top level environment

    For later reports like the same section in R6RS top level is replaced with "definition or import at the top of the enclosing library or top-level program".