FEXPRs vs. vtable: The Inner Workings of the LispE Interpreter

LispE presents a fascinating architectural contradiction: it functions as an interpreter of compiled objects.

Typically, developers face a binary choice:

1. Maintain original source code: This ensures high malleability and flexibility, but sacrifices machine-level optimization.
2. Compile to binary: This provides extreme efficiency, but the resulting code is rigid and locked to a specific machine architecture.

While one can usually optimize in either direction, the cost is often the loss of homoiconicity—the property where code and data are interchangeable. LispE refuses to accept this trade-off.

The Architectural "Miracle"

LispE solves this by transforming every language instruction into a derived class that implements an eval method. All these classes inherit from a single root class: Element.

By using a std::vector<Element*>, LispE can store these objects together. This allows the Abstract Syntax Tree (AST) to remain intact while each individual node is optimized using the full power of C++.

The Core Equivalence

The entire system rests on a specific mathematical and logical equivalence:

$\text{datum: } f() \iff F.\text{eval}()$ $\text{instruction: } f(a_1, \dots, a_n) \iff F(a_1, \dots, a_n).\text{eval}()$

In this model:

• $F$ is an instance of a class derived from the universal Element root.
• Arguments are stored as sub-nodes.
• eval is a uniform method across the entire class hierarchy that takes no arguments.

Comparison of Execution Models

---

Historical Context: The FEXPR Debate

To understand LispE, we must look back at early Lisp dialects (like Lisp 1.5 and MacLisp), where operators were split into two categories:

1. EXPR: Standard functions. Arguments are evaluated before the function is called (applicative order).
2. FEXPR: Functions that receive arguments unevaluated. The FEXPR decides at runtime which arguments to evaluate and when, manually calling eval as needed.

The FEXPR Power: Because the operator controls the evaluation flow, you can implement if, quote, or complex loops as simple FEXPRs.

However, this flexibility creates a "black box" for the compiler. As Kent Pitman argued in Special Forms in Lisp (1980), FEXPRs are opaque; the static analyzer cannot perform inlining, early resolution, or other optimizations because it doesn't know what will be evaluated.

Example of FEXPR Logic

;; Conceptual FEXPR implementation of 'if'
(fexpr my-if (test then else)
  (if (eval test) 
      (eval then) 
      (eval else)))

LispE addresses these same constraints but utilizes the Element.eval() equivalence instead of the traditional FEXPR mechanism.

---

Realizing Homoiconicity in C++

In LispE, the distinction between "code" and "data" is erased.

• Instructions are simply std::vector<Element*>, where each cell is an Element capable of evaluating itself.
• Data is treated as a degenerate case of an instruction. Specifically, a datum is an instruction with zero arity whose evaluation rule is the identity function.

$\text{Data} \implies X.\text{eval}() \to X$

This means data is the fixed point of eval. Because both a complex list (which descends into sub-evaluations) and a simple value (which returns itself) share the same type, LispE achieves true homoiconicity within a C++ framework.

System Logic Flow

---

The Necessity of Immutability

The equivalence $f(a_1, \dots, a_n) \iff F(a_1, \dots, a_n).\text{eval}()$ is only valid if the object $F$ is immutable.

If the act of evaluation were to mutate the object or its children, the following would occur:

• The first call to eval() would produce one result.
• The second call would encounter a modified state, producing a different result.

To maintain the mathematical integrity of the system, LispE requires:

• Immutable Element nodes.
• Consistent return values for identical expressions.
• Substitution transparency (the ability to replace an expression with its value).

Figure 1: Conceptual representation of the LispE AST where each node is a C++ object.