Programming Languages: Concepts and Implementation

5.5 cons Cells: Building Blocks of Dynamic Memory Structures

To develop functions that are more sophisticated than pow, we need to examine how lists are represented in memory. Such an examination helps us conceptualize and conceive abstract data structures and design algorithms that operate on and manipulate those structures to solve a variety of problems. In the process, we also consider how we can use BNF to define data structures inductively. (Recall that in Lisp, code and data are one and the same.) In a sense, all programs are interpreters, so the input to those programs must conform to the grammar of some language. Therefore, as programmers, we are also language designers. A well-defined recursive data structure naturally lends itself ...