CSE3401.03, Section A, Fall 2005
Report 1 Exercises
Due: October 7
Be sure to read On Academic Honesty and Reports from the home page for
the course. Note: For this exercise, partnering is not permitted.
What you hand in:
- The first page of the report is a standard cover page.
- The body part of the report is a hardcopy of your answers in exercise order. For
each exercise for which you develop Lisp functions you submit the following:
A printout of your documented functions. Use one file per exercise
named exercise-n.lsp, where n corresponds to the exercise number. For an
example, look at the file exercise-N.lsp in the course directory. You must
use the command enscript to print the file.
- A printout of the output file exercise-N.test created by executing the file
exercise-N.lsp using the following command.
As an example, look at the
file exercise-N.test, in the course directory, which is created by executing the file
clisp exercise-N.lsp >! exercise-N.test
- Before the deadline, submit a directory called report1 that should contain one
*.lsp file and one *.test file for each exercise for which you wrote Lisp functions.
Use the following Prism command:
submit 3401 r1 report1
While you can develop your functions on your personal computer, be sure your file will
load correctly and all your functions execute properly on Prism.
Question 1. polynomial approximation
Trignometric and exponential functions can be approximated (over portions of their domains) by polynomials with rational coefficients. For example,
tan-1 x = x - 1/3x3 + 1/5x5 - 1/7x7 . . .
An approximation of this type can be compactly specificied by three lists of integers - the numerators and denominators of the rational coefficients, and the list of exponents. For example, the approximation for tan-1 x given above is specified by the lists
1 -1 1 -1 (numerators)
1 3 5 7 (denominators)
1 3 5 7 (exponents)
Your task in this exercise is to define a Common Lisp function poly in the form
poly(x nums denoms exps)
which returns an approximate value of the corresponding polynomial at x.
You are not to use non-functional features of Lisp such as explicit loops or assignments to variables. Useful functions you can use are the usual arithmetic functions, including EXPT (see p. 123 in Mueller & Page), LENGTH, MAPCAR, REDUCE, and MAKE-LIST. You can find the specifications of all of these using the index to the online edition of Common Lisp, The Language.
Demonstrate your implementation of poly on the following examples
Compare your results with expressions using the more accurate functions atan (= tan-1), cos and log built in to Common Lisp. (Common Lisp also has the constant pi built in.)
- approximation to tan-1(π/6) using the polynomial given above
- approximation to log(cos(-0.5)) using the polynomial
-x2/2 - x4/12 - x6/45 - 17x8/2520
Question 2: a functional approach to implementing a database interface
This exercise demonstrates how we can use functions instead of variables to store data, and generate access methods dynamically, hiding the details of a particular structure from the high-level programmer.
- Define two functions db1 and db2 which have no arguments but return two versions of a toy database in the form of lists of lists.
Db1 should return the data:
(((Seibel Peter) "Practical Common Lisp" (QA 76.73 L23 S45 2005))
((Graham Paul) "ANSI Common Lisp" (QA 76.73 C28 G69 1996)))
The function db2 should return the data:
(((Peter Seibel) "Practical Common Lisp" (2005))
((Paul Graham) "ANSI Common Lisp" (1996)))
Define two functions setup1 and setup2 each of which creates (using DEFUN) the appropriate functions db(),
lastName(book) and pubDate(book), with the specifications:
- the function db() returns either (db1) or (db2) depending in which setup function it is defined;
- the functions lastName(book) and pubDate(book) return, respectively, the last name of the author of the book, and the publication year of the book, where book is a component (as defined in Mueller & Page, p. 14) of db1 in the case of setup1, and a component of db2 in the case of setup2. (In db1, the publication year is the last item in the call-number, and in db2, the publication year is the last item of a database entry.)
Modify the setup functions so that they return the current value of (db). Demonstrate that the setup functions work as intended by showing that expressions such as
(MAPCAR (FUNCTION lastName) (db)))
return the correct answers regardless of which database has been selected by executing setup1 or setup2.
Question 3: IF's and COND's
- Rewrite the functions greater3 and match on pages 53-54 of the text, eliminating the IF's using COND's and/or conditional expressions. Keep the conditionals as simple as possible, by taking advantage of the fact that if the first test that succeeds in a COND has no following expression then the value returned is the just the value of the test. (Example:
(COND ((EQUAL X 0)) )
evaluates to T if X is 0 and NIL otherwise.)
Eliminate occurrences of car, cdr, etc. -- use first, rest, etc. instead.
- The text's solution for match calls first3, but the specification for first3 as given in the text doesn't achieve what match requires. If you leave first3 as written, then if the pattern doesn't have 3 components, match returns T although according to the specification on p. 52, it shouldn't. Fix your version of either match or first3 so that match works correctly.
- Demonstrate that match works by showing an example in which the list argument matches the pattern, and three examples in which it doesn't--one with a list of two components, one with a list of five, and one with a list of four components and a pattern of two components, where the pattern occurs in the list argument.
Question 4: Translating boolean expressions
Let infix boolean expressions be defined by the following BNF grammar:
infix boolean expression is
(unary operator infix boolean expression) or
unary operator is not
(infix boolean expression binary operator infix boolean expression) or
binary operator is and or or
Last Updated: September 23, 2005 (spelling error corrected)
- Write a function infix_to_prefix that translates an arbitrary
infix boolean expression into an equivalent lisp prefix boolean
expression. For example,
(infix_to_prefix '((NOT (EQL 3 2)) AND (NIL OR (NOT T)))) should return
(AND (NOT (EQL 3 2)) (OR NIL (NOT T))).
- Write a function eval_infix that evaluates an arbitrary
infix boolean expression and returns its value.
(eval_infix '((NOT (EQL 3 2)) AND (NIL OR (NOT T))))
should return NIL.
Note: Besides the built-in functions described in the text (Chapters 3-10), your solution can use other built-in functions such as COND or MEMBER, and you may wish to define additional functions to simplify your code.