A real project, functions over data, validated structs, and the first real interpreter

Milestone 1Racket, DrRacket, and raco

Goal

Turn the instalment's shell experiments into a real, multi-module langfac project, with its first real module and the compile/run/test cycle you will use for the rest of the course.

Concepts

S-expressions, define, modules, and the REPL, applied for the first time to a project rather than one-off expressions.

Design

The toolkit needs, from the very first milestone, one small but genuinely load-bearing piece: a way to attach a human-readable name to a value, used throughout later milestones for error messages that say which account, rule, or robot went wrong, not just that something did.

Implementation

langfac/
├── info.rkt
├── main.rkt
├── labeled.rkt
└── tests/
    └── labeled-tests.rkt

;; labeled.rkt
#lang racket
(provide labeled labeled? labeled-name labeled-value)

(struct labeled (name value) #:transparent)

;; main.rkt
#lang racket
(require "labeled.rkt")
(provide (all-from-out "labeled.rkt"))

main.rkt re-exporting everything from labeled.rkt is the project's public entry point — (require "main.rkt") from anywhere else in the project, or eventually from outside it, is meant to be the one line that pulls in the whole toolkit's public surface, the same role Perl's top-level Strata.pm or Go's package-level exports played in earlier courses.

Verified

> (require "labeled.rkt")
> (define l (labeled "checking" 2400.00))
> (labeled-name l)
"checking"
> (labeled-value l)
2400.0

Experiment

Construct a second labeled value with an exact integer instead of a decimal literal — 2400, not 2400.00 — and compare what prints back.

(define l2 (labeled "checking" 2400))
(labeled-value l2)
(exact? (labeled-value l2))

> (labeled-value l2)
2400
> (exact? (labeled-value l2))
#t

No .0 this time, and exact? confirms why: a literal written without a decimal point is an exact integer, and Racket only normalises the way 2400.00 did above when a number is inexact in the first place. Nothing about labeled itself changed — the same struct, the same accessor — only the kind of number handed to it did.

(define (labeled-map f l)
  (labeled (labeled-name l) (f (labeled-value l))))

Checkpoint

1. What is the difference between what labeled.rkt provides and what main.rkt provides?
2. Why does a decimal literal like 2400.00 print back differently from how it was written?

Milestone 2Functional groundwork

Goal

Build the pure, data-handling functions the rest of the toolkit needs — before any macro or interpreter exists to use them — the same "get the data model right while it is still trivial to test" instinct Erlang's Milestone 2 and Go's Milestone 1 both applied.

Concepts

Lists, pairs, map/filter/foldl, recursion, and match applied to more than one shape at once.

Design

Every function here takes a plain Racket list and returns a plain number — not a custom "dataset" struct wrapping one, and not a labeled value from Milestone 1. The toolkit does not yet know what these numbers will eventually represent (an account balance, a robot's recorded positions, a benchmark's measured timings), so keeping sum, average, minimum, and maximum ignorant of all of that, working over the single simplest shape Racket gives you for "a bunch of values," is what lets these same four functions get reused unchanged wherever a later milestone needs one. foldl specifically, rather than hand-written recursion, is the other half of the decision: all four are "reduce a list to one value," and writing that shape once as a call to a built-in higher-order function is both shorter and, per the comparison below, the exact pattern every other course in this curriculum converges on under a different name.

Implementation

;; stats.rkt
#lang racket
(provide sum average minimum maximum)

(define (sum xs) (foldl + 0 xs))

(define (average xs)
  (if (empty? xs) 0 (/ (sum xs) (length xs))))

(define (minimum xs) (foldl min (first xs) (rest xs)))
(define (maximum xs) (foldl max (first xs) (rest xs)))

Verified

> (sum (list 1 2 3 4 5))
15
> (average (list 10 20 30))
20
> (minimum (list 5 2 8 1 9))
1
> (maximum (list 5 2 8 1 9))
9

Explanation

(foldl min (first xs) (rest xs)) is worth pausing on: rather than special- casing an empty list with an awkward sentinel value ("what is the minimum of nothing?"), it seeds the fold with the list's own first element and folds over the rest — which is also, not incidentally, why minimum and maximum both raise a clear error on an empty list (first of '() fails) rather than silently returning a made-up default the way average deliberately chose to for zero.

Experiment

Call average and minimum on the same empty list, and predict, before running it, whether both behave the same way.

(average (list))
(minimum (list))

> (average (list))
0
> (minimum (list))
; first: contract violation
;   expected: (and/c list? (not/c empty?))
;   given: '()

