Rules, Types, and Glue: A Multi-Paradigm Architecture for Game Simulation

Abstract

We describe a domain exercise that evaluates three programming paradigms as layers in a game simulation engine: Prolog for rule-based knowledge, an ML-style type system (Coalton DSL) for typed computation, and Common Lisp as glue and tooling. The domain is a Gen-I Pokémon Yellow battle simulator — chosen for its well-specified rules, enumerable state space, and rich catalog data. We report benchmark results across SBCL (native compilation) and ECL (C-native and bytecode), document where each paradigm excels, and give honest findings about the friction at language boundaries. The central conclusion is that Prolog’s backward-chaining over ground facts is genuinely well-suited to rule-driven game knowledge; that an ML type layer adds real value at internal interfaces but creates a portability ceiling; and that Common Lisp’s role is strongest at the metalevel — tooling, codegen, and REPL-driven development — rather than as a runtime layer competing with C.

Source: github.com/denzuko/ml-prolog-pokemon

1. Introduction

Game simulation engines solve a recurring architectural problem: a large, structured body of rules (damage formulas, type interactions, status effects, item behaviors) must be applied efficiently to a dynamic state that changes every frame or turn. The naive approach — encode everything as C structs and switch statements — is fast but brittle. Rules are scattered across source files, adding a new mechanic requires touching multiple sites, and testing rule correctness in isolation is difficult.

The alternative explored here is layered paradigm specialisation: let each layer do what it does best, with explicit boundaries between them.

This is not a new idea. Logic programming for game AI has a lineage stretching from PROLOG-based adventure game engines in the 1980s through modern Datalog-based query systems in commercial engines. What is less explored is the interaction between a Prolog knowledge layer and a typed functional layer in the same runtime, and the performance and portability consequences of that interaction.

We chose Pokémon Gen-I Yellow as the domain because:

1. The type-effectiveness chart (17 types, ~72 non-trivial matchups) is a canonical example of a relational knowledge base — a set of ground facts with derived rules.
2. The battle mechanics are formally specified and well-documented, giving us a ground truth against which to test correctness.
3. The state space is small enough that exhaustive testing is practical.
4. The domain is familiar enough that readers can evaluate architectural decisions without domain-specific knowledge.

The exercise produced a working simulator: 65 functional tests passing at 100%, 11 performance regression tests, and benchmarks across two Common Lisp implementations.

2. Architecture

The system is structured as three layers with strict ownership boundaries.

┌────────────────────────────────────────────────────────────┐
│  PROLOG  (logic-engine.lisp + catalog.lisp)                 │
│  Rules: type chart · item effects · team validity           │
│  Facts: 151 Pokémon · 85 moves · 19 items · all trainers   │
│  Queries: suggest-badge-team · usable-item-p · team-valid-p │
└──────────────────────────┬───────────────────────────────────────────────────────┘
                           │  get-logic-multiplier
                           │  db-prove-first / db-prove-all
┌──────────────────────────╬───────────────────────────────────────────────────────┐
│  COALTON  (types.ct)                                        │
│  ADTs: PkmnType · Status · Move · Pokemon · BattleOutcome   │
│  Pure: calculate-damage · apply-end-of-turn · run-turn      │
│  Pure: simulate-battle (recursive, typed turn counter)      │
│  Escape: lookup-multiplier → one lisp form → Prolog query   │
└──────────────────────────┬───────────────────────────────────────────────────────┘
                           │  plist→Pokemon · match-outcome
┌──────────────────────────╬───────────────────────────────────────────────────────┐
│  CL GLUE  (simulator.lisp — ~80 lines)                      │
│  Bridges catalog plists to Coalton values                   │
│  Entry points: run-simulation · run-badge-battle            │
└──────────────────────────────────────────────────────────────────────────────────┘

The boundary rule is explicit: Prolog owns facts and rules; Coalton owns typed computation; CL owns nothing except bridging. If simulator.lisp acquires logic, something has crossed the wrong boundary.

2.1 The Prolog Layer

The knowledge base is a prolog-db struct (a hash table keyed by functor) populated by make-pokemon-kb. Fact schemas:

(pokemon   name num type1 type2 base-hp base-atk base-def base-spc base-spd)
(move      name type category power accuracy pp effect)
(item      name symbol description)
(gym-party gym  slot species level m1 m2 m3 m4)
(effectiveness  atk-type def-type result)
(immune         atk-type def-type)
(counters       atk-type def-type)

All atoms are normalised to Common Lisp keywords on db-assert — :fire not POKEMON-LOGIC::FIRE. This eliminates cross-package symbol mismatch entirely.

A note on the Prolog evaluator: we evaluated wmannis/cl-gambol first. It has a known infinite-loop bug in SBCL 2.x headless environments: the continuation-passing search causes unify to recurse infinitely via SBCL’s tail-call optimiser. The bug was confirmed via disassembly and call-depth tracing. We replaced it with a self-contained 60-line backward-chaining interpreter with correct symmetric unification.

