-
Notifications
You must be signed in to change notification settings - Fork 0
Home
Lisa is a production-quality expert-system shell, developed atop an optimized implementation of Charles Forgy's Rete algorithm, a very efficient mechanism for solving the difficult many-to-many matching problem1. Lisa is written in modern Common Lisp and the Common Lisp Object System (CLOS), with a smattering of the Meta Object Protocol (MOP) sprinkled about.
Unique to Lisa is the ability to reason over CLOS objects without imposing special class hierarchy requirements; thus it should be possible to easily augment existing CLOS applications with reasoning capabilities. As Lisa is an extension to Common Lisp, the full power of the Lisp environment is always available. Lisa-enabled applications should run on any ANSI-compliant Common Lisp platform.
The Lisa project is driven by a number of important goals:
-
Unrestricted availability: Lisa is intended to be freely available to anyone interested in applying classic expert-systems technologies to real-world problems today. Production-rule systems still have their place within the AI community, regardless of the infatuation with LLM AIs. Indeed, Lisa is known to be currently used for logistics and planning applications, along with numerous research projects within universities around the world.
-
Portability: Vendor neutrality is a significant project goal, not because I disapprove of commercial software but to ensure Lisa is available on as many platforms as I can manage. As previously mentioned, Lisa is implemented in ANSI Common Lisp; currently, all development is being done using SBCL. Every effort will be made to avoid the use of implementation-specific functionality; in the cases where a non-ANSI feature must be used (e.g. multiprocessing support), Lisa will attempt to support the major Lisp implementations either through conditional evaluation or the use of a portable library.
-
Familiarity: Lisa's production-rule system has its roots in CLIPS, making it readily familiar to developers who've worked with either that product, or something similar.
-
Flexibility: Lisa reasons over CLOS objects without requiring changes to an application's class hierarchy. In addition, the full power of Common Lisp is available for use within productions; there is no dichotomy between Lisa's programming language and its implementation.
-
Simplicity: Along with portability, the project strives for simplicity and elegance at the functional, architectural and source code levels. This doesn't mean Lisa should have limited usefulness or suffer from poor performance; rather, it should be possible for new developers to easily understand the code layout and behavior. Unless performance absolutely demands otherwise, clarity of design and implementation will take precedence.
Version 3.2 was the latest official release on SourceForge, with its major improvement being the addition of support for Certainty Factors (CF), as described by Peter Norvig2.
As of December 2024, Lisa underwent a re-home effort to GitHub; it builds and runs successfully on SBCL 2.4.11. There are now numerous upgrades planned, including support for logging, metrics collection and new conditional elements.
Lisa should be considered stable and production quality. It is known to have been used in at least one commercial system, as well as numerous university and corporate research projects.
Full documentation on the Lisa programming environment may be found here. See the Getting Started section first, for details on easily configuring your SBCL/Emacs environment for Lisa use and development.
Lisa, as it has for decades, successfully runs the Monkey and Bananas rulebase, a classic AI planning problem. SBCL 2.4.11 was used as the test Lisp implementation, and the CLOS version of the MaB rulebase was used:
CL-USER> (load (translate-logical-pathname "lisa:examples;mab-clos.lisp"))
T
CL-USER> (in-package :lisa-user)
#<PACKAGE "LISA-USER">
LISA-USER> (run-mab)
<INFO> [15:00:26] lisa-mab mab.lisp (run-mab repeat-mab) - Starting run...
Monkey jumps off the GREEN-COUCH onto the floor.
Monkey walks to T2-2.
Monkey climbs onto the RED-COUCH.
Monkey climbs onto the BIG-PILLOW.
Monkey grabs the RED-CHEST.
Monkey throws the RED-CHEST off the BIG-PILLOW onto the floor.
Monkey jumps off the BIG-PILLOW onto the floor.
Monkey walks to T1-3.
Monkey grabs the RED-KEY.
Monkey walks to T2-2 holding the RED-KEY.
Monkey opens the RED-CHEST with the RED-KEY revealing the LADDER.
Monkey drops the RED-KEY.
Monkey climbs onto the RED-CHEST.
Monkey grabs the LADDER.
Monkey jumps off the RED-CHEST onto the floor.
Monkey walks to T7-7 holding the LADDER.
Monkey drops the LADDER.
Monkey climbs onto the LADDER.
Monkey grabs the BLUE-CHEST.
Monkey throws the BLUE-CHEST off the LADDER onto the floor.
Monkey jumps off the LADDER onto the floor.
Monkey grabs the LADDER.
Monkey walks to T8-8 holding the LADDER.
Monkey drops the LADDER.
Monkey climbs onto the LADDER.
Monkey grabs the GREEN-CHEST.
Monkey throws the GREEN-CHEST off the LADDER onto the floor.
Monkey jumps off the LADDER onto the floor.
Monkey walks to T2-2.
Monkey grabs the RED-KEY.
Monkey walks to T8-8 holding the RED-KEY.
Monkey opens the GREEN-CHEST with the RED-KEY revealing the BLUE-KEY.
Monkey drops the RED-KEY.
Monkey climbs onto the GREEN-CHEST.
Monkey grabs the BLUE-KEY.
Monkey jumps off the GREEN-CHEST onto the floor.
Monkey walks to T7-7 holding the BLUE-KEY.
Monkey opens the BLUE-CHEST with the BLUE-KEY revealing the BANANAS.
Monkey drops the BLUE-KEY.
Monkey climbs onto the BLUE-CHEST.
Monkey grabs the BANANAS.
Monkey eats the BANANAS.
Monkey is satisfied: #<MONKEY {7005BDC793}>
Evaluation took:
0.053 seconds of real time
0.053909 seconds of total run time (0.049362 user, 0.004547 system)
[ Real times consist of 0.011 seconds GC time, and 0.042 seconds non-GC time. ]
[ Run times consist of 0.011 seconds GC time, and 0.043 seconds non-GC time. ]
101.89% CPU
572 lambdas converted
27,305,904 bytes consed
NILLisa has been profiled using the Emacs Slime profiler front-end for SBCL's deterministic profiler. The results were impressive; the profiler found a significant hotspot within token management, leading to a change that greatly reduced time, memory usage and consing. Release 3.5 contains the latest performance enhancements:
CL-USER> (load "examples/mab")
M-x slime-profile-package
Package: lisa
CL-USER> (lisa-mab:run-mab 100)
<INFO> [10:33:48] lisa-mab mab.lisp (run-mab repeat-mab) - Starting run...
Monkey jumps off the GREEN-COUCH onto the floor.
Monkey walks to T2-2.
Monkey climbs onto the RED-COUCH.
...
CL-USER>
M-x slime-profile-report
measuring PROFILE overhead..done
seconds | gc | consed | calls | sec/call | name
----------------------------------------------------------------
0.086 | 0.015 | 494,573,472 | 473,600 | 0.000000 | LISA::REPLICATE-TOKEN
0.062 | 0.017 | 216,898,240 | 1,803,500 | 0.000000 | LISA::TOKEN-TOP-FACT
0.057 | 0.015 | 233,718,192 | 1,708,500 | 0.000000 | LISA::GET-SLOT-VALUE
0.027 | 0.004 | 84,660,288 | 1,510,500 | 0.000000 | LISA::TOKEN-PUSH-FACT
0.013 | 0.000 | 64,084,928 | 480,500 | 0.000000 | LISA::HASH-KEY
0.009 | 0.002 | 19,200,048 | 522,300 | 0.000000 | LISA::TOKEN-POP-FACT
0.005 | 0.000 | 40,319,552 | 46,400 | 0.000000 | LISA::MAKE-ADD-TOKEN
0.004 | 0.000 | 18,675,616 | 78,400 | 0.000000 | LISA::ACTIVATION-PRIORITY
0.003 | 0.000 | 13,171,680 | 86,000 | 0.000000 | LISA::CLASS-MATCHES-P
0.003 | 0.002 | 9,174,080 | 62,700 | 0.000000 | LISA::LOGICAL-BLOCK-P
0.002 | 0.002 | 0 | 8,100 | 0.000000 | LISA::ACTIVATION-TOKENS
0.002 | 0.000 | 2,031,584 | 24,400 | 0.000000 | LISA:INFERENCE-ENGINE
0.002 | 0.000 | 14,546,896 | 111,600 | 0.000000 | LISA::FIND-INSTANCE-OF-FACT
0.001 | 0.000 | 3,341,712 | 10,100 | 0.000000 | LISA::TOKEN-MAKE-FACT-LIST
0.001 | 0.000 | 982,960 | 25,600 | 0.000000 | (SETF LISA:SLOT-VALUE-OF-INSTANCE)
0.001 | 0.000 | 1,113,904 | 7,400 | 0.000000 | LISA::CLEAR-MEMORIES
0.001 | 0.000 | 3,014,096 | 14,300 | 0.000000 | LISA::TOKEN-INCREMENT-NOT-COUNTER
0.001 | 0.000 | 3,996,944 | 25,600 | 0.000000 | LISA::INITIALIZE-SLOT-VALUE
0.001 | 0.000 | 1,245,040 | 11,600 | 0.000000 | LISA::NEXT-FACT-ID
0.001 | 0.000 | 851,968 | 10,000 | 0.000000 | LISA::FIND-META-OBJECT
0.000 | 0.000 | 1,834,960 | 18,900 | 0.000000 | LISA::ELIGIBLE-P
0.000 | 0.000 | 2,174,224 | 13,500 | 0.000000 | LISA::MAKE-ACTIVATIONHere are the results of the initial performance run:
CL-USER> (load "examples/mab")
M-x slime-profile-package
Package: lisa
CL-USER> (lisa-mab:run-mab 100)
<INFO> [10:33:48] lisa-mab mab.lisp (run-mab repeat-mab) - Starting run...
Monkey jumps off the GREEN-COUCH onto the floor.
Monkey walks to T2-2.
Monkey climbs onto the RED-COUCH.
...
CL-USER>
M-x slime-profile-report
measuring PROFILE overhead..done
seconds | gc | consed | calls | sec/call | name
----------------------------------------------------------------
0.195 | 0.020 | 758,884,512 | 1,510,500 | 0.000000 | LISA::TOKEN-PUSH-FACT
0.075 | 0.004 | 390,672,512 | 522,300 | 0.000000 | LISA::TOKEN-POP-FACT
0.052 | 0.006 | 235,900,688 | 1,803,500 | 0.000000 | LISA::TOKEN-TOP-FACT
0.052 | 0.013 | 207,197,584 | 1,708,500 | 0.000000 | LISA::GET-SLOT-VALUE
0.014 | 0.000 | 64,217,568 | 480,500 | 0.000000 | LISA::HASH-KEY
0.011 | 0.006 | 20,641,904 | 601,900 | 0.000000 | LISA::TOKEN-FIND-FACT
0.009 | 0.004 | 18,150,912 | 78,400 | 0.000000 | LISA::ACTIVATION-PRIORITY
0.005 | 0.000 | 15,595,424 | 86,000 | 0.000000 | LISA::CLASS-MATCHES-P
0.004 | 0.002 | 12,975,408 | 111,600 | 0.000000 | LISA::FIND-INSTANCE-OF-FACT
0.004 | 0.000 | 3,736,176 | 24,403 | 0.000000 | LISA:INFERENCE-ENGINE
0.002 | 0.000 | 2,479,616 | 400 | 0.000006 | LISA::MAKE-RESET-TOKEN
0.002 | 0.000 | 1,114,096 | 7,400 | 0.000000 | LISA::CLEAR-MEMORIES
0.002 | 0.000 | 2,686,768 | 25,600 | 0.000000 | (SETF LISA:SLOT-VALUE-OF-INSTANCE)
0.001 | 0.000 | 2,235,856 | 13,500 | 0.000000 | LISA::MAKE-ACTIVATION
0.001 | 0.006 | 23,787,456 | 468,300 | 0.000000 | LISA::NODE1-TEST
0.001 | 0.000 | 1,376,432 | 10,100 | 0.000000 | LISA::TOKEN-MAKE-FACT-LIST
0.001 | 0.000 | 3,931,568 | 14,300 | 0.000000 | LISA::TOKEN-INCREMENT-NOT-COUNTER
0.001 | 0.000 | 3,800,384 | 18,900 | 0.000000 | LISA::ELIGIBLE-P
0.001 | 0.000 | 1,834,784 | 11,600 | 0.000000 | LISA::NEXT-FACT-ID
0.001 | 0.000 | 5,635,408 | 25,600 | 0.000000 | LISA::INITIALIZE-SLOT-VALUE
0.001 | 0.000 | 851,760 | 24,403 | 0.000000 | LISA:CURRENT-ENGINE
0.001 | 0.000 | 8,584,304 | 62,700 | 0.000000 | LISA::LOGICAL-BLOCK-P
0.001 | 0.002 | 1,834,576 | 78,400 | 0.000000 | LISA:RULE-SALIENCE
0.001 | 0.002 | 3,997,200 | 100,000 | 0.000000 | LISA::ACTIVATION-RULE
0.001 | 0.000 | 0 | 10,001 | 0.000000 | LISA::FIND-META-OBJECT
0.000 | 0.000 | 1,179,360 | 15,900 | 0.000000 | LISA:IN-RULE-FIRING-P
0.000 | 0.000 | 0 | 3,100 | 0.000000 | LISA::CLEAR-ACTIVATION-BINDINGS
...Note that LISA::TOKEN-PUSH-FACT was typically on the stack top, which makes sense given its importance. However, prior to performance tuning TOKEN-PUSH-FACT was consuming at least 2.5 seconds of CPU time on the MaB problem. After examining the function, the culprit was determined to be VECTOR-PUSH-EXTEND, as the TOKEN class's fact vector was not provided a size hint. Once that was addressed, and a slight change to TOKEN-PUSH-FACT written, a substantial improvement was realized.
NB: After a second performance tune and run, LISA::REPLICATE-TOKEN is now at the stack top. More detailed tuning is in store for the future. Additional performance analyses should be attempted with more sophisticated knowledge bases, as time progresses.
1: "Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem" Charles L. Forgy, Artificial Intelligence 19(1982), 17-37.
2: "Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp" Peter Norvig, (1991).