CS 3323 Topics in Programming Languages

• Elementary Lisp Programming:
  • Lisp Assignment 1 Due January 29, 1999.
  • Lisp Assignment 2 Due February 5, 1999.
• Lisp Interpreter Project:
  • Overview
  • Scanner for Lisp. Due February 12, 1999.
  • Parser and translator for Lisp. Due February 24, 1999.
  • Simple initial evaluator of S-expressions. Due March 5, 1999.
  • Lisp interpreter with function definitions and SETQ's.
• C++ Assignments: C++ Assignment 1 Due April 12, 1999.
• Java Assignments: To be determined.

Source files:

• scanner.h
• parse.h
• lisp.h
• scanner.c
• parse.c
• lisp.c
• lispdev.c

% cc -o lispdev scanner.c parse.c lisp.c lispdev.c
 

% lispdev
T
-1
-1.000000
(PLUS 3 -1)
2.000000
(SETQ  ABC  (QUOTE  (A  B  C ) ) )
(A B C )
(SETQ  TWO  2)
2.000000
(SETQ  THREE  3)
3.000000
(PLUS  TWO  THREE)
5.000000
(CONS  TWO  ABC)
(2.000000 A B C )
(PLUS (TIMES 3 (PLUS 5 1)) (QUOTIENT (TIMES 12 3) (PLUS 7 5)))
21.000000
(CONS (CAR (QUOTE (A B C))) (CDR (QUOTE (A B C))))
(A B C )

But ....
MINUS seems to work with just one argument.
DEFUN doesn't seem to work at all, though it once did???
(I don't have time now to chase down the problem.)

(Code requested by:
From drewmarek@msn.com  Tue Oct  1 04:26:18 2002
Delivered-To: wagner@mail.cs.utsa.edu
X-Originating-IP: [128.252.165.212]
From: "Andrew Marek" 
To: wagner@cs.utsa.edu
Subject: LISP interpreter
Date: Tue, 01 Oct 2002 04:26:17 -0500
Mime-Version: 1.0
X-OriginalArrivalTime: 01 Oct 2002 09:26:17.0719 (UTC) FILETIME=[9876B870:01C2692C]

Hi Dr. Wagner,

My name is Andrew Marek and I am a Masters student at Washington University 
in St. Louis.  I am currently doing some work in Genetic Programming (GP) 
that uses GP to analyze and come up with interesting algorithms for 
processing images.  The problem wth GP is that the LISP algorithms it 
produces are often very complex and difficult to read and understand for 
humans (me).  To make my research easier and better, I wanted to find a LISP 
interpreter that I could use as a framework for taking the LISP sexpressions 
that are generated and put them in C form.

I am contacting you because I saw your class web site up on the web from 
1999 (a google search) and saw:

LISP Interpreter 2--Parser and Translator
                                                              Due February 
24, 1999

This project looks like it could be helpful to me in that it's framework 
(reading in a LISP sexpression, translating it to an internal linked list, 
and printing it out again) might be very helpful to me.  As I read in the 
LISP sexpression using your framework, I could save the sexpressions, 
numbers, functions, etc. in a representation that makes sense, namely C.  
And then I could just output this representation into some recognizable and 
readable form of C.

This is an example of a generation of a GP run and the sexpressions that are 
produced as denoted by Result: and ADF0:

Starting generation: 9
Starting evaluation number 250
Starting evaluation number 500
Starting evaluation number 750
Starting evaluation number 1000
Starting evaluation number 1250
Starting evaluation number 1500
Starting evaluation number 1750
Starting evaluation number 2000
Starting evaluation number 2250
Starting evaluation number 2500
Starting evaluation number 2750
Starting evaluation number 3000
Starting evaluation number 3250
Starting evaluation number 3500
Starting evaluation number 3750
Starting evaluation number 4000
0.230875 CPU seconds per eval.
                   Generation 9
Hits: Max=175, Median=61, Avg=56.5097, Min=0
Standardized Fitness: Best=0.583333, Median=0.854762, Avg=0.865453, Worst=1
0.416667 raw, 0.583333 std, 175 hits:

Result: (Iterate-Down r66 (- desired-x (atan2 desired-x (- desired-x 
desired-x))) (* RAWS (if-le MEDIAN (if-le (set-e (set-c (/ MEDCORS 
image-max-y))) (atan2 (set-e (set-b GRAD)) (prog2 (sin MEDIANS) (+ MORSLASH 
iter2-a))) (sqr MEDIAN) (set-b (atan (set-a y)))) (if-le MEDCORS (set-b (- 
(prog2 GRADS x) image-max-y)) (+ x (if-le MEDCORS x (set-c read-c) (set-a 
MEDIAN))) read-b) image-max-y)))

ADF0: (Iterate-Down r83 (if-le desired-x desired-x (/ desired-x desired-x) 
desired-x) MEDCOR)

Raw Fitness: Best=0.416667, Median=0.145238, Avg=0.134547, Worst=0
MaximumDepth: Max=22, Median=8, Avg=8.2005, Min=3
Structural Complexity: Max=635, Median=58, Avg=57.453, Min=10

This is only an example, and the results can get much more complex.   More 
complexity just makes things tougher to understand, so it would be great if 
you could offer some help.  I'm hoping that you may have a copy of the 
interpreter that you have used as a model for your students for this class, 
and possibly some guidelines for its use.

If you don't want to give out your code to a stranger I understand.  I am 
just looking for a shortcut that would help me a great deal with my 
research.

Sincerely,
Andrew