2.2 The Coalton Layer

Coalton is an ML-style type system DSL for Common Lisp. It compiles to CL via a macro-expansion pipeline and provides Hindley-Milner type inference, algebraic data types, and pattern matching. The battle computation is fully typed:

BattleOutcome = Victor Pokemon | Draw | Ongoing Pokemon Pokemon

simulate-battle :
  PrologDb → Pokemon → Move → Pokemon → Move → IFix → BattleOutcome

The Victor | Draw | Ongoing sum type means the compiler enforces exhaustiveness on every match. This caught a real bug during development: an early version of the loop body used a CL cond that had no draw arm.

The single impure call site is lookup-multiplier:

(define (lookup-multiplier kb atk-t def-t)
  (lisp Fraction (kb atk-t def-t)
    (pokemon-logic:multiplier->ratio
      (pokemon-logic:get-logic-multiplier
        kb
        (cl:intern (pokemon-sim::type->string atk-t) "KEYWORD")
        (cl:intern (pokemon-sim::type->string def-t) "KEYWORD")))))

The lisp form is Coalton’s controlled escape hatch. There is exactly one in the codebase.

2.3 The CL Glue Layer

simulator.lisp is ~80 lines with no logic. It bridges catalog data (plists) to Coalton values and exposes human-readable entry points. The match-outcome macro required three iterations due to cross-package symbol resolution: BattleOutcome/Victor’s slot is POKEMON-SIM::|_0| (Coalton’s generated name), but the binding name winner in the macro expansion resolves to the caller’s package. The final form accepts keyword arguments (:winner w) to let the caller control the binding name.

3. Layer-by-Layer Analysis

3.1 Prolog: What Worked

The type-effectiveness chart as Prolog facts is the most natural representation considered. The advisor query is four lines of logic on top of the Prolog query. In a C implementation this is a lookup table, a scoring loop, and a sort — more code, harder to change. When the Gen-II type chart added Steel and Dark, only new effectiveness facts need asserting; the query logic is unchanged.

Item interactions — item-cures-status, item-restores-hp, item-revives — are Prolog facts. When a new item is added, one fact is asserted; no recompilation.

3.2 Prolog: What Didn’t

Performance at the Prolog/Coalton boundary. lookup-multiplier takes ~7 µs per call on SBCL — one intern call plus one hash-table probe. For turn-based simulation this is acceptable; for real-time simulation the boundary cost accumulates. Pre-computing a 17×17 effectiveness matrix at kb-construction time reduces per-call cost to a single array lookup. Robert Smith (Coalton, HRL) identifies type->string on the hot path as the deeper issue: Coalton’s REPR :ENUM would represent PkmnType as package-qualified symbols without a string conversion step; REPR :NATIVE gives fully user-controlled layout. Either eliminates the type->string → intern round-trip on every damage calculation.

The gambol bug. A production Prolog evaluator embedded in a CL system should be expected to work. wmannis/cl-gambol does not in SBCL 2.x headless, and the TCO interaction bug is non-trivial to fix. Teams evaluating this architecture should use SWI-Prolog’s libswipl or write a domain-specific evaluator.

3.3 Coalton: What Worked

Exhaustiveness at sum-type boundaries. The BattleOutcome type made the turn loop correct by construction. Catching type errors early. calculate-damage was initially declared to return UFix but the body computed Integer (from floor). Coalton caught this at compile time. Self-documenting boundaries. The lisp escape is syntactically visible; any reviewer immediately sees where the type system boundary is.

3.4 Coalton: What Didn’t

Limited portability. The official Coalton README states: “While we try to be ANSI-conforming, Coalton is currently only tested on recent versions of SBCL, Allegro CL, and Clozure CL.” [coalton-lang/coalton] ECL is not in that tested set. Our tests confirmed it fails to load on ECL 21.2.1 — the root cause is a readmacro returning two values, which SBCL permits as an extension but ECL rejects. Robert Smith (HRL Laboratories, Coalton core contributor) notes that patches exist to make Coalton compile on ECL but compilation takes upwards of an hour versus under 60 seconds on SBCL, making it impractical for any workflow. ABCL lacks tail-call elimination and has required multiple compliance patches over the project’s history. This is a practical resource and testing constraint, not a philosophical design position.

lisp escape capture requires care. During development, variable names captured in lisp forms produced unexpected internal names (def-type appearing as DEF-TYPE-45 in the generated code), causing an “illegal function call” error. Our fix — routing type strings into the escape rather than PkmnType values directly — resolved it. Robert Smith (Coalton, HRL) notes that Coalton variables are intentionally renamed during compilation, the lisp form’s capture list is the correct mechanism for controlling what is visible inside the body, and the injected Lisp code is passed through as-is. On reflection this was likely a misuse of the capture syntax on our part rather than a Coalton deficiency; the workaround is valid but the root attribution in an earlier version of this article was incorrect.

