ASSIGNMENT: LISP

Overview

The purpose of this assignment is for you to gain some experience designing and implementing LISP programs. This assignment explores only a few of the many interesting LISP features.

This assignment is broken into several parts. The first part is a fairly straightforward LISP warmup. The second part continues the warmup. The third part involves writing your own ver- sion of the standard LISP function every; the remaining parts will use your function. The fourth part illustrates the standard technique of car-cdr recursion. The remaining parts involve writing functions that rewrite LISP expressions. More specifically, these parts takes as input a LISP expression and produces as output another, possibly different LISP expression. The modified expression will be semantically equivalent to the original, but it will use if's rather than cond's.

N.B., You are restricted as to which LISP functions you are allowed to use for various parts of this assignment. See "Notes" for details.

Part 1: The Cross1 Functions Write the following three functions.

cross1-recursive (x y)
cross1-iterative (x y)
cross1-mapcar (x y)

If x or y is not a list, the function returns nil. Otherwise, each of these returns the list con- sisting of pairs, one pair for each element of x; each pair contains as its first element an ele- ment of x and as its second element the entire list y. The overall order of the list follows the order from x. For example,

(cross1-recursive '(1 2) '(a b c))
returns
((1 (a b c)) (2 (a b c)))

cross1-recursive is to be written recursively, cross1-iterative is to be written iteratively using either ‘go' or ‘do', and cross1-mapcar is to be written using ‘mapcar'.

Part 2: The Cross2 Functions Write the following three functions.

cross2-recursive (x y)
cross2-iterative (x y)
cross2-mapcar (x y)

If x or y is not a list, the function returns nil. Otherwise, each of these returns the usual 2-dimensional cross-product of x and y. The overall order of the list follows the order from x. For example,

(cross2-recursive '(1 2) '(a b c))
returns
((1 a) (1 b) (1 c) (2 a) (2 b) (2 c))

cross2-recursive is to be written recursively, cross2-iterative is to be written iteratively using either ‘go' or ‘do', and cross1-mapcar is to be written using ‘mapcar'.

If you want, cross2-recursive can use cross1-recursive, cross1-iterative can use cross1-iterative, and cross1-mapcar can use cross1-mapcar. However, doing so didn't simplify my solutions.

Hint: for cross2-mapcar, use the "apply-append trick" (see text). In fact, there's a nice one-line solution that uses the apply-append trick and lambda expressions, but don't fret about getting that solution; get something working first.

Part 3: The my-every Function

The LISP predicate every returns t or nil to indicate whether a given function holds for every ele- ment in a list. Examples:

