Showing posts with label functional. Show all posts
Showing posts with label functional. Show all posts

Saturday, September 5, 2026

Githack: A Persistent Object Store for Lisp Based on Git

Git has a built-in persistent store for objects based on Merkle trees. It is tailored to store files and directories, but these are just specializations of trees of blobs. There is no reason it couldn't be used to store Lisp objects.

Githack is a Lisp object store that uses Git as its backend. It is a simple library that provides persistent objects for Lisp and a transactional interface for manipulating them. Simple atomic objects are stored as blobs and composite objects are stored as trees. Standard composite Lisp objects, such as lists, vectors, and hash tables, are supported. Custom composite objects can be created through DEFINE-PERSISTENT-STRUCT or DEFCLASS with a :STANDARD-PERSISTENT-METACLASS.

WITH-REPOSITORY is used to specify which repository to use for storing objects. WITH-TRANSACTION sets up a transaction for manipulating objects and retrieves the root object. You use standard slot accessors to walk the object tree. When you are done, you commit the transaction, and modifications are atomically written to the repository with a new root object being placed in a Git branch.

By placing the database in an orphan Git branch, you can store it right beside your source code without tangling the histories. You can use Git to manage the history of the database, branch it, and share it with others. Githack even stores object docstrings as README.md files inside the repository trees, so the stored objects are natively self-documenting in the Git web UI.

Githack comes with example code and an example database living on its own orphan branch, so if you clone the repository, you'll clone the working example database as well.


Tuesday, August 25, 2026

The Functional Refactoring Pass

This is an anecdote, not a data point, yet.

I'm a firm believer in functional programming and I consider myself a `mostly functional` programmer. I use functional programming when I can, but when a side effect is required, I'll use it. I'm not a purist.

Functional programming is supposed to have a number of advantages over imperative, procedural programming. The primary advantage is that there are provably no race conditions. You can trivially scale functional code to multiple threads and multiple processors. In theory, functional code is easier to reason about and easier to test because each function can be reasoned about and tested in isolation. In practice, functional code can become a maze of thunks and lambdas that many find difficult to read. Nonetheless, I prefer to reason about tangled lambdas than to reason about tangled state.

I believe that functional code is easier for an LLM to reason about as well. I haven't proven this, but anecdotally it seems to be the case. In theory, the LLM would gain all the usual benefits of functional programming. It would find the code easier to reason about and easier to test.

Unfortunately, the vast majority of code that the LLM has been trained on is imperative, procedural code. The LLM can write functional code when specifically prompted, but it will default to writing imperative, procedural code.

If you start a vibe coding project ab initio, you'll get a lot of imperative, procedural code, and the LLM will have more and more difficulty reasoning about it as the project grows. To stop this from happening, I prompt the LLM to refactor the code to be more functional. I do this fairly early on in the project, once the project starts to show signs of life.

The functional refactoring is a multi-step process and the best way to do it is to prompt the LLM to first create a plan for the refactoring. I use a prompt something like this:

Make a plan. We need the code to be refactored to be more functional and to adhere to functional programming principles. Take several steps to refactor the code so that the main interaction path is functional and stateless. Move the side effects to the edges of the codebase. Use functional programming techniques such as monads and reactive programming to keep the core of the codebase functional. Make sure that utility functions are pure and stateless. Write the plan to a file FUNCTIONAL_REFACTORING.md

The LLM will cogitate for a while and will write a multi-step plan for the refactoring. Here is the plan that the LLM generated for the jrm-code-project.com web site.

# Functional Refactor Plan for `jrm-code-project`

**Author's lens:** Senior Functional Programming Architect
**Scope:** `package.lisp`, `csrf.lisp`, `server.lisp`, `auth.lisp`, `billing.lisp`,
`admin.lisp`, `chef.lisp`, `db-auth.lisp`, `stripe.lisp`, `jwt.lisp`, `totp.lisp`, `ses.lisp`
**Status:** Complete. Phases 1-8 below have all landed as separate,
individually-tested commits; the codebase now reflects this plan. The
phase write-ups are retained as historical design-rationale documentation
-- comments elsewhere in the codebase that cite "FUNCTIONAL_REFACTOR.md
Phase N" are pointing at finished work, not an in-progress migration.

---

## 0. Framing

This codebase is a working, well-organized Hunchentoot application (the recent
file split into `csrf`/`server`/`auth`/`billing`/`admin`/`chef` was a good move
along the *separation-of-concerns* axis). But every one of those modules is
written in a straight-line, **imperative-shell-with-no-functional-core** style:
HTTP handling, session mutation, SQL, third-party HTTP calls, HTML rendering,
and business rules are all fused into single `DEFUN`s that read the world,
mutate the world, and print strings, in one undifferentiated breath.

The project already imports `SERIES`, `FOLD`, `FUNCTION` (compose/inverse), and
`NAMED-LET` — real functional-programming firepower — via shadowing imports in
`package.lisp`. Almost none of it is actually used in the handler code; the
shadowed `LET`/`DEFUN`/`LET*`/`MULTIPLE-VALUE-BIND` forms are used as drop-in
replacements for their vanilla CL counterparts, not as a foundation for a
different *style* of programming. That's the central irony this plan
addresses: the tools for a functional architecture are already a dependency of
the system; they're just not driving any design decisions yet.

The plan below does **not** propose rewriting Hunchentoot, Postmodern, or
Stripe's HTTP API into something pure — those are unavoidably effectful
boundaries. It proposes pushing effects to the *edges* (a thin imperative
shell) and pulling everything else — validation, view-model construction,
tier/authorization logic, Stripe payload shaping, HTML rendering — into a
**pure, immutable, composable core** that can be unit-tested without a
database, without Hunchentoot, and without live Stripe credentials.

---

## 1. Anti-Pattern Catalog (current state)

### 1.1 Global mutable state used as an implicit parameter-passing channel

- `*acceptor*` (`server.lisp`) — mutated by `start-server`/`stop-server`.
- `*stripe-tier-price-ids*`, `*stripe-tier-product-ids*`, `*stripe-price-id-tiers*`,
  `*stripe-billing-portal-configuration-id*` (`stripe.lisp`) — four separate
  `DEFVAR`s, populated by side-effecting `PUSH` inside `ensure-tier-product`
  and `ensure-billing-portal-configuration`, and read by unrelated functions
  (`tier-price-id`, `tier-from-price-id`, `create-billing-portal-session`)
  scattered throughout the file. This is really *one* piece of "Stripe
  catalog" data, represented as four uncoordinated globals that must be
  mutated in lock-step (see `init-stripe-product`, which zeroes all four by
  hand before repopulating them) — a classic sign that a single immutable
  value is trying to escape.
- Every handler reaches into `hunchentoot:session-value`/`hunchentoot:cookie-in`
  as ambient dynamic state rather than being handed an explicit `Request`
  value. E.g. `dashboard-page` (`auth.lisp`) pulls `:authenticated-user` from
  the session, `challenge-2fa-page` reads/writes `:limbo-email` and
  `:post-login-redirect` via `setf` in the middle of a rendering branch.

### 1.2 God-functions that fuse I/O, business logic, and presentation

Nearly every `hunchentoot:define-easy-handler` in `auth.lisp`, `billing.lisp`,
and `admin.lisp` does all of the following in one function body:

