Symbolic data

Lesson 05 gave us unbounded hierarchical structure and a clean way to process it — but every leaf, every accumulate, every result, bottomed out in a number to be evaluated. That hid a rule we never questioned: data must be evaluated to its value. This lesson lifts exactly that rule. With quotation we can refer to a symbol itself — hold the name x rather than the number it stands for — and the moment we can, the same pairs and the same conventional interfaces from Lesson 05 begin processing representations: an algebraic expression to be differentiated, a set, a Huffman code. Programs stop computing with quantities and start computing with the structure of expressions.

1 · Quotation — referring to a symbol, not its value

Until now, writing x in a program meant "the value bound to x." But to do algebra we must talk about the symbol x — the thing that appears in x + 3 — without asking what number it holds. That is quotation: a way to say "take this literally as data, do not evaluate it." In Lisp it is the quote mark; in our JavaScript we represent a quoted symbol as a string and an expression as a list (built from Lesson 05's pairs).

// the SYMBOL x, as data — a string, never looked up
const x = "x";
// the EXPRESSION  x + 3  as a tagged list:  ["+", "x", 3]
const e = list("+", "x", 3);
// without quotation we could only ever store the *number* x holds;
// with it we store the name itself and inspect its structure.

This is the rule from Lesson 05 lifted: a leaf no longer has to be a value to be evaluated — it can be a symbol that stands for itself. Equality of symbols becomes meaningful ("x" === "x" asks "same name?", not "same value?"), and lists of symbols become expressions, rules, and codes. Everything below is a consequence of being able to hold structure instead of evaluating it.

2 · Symbolic differentiation — tree rewriting

Differentiation is defined by structural rules: the derivative of a sum is the sum of the derivatives; the derivative of a product follows the product rule; and so on. Each rule says "an expression of this shape rewrites to an expression of that shape." So differentiation is a tree rewrite: walk the expression tree, dispatch on its shape, build a new tree. First, selectors behind an abstraction barrier (Lesson 04) so the algorithm never touches the list layout (isPair(x) is the primitive predicate from Lesson 05 — true for a pair, false for an atom):

const isVar    = e => typeof e === "string";
const isSame   = (e, v) => e === v;
const isSum    = e => isPair(e) && head(e) === "+";
const isProd   = e => isPair(e) && head(e) === "*";
const addend   = e => head(tail(e));            // a in ["+", a, b]
const augend   = e => head(tail(tail(e)));      // b
const multiplier   = e => head(tail(e));
const multiplicand = e => head(tail(tail(e)));

function deriv(e, v) {
  if (typeof e === "number") return 0;                 // d/dv c = 0
  if (isVar(e))   return isSame(e, v) ? 1 : 0;          // d/dv v = 1, else 0
  if (isSum(e))   return makeSum(deriv(addend(e), v),   // sum rule
                                 deriv(augend(e), v));
  if (isProd(e))  return makeSum(                       // product rule
        makeProd(multiplier(e),   deriv(multiplicand(e), v)),
        makeProd(deriv(multiplier(e), v), multiplicand(e)));
  throw new Error("unknown expression");
}

deriv(["*","x","y"], "x")
  = makeSum( makeProd("x",            deriv("y","x")),    // u * v'
             makeProd(deriv("x","x"), "y") )              // u' * v
  = makeSum( makeProd("x", 0),                            // deriv("y","x") -> 0
             makeProd(1,   "y") )                         // deriv("x","x") -> 1

function makeSum(a, b) {
  if (a === 0) return b;            // 0 + b = b
  if (b === 0) return a;
  if (typeof a === "number" && typeof b === "number") return a + b;
  return list("+", a, b);
}
function makeProd(a, b) {
  if (a === 0 || b === 0) return 0; // 0 * _ = 0
  if (a === 1) return b;            // 1 * b = b
  if (b === 1) return a;
  if (typeof a === "number" && typeof b === "number") return a * b;
  return list("*", a, b);
}

3 · Representing sets — three layouts, three cost models

A set is an abstract object (a collection with no duplicates) with operations isMember, adjoin, union, intersection. Lesson 04 told us one abstract object admits many representations behind one barrier; here three layouts honor the same contract but cost wildly different amounts. n is the set size.

// unordered-list membership: linear scan
function isMember(x, set) {
  if (isEmpty(set)) return false;
  return head(set) === x ? true : isMember(x, tail(set));
}
// ordered-list membership: stop as soon as we pass x
function isMemberOrdered(x, set) {
  if (isEmpty(set) || head(set) > x) return false;   // can't be further on
  return head(set) === x ? true : isMemberOrdered(x, tail(set));
}

The abstract operations are identical; the cost model is the representation's signature. Choosing a layout is choosing which operation you want to be cheap — and there is no free lunch (the tree's fast lookup costs balancing discipline). This is the same lesson as rational reduction (04), now with the trade-off made quantitative.

