Lisp Assignment

 

(Prepared by Lei Tang)

Jan-18-2007

 

Lisp Resources:

 

Installing and setting up lisp:

Lisp in a box which combines the emacs editor with different compilers.

http://common-lisp.net/project/lispbox/

I would recommend Clisp as the compiler.

 

A simple video: http://www.unixuser.org/~euske/vnc2swf/slime.html

 

Books:

Peter Seibel¡¯s ¡°Practical Common lisp¡± (Online at http://www.gigamonkeys.com/book/)

Paul Graham¡¯s ¡°ANSI Common Lisp¡±

David S. Touretzky¡¯s ¡°Common Lisp: A Gentle Introduction to Symbolic Computation¡±

(Online at http://www.cs.cmu.edu/~dst/LispBook/)

 

Other resources:

Newsgroup: comp.lang.lisp can be accessed using news.asu.edu or Google groups, or several other other sites allow posting to and receiving emails from this usenet news group.

 

Lisp Wiki: www.cliki.net

 

Lisp hyperspec: http://www.lispworks.com/documentation/HyperSpec/Front/Contents.htm

 

Irc channel: #lisp

 

Besides you can always ask question on the lisp discussion forum on myasu, or email the TA Lei Tang (L.Tang@asu.edu) and ask him..

 

 

Submission guidelines

 

You have to submit both softcopies and hardcopies:

Softcopy is due on 11:59pm 02/06/2007 (Tuesday). Please submit the soft copy via myASU Assignment section (Keep in mind that you can only submit once).

Hardcopies will be collected in class the next day (02/07/2007, Wednesday)

 

    * The first line in the file should be your name and ASU-ID (please comment it).

    * Please make sure that the file of softcopy is in simple text format and not in document (Microsoft Word or some other document) format.

    * There should be no syntax errors in the program (like forgotten closing brackets, misplaced semicolon unmatched double quotes, etc. In other words, one can run the program without your presence.)

    * Please try to comment whatever code you have written for debugging purpose. The function execution calls like (find-most-frequent ¡°C:\\input.txt¡±) should all be commented.

    * Your program will be tested by an automatic script written in LISP.

 

 

Please also try to follow the stylistic guidelines given at

http://www.lisp.org/table/style.htm

 

 

1). Exponentiation
Write a recursive function two-to-the which takes a single non-negative integer parameter x and returns 2x. (This can be done in logarithmic time.)

 

2). List recursion
Write the following functions using recursion (You cannot use functions like last, nth, length, or nreverse; But car and cdr are fine in your function):
(last-element l) returns the last element of l;
(all-but-last l) returns all but the last element;
(middle l) returns the middle element, assuming an odd number of elements.

Don't use any numbers to implement middle.

 

(Optional) A definition of middle using cdr and all-but-last uses quadratic time and space; you can try to write a version (fast-middle l) without recursion that uses linear time and constant space (Google interview question J)

.

 

3.)  List processing
Write a function fringe that takes a list as argument and returns a list whose elements are all the atoms appearing in the original list or any of its sublists, arranged in left-to-right order. For example,

? (setf x (cons (list 1 2) (list 3 4)))

((1 2) 3 4)

? (fringe x)

(1 2 3 4)

? (fringe (list x x))

(1 2 3 4 1 2 3 4)

 

4.) Function as parameters

The mathematicians use the ¡°sigma notation¡± to express the summation of a series¡±. For example

(n=a, b)¡Æf(n) = f(a) + ¡­.. + f(b)

In lisp we can write a general procedure which does summation of series:

  (defun sum-series (term a next b)

      (if (> a b)

           0

           (+ (funcall term a)

                (sum-series term (funcall next a) next b))))

 

So now if we have to compute sum of cubes from 1 to 10:

 

(defun cube (x) (* x x x))

(sum-series #'cube 1 #'1+ 10)

 

An analogous procedure product-series can be written that returns the values of a function at points over a given range.

 

(defun product-series (term a next b)

      (if (> a b)

           1

           (* (funcall term a)

                (product-series term (funcall next a) next b))))

 

So now if we have to compute the value of pi/4 = (2/3) *(4/3)*(4/5)*(6/5)*(6/7)*(8/7)¡­

we can use the following function call:

 

(product-series (lambda (x) (if (= (mod x 2) 1)

                                                 (/  (1+ x)

                                                      (+ 2 x))

                                                 (/ (+ 2 x)

                                                     (1+ x))))

                     1.0

                     #¡¯1+

                    40)

 

Both sum and product are special cases of a more general notion called accumulate that combines a collection of terms, using some general accumulation function:

 

(accumulate combiner null-value term a next b)

 

Accumulate takes as arguments the same term and range specifications as sum and product, together with a combiner procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of preceding terms and a null-value that specifies what base values to use when the terms run out.

Write accumulate and show how sum and product can both be defined as simple calls to accumulate.

 

The related common lisp function which behaves similar to accumulate is ¡®reduce¡¯.

http://www.lispworks.com/documentation/HyperSpec/Body/f_reduce.htm

 

5.) I/O operation

Write a function, called find-most-frequent, that takes an input file name and return a list of words occurred most frequently in the file. You don¡¯t have to handle the capitalization (AI, ai, Ai, aI are considered as four different words).  You only need to consider words consisting of English letters. All the other symbols including digits are considered as separators of words.

 

Suppose the content of your input file is below:

Welcome to AI class¡¯s first Lisp project. You¡¯ll like AI and Lisp in the future.

 

(find-most-frequent ¡°input.txt¡±) should return

(AI Lisp)  or (¡°AI¡± ¡°Lisp¡±)

 

For I/O operation, please check the macro WITH-OPEN-FILE and other related functions.

For data structure, you might want to use hashtable.

 

(Optional): The above is a simplified Google interview question. You can think about solving the problem of finding the most frequent word in 1 billion documents in hard disk. Suppose you have only 1 machine with 128M memory and enough hard disk space. Please provide an efficient method. Describe it briefly (no code is required).

 

 

6). (Optional) Generating programs...! (This is related to Macro in Lisp)
Write a function, called wheres-waldo, that takes a lisp object (i.e., a data structure built from conses) as argument and returns a Lisp expression that extracts the symbol waldo from this object, if it is present. For example,

? (wheres-waldo '(ralph waldo emerson))

(FIRST (REST '(RALPH WALDO EMERSON)))

 

Note that if we evaluate this expression, we get waldo,

 

? (first (rest '(ralph waldo emerson)))

WALDO

? (eval (wheres-waldo '(ralph waldo emerson)))

WALDO

 

In general, (eval (wheres-waldo x)) should return waldo if waldo is

anywhere in x, and nil otherwise. Some more examples:

 

? (wheres-waldo '(emerson ralph waldo))

(FIRST (REST (REST '(EMERSON RALPH WALDO))))

? (wheres-waldo

   '(mentor (ralph waldo emerson) (henry david thoreau)))

(FIRST (REST (FIRST (REST

                     '(MENTOR (RALPH WALDO EMERSON)

                              (HENRY DAVID THOREAU))))))

? (wheres-waldo '(henry david thoreau))

NIL

 

 

Have Fun.

---------------------------------------------------------------------------------------------------------