Introduction to

Function layers of EusLisp.

• Purpose and Goal
  EusLisp is an integrated programming system for the research on intelligent robots based on Common Lisp and Object-Oriented programming. The principal subjects in the field of robotics research are sensory data processing, visual environment recognition, collision avoiding motion planning, and task planning. In either problem, three dimensional shape models of robots and environment play crucial roles. A motivation to the development of EusLisp was a demand for an extensible solid modeler that can easily be made use of from higher level symbolic processing system. Investigations into traditional solid modelers proved that the vital requirement for their implementation language was the list processing capability to represent and manage topology among model components. Numerical computation power was also important, but locality of geometric computation suggested the provision of vector/matrix functions as built-ins would greatly ease programming.

  Thus the primary decision to build a solid modeler in a Lisp equipped with a geometric computation package was obtained. Although a solid modeler provides facilities to define shapes of 3D objects, to simulate their behaviors, and to display them graphically, its applications are limited until it is incorporated in robot modules mentioned above. These modules also need to be tightly interconnected to achieve fully integrated robot systems. EusLisp sought for the framework of this integration in object-oriented programming (OOP). While OOP promotes modular programming, it facilitates incremental extension of existing functions by using inheritance of classes. In fact, components in the solid modeler, such as bodies, faces, and edges, can orderly be inplemented by extending one of the most basic class coordinates . These components may have further subclasses to provide individual functions for particular robot applications. Based upon these considerations, EusLisp has been developped as an object-oriented Lisp which implements an extensible solid modeler^[7]. Other features include intertask communication needed for the cooperative task coordination, graphics facilities on X-window for visual user interface, and foreign language interface to support mixed language programming. In the implementation of the language, two performance-effective techniques were invented in type discrimination and memory management ^[4,5,6] . The new type discrimination method guarantees constant-time discrimination between types in tree structured hiearchy without regard to the depth of trees. Heap memory is managed in Fibonacci buddy method, which improves memory efficiency without sacrificing runtime or garbage-collection performance.

• Object-Oriented Programming
  Unlike other Lisp-based object-oriented programming languages like CLOS ^[5] , EusLisp is a Lisp system built on the basis of object-orientation. In the former approach, Lisp is used as an implementation language for the object-oriented programming, and there is apparent distinction between system defined objects and user defined objects, since system data types do not have corresponding classes. On the other hand, every data structure in EusLisp except number is represented by an object, and there is no inherent difference between built-in data types, such as cons and symbols , and user defined classes. This implies that even the system built-in data types can be extended (inherited) by user-defined classes. Also, when a user defines his own class as a subclass of a built-in class, he can use built-in methods and functions for the new class, and the amount of description for a new program can be reduced. For example, you may extend the cons class to have extra field other than car and cdr to define queues, trees, stacks, etc. Even for these instances, built-in functions for built-in cons are also applicable without any loss of efficiency, since those functions recognize type hierarchy in a constant time. Thus, EusLisp makes all the system built-in facilities open to programmers in the form of extensible data types. This uniformity is also beneficial to the implementation of EusLisp, because, after defining a few kernel functions such as defclass, send , and instantiate , in the implementation language, most of house-keeping functions to access the internal structure of built-in data types can be coded in EusLisp itself. This has much improved the reliability and maintainability of EusLisp.
• Features
  • [object-oriented programming] EusLisp provides single-inheritance Object-Oriented programming. All data types except numbers are represented by objects whose behaviors are defined in their classes.
  • [Common Lisp] EusLisp follows the specifications of Common Lisp described in ^[4,5] as long as they are consistent with EusLisp's goal and object-orientation. See next subsection for incompatibilities.
  • [compiler] EusLisp's compiler can boost the execution 5 to 30 times as fast as the interpreted execution. The compiler keeps the same semantics as the interpreter.
  • [memory management] Fibonacci buddy method, which is memory efficient, GC efficient, and robust, is used for the memory management. EusLisp can run on machines with relatively modest amount of memory. Users are free from the optimization of page allocation for each type of data.
  • [geometric primitives] Since numbers are always represented as immediate data, no garbage is generated by numeric computation. A number of geometric functions for arbitrary-sized vectors and matrices are provided as built-in functions.
  • [geometric modeler] Solid models can be defined from primitive bodies using CSG set operations. Mass properties, interference checking, contact detection, and so on, are available.
  • [graphics] Hidden-line eliminated drawing and hidden-surface eliminated rendering are available. Postscript output compatible with idraw and PICT format graphics description for Macintosh can be generated.
  • [image processing] Edge based image processing facility is provided.
  • [manipulator model] 6 D.O.F.s robot manipulator can easily be modeled.
  • [Xwindow interface] Three levels of Xwindow interface, the Xlib foreign functions, the Xlib classes and the original XToolKit classes are provided.
  • [foreign-language interface] Functions written in C or other languages can be linked into EusLisp. Bidirectional call between EusLisp and other language are supported. Functions in libraries like LINPACK become available through this interface. Call-back functions in X toolkits can be defined in Lisp.
  • [unix binding] Most of unix system calls and unix library functions are assorted as Lisp functions. Signal handling and asynchronous I/O are also possible.
  • [multithread] multithread programming, which enables multiple contexts sharing global data, is available on Solaris 2 operating system. Multithread facilitates asynchronous programming and improves real-time response ^[6,7] . If EusLisp runs on multi-processor machines, it can utilize parallel processors' higher computating power.
