About This Assignment
ECS 140A Programming Languages
Winter 2019
Homework 3
• This assignment asks you to complete programming tasks using the GNU Common Lisp programming language.
• You are only allowed to use the subset of lisp that we have discussed in class. For example, using loop constructs or other built-in functions is not allowed. You will get no credit for a solution that uses these functions in your solution. Please use Piazza for any clarifications regarding this issue.
• To complete the assignment (i) download hw3-handout.zip from Canvas, (ii) modify the .lisp files in the hw3-handout directory as per the instructions in this document, and (iii) zip the hw3-handout directory into hw3-handout.zip and upload this zip file to Canvas by the due date.
Do not change the file names, create new files, or change the directory structure in hw3-handout.
• This assignment has to be worked on individually.
• We will be using the GNU CLISP implementation of Common Lisp, version 2.49, which
can be installed from https://clisp.sourceforge.io/.
Use the command clisp –version to verify that you have the correct version in-
stalled:
$ clisp –version
GNU CLISP 2.49
• CLISP 2.49 is also installed on all CSIF machines. For instance,
$ ssh
$ clisp –version
GNU CLISP 2.49
• Information about using CSIF computers, such as how to remotely login to CSIF computers from home and how to copy files to/from the CSIF computers using your personal computer, can be found at http://csifdocs.cs.ucdavis.edu/about-us/ csif-general-faq.
1
• Begin working on the homework early.
• Apart from the description in this document, look at the unit tests provided to under-
stand the requirements for the code you have to write.
We are using the lisp-unit test framework.1
You do NOT need to write new unit tests: code coverage is not going to be a factor in the grade for this assignment. However, you are encouraged to add new tests to understand and test your own code.
• Post questions on Piazza if you require any further clarifications. Use private posts if your question contains part of the solution to the homework.
General Tips
• When developing your program, you might find it easier to first test your functions interactively before using the test program. You might find trace, step, print functions useful in debugging your functions.
• The command clisp myFile.lisp runs the lisp interpreter on the file myFile.lisp.
• You can start clisp interactively using:
$ clisp
• To load function definitions from/run myFile.lisp in the current directory: [1]> (load “myFile.lisp”)
• To exit error mode, choose the command for ABORT (in this case, it’s :R3):
[1]> asjfkasf
ABORT :R3
[2]> :R3
[3]>
Abort main loop
• You can exit the interactive clisp interpreter using: [1]> (bye)
1https://github.com/OdonataResearchLLC/lisp-unit 2
1
•
mmm (10 points)
Complete the definition of the function min-mean-max in hw3-handout/mmm/mmm.lisp, which takes a list of numbers (with at least one element) and returns a list of length 3 that consists of the smallest number, the mean (reduced to the simplest fraction) of all numbers and the largest number.
> (min-mean-max ’(2 5 11 15 7 1 8))
(1 7 15)
> (min-mean-max ’(6 6 5 -4 3 2 1 1))
(-4 5/2 6)
Use the following commands to run the unit tests provided in hw3-handout/mmm/mmm test.lisp:
$ cd hw3-handout/mmm/
$ clisp mmm_test.lisp
qsort (10 points)
Complete the definition of the function pivot in hw3-handout/qsort/qsort.lisp, which takes a list l and a number n and splits it into two lists, one containing all the numbers in l less than n and the other containing all numbers in l greater than or equal to n. The function should preserve the relative order of elements inside the list.
> (pivot 3 ’(3 2 5 1 4)))
((2 1) (3 5 4))
> (pivot 3 nil))
(NIL NIL)
Completethedefinitionofthefunctionquicksortinhw3-handout/qsort/qsort.lisp, which sorts a list.
Review of the quicksort algorithm: First pick an element and call it the pivot. The head of the list is an easy option for pivot. Partition the rest of the list into two sublists, one with all the elements less than the pivot and the other with all the elements not less than the pivot. Recursively sort the sublists. Combine the two sublists and the pivot into a final sorted list.
•
2
•
•
3
•
3
•
•
•
•
> (quicksort ’(2 9 5 3 8))
(2 3 5 8 9)
Use the following commands to run the unit tests provided in hw3-handout/qsort/qsort test.lisp:
$ cd hw3-handout/qsort/
$ clisp qsort_test.lisp
match (15 points)
An assertion represents a fact in the form of a list. For instance, the following are three different assertions:
(this is an assertion)
(color apple red)
(supports table block1)
The set of assertions can be maintained in a database by representing them in a list.
For instance, the following list represents an assertion database containing the above assertions:
((this is an assertion) (color apple red) (supports table block1))
Patterns are like assertions, except that they may contain certain special atoms ? and !, which are not allowed in assertions. Two examples of patterns are:
(this ! assertion)
(color ? red)
Complete the definition of the function match in hw3-handout/match/match.lisp, which compares a pattern and an assertion.
When a pattern containing no special atoms is compared to an assertion, the two match only if they are exactly the same, with each corresponding position occupied by the same atom.
> (match ’(color apple red) ’(color apple red))
T
> (match ’(color apple red) ’(color apple green))
NIL
4
The special atom ? matches any single atom.
> (match ’(color apple ?) ’(color apple red))
T
> (match ’(color ? red) ’(color apple red))
T
> (match ’(color ? red) ’(color apple green))
NIL
In the last example, (color ? red) and (color apple green) do not match be- cause red and green do not match.
The special atom ! expands the capability of match by matching any one or more atoms.
> (match ’(! table !) ’(this table supports a block))
T
Here, the first ! symbol matches this, table matches table, and the second ! symbol matches supports a block.
> (match ’(this table !) ’(this table supports a block))
T
> (match ’(! brown) ’(green red brown yellow))
NIL
In the last example, the special symbol ! matches green red. However, the match fails because yellow occurs in the assertion after brown, whereas it does not occur in the assertion. However, the following example succeeds:
> (match ’(! brown) ’(green red brown brown))
T
In this example, ! matches the list (green red brown), whereas brown matches the last element.
• Use the following commands to run the unit tests provided in hw3-handout/match/match test.lisp:
$ cd hw3-handout/match/
$ clisp match_test.lisp
5
4
•
nfa (15 points)
A non-deterministic finite automaton (NFA) is defined by a set of states, symbols in an alphabet, and a transition function. A state is represented by an integer. A symbol is represented by a rune, i.e., a character. Given a state and a symbol, a transition function returns the set of states that the NFA can transition to after reading the given symbol. This set of next states could be empty.
A graphical representation of an NFA is shown below:
In this example, {0,1,2} are the set of states, {a,b} are the set of symbols, and the transition function is represented by labelled arrows between states.
– If the NFA is in state 0 and it reads the symbol a, then it can transition to either state 1 or to state 2.
– If the NFA is in state 0 and it reads the symbol b, then it can only transition to state 2.
– If the NFA is in state 1 and it reads the symbol b, then it can only transition to state 0.
– If the NFA is in state 1 and it reads the symbol a, it cannot make any transitions.
– If the NFA is in state 2 and it reads the symbol a or b, it cannot make any
transitions.
A given final state is said to be reachable from a given start state via a given input sequence of symbols if there exists a sequence of transitions such that if the NFA starts at the start state it would reach the final state after reading the entire sequence of input symbols.
In the example NFA above:
– The state 1 is reachable from the state 0 via the input sequence abababa.
– The state 1 is not reachable from the state 0 via the input sequence ababab. – The state 2 is reachable from state 0 via the input sequence abababa.
Complete the definition of the function reachable in hw3-handout/nfa/nfa.lisp, which returns true if a final state is reachable from the start state after reading an input sequence of symbols, and nil, otherwise.
•
•
•
•
6
•
5
•
•
•
The transition function for the NFA described above is represented by the expTransitions function in hw3-handout/nfa/nfa test.lisp.
> (reachable ’expTransitions 0 0 ’(A B))
T
> (reachable ’expTransitions 0 0 ’(A A))
nil
Use the following commands to run the unit tests provided in hw3-handout/nfa/nfa test.lisp:
$ cd hw3-handout/nfa/
$ clisp nfa_test.lisp
matrix (30 points)
Suppose we represent a matrix in LISP as a list of lists. For example, ((a b) (c d)) would represent a 2*2 matrix whose first row contains the elements a and b, and whose second row contains the elements c and d. You may assume that the matrices are well-formed, compatible, and not empty.
Complete the definition of the function matrix-add
in hw3-handout/matrix/matrix.lisp, which takes two matrices as input and outputs the sum of the two matrices.
> (matrix-add ’((1 2) (2 1)) ’((1 2) (3 4)))
((2 4) (5 5))
Complete the definition of the function matrix-multiply
in hw3-handout/matrix/matrix.lisp, which takes two matrices as input and mul- tiplies them and outputs the resultant. You may assume that the matrices are well- formed, compatible, and not empty.
> (matrix-multiply ((1 2) (2 1)) ’((3 1) (1 3)))
((5 7) (7 5))
Complete the definition of the function matrix-transpose
in hw3-handout/matrix/matrix.lisp, which takes a matrix as input, and outputs its transpose. You may assume that the matrix is well-formed, and not empty.
•
7
> (matrix-transpose ’((1 2 3) (4 5 6)))
((1 4) (2 5) (3 6))
• Use the following commands to run the unit tests provided in hw3-handout/matrix/matrix test.lisp:
$ cd hw3-handout/matrix/
$ clisp matrix_test.lisp
8