They do not — average silently returns 0 for an empty list, a deliberate choice made explicit in its own if, while minimum raises immediately, because its foldl seed is (first xs) and first has nothing to return on an empty list. Two different, equally deliberate answers to "what should the empty case do," living side by side in the same four-function file — worth noticing precisely because nothing about average's or minimum's code loudly announces that they disagree.

(require racket/list)
(define (group-by-sign xs) (partition negative? xs))

(define (describe-trend xs)
  (match xs
    [(list a b c) #:when (and (< a b) (< b c)) 'rising]
    [(list a b c) #:when (and (> a b) (> b c)) 'falling]
    [(list _ _ _) 'flat]))

Checkpoint

1. Why does minimum seed its fold with the list's own first element rather than a sentinel like +inf.0?
2. What does matching (list a b c) against a list of the wrong length actually do?

Milestone 3Structs and contracts

Goal

Design the toolkit's core data types with validation built into construction itself, so an invalid value cannot exist in the first place rather than needing to be checked for after the fact.

Concepts

struct, the #:guard option for constructor-time validation, and contracts on provide for validating at the module boundary.

Design

Two different validation points, used for two different purposes, both meeting in this milestone. A #:guard on a struct makes an invalid instance impossible to construct at all, anywhere, including inside the module that defines it — the strongest guarantee available. Contracts on provide check values crossing the module boundary specifically, which is the right place to check when the validation genuinely only matters for external callers (internal code that already maintains its own invariants pays no contract-checking cost for calls to itself).

Implementation

;; robot.rkt
#lang racket
(provide (struct-out robot) move)

(struct robot (name x y energy) #:transparent
  #:guard (lambda (name x y energy type-name)
    (unless (>= energy 0)
      (error type-name "energy cannot be negative: ~a" energy))
    (values name x y energy)))

(define (move r dx dy)
  (struct-copy robot r
    [x (+ (robot-x r) dx)]
    [y (+ (robot-y r) dy)]
    [energy (max 0 (- (robot-energy r) 1))]))

Explanation

(provide (struct-out robot) move) — struct-out exports the constructor, predicate, and every accessor for robot in one line, rather than listing robot, robot?, robot-name, robot-x, robot-y, and robot-energy individually. The guard runs on every construction, including the one inside move's own struct-copy — move a robot until its energy would go negative and the guard rejects it just as firmly as a hand-written bad literal would, which is exactly why move clamps with (max 0 ...) itself rather than relying on the guard to catch a case it should simply never produce.

Verified

> (define r (robot "wall-e" 0 0 100))
> (move r 3 4)
#(struct:robot "wall-e" 3 4 99)
> (robot "bad" 0 0 -5)
robot: energy cannot be negative: -5

Experiment

Move a robot a very long way — far past any sensible board edge — and confirm the guard, as written so far, has nothing to say about it.

(define r (robot "wall-e" 0 0 1))
(define r2 (move (move r 100000 0) 0 0))
(printf "x=~a y=~a energy=~a\n" (robot-x r2) (robot-y r2) (robot-energy r2))

$ racket robot-far.rkt
x=100000 y=0 energy=0

Accepted without complaint. The guard only ever checks energy — x and y can be anything at all right now, however far outside a sensible playing field, because nothing has told the struct that a bound on position is even a rule yet. Exercise 3 is precisely where that rule gets written.

#:guard (lambda (name x y energy type-name)
  (unless (>= energy 0)
    (error type-name "energy cannot be negative: ~a" energy))
  (unless (and (<= -100 x 100) (<= -100 y 100))
    (error type-name "position out of bounds: (~a, ~a)" x y))
  (values name x y energy))

(provide (contract-out [distance-to-origin (-> robot? (and/c real? (>=/c 0)))]))
(define (distance-to-origin r)
  (sqrt (+ (sqr (robot-x r)) (sqr (robot-y r)))))

Checkpoint

1. What does struct-out save you from writing by hand?
2. Why did move's own arithmetic need to clamp energy, rather than relying entirely on the struct's guard?
3. When would a contract on provide be the better choice over a struct guard, and vice versa?

Milestone 4An interpreter for a config language

Goal

Build a real interpreter — an AST, an environment, and an evaluator — for a tiny expression language: numbers, addition, variables, and let-bindings. This is the instalment's "code is data" claim, turned into working code for the first time.

Concepts

AST design as a set of structs, environments as association lists, recursive evaluation via match, and the distinction between quote-ing data and evaluating code that Section 2.1 introduced.

Design

Five AST node types, each a small struct: a number literal, a string literal, addition, a variable reference, and a let-binding. An environment is a list of (name . value) pairs — genuinely the simplest correct representation, and, per Milestone 2's own established idiom, already exactly the shape assoc from the standard library knows how to search.

Implementation

;; config-interp.rkt
#lang racket
(provide (struct-out num-e) (struct-out str-e) (struct-out add-e)
         (struct-out var-e) (struct-out let-e) eval-expr)

(struct num-e (val) #:transparent)
(struct str-e (val) #:transparent)
(struct add-e (l r) #:transparent)
(struct var-e (name) #:transparent)
(struct let-e (name val body) #:transparent)

(define (eval-expr e env)
  (match e
    [(num-e v) v]
    [(str-e v) v]
    [(add-e l r) (+ (eval-expr l env) (eval-expr r env))]
    [(var-e name)
     (cond [(assoc name env) => cdr]
           [else (error 'eval-expr "unbound variable: ~a" name)])]
    [(let-e name val body)
     (eval-expr body (cons (cons name (eval-expr val env)) env))]))

Explanation

One match, one clause per AST node type — this is the entire evaluator, and it reads almost like a specification of the language's semantics rather than an implementation of one: a number evaluates to itself, addition evaluates both sides and adds them, a variable looks itself up in the environment, a let evaluates its value, extends the environment with a new binding, and evaluates its body in that extended environment. (cond [(assoc name env) => cdr] ...) is a real, idiomatic Racket form worth knowing: => inside a cond clause means "if the test expression is truthy, pass that value (not just a boolean) to the function on the right" — assoc returns the whole matching pair or #f, and cdr extracts the value from it, without needing to call assoc a second time or bind an intermediate variable.

Verified

;; (let x = 2 + 3 in x + 10)
> (define prog
    (let-e 'x (add-e (num-e 2) (num-e 3))
           (add-e (var-e 'x) (num-e 10))))
> (eval-expr prog '())
15
> (eval-expr (var-e 'y) '())
eval-expr: unbound variable: y

Fifteen, correctly — x bound to 5, then x + 10 — and an unbound variable fails with a specific, immediately useful message rather than a generic pattern-match failure, because var-e's clause deliberately checks and raises its own clear error rather than letting a failed assoc propagate as something more cryptic.

Experiment

Shadow a name: build a program where an inner let rebinds x to a different value while an outer x is still in scope, and confirm each reference to x sees the binding that was actually closest to it, not the first one ever created.

;; (let x = 1 in x + (let x = 100 in x + 0))
(define prog
  (let-e 'x (num-e 1)
    (add-e (var-e 'x)
      (let-e 'x (num-e 100)
        (add-e (var-e 'x) (num-e 0))))))
(eval-expr prog '())

> (eval-expr prog '())
101

101, not 1 and not 200 — the inner (var-e 'x) uses (100), and the outer one uses 1. Nothing in eval-expr was written specifically to handle shadowing; it falls out entirely from let-e's clause consing the new binding onto the front of env and assoc always returning the first match it finds — the newest binding for a name is always the first one assoc sees, which is exactly what "closest enclosing scope wins" means, implemented with no special-casing at all.

(struct bool-e (val) #:transparent)
(struct if-e (cond then else) #:transparent)

;; in eval-expr's match:
[(bool-e v) v]
[(if-e c t e)
 (if (truthy? (eval-expr c env)) (eval-expr t env) (eval-expr e env))]

(define (truthy? v) (not (or (eq? v #f) (equal? v 0))))

(struct let*-e (bindings body) #:transparent)

[(let*-e bindings body)
 (eval-expr body
   (foldl (lambda (binding env)
            (cons (cons (car binding) (eval-expr (cdr binding) env)) env))
          env bindings))]

Checkpoint

1. Why does the evaluator need no separate parser or tokenizer for this milestone specifically?
2. What does => inside a cond clause do, and why does it avoid calling assoc twice?
3. Why does var-e's clause raise its own specific error rather than letting a failed lookup propagate some other way?

Common mistakes in Milestone 4

; eval-expr: unbound variable: x

Common mistakes in Milestones 1–4

Repository state after Milestone 4

langfac/
├── info.rkt, main.rkt
├── labeled.rkt              Milestone 1
├── stats.rkt                 Milestone 2
├── robot.rkt                  Milestone 3 (struct + guard)
├── config-interp.rkt           Milestone 4: AST + evaluator
└── tests/                       4 files

$ raco test tests/
All tests passed.
$ git commit -am "milestones 1-4: project, data, validated structs, a working interpreter"