As a car repair expert and content creator for carcodescanner.store, I’ve spent years diving deep into the intricate systems of vehicles. Interestingly, the world of programming, especially languages like Scheme, sometimes feels similarly complex yet elegantly designed. While seemingly unrelated, the logical thinking required for both car diagnostics and coding shares surprising parallels. Today, we’ll explore a fundamental aspect of Scheme programming that might seem a bit cryptic at first: the dot notation and its relationship to car and cdr. This is crucial for anyone learning Scheme and understanding how data is structured within this powerful language.
Like many venturing into new fields, my journey into programming languages started with a desire to broaden my horizons beyond the familiar. Having worked extensively with C and C++ in embedded systems and scripting languages, I was drawn to the functional programming paradigm. A friend introduced me to Lisp, pointing me towards Paul Graham’s insightful essay. Inspired by the concepts, I decided to delve into Scheme, armed with a digital copy of the legendary SICP (Structure and Interpretation of Computer Programs).
That was a year ago. My progress? I’ve just completed the first chapter of SICP. It’s not for lack of trying! The exercises in SICP are notoriously challenging, demanding a deep understanding even for seemingly simple concepts. I recall spending three days wrestling with a problem that required just two lines of code. Despite the slow pace, this deep dive into Scheme has fundamentally reshaped how I approach code.
Alongside SICP, I’ve been exploring Rust, working through The Rust Programming Language (TRPL). To solidify my learning of both Rust and Scheme, I embarked on an ambitious project: writing a Scheme interpreter in Rust. The catch? My Scheme knowledge was limited to SICP chapter one, and my formal understanding of language design was non-existent. Essentially, I was attempting to build a language with barely any formal training in Programming Language Theory (PLT) and primarily experience in imperative languages.
So, how does one approach writing a Scheme interpreter with such a background? Instead of diving into formal language theory texts, I opted for a more hands-on, exploratory approach. I decided to reverse-engineer Scheme by observing its behavior directly. This led to some fascinating discoveries, particularly around the concept of the “dot” in Scheme, which is the focus of this article.
Reverse-Engineering Scheme’s Dot Notation for car and cdr
While not reverse engineering in the traditional, rigorous sense, my method involved observing and deducing rules from the behavior of existing Scheme implementations. I used two prominent Scheme environments: GNU Guile, adhering to the R5RS standard, and Racket, a more expansive language in the Lisp family. By feeding various code snippets into their REPLs (Read-Eval-Print Loops), I meticulously observed their responses, focusing particularly on how the “dot” notation functioned.
Scheme’s power and elegance stem partly from its homoiconicity. This means code and data share the same fundamental structure – the list. Lisp, after all, stands for List Processor. Until implementing my own language, the significance of this was something I hadn’t fully appreciated. It’s easy to take core language features for granted until you need to build them from scratch.
So, what exactly is a list in Scheme? In its simplest form, it’s anything enclosed in parentheses. Given that almost everything in Lisp syntax uses parentheses, this might seem like a trivial observation. However, the “list-centric” nature is fundamental.
Lists are designed for easy manipulation. Scheme fundamentally works with two primary data structures: lists and atoms. Lists are collections composed of atoms or other lists. They can be broken down into individual components, and atoms can be combined to form lists. Atoms are the indivisible units, like numbers (1, 2, 3) or symbols. A list of these numbers is represented as '(1 2 3).
Scheme provides three core procedures for list manipulation: cons, car, and cdr. The names, while not immediately intuitive (due to historical reasons), are essential to Scheme. cons is for “construction,” building lists. Let’s see it in action using Racket’s REPL:
> (cons 1 '(2 3))
'(1 2 3)Note: Throughout this article, I’ll use Racket’s REPL format for clarity. Racket’s default REPL is minimalistic, using
>as the prompt and typically placing output on the next line. Guile’s REPL is more verbose. While Guile served as a reference implementation, both Guile and Racket exhibit consistent behavior for the examples discussed here.
car retrieves the first element of a list, and cdr returns the rest of the list after the first element.
> (car '(1 2 3))
1
> (cdr '(1 2 3))
'(2 3)Combined with recursion, a cornerstone of functional programming, these procedures enable list traversal. You can process a list by extracting the first element with car, manipulating it, and then recursively applying the same process to the remainder of the list obtained by cdr. This might seem basic, but it’s incredibly powerful because, in Scheme, everything is fundamentally a list.
However, there’s a slight nuance. cons, car, and cdr don’t strictly operate on lists in the way we might initially think. They work with pairs.
Pairs? What are pairs? Just when we thought we had lists and atoms figured out! A pair is a more fundamental structure than a list. It’s a combination of two elements, represented in Scheme’s printed form as a list with a dot separating the first and second elements: (1 . 2). Crucially, a pair isn’t quite a list; it’s a cons cell.
> (cons 1 2)
'(1 . 2)And here’s the key: lists are built from pairs.
If you’re familiar with linked lists in languages like C, you’ll know they are composed of nodes. Each node stores data and a pointer to the next node. The end of the list is often indicated by a special null pointer. A minimal list, in essence, consists of at least two components: the data element and the pointer (even if it’s a null pointer). This concept aligns remarkably with Scheme’s pairs.
Consider this example:
> (cons 1 '())
'(1)Because lists are essentially nested pairs, the final pair in a standard list has '() (the empty list) as its second element. We can construct longer lists by nesting cons operations:
> (cons 1 (cons 2 (cons 3 '())))
'(1 2 3)Let’s unravel how this works. cons creates a pair. If we manually evaluate the nested cons expression, we get:
'(1 . (2 . (3 . ())))Now, how does '(1 . (2 . (3 . ()))) become '(1 2 3)? Through observation, I’ve deduced two “dot rules”:
- Dot Position: The dot must be the second-to-last element within a parenthesized expression.
- Dot Removal: If a dot is followed immediately by an opening parenthesis, the dot and the matching parentheses pair can be removed.
Applying these rules to '(1 . (2 . (3 . ()))):
Start with the innermost part: '(3 . ()). Applying rule 2, we remove the dot and parentheses, resulting in '(3). Now we have '(1 . (2 . (3))). Applying rule 2 again to '(2 . (3) gives '(2 3). Finally, applying rule 2 to the last dot in '(1 . (2 3)) produces the familiar list '(1 2 3).
Note: These “dot rules” are my interpretation based on observation and are likely a simplification of the underlying parsing and printing mechanisms. The dot is syntactic sugar for representing the internal pair structure.
This explains why car and cdr work on both pairs and lists. car extracts the element before the first dot (or the first element in list notation), and cdr returns everything after the first dot (or the rest of the list).
> (car '(1 . (2 . (3 . ()))))
1 ;; 1 is before the `. (2 . (3 . ()))'
> (cdr '(1 . (2 . (3 . ()))))
'(2 . (3 . ())) ; or '(2 3) for shortTherefore, whenever Scheme encounters something like (a b c), it internally interprets it as (a . (b . (c . ()))). This elegant representation is why car and cdr function seamlessly with both pairs and lists – because lists are fundamentally built from pairs.
The Beauty of Dot Notation in Scheme Coding
Initially, I questioned the validity of my dot rule observations when I encountered an unexpected behavior. But first, let’s quickly recap how procedures (functions) are defined in Scheme:
> (define (sum a b) (+ a b))This defines a procedure named sum that takes two arguments, a and b, and returns their sum. We can call it like this:
> (sum 1 3)
4While experimenting with the dot notation rules, I wondered what would happen if I used a dot in the procedure definition syntax:
(define (foo . bar) bar)Surprisingly, this didn’t throw an error. Instead, it worked, but in a way that initially seemed nonsensical:
> (foo 22)
'(22)“What’s going on?” I thought. Even more strangely, passing two arguments also worked:
> (foo 1 2)
'(1 2)At this point, I was questioning my entire understanding. However, after some contemplation, the underlying logic became clear, revealing a beautiful aspect of Scheme’s design.
The standard procedure definition syntax (define (sum a b) (+ a b)) is actually syntactic sugar. Under the hood, it’s equivalent to defining sum as a lambda expression:
(define sum (lambda (a b) (+ a b)))While we could always use this lambda form, the (define (sum a b) ...) syntax is much more convenient.
So, what happens when we introduce the dot into the procedure definition like (define (foo . bar) bar)? To understand this, we need to revisit the fundamental role of lists and the primitive list operations.
Note: The following explanation draws from my experience implementing GRScheme, my Scheme-like interpreter. While real Scheme implementations may have internal variations, the core principles are likely similar. More details on GRScheme will be shared later.
To transform (define (foo bar) bar) into (define foo (lambda (bar) bar)), the Scheme interpreter essentially performs these steps:
- Extract the procedure name (
foo) using something akin tocaron the list(foo bar). - Extract the argument list
(bar)using something likecdron(foo bar). - Construct the
lambdaexpression using the extracted name and arguments.
Now, consider what happens when we apply cdr to a dotted list:
> (cdr '(foo . bar))
'barcdr on a dotted pair returns the second element without enclosing parentheses. Applying this to the procedure definition (define (foo . bar) bar), the interpreter would extract foo as the name (using car-like operation) and bar (without parentheses) as the argument part (using cdr-like operation). This leads to an interpretation similar to: (define foo (lambda bar bar)), where lambda takes bar as a single, potentially variable-length argument, not a fixed list of arguments.
Let’s test this lambda form directly:
> ((lambda x x) 1)
'(1)
> ((lambda x x) 1 2)
'(1 2)This is a procedure that accepts a variable number of arguments! Why? Let’s analyze it using car and cdr concepts.
When we evaluate (lambda x x), Racket returns a procedure representation (e.g., #<procedure:x>). Let’s conceptually represent it as (#procedure 1).
Now, applying car and cdr:
(car (#procedure 1)) ; conceptually extracts the procedure itself
#<procedure:x>
(cdr (#procedure 1)) ; conceptually extracts the arguments
'(1)The arguments are treated as a single list: '(1). The lambda defined as (lambda x x) takes one “thing” (x) and returns it. In the first example, x is bound to the list '(1), hence the result '(1).
Similarly, for ((lambda x x) 1 2), the arguments become '(1 2), which is then returned.
Why doesn’t this variable argument behavior occur with standard lambda definitions like (lambda (a b) ...)? My hypothesis is that when arguments are enclosed in parentheses in the lambda definition, Scheme expects a list of arguments of a specific structure and attempts to bind list elements to the argument names. Without parentheses around the argument in lambda, it treats everything after the lambda keyword as a single, potentially variable-length argument list.
Let’s summarize our Scheme knowledge so far:
- Everything is fundamentally a list.
- More accurately, everything is built from pairs, and lists are sequences of nested pairs ending in an empty list.
- A pair or cons cell uses a dot
.to separate its two elements. carandcdruse the dot (or list structure) to determine what to extract from a cons cell or list.
Implementing Dot Notation and car/cdr in an Interpreter (GRScheme)
When I began writing this article, I hadn’t anticipated that I’d still be working on my Scheme interpreter prototype, GRScheme, by the time it was finished. The current, still evolving, GRScheme implementation is available here. It directly utilizes the concepts discussed above to evaluate Scheme code, although it’s still a work in progress.
GRScheme’s core evaluation logic revolves around these functions:
parse: Converts text input into GRScheme’s internal data structure.eval: Recursively evaluates the parsed expression tree.apply: Applies procedures to expressions.get_first_subexpression: Extracts the first sub-expression from a given expression tree (analogous tocar).get_rest_subexpression: Extracts the remaining sub-expressions as a tree (analogous tocdr).
Other functions handle built-in procedures like car, +, lambda, define, etc.
A crucial point is that GRScheme doesn’t inherently have a “dot” as a fundamental data type. Instead, it emulates the behavior of the dot notation to align with standard Scheme. I suspect that even standard Scheme implementations might not store the dot explicitly as a separate entity internally, but rather as a syntactic marker.
After parsing Scheme code, GRScheme creates a tree-like Abstract Syntax Tree (AST) that directly represents the code structure. This tree-based representation simplifies parsing significantly and allows for a more intuitive way to think about Scheme code, as it mirrors the inherent tree-like nature of Lisp syntax. Parentheses and atoms are represented as nodes in this tree. Procedure calls are easily identified by checking if a node is an opening parenthesis.
get_first_subexpression and get_rest_subexpression are generalized versions of car and cdr, operating directly on the AST. Because dot notation is emulated, these functions check for the presence of a dot node in the tree to handle pairs and lists correctly. While not direct car and cdr equivalents, they provide the underlying mechanisms for list and pair manipulation within GRScheme. True car and cdr in GRScheme are built upon these functions, incorporating quoting and other Scheme semantics, topics for future discussions.
As mentioned, GRScheme emulates the dot. In the AST, the dot is stored as a node. Let’s visualize how '(a . b) is represented in GRScheme’s data structure:
Note: Because quoted lists are written in shorthand (e.g.,
'(a . b)is shorthand for(quote (a . b))), the tree representations might appear more complex than the input. For example,'(a . b)becomes(quote (a . b))in the tree.
The tree for '(a . b) has a root node ( with children quote and another (. This second ( node then has children a, ., and b.
In contrast, a “real” Scheme implementation likely represents a pair using cons cells, which are data structures holding two pointers, as depicted below:
Lists in GRScheme are represented as trees with a variable number of children per node. For instance, '(1 2 3) in GRScheme is:
Let’s compare this to the dotted list representation '(1 . (2 . (3 . ()))) in GRScheme:
Each subtree in the dotted list representation in GRScheme has exactly three nodes. However, in a standard Scheme, lists as sequences of pairs are essentially binary trees, with each cons cell having two branches:
GRScheme’s parser is designed to handle dot notation, recognizing the dot rules discussed earlier. Consequently, both '(1 2 3) and '(1 . (2 . (3 . ()))) are parsed into the same internal tree structure in GRScheme:
Lists that don’t end with an empty list, like '(1 2 . 3) and '(1 . (2 . 3)), are parsed similarly:
In a real Scheme, these “improper lists” would be represented as:
Applying car to '(1 2 . 3) in Scheme yields 1. Applying cdr gives '(2 . 3). Applying cdr again to the result gives 3. GRScheme emulates this behavior by analyzing the tree structure during cdr operations, checking for the dot node, which might not be the most performant approach but achieves the desired functionality.
The Role of the Dot in Scheme Coding and GRScheme
Reflecting on the dot notation, it appears to be a syntactically elegant way to represent binary trees that are not necessarily terminated by a null pointer (or empty list in Scheme terms). However, this also suggests that the dot’s primary purpose is for representing these specific cases. While GRScheme emulates dots by storing them explicitly in the tree, this might not be the most semantically accurate approach.
Given that GRScheme’s underlying data structure is a more general graph, rather than strictly binary trees, the concept of “pairs” as distinct cons cells might be less relevant. Pairs in standard Scheme are intrinsically linked to the binary tree structure and the cons cell concept. In GRScheme, lacking cons cells, the significance of pairs in the traditional Scheme sense diminishes. This is a key divergence from standard Scheme. Algorithms relying heavily on direct cons cell manipulation might behave differently in GRScheme.
To potentially address this, I considered introducing a new procedure in GRScheme, alongside car and cdr, tentatively named “Contents of Cons cell Representation” (ccr). ccr would aim to return the second element of a pair directly if it’s the final element, or behave like cdr otherwise, always returning a list. This is still an evolving idea and might introduce ambiguity. Alternatively, the existing cadr procedure (which gets the second element of a list) might suffice in many cases.
I plan to delve deeper into GRScheme’s design and implementation in a subsequent article. The current GRScheme prototype has limitations and areas for improvement, which I intend to address in future development.