Expression                              Returns
(every #'integerp '(2 4 8))            t
(every #'integerp '(2 nope 8))       nil

Evaluation of every stops early, and returns nil, if it finds an element for which the given function evaluates to nil.

Write your own version of every

my-every (fun q)

it behaves exactly as every using fun with argument list q. Assume that my-every is invoked with only one argument list and that fun can be evaluated on one argument. You'll need to use funcall. Write my-every recursively. Use no iteration or mapping functions!

Just FYI, LISP's every also allows functions with multiple arguments (just as mapcar does). Examples:

Expression                                 Returns
(every #'> '(1 2 3) '(0 0 2))             t
(every #'> '(1 2 3) '(0 4 2))             nil

That's beyond the scope of my-every.

Part 4: The flatp Function

A "flat" list is a list that contains no nested lists.

Write the function

flatp (x)

it returns t if x is flat and nil if x isn't flat. Assume x is a list. Examples:

Hint: use my-every.

Part 5: The lenLFL Function

Write the function

lenLFL (x)

it returns:

• if x is flat, the length of x
• if x isn't flat, the length of the longest flat list recursively within x.

That is, consider each element of x that is a list and recursively apply this definition.

See the examples in the table in Part 4.

Hint: use flatp; use car-cdr recursion to get inside nested lists. Use LISP's max function, which works with two or more integer arguments (but not on a list of integers).

Part 6: The legalcondp Function

This part considers what constitutes a "legal" cond. Our definition will be simpler than (and a subset of) what LISP allows. A legal cond has the form

(cond a1 a2 ... aN)
• N must be ≥ 1. Terminology:

• arm - an ai

• Each arm ai is a list with 1 or 2 elements. (LISP allows any non-empty list; we don't.) Terminology:

• conditional - ai's first element
• body - ai's second element

Thus, an arm consists of a conditional and, optionally, a body.

Write the function

legalcondp (x)

it returns t if all cond expressions that the s-expr x contains are legal; or it returns nil if x contains any illegal cond expression.

Examples:

Hint: use car-cdr recursion to get inside nested lists.

Part 7: The Rewrite Function

Write the function

rewrite (x)

x is an s-expr. If x is not a "legal" cond, rewrite returns nil. Otherwise, rewrite returns an expression in which each cond has been replaced by an equivalent sequence of nested if- then.

Examples:

Expression                                                                              Returns
(rewrite '(* 44 2))                                                        (* 44 2)
(rewrite '(cond (3 4) (t 5)))                                           (if 3 4 (if t 5))
(rewrite '(cond ((= 3 3) 11) (t 15)))                               (if (= 3 3) 11 (if t 15))
(rewrite '(cond ((= 3 4) 11) ((= 5 6) 12) (t 17)))             (if (= 3 4) 11 (if (= 5 6) 12 (if t 17)))
(rewrite '(list (cond ((= 8 8) 'y)) (cond ((= 8 7) 'no))))     (list (if (= 8 8) 'y) (if (= 8 7) 'no))

Note that each cond is rewritten to use only a sequence of nested if-then expressions. (They do not use any if-then-else expressions; that's for Part 9.) Reminders about evaluating a cond:

• If no conditional is found true, cond returns nil.

• If an arm's conditional evaluates to true and the arm's body is empty, the arm returns the value of the arm's conditional. We'll assume that the arm's conditional has no side effects, so that the same expression can be replicated as the "then" for the if (since an if requires a "then" part).

• Recall that LISP allows a body of a cond's arm to contain multiple s-expr. Each would be executed and the value of the last s-expr is what's returned. Having multiple s-expressions is useful only if the non-last s-expressions have side effects. This HW, as noted previ- ously, allows only one s-expression at most in each arm's body.

Examples illustrating cond evaluation:

return conditional's value

Part 8: The Check Function

The function

check (x)

x is an s-expr. If x is not a "legal" cond, check returns nil. Otherwise, check returns a list of three values. The second element is the result of evaluating expression x. The third element is the result of evaluating the result of (rewrite x). The first element is t or nil corresponding to whether or not the value of the second element is equal to that of the third element. Note that if your rewrite function (and check function!) is correct, the first element of each list that check returns will be "t". Assume that x contains no variables.

Part 9: The Rewrite-ite and Check-ite Functions

Write the function

rewrite-ite (x)

rewrite-ite (ite is short for "if-then-else") is the same as rewrite, except it uses an if-then- else in replacing the last part of a cond expression that

• has ≥ 2 arms
• and whose last arm's conditional is exactly the symbol t.

These examples use the same arguments as in the table in Part 7; a † indicates that the value in the Returns column differs from the corresponding value in that earlier table.

Also write the function

check-ite (x)

It's the analogue of check for rewrite-ite.

Notes

• The command to use Common LISP is "clisp -q". clisp is available on CSIF systems.

• Some editors provide specific support to simplify editing LISP functions, for example, emacs's LISP mode, vi's -l option, and nedit's and jot's parenthesis matching.

• Appendix A of LISPcraft summarizes LISP's built-in functions. Each function is explained briefly. You will find this a very useful reference as you write and debug your program.

• The test program "test.l" is provided in the "given" on the class webpage. It exercises the func- tions that you write; hence, there is no test data. When executing within LISP within a part directory, you need only type "(load "../test.l")". This file defines the test functions
test-cross1, test-cross2, etc.

Each of these functions exercises the corresponding functions that you are to write. For exam- ple, to test your cross1 functions simply type
(test-cross1)

In addition, the function test simply invokes each of the above test functions. These test func- tions use additional helper functions. For example,

(test-cross1-recursive)

tests only cross1-recursive. See the test file for additional helper functions. Do not use any of the test function names as a name of one of your functions. Note that each of these functions returns "t" when complete, so there will be an extra line of output.

• We're also providing a "batch mode" test script ("tester"), which you should find very helpful.

• "Correct" output will also be given. Your output must match the "correct" output. By "match", we mean match exactly character by character, including blanks, on each line; also, do not add or omit any blank lines. (For this program, since LISP is doing all the output, that shouldn't be hard.)

Be sure to read and follow relevant comments in the test program test.l.

In any case, it is up to you to verify the correctness of your output.

• You may define additional helper functions that your main functions use. Be sure, though, to name the main functions as specified since the test program uses those names.

• Coding restrictions.

See the LISP functions webpage under HW5 on the webpage. As noted there, use only PURE functions for all functions you write, except:
cross1-iterative, cross2-iterative: PURE, BASICITERATIVE, prog, return, setq cross1-mapcar, cross2-mapcar: PURE, MAPPING

(OK, I'll be explicit: Don't even think about using INDEFINITES for my-every!) Use no global variables.

• To define your own initial LISP environment, place an init.lsp file in the directory in which you execute clisp and run clisp via "clisp -q -i init.lsp". For example, you will probably want to put the command

(setq *print-case* :downcase) in that file.

• When developing your program, you might find it easier to test your functions first interactively before using the test program. You might also find trace feature (LISPcraft section 11.5) or print functions (including the format function) useful in debugging your functions.

• Your code's execution on CSIF must not be grossly inefficient: your code must complete all the provided tests in at most 10 seconds (which is very generous). If your code is taking longer, then you are likely doing much needless recomputing. Using "let" expressions will likely help you solve that problem.

• A few points to help the novice LISP programmer:

• Watch your use of "(", ")", """, and "'". Be sure to quote things that need to be quoted, e.g., the name of the file in load.

• To see how LISP reads in your function, use pretty printing. For example, (pprint (sym- bol-function ‘foo)) will print out the definition of function foo, using indentation to show nesting. This is useful to locate logically incorrect nesting due to, e.g., wrong parenthesiz- ing.

• If you cause an error, Common LISP places you into a mode in which debugging can be performed (LISPcraft section 11.2). To exit any level, except the top level, type ":q". To exit the top level, type "ˆD". See the class handout for an example.

• See the webpage for exact details of what to turn in, the provided source files, etc. As usual, you must develop this program in "part order": No credit will be given for one part if the previ- ous part is not entirely working.

Attachment:- Assignment.rar