4. Performance

All benchmarks on SBCL 2.2.9 and ECL 21.2.1, x86-64. SBCL: native compilation. ECL: C-compiled .fas files (Speed=3, Safety=2).

4.1 Knowledge Layer

4.2 Battle Computation Layer (Coalton, SBCL/CCL/Allegro)

At 138 µs per simulation, SBCL delivers approximately 7,200 simulations per second on a single core. For a team-building advisor this is more than adequate. For a real-time engine at 60 Hz with hundreds of combatants, the Coalton layer would need to be replaced with C99, with the Prolog layer retained for cached rule queries.

4.3 ECL Portability

The Coalton layer does not load on ECL. The pure-CL knowledge layer runs on ECL C-native at 3.5× the SBCL baseline. ECL bytecode is 50–55× slower than SBCL for query-heavy operations — not suitable for any tight simulation loop.

5. Architectural Conclusions

5.1 What Belongs Where

The correct layering for a high-performance game engine with this architecture:

C99          Hot path, state machine, arena allocation.
             Prolog multiplier results cached after first query.

Prolog       Rules and knowledge: type chart, AI decision trees,
             item interactions, encounter tables, dialogue conditions.

Common Lisp  Metalevel: spec → C header generation, asset pipeline,
             REPL inspection of live state via CFFI, test harness.

The Coalton/SML layer is valuable at internal module boundaries but creates a portability ceiling when the runtime target is C-embedded Lisp. The same exhaustiveness guarantees come from C enums with -Wswitch-enum at zero portability cost.

5.2 The Overlap Question

There is an apparent overlap between Coalton’s PkmnType sum type and Prolog’s :fire, :grass keyword atoms. In practice these serve orthogonal purposes. Coalton’s PkmnType is a static dispatch discriminant: pattern matching is checked for exhaustiveness at compile time. Prolog’s keyword atoms are dynamic unification terms: the type chart query succeeds or fails at runtime. The bridge — (intern (type->string t) "KEYWORD") — is one line, not a design smell.

5.3 Do You Need SML/Coalton?

The argument is strongest when typed functional computation sits between CL and Prolog as a middle layer — and the benefits (exhaustiveness, early type error detection) were real. But if C99 owns the hot path and Prolog owns the rules, the typed middle layer shrinks to: “Do I need exhaustiveness checking on my game’s state machine transitions?” If those are C enums in a switch with -Wswitch-enum, the compiler already provides that guarantee. Coalton adds value proportional to the number and complexity of sum types at internal boundaries. The weak version of the conclusion: use Prolog for rules, CL for tooling, and C for runtime. The typed functional layer is optional and SBCL-specific.

6. Related Work

Orkin’s work on F.E.A.R.’s planning system used a STRIPS-style planner that shares the Prolog philosophy of declarative goal specification. Datalog-based query engines have appeared in several commercial engines precisely because backward-chaining is a natural fit for “is the player in state X?” queries. The Coalton project, developed at HRL Laboratories and maintained as open source at github.com/coalton-lang/coalton, targets exactly the use case explored here. Languages like AngelScript and Squirrel are designed as embedded scripting layers above a C engine — the same architectural position as the Prolog + CL stack, but without backward-chaining.

7. Availability

Source code, benchmarks, and all documentation: github.com/denzuko/ml-prolog-pokemon. Three ASDF systems: pokemon-sim (core), pokemon-sim/test (65 tests), pokemon-sim/perf (11 performance regression tests). Requires SBCL 2.x and Quicklisp.

Acknowledgements

Robert Smith (u/stylewarning, HRL Laboratories) provided corrections to an earlier version of this article via the r/Common_Lisp community: the Coalton portability framing, the lisp capture semantics, and the REPR recommendation for the hot path. Those corrections are incorporated above. Errors that remain are the author’s own.

References

1. Clocksin, W. F. and Mellish, C. S. Programming in Prolog. Springer, 1981.
2. Norvig, P. Paradigms of Artificial Intelligence Programming. Morgan Kaufmann, 1992.
3. Orkin, J. “Three States and a Plan: The AI of F.E.A.R.” GDC Proceedings, 2006.
4. The Coalton Authors. Coalton: ML-style Types for Common Lisp. HRL Laboratories / coalton-lang, 2021–present. README: “Coalton is currently only tested on recent versions of SBCL, Allegro CL, and Clozure CL.” github.com/coalton-lang/coalton
5. Milner, R., Tofte, M., and Harper, R. The Definition of Standard ML. MIT Press, 1990.
6. Steele, G. L. Common Lisp the Language, 2nd ed. Digital Press, 1990.
7. wmannis. cl-gambol: A Gambol Prolog Interpreter for Common Lisp. github.com/wmannis/cl-gambol.
8. ECL Team. Embeddable Common Lisp 21.2.1. ecl.common-lisp.dev, 2021.