Implementation details of the AutoLISP simulator in PLT-Scheme

Brief description of the core of the AutoLISP language

First of all, the AutoLISP language is a very much simplified LISP as there is no macro, no lexical scoping and no object-oriented interface. The language is dynamicaly scoped and is less strictly defined than a modern Scheme language which adheres to the R5RS specification.

Every variable is defined (they do not have to be defined explicitly) and the initial value of a variable is nil. nil has a special role in the language. It represents the empty list and the `false' value, furthermore it is an atom and a list at the same type. The other special symbol is t which represents the `true' value, however any non-nil value is true.

Most of the language constructs are the same as in LISP or Scheme languages. A list is denoted by a start and an end bracket. A list can represent data or a function. When a list is evaluated as a function call then the first expression in the list denotes the function and all further expressions in the list are arguments to the function. Every function has a return value, which is the result of the last evaluation. To define a new function defun should be used in the form of:

(defun name (arg1 arg2 ... / lv1 lv2 ...)
  expressions ...
)

where name is the name of the newly defined function, arg1 arg2 ... are the arguments of the function, the symbol `/' separates the arguments from local variables and lv1 lv2 ... are the local variables. The user defined functions can have only a fixed number of arguments or no arguments. There are no binding constructs like let, let* and letrec, local variables can only be defined in the function. The value of the local variables is initialised to nil and they shadow the definiton of any previously defined variable with the same name as the language uses dynamic scoping. To assign a value to a variable the variable does not have to be defined, simply the following expression can be used:

(setq variable value)

The following section describes how the AutoLISP language has been implemented using a macro translator of PLT-Scheme.

Syntax transformers in PLT-Scheme

Although it is a standard exercise while learning LISP languages to create a LISP interpreter in the LISP environment itself, by overriding the read-eval-print loop, here a slightly different approach has been used. PLT-Scheme provides some primitive syntax transformers that expand all expressions into the most basic form. For example, expression

(+ e 4)

is turned into the following:

(#%app (#%top . +) (#%top . e) (#%datum . 4))

This example shows that in PLT-Scheme it is enough to override the `#%app', `#%top' and `#%datum' syntax transformers to replace the evaluation process and in this way to simulate a new LISP-type language. The `#%app' transformer is used for functions (lists), the `#%top' transformer is used for identifiers to determine their current value and the `#%datum' transformer is used when the expression is not a pair and not an identifier.

Implementation of dynamic scoping

One of the crucial things in the implementation of the AutoLISP execution environment is to implement dynamic scoping in a lexically scoped language. Dynamic scoping has been implemented with a hash table using the `#%top' syntax transformer.

(define autolisp-atoms (make-hash-table 'equal))
(define (%%get v)
  (hash-table-get autolisp-atoms v (lambda () '#f))
)
(define (%%set! v e)
  (hash-table-put! autolisp-atoms v e)
)

In the hash table a list is assigned to each variable. If a variable is not defined, (not in the hash table), or the list that is assigned to the variable is empty then the current value of the variable is nil. If the variable is in the hash table then the current value of the variable is the car of the list that is assigned to the variable. When a variable is used in a function definition as an argument or local variable (the argument and local variable shadows a variable) then a new value is consed to the list. In this case the list behaves as a stack. The above described algorithm is implemented in the `#%top' syntax transformer.

