Go语言代写 | ECS 140A Programming Languages Homework 4
这个作业是用Go语言解决有限自动机(NFA)相关的问题
ECS 140A Programming Languages
Spring 2020
Homework 4 due Tuesday June 2nd at 5pm
About This Assignment
• This assignment asks you to complete programming tasks using the Go programming
language.
• You are only allowed to use the subset of Go that we have discussed 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.
– Especially, the use of the runtime and reflect packages is forbidden (runtime
is used in test scripts to check whether your program is concurrent, but other than
that you should not use this package).
– Although the package time is discussed in class, you are NOT allowed to use it
in this homework (e.g. time.Sleep).
• Since the focus of this homework is concurrency, homework solutions are
required to be concurrent in order to receive credit.
• To complete the assignment (i) download hw4-handout.zip from Canvas, (ii) modify the .go files in the hw4-handout directory as per the instructions in this document, and (iii) zip the hw4-handout directory into hw4-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
hw4-handout.
• This assignment has to be worked on individually.
• We will be using Go version 1.11.4, which can be downloaded from
https://golang.org/dl/
Run the command go version to verify that you have the correct version installed:
$ go version
go version go1.11.4
• Go 1.11.4 is installed on all CSIF machines in the directory /usr/local/go/; the
go binary is, thus, at /usr/local/go/bin/go.
Consider adding /usr/local/go/bin to your PATH.
1
© Cindy Rubio Gonzalez 2020
This content is protected and may not be shared, uploaded, or distributed.
• 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.
• Apart from the description in this document, look at the unit tests provided to understand 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.
• This content is protected and may not be shared, uploaded, or distributed.
1 Bug1 (5 points)
• Modify code in hw4-handout/bug1/bug1.go to fix the concurrency bug.
• Some unit tests are provided for you in hw4-handout/bug1/bug1_test.go. You
are not allowed to make changes in hw4-handout/bug1/bug1_test.go to
fix the bug.
From the hw4-handout/bug1 directory, run the go test command to run the unit
tests.
Run the go test -race command to run the unit tests with the race detector,1 a
tool for finding race conditions in Go code.
• From the hw4-handout/bug1 directory, run go test -cover command to see
the current code coverage.
• If needed, add more unit tests in hw4-handout/bug1/bug1_test.go to get 100%
code coverage for the code in hw4-handout/bug1/bug1.go.
• From the hw4-handout/bug1 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
2 Bug2 (5 points)
• Modify code in hw4-handout/bug2/bug2.go to fix the concurrency bug.
1https://blog.golang.org/race-detector
2
© Cindy Rubio Gonzalez 2020
This content is protected and may not be shared, uploaded, or distributed.
• Some unit tests are provided for you in hw4-handout/bug2/bug2_test.go. You
are not allowed to make changes in hw4-handout/bug2/bug2_test.go to
fix the bug.
From the hw4-handout/bug2 directory, run the go test command to run the unit
tests.
Run the go test -race command to run the unit tests with the race detector,2 a
tool for finding race conditions in Go code.
• Removing the use of concurrency is not a valid way to fix the bug.
• From the hw4-handout/bug2 directory, run go test -cover command to see
the current code coverage.
• If needed, add more unit tests in hw4-handout/bug2/bug2_test.go to get 100%
code coverage for the code in hw4-handout/bug2/bug2.go.
• From the hw4-handout/bug2 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
3 NFA (10 points)
A nondeterministic 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
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.
2https://blog.golang.org/race-detector
3
© Cindy Rubio Gonzalez 2020
This content is protected and may not be shared, uploaded, or distributed.
• 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.
The transition function for the NFA described above is represented by the expTransitions
function in hw4-handout/nfa/nfa_test.go. Some unit tests have also been given to
you in hw4-handout/nfa/nfa_test.go. From the hw4-handout/nfa directory, run
the go test command to run the unit tests.
• Write a concurrent implementation of the Reachable function in
hw4-handout/nfa/nfa.go that returns true if a final state is reachable from the
start state after reading an input sequence of symbols, and false, otherwise. The
goal of this assignment is to test your knowledge on concurrency in Go,
thus no credit will be given if your implementation is not concurrent.
• If needed, write new tests, in hw4-handout/nfa/nfa_test.go to ensure that you
get 100% code coverage for your code.
From the hw4-handout/nfa directory, run the go test -cover command to see
the current code coverage.
From the hw4-handout/nfa 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
• Implementing a sequential version of Reachable will get you no points.
• OPTIONAL: From the hw4-handout/nfa directory, run the following command:
$ go test -cpu 1,2,4,8 -bench=.
to benchmark3 your concurrent implementation of Reachable and see how your implementation scales with increasing number of CPUs.
3https://golang.org/pkg/testing/#hdr-Benchmarks
4
© Cindy Rubio Gonzalez 2020
This content is protected and may not be shared, uploaded, or distributed.
4 Smash (10 points)
• Write a concurrent implementation of Smash in hw4-handout/smash/smash.go.
The goal of this assignment is to test your knowledge on concurrency in Go,
thus no credit will be given if your implementation is not concurrent.
• The Smash function takes the following inputs:
– io.Reader4
to read text data, and
– a smasher function that returns a uint32 given a word. smasher may return
the same output uint32 value for different input words.
• The output of Smash is a map[uint32]uint that stores the count of the number
of words that are mapped to the same value by smasher. Words in a string are
separated by whitespace and newline.
• As an example, suppose smasher maps a word to its length.
Then for the input a c d ab abc bac abcd dcba, Smash will return the map
{1: 3, 2: 1, 3: 2, 4: 2}.
On the other hand, if the given smasher were to map each word to unique output,
then Smash would return the count of each word in the input io.Reader.
• Some unit tests are provided for you in hw4-handout/smash/smash_test.go.
From the hw4-handout/smash/ directory, run the go test command to run the
unit tests.
• If needed, write more unit tests in hw4-handout/smash/smash_test.go to get
100% code coverage for the code in hw4-handout/smash/smash.go.
• From the hw4-handout/smash 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
• You can look into using bufio.Scanner5
to read data from the io.Reader.
6
• You might want to use strings.Fields7
to split a string into words.
• Implementing a sequential version of Smash will get you no points.
4https://golang.org/pkg/io/#Reader
5https://golang.org/pkg/bufio/#Scanner
6https://golang.org/src/bufio/example_test.go
7https://golang.org/pkg/strings/#Fields
5
© Cindy Rubio Gonzalez 2020
This content is protected and may not be shared, uploaded, or distributed.
• OPTIONAL: From the hw4-handout/smash directory, run the following command:
$ go test -cpu 1,2,4,8 -bench=.
to benchmark8 your concurrent implementation of Smash and see how your implementation scales with increasing number of CPUs.
8https://golang.org/pkg/testing/#hdr-Benchmarks
6
© Cindy Rubio Gonzalez 2020
This content is protected and may not be shared, uploaded, or distributed.