Lisp for Robots

[Henry G. Baker]

[hbaker: sorry about this long posting, but it is relevant to the
discussions we were having before.]

[From isr.com home page:]

Introduction

We presented a paper, L - A Common Lisp for Embedded Systems, about
the details of our new Common Lisp based development environment. We
will be selling L as a development environment for our robots as well
as an environment or stand alone embedded systems.

Reference

For the full paper text see: R. A. Brooks and C. Rosenberg, "L - A
Common Lisp for Embedded Systems", Lisp Users and Vendors Conference,
sec. 2.4a, 1995.

Extended Abstract

Abstract

A system has been developed which allows for the use of Common Lisp in
real time embedded control systems. The backbone of this system is a
language called "L". L is a downwardly compatible subset of Common
Lisp with multi-processing extensions. It is ideal for use in embedded
systems with small computers. The system has a minimal memory
footprint and can run on small processors. L contains both a runtime
environment and an interpreter which runs on the target system and a
cross compiler which runs on the host system. Making use of Common
Lisp's macro facilities, a special purpose language has been
constructed on top of L, called MARS - multiple agency reactive
system. This language is uniquely tailored for real time control
applications. It allows for the spawning of many small processes which
communicate to one another via a message passing paradigm. A graphical
user interface debugging tool was also developed which allows real
time monitoring and modification of values of variables on the target
system by the host system. Underlying this system is an efficient real
time operating system, called Venus. The operating system is written
in "C" for portability. The interface between "L" code and the
hardware takes place via operating system calls. L accesses the "C"
operating system calls via its foreign function interface. The first
application for this system has been the programming and control of
autonomous mobile robots. These robotic systems must process and react
to their sensor system in real time.

Introduction

This development effort was motivated by IS Robotics main business,
the manufacture and programming of small autonomous robots for real
world tasks. These robots have relatively small processors, 16 MHz
68020's with 1 megabyte of RAM. Development for these systems is
performed on a host computer and code is then installed on the target
system. IS Robotics uses the behavior control paradigm to program its
robots. In this paradigm the control of the robot is broken up into
many small parallel processes each of which operates on some sensor
data and can control actuators on the robot. To implement these
control systems we looked to the power of Common Lisp. We wanted a
system which allow us to dynamically redefine functions, test new code
interactively, start and kill processes, and easily create extensions
to the language and tools which would reduce development time. To
realize these goals we created a new system composed of a dialect of
Common Lisp (which we call L), a set of language extensions specific
to real time control, and a special operating system.

L

L is a language which is a downwardly compatible subset of Common Lisp
with multi-processing extensions. The L system consists of a run time
environment with an interpreter which runs on the target system and a
cross compiler which runs on the host system. All code development and
debugging can be carried out on standard workstations will full
programming environments. The code can then be downloaded and
dynamically linked onto a running target system. L contains all of the
main functionality of Common Lisp, this includes: multiple values,
strings, characters, arrays, a simplified (but compatible) package
system, all the "ordinary" aspects of format, backquote and comma,
setf, etc., full Common Lisp lambda lists including optionals and
keyword arguments, macros, an inspector, a debugger, defstruct
(integrated with the inspector), block, catch, and throw, etc., full
dynamic closures, a full lexical interpreter, floating point, fast
garbage collection.

The cross compiler developed is written in Common Lisp and has a
flexible backend which can easily be retargetted for different
processors. Currently, the system generates code for a 68020
processor. The run time environment load image is less than 160K
bytes, not including the cross compiler which executes on the host
system.

The user can access the interpreter front end via a terminal interface
on the host computer. This allows the user to experiment and define
functions on the fly and observe the effects of code in the actual run
time environment before going through a compilation cycle.

The L system utilizes a simple stop and copy garbage collector. The
design strategy was too keep it simple and fast so that it runs
unnoticeably in small applications with small heaps. The structure of
L's implementation is such that multiple independent heaps can be
maintained within a single address space, sharing all the code and
data segments of Lisp proper. In this way super-critical portions of a
system can be placed in heap where no consing is occurring, and hence
there is no possibility that they will be blocked by garbage
collection.

The multi-processing extensions of L allow a Lisp function to be
spawned as a process, which is run at regularly scheduled intervals.
The multi-processing system utilizes a pre-emptive scheduler which
allows many parallel processes to run in a single lisp heap. Each
process executes with its own stack. The standard multi-processing
model supports processes which are either pre-empted or can suspend
their execution and reschedule their next execution time. The
exception are what have been deemed "lightweight" processes. These
processes are small processes which run until completion. These
processes execute using the system stack and do not retain state
between invocations. Utilizing this type of process greatly reduces
the overhead and memory associated with context switching and is
extremely useful for many applications.

The interface between the L runtime environment and the target
hardware system is via a foreign function interface. Currently this
foreign function interface allows L access to functions compiled with
a variant of the GNU C compiler. This interface allows the L system to
be extremely portable, a new target system need only support a handful
of basic C calls to support L.

MARS

The Multiple Agency Reactivity System, or MARS, is a language built on
top of L to simplify the process of programming multiple asynchronous
parallel processes. Since it is embedded in L, all of that subset of
Common Lisp is available for use anywhere within a program.

MARS provides a means of defining many asynchronous parallel processes
which run in a single heap. These processes can be grouped together
into constructs called assemblages which share a lexical environment
and some number of ports. Ports are bi-directional message passing
interfaces to other assemblages. A software connection between the
ports on two assemblages enables bi-directional communication. Each
connection contains a one deep buffer and a message arrival flag.
Assemblages and the connections between them can be dynamically
created and destroyed at run time. Great care was taken in the
implementation of MARS to make debugging easy. Everything is
dynamically linked so that new versions of subsystems can be
recompiled and reloaded onto an existing working system, without any
interruptions.

MARS also supports a graphical user interface on the host machine
which allows ports to be monitored and their values to be modified in
real time.

Venus

To implement these systems efficiently, a fast, compact real time
operating system was developed, named Venus. Venus is a mixture of
assembly language and C. It provides the low level interface to the
target system hardware necessary to support L. It has been designed to
be modular, so only the pieces of the system required can be loaded
into the system. It is also a dynamically linkable and modifiable
system. This allows the most basic parts of the operating system to be
changed in short order without rebuilding the entire system, as is the
case with many other operating systems. For our 68020 implementation,
the entire operating system occupies less than 64K bytes of memory.

Conclusion

Our goal was to create a development system which would allow us to
have all of the advantages of Common Lisp on a small embedded computer
system. The "L" language was developed to serve this purpose. It is a
highly efficient subset of Common Lisp with multi-processing
extensions and a cross compiler. It can run on the relatively small
processors often used in embedded systems. To improve programming
efficiency, a language, named MARS, was built on top of L. This
package greatly simplifies the creation and debugging of large numbers
of inter-communicating processes. IS Robotics is committed to the
continuing development and improvement of the L system. We firmly
believe L to be a superior solution for creating complex real time
embedded control systems.
  _________________________________________________________________


 web@isr.com