1. Read ambient state (session, cookies, POST params).
2. Validate/branch on it.
3. Call the database or an external HTTP API (side effect #1).
4. Mutate session/cookie state (side effect #2).
5. Build and return an HTML string via nested `FORMAT` calls (presentation).

`dashboard-page` (`auth.lisp`) is the extreme case: ~250 lines mixing tier
math, JWT issuance (a side effect), a conditional redirect, and a giant
`FORMAT` template with 20+ interpolation arguments computed inline. There is
no way to unit-test "what should the dashboard tier grid look like for a
LAMBDA-tier user with a Stripe customer ID" without spinning up Hunchentoot,
a session, and a database row.

`stripe-webhook-handler` (`billing.lisp`) mixes signature verification,
JSON parsing, event-type dispatch, and five different DB-mutation call sites
in one `COND`, with logging `FORMAT` calls interleaved — untestable without a
live (or heavily mocked) Postgres connection and a hand-built JSON fixture.

### 1.3 Stringly-typed, un-composable HTML rendering

Every page is a hand-written `FORMAT nil "<html>...~A...</html>"` template.
Consequences:

- No composition: the "vault" card, the "tier grid", and the notification
  banner in `dashboard-page` cannot be reused or tested independently — they
  are inline slices of one giant format string.
- No enforced escaping discipline: some interpolations go through
  `hunchentoot:escape-for-html` (e.g. `(hunchentoot:escape-for-html user)`),
  others don't (e.g. tier-derived CSS class strings, which happen to be safe
  today only because they come from a fixed internal vocabulary) — the
  safety property is not structurally guaranteed, only true by convention and
  developer discipline.
- Every handler re-embeds the same `<style>` block or repeats layout
  boilerplate (`signup-page` and `setup-2fa-page` both hand-roll near-identical
  `<html><head><style>...` wrappers).

### 1.4 Alist-of-keywords as a poor man's record type

`db-auth.lisp`'s `get-user`/`list-users`/`get-user-by-customer` all return
`postmodern:query ... :alists` rows, and every caller repeats
`(cdr (assoc :membership-tier user-data))`, `(cdr (assoc :wheel user-data))`,
etc. — by grep, this exact shape appears **20+ times** across `auth.lisp`,
`billing.lisp`, and `admin.lisp`. There is no `USER` type: the "schema" is an
implicit contract enforced only by every call site independently getting the
keyword spelling right (`:stripe-subscription-id` vs. a typo would fail
silently, returning `NIL`, not a compile- or run-time error).

### 1.5 Side-effecting, non-monadic error/control flow

- `csrf.lisp`'s `WITH-CSRF-PROTECTION` macro is a control-flow combinator
  wearing a syntactic disguise: it's really "if failure, mutate the HTTP
  return code and short-circuit" — imperative branching hidden inside a
  `DEFMACRO`, not a composable value.
- `jwt.lisp`'s `require-membership-tier`/`require-wheel`/`require-membership-jwt`
  each *either* return a value *or* perform a side-effecting `REDIRECT` and
  return `NIL` — callers are contractually obligated to check for `NIL` and
  "immediately stop processing" (a convention documented in a comment,
  not enforced by the type/control-flow system). This is exactly the shape
  `Either`/`Result`/`Maybe` monadic short-circuiting exists to replace.
  Compare with e.g. `require-session-wheel` in `admin.lisp`, which duplicates
  the same "return value or redirect-and-return-nil" shape independently for
  session-based (not JWT-based) authorization — the same *pattern* implemented
  twice, un-abstracted.
- `stripe-webhook-handler` and `roast-code-with-gemini`/`chef-handler` use
  `HANDLER-CASE` around large blocks and communicate failure by mutating
  `hunchentoot:return-code*` and returning an ad hoc string — errors are
  effectively `(values nil side-effect)`, not typed outcomes.

### 1.6 Duplicated imperative HTTP-client boilerplate

`stripe.lisp` rebuilds `(stripe-auth-headers secret-key)` and re-checks
`(and secret-key (not (string= secret-key "")))` in nearly every function
(`find-existing-tier-product`, `create-tier-product`,
`ensure-billing-portal-configuration`, `create-stripe-checkout-session`,
`create-billing-portal-session`, `get-stripe-subscription-tier`,
`cancel-stripe-subscription-with-prorated-refund`) — eight independent,
hand-written guard clauses for what is structurally one precondition
("do we have Stripe configured") and one authenticated-GET/POST helper.
Request payloads are built as raw `(cons "key[bracket][path]" "value")` lists
by hand at each call site (see the billing-portal-configuration content-list
construction) rather than through a small combinator/DSL that could be unit
tested for correct shape independent of the network call.

### 1.7 Unused functional idioms already in scope

`package.lisp` imports `SERIES` (lazy, compiler-fused sequence pipelines) and
`FOLD`, yet the codebase's list processing — `list-users` pagination,
`mapcar #'render-member-row members`, `dolist` loops in `db-auth.lisp` and
`stripe.lisp`, the `LOOP ... COLLECT` in `generate-recovery-codes` — is all
plain `CL:LOOP`/`DOLIST`/`MAPCAR` with `SETF`-based accumulation
(`random-string`'s `(setf (char res i) ...)` loop, `admin-members-page`'s
imperative pagination math). None of it is wrong CL, but it means the
project's own stated architectural direction (series/fold-based composition)
isn't actually load-bearing anywhere yet.

### 1.8 Testing is coupled to live, mutable external state

`recovery-code-verification`, `stripe-database-and-routes`, and
`user-membership-tiers` (per `tests/tests.lisp` and this repo's own
documented conventions) require a live Postgres instance and mutate real
rows. This is a direct consequence of §1.2/§1.4: because business logic is
never separated from the DB/HTTP shell, there is no way to test "does
`tier-meets-minimum-p` correctly rank CADR above CONS" or "does the webhook
handler correctly map a `customer.subscription.deleted` event to a
cancellation" without a database in the loop.

---

## 2. Target Architecture

**Functional core, imperative shell**, applied consistently:

```
┌─────────────────────────────────────────────────────────────┐
│ Imperative shell (thin, at the edges only)                   │
│  - Hunchentoot handlers: parse Request, call pure core,      │
│    interpret its pure Response/Effect value, perform I/O.    │
│  - Postmodern calls: translate SQL rows <-> immutable domain │
│    records at the boundary only.                             │
│  - Stripe/Gemini HTTP calls: translate typed request records │
│    <-> typed response records at the boundary only.          │
│  - *ACCEPTOR*, *STRIPE-CATALOG*, cookie/session get/set.      │
└───────────────────────────┬───────────────────────────────────┘
                            │ immutable values only cross this line
┌───────────────────────────▼───────────────────────────────────┐
│ Pure functional core (the bulk of new/moved code)             │
│  - Domain records: USER, MEMBERSHIP-CLAIMS, STRIPE-CATALOG,   │
│    CHECKOUT-REQUEST, WEBHOOK-EVENT, VIEW-MODEL, RESULT.       │
│  - Pure decision functions: tier-meets-minimum-p,              │
│    dashboard-view-model, webhook-event->db-commands,          │
│    checkout-request->stripe-params, csrf-check, auth-check.   │
│  - Pure rendering functions: view-model -> HTML string.       │
│  - Composable middleware combinators over a Request->Result   │
│    handler shape.                                              │
└─────────────────────────────────────────────────────────────────┘
```

Key design commitments:

1. **Immutable domain records, not alists-of-keywords.** Every "row" that
   crosses the DB boundary becomes a `defstruct` (or `defclass` with
   `:read-only` when the CLOS overhead-per-instance is not a concern) with
   named, typed accessors — `user-membership-tier`, `user-wheel-p`, etc. —
   constructed once at the DB boundary via a single `row->user` converter,
   never re-derived by ad hoc `(cdr (assoc :x row))` at call sites.

2. **Explicit `Result`/`Either`-style outcomes instead of "return NIL and
   trust the caller to have already redirected."** A tiny `defstruct result`
   (or reuse of `(values status payload)`, or a proper condition-based
   approach — see Phase 6) makes success/failure a first-class value that
   the *shell* interprets (issue a redirect, render an error page), rather
   than a side effect the *core* performs mid-computation.

3. **Middleware as composable functions, not macros with inline control
   flow.** `WITH-CSRF-PROTECTION`, `require-membership-tier`,
   `require-session-wheel` all collapse into one combinator shape:
   `(defun wrap-with-csrf (handler) ...)`, `(defun wrap-with-tier (min-tier handler) ...)`,
   composed via `FUNCTION:COMPOSE` (already a dependency!) at route-definition
   time, e.g. `(compose (require-tier "CADR") require-login csrf-protected) #'chef-page-core)`.

4. **Pure view-model construction, separated from HTML string rendering,
   separated from the HTTP handler.** `dashboard-page` becomes: (a) a pure
   `dashboard-view-model` function (user record + query params -> an
   immutable `DASHBOARD-VIEW-MODEL` struct), (b) a pure `render-dashboard`
   function (view-model -> HTML string, independently unit-testable with
   hand-built view-models and no session/DB at all), and (c) a thin handler
   that wires the two together and performs the one real side effect
   (issuing the JWT cookie).

5. **One immutable `Stripe` catalog value, not four mutable globals.**
   `ensure-tier-product`/`ensure-billing-portal-configuration` become pure
   functions that *return* an updated `STRIPE-CATALOG` record; `init-stripe-product`
   becomes the one place that takes the pure result and stores it in a single
   `*stripe-catalog*` global (still a necessary impurity — Stripe's actual
   product IDs are genuinely mutable external state fetched once at startup —
   but now it's *one* clearly-labeled impurity instead of four unsynchronized
   ones).

6. **Lean on `SERIES`/`FOLD` where they fit naturally** (pagination,
   filtering, tier-ranking, recovery-code generation) so the project's own
   declared functional dependencies start pulling their weight, without
   forcing awkward `SERIES` usage onto genuinely imperative I/O loops (the
   SMTP hand-rolled protocol in `ses.lisp`, for instance, is legitimately
   sequential/stateful and is *not* a refactor target for series-ification).

---

## 3. Non-Goals

- **Not** rewriting Hunchentoot request handling, Postmodern's connection
  model, or the raw SMTP-over-TLS code in `ses.lisp` — these are genuine
  imperative shells (sockets, connections, OS processes) and should stay
  imperative, just kept as thin and as clearly bounded as possible.
- **Not** introducing a heavyweight external templating engine or ORM as a
  prerequisite — the plan below builds small in-house combinators sized to
  this codebase, consistent with its existing dependency footprint
  (`alexandria`, `fold`, `function`, `series`).
- **Not** a big-bang rewrite. Every phase below ships independently, keeps
  `(asdf:test-system :jrm-code-project)` green throughout, and preserves
  every documented behavior (CSRF exemptions, the `next` breadcrumb, JWT
  redirect-to-`/` semantics, wheel bootstrap, etc.) verbatim.

---

## 4. Incremental Migration Plan

Each phase is scoped to be its own PR/commit, independently testable, and
reversible. Phases are ordered so that later phases can build on the domain
types and combinators introduced earlier ones.

### Phase 1 — Immutable domain records at the database boundary
**Files touched:** `db-auth.lisp`, call sites in `auth.lisp`, `billing.lisp`,
`admin.lisp`.

- Introduce `defstruct (user (:copier nil))` (email, password-hash,
  totp-secret, auth-state, stripe-customer-id, stripe-subscription-id,
  subscription-status, membership-tier, wheel-p) plus a single
  `row->user` converter used by `get-user`, `get-user-by-customer`, and
  `list-users`.
- `get-user`, `list-users`, etc. keep their existing names/call signatures
  (no handler changes yet) but return `USER` structs instead of alists.
- Replace every `(cdr (assoc :membership-tier user-data))`-style call site
  with `(user-membership-tier user-data)`.
- **Payoff:** typos become compile-time `SLOT-UNBOUND`/undefined-function
  errors instead of silent `NIL`; this is the least risky phase (pure
  mechanical substitution) and unblocks everything else.
- **Tests:** existing FiveAM DB tests continue to pass unchanged (they
  already exercise these accessors indirectly); add direct unit tests for
  `row->user` using a hand-built alist fixture, no DB required.

### Phase 2 — Extract pure decision logic out of handlers
**Files touched:** new `tier.lisp` (or fold into `jwt.lisp`), `auth.lisp`,
`billing.lisp`.

- Move `tier-rank`/`tier-meets-minimum-p` (already pure!) into a dedicated,
  independently-tested module — they're the easiest possible first win.
- Extract the *decision* half of `dashboard-page` into a pure
  `dashboard-view-model` function: given a `USER`, a `checkout-status`, and a
  `next` param, return an immutable `DASHBOARD-VIEW-MODEL` struct (tier
  flags, badge/button HTML fragments *as data*, e.g.
  `(:active-p t :badge :current :button :manage-subscription)` rather than
  pre-rendered HTML — defer string rendering to Phase 5).
- Extract the *decision* half of `stripe-webhook-handler`'s event dispatch
  into a pure `webhook-event->db-commands` function: given the decoded JSON
  alist, return a list of *data* describing what should happen (e.g.
  `(:update-subscription :email ... :tier ...)`), with a thin imperative
  loop in the handler that executes each command against `jrm-auth:*`.
- **Payoff:** these pure functions get direct FiveAM unit tests with
  hand-built fixtures — no Postgres, no Hunchentoot, no live Stripe webhook
  payloads needed to verify "a `customer.subscription.deleted` event
  produces a cancel command for the right user."

### Phase 3 — Composable middleware combinators
**Files touched:** `csrf.lisp`, `jwt.lisp`, `admin.lisp`.

- Replace `WITH-CSRF-PROTECTION` (macro) with a higher-order function
  `wrap-csrf-protected` that takes a zero-argument thunk (or, once Phase 4
  handler shape lands, a `Request -> Result` handler) and returns a value
  representing either "proceed" or "403 forbidden" — usable both as today's
  macro (thin `defmacro with-csrf-protection (&body body) `(funcall
  (wrap-csrf-protected (lambda () ,@body)))`, preserving all call sites) *and*
  directly composable with `FUNCTION:COMPOSE` for new code.
- Unify `require-membership-tier`, `require-wheel`, and `admin.lisp`'s
  hand-rolled `require-session-wheel` behind one combinator shape:
  `(defun require (predicate on-failure) ...)`, parameterized by *what* to
  check (JWT tier, session wheel bit) and *what to do on failure*
  (redirect-to-login vs. redirect-to-dashboard vs. redirect-to-upgrade),
  eliminating the duplicated "return value or side-effecting-redirect-and-nil"
  pattern called out in §1.5.
- **Payoff:** one audited implementation of "check X, else redirect Y" instead
  of three ad hoc ones; new protected routes become one line of composition
  instead of copy-pasted boilerplate.

### Phase 4 — Consolidate Stripe catalog state into one immutable value
**Files touched:** `stripe.lisp`.

- Introduce `(defstruct stripe-catalog tier-price-ids tier-product-ids
  price-id-tiers billing-portal-configuration-id)`.
- Rewrite `ensure-tier-product`, `ensure-billing-portal-configuration`, and
  `init-stripe-product` as pure functions of `(catalog, ...) -> new-catalog`
  (the actual Stripe HTTP calls remain side effects, but the *bookkeeping*
  that today happens via four `PUSH`es across two functions becomes one
  `(defun catalog-with-tier (catalog tier price-id product-id) ...)`
  returning a fresh struct).
- `*stripe-tier-price-ids*` etc. collapse into a single `*stripe-catalog*`
  global, set once by `init-stripe-product`, read via small accessor
  functions (`tier-price-id`, `tier-from-price-id`) that close over it —
  same call-site API, one source of truth underneath.
- Extract the repeated `(and secret-key (not (string= secret-key "")))`
  guard and `stripe-auth-headers` construction into a single
  `with-stripe-credentials (headers) ...` macro/combinator so the eight
  duplicated guard clauses in §1.6 collapse to one.
- **Payoff:** `init-stripe-product`'s "zero all four, then repopulate" dance
  disappears; the catalog can never be observed half-updated.

### Phase 5 — Pure, composable HTML rendering
**Files touched:** new `views.lisp`, `auth.lisp`, `billing.lisp`, `admin.lisp`.

- Introduce small rendering combinators: `(html-page title body-html)`,
  `(html-form action fields &key csrf-token)`, `(html-notification kind text)`
  — pure string -> string functions, each independently testable.
- Rewrite the Phase-2 `DASHBOARD-VIEW-MODEL` -> HTML as a pure
  `render-dashboard` function built from the above combinators; the
  `dashboard-page` handler shrinks to "build view-model, issue JWT cookie,
  call `render-dashboard`."
- Apply the same pattern to `admin-members-page`/`render-member-row` (already
  half-decomposed — `render-member-row` is already a pure function of a
  `USER`; formalize it as `(user -> html)` operating on the Phase-1 struct)
  and to the repeated signup/2FA/login page chrome.
- Standardize escaping: every interpolated *user-controlled* value flows
  through one `(html-escape value)` combinator used *inside* the rendering
  combinators themselves, so escaping is structurally guaranteed rather than
  convention-dependent (closes the gap in §1.3).
- **Payoff:** view logic becomes unit-testable ("does a LAMBDA-tier user
  with no Stripe customer ID render a disabled CONS button and an active
  LAMBDA badge?") without any I/O; duplicated page chrome collapses to one
  `html-page` call per handler.

### Phase 6 — Explicit outcome values for error handling
**Files touched:** `billing.lisp` (webhook + checkout), `chef.lisp` (Gemini
call), `stripe.lisp`.

- Introduce a minimal `(defstruct (result (:constructor ok (value)))
  value)` / `(defstruct (failure (:constructor err (reason))) reason)` pair
  (or a tagged `(cons :ok value)` / `(cons :error reason)` if a full struct
  is overkill) used by `roast-code-with-gemini`, `create-stripe-checkout-session`,
  and the webhook command interpreter from Phase 2.
- Handlers interpret the `RESULT`/`FAILURE` value at the shell boundary
  (mutate `return-code*`, pick the right error string) — the pure/impure
  split becomes: *pure code computes an outcome value; only the handler
  performs the HTTP-visible side effect of reporting it.*
- **Payoff:** `stripe-webhook-handler`'s `HANDLER-CASE`-wrapped cascade of
  five DB mutations becomes: compute a list of typed commands (Phase 2),
  execute them, collect any resulting `FAILURE`s, report once — testable end
  to end by mocking the command-execution step.

### Phase 7 — Lean on `SERIES`/`FOLD` for sequence-shaped logic
**Files touched:** `db-auth.lisp`, `admin.lisp`, `stripe.lisp`.

- `admin-members-page`'s pagination math (`offset`, `total-pages`,
  `has-prev`/`has-next`) and `random-string`'s character-by-character
  `SETF` loop are natural, low-risk candidates for `SERIES`-based rewrites
  once the surrounding data is already immutable (Phases 1 and 5).
- `generate-recovery-codes`'s `LOOP REPEAT 10 COLLECT ...` and the
  `dolist`-based Stripe tier-plan initialization in `init-stripe-product`
  are good `FOLD`/`SERIES` candidates once Phase 4 makes the underlying
  state immutable.
- Treat this phase as *opportunistic polish*, not a hard requirement — the
  goal is internal consistency with the project's declared dependencies, not
  a mandate to force every loop into `SERIES` syntax.

### Phase 8 — Test suite rebalancing
**Files touched:** `tests/tests.lisp`.

- Once Phases 1–6 land, add a large batch of **pure unit tests** requiring no
  Postgres/Stripe/Hunchentoot: `row->user`, `tier-meets-minimum-p`,
  `dashboard-view-model`, `webhook-event->db-commands`, `render-dashboard`,
  `catalog-with-tier`, the CSRF/tier middleware combinators.
- Keep the existing live-Postgres tests (`recovery-code-verification`,
  `stripe-database-and-routes`, `user-membership-tiers`) as the *thin*
  integration-test layer that only needs to verify the imperative shell
  correctly wires pure functions to real I/O — their scope should shrink
  over time as more logic moves into directly-tested pure functions.
- **Payoff:** CI/local runs that don't have Postgres available can still
  exercise the majority of the codebase's actual logic; the live-DB tests
  become a smaller, more focused confirmation layer instead of the primary
  way anything gets tested.

---

## 5. Sequencing & Risk Notes

- Phases are ordered by **increasing dependency on prior phases**, not by
  file. Do not skip Phase 1 — every later phase assumes `USER` (and later
  `STRIPE-CATALOG`) structs exist, so alist-accessor call sites should be
  fully migrated before Phase 2 work begins on the same files.
- Each phase should land as its own commit/PR with `(asdf:test-system
  :jrm-code-project)` green before and after — this plan is explicitly
  incremental so the app is deployable after every single phase.
- No phase changes an HTTP-visible behavior (routes, redirects, cookie
  names/lifetimes, CSRF exemption list, the `next` breadcrumb contract, or
  JWT-missing-redirects-to-`/` semantics) — those are refactors of
  *implementation*, not of *behavior*. Any phase whose diff would change
  observable behavior should be split so the behavior change is its own,
  separately-reviewed commit.
- `ses.lisp`'s hand-rolled SMTP client is explicitly out of scope (§3) —
  it's a sequential protocol state machine talking to a raw socket, not a
  data-transformation pipeline, and forcing it into this plan's shape would
  fight the grain of what it actually is.

---

## 6. Definition of Done

The refactor is "complete" (per phase, and overall) when:

1. No handler function directly calls Postmodern, Stripe's HTTP API, or
   builds a final HTML response string in the same function body that also
   makes the authorization/business decision — each of those three concerns
   is a separately named, separately testable function.
2. No `(cdr (assoc :keyword row))` pattern remains outside the Phase-1
   `row->*` converter functions.
3. Every cross-cutting concern (CSRF, session auth, JWT tier-gating,
   wheel-gating) is expressed as a composable function over a handler, with
   exactly one implementation per concern (no duplicated
   `require-session-wheel`-style reimplementations).
4. Stripe's in-memory catalog is one immutable value with one owning
   global, not four independently-mutated globals.
5. A newly-added contributor can run the pure-function unit tests (Phase 8)
   with zero external services configured and still exercise the majority of
   the application's actual decision logic.

As you can see, this is a very detailed and serious plan. Come to think about it, I should have done the functional refactor sooner so that it would not have needed such an extensive plan.

Once the plan is written, I prompt the LLM to implement each phase of the plan in turn. The prompt is straightforward: Read FUNCTIONAL_REFACTORING.md and implement the next phase of the Incremental Migration plan. I use this prompt over and over until all the phases have been implemented. I monitor the progress of the LLM to make sure it is not getting lost in the weeds.

Functional refactoring is expensive. It chews through a ton of tokens, and it may seem like a waste because if it is done correctly, the code will behave exactly the same as it did before the refactoring. I have done a functional refactoring on most of my vibe coding projects and I have been pleased with the results. The generated code is surprisingly good, and subsequent `vibing` seems to be quite easy for the LLM.

Once the functional refactoring is complete, the LLM will tend to write future code in a more functional style. It is a pattern matcher, so if it sees functional patterns, it will tend to mimic them. But imperative code will creep back in over time because the LLM is so heavily trained on imperative code. I have found that occasionally prompting the LLM to refactor the code to be more functional is useful. Subsequent functional refactorings are much easier than the first functional refactoring because the core code is already functional and large refactorings are not needed.

If you are not a functional programmer, I expect that you will find this to be a massive waste of time with a lot of code churn. But if you are a functional programmer, I bet you'll be pleased with the results - I have been.


Monday, February 16, 2026

binary-compose-left and binary-compose-right

If you have a unary function F, you can compose it with function G, H = F ∘ G, which means H(x) = F(G(x)). Instead of running x through F directly, you run it through G first and then run the output of G through F.

If F is a binary function, then you either compose it with a unary function G on the left input: H = F ∘left G, which means H(x, y) = F(G(x), y) or you compose it with a unary function G on the right input: H = F ∘right G, which means H(x, y) = F(x, G(y)).

(binary-compose-left f g)  = (λ (x y) (f (g x) y))
(binary-compose-right f g) = (λ (x y) (f x (g y)))

We could extend this to trinary functions and beyond, but it is less common to want to compose functions with more than two inputs.

binary-compose-right comes in handy when combined with fold-left. This identity holds

 (fold-left (binary-compose-right f g) acc lst) <=>
   (fold-left f acc (map g lst))

but the right-hand side is less efficient because it requires an extra pass through the list to map g over it before folding. The left-hand side is more efficient because it composes g with f on the fly as it folds, so it only requires one pass through the list.


Sunday, February 1, 2026

Some Libraries

Zach Beane has released the latest Quicklisp beta (January 2026), and I am pleased to have contributed to this release. Here are the highlights:

  • dual-numbers — Implements dual numbers and automatic differentiation using dual numbers for Common Lisp.
  • fold — FOLD-LEFT and FOLD-RIGHT functions.
  • function — Provides higher-order functions for composition, currying, partial application, and other functional operations.
  • generic-arithmetic — Defines replacement generic arithmetic functions with CLOS generic functions making it easier to extend the Common Lisp numeric tower to user defined numeric types.
  • named-let — Overloads the LET macro to provide named let functionality similar to that found in Scheme.

Selected Functions

Dual numbers

DERIVATIVE function → function

Returns a new unary function that computes the exact derivative of the given function at any point x.

The returned function utilizes Dual Number arithmetic to perform automatic differentiation. It evaluates f(x + ε), where ε is the dual unit (an infinitesimal such that ε2 = 0). The result is extracted from the infinitesimal part of the computation.

f(x + ε) = f(x) + f'(x)ε

This method avoids the precision errors of numerical approximation (finite difference) and the complexity of symbolic differentiation. It works for any function composed of standard arithmetic operations and elementary functions supported by the dual-numbers library (e.g., sin, exp, log).

Example

(defun square (x) (* x x))

(let ((df (derivative #'square)))
  (funcall df 5)) 
;; => 10
    

Implementation Note

The implementation relies on the generic-arithmetic system to ensure that mathematical operations within function can accept and return dual-number instances seamlessly.

Function

BINARY-COMPOSE-LEFT binary-fn unary-fn → function
BINARY-COMPOSE-RIGHT binary-fn unary-fn → function

Composes a binary function B(x, y) with a unary function U(z) applied to one of its arguments.

(binary-compose-left B U)(x, y) ≡ B(U(x), y)
(binary-compose-right B U)(x, y) ≡ B(x, U(y))

These combinators are essential for "lifting" unary operations into binary contexts, such as when folding a sequence where elements need preprocessing before aggregation.

Example

;; Summing the squares of a list
(fold-left (binary-compose-right #'+ #'square) 0 '(1 2 3))
;; => 14  ; (+ (+ (+ 0 (sq 1)) (sq 2)) (sq 3))
    

FOLD

FOLD-LEFT function initial-value sequence → result

Iterates over sequence, calling function with the current accumulator and the next element. The accumulator is initialized to initial-value.

This is a left-associative reduction. The function is applied as:

(f ... (f (f initial-value x0) x1) ... xn)

Unlike CL:REDUCE, the argument order for function is strictly defined: the first argument is always the accumulator, and the second argument is always the element from the sequence. This explicit ordering eliminates ambiguity and aligns with the functional programming convention found in Scheme and ML.

Arguments

  • function: A binary function taking (accumulator, element).
  • initial-value: The starting value of the accumulator.
  • sequence: A list or vector to traverse.

Example

(fold-left (lambda (acc x) (cons x acc))
           nil
           '(1 2 3))
;; => (3 2 1)  ; Effectively reverses the list
    

Named Let

LET bindings &body body → result
LET name bindings &body body → result

Provides the functionality of the "Named Let" construct, commonly found in Scheme. This allows for the definition of recursive loops within a local scope without the verbosity of LABELS.

The macro binds the variables defined in bindings as in a standard let, but also binds name to a local function that can be called recursively with new values for those variables.

(let name ((var val) ...) ... (name new-val ...) ...)

This effectively turns recursion into a concise, iterative structure. It is the idiomatic functional alternative to imperative loop constructs.

While commonly used for tail recursive loops, the function bound by named let is a first-class procedure that can be called anywhere or used as a value.

Example

;; Standard Countdown Loop
(let recur ((n 10))
  (if (zerop n)
      'blastoff
      (progn
        (print n)
        (recur (1- n)))))
    

Implementation Note

The named-let library overloads the standard CL:LET macro to support this syntax directly if the first argument is a symbol. This allows users to use let uniformly for both simple bindings and recursive loops.


Tuesday, January 20, 2026

Filter

One of the core ideas in functional programming is to filter a set of items by some criterion. It may be somewhat suprising to learn that lisp does not have a built-in function named “filter” “select”, or “keep” that performs this operation. Instead, Common Lisp provides the “remove”, “remove-if”, and “remove-if-not” functions, which perform the complementary operation of removing items that satisfy or do not satisfy a given predicate.

The remove function, like similar sequence functions, takes an optional keyword :test-not argument that can be used to specify a test that must fail for an item to be considered for removal. Thus if you invert your logic for inclusion, you can use the remove function as a “filter” by specifying the predicate with :test-not.

> (defvar *nums* (map 'list (λ (n) (format nil "~r" n)) (iota 10)))
*NUMS*

;; Keep *nums* with four letters
> (remove 4 *nums* :key #'length :test-not #'=)
("zero" "four" "five" "nine")

;; Keep *nums* starting with the letter "t"
> (remove #\t *nums* :key (partial-apply-right #'elt 0) :test-not #'eql)
("two" "three")

Saturday, July 19, 2025

GitHub updates 19/Jul/2025

https://github.com/jrm-code-project/dual-numbers

This library implements dual numbers for automatic differentiation.


https://github.com/jrm-code-project/function

This library implements higher-order functions, composing, currying, partial-application, etc.


https://github.com/jrm-code-project/generic-arithetic

This library redefines the standard Common Lisp arithemetic with generic functions so that math operations can be extended with defmethod.


https://github.com/jrm-code-project/named-let

This library implements some Scheme-inspired macros.

  • define — a Lisp-1 define that binds in both the function and value namespaces
  • flambda — a variant of lambda that binds its arguments in the function namespace
  • overloaded let — a redefinition of the let macro that enables a named-let variant
  • letrec and letrec* — binds names with values in the scope of the names so that recursive function definitions are possible

Friday, December 27, 2024

Composing Binary Functions

Functions that take one argument and return one value are cool because you can make pipelines out of them. You just send the output of one function into the input of the next. Of course the output of the first function must be of a type that the second function can accept. Or you can just stick with functions that take and return the same type, and then you can compose these as desired.

But what if you want to compose binary functions that take two arguments and return two values? There are a couple of ways to take multiple arguments: you can pass them in a list (or vector), or you can pass the arguments one at a time by curry the function.

(defun curry (B)
  (lambda (l)
    (lambda (r)
      (funcall B l r))))

There are two lambdas here. The outer lambda accepts the left argument and returns the inner lambda. The inner lambda accepts the right argument and calls the original binary function with both arguments.

To call a curried function, you first call it with the left argument. This will return a lambda that you call with the right argument.

(funcall (funcall curried-binary-function left) right)

The two-argument identity function would be curried like this:

(defun curried-values (left)
  (lambda (right)
    (values left right)))

Composing two curried functions is a little complicated. Let us suppose that F and G are curried binary functions. Further assume that G has already been applied to its left argument, i.e., it is an inner lambda of a curried binary function. We want to compute the inner lambda of F composed with G.

(defun curried-compose (f g)
  (lambda (right)  ; return an inner lambda
    (multiple-value-bind (vall valr) (funcall g right)
      (funcall (funcall f vall) valr))))

Here is how it works. We return an inner lambda that accepts the right argument of the composition. We call the inner lambda G on this argument and collect the two values it returns. We then pass the two values one at a time to F.

If we did this right, we should end up with these identities:

(curried-compose #’F (curried-values left))
    ==> (F left)

and

(curried-compose #’curried-values G-inner)
    ==> G-inner

furthermore, curried-compose should be associative:

(curried-compose (curried-compose F G) H)
    ==> (curried-compose F (curried-compose G H))

Let’s try it out.

(defun curried-cons (left)
  (lambda (right)
    (cons left right)))

;; Check first identity.
(let ((x (curried-compose #’curried-cons (curried-values ’car))))
  (assert (equal (funcall x ’cdr) ’(car . cdr))))

;; Check second identity.
(let ((x (curried-compose #’curried-values (curried-cons ’car))))
  (assert (equal (funcall x ’cdr) ’(car . cdr))))

;; Check associativity.
(defun curried-sum-difference (left)
  (lambda (right)
    (values (+ left right) (- left right))))

(let ((x (curried-compose
           #’curried-cons
           (curried-compose
             #’curried-sum-difference
             (curried-values 7))))
      (y (curried-compose
           (lambda (v)
             (curried-compose #’curried-cons
               (curried-sum-difference v)))
            (curried-values 7))))
  (assert (equal (funcall x 3) (funcall y 3))))

If the binary function is closed over its right argument, then when you curry it, the inner lambda will be closed over its argument. We should be able to compose various inner lambdas to make a pipeline. The pipeline will daisy chain the right argument from one curried function in the pipeline to the next.

Pipelines like this have two properties we want to exploit: first, they force an order of execution on the functions in the pipeline. The earlier stages in the pipeline have to produce an answer before the later stages consume it, even if all the functions in the pipeline are lazy pure functional. Second, we can abstract out the argument we are daisy chaining through the stages.

Let’s use this in a real problem. Our task is to build a binary tree where each node has a serial number. The serial number will be our right hand argument which is daisy chained through the computation.

(defun next-sn (sn)
   (values sn (1+ sn)))

(defun curried-make-node (depth children)
  (curried-compose
    (lambda (sn)
      (curried-values (cons (cons depth sn) children)))
    #’next-sn))

(defun curried-make-tree (depth)
  (if (zerop depth)
      (curried-make-node depth nil)
      (curried-compose
        (lambda (left-branch)
          (curried-compose
            (lambda (right-branch)
              (curried-make-node depth (list left-branch right-branch)))
            (curried-make-tree (1- depth))))
        (curried-make-tree (1- depth)))))

curried-make-tree returns a curried function. It hasn’t built a tree, but built a function that builds the tree once it gets the serial number passed in.

Notice these two things: we have no global state or assignment, but we get a serial number that is incremented for each node. The serial number is passed around as the curried right hand argument and returned as the right hand value. Notice, too, that curried-make-tree has no mention of the serial number. It is a hidden variable.

curried-compose is reminiscent of a let expression, so we can create some analagous syntactic sugar:

(defmacro LetM (((var val) &rest more) &body body)
  ‘(curried-compose
     (lambda (,var)
       ,@(if more
            ‘((LetM ,more ,@body))
            body))
     ,val))

(defun curried-make-tree (depth)
  (if (zerop depth)
      (curried-make-node depth nil)
      (LetM ((left-branch (curried-make-tree (1- depth)))
             (right-branch (curried-make-tree (1- depth))))
        (curried-make-node depth (list left-branch right-branch)))))

There is a special name for the inner lambda that is expecting the right hand argument. It is a “monad”. curried-values is the monad “unit”, and curried-compose is the monad “bind”.

As I mentioned in a previous post, it makes more sense to use this approach in a lazy functional language. The chain of curried functions force sequential evaluation because the output of each curried function must be computed before it becomes the input of the next curried function. The right hand argument that is threaded through the curried calls can be used as a “store” that is (functionally) updated by each curried function before passing it along, giving you the illusion of mutable storage.

A monad is how you embed an imperative language within a pure, lazy, functional language. But in a mixed language like Lisp, you can force sequential evaluation by progn and the store is actually mutable, so there is less of a need for monads. Nonetheless, they provide a way to “hide” a variable that is threaded through the curried functions and that can come in handy. For example, if you are doing I/O, you can hide the stream variable so you don’t have to pass it along to every intermediate function.


Saturday, November 2, 2024

Don't Try to Program in Lisp

A comment on my previous post said,

The most difficult thing when coming to a different language is to leave the other language behind. The kind of friction experienced here is common when transliterating ideas from one language to another. Go (in this case) is telling you it just doesn’t like to work like this.
Try writing simple Go, instead of reaching for Lisp idioms. Then find the ways that work for Go to express the concepts you find.

That's not at all how I approach programming.

A friend of mine once paid me a high compliment. He said, “Even your C code looks like Lisp.”

When I write code, I don't think in terms of the language I'm using, I think in terms of the problem I'm solving. I'm a mostly functional programmer, so I like to think in terms of functions and abstractions. I mostly reason about my code informally, but I draw upon the formal framework of Lambda Calculus. Lambda Calculus is a simple, but powerful (and universal) model of computation.

Programming therefore becomes a matter of expressing the solution to a problem with the syntax and idioms of the language I'm using. Lisp was inspired by Lambda Calculus, so there is little friction in expressing computations in Lisp. Lisp is extensible and customizable, so I can add new syntax and idioms as desired.

Other languages are less accommodating. Some computations are not easily expressable in the syntax of the language, or the semantics of the language are quirky and inconsistent. Essentially, every general purpose fourth generation programming language can be viewed as a poorly-specified, half-assed, incomplete, bug-ridden implementation of half of Common Lisp. The friction comes from working around the limitations of the language.


Saturday, July 8, 2023

Playing with AI

Write a polemic about how omitting conditional expressions from a language is lazy and stupid.

Conditional expressions are a fundamental feature of any programming language that claims to be expressive, concise and elegant. They allow programmers to write complex logic in a single line, without the need for verbose and repetitive if-else statements. They also enable functional programming paradigms, such as pattern matching and recursion, that are essential for solving many problems efficiently and elegantly.
Omitting conditional expressions from a language is a sign of laziness and stupidity on the part of the language designers. It shows that they do not care about the needs and preferences of their users, who have to write more code, introduce more bugs, and suffer more frustration. It also shows that they do not understand the principles and benefits of functional programming, which have been proven by decades of research and practice. They are stuck in an imperative mindset, where everything has to be done with side effects and mutations.
A language without conditional expressions is a crippled language, that forces programmers to use hacks and workarounds to achieve what should be simple and natural. It is a language that discourages creativity, elegance and readability. It is a language that should be avoided by anyone who values their time, sanity and reputation.
Some examples of programming languages that don’t have conditional expressions are:
  • CoffeeScript
  • Go
  • MATLAB
  • Pascal
  • Rust

This isn't bad, but I wanted more vitriol. I asked and I got a screed that could have come out of comp.lang.functional Unfortunately, it thought better of it and erased its own output before I could snapshot it.


Tuesday, May 30, 2023

Raymarching in Lisp

It turns out there’s a nice functional variation of raytracing called raymarching. The algorithms involved are simple and elegant. The learning curve is shallow and you can generate great looking images without hairy trig or linear algebra.

We’ll follow the example of Georges Seurat and simply compute the color independently for each of myriads of pixels. This is efficiently done in parallel in real time on a GPU, but then you have to use shader language and I want to use Lisp. It is insanely inefficient to do this serially on the CPU in Lisp, but still fast enough to render an image in a couple of seconds.

Imagine you have some scene you want to render. There is a volume of 3-dimensional space the scene occupies. Now imagine we know for every point in 3-dimensional space how far away that point is from the nearest surface. This is a scalar value that can be assigned to any point. It is zero for every point that lies on a surface, positive for points above surfaces, and negative for points below. This is the SDF (Signed Distance Field). The SDF is all we need to know to generate a raytraced image of the scene.

We’ll use the SDF to feel our way through the scene. We’ll start at the tip of the ray we’re tracing. We don’t know where the surface is, but if we consult the SDF, we can determine a distance we can safely extend the ray without hitting any surface. From this new point, we can recur, again stepping along no further than the SDF at this new location permits. One of two things will happen: we either step forever or we converge on a surface.

(defun raymarch (sdf origin direction)
  (let iter ((distance 0)
             (count 0))
    (let* ((position (+ origin (* direction distance)))
           (free-path (funcall sdf position)))
      (if (< free-path +min-distance+)
          position  ;; a hit, a very palpable hit
          (unless (or (> count +max-raymarch-iterations+)
                      (> free-path +max-distance+))
            (iter (+ distance free-path) (+ count 1)))))))

To convert an SDF to a Seurat function, we trace an imaginary ray from our eye, through the screen, and into the scene. The ray origin is at your eye, and we’ll say that is about 3 units in front of the window. The ray will travel 3 units to the screen and hit the window at point (i,j), so the ray direction is (normalize (vector i j 3)). We march along the ray to find if we hit a surface. If we did, we compute the amount of light the camera sees using the Lambert shading model.

(defun sdf->seurat (sdf)
  (let ((eye-position (vector 0 0 -4))
        (light-direction (normalize (vector 20 40 -30))))
    (lambda (i j)
      (let* ((ray-direction (normalize (vector i j 3)))
             (hit (raymarch sdf eye-position ray-direction)))
        (if hit
            (* #(0 1 0) (lambert sdf hit light-direction))
            (vector 0 0 0))))))

Lambert shading is proportional to the angle between the surface and the light falling on it, so we take the dot product of the light direction with the normal to the surface at the point the light hits it. If we know the SDF, we can approximate the normal vector at a point by probing the SDF nearby the point and seeing how it changes.

(defun lambert (sdf hit light-direction)
  (dot (pseudonormal sdf hit) light-direction))

(defun pseudonormal (sdf position)
  (let ((o (funcall sdf position))
        (dsdx (funcall sdf (+ #(0.001 0 0) position)))
        (dsdy (funcall sdf (+ #(0 0.001 0) position)))
        (dsdz (funcall sdf (+ #(0 0 0.001) position))))
      (normalize (vector (- dsdx o) (- dsdy o) (- dsdz o)))))

These are all you need to generate good looking 3-d images from a SDF. Now the SDFs for primitive geometric shapes are pretty simple. Here is the SDF for a sphere.

(defun sdf-sphere (position radius)
  (lambda (vector)
    (- (length (- vector position)) radius)))

and the SDF for the ground plane

(defun sdf-ground (h)
  (lambda (vector)
    (+ (svref vector 1) h)))

Given the SDF for two objects, you can use higher order functions to compose them into a scene. Taking the minimum of two SDFs will give you the union of the shapes. Taking the maximum will give you the intersection of two shapes. Other higher order functions on SDFs can blend two SDFs. This has the effect of morphing the shapes together in the image.

I like this approach to raytracing because the arthimetic is straightforward and obvious. You only need the simplest of vector arithmetic, and you don’t need linear algebra or matrix math to get started (although you’ll want project matrixes later on when you want to move your camera around). I’m more comfortable with recursive functions than 3x3 matrices.

This approach to raytracing is best done on a graphics card. These algorithms are pretty straightforward to code up in shader language, but shader language is fairly primitive and doesn’t have higher order functions or closures. Code written in shader language has to be converted to not use closures and HOFs.


Wednesday, September 28, 2022

Observationally Functional

A couple of years back I wrote a Java microservice that talks to Jenkins to find the state of a series of builds. The code was structured to be “observationally functional” — there were plenty of side effects, but the main data abstractions behaved as if they were immutable as far as the abstract API was concerned. This allows us to treat code that uses these objects as if it were pure functional code.

If a data structure is observationally functional, then regardless of what the implementation does, there is no way to observe side effects at the abstract level. Primarily, this means that if you call a function twice with the same arguments, you always get the same answer. (This implies, but it isn't obvious, that calling a function should not mutate anything that would cause a different function to change.) This restriction has a lot of wiggle room. You can certainly side effect anything local to the abstraction that doesn't get returned to the caller. You can side effect data until the point it is returned to the caller.

The main data abstraction my microservice works with is a representation of the build metadata tree on the Jenkins server. The higher level code walks this tree looking for builds and metadata. The code maintains the illusion that the tree is a local data structure, but the implementation of the tree contains URL references to data that is stored on the Jenkins server. As the higher level code walks the tree, the lower level code fetches the data from the Jenkins server on demand and caches it.

Writing the code this way allows me to separate the data transfer and marshaling parts from the data traversal and analysis part. The tree, though it is mutated as it is traversed, is immutable in the parts that have already been visited. The caching code, which actually mutates the tree, needs to be synchronized across multiple threads, but the traversal code does not. Nodes in the tree that have already been visited are never mutated, so no synchronization is needed.

Once the caching tree abstraction was written, the higher level code simply walks the tree, selecting and filtering nodes, then reading the field values in the nodes. But the higher level code can be treated as if it were pure functional because there are no observable side effects. An advantage of pure functional code is that it is trivially thread safe, so my microservice can run hundreds of threads in parallel, each walking separate parts of the Jenkins tree and none interfering with the other. The only part of the code that uses synchronization is the tree caching code.

This implementation approach was quite fruitful. Once the code was tested with a single thread, it was obvious that multiple threads ought to work (because they couldn't observe each other's side effects) and when I turned the thread count up, no debugging was necessary. The code has been running continuously with dozens of threads for the past couple of years with no timing, synchronization, or race condition bugs.


Wednesday, September 7, 2022

Playing with raycasting

I wanted to learn about raycasting. Raycasting is like a simplified version of ray tracing. As in ray tracing, you examine the environment by projecting a ray from your current location out in some direction to determine what is visible in that direction. But we simplify the problem by only considering two dimensions.

I was also interested in making the graphics more functional and less dependent upon side effects. Now obviously rendering an image to the screen is going to involve side effects, but we can refactor the rendering problem into two subproblems, a pure function that maps the world to an image and the procedure that displays the image.

I'll put the code below. The run procedure implements the event loop state machine. It keeps track of the world and calls next-world on the current world to update the world as time passes. next-world just maps next-state over the objects in the world. next-state does not mutate an object, rather it returns a new object in the new state. Every 13 milliseconds, run calls render-world!, which calls render! on each object in the world.

We're going to use raycasting to fake up a first-person view of a two-dimensional maze. From a position within the maze, we'll cast a ray in a direction and see how far away the wall is. If we peer at the wall through a narrow slit in just that direction, it will appear as a vertical line with height inversely proportional to its distance. If we sweep the ray direction and stack the vertical lines next to each other, it will create three dimensional effect.

The render! method for a fp-view will side effect the screen, but we'll compute the contents functionally. We'll go through each column on the screen and call (vraster fp-view column) to compute a color and a height and we'll draw a vertical line of that height in that color in that column.

(defmethod render! (renderer (fp-view fp-view))
  (dotimes (column +window-width+)
    (multiple-value-bind (r g b height)
        (vraster fp-view column)
      (sdl2:set-render-draw-color renderer r g b #xFF)
      (sdl2:render-draw-line renderer
                             column (round (+ (/ +window-height+ 2) (/ height 2)))
                             column (round (- (/ +window-height+ 2) (/ height 2)))))))

vraster is a function that returns the color and height of the wall on a particular column on the screen. It figures out the angle at which to cast to a ray and calls range to find the distance to the nearest wall at that angle. This is sufficient to determine the wall height for that column, but the first person effect is enhanced significantly if you tint the color according to the distance and the direction of the wall. Knowing the distance, we compute the exact point px, py that the ray hit. It's a wall in the x direction if the y coordinate is an integer and vice versa.

(defparameter +field-of-view+ (/ pi 4))

(defun column->theta (column)
  (- (* (/ column +window-width+) +field-of-view+) (/ +field-of-view+ 2)))

(defun vraster (fp-view column)
  (let* ((location (get-location fp-view))
         (theta (column->theta column))
         (distance (range location theta))
         (px (+ (get-x location) (* (sin (+ (get-theta location) theta)) distance)))
         (py (+ (get-y location) (* (cos (+ (get-theta location) theta)) distance)))
         (wx (< (abs (- py (round py))) 0.05))
         (wy (< (abs (- px (round px))) 0.05)))
    (values
     (min #xFF (floor (/ (if wx #xff #x00) distance)))
     (min #xFF (floor (/ #xFF distance)))
     (min #xFF (floor (/ (if wy #xff #x00) distance)))
     (min +window-height+ (/ (* +window-height+ 2) distance)))))

So we've factored the rendering of a frame into a procedure that draws on the screen and a function that returns what to draw. The direct advantage of this is that we can determine what we should draw without actually drawing it. As an example, suppose we wanted to generate a stereo pair of images. The only thing we need to change is the render! method. It will now compute the view from two slightly different locations and put one set of columns on the left and the other on the right.

(defmethod render! (renderer (fp-view fp-view))
  (dotimes (column (/ +window-width+ 2))
    (multiple-value-bind (r g b height)
        (vraster (left-eye (get-location fp-view)) (* column 2))
      (sdl2:set-render-draw-color renderer r g b #xFF)
      (sdl2:render-draw-line renderer
                             column (round (+ (/ +window-height+ 2) (/ height 2)))
                             column (round (- (/ +window-height+ 2) (/ height 2)))))
    (multiple-value-bind (r g b height)
        (vraster (right-eye (get-location fp-view)) (* column 2))
      (sdl2:set-render-draw-color renderer r g b #xFF)
      (sdl2:render-draw-line renderer
                             (+ column (/ +window-width+ 2)) (round (+ (/ +window-height+ 2) (/ height 2)))
                             (+ column (/ +window-width+ 2)) (round (- (/ +window-height+ 2) (/ height 2)))))))

In this and in a previous post I've gone through the effort of writing some graphics code while avoiding unnecessary side effects. Typical graphics examples and tutorials are stuffed to the brim with global variables, state, and side effects. I wanted to see which side effects were intrinsic to graphics and which are simply incidental to how the examples are coded. It appears that large amounts of the global state and side effects are unnecessary and a more functional approach is reasonable.

As promised, here is the code.

;;; -*- Lisp -*-

(defpackage "RAYCAST"
  (:shadowing-import-from "NAMED-LET" "LET")
  (:use "COMMON-LISP" "NAMED-LET""))

(in-package "RAYCAST")

(defparameter +window-height+ 480)
(defparameter +window-width+ 640)

(defgeneric next-state (object dt)
  (:method ((object t) dt) object))
(defgeneric render! (renderer thing))

(defun next-world (previous-world dt)
  (map 'list (lambda (object) (next-state object dt)) previous-world))

(defun render-world! (renderer world)
  (sdl2:set-render-draw-color renderer #x00 #x00 #x00 #xFF)
  (sdl2:render-clear renderer)
  (mapc (lambda (object) (render! renderer object)) world)
  (sdl2:render-present renderer))

(defun run (initial-world)
  (sdl2:with-init (:video)
    (sdl2:with-window (window
                       :h +window-height+
                       :w +window-width+
                       :flags '(:shown))
      (sdl2:with-renderer (renderer window :index -1 :flags '(:accelerated :presentvsync))

        (let ((last-ticks 0)
              (render-ticker 0)
              (title-ticker 0)
              (sim-count 0)
              (frame-count 0)
              (world initial-world))

          (flet ((title-tick! (dticks)
                   (incf title-ticker dticks)
                   (when (>= title-ticker 1000)
                     (decf title-ticker 1000)
                     (sdl2:set-window-title window
                                            (format nil "Sim rate: ~d, Frame rate: ~d"
                                                    sim-count frame-count))
                     (setq sim-count 0)
                     (setq frame-count 0)))

                 (world-tick! (dticks)
                   (incf sim-count)
                   (setq world (next-world world (/ dticks 1000))))

                 (render-tick! (dticks)
                   (incf render-ticker dticks)
                   (when (>= render-ticker 13)
                     (incf frame-count)
                     (decf render-ticker 13)
                     (render-world! renderer world))))

            (sdl2:with-event-loop (:method :poll)

              (:idle ()
                     (let ((this-ticks (sdl2:get-ticks)))
                       (if (= this-ticks last-ticks)
                           (sdl2:delay 1)
                           (let ((dticks (- this-ticks last-ticks)))
                             (setq last-ticks this-ticks)
                             (title-tick! dticks)
                             (world-tick! dticks)
                             (render-tick! dticks)))))

              (:keydown (:keysym keysym)
                        (case (sdl2:scancode keysym)
                          ((:scancode-x :scancode-escape) (sdl2:push-quit-event))
                          ((:scancode-left :scancode-right
                            :scancode-up :scancode-down
                            :scancode-pageup :scancode-pagedown)
                           nil)
                          (t (format *trace-output* "~&Keydown: ~s" (sdl2:scancode keysym))
                           (force-output *trace-output*))))

              (:quit () t)
              )))))))

(defparameter +maze+
  #2a((1 1 1 1 1 1 1 1 1 1 1 1)
      (1 0 0 1 0 0 0 0 0 0 0 1)
      (1 0 0 1 0 0 0 0 0 0 0 1)
      (1 0 1 1 0 0 0 1 0 1 0 1)
      (1 0 0 0 0 0 0 0 0 0 0 1)
      (1 0 0 0 0 0 0 1 0 1 0 1)
      (1 0 0 0 0 0 0 0 0 0 0 1)
      (1 0 0 0 0 0 0 0 0 0 0 1)
      (1 0 0 0 0 1 0 0 0 1 0 1)
      (1 0 0 0 0 0 0 0 0 0 0 1)
      (1 1 1 1 1 1 1 1 1 1 1 1)))

(defclass location ()
  ((maze :initarg :maze
         :initform +maze+
         :reader get-maze)
   (x :initarg :x
      :initform 2.5
      :reader get-x)
   (y :initarg :y
      :initform 2.5
      :reader get-y)
   (theta :initarg :theta
          :initform 0
          :reader get-theta)))

(defun ud-input ()
  (- (if (sdl2:keyboard-state-p :scancode-up) 1 0)
     (if (sdl2:keyboard-state-p :scancode-down) 1 0)))

(defun lr-input ()
  (- (if (sdl2:keyboard-state-p :scancode-right) 1 0)
     (if (sdl2:keyboard-state-p :scancode-left) 1 0)))

(defun pg-input ()
  (- (if (sdl2:keyboard-state-p :scancode-pageup) 1 0)
     (if (sdl2:keyboard-state-p :scancode-pagedown) 1 0)))

(defun canonicalize-angle (angle)
  (cond ((>= angle pi) (canonicalize-angle (- angle (* pi 2))))
        ((>= angle (- pi)) angle)
        (t (canonicalize-angle (+ angle (* pi 2))))))

(defparameter +translation-rate+ 3.0) ;; tiles per second
(defparameter +rotation-rate+ pi) ;; radians per second

(defmethod next-state ((location location) dt)
  (let ((fbstep (* (ud-input) +translation-rate+ dt))
        (lrstep (* (pg-input) +translation-rate+ dt))
        (thstep (* (lr-input) +rotation-rate+ dt))

        (old-x (get-x location))
        (old-y (get-y location))
        (cos-theta (cos (get-theta location)))
        (sin-theta (sin (get-theta location))))

    (let ((new-x (+ old-x (* sin-theta fbstep) (- (* cos-theta lrstep))))
          (new-y (+ old-y (* cos-theta fbstep) (+ (* sin-theta lrstep))))
          (new-theta (canonicalize-angle (+ (get-theta location) thstep))))
      (cond ((zerop (aref (get-maze location) (floor new-x) (floor new-y)))
             (make-instance 'location :x new-x :y new-y :theta new-theta))
            ((zerop (aref (get-maze location) (floor old-x) (floor new-y)))
             (make-instance 'location :x old-x :y new-y :theta new-theta))
            ((zerop (aref (get-maze location) (floor new-x) (floor old-y)))
             (make-instance 'location :x new-x :y old-y :theta new-theta))
            (t
             (make-instance 'location :x old-x :y old-y :theta new-theta))))))

(defclass fp-view ()
  ((location :initarg :location
             :reader get-location)))

(defmethod next-state ((fp-view fp-view) dt)
  (make-instance 'fp-view :location (next-state (get-location fp-view) dt)))

(defun range (location relative-theta)
  (let* ((angle (+ (get-theta location) relative-theta))

         (dx/dS (sin angle))
         (dy/dS (cos angle))

         (x-step (if (< dx/dS 0) -1 1))
         (y-step (if (< dy/dS 0) -1 1))

         (dS/dx (abs (/ 1 (if (zerop dx/dS) 1e-30 dx/dS))))
         (dS/dy (abs (/ 1 (if (zerop dy/dS) 1e-30 dy/dS)))))

    (let dda ((next-x (* dS/dx
                         (if (< dx/dS 0)
                             (- (get-x location) (floor (get-x location)))
                             (- (+ 1.0 (floor (get-x location))) (get-x location)))))
              (mapx (floor (get-x location)))
              (next-y (* dS/dy
                         (if (< dy/dS 0)
                             (- (get-y location) (floor (get-y location)))
                             (- (+ 1.0 (floor (get-y location))) (get-y location)))))
              (mapy (floor (get-y location)))
              (distance 0))
      (cond ((not (zerop (aref (get-maze location) mapx mapy))) distance)
            ((< next-x next-y)
             (dda (+ next-x dS/dx) (+ mapx x-step)
                  next-y mapy
                  next-x))
            (t
             (dda next-x mapx
                  (+ next-y dS/dy) (+ mapy y-step)
                  next-y))))))

(defparameter +field-of-view+ (/ pi 4))

(defun column->theta (column)
  (- (* (/ column +window-width+) +field-of-view+) (/ +field-of-view+ 2)))

(defun vraster (location column)
  (let* ((theta (column->theta column))
         (distance (range location theta))
         (px (+ (get-x location) (* (sin (+ (get-theta location) theta)) distance)))
         (py (+ (get-y location) (* (cos (+ (get-theta location) theta)) distance)))
         (wx (< (abs (- py (round py))) 0.05))
         (wy (< (abs (- px (round px))) 0.05)))
    (values
     (min #xFF (floor (/ (if wx #xff #x00) distance)))
     (min #xFF (floor (/ #xfF distance)))
     (min #xFF (floor (/ (if wy #xff #x00) distance)))
     (min +window-height+ (/ (* +window-height+ 2) distance)))))

(defmethod render! (renderer (fp-view fp-view))
  (dotimes (column +window-width+)
    (multiple-value-bind (r g b height)
        (vraster (get-location fp-view) column)
      (sdl2:set-render-draw-color renderer r g b #xFF)
      (sdl2:render-draw-line renderer
                             column (round (+ (/ +window-height+ 2) (/ height 2)))
                             column (round (- (/ +window-height+ 2) (/ height 2)))))))

;; (run (list (make-instance 'fp-view :location (make-instance 'location))))

Wednesday, August 17, 2022

Playing with graphics

I wanted to play with some graphics. I don't know much about graphics, so I wanted to start with the basics. I played around with a couple of demos and I found that easiest to get reliably working was SDL2.

After downloading the SDL binary library and installing the FFI bindings with Quicklisp, I was off and running. You can find numerous SDL demos and tutorials on line and I tried a number of them. After I felt confident I decided to try something simple.

One thing I've noticed about graphics programs is the ubiquity of mutable state. Everything seems mutable and is freely modified and global variables abound. As a mostly functional programmer, I am alarmed by this. I wanted to see where we'd get if we tried to be more functional in our approach and avoid mutable data structures where practical.

Now the pixels on the screen had best be mutable, and I'm not trying to put a functional abstraction over the drawing primitives. We'll encapsulate the rest of the state in a state machine that is driven by the SDL event loop. The state machine will keep track of time and the current world. The current world is simply an immutable list of immutable objects. The state machine can transition through a render! phase, where it renders all the objects in the current world to a fresh frame. It attempts to do this about 75 times a second. The state machine can also transition through a next-world phase, where the current world and a delta-t are used to compute a new version of the world.

Our run program will take the initial list of objects. We'll start by initializing SDL, creating a window, and allocating a renderer for that window:

(defun run (initial-world)
  (sdl2:with-init (:video)
    (sdl2:with-window (window
                       :h +window-height+
                       :w +window-width+
                       :flags '(:shown))
      (sdl2:with-renderer (renderer window :index -1 :flags '())
        ... )))

Now we need the event loop state. last-ticks records the value from sdl2:get-ticks from the last time we processed the :idle event. This will be used to compute the elapsed time in ticks. render-ticker will record how many ticks have elapsed since the last time we rendered a frame to the screen. When render-ticker exceeds a certain amount, we'll call (render! current-world) and reset the ticker to zero. title-ticker will record how many ticks have occurred since the last time the window title was updated. When title-ticker exceeds a certain amount, we'll call sdl2:set-window-title to update the window title with some stats. sim-count is simply the number of times we've iterated next-world and frame-count is the number of times we've called render!. These are reset to zero every time we refresh the window title, so we'll have the frames per second and the world steps per second in the window title.

        (let ((last-ticks 0)
              (render-ticker 0)
              (title-ticker 0)
              (sim-count 0)
              (frame-count 0)
              (world initial-world))

          (flet ((title-tick! (dticks)
                   (incf title-ticker dticks)
                   (when (>= title-ticker 1000)
                     (decf title-ticker 1000)
                     (sdl2:set-window-title window (format nil "Sim rate: ~d, Frame rate: ~d" sim-count frame-count))
                     (setq sim-count 0)
                     (setq frame-count 0)))

                 (world-tick! (dticks)
                   (incf sim-count)
                   (setq world (next-world world (/ dticks 1000))))

                 (render-tick! (dticks)
                   (incf render-ticker dticks)
                   (when (>= render-ticker 13)
                     (incf frame-count)
                     (decf render-ticker 13)
                     (render-world! renderer world))))

Now we can run the event loop. The idle event is where the action happens:

          (sdl2:with-event-loop (:method :poll)

              (:idle ()
                     (let ((this-ticks (sdl2:get-ticks)))
                       (if (= this-ticks last-ticks)
                           (sdl2:delay 1)
                           (let ((dticks (- this-ticks last-ticks)))
                             (setq last-ticks this-ticks)
                             (title-tick! dticks)
                             (world-tick! dticks)
                             (render-tick! dticks)))))

              (:keydown (:keysym keysym)
                        (case (sdl2:scancode keysym)
                          (:scancode-escape (sdl2:push-quit-event))
                          (:scancode-x      (sdl2:push-quit-event))))

              (:quit () t))

Now that's a bunch of state, but it's more or less under control because what we have is a state machine and the state variables aren't accessible to anything.

render-world! is straightforward. It clears the renderer, calls render! on every object in the world, and presents the renderer for display.

(defun render-world! (renderer world)
  (sdl2:set-render-draw-color renderer #x00 #x00 #x00 #xFF)
  (sdl2:render-clear renderer)
  (mapc (lambda (object) (render! renderer object)) world)
  (sdl2:render-present renderer)
  )

next-world is a function that maps the current world to the next. It basically calls next on each object in the world and accumulate the results. We want objects to be able to go away, so if (next object) returns nil, we don't accumulate anything in the new world. If next returns the object unchanged, it will be accumulated unchanged in the next world. (next object) returns a new version of an object to simulate an update to the object. We want to be able to increase the amount of objects, so we allow (next object) to return a list of objects to be accumulated.

(defun next-world (previous-world dt)
  (fold-left
   (lambda (items item)
     (let ((more (next item dt)))
       (cond ((null more) items)
             ((consp more) (append more items))
             (t (cons more items)))))
   '()
   previous-world))

We'll start with a user-controlled player.

(defclass player ()
  ((x :initarg :x
      :reader get-x)
   (y :initarg :y
      :reader get-y)))

Everything that is to be displayed needs a render! method. This one just draws a little green triangle facing up.

(defmethod render! (renderer (player player))
  (let ((x (floor (get-x player)))
        (y (floor (get-y player))))
    (sdl2:set-render-draw-color renderer #x00 #xFF #x00 #xFF)
    (sdl2:render-draw-line renderer (- x 8) (+ y 8) (+ x 8) (+ y 8))
    (sdl2:render-draw-line renderer (- x 8) (+ y 8) (- x 1) (- y 16))
    (sdl2:render-draw-line renderer (+ x 8) (+ y 8) x (- y 16))
    (sdl2:render-draw-point renderer x y)
    ))

The next method computes the player in the next world:


(defun x-input ()
  (- (if (sdl2:keyboard-state-p :scancode-right)
         1
         0)
     (if (sdl2:keyboard-state-p :scancode-left)
         1
         0)))

(defun y-input ()
  (- (if (sdl2:keyboard-state-p :scancode-down)
         1
         0)
     (if (sdl2:keyboard-state-p :scancode-up)
         1
         0)))

(defparameter +player-speed+ 200.0) ;; pixels per second

(defmethod next ((player player) dt)
  (let ((new-x (max 8  (min (- +window-width+ 8)
                            (+ (get-x player)
                               (* (x-input) +player-speed+ dt)))))
        (new-y (max 16 (min (- +window-height+ 8)
                            (+ (get-y player)
                               (* (y-input) +player-speed+ dt))))))
    (make-instance 'player :x new-x :y new-y)))

Once we've defined a render! method and a next method, we're ready to go. If we call run on a list containing a player object, we'll have our little player on the screen controllable with the arrow keys.

An enemy ship can be defined.

(defclass enemy ()
  ((x :initarg :x :reader get-x)
   (y :initarg :y :reader get-y)
   (dx :initarg :dx :reader get-dx)
   (dy :initarg :dy :reader get-dy)))

(defmethod next ((enemy enemy) dt)
  (let ((new-x (+ (get-x enemy) (* (get-dx enemy) dt)))
        (new-y (+ (get-y enemy) (* (get-dy enemy) dt))))
    (when (and (>= new-x 8)
               (< new-x (+ +window-width+ 8))
               (>= new-y 8)
               (< new-y (- +window-height+ 16)))
      (make-instance 'enemy
                     :x new-x
                     :y new-y
                     :dx (get-dx enemy)
                     :dy (get-dy enemy)))))

;;; Render method omitted

As given, enemy ships will drift at constant speed until they run off the screen. We'd like to replenish the supply, so we'll make an enemy spawner:

(defclass enemy-spawner ()
  ((timer :initarg :timer :initform 0 :reader get-timer)))

(defmethod next ((spawner enemy-spawner) dt)
  (let ((new-time (- (get-timer spawner) dt)))
    (if (> new-time 0)
        (make-instance 'enemy-spawner :timer new-time)
        (list (make-instance 'enemy-spawner :timer (+ 1 (random 4)))
              (make-instance 'enemy :x (random (+ (- +window-width+ 32) 16))
                                    :y 16
                                    :dx (- 25 (random 50))
                                    :dy (+ (random 100) 50))))))

(defmethod render! (renderer (enemy-spawner enemy-spawner))
  nil)
The render! method doesn't do anything so a spawner doesn't have an image. It simply has a timer. To compute the next spawner, we subtract dt and create a new spawner with the reduced amount of time. If that's not a positive amount of time, though, we create two objects: a new spawner with somewhere between 1 and 5 seconds time and a new enemy ship.

We'll modify our player to allow him to shoot at the enemy:

(defclass player ()
  ((x :initarg :x
      :reader get-x)
   (y :initarg :y
      :reader get-y)
   (fire-cycle :initarg :fire-cycle
               :initform 0
               :reader get-fire-cycle)))

(defmethod next ((player player) dt)
  (let ((new-x (limit 8 (- +window-width+ 8) (+ (get-x player) (* (x-input) +player-speed+ dt))))
        (new-y (limit 16 (- +window-height+ 8) (+ (get-y player) (* (y-input) +player-speed+ dt))))
        (next-fire-cycle (- (get-fire-cycle player) dt)))
    (if (and (sdl2:keyboard-state-p :scancode-space)
             (< next-fire-cycle 0))
        (list
         (make-instance 'player
                        :x new-x
                        :y new-y
                        :fire-cycle .1)
         (make-instance 'bullet
                               :x (- (get-x player) 8)
                               :y (- (get-y player) 16)
                               :dx 0
                               :dy (- +bullet-speed+))
         (make-instance 'bullet
                               :x (+ (get-x player) 8)
                               :y (- (get-y player) 16)
                               :dx 0
                               :dy (- +bullet-speed+)))
        (make-instance 'player
                       :x new-x
                       :y new-y
                       :fire-cycle next-fire-cycle))))

A bullet is a simple moving object:

(defclass bullet ()
  ((x :initarg :x :reader get-x)
   (y :initarg :y :reader get-y)
   (dx :initarg :dx :reader get-dx)
   (dy :initarg :dy :reader get-dy)))

(defmethod next ((bullet bullet) dt)
  (let ((new-x (+ (get-x bullet) (* (get-dx bullet) dt)))
        (new-y (+ (get-y bullet) (* (get-dy bullet) dt))))
    (when (and (>= new-x 0)
               (< new-x +window-width+)
               (>= new-y 0)
               (< new-y +window-height+))
      (make-instance 'bullet
                     :x new-x
                     :y new-y
                     :dx (get-dx bullet)
                     :dy (get-dy bullet)))))

At this point we can move around the screen and shoot at enemies that spawn periodically. The problem is that the bullets go right through the enemy. We need to handle object collisions. We'll modify the next-world function. As it loops over the objects in the world, it will perform an inner loop that checks for collisions with other objects. If two objects collide, a function is called to get the collision results and those results are added to the list of objects in the world. If an object doesn't collide with anything, the next method is called to get the next version of the object.

(defun next-world (previous-world dt)
  (let outer ((tail previous-world)
              (next-world '()))
    (cond ((consp tail)
           (let ((this (car tail)))
             (let inner ((those (cdr tail)))
               (cond ((consp those)
                      (let ((that (car those))
                            (others (cdr those)))
                        (if (collides? this that)
                            (outer (append (collide this that) (delete that (cdr tail)))
                                   next-world)
                            (inner others))))
                     ((null those)
                      (outer (cdr tail)
                             (let ((more (next this dt)))
                               (cond ((consp more) (append more next-world))
                                     ((null more) next-world)
                                     (t (cons more next-world))))))
                     (t (error "Bad list."))))))
          ((null tail) next-world)
          (t (error "Bad list.")))))

We define collides? as a generic function that returns nil by default

(defgeneric collides? (this that)
  (:method ((this t) (that t)) nil)
  )
so that most objects don't collide. In the case where something does collide, we'll define collide as a generic function that returns nil by default
(defgeneric collide (this that)
  (:method ((this t) (that t)) nil)
  )
so when two objects collide, they simply disappear.

collides? will be called on pairs of objects in no particular order, so method pairs will be needed to handle both orders. We'll define collides? methods on bullets and enemies that checks if the bullet is within the bounding box of the enemy:

(defmethod collides? ((this bullet) (that enemy))
  (and (> (get-x this) (- (get-x that) 8))
       (< (get-x this) (+ (get-x that) 8))
       (> (get-y this) (- (get-y that) 8))
       (< (get-y this) (+ (get-y that) 8))))

(defmethod collides? ((this enemy) (that bullet))
  (collides? that this))

At this point, we can shoot enemy ships. The default method for collide between an enemy and a bullet returns nil so the enemy and the bullet simply disappear. If we were fancy, we could arrange for it to return an explosion object or several debris objects.

It would be nice to keep a tally of the number of enemy ships we have shot. We don't have to add any extra machinery for this. We create a score class and a point class:

(defclass score ()
  ((value :initarg :value
          :reader get-value)))

(defmethod next ((score score) dt) score)

;;; Render method prints score on screen.

(defclass point ()
  ((value :initarg :value
          :reader get-value)))

(defmethod next ((point point) dt) point)

(defmethod render! (renderer (point point)) nil)
Scores and points are immutable objects without positions, but we'll define methods so that when a score and a point collide, the result is a higher score.
(defmethod collides? ((this point) (that score)) t)
(defmethod collides? ((this score) (that point)) t)

(defmethod collide ((this point) (that score))
  (list (make-instance 'score
                       :font (get-font that)
                       :value (+ (get-value this) (get-value that)))))

(defmethod collide ((this score) (that point))
  (collide that this))
Now we'll define a bullet colliding with an enemy to produce a point:
(defmethod collide ((this bullet) (that enemy))
  (list (make-instance 'point :value 1)
        ;; add explosion object here
        ))

(defmethod collide ((this enemy) (that bullet))
  (collide that this))
So when you shoot an enemy, the bullet and enemy disappear to be replaced by a point. On the next update, the point will collide with the score to be replaced with an updated score.

At this point we've got a little demo game where we can fly a ship around and shoot enemies and a running score is kept. The world model is immutable and worlds are functions of previous worlds. I'll call it a successful proof of concept.

But did this buy us anything? We don't have mutable state per se, but we've kind of cheated. When we create new versions of an object, each version is immutable, but the sequence of versions taken as a whole seem to be evolving over time. For example, consider the score. At each time step, there is an immutable score object, but over time what is considered the current score changes. We've eliminated the direct problems of mutation, but we've introduced the problem of keeping track of what series of immutable versions correspond to a single evolving instance.

In this small example, we're not keeping track of the evolving objects. For instance, each bullet, as it is updated from step to step, is actually created anew at its new position on each step. The old bullet instance is dropped and the new instance really has no idea how it got there. Bullets are such simple objects that this doesn't matter, but the current score is different. It makes sense for there to be a singleton score object that increases over time, but we haven't built that in to our model. Instead, we've designed a set of collision interactions that drive the score.

We've eliminated the direct mutable state in our objects and our world, but sometimes we want to model stateful objects. We therefore create objects that represent state transitions (e.g. points) and then use the collision mechanism to combine the transition objects with the objects that represent physical entities. That seems a bit convoluted, and I don't think it will scale.

On the other hand, we do gain the immediate benefits of the world and the objects being immutable. Saving and restoring a world is trivial. Reasoning about objects at each update is easy because the objects don't change, but we now have to reason about how objects appear to change in the long run.

The tradeoff of immutable objects is increased allocation. But although a lot more consing is happening, most of it can be quickly reclaimed by the generational collector, so noticable GC pauses are infrequent. I haven't measured the performance, but it is certainly adequate for the little example I wrote. If you had a mechanism to reason about the objects as linear types (Sufficiently Smart Compiler), you could determine when you can update objects in place and avoid reallocating.

The world model, simply a list of objects, is flexible, but not well structured. For instance, the current score and the bullets are among the elements mixed together in this list. You'd have to search this list to find specific elements or filter this list to find elements of a certain type.

The simple collision model is O(n2), so it can't handle a ton of objects. A more sophisticated world model would be needed to keep track of different classes of collidable objects to avoid the O(n2) search. For example, if bullets were kept separately, we could avoid checking if they collide with each other.

The point of this exercise was to play with graphics and see what you can do without the mutable state that is alarmingly ubiquitous. It turns out that you can go pretty far, but it's kind of strange.