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:

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

  1. approximation to tan-1(π/6) using the polynomial given above
  2. approximation to log(cos(-0.5)) using the polynomial
    -x2/2 - x4/12 - x6/45 - 17x8/2520
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.)

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.
  1. 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)))
    
  2. Define two functions setup1 and setup2 each of which creates (using DEFUN) the appropriate functions db(), lastName(book) and pubDate(book), with the specifications:

  3. 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

  1. 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.

  2. 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.

  3. 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
(infix boolean expression     binary operator     infix boolean expression)     or
lisp expression

unary operator     is     not

binary operator     is     and     or     or

  1. 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))).
  2. Write a function eval_infix that evaluates an arbitrary infix boolean expression and returns its value. For example,
    (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.

Last Updated: September 23, 2005 (spelling error corrected)