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.