LISP Interpreter Design
Sat 14 May 2005 02:49:27 PM EDT

This LISP interpreter is programmed in Java. The interpreter runs in a 
read-eval-print mode.

- The interpreter is case-insensitive

- INPUT: Both the list and dot notations are supported for input. An expression 
  can also be in the mixed notation.

- OUTPUT: Output is in the list notation.  

- ALIST: On a function call, the new bindings are added to the front of 
  the current a-list: however, the current a-list reference is not 
  modified; a new reference to the prepended a-list is passed to the 
  function called. Bindings are always searched from the front. When the 
  call returns, since its a-list reference is never used again, all the 
  bindings that were added are eventually collected as garbage by the 
  Java Runtime Garbage Collector.

- ERROR HANDLING: If a parse error occurs (i.e. an error in the read 
  mode), the appropriate error message is output and the interpreter 
  terminates. However, if the error occurs while in 'eval' mode, after 
  outputting the error message, the interpreter proceeds to the next 
  LISP expression as we know where the next expression starts in this 
  case. So post-poning some stuff to the 'eval' mode makes the 
  interpreter more robust.

- For the reason mentioned above, most of the checks, for example, for 
  invalid atoms, malformed conditional expressions, malformed functions 
  are done in 'eval' mode. Only proper parse errors are thrown in the 
  'read' mode.

- CONDITIONAL EXPRESSIONS: If none of the conditional expressions 
  evaluates to true, an error message is printed. Conditional 
  expressions should be strictly in the correct format i.e. a list of 
  pairs of s-expressions to be evaluated correctly.

- When a correctly written LISP expression is completely parsed, the 
  next token if on the same line is taken as part of the next 
  expression.

- DEFUN: Due to limited knowledge during parse time, defun expressions 
  are checked for limited correctness during evaluation time (i.e. when 
  the DEFUN expression is evaluated). The basic structure of 
  (DEFUN f (x y) z) is verified. The parameter list is checked for 
  validity. However, the body is not checked for correctness which gets 
  taken care of during function call time. Also, a defun within a defun 
  body is taken care of during evaluation time. All of these are in line 
  with what GNU CLISP 2.33 does.

- D-LIST: The d-list keeps growing as each new function definition is 
  added to it.

- Incorrect number of parameters (either few or many) is reported for 
  all functions (user-defined and primitive). 

- ATOMS:  As stated in the assignment hand-out, only integers and 
  identifiers may be atoms. An identifier starts with a letter of the 
  alphabet, and may be followed by one or more letters or digits. No 
  other characters are allowed. Integers may be signed or unsigned.


OPTIMIZATION:

- Instead of checking for the existence of a function definition in 
  'apply', this check could be done in 'eval' itself.  This will save 
  unnecessary computation that would have been done evaluating the 
  arguments of the function. Checking for illegal function names (like 
  lists) is also done in eval for the same reason.
