Project 3: Lisp

Note: Don't do this project if you're doing the Lisp interpreter team project.

Functional programming is an alternative programming paradigm, significantly different from the more familiar imperative or object-oriented paradigms that you have probably seen. Lisp is one of the oldest and most popular functional programming language. In this project you'll learn Lisp and then write a couple of programs.

Material for learning and using Lisp:

Texas A&M tutorial
This is the best on-line tutorial I could find; the first three chapters (``LISt Processing'', ``Defining LISP functions'', and ``Recursion and Iteration'') are the ones to look over (and just the ``Recursive definitions'' section of the last is important for this project).
Tulane tutorial
This tutorial is a bit weaker than the last one, but I provide a link just as an alternative.
Allegro Common Lisp
This Lisp interpreter is already installed on the Windows NT machines. Look in the Applications:Programming submenu of the Start menu.

This system is meant for much more complex programs than what we want to do. Once it opens, close all the windows except for the topmost menu bar, the empty editor window (initially labeled `untitled', and the interactive system (where the system will print some things out before finally giving you its prompt `>'.

The system I found most useful is to define functions in the editor window, compile using the right-arrow menu bar button, and then to test the program by trying to use the functions.

Here are some functions for you to define. For this project, turn in a single file containing definitions for all these functions.

Note: It's possible to force the imperative paradigm used in C, C++, Pascal, and many other languages onto Lisp. Try to avoid this. ``Real'' Lisp functions should not really use variables in the sense that they change values frequently, nor do they use iteration. Instead both of these are taken up by recursion. Your implementations of the following should reflect this functional paradigm.

  1. A function fib to compute the nth Fibonacci number (using the Fibonacci algorithm on page 102 in the textbook). After you define this function, you should be able to type `(fib 5)' to the interpreter, and it should print 5 as the value.
  2. A faster Fibonacci implementation called dyn-fib similar to the Dynamic-Fibonacci algorithm defined on page 103. (It won't be an exact translation - think about how to phrase it so that the Lisp definition is most convenient.) This should work exactly as fib.

    Probably you will actually want to define two functions, one function that works almost exactly as you want (but takes extra parameters or returns a list of several return values) and dyn-fib that simply translates the inputs and outputs to work with the function doing the real work. (Such a simple function defined simply to call another is called a wrapper function. It's very useful, especially when you want to use recursion (as you usually do in Lisp).)

  3. A function bracket-match that returns t if the brackets in the list match and nil otherwise. For example `(bracket-match '([ x [ 2 ] [ ] ])' returns t while `(bracket-match '(x [ [ y ])' returns nil.
  4. A function prefix-eval to evaluate prefix expressions. For example, if I type `(prefix-eval '(/ 9 - 7 4))' (see how I omitted the parentheses?), the function should return 3.

Go to the project index.