4 · Huffman trees — the cost model is the shape

A Huffman encoding tree assigns short bit-codes to frequent symbols and long codes to rare ones, minimizing total message length. It is built bottom-up: repeatedly merge the two lowest-weight nodes into a parent whose weight is their sum, until one tree remains. A symbol's code is the path from the root (left = 0, right = 1); frequent symbols end up near the root with short paths.

freqs: A=8  B=3  C=1  D=1            merge two smallest each step
                                      ((C1 D1)=2)  then (B3 . 2)=5  then (A8 . 5)=13
        ( . )13
        /     \
      A=8     ( . )5          A -> 0          (1 bit, most frequent)
              /    \          B -> 10         (2 bits)
            B=3   ( . )2      C -> 110        (3 bits, rarest)
                  /    \      D -> 111        (3 bits)
                C=1    D=1

The encode/decode procedures are tree walks over this structure (a perfect fit for Lesson 05's tree recursion, operating on symbols quoted as data from §1). The point worth keeping: the cost model is visible in the tree's geometry. Depth equals code length; merging the two smallest weights at each step is precisely what pushes rare symbols deep and frequent ones shallow, so the shape is the optimization. Reading the tree, you read the cost. Different symbol frequencies grow a different-shaped tree — a different representation of the same code idea, each tuned to its data.

Common mistakes / failure modes

Checkpoint exercise

Where this points next

Symbolic data already showed the crack: the same abstract object — an expression, a set, a code — admits many representations with different costs and shapes. Our deriv dispatched on shape with a tower of if (isSum) … else if (isProd) …, and our set operations would need a separate version per layout. Add complex numbers in rectangular and polar form, or one more expression type, and that conditional tower grows quadratically and must be edited in every operation whenever a representation is added — it does not scale and it is not additive. Lesson 07 confronts exactly this pressure: how to support multiple representations of one object cleanly, with tagged data and data-directed programming so a new representation installs itself without editing any existing operation. The unscalable conditional dispatch we just wrote is what forces it.

Interview prompts

• What problem does quotation solve, and what rule does it lift? (§1 — it lets a program refer to a symbol as data rather than evaluating it to a value, lifting the "data must be evaluated" rule so leaves can be symbols/expressions.)
• Explain symbolic differentiation as tree rewriting. (§2 — each derivative rule maps an expression of one shape to another; deriv dispatches on shape behind selectors and builds a new tree by the sum/product rules.)
• Why must deriv output be simplified, and where does simplification belong? (§2 — naive constructors emit correct but ugly trees like x*0+1*y; put simplification inside the constructors below the abstraction barrier so representation choices stop leaking into the result.)
• Compare three set representations and their costs. (§3 — unordered list (Θ(n) membership), ordered list (early-stop membership, linear merge intersection), balanced binary tree (Θ(log n) membership, needs balancing); pick by which operation must be cheap.)
• How does a Huffman tree encode its cost model in its shape? (§4 — depth = code length; merging the two lowest weights each step places frequent symbols near the root (short codes) and rare ones deep (long codes), so the geometry is the optimization.)
• Why is symbol equality different from value equality here? (§1, common mistakes — quoted symbols compare by name ("x"==="x"), asking "same symbol?" not "same value?"; conflating them reintroduces evaluation.)
• Why does conditional dispatch on representation fail to scale? (§Where next — each operation needs an arm per representation, so adding a representation forces edits across every operation (non-additive, growing toward quadratic) — the motivation for data-directed programming.)