CMSC331 Programming Languages, Fall 2003 Homework 9 LISP out: 11/13, due: 11/20

This assignment gives you a chance to get your Lisp environment together and write some simple Lisp functions. Unless otherwise specified (or suggested by the examples) you can assume that reasonable arguments are given to your functions. In other words, you need not add code to check the arguments provided. Obsessive compulsives are free to do so, of course.

Getting ready

We'll use the clisp system, which has been installed on the OIT linux machines and is also available to download and install on your own computer. See our Lisp resources page for information on how to use clisp at UMBC and/or install it on your own computer. Read chapter 15 of our text and chapter two of Paul Graham's book Ansi Common Lisp, which is a brief introduction to Lisp and Lisp programming. Review the Lisp Primer by Colin Allen and Maneesh Dhagat. Keep handy this link to the online version of the Common Lisp standard specification -- Common Lisp the Language (sometimes referred to as CLtL).

Your assignment

(1) Constructing s-expressions

One thing you have to master in learning Lisp is how to construct s-expressions. In the following table, the first column lists some s-expressions we would like to construct. Complete the rest of the table by giving the simplest possible expression to build the s-expression. The expression in the second column should only use the CONS function and the one in the third should only use LIST. If it's not possible to construct an s-expression say so. You are not permitted to include a quoted list (like '(b c)) in giving you answer. You are permitted, of course to use quoted atoms and also to use nil (which need never be quoted). We've done the first row for you as an example. You should, of course, verify your work using the Lisp interpreter.

(2) De-constructing s-expressions

Another thing you have to master in learning Lisp is how to access elements in an s-expression. In the following table, the first column lists some s-expressions containing a single instance of the atom X. Assume that the variable S is bound to the s-expression in the first column. The second column should be an expression that when evaluated returns the atom X. You are only allowed to use the functions CAR and CDR and a single instance of the variable S. We've done the first row for you as an example. You should, of course, verify your work using the Lisp interpreter. In doing so, you can assign S a value using the setq function, e.g., do (setq s '(a b x)) whcn checking your answer for 2.1

(3) Depicting s-expressions

It's important to understand how s-expressions are represented in Lisp, but luckily, it's so simple that it's very easy. S-expressions are either atoms or lists. This problem focuses on the representation of lists and assumes that atoms (e.g., numbers and symbols) are simple objects to which we can point. Lists are made up of cons cell, which are data structure that hold two pointers (the car and the cdr). Every cons cells represents a list and the car points to the first element of the list and the cdr points to the list containing the remaining elements. Suppose we type the following to expressions into our Lisp interpreter