• Compatibility with Common Lisp
  Common Lisp has become the well-documented and widely-available standard Lisp. Although EusLisp has introduced lots of Common Lisp features such as variable scoping rules, packages, sequences, generalized variables, blocks, structures, keyword parameters, etc., incompatibilities still remain. Here is a list of missing features:
  • multiple values: multiple-value-call,multiple-value-prog1, etc.
  • some of data types: complex number, character and deftype; bignum and ratio are incomplete.
  • some of special forms: progv, compiler-let,macrolet
  Following features are incomplete:
  • closure -- only valid for dynamic extent
  • declare,proclaim -- inline and ignore are unrecognized
• Why object oriented?
• Why Lisp?
• Revision History
  • [1986] The first version of EusLisp ran on Unix-System5/Ustation-E20. Fibonacci buddy memory management, simple compiler generating M68020 assembly code, and vector/matrix functions were tested.
  • [1987] The new fast type checking method is implemented. The foreign language interface and the SunView interface were incorporated.
  • [1988] The compiler was changed to generate C programs as intermediate code. Since the compiler became processor independent, EusLisp was ported on Ultrix/VAX8800 and on SunOS3.5/Sun3 and /Sun4 . IPC facility using socket streams was added. The solid modeler was implemented. Lots of Common Lisp features such as keyword parameters, labeled print format to handle recursive data objects, generic sequence functions, readtables, tagbody, go, flet, and labels special forms, etc., were added.
  • [1989] The Xlib interface was introduced. % read macro to read C-like mathematical expressions was made. manipulator class is defined.
  • [1990] The XView interface was written by M.Inaba. Ray tracer was written. Solid modeler was modified to keep CSG operation history. Asynchronous I/O was added.
  • [1991] The motion constraint program was written by H.Hirukawa. Ported to DEC station. Coordinates class changed to handle both 2D and 3D coordinate systems. CSG functions were enhanced to handle contacting objects. The package system became compatible with Common Lisp.
  • [1992] Face+ and face* for union and intersection of two coplanar faces were added. Image processing facility was added. The first completed reference manual was printed and delivered.
  • [1993] EusLisp was stable, since the author was put in the requisition in the research planning section of ETL.
  • [1994] Ported to Solaris 2. Multithread facilities are incorporated on Solaris-2. XToolKit is built. Multi robot simulator, MARS was written by Dr. Kuniyoshi. EusLisp organized session at RSJ 94, in Fukuoka.
  • [1995] The second version of the reference manual is published. Bignum and ratio types are added. Porting to Linux by Hara, to Windows, Windows95, and Windows-NT by Nakagaki.
• Future Plan
  
  • Incorporation of MPI (message passing interface) for the standard distributed computing
  • porting to 64bit architecture machines such as R8000, Ultra Sparc, Alpha
  • Faster Graphics on SGI with OpenGL and Mesa interface
  • Concurrent Parallel GC for non-stop operation
• About the author and the development team
  Author: Toshihiro Matsui (Electrotechnical Laboratory)
  EusLisp Hacking Team: Isao Hara(ETL), Hirofumi Nakagaki(KEPCO)
  Graphics Hacker: Kenji Konaka (Logic Design)
  Application Research: Hirohisa Hirukawa, Hiromu Onda (ETL), Masayuki Inaba, Satoshi Kagami, Kanehiro (University of Tokyo).
  Supporters and Users: ... many...