(provide (rename top~ #%top))
(define-syntax top~
  (syntax-rules ()
    ((top~ . id)
     (let ((val (%%get 'id)))
       (if (and val (not (null? val)))
         (car val)
         'nil)))))

The hash table stores not only the variables, but the functions as well. This means that the execution of the functions should also be modified, as the value of a functions must come from the hash table and not from the original Scheme environment. The implementation of the #%app syntax transformer is the following:

(provide (rename app~ #%app))
(define-syntax (app~ stx)
  (syntax-case stx ()
    ((_ x ...)
     (with-syntax
       ((func (car (syntax-e #'(x ...)))))
       (syntax
         (if (%%get 'func)
           (#%app x ...)
           (error "error: unknown function:" 'func)))))))

Implementation of the base system

This section describes how the base functions of the AutoLISP execution environment is implemented. First of all some auxiliary functions are required. These functions handle the list assigned to a variable as a stack:

vpush!: pushes a new value on the list which belongs to a variable;
vpop!: pops a value from the list which belongs to a variable;
vset!: replaces the car value of the list which belongs to a variable.

(define-syntax vpush!
  (lambda (x)
    (syntax-case x ()
      ((_ v e)
       (syntax
         (let ((old (%%get 'v)))
           (if old
             (%%set! 'v (cons e old))
             (%%set! 'v (list e)))))))))

(define-syntax vpop!
  (lambda (x)
    (syntax-case x ()
      ((_ v)
       (syntax
         (let ((old (%%get 'v)))
           (if old
             (%%set! 'v (cdr old)))))))))

(define-syntax vset!
  (lambda (x)
    (syntax-case x ()
      ((_ v e)
       (syntax
         (let ((old (%%get 'v)))
           (if (and old (not (null? old)))
             (%%set! 'v (cons e (cdr old)))
             (%%set! 'v (list e)))))))))

One of the basic operations is to change the current value of a variable. In AutoLISP the setting of a variable can be performed by the setq function. setq is implemented as a macro. However the macro is recursive as in a setq expression several assignments can be performed. Implementation of setq:

(provide (rename setq~ setq))
(define-syntax setq~
  (letrec
    ((setq-i
      (lambda (x)
        (syntax-case x ()
          ((v)
           (error 'setq "pairs of values are required ~s" 
                  (syntax-e #'v)))
          ; if only one pair is given
          ((v e)
           (syntax
             (let 
               ((new e))
               (vset! v new)
               new)))
          ; if several pairs are given
          ((v1 e1 others ...)
           (with-syntax
               (((set1 ...) (setq-i (syntax (v1 e1))))
                ((set2 ...) (setq-i (syntax (others ...)))))
             (syntax (begin (set1 ...) (set2 ...)))))))))
    (lambda (x)
      (syntax-case x ()
        ((_ v ...)
         (setq-i (syntax (v ...))))))))

The other important and subtantially different aspect of AutoLISP compared to Scheme is the definition of functions. Functions are defined by the defun expression.

Lets consider the following simple example function

(defun add2 (a / b)
  (setq b 2)
  (+ b a)
)

that should expand into something like:

(begin
  (setq~ add2
    (lambda (temp1)
      (let ((a 'nil) (b 'nil))
        (vpush! a temp1)
        (vpush! b 'nil)
        (let ((temp2 (begin (setq b 2) (+ b a)))) 
          (vpop! b) 
          (vpop! a) 
          temp2))))
  add2)

This example shows that the functions are still lambda expressions in AutoLISP as in Scheme. Moreover it also shows how the dynamic scoping is implemented for user defined functions.

New values are pushed on the lists in the hash table for the arguments and nil is pushed on the lists in the hash table for the local variables.
The expressions inside the function are evaluated.
The result of the last evaluation is stored in a variable.
The variables are restored to the state that they have before the execution of the function and
finally the result of the last evaluation is returned.

The implementation of the defun macro is shown in the following. The interesting part of the macro is where the list after the name of the function is processed in such a way that arguments and local variables are separated.

(define-syntax defun
  (lambda (x)
    (syntax-case x ()
      ((_ n1 (args ...) e1 ...)
       (letrec
         ((vars-get (lambda (lst)
            (let loop ((lst lst))
              (cond
                ((null? lst) '())
                ((equal? (car lst) '/) (loop (cdr lst)))
                (else (cons (list (car lst) ''nil)
                            (loop (cdr lst))))))))
          (vl (vars-get (syntax-object->datum
                            (syntax (args ...)))))
          (locals-get (lambda (lst)
            (let loop ((lst lst))
              (cond
                ((null? lst) '())
                ((equal? (car lst) '/) (cdr lst))
                (else (loop (cdr lst)))))))
          (ll (locals-get (syntax-object->datum
                              (syntax (args ...)))))
          (args-get (lambda (lst)
            (let loop ((lst lst))
              (cond
                ((null? lst) '())
                ((equal? (car lst) '/) ())
                (else (cons (car lst) (loop (cdr lst))))))))
          (al (args-get (syntax-object->datum 
                            (syntax (args ...)))))
          (ag (map (lambda (x) (gensym)) al))
         )
         (with-syntax
           (((vll ...) vl)
            ((lb ...) (map (lambda (x) (list 'vpush! x ''nil))
                           ll))
            ((le ...) (map (lambda (x) (list 'vpop! x)) ll))
            (aa ag)
            ((ab ...) (map (lambda (x y) (list 'vpush! x y))
                           al ag))
            ((ae ...) (map (lambda (x)   (list 'vpop! x)) al))
            (res (gensym))
           )
           (syntax
             (begin
               (setq~ n1 (lambda aa 
                                 (let (vll ...)
                                   ab ... lb ... 
                                   (let ((res (begin e1 ...)))
                                     le ... ae ...
                                     res))))
               n1))))))))

Implementation of some special functions

Most of the functions in AutoLISP are very similar to the functions in Scheme, however the functions in AutoLISP are less restrictive. This causes the problem that a lot of functions have to be either reimplemented or new, complex macros must be created for them. For example the mapcar function is the same as the map function but mapcar can handle lists with different length. An example for the non-standard use of mapcar is shown in the following:

(mapcar '- '(5 5 5 5) '(1 2))    ->    (4 3)

This example would generate an error message in Scheme as the length of the lists is different.

To be able to handle this situation in the current implementation the above example should expand into the following form which can consider lists with different length:

(apply 
  (lambda (temp_a1 temp_a2)
    (let loop ((temp_v1 temp_a1) (temp_v2 temp_a2))
      (if (or (null? temp_v1) (null? temp_v2))
        (list)
        (cons (- (car temp_v1) (car temp_v2))
              (loop (cdr temp_v1) (cdr temp_v2))))))
  (list '(5 5 5 5) '(1 2)))

The actual implementation of the macro is omited for brevity.

Testing the AutoLISP execution environment

Besides implementing the execution environment a testing environment has also been developed. The testing environment tries to check the behaviour of different functions and the conformance of the implemented AutoLISP system to the AutoLISP system in an AutoCAD program.

At the moment (June 2007) the testing environment contains 387 tests.

Implementation of the CAD system

Obviously the implemented AutoLISP environment is only the base of the system as some very basic CAD functionality must also be implemented. In this case only basic drawing commands, for example drawing of a line, a circle or a text, is required.

The other important aspect of the created execution environment, that it does not require user input in the standard way, mouse or keyboard, as in the CAD system, but the input of the program is an XML file. This also means that simulator does not uses the graphical system or any library of AutoCAD. The input XML file contains the description of the geometry of the hall structure. This is an addition to the original hall pricing program as now the created environment must parse the XML file, create the appropriate data structures and then call the original functions.

Only a small set of commands have been implemented which are required for the pricing application. Some of the commands are fully implemented, some of them are implemented as "empty" commands. An empty command behaves like a normal command, accepts all possible options and input but does nothing. The implemented commands are the following:

Name of the AutoCAD command	Implementation level
layer	full
point	full
circle	full
line	full
pline	full
style	full
text	full
rectang	full
dimlinear	full
erase	full
chprop	full
block	empty
undo	empty
insert	empty
regen	empty
zoom	empty
pedit	empty
trim	partly

For further details or enquiries, please contact the author.