Iliad

Rage—Goddess, sing the rage of Peleus' son Achilles,
murderous, doomed, that cost the Achaeans countless losses,
hurling down to the House of Death so many sturdy souls,
great fighters’ souls, but made their bodies carrion,
feasts for the dogs and birds,
and the will of Zeus was moving toward its end.
Begin, Muse, when the two first broke and clashed,
Agamemnon lord of men and brilliant Achilles.

—Homer. The Iliad.

Iliad, the Implementation of Logical Inference for Adaptive Devices is the infrastructure for the Poem language. Poem is a language developed as part of the ASCENS project which is particularly well-suited to the development of awareness mechanisms. Awareness mechanisms are combinations of models, reasoners and a sensor system used by an agent at runtime to "understand" its environment and determine what to do, e.g., by performing state estimation, learning value functions, or planning behaviors to reach goals.

The main components of Iliad are a blackboard system (Achilles), logical reasoners (Odysseus), reinforcement learning (Hector), and constraint solving and non-deterministic computing (Bold Dancer). Each of these systems is maintained in its own git submodule. Iliad itself provides a shared package that is useful when all components are required; it is also possible to load the different components individually.

A Short Historical Note

Strictly speaking this repository contains version 3 of the Iliad runtime which differs significantly from its predecessors. The first two versions of , Iliad were developed as unified packages containing a virtual machine written in Common Lisp that interpreted a bytecode tailored to the features provided by Poem, a compiler from Poem to the bytecode for the VM written in Poem, and interfaces to the Snark theorem prover. While this enabled us to support all features of the Poem language, we determined that the disadvantages of this solution outweighed its advantages.

It was clear from the beginning that we would need to integrate other forms of reasoning besides logical inference into the system. Since it is impractical to rewrite the reasoners used by Iliad, a binding between the VM and the reasoner has to be written. Furthermore, when trying to build efficient systems, it is generally impossible to use reasoners purely as black-box components; instead it is almost always necessary to connect the reasoning engine to the underlying domain model. This code has to use the extension facilities of the reasoner and must therefore typically be written in Common Lisp; to make it useful for the Poem language, "reverse" bindings to the Iliad runtime have to be written as well. Writing these bindings correctly requires a deep understanding of the way in which partial continuations and continuation marks are used in the semantics of Poem (and the VM) to enable non-deterministic computations, otherwise subtle bugs can arise where the state of the reasoners and the state of the Poem program are no longer synchronized. In summary, the presence of the virtual machine added a lot of overhead for the programmer.

Therefore, this implementation uses a different strategy: it implements a subset of Poem as an internal domain-specific language on top of Common Lisp. To make this feasible, several features of the original Poem specification are not supported in Iliad:

• Non-deterministic computations are always executed using a depth-first chronological backtracking strategy; it is no longer possible to influence the control flow of a non-deterministic program using declarative search strategies.

• Currently only functions may contain non-deterministic code; non-deterministic constructs in method bodies are not correctly processed. It is, however, permissible to call non-deterministic functions from methods. This restriction is due to the manner in which the partial CPS transformation of the program is performed and will likely be removed in the future.

• The reasoning mechanism is only invoked for predicates wrapped inside a holds form, i.e., it is necessary to write (if (holds (p 0)) ...) instead of (if (p 0) ...) when validity of the (p 0) form should be decided by the reasoning mechanism instead of the programming language.

On the positive side, the implementation choices for the new Iliad version have led to several important improvements:

• The performance and memory consumption of Iliad has been significantly improved; it should now be possible to run Iliad also on resource-constrained devices such as the marXbot or smartphones. (Of course, some reasoners are not well suited for these environments.)

• Iliad now contains a blackboard system based on GBBOpen that greatly facilitates the integration and coordination of different reasoning mechanisms.

• Iliad now integrates a hierarchical reinforcement learning system based on Concurrent ALisp.

• Iliad supports specialized ontology reasoning using the PowerLoom reasoner.

• Iliad can now use the constraint-solving features of Screamer.

Installation and Execution

I currently provide neither precompiled packages nor scripts to run Iliad from the command line. Instead you have to download the sources and run Iliad from within your Lisp implementation of choice. Once the Iliad implementation becomes more stable I will make precompiled versions available.

Prerequisites

To run Iliad you need:

• One of the supported Lisp implementations (ABCL, CCL, CMUCL or SBCL, see below for the exact versions that I am using). Unless you have specific requirements, CCL or SBCL are recommended.
• ASDF 2. This is already be included in all supported Lisp implementations.
• Quicklisp (If you install the required packages by hand you could dispense with Quicklisp, but this is not something I would recommend.)

Installing from sources

You interact with Iliad from the read-eval-print loop of your Lisp system. To install Iliad from sources you have to perform the following steps.

• Download the sources of the latest Iliad release from the github page at https://github.com/hoelzl/Iliad/tags and unpack them in a location where ASDF can find them. (To simplify updating to newer versions it's even better if you checkout the master branch with git clone git://github.com/hoelzl/Iliad.git or one of the other methods given on the project page (https://github.com/hoelzl/Iliad). If you are feeling adventurous and want to get the latest features you can checkout the development branch instead.)

• Add the directories in which you have installed Iliad to ASDF's search path. you might have to add a form like

    (:source-registry
        (:tree (:home "Prog/Lisp/Hacking/"))
        (:tree (:home "Prog/Lisp/Imported-Projects/"))
        :inherit-configuration)

  to the file ~/.config/common-lisp/source-registry.conf on Linux/Unix/OSX, or to %HOME%\AppData\Local\common-lisp\config\source-registry.conf on Windows.

• Start your Lisp implementation and enter the following command:

  (asdf:load-system :iliad)

  This builds and loads all dependencies and the Iliad system.

Running the tests

To run the unit test suite for Odysseus, enter the commands

(in-package #:poem-user)
(asdf:load-system :iliad-tests)
(run-all-tests)

after loading the poem-tests system. Currently this runs the test suites for Screamer and Snark; in particular the tests for Snark will take a long time.

Running an example application

There is a simple example program available from here.

Supported Lisp Implementations

Iliad has been tested on the folowing implementations running on OSX:

• Clozure Common Lisp: Version 1.8-r15378M (DarwinX8664)
• CMU Common Lisp: 20c release-20c (20C Unicode)
• SBCL: 1.0.58
• Armed Bear Common Lisp: 12.1
• Allegro Common Lisp: 9.0 [Mac OS X (Intel)] (Jun 24, 2013 17:07)

It should be straightforward to port Iliad to other Lisp implementations or operating systems.

The following Lisp implementations don't seem to work:

• ECL: 12.7.1: Fails with an internal error while compiling Snark. TODO Check whether this has been fixed.

I haven't tried running Iliad on LispWorks, CLisp or any other Lisp implementation. Reports and bug fixes are always welcome.

The Workflow for the Poem Project

The work done, the feast laid out, they ate well
and no man’s hunger lacked a share of the banquet.

—Homer. The Iliad.

I am currently experimenting with the git-flow branching model for Poem. Please see the article "A successful Git branching model" for details. Furthermore, I try to write the commit messages loosely based on the Note About Git Commit Messages from tbaggery.

About this Document

No one should ever let such nonsense pass his lips,
no one with any skill in fit and proper speech—

—Homer. The Iliad.

All quotes from the Iliad are taken from the Penguin Classics edition translated by Robert Fagles. The HTML markup for the quotes uses the old-fashioned align="right" style, since CSS does currently not seem to work for the Github renderer.