LISP Interpreter

Spring 2022 • CS 403

Language used: Python3

Part 1
Implementation
Part 2
Testing
Part 3
Compilation and Running Tests

Members

Name CWID Email Address Time Spent
Cara Cannarozzi 11970792 cacannarozzi@crimson.ua.edu 13 hours
Madeline Moore 11884126 mcmoore11@crimson.ua.edu 13 hours
Peter Zhang 11861641 pwzhang@crimson.ua.edu 10 hours

Implementation Task Distribution

Task Percentage of Task
Cara Cannarozzi Madeline Moore Peter Zhang
Research/Learning 33.33% 33.33% 33.33%
Design 33.33% 33.33% 33.33%
Implementation of Code 35.00% 35.00% 30.00%

Research/Learning

We took a group approach for the research required for this project. This involved meeting up as a group every Tuesday at the library. During these meetings, we discussed the goals of the project, the language to use, and how to implement each part of the interpreter (scanner, parser, and the interpreter. We popcorn read the Crafting Interpreters textbook in order to learn about the general grammar of languages (this is an agile team building exercise). This was a great opportunity to get to learn about interpreter concepts together as a group and stay on the same page. After we learned about the general grammar of languages through the implementation of JLox. We then learned about LISP, we played around with a Common Lisp by using Steel Bank Common Lisp (SBCL). This helped us understand some general Lisp concepts. Then we read through Kamin's Pascal Lisp to see the flavour of Lisp we will be implementing. After all of this was complete we could then begin to work on our own implementation of the Kamin's Lisp.

Design

Since this project has many parts that must work together, we had to make some selective design choices. Due to all group members' familiarity with python, that is the language we selected. We decided to use python's built-in operator library to implement the operators and define our own functions as needed. We whiteboarded different ideas for the implementation of the code and discussed as a group our plans for implementation of certain functionalities such as operators, types (number?, symbol?, list?, null?), replacing true and false with T and (), printing, and other built in names such as if, while, set, begin, cons, car, cdr, and how to implement function definition and calling. For the define functionality, we defined a class named Procedure that has the function's parameters, formula, and environment (implemented as a python dictionary) as its attributes. When a later Lisp command uses the predefined function, the class adds the parameters given to the list of environment dictionaries and evaluates the function.

Implementation of Code

To implement this code, we met as a group many times until the project was complete. One group member would broadcast their screen onto a TV in a group study room in Gorgas and the others would discuss specifically how to implement the design we came up with in the beginning stages of development. We changed which member would be broadcasting their screen and which members would be verbally describing how to implement the design. We worked collaboratively and efficiently to implement this program as a group using a style of trio programming that has been common throughout internships. This style of implementation worked well for us as we were able to communicate efficiently and clearly with each other throughout the process so our design could come to life.

Members

Name CWID Email Address Time Spent
Cara Cannarozzi 11970792 cacannarozzi@crimson.ua.edu 4 hours
Madeline Moore 11884126 mcmoore11@crimson.ua.edu 4 hours
Peter Zhang 11861641 pwzhang@crimson.ua.edu 8 hours

Testing Task Distribution

Task Percentage of Task
Cara Cannarozzi Madeline Moore Peter Zhang
Fix Tim Budd's C++ Kamin Lisp Interpreter 15.00% 15.00% 70.00%
Testing Script 5.00% 5.00% 90.00%
Test Cases 40.00% 40.00% 20.00%

Fix Tim Budd's C++ Kamin Lisp Interpreter

We wanted something to compare our test outputs to. Kamin references Tim Budd's C++ version of the Kamin interpreters here and the download for Tim Budd's code can be found here on the CMU AI repository. Since Tim Budd's C++ implementation was made in 1994 it did not work with a modern compiler, we had to manually update each file to compile. This involved renaming true and false, fixing imports, replacing gets with fgets, and other small changes. Once the program was able to compile, we used the program to aid our development and testing.

Testing Script

We used a bash script to help automate our tests. The bash script is named "tester.sh" and it is located in the main directory. It is hardcoded to specifically work with our project directory. We updated a 1994 C++ version of Kamin's Lisp Interpreter to work with a modern day C++ compiler. The testing script ask to run either a specified single test case or all of the test cases. It will then compile Kamin's Lisp Interpreter. Then the tester will then run the test case(s) on the C++ Kamin Interpreter and our own interpreter and compare the outputs. If the resulting outputs are the same then the test passes.

Below, to the right you can see the output of our tester when we ran it. To the left there is a list of our test cases. You can view each test case individually along with the output of our interpreter (the output is the same as Tim Budd's version of Kamin's Lisp Interpreter).

Test Cases

Choose the test case to view:

Requirements

This project has a few requirements. They are listed below.

  • Python3 - For running the interpreter
    • You can get Python3 from this link.
  • Bash - For running the tester
    • Bash typically comes with Linux and MacOS. If you are Windows you can install Cywgin in order to run bash scripts. You can find the installation page here.
  • C++ - For running the tester
    • MacOS comes with a C++ compiler (Apple Clang). If you are using Windows or Linux, any C++ compiler should work.

Interpreter Modes

This project was made using python3. The interpreter itself is like Python3 since it has two modes. It can either interpret Lisp code from the command line or from a file. The file mode uses argv to read in the name of the file to interpret.

Interpreting code from the command line

To run the interpreter (reading from command line), type the following into the command line while in the main directory:

$ python3 src/project1.py

Interpreting code from a file

To run the interpreter (reading a file), type the following into the command line while in the main directory:

$ python3 src/project1.py LISPFILE.lisp

Where LISPFILE.lisp is the name of the file you want to read.

Running the tester

The tester is a bash script that can be run from the command line. You can run the tester by typing the following into the command line while in the main directory:

$ bash tester.sh

Using the tester

Once you have ran the tester, it will prompt you for a test case to run. You can either type a specific test case number or type "ALL" to run all test cases. The tester will run run the case(s) and print if the interpreter passed or failed the test case(s).

Common Problems

These are some fixes for common problems.

  • If you are using a Windows machine, make sure the file line endings are LF and not CRLF. CRLF line endings will break the tester.