CS 4303 Concept of Programming Languages

 

Purpose: Introduction to Functional Programming/LISP

 

This document provides instructions about using Lisp and examples of the design of Lisp functions.

 

TASK 1: Using the LISP interpreter

 

Download and install Racket software (https://racket-lang.org/download/) on your computer. You may explore the features of the software by trying to run simple lisp functions.

 

Some of the primitive functions allowed in Lisp are listed below. It would be a very good practice if you try these primitive functions on the system.  You may look at the other primitive functions supported by Lisp from any sources.

 

Please note that Racket, a dialect of Scheme, uses a naming practice that is dramatically different from that of other Lisp dialects, such as Common Lisp, and has a lot of features that are different from those from other Lisp software. Therefore, it is mandatory that you use Raket to write Lisp programs for this lab.

 

EXAMPLE:

 

 

                        LC-USER 1>(car '(a b c))     <in>

                        A                                                          <out>

                        LC-USER 2>(eq? 'x 'y)          <in>

                        #false                                                   <out> 

                        LC-USER 3>(let ((x '(a b c))) x)                   <in>

                        (list 'a 'b 'c)

 

To learn more about LISP programming, click on the following link:

 

http://cms.dt.uh.edu/Faculty/LinH/courses/CS4303/LISP/Lisp_sources.html

 

TASK 2: More practice:

In each of the following questions predict the results first and then use the Lisp interpreter to check your answers:

 

1. Write down the results of typing the following expressions in Lisp. (one line at a time).

 

(list 'big 'cat 'sat)

(cons 'the (list 'big 'cat 'sat))

(list 'all (list 'good 'people) 'should (list 'go 'ahead))

(cdr (car (cdr '(a (b c) d))))

(cdadr '(a (b c) d))

 

2. What will be the value of the last expression in each case?

  

a.         (let ((a '(u v w)))

               (let ((b (car (cdr a))))

                   (cons b a)))

 

b.         (local ((define A 'A))

               (local ((define B 'A))

                   (list A B 'B)))

 

3. What will be the result of each of the following sets of s-expressions typed in Lisp environment?

 

a.         (define (double x) (* 2 x))

            (double 2.3)

 

b.         (define (times-square x y) (* x y y))

            (times-square 4 3)

 

c.         (define (TIMES-CUBE X Y) (* X Y Y Y))

            (define (CUBE-TIMES X Y) (TIMES-CUBE Y X))

            (CUBE-TIMES 3 2)

 

Using the editor on Racket you may type the above functions in a Racker source file with ".rkt" extension. And then run the program in Racket IDE.

 

            CL-USER 1> (double 5)         ;running the function double

            10

 

4. Evaluate each of the following s-expressions:

 

a.         (number? '3)

b.         (integer? '(A B))

c.         (list? '(A B))

d.         (not (null? 'nil))

e.         (not (string? '(A B)))

f.          (eq? 'a 'a)

g.         (eq? '(A B) (list 'A 'B))

h.         (eq? 3 3.0)

i.          (equal? 3 3.0)

j.          (eq? 2.3 (+ 1.1 1.2))

k.         (and (integer? '3) (list? '(A B)))

 

5. Write an s-expression with car’s and cdr’s to access symbol C for each of the following lists.

 

a.         (A B C D E)

b.         ((A B C) (D E F))

c.         ((A B) (C D) (E F))

d.         (A (B C D) E F)

 

6. Write a function DOT-PRODUCT that takes two lists, each list has three numbers (elements), and produces the dot product of the vectors that they represent. For example,

 

            -> (DOT-PRODUCT '(1.2 2.0 -0.2) '(0.0 2.3 5.0))

            -> 3.6

 

      The answer for this question can be found in file DOT-PRODUCT.LSP in the same directory. The key for designing a lisp function is using recursion.

 

7. Write a function COUNT-NUMBER that counts the number of numbers that occur in a list. It should work like this:

 

            -> (COUNT-NUMBER '(A 2.3 B 5 4.53 C F))

            -> 3

 

     Hint: To determine whether s-expression is a number or not, use number? function. The following examples show how number? works:

 

-> (number? 5)

-> #true

-> (number? 5.5)

-> #true

-> (number? true)

->  #false

-> (number? ‘(A B))

-> #false

 

8. Write a function NEW-LIST that takes a number as its argument and constructs a list of that length containing all Ts. For example,

 

-> (new-list 5)

-> (T T T T T)

 

9. The Lisp function LENGTH counts the number of elements in the top level of a list. Write a function ALL-LENGTH of one argument that counts the number of atoms that occur in a list at all levels.  Thus, the following lists will have the corresponding ALL-LENGTHs.

 

            (A B C)                       => 3

            ((A (B C) D (E F))      => 6

            (NIL NIL (NIL NIL) NIL )    => 5

 

For each of questions 6-9, test cases are given in the instructions. Write the code for each function, and after each function bundle the test cases together as a block of check-expect invocations. These tests should illustrate the output you expect, and produce the actual output when running the program. You can write these test cases as executable code using the check-expect primitive. The following are examples:

 

;; Test Examples:

(check-expect (DOT-PRODUCT '(1.2 2.0 -0.2) '(0.0 2.3 5.0)) 3.6)

(check-expect (COUNT-NUMBER '(A 2.3 B 5 4.53 C F)) 3)

 

When running your program, if the test passes, Racket will display a message telling that all tests have passed. Otherwise, it will show which test cases do not pass.

 

Turn in your responses to these questions 6-9 in one single Racket source file (.rkt file) that include all test cases for each function in check-expect primitives. The Racket source file you submit must run on DrRacket as is. Submit the Racket source file on Canvas by the due date. Failure to include all the test cases given in this lab handout will cause loss of credits.