Lisp Assignment I (with some corrections)

 

                (Prepared by Surendra Singhi)

 

                        Getting started with Lisp

 

Q. Why Lisp and what lisp has got to do with AI?

 

Many of you must be wondering why do we have to learn one more language? How will learning lisp help us? Well, there are 3 main types of programming languages: C++ type, Lisp type, and Haskell type. As a computer engineer/scientist throughout your career you will be expected to learn and use many different programming languages. Knowing these 3 languages will make learning any other language a piece of cake, most of the programming languages are some mish-mash of these 3 languages, and so if you know these 3 then you will have most of the concepts in programming languages covered, only thing which you will need to learn is the syntax of the target language.

 

Lisp has been the traditional language used for AI programming, the reason for this is below:

(1)It is an interpreted language and requires very little effort to get started, it is easy to experiment with the program and makes it possible to write it incrementally (bottom-up programming).

(2)Provides lists and dictionaries as primitive data-structures, this greatly enhances the power of language. Easy to change and use different data-structures/algorithms, allows more experimentation.

(3)Functions are first class variables, this means that functions can be passed to other functions, and this allows easy conversion of mathematical formulas to lisp-code.

(4)Powerful macro facility which makes it easy to write programs writing other programs.

 

Lisp Resources:

 

Installing and setting up lisp: The Lisp in a Box project makes it easy:

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

 

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/)

Paul Graham’s “On Lisp” (advanced level) (http://www.paulgraham.com/onlisp.html)

 

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.

But before asking questions read: http://www.catb.org/~esr/faqs/smart-questions.html

 

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 (Surendra Singhi) and ask him..

 

 

Submission guidelines

 

Due on 8/31/2005 by 11:59pm.

 

You need to submit the soft copy of the assignment via myASU Assignments section.

 

    * The LISP file should be named {last name}-{first-name}.lisp  Please don't abbreviate your name.

    * Submit the file through Assignment section in myASU.

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

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

    * If you want to label portions of your code as solution to part one, part two, etc., or you want to write the problem statement in the lisp file (it is not needed, you can do it if you feel it is convenient for you), please make sure that they are all commented.

    * 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 (parse

“C:\\input.txt”) should all be commented.

    * Make sure your program executes in Allegro lisp (ideally it should execute in clisp too).

    * Your program will be tested by an automatic script.

 

 

Please also try to follow the stylistic guidelines given at

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

 

You can form groups of 2-3 and help each other in learning lisp, but each one of you need to submit their own copy of the assignment, and any it should be entirely your work. We make use sophisticated AI scripts to catch mal-practices, students found indulging in plagiarising, copying will be reported to the department and this can result in severe consequences.

 

1.) Fibonacci series is a series in which each number is a sum of the preceding two, except the first two numbers.

0, 1, 1, 2, 3, 5, 8, 13, 21

 

A recursive procedure for computing the nth Fibonacci numbers will be:

  (defun fib (n)

      (cond ((= n 0) 0)

                ((= n 1) 1)

                (t (+ (fib (- n 1))

                          (fib (- n 2))))))

 

But as you can clearly see this procedure is terribly inefficient because it does so much redundant computation. The number of steps required, grow exponentially with the input.

 

An efficient (without redundant computation) way to compute Fibonacci number, which makes use of tail-recursion so that the interpreter can easily translate a recursive procedure to an iterative one, is shown below:

 

 

(defun fib (n)

  (labels ((fib-iter (a b count)

                 (if  (= count 0)

                          b

                          (fib-iter (+ a b) a (- count 1)))))

    (fib-iter 1 0 n)))

 

The task is given a function ‘f ‘defined by f(n) =n if n < 3 and f(n) = 3*f(n-1) + 2*f(n-

2) + f(n-3) if n>=3. Write a procedure that computes f by means of a recursive process. Also write a procedure that computes f by means of an iterative (tail-recursive) procedure.

The recursive procedure should be named “func-rec” and the iterative procedure should be named “func-tail-rec”.

 

N.P. – The tail recursive function should not use loop, or any of the variants of do construct.

 

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

 

3.) The ‘defstruct’ macro allows us to create structures. A structure to define a point in Cartesian co-ordinate system would be:

           (defstruct point (:constructor make-point (x y)) x y)

and one to define a line segment would be

           (defstruct segment start end)

 

To create point ‘p’ we can use a procedure like

       (setf  p (make-point 3 4))

and to create segment

(make-segment  :start p :end (make-point 5 6))

 

Now a procedure to find the distance between points will be:

       (defun distance (p1 p2)

              (sqrt  (+ (square (- (point-x p1) (point-x p2)))

                            (square (- (point-y p1) (point-y p2))))))

 

Implement a structure representation for rectangles (named rectangle) and circles (named circle) in a plane. Also create a procedure to find the area and the perimeter of the rectangle (or circle). These procedures should be designed with suitable abstraction barriers so that they are general enough to work with either circle or rectangle.

The rectangle representation should take the top-left and the bottom-right points as the input coordinate points, and the circle representation should take the center and the radius as the inputs. Also, the constructors should not take keyword arguments.

 

It should be possible to use the perimeter and area procedures through the procedure calls shown below:

 

(perimeter rec1)……..

(area rec1)……..

(perimeter circ1)……..

(area circ1)……..

 

4.) Write a function “parse” which given an input file name opens the file and return(don’t forget to return) 3 values: number of code lines, number of comment lines and number of blanks.

The same line can have both code and comment.

And remember (print "he;ll") is not a comment.

 

Even, (print "he ;)
ll")

should not be counted as a comment line.
Also,

>1. What is the line " "? Is it blank because it is all blanks? Or is it code? What about a line with >just tab characters?

Blank.

>2. What is the line ";"? Is it a comment, even though there is no comment there? What about "; ", >a blank comment?

Comment.

>3. What is the line "   ; "? Is it code, a comment, or both?

Comment

The signature of the program should be:

    (defun parse (file-name) ( ….. ))

 

Some functions useful for reading and writing to a file can be found here:

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

Also, you should return the values, look at the accessor values:

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

 

5.)Tower of Hanoi problem

Ref: http://www.cut-the-knot.org/recurrence/hanoi.shtml

 

Your lisp program given an integer (the number of disks) should find out how many steps will it take to move all the disks from one peg to another.

 

The signature of the program should be:

    (defun tower-of-hanoi (n) ( ….. ))

 

 

6.)Magic Square problem

Ref: http://mathworld.wolfram.com/MagicSquare.html

 

Your lisp program given an odd integer should return a two dimensional array containing the magic square. You can use ‘Siamese method’ or any other method you wish.

 

The signature of the program should be:

    (defun magic-square (n) ( ….. ))

 

For example, (magic-square 3) should return

 

#2A((8 1 6) (3 5 7) (4 9 2))

 

Have Fun.

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