CSE 341 -- Programming Languages

Autumn 2003

Department of Computer Science and Engineering, University of Washington

Steve Tanimoto (instructor)

Assignment 2

Version 1.0 of October 2

Lisp Warmup

Due date and time: Part I: Friday, October 10, 2003 (12:30 -- beginning of class); Part II: Monday, October 13, 2003 (midnight).

Turn in this assignment in two parts: Part I as a hardcopy printout, and Part II using web-based turn-in.

Title: Introduction to Lisp.

Purposes: Learn to use Lisp syntax, built-in functions, how to define recursive functions, understand Lisp evaluation, and how to manipulate list structures.

Instructions: Read pages 2-73 in Symbols, Programs, Interaction. (You may purchase a copy at Rams Copy at 4144 University Way, N.E.

Part I

Do the following exercises:

A. pp.10-12 # 1a-f; #2a-d; You may use the built-in predicates (MACRO-FUNCTION 'sym) and (SPECIAL-FORM-P 'sym) to test whether a symbol names a macro or whether it names a special form.
B. p.16 # 1c, d; #2a, b, f; #3a-h
C. pp. 23-24 #2; #3.
D. Write a recursive function SUM-CUBES that takes a list of numbers and returns the sum of their cubes. For example, (SUM-CUBES '(2 3 4)) should return 99. Implement your function in Lisp and demonstrate it on this example and another of your own choosing.

Part II

In this part of the assignment, you will define a series of functions of increasing complexity, culminating in a facility that translates mathematical expressions from Lisp's own syntax to that of the mathematical typesetting language LaTeX.

There are four "steps" to this part of the assignment, each one taking you closer to the goal. This is a relatively long assignment, but much of the text on this page is tutorial in nature. Also, we have set a later turn-in deadline for this part than was originally given.

Step 1. Defining recursive functions. In list processing, to transpose means to interchange two elements of a list.

Write a function TRANSPOSE in Lisp that will take two arguments: a list and an integer, and will return a new version of the list in which a certain transposition has been performed. For example:

(transpose '(a b c d e) 2)  =>  (A B D C E)

Here, the 2 indicates that the tranposition involves the elements in position 2 (third element, since indexing starts at 0 in Lisp) and position 3. Next, make a variant of this function that does lots of transpositions. It should take a list and transpose the first and second elements, third and fourth elements, etc., returning the resulting list. If there is an odd number of elements, the last one is not moved. Here's an example:

(transpose-all '(a b c d e))  => (B A D C E)

Here there is an odd element, E, at the end that doesn't move. With an even number of elements, they would all trade places with a neighbor.

After that, create a doubly-recursive version of it called DEEP-TRANSPOSE-ALL that works on any and all sublists (at all levels) as well as the top-level elements. Here's an example. Note that a sublist serves as an element at the level of the expression it occurs in, and so it will trade places with another element (unless it is an "odd man out" like the element E in the previous example).

(deep-transpose-all '(a b (c d (e f) g) h)) =>
  (B A H (D C G (F E)))

Step 2. Now that we've got double recursion under our belts, let's apply it to the problem of converting ordinary Lisp syntax into something that looks (slightly) more like conventional mathematics. Here is a definition for a function called PREFIX-TO-INFIX and its helper, INFIX-SERIES. Your job is to create deep versions of them so that subexpressions will be handled, too. PREFIX-TO-INFIX takes a single argument, which is a Lisp expression involving +, *, -, or /, and any numbers or symbols that represent arguments to those operations. INFIX-SERIES takes two arguments: an operator like + or * and a list of arguments. Its job is to form a list in which there is a separate copy of the operator in front of each argument. It returns the new list. The deep versions must correctly handle sublists at any depth within the main expression. The examples here show how these functions should work.

(defun prefix-to-infix (exp)
  (if (member (first exp) '(+ *))
    (cons (second exp)(infix-series (first exp)(rest (rest exp))))
    exp) )

(defun infix-series (op args)
  (if (null args) nil
    (cons op (cons (first args)(infix-series op (rest args)))) ) )

;;; (prefix-to-infix '(+ 1 2 3 4))  => (1 + 2 + 3 + 4)

;;; (deep-prefix-to-infix '(+ 1 2 (* 3 4 5))) =>
;;;    (1 + 2 + (3 * 4 * 5))

Step 3: Working with strings. (See appendix explaining the importance of strings.) Two of Common Lisp's most important string processing functions are FORMAT and CONCATENATE. Each has its own idiosyncrasies. FORMAT is typically used to format and print information, but it can also be used to prepare strings in special ways, and it can even be used to concatenate two given strings. CONCATENATE can be used to build longer sequences (including strings) from shorter ones, and it is not limited to two arguments.

Here is a simple example of using FORMAT to prepare a string that includes the value of a Lisp arithmetic expression.

(format nil "Here is PI divided by 2: ~A. That's it." (/ pi 2))
;;; =>  "Here is PI divided by 2: 1.5707963267948966. That's it."

The first argument to FORMAT here indicates what output stream to use. NIL has a special significance here, telling FORMAT not to use any output stream. FORMAT returns the string as its value rather than printing it or writing it to, say, a file.

Here is an example of how we can use CONCATENATE to combine three strings

;;; (concatenate 'string "abc" "d" "efg")  => "abcdefg"

Because this looks a little awkward, having to always give the second argument STRING to tell CONCATENATE to produce a string, as opposed to a LIST, let's use our own simpler function CAT, defined as follows:

(defun cat (&rest args)
  (apply #'concatenate 'string args) )

We can use it as follows:

;;; (cat "abc" "d" "efg")  => "abcdefg"

Now let's apply strings with single recursion to do a simple kind of translation of a list into another expression. Here is a sample function that takes a list representing a set of objects and returns a string representing that set in a more traditional mathematical notation.

(defun lisp-to-set (lst)
  (if (null lst)
     "{}"
     (cat (format nil "{~A" (first lst))
          (lisp-to-set-help (rest lst)) ) ) )

(defun lisp-to-set-help (lst)
  (if (null lst) "}"
    (cat (format nil ",~A" (first lst))
         (lisp-to-set-help (rest lst)) ) ) )

;;; (lisp-to-set '(a b c)) => "{A,B,C}"

Your job in this step is to write a function LISP-TO-[LIST] that takes a list as an argument and returns a string in which each left parenthesis is represented by "[" and each right parenthesis by "]".

;;; (lisp-to-[list] '(this is a (((deep))) test)) =>
;;;   "[THIS IS A [[[DEEP]]] TEST]"

Step 4. Translating into another language.

Now we've licked the main ingredients for translation of nested expressions: doubly-recursive processing and conversion of lists to strings. Let's apply these techniques to a real-world task: translation of Lisp expressions (limited to certain arithmetic operations) into LaTeX source.

About LaTeX: You don't need to know much about LaTeX to do this. However, LaTeX ("Lamport's TeX") is a formatting system built on Donald Knuth's TeX system that is used by lots of computer scientists and mathematicians to format their technical papers.

A LaTeX source file consists mainly of ordinary text plus formatting commands. However, there are special facilities for specifying the formatting of mathematical expressions. Here is an example of a sentence that includes two mathematical expressions, in LaTeX.

"Let the variable $y$ represent the value of $2 x^3 + x^2 + 3x - 1$."

The first mathematical expression is $y$, and the formatting causes the y to be typeset in an italic font. The second formula is $2 x^3 + x^2 + 3x - 1$. In this formula, the numbers before the x's (the coefficients) get typeset in a normal font, the operators + and - get typeset with mathematical symbols, and the exponents are raised and typeset in a smaller font. If we wanted a multi-character exponent, we would put it within curly brackets: for example, $x^{n+1}$. The dollar signs are used to start and end "math mode."

There are many interesting formatting capabilities in LaTeX, but let's just consider three more: square root, fractions with bars, and special symbols. The LaTeX source for the law of Pythagoras is $c = \sqrt{a^2 + b^2}$. Here we see that the square-root sign is obtained by using the command \sqrt, and the argument to it is given within curly brackets.

To get a fraction with a horizontal fraction bar, we use an expression like this:

$r = \frac{c}{2 \pi}$.

This expression can be interpreted as "radius equals circumference divided by two times pi." Here the \frac command requires two arguments, each one surrounded by curly brackets. Note that \pi is a command that causes the Greek letter pi to be printed.

Here are some commands that produce special symbols or names in LaTeX:

LaTeX       Lisp
-----       ----
\log        LOG
\sin        SIN
\cos        COS
\pm         +-  (the "plus or minus" sign used
                 in the quadratic formula
                 and in expressing error intervals
                 in the sciences and engineering.
                 Note: this is not standard in Lisp)
\pi         PI
\,              (No real counterpart in Lisp -- " "?
                 In LaTeX it means put in some additional
                 white space, the width of the character ",").

Within LaTeX's math mode, extra spaces between symbols do not affect the output.

What to write: Write a main function named LISP-TO-LATEX that takes a single argument (an arithmetic expression in Lisp) and that returns a single value (a string). You should handle any valid Lisp expression made up of numbers, single-letter symbols (that we assume represent variables) and the following functions: +, -, *, /, SIN, COS, LOG, EXPT, SQRT, +- (which is not standard but we'll use to represent the "plus-or-minus" operator). The string that is returned should represent a mathematically equivalent formula, in LaTeX format. It should not contain the enclosing dollar signs that change into and out of math mode. The formula should all be on one line (no embedded newline characters. The expression may contain subexpressions, and those should all be translated correctly. You may assume that / is used as a binary operator, even though Lisp permits it to take fewer or more than two arguments. With + and *, you may assume they always take 2 or more arguments in the input expression. With -, assume it takes either one argument (unary minus) or two arguments (representing simple subtraction). Also, write any helping functions that you need. Comment every function you write either with regular comments preceded by semicolons or by giving a documentation string within each function.

Testing your output: To test your output, place it in a file that looks like this:

\documentclass{article}
\begin{document}
Here is my formula, in display-math mode:

$$c = \sqrt{a^2 + b^2}$$

\end{document}

The formula in this example has double dollar signs around it, which specify "display-math" mode. The formula is then typeset on a line all by itself, nicely centered.

After you have a file with these contents (where the formula is what your program produces), and assuming you have named your file "myfile.tex", you can typeset it on a Unix system with the commands

latex myfile.tex
dvips -o myfile.ps myfile.dvi

Then you can print out the file myfile.ps on a Postscript printer. You can also view it directly if you have Ghostview installed, or you can convert it to PDF with Adobe Acrobat (I just double-click on myfile.ps, since I have Acrobat installed.)

Test your translation function on the Lisp expression for the quadratic formula:

(/ (+- (- b) (sqrt (- (expt b 2)(* 4 a c)))) (* 2 a))

The corresponding output should look like:

"\\frac{{-B\\pm\\sqrt{B^2-4AC}}}{2A}"

Here, the backslash characters are doubled, because in Common Lisp, the backslash character is the normal escape character, and so to get an actual backslash character into a string, it has to be preceded by another backslash. To show the string without the extra backslashes and without the surrounding double quotes, we can print the string with PRINC, resulting in:

\frac{{-B\pm\sqrt{B^2-4AC}}}{2A}

However, your LISP-TO-LATEX function should return the string itself. It should NOT try to remove any of these "extra" backslashes.

Automatic Testing: We are planning to use an automatic testing procedure to help grade your assignment. We'll ask you to submit a file called a2.lsp that contains all of your function definitions for Part II. Submission will be via a Turn-in procedure to be described later. We plan to test your LISP-TO-LATEX function by calling it with a couple of different formulas and then using our own functions and scripts to translate your output string into a LaTeX source file and process it.

Additional Information

Some additional information relevant to this assignment is posted in an appendix.

Scoring

Scoring for this assignment: 25 points for Part I and 50 points for Part II. Total: 75 points.