About This Assignment
ECS 140A Programming Languages
Winter 2021
Homework 3
• This assignment asks you to complete programming tasks using the Go programming language and the GNU Common Lisp programming language.
• You are only allowed to use the subset of Go and Lisp that we have dis- cussed in class. No credit will be given in this assignment if any of the problem solutions use material not discussed in class. Please use Piazza for any clarifications regarding this issue.
• To complete the assignment (i) download hw3-handout.zip from Canvas, (ii) modify the members.txt, .go and .lisp files in the hw3-handout directory as per the instruc- tions 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 of hw3-handout.
• This assignment can be worked on in a group of at most 4.
• List all the names and email addresses of all members of the group in the members.txt
file in the hw3-handout directory, one per line in the format name
If you are working individually, then only add your name and email to members.txt.
• Refer to Homework 0 for instructions on installing the correct versions of the pro- gramming language as well as using CSIF computers.
• 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.
• Post questions on Piazza if you require any further clarifications. Use private posts if your question contains part of the solution to the homework.
• Keep your homework solution after you submit it. You may need to use it for later assignments.
1
© Aditya Thakur 2021
This content is protected and may not be shared, uploaded, or distributed.
1 nfa (15 points)
For this part of the assignment, you only need to modify hw3-handout/nfa/nfa.lisp.
• 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:
1
a
0a2 b
• 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.
2
© Aditya Thakur 2021
This content is protected and may not be shared, uploaded, or distributed.
b
2
•
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.
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
You may need to use funcall or apply to call the transition function to get the next states.
matrix (15 points)
•
•
For this part of the assignment, you only need to modify hw3-handout/matrix/matrix.lisp.
• A 1 × m matrix of integers can be represented as a list in LISP.
For example, the 1 × 3 matrix 1 2 3 is represented as the list (1 2 3).
• Given a 1×m matrix mat, the numbers a and b are adjacent in m if and only if a
occurs immediately to the left or right of b in mat.
For example, in the 1 × 3 matrix above, 1 and 2 are adjacent, 2 and 3 are adjacent,
and 1 and 3 are NOT adjacent.
• In hw3-handout/matrix/matrix.lisp, implement the are-adjecent function.
(are-adjacent lst a b) returns T if the two numbers a and b are adjacent in the 1 × m matrix represented by lst, else it returns NIL.
• An n × m matrix of integers can be represented as a list of list of integers stored in 1 2 3
row-major order. For example, the 2 × 3 matrix 4 5 6 is represented as the list ((1 2 3) (4 5 6)).
• In hw3-handout/matrix/matrix.lisp, implement the transpose function. (transpose mat) returns the transpose of the n × m matrix represented by mat.
3
© Aditya Thakur 2021
This content is protected and may not be shared, uploaded, or distributed.
3
For example, in the 2 × 3 matrix above, 1 and 2 are neighbors, 2 and 5 are neighbors, 5 and 6 are neighbors, and 2 and 6 are NOT neighbors.
In hw3-handout/matrix/matrix.lisp, implement the AreNeighbors function. (are-neighbors m a b) returns T if the two numbers a and b are neighbors in the
n × m matrix represented by m, else it returns NIL.
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 match (15 points)
•
•
•
is represented as the list ((1 4) (2 5) (3 6)).
to the immediate left, right, top, or bottom of a in mat.
1 4
For example, the transpose of the 2×3 matrix above is the 3×2 matrix 2 5, which
36
Given a matrix mat, we say that the numbers a and b are neighbors in mat if b occurs
For this part of the assignment, you only need to modify hw3-handout/match/match.lisp.
• 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.
4
© Aditya Thakur 2021
This content is protected and may not be shared, uploaded, or distributed.
> (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.
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
© Aditya Thakur 2021
This content is protected and may not be shared, uploaded, or distributed.
4 MiniLisp (40 points)
In this assignment, you will implement a parser and interpreter for a small subset of lisp (MiniLisp) in the Go programming language.
For this part of the assignment, you only need to modify hw3-handout/sexpr/parser.go and hw3-handout/sexpr/parser_test.go, which implements the parser for MiniLisp, as well as hw3-handout/sexpr/eval.go and hw3-handout/sexpr/eval_test.go, which im- plements the interpreter for MiniLisp.
• You need to define a struct type that implements the Parser interface defined in hw3-handout/sexpr/parser.go. Do not modify this interface.
Specifically,thistypeneedstoimplementthemethodParse(string) (*SExpr, error) that takes a string and parses it to a *SExpr if the input string is in the language of grammar G defined below, else it returns an error.
The grammar G, whose start symbol is
::=
::= NUMBER | SYMBOL
::= LPAR
• The type SExpr is defined in hw3-handout/sexpr/sexpr.go. You will also find helpful comments and helper functions in this file.
• See the tests in hw3-handout/sexpr/parser_test.go to understand the behavior of Parse.
• You need to modify the NewParser function in hw3-handout/sexpr/parser.go to create an instance of the type that satisfies the Parser interface.
• We have provided an implementation of a lexer in hw3-handout/sexpr/lexer.go for the grammar G.
The lexer performs lexical analysis, converting an input string into a sequence of lexical tokens, which correspond to terminals in the grammar G (e.g., NUMBER, SYMBOL, QUOTE, )) or the end-of-file (EoF) symbol.
Forexample,thelexerturnstheinputstring“'(a 1)”intotokens”QUOTE”, “(“, “a”, “1”, “)”.
• We have provided unit tests the lexer in hw3-handout/sexpr/lexer_test.go. These tests should help you understand how to use the lexer in your implementation of the parser.
• Then you need to implement the Eval function in hw3-handout/sexpr/eval.go, which evaluates an S-expression.
6
© Aditya Thakur 2021
This content is protected and may not be shared, uploaded, or distributed.
• You are required to implement the evaluation of
– numbers;
– Quotations QUOTE;
– CAR, CDR, CONS and LENGTH;
– Unary predicates ATOM, LISTP and ZEROP;
– Arithmetic operations + and *. To support arbitrary-precision arithmetic for integers you should use the package big.
• See the tests in hw3-handout/sexpr/eval_test.go to understand the behavior of Eval. The semantics of MiniLisp CLISP are mostly the same. In some cases, the behavior of MiniLisp might deviate from that in CLISP; this is primarily to simplify the implementation. Please use Piazza if you require further clarification.
• If needed, write new tests in hw3-handout/sexpr/eval_test.go and hw3-handout/sexpr/parser_test.go to ensure that you get 100% code coverage for your code.
From the hw3-handout/sexpr directory, run the go test -cover command to see the current code coverage.
From the hw3-handout/sexpr directory, run the following two commands to see which statements are covered by the unit tests:
$ go test -coverprofile=temp.cov $ go tool cover -html=temp.cov
7
© Aditya Thakur 2021
This content is protected and may not be shared, uploaded, or distributed.
General Tips on Lisp
• 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]> some)nonsense
ABORT :R3 Abort main loop
[2]> :R3
[3]>
• You can exit the interactive clisp interpreter using: [1]> (bye)
8
© Aditya Thakur 2021
This content is protected and may not be shared, uploaded, or distributed.