Daniel Holden. - Build Your Own Lisp: Learn C and Build Your Own Programming Language

• About
• Who this is for
• Why learn C
• How to learn C
• Why build a Lisp
• Your own Lisp

• Setup
• Text Editor
• Compiler
• Hello World
• Compilation
• Errors
• Documentation

• Overview
• Programs
• Variables
• Function Declarations
• Structure Declarations
• Pointers
• Strings
• Conditionals
• Loops

• Read, Evaluate, Print
• An Interactive Prompt
• Compilation
• Editing input
• The C Preprocessor

• What is a Programming Language?
• Parser Combinators
• Coding Grammars
• Natural Grammars

• Polish Notation
• Regular Expressions
• Installing mpc
• Polish Notation Grammar
• Parsing User Input

• Trees
• Recursion
• Evaluation
• Printing

• Crashes
• Lisp Value
• Enumerations
• Lisp Value Functions
• Evaluating Errors
• Plumbing

• Lists and Lisps
• Types of List
• Pointers
• The Stack & The Heap
• Parsing Expressions
• Expression Structure
• Constructors & Destructors
• Reading Expressions
• Printing Expressions
• Evaluating Expressions

• Adding Features
• Quoted Expressions
• Reading Q-Expressions
• Builtin Functions
• First Attempt
• Macros
• Builtins Lookup

• Immutability
• Function Pointers
• Cyclic Types
• Function Type
• Environment
• Variable Evaluation
• Builtins
• Define Function
• Error Reporting

• What is a Function?
• Function Type
• Lambda Function
• Parent Environment
• Function Calling
• Variable Arguments
• Interesting Functions

• Doing it yourself
• Ordering
• Equality
• If Function
• Recursive Functions

• Libraries
• String Type
• Reading Strings
• Comments
• Load Function
• Command Line Arguments
• Print Function
• Error Function
• Finishing Up

• Minimalism
• Atom
• Building Blocks
• Logical Operators
• Miscellaneous Functions
• List Functions
• Conditional Functions
• Fibonacci

• Only the Beginning
• Native Types
• User Defined Types
• List Literal
• Operating System Interaction
• Macros
• Variable Hashtable
• Pool Allocation
• Garbage Collection
• Tail Call Optimisation
• Lexical Scoping
• Static Typing
• Conclusion

You'll notice that the following chapters will all follow a similar pattern. This pattern is the typical approach used to add new features to a language. It consists of a number of steps that bring a feature from start to finish. These are listed below, and are exactly what we're going to do in this chapter to introduce a new feature called a Q-Expression.

In this chapter we'll implement a new type of Lisp Value called a Q-Expression.

This stands for quoted expression, and is a type of Lisp Expression that is not evaluated by the standard Lisp mechanics. When encountered by the evaluation function Q-expressions are left exactly as they are. This makes them ideal for a number of purposes. We can use them to store and manipulate other Lisp values such as numbers, symbols, or other S-Expressions themselves.

After we've added Q-Expressions we are going to implement a concise set of operators to manipulate them. Like the arithmetic operators these will prove fundamental in how we think about and play with expressions.

The syntax for Q-Expressions is very similar to that of S-Expressions. The only difference is that instead of parenthesis () Q-Expressions are surrounded by curly brackets {}. We can add this to our grammar as follows.

I've never heard of Q-Expressions.

Q-Expressions don't exist in other Lisps. Other Lisps use Macros to stop evaluation. These look like normal functions, but they do not evaluate their arguments. A special Macro called quote ' exists, which can be used to stop the evaluation of almost anything. This is the inspiration for Q-Expressions, which are unique to our Lisp, and will be used instead of Macros for doing all the same tasks and more.

The way I've used S-Expression and Q-Expression in this book is a slight abuse of terminology, but I hope this misdemeanor makes the behaviour of our Lisp clearer.

We also must remember to update our cleanup function to deal with the new rule we've added.

Because Q-Expressions are so similar S-Expressions much of their internal behaviour is going to be the same. We're going to reuse our S-Expression data fields to represent Q-Expressions, but we still need to add a separate type to the enumeration.

We can also add a constructor for this variation.

To print and delete Q-Expressions we do essentially the same thing as with S-Expressions. We can add the relevant lines to our functions for printing and deletion as follows.