LUV '95

Lisp Users and Vendors Conference, August 14-17, 1995, Cambridge, MA


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.