Lisp代写 | ECS 140A Programming Languages

这个作业是用lisp完成快排算法
ECS 140A Programming Languages
About This Assignment
• 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 in this assignment if any of the problem solutions
use constructs or built-in functions not discussed in class. Please use Piazza
for any clarifications regarding this issue.
• To complete the assignment (i) download hw2-handout.zip from Canvas, (ii) modify
the .lisp files in the hw2-handout directory as per the instructions in this document,
and (iii) zip the hw2-handout directory into hw2-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
hw2-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 installed:
$ clisp –version
GNU CLISP 2.49
• CLISP 2.49 is also installed on all CSIF machines. For instance,
$ ssh @pc2.cs.ucdavis.edu

$ 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.
• Begin working on the homework early.
1
© Cindy Rubio Gonzalez 2020
This content is protected and may not be shared, uploaded, or distributed.
• Apart from the description in this document, look at the unit tests provided to understand 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.
• This content is protected and may not be shared, uploaded, or distributed.
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 Abort main loop

[2]> :R3
[3]>
• You can exit the interactive clisp interpreter using:
[1]> (bye)
1https://github.com/OdonataResearchLLC/lisp-unit
2
© Cindy Rubio Gonzalez 2020
This content is protected and may not be shared, uploaded, or distributed.
1 mmm (10 points)
• Complete the definition of the function min-mean-max in hw2-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
hw2-handout/mmm/mmm_test.lisp:
$ cd hw2-handout/mmm/
$ clisp mmm_test.lisp
2 qsort (10 points)
• Complete the definition of the function pivot in hw2-handout/qsort/qsort.lisp,
which takes a list xs and a number n and splits it into two lists, one containing all the
numbers in xs less than n and the other containing all numbers in xs 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)
• Complete the definition of the function quicksort in hw2-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.
> (quicksort ‘(2 9 5 3 8))
(2 3 5 8 9)
• Use the following commands to run the unit tests provided in
hw2-handout/qsort/qsort_test.lisp:
3
© Cindy Rubio Gonzalez 2020
This content is protected and may not be shared, uploaded, or distributed.
$ cd hw2-handout/qsort/
$ clisp qsort_test.lisp
3 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 hw2-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
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 because
red and green do not match.
4
© Cindy Rubio Gonzalez 2020
This content is protected and may not be shared, uploaded, or distributed.
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
hw2-handout/match/match_test.lisp:
$ cd hw2-handout/match/
$ clisp match_test.lisp
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:
0
1
2
b a
a
b
5
© Cindy Rubio Gonzalez 2020
This content is protected and may not be shared, uploaded, or distributed.
• 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 hw2-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.
The transition function for the NFA described above is represented by the
expTransitions function in hw2-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
hw2-handout/nfa/nfa_test.lisp:
$ cd hw2-handout/nfa/
$ clisp nfa_test.lisp
• You may need to use funcall or apply to call the transition function to get the next
states.
6
© Cindy Rubio Gonzalez 2020
This content is protected and may not be shared, uploaded, or distributed.
5 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 hw2-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 hw2-handout/matrix/matrix.lisp, which takes two matrices as input and multiplies them and outputs the resultant. You may assume that the matrices are wellformed, 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 hw2-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.
> (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
hw2-handout/matrix/matrix_test.lisp:
$ cd hw2-handout/matrix/
$ clisp matrix_test.lisp
7
© Cindy Rubio Gonzalez 2020
This content is protected and may not be shared, uploaded, or distributed.