[1] > (setq foo (cons 'b (cons 'c nil)))
(b c)
[2] > (setq bar (cons 'a foo))
(a b c)

The standard way to depict the results is shown in the figure to the right. It shows the variables foo and bar pointing to s-expressions that are their values. The depiction makes it obvious that the two lists "share structure".

Draw a similar diagram to show the result of the following dialog with the LIsp interpreter.

[1] (setq x (cons 'a (cons 'b nil)))
...
[2] (setq y (cons x x))
...
[3] (setq z (list x (cdr x)))
...

(4) Temperature conversion

Write two conversion functions, f2c and c2f for converting values between Celsius and Fahrenheit. . Each function takes exactly one argument. The f2c function takes a number representing a temperature in Fahrenheit and returns a number representing the same temperature in Celsius. The c2f function takes a number representing a temperature in Celsius and returns a number representing the same temperature in Fahrenheit. This function should display the answer in the form of a decimal number. For example

[48]> (f2c 0)
-17.777777
[49]> (c2f 0)
32.0
[50]> (c2f 21)
69.799995
[51]> (f2c 90)
32.22223
[52]> (f2c 72)
22.222225
[53]> (f2c -40)
-40.0
[54]> (c2f 0)
32.0
[55]> (c2f 22)
71.6

When converting between temperatures in degrees Fahrenheit and degrees Celsius, it is useful to note that -40 degrees Fahrenheit equals -40 degrees Celsius. This observation makes for the following symmetric conversion formulae:

C = (F + 40) * 5/9 - 40
F = (C + 40) * 9/5 - 40

(5) Harmonic function

One of the standard examples for a recursive definition is the factorial function. This is also a standard example used in introducing Lisp:

(defun factorial (n)
  ;; Assumes that N is a positive integer and returns n!
  (if (= n 0) 
      1 
	  (* n (factorial (1- n)))))

harmonic(n) = 1 + 1/2 + 1/3 + 1/4 + ... 1/n

(6) Interleave

Define a recursive function for interleaving the elements of two lists that have the same length. For example:

	  
[59]> (interleave nil nil)
NIL
[60]> (interleave '(a b c) '(1 2 3))
(A 1 B 2 C 3)
[61]> (interleave '(1) '(a))
(1 A)

(7) Permp

Write a recursive function permp that takes to take two lists of atoms and returns T if one is a permutation of the other -- i.e., the two lists have the same elements but maybe in a different order. You can assume that both lists have the same number of elements.

[2]> (permp nil nil)
T
[3]> (permp '(1) '(1))
T
[4]> (permp '(a b c) '(b c a))
T
[5]> (permp '(a b c) '( c b d))
NIL

Notes: This function follows the lisp function naming tradition in that a predicate (a function whose return value is to be interpreted as a boolean) ends in the letter P. If you are stuck, try this. The empty list is a permutation of the empty list. If you are given two non-empty lists S1 and S2, then they are permutations if (i) the first element of S1 is an element of S2, and (ii) the rest of S1 is a permutation of the list S2 with S1's first element removed from it. Two functions you will find useful are MEMBER and REMOVE. The function REMOVE takes a thing and a list and returns a list formed by removing a top level element equal to the thing from it.

[1] (remove 'x '(a b x c d x e) :count 1)
(a b c d x e)

(8) SortedP

Write a recursive function SORTEDP that takes a list of numbers and returns T iff the numbers are in ascending order. For example,

[6]> (sortedp nil)
T
[7]> (sortedp '(1))
T
[8]> (sortedp '(2 1))
NIL
[9]> (sortedp '(1 2))
T
[10]> (sortedp '(1 2 3 4 6 8 100 201 201 202 202 2004))
T
NIL

Note: This one is easy too: The empty list is sorted. A list with one element is sorted. A list with more than one element is sorted iff it's first element is less than its second element and the list after the first element is sorted. You will want to use the <= comparison function for this one.

What to hand in

Put all of your Lisp code in a single file named hw9.lsp. Make sure it works correctly on the test file test.lsp. You must submit your code electronically via the submit system. You can submit your answers to problems 1-3 either electronically or in hardcopy. The deadline for electronic submission is midnight Thursday 20 November. Hardcopy must be submitted in class on Thursday 20 November.

Getting started with Lisp

CLisp is installed on the UMBC Unix machines and can be downloaded (free) and installed on your own computers (including windows systems). See our Lisp resources page for information on how to use clisp at UMBC and/or install it on your own computer.

Here are some basic things that you will need to know.

You can load a file of definitions into lisp with the load function. For example, if you have your function ins the file demo.lsp then you would do (load "demo.lsp"). This causes the Lisp interpreter to read and evaluate each s-expression found in the file.

[12:34pm] linuxserver1 113(lisp)=>clisp

  i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
  I I I I I I I      8     8   8           8     8     o  8    8
  I  \ `+' /  I      8         8           8     8        8    8
   \  `-+-'  /       8         8           8      ooooo   8oooo
    `-__|__-'        8         8           8           8  8
        |            8     o   8           8     o     8  8
  ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8


Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999

[1]> (load "demo.lisp")
;; Loading file demo.lisp ...
;; Loading of file demo.lisp is finished.
T
[2]>

If the Lisp interpreter encounters an error in evaluating an s-expression, it stops and enters a debugging loop. This is a separate read-eval-print loop from which you can examine the current state of the computation and, possibly, continue. For example, after loading demo.lisp, if we call (fib 3) we will encounter an error.

[2]> (fib 3)
*** - EVAL: variable M has no value
1. Break [3]>

1. Break [3]> n
2
1. Break [3]> help
Help   = this command list
Abort  = abort to the next recent input loop
Unwind = abort to the next recent input loop
Mode-1 = inspect all the stack elements
Mode-2 = inspect all the frames
Mode-3 = inspect only lexical frames
Mode-4 = inspect only EVAL and APPLY frames (default)
Mode-5 = inspect only APPLY frames
Where  = inspect this frame
Up     = go up one frame, inspect it
Top    = go to top frame, inspect it
Down   = go down one frame, inspect it
Bottom = go to bottom (most recent) frame, inspect it
Backtrace-1 = list all stack elements
Backtrace-2 = list all frames
Backtrace-3 = list all lexical frames
Backtrace-4 = list all EVAL and APPLY frames
Backtrace-5 = list all APPLY frames
Backtrace   = list stack in current mode
Break+ = set breakpoint in EVAL frame
Break- = disable breakpoint in EVAL frame
Redo   = re-evaluate form in EVAL frame
Return = leave EVAL frame, prescribing the return values
1. Break [3]> abort
[4]>

if you are new to lisp, you will probably just want to abort back to the top level most of the time. After fixing the problem in the fib definition by editing the file, it can be reloaded. This example shows that if the argument to load evals to a symbol (e.g. demo) then it is taken as a filename (again -- case is ignored) and the default extension .lsp is tried. The following example also shows the use of the trace function to turn on tracing for fib.

[4]> (load 'demo)
;; Loading file demo.lisp ...
;; Loading of file demo.lisp is finished.
T
[5]> (fib 3)
2
[6]> (trace fib)
;; Tracing function FIB.
(FIB)
[7]> (fib 4)
1. Trace: (FIB '4)
2. Trace: (FIB '3)
3. Trace: (FIB '2)
4. Trace: (FIB '1)
4. Trace: FIB ==> 1
4. Trace: (FIB '0)
4. Trace: FIB ==> 0
3. Trace: FIB ==> 1
3. Trace: (FIB '1)
3. Trace: FIB ==> 1
2. Trace: FIB ==> 2
2. Trace: (FIB '2)
3. Trace: (FIB '1)
3. Trace: FIB ==> 1
3. Trace: (FIB '0)
3. Trace: FIB ==> 0
2. Trace: FIB ==> 1
1. Trace: FIB ==> 3
3
[8]> (untrace fib)
(FIB)
[9]> (fib 12)
144
[10]> (fib 30)
*** - EVAL: User break
1. Break [11]> abort

[12]> (fib 15)
610
[13]> (fib 20)
6765
[14]> (fib 23)
28657
[15]> (fib 25)
75025