summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDimitri Sokolyuk <demon@dim13.org>2018-09-22 18:16:45 +0200
committerDimitri Sokolyuk <demon@dim13.org>2018-09-22 18:16:45 +0200
commit389aaf8f88f565d6983765f529905d4799e7a031 (patch)
treeadd059730fe9954a8a4690be1fab627b8d020f99
parent1c0526fd0df159c46c9b5117704894ec49158cd0 (diff)
solve forth; needs refactoring
-rw-r--r--go/forth/.solution.json1
-rw-r--r--go/forth/README.md46
-rw-r--r--go/forth/cases_test.go309
-rw-r--r--go/forth/forth.go217
-rw-r--r--go/forth/forth_test.go41
5 files changed, 614 insertions, 0 deletions
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)
+ }
+ }
+ }
+}