From 389aaf8f88f565d6983765f529905d4799e7a031 Mon Sep 17 00:00:00 2001 From: Dimitri Sokolyuk Date: Sat, 22 Sep 2018 18:16:45 +0200 Subject: solve forth; needs refactoring --- go/forth/.solution.json | 1 + go/forth/README.md | 46 +++++++ go/forth/cases_test.go | 309 ++++++++++++++++++++++++++++++++++++++++++++++++ go/forth/forth.go | 217 ++++++++++++++++++++++++++++++++++ go/forth/forth_test.go | 41 +++++++ 5 files changed, 614 insertions(+) create mode 100644 go/forth/.solution.json create mode 100644 go/forth/README.md create mode 100644 go/forth/cases_test.go create mode 100644 go/forth/forth.go create mode 100644 go/forth/forth_test.go diff --git a/go/forth/.solution.json b/go/forth/.solution.json new file mode 100644 index 0000000..72a1516 --- /dev/null +++ b/go/forth/.solution.json @@ -0,0 +1 @@ +{"track":"go","exercise":"forth","id":"8c599d700c4d4b71a527bcde617d327d","url":"https://exercism.io/my/solutions/8c599d700c4d4b71a527bcde617d327d","handle":"dim13","is_requester":true,"auto_approve":false} \ No newline at end of file diff --git a/go/forth/README.md b/go/forth/README.md new file mode 100644 index 0000000..b00d810 --- /dev/null +++ b/go/forth/README.md @@ -0,0 +1,46 @@ +# Forth + +Implement an evaluator for a very simple subset of Forth. + +[Forth](https://en.wikipedia.org/wiki/Forth_%28programming_language%29) +is a stack-based programming language. Implement a very basic evaluator +for a small subset of Forth. + +Your evaluator has to support the following words: + +- `+`, `-`, `*`, `/` (integer arithmetic) +- `DUP`, `DROP`, `SWAP`, `OVER` (stack manipulation) + +Your evaluator also has to support defining new words using the +customary syntax: `: word-name definition ;`. + +To keep things simple the only data type you need to support is signed +integers of at least 16 bits size. + +You should use the following rules for the syntax: a number is a +sequence of one or more (ASCII) digits, a word is a sequence of one or +more letters, digits, symbols or punctuation that is not a number. +(Forth probably uses slightly different rules, but this is close +enough.) + +Words are case-insensitive. + +## Running the tests + +To run the tests run the command `go test` from within the exercise directory. + +If the test suite contains benchmarks, you can run these with the `--bench` and `--benchmem` +flags: + + go test -v --bench . --benchmem + +Keep in mind that each reviewer will run benchmarks on a different machine, with +different specs, so the results from these benchmark tests may vary. + +## Further information + +For more detailed information about the Go track, including how to get help if +you're having trouble, please visit the exercism.io [Go language page](http://exercism.io/languages/go/about). + +## Submitting Incomplete Solutions +It's possible to submit an incomplete solution so you can see how others have completed the exercise. diff --git a/go/forth/cases_test.go b/go/forth/cases_test.go new file mode 100644 index 0000000..63f1f19 --- /dev/null +++ b/go/forth/cases_test.go @@ -0,0 +1,309 @@ +package forth + +// Source: exercism/problem-specifications +// Commit: c853973 forth: add tests for word redefinition (#1243) +// Problem Specifications Version: 1.6.0 + +type testGroup struct { + group string + tests []testCase +} + +type testCase struct { + description string + input []string + expected []int // nil slice indicates error expected. +} + +var testGroups = []testGroup{ + { + group: "parsing and numbers", + tests: []testCase{ + { + "numbers just get pushed onto the stack", + []string{"1 2 3 4 5"}, + []int{1, 2, 3, 4, 5}, + }, + }, + }, + { + group: "addition", + tests: []testCase{ + { + "can add two numbers", + []string{"1 2 +"}, + []int{3}, + }, + { + "errors if there is nothing on the stack", + []string{"+"}, + []int(nil), + }, + { + "errors if there is only one value on the stack", + []string{"1 +"}, + []int(nil), + }, + }, + }, + { + group: "subtraction", + tests: []testCase{ + { + "can subtract two numbers", + []string{"3 4 -"}, + []int{-1}, + }, + { + "errors if there is nothing on the stack", + []string{"-"}, + []int(nil), + }, + { + "errors if there is only one value on the stack", + []string{"1 -"}, + []int(nil), + }, + }, + }, + { + group: "multiplication", + tests: []testCase{ + { + "can multiply two numbers", + []string{"2 4 *"}, + []int{8}, + }, + { + "errors if there is nothing on the stack", + []string{"*"}, + []int(nil), + }, + { + "errors if there is only one value on the stack", + []string{"1 *"}, + []int(nil), + }, + }, + }, + { + group: "division", + tests: []testCase{ + { + "can divide two numbers", + []string{"12 3 /"}, + []int{4}, + }, + { + "performs integer division", + []string{"8 3 /"}, + []int{2}, + }, + { + "errors if dividing by zero", + []string{"4 0 /"}, + []int(nil), + }, + { + "errors if there is nothing on the stack", + []string{"/"}, + []int(nil), + }, + { + "errors if there is only one value on the stack", + []string{"1 /"}, + []int(nil), + }, + }, + }, + { + group: "combined arithmetic", + tests: []testCase{ + { + "addition and subtraction", + []string{"1 2 + 4 -"}, + []int{-1}, + }, + { + "multiplication and division", + []string{"2 4 * 3 /"}, + []int{2}, + }, + }, + }, + { + group: "dup", + tests: []testCase{ + { + "copies a value on the stack", + []string{"1 dup"}, + []int{1, 1}, + }, + { + "copies the top value on the stack", + []string{"1 2 dup"}, + []int{1, 2, 2}, + }, + { + "errors if there is nothing on the stack", + []string{"dup"}, + []int(nil), + }, + }, + }, + { + group: "drop", + tests: []testCase{ + { + "removes the top value on the stack if it is the only one", + []string{"1 drop"}, + []int{}, + }, + { + "removes the top value on the stack if it is not the only one", + []string{"1 2 drop"}, + []int{1}, + }, + { + "errors if there is nothing on the stack", + []string{"drop"}, + []int(nil), + }, + }, + }, + { + group: "swap", + tests: []testCase{ + { + "swaps the top two values on the stack if they are the only ones", + []string{"1 2 swap"}, + []int{2, 1}, + }, + { + "swaps the top two values on the stack if they are not the only ones", + []string{"1 2 3 swap"}, + []int{1, 3, 2}, + }, + { + "errors if there is nothing on the stack", + []string{"swap"}, + []int(nil), + }, + { + "errors if there is only one value on the stack", + []string{"1 swap"}, + []int(nil), + }, + }, + }, + { + group: "over", + tests: []testCase{ + { + "copies the second element if there are only two", + []string{"1 2 over"}, + []int{1, 2, 1}, + }, + { + "copies the second element if there are more than two", + []string{"1 2 3 over"}, + []int{1, 2, 3, 2}, + }, + { + "errors if there is nothing on the stack", + []string{"over"}, + []int(nil), + }, + { + "errors if there is only one value on the stack", + []string{"1 over"}, + []int(nil), + }, + }, + }, + { + group: "user-defined words", + tests: []testCase{ + { + "can consist of built-in words", + []string{": dup-twice dup dup ;", "1 dup-twice"}, + []int{1, 1, 1}, + }, + { + "execute in the right order", + []string{": countup 1 2 3 ;", "countup"}, + []int{1, 2, 3}, + }, + { + "can override other user-defined words", + []string{": foo dup ;", ": foo dup dup ;", "1 foo"}, + []int{1, 1, 1}, + }, + { + "can override built-in words", + []string{": swap dup ;", "1 swap"}, + []int{1, 1}, + }, + { + "can override built-in operators", + []string{": + * ;", "3 4 +"}, + []int{12}, + }, + { + "can use different words with the same name", + []string{": foo 5 ;", ": bar foo ;", ": foo 6 ;", "bar foo"}, + []int{5, 6}, + }, + { + "can define word that uses word with the same name", + []string{": foo 10 ;", ": foo foo 1 + ;", "foo"}, + []int{11}, + }, + { + "cannot redefine numbers", + []string{": 1 2 ;"}, + []int(nil), + }, + { + "errors if executing a non-existent word", + []string{"foo"}, + []int(nil), + }, + }, + }, + { + group: "case-insensitivity", + tests: []testCase{ + { + "DUP is case-insensitive", + []string{"1 DUP Dup dup"}, + []int{1, 1, 1, 1}, + }, + { + "DROP is case-insensitive", + []string{"1 2 3 4 DROP Drop drop"}, + []int{1}, + }, + { + "SWAP is case-insensitive", + []string{"1 2 SWAP 3 Swap 4 swap"}, + []int{2, 3, 4, 1}, + }, + { + "OVER is case-insensitive", + []string{"1 2 OVER Over over"}, + []int{1, 2, 1, 2, 1}, + }, + { + "user-defined words are case-insensitive", + []string{": foo dup ;", "1 FOO Foo foo"}, + []int{1, 1, 1, 1}, + }, + { + "definitions are case-insensitive", + []string{": SWAP DUP Dup dup ;", "1 swap"}, + []int{1, 1, 1, 1}, + }, + }, + }, +} diff --git a/go/forth/forth.go b/go/forth/forth.go new file mode 100644 index 0000000..8675941 --- /dev/null +++ b/go/forth/forth.go @@ -0,0 +1,217 @@ +package forth + +import ( + "errors" + "log" + "strconv" + "strings" +) + +type stacker interface { + push(int) error + pop() (int, error) + values() []int +} + +type stack []int + +func (s *stack) push(n int) error { + *s = append(*s, n) + return nil +} + +func (s *stack) pop() (int, error) { + depth := len(*s) + if depth < 1 { + return 0, errors.New("stack underflow") + } + tos := (*s)[depth-1] + *s = (*s)[:depth-1] + return tos, nil +} + +func (s *stack) values() []int { + return []int(*s) +} + +func pop2(s stacker) (int, int, error) { + tos, err := s.pop() + if err != nil { + return 0, 0, err + } + nos, err := s.pop() + if err != nil { + return 0, 0, err + } + return tos, nos, nil +} + +func pushN(s stacker, n ...int) error { + for _, v := range n { + if err := s.push(v); err != nil { + return err + } + } + return nil +} + +type dictionary map[string][]func(stacker) error + +func (d dictionary) find(name string) ([]func(stacker) error, bool) { + fs, ok := d[strings.ToLower(name)] + return fs, ok +} + +func (d dictionary) add(name string, fs ...func(stacker) error) { + d[strings.ToLower(name)] = fs +} + +func add(s stacker) error { + tos, nos, err := pop2(s) + if err != nil { + return err + } + return s.push(nos + tos) +} + +func sub(s stacker) error { + tos, nos, err := pop2(s) + if err != nil { + return err + } + return s.push(nos - tos) +} + +func mul(s stacker) error { + tos, nos, err := pop2(s) + if err != nil { + return err + } + return s.push(nos * tos) +} + +func div(s stacker) error { + tos, nos, err := pop2(s) + if err != nil { + return err + } + if tos == 0 { + return errors.New("division by zero") + } + return s.push(nos / tos) +} + +func dup(s stacker) error { + tos, err := s.pop() + if err != nil { + return err + } + return pushN(s, tos, tos) +} + +func drop(s stacker) error { + _, err := s.pop() + return err +} + +func swap(s stacker) error { + tos, nos, err := pop2(s) + if err != nil { + return err + } + return pushN(s, tos, nos) +} + +func over(s stacker) error { + tos, nos, err := pop2(s) + if err != nil { + return err + } + return pushN(s, nos, tos, nos) +} + +func literal(n int) func(stacker) error { + return func(s stacker) error { + return s.push(n) + } +} + +func number(word string) (int, bool) { + n, err := strconv.Atoi(word) + return n, err == nil +} + +func index(s []string, r string) int { + for i, v := range s { + if v == r { + return i + } + } + return -1 +} + +func compile(dict dictionary, s []string) ([]func(stacker) error, error) { + log.Println("compile", s) + var words []func(stacker) error + for i := 0; i < len(s); i++ { + v := s[i] + // lookup dictionary first + if w, ok := dict.find(v); ok { + words = append(words, w...) + continue + } + if v == ":" { + next := index(s[i+1:], ";") + if next == -1 { + return nil, errors.New("unterminated colon operator") + } + name := s[i+1] + if _, ok := number(name); ok { + return nil, errors.New("name cannot be a number") + } + w, err := compile(dict, s[i+2:i+next+1]) + if err != nil { + return nil, err + } + log.Println("add", name) + dict.add(name, w...) + i += next + 1 + continue + } + // try to parse literal + if n, ok := number(v); ok { + words = append(words, literal(n)) + continue + } + return nil, errors.New("unknown word") + } + return words, nil +} + +func Forth(v []string) ([]int, error) { + s := new(stack) + dict := make(dictionary) + dict.add("+", add) + dict.add("-", sub) + dict.add("*", mul) + dict.add("/", div) + dict.add("dup", dup) + dict.add("drop", drop) + dict.add("swap", swap) + dict.add("over", over) + + var words []func(stacker) error + for _, line := range v { + w, err := compile(dict, strings.Split(line, " ")) + if err != nil { + return nil, err + } + words = append(words, w...) + } + for _, w := range words { + if err := w(s); err != nil { + return nil, err + } + } + return s.values(), nil +} diff --git a/go/forth/forth_test.go b/go/forth/forth_test.go new file mode 100644 index 0000000..0eff3c6 --- /dev/null +++ b/go/forth/forth_test.go @@ -0,0 +1,41 @@ +package forth + +// API: +// func Forth([]string) ([]int, error) +// + +import ( + "reflect" + "testing" +) + +func TestForth(t *testing.T) { + for _, tg := range testGroups { + for _, tc := range tg.tests { + if v, err := Forth(tc.input); err == nil { + var _ error = err + if tc.expected == nil { + t.Fatalf("FAIL: %s | %s\n\tForth(%#v) expected an error, got %v", + tg.group, tc.description, tc.input, v) + } else if !reflect.DeepEqual(v, tc.expected) { + t.Fatalf("FAIL: %s | %s\n\tForth(%#v) expected %v, got %v", + tg.group, tc.description, tc.input, tc.expected, v) + } + } else if tc.expected != nil { + t.Fatalf("FAIL: %s | %s\n\tForth(%#v) expected %v, got an error: %q", + tg.group, tc.description, tc.input, tc.expected, err) + } + t.Logf("PASS: %s | %s", tg.group, tc.description) + } + } +} + +func BenchmarkForth(b *testing.B) { + for i := 0; i < b.N; i++ { + for _, tg := range testGroups { + for _, tc := range tg.tests { + Forth(tc.input) + } + } + } +} -- cgit v1.2.3