_{"Even in our sleep, pain which cannot forget falls drop by drop upon the heart, until, in our own despair, against our will, comes wisdom through the awful grace of God." -- Aeschylus}

Lisa is a production-quality, forward-chaining expert system shell featuring an optimized implementation of Charles Forgy's Rete algorithm, a highly efficient solution to the difficult many-to-many pattern matching problem¹. Written in modern Common Lisp using the Common Lisp Object System (CLOS) and the Meta Object Protocol (MOP), Lisa is designed for seamless integration with existing Common Lisp applications. Lisa maximizes the expressive power of CLOS and the MOP without imposing strict class hierarchy constraints, allowing developers to add sophisticated reasoning capabilities to their applications with minimal effort.

Lisa is known to run on the following ANSI Common Lisp implementations:

• SBCL
• Clasp (NEW!)
• LispWorks
• Allegro Common Lisp (ACL)
• CLISP
• CMUCL (19a)
• OpenMCL
• Armed Bear Common Lisp (ABCL)

Lisa is under active development as of January 2025. In December 2024, the project was migrated from SourceForge to GitHub, with comprehensive updates to the codebase and directory structure. Several bugs that had accumulated during the project's hiatus were identified and resolved (see Credits).

Lisa has been modernized with new features including integrated logging support via log4cl. Most significantly, extensive performance profiling using SLIME and SBCL's deterministic profiler has led to substantial optimization improvements (see Performance Optimization).

Lisa successfully loads and runs on SBCL 2.4.11. See the Example Rulebases documentation for demonstrations of classic AI problems implemented in Lisa, including the Monkey and Bananas planning problem, the Towers of Hanoi, and others.

• Quicklisp Support: As of Spring 2025.
• Modern Logging: Integrated log4cl throughout the codebase, replacing ad-hoc format and error forms with structured logging.
• Performance Optimization: Runtime improvements through strategic inlining and build order optimization (see Performance Optimization).
• Bug Fixes: Repaired the long-broken TEST and LOGICAL conditional elements.
• SBCL Enhancements: Ported auto-notification support to SBCL.

Recent profiling work using SBCL's deterministic profiler identified critical performance bottlenecks in Lisa's token manipulation code. The primary hotspot was TOKEN-PUSH-FACT, which was being called millions of times during typical inference runs without being inlined.

Several key optimizations were implemented:

1. Inline Declarations: Added (declaim (inline ...)) declarations for hot-path token functions including TOKEN-PUSH-FACT, TOKEN-POP-FACT, and TOKEN-TOP-FACT.

2. Accessor Replacement: In a few cases, some hot class accessors were replaced with regular Lisp functions that now use SLOT-VALUE. Such rewrites allowed these functions to be inlined.

3. Build Order Optimization: Moved token.lisp earlier in the ASDF system definition (from 19th to 5th position) to ensure the compiler sees inline declarations before compiling files that depend on them. This simple reordering allowed the compiler to eliminate 45+ million function calls through inlining.

Time Improvements

1. Critical hotspot (TEST-TOKENS)

   • Unoptimized: 1.298 seconds
   • Optimized: 0.629 seconds
   • 51% faster: cut execution time in half

2. Total profiled execution

   • Unoptimized: 3.298 seconds
   • Optimized: 1.614 seconds
   • 51% reduction in profiled time

Memory Improvements

1. Memory allocation reduction
   • Unoptimized: 13,612,824,256 bytes
   • Optimized: 8,609,908,064 bytes
   • 37% less memory allocated

The key win is visible in the profile differences. In the unoptimized version, these hot functions appeared:

• FAST-ARRAY-COPY: 0.304s, 444MB consed
• TOKEN-PUSH-FACT: 0.301s, 356MB consed
• GET-SLOT-VALUE: 0.280s, 307MB consed
• TOKEN-TOP-FACT: 0.243s, 237MB consed
• TOKEN-HASH-CODE: 0.019s
• TOKEN-FACT-COUNT: 0.023s

In the optimized version, these functions show up in the "not called" list, confirming they've been successfully inlined. Their overhead disappeared into their callers.

TEST-TOKENS dropped from 1.95GB consed to just 161MB consed - that's a 91% reduction in allocations for the hottest function. The inlining eliminated function call overhead and allowed better compiler optimization.

These optimizations yielded a significant improvement in overall runtime performance on the Monkey and Bananas benchmark (500 iterations). They demonstrate the importance of both compiler hints and compilation order in Common Lisp systems. Lisa's CLOS-based architecture is now performing close to its theoretical maximum on SBCL/ARM64.

You can see the current Apple M2 Pro profiling benchmark results in the sbcl directory.

Lisa's fundamental CLOS-based architecture will remain unchanged, as it provides an elegant foundation for the Rete implementation. Current development priorities include:

• Linux Performance Testing: Profiling will continue on x86-64 hardware to analyze Lisa's performance characteristics on SBCL/Linux. On that hardware, SBCL's statistical profiler should be available to better analyze Lisa's behavior under significant load.

Lisa is actively developed and tested on SBCL. Additional testing has been performed on AllegroExpress (the free version of Allegro Common Lisp) with excellent results. The core codebase represents Lisa version 3.2 and should run correctly on all supported Common Lisp implementations listed above.

Lisa intentionally maintains a simpler feature set compared to some expert system shells like CLIPS. While additional conditional elements (OR, FORALL, etc.) have been considered, they introduce behavioral complexity and are rarely essential in practice. Lisa prioritizes simplicity and elegance over syntactic convenience, keeping the system approachable and maintainable.

Complete documentation is available on the Lisa Wiki. New users should start with the Getting Started section for guidance on setting up SBCL with Emacs.

• SBCL - Steel Bank Common Lisp
• Emacs for MacOS
• Peter Norvig's Paradigms of Artificial Intelligence Programming
• Expert Systems: Principles and Programming, Giarratano & Riley

Over the years, several individuals have contributed enhancements, bug fixes, and useful functionality to Lisa. While I've lost touch with many of them, their contributions deserve recognition:

• Aneil Mallavarapu: Contributed several enhancements and bug fixes to the core system.
• Paolo Amoroso: Early advocate for Lisa in the open source community who suggested adding Certainty Factor support. His review of Lisa remains appreciated.
• Paul Werkowski: Contributed essential code for SBCL compatibility and an elegant package macro.
• Fred Gilham: Implemented auto-notification support for CMUCL.
• gassechen (Gaston): Created cl-lisa-web, an impressive web-based front-end for Lisa.

Special thanks to community members who have helped improve Lisa during its recent revival:

• gassechen (Gaston): Extensively tested Lisa and identified several long-standing bugs that had accumulated during the project's hiatus.
• cdmojoli: Identified and reported an auto-notification issue with SBCL.

David E. Young