Add brainfuck interpreter (#65)

Not sure if it builds correctly.
You have to have go compiler.

10 files changed, 523 insertions, 0 deletions

diff --git a/homework/81319/bfinterpreter/Makefile b/homework/81319/bfinterpreter/Makefile
new file mode 100644
index 0000000..00d7439
--- /dev/null
+++ b/homework/81319/bfinterpreter/Makefile
@@ -0,0 +1,15 @@
+CURRENT_DIR = $(shell pwd)
+GOPATH=$(CURRENT_DIR)/.tmp/
+
+interpreter: tmp
+	$(cd .tmp/src/bfinterpreter)
+	@echo $(CURRENT_DIR)
+	go build
+
+tmp:
+	$(shell ./make_temp_folders.sh)
+
+clean:
+	rm -rf .tmp
+	rm -rf bfinterpreter
+
diff --git a/homework/81319/bfinterpreter/README.md b/homework/81319/bfinterpreter/README.md
new file mode 100644
index 0000000..7f65de0
--- /dev/null
+++ b/homework/81319/bfinterpreter/README.md
@@ -0,0 +1,19 @@
+# Brainfuck Interpreter in Golang
+
+### Steps
+#### 1. Install Go compiler
+#### 2. Run:
+```
+make
+```
+#### 3. Run:
+```
+./bfinterpreter
+```
+#### 4. Enjoy!
+
+
+
+#### Make sure to read the language specification of Brainfuck.
+
+#### You can find it [here](https://en.wikipedia.org/wiki/Brainfuck#Commands).
\ No newline at end of file
diff --git a/homework/81319/bfinterpreter/bf/cell.go b/homework/81319/bfinterpreter/bf/cell.go
new file mode 100644
index 0000000..9767bbb
--- /dev/null
+++ b/homework/81319/bfinterpreter/bf/cell.go
@@ -0,0 +1,21 @@
+package bf
+
+type cell struct {
+	value byte
+}
+
+func (c *cell) increment() {
+	c.value = byte(int(c.value) + 1)
+}
+
+func (c *cell) decrement() {
+	c.value = byte(int(c.value) - 1)
+}
+
+func (c *cell) getValue() byte {
+	return c.value
+}
+
+func (c *cell) setValue(value byte) {
+	c.value = value
+}
diff --git a/homework/81319/bfinterpreter/bf/interpreter.go b/homework/81319/bfinterpreter/bf/interpreter.go
new file mode 100644
index 0000000..87c9870
--- /dev/null
+++ b/homework/81319/bfinterpreter/bf/interpreter.go
@@ -0,0 +1,189 @@
+package bf
+
+import (
+	"bufio"
+	"errors"
+	"fmt"
+	"io"
+	"os"
+	"strconv"
+)
+
+type instruction struct {
+	idx             uint
+	instructionType token
+
+	matchingBracketIdx uint
+}
+
+type state struct {
+	mem            memoryState
+	src            []instruction
+	instructionPtr uint
+
+	buffer []byte
+	reader io.Reader
+	writer io.Writer
+}
+
+func (s *state) moveRight() {
+	s.mem.incrementPtr()
+}
+
+func (s *state) moveLeft() {
+	s.mem.decrementPtr()
+}
+
+func (s *state) incrementValue() {
+	s.mem.incrementCell()
+}
+
+func (s *state) decrementValue() {
+	s.mem.decerementCell()
+}
+
+func (s *state) readCellValue() error {
+	count, err := s.reader.Read(s.buffer)
+	if err == io.EOF {
+		return nil
+	}
+
+	if err != nil {
+		return errors.New("couldn't read from input")
+	}
+
+	if count < 1 {
+		return errors.New("couldn't read from input")
+	}
+
+	s.mem.setCell(s.buffer[0])
+
+	return nil
+}
+
+func (s *state) writeCellValue() error {
+	count, err := s.writer.Write([]byte{s.mem.getCell()})
+
+	if err != nil {
+		return errors.New("couldn't write to output")
+	}
+
+	if count != 1 {
+		return errors.New("couldn't write to output")
+	}
+
+	return nil
+}
+
+func (s *state) interpretInstruction() {
+	instr := s.src[s.instructionPtr]
+
+	switch instr.instructionType {
+	case movR:
+		s.moveRight()
+	case movL:
+		s.moveLeft()
+	case incD:
+		s.incrementValue()
+	case decD:
+		s.decrementValue()
+	case outD:
+		s.writeCellValue()
+	case inD:
+		s.readCellValue()
+	case loopS:
+		if s.mem.getCell() == 0 {
+			s.instructionPtr = instr.matchingBracketIdx
+		}
+	case loopE:
+		if s.mem.getCell() != 0 {
+			s.instructionPtr = instr.matchingBracketIdx
+		}
+	}
+	s.instructionPtr += 1
+}
+
+func (s *state) addInstructions(src string) {
+	instructions := parseInput(tokenizeInput(src))
+
+	s.src = append(s.src, instructions...)
+}
+
+type flushingWriter struct {
+	w *bufio.Writer
+}
+
+func newFlushingWriter() io.Writer {
+	writer := &flushingWriter{
+		w: bufio.NewWriter(os.Stdout),
+	}
+
+	return writer
+}
+
+func (w *flushingWriter) Write(p []byte) (int, error) {
+	fmt.Print("#=> ")
+	count, err := w.w.Write(p)
+	if err != nil {
+		return 0, err
+	}
+	w.w.Flush()
+
+	fmt.Println()
+
+	return count, nil
+}
+
+type lineReader struct {
+	r *bufio.Reader
+}
+
+func newLineReader() io.Reader {
+	reader := &lineReader{
+		r: bufio.NewReader(os.Stdin),
+	}
+
+	return reader
+}
+
+func (r *lineReader) Read(buffer []byte) (int, error) {
+	stringVal, err := r.r.ReadString('\n')
+
+	if err != nil {
+		return 0, err
+	}
+
+	result, err := strconv.ParseInt(stringVal[:len(stringVal)-1], 10, 8)
+
+	if err != nil {
+		return 0, err
+	}
+
+	buffer[0] = byte(result)
+
+	return 1, nil
+}
+
+func NewInterpreter(src string) state {
+	instructions := parseInput(tokenizeInput(src))
+
+	state := state{
+		instructionPtr: 0,
+		src:            instructions,
+		buffer:         make([]byte, 1),
+		writer:         newFlushingWriter(),
+		reader:         newLineReader(),
+	}
+
+	return state
+}
+
+func (s *state) Run() {
+	for {
+		if int(s.instructionPtr) == len(s.src) {
+			return
+		}
+
+		s.interpretInstruction()
+	}
+}
diff --git a/homework/81319/bfinterpreter/bf/interpreter_test.go b/homework/81319/bfinterpreter/bf/interpreter_test.go
new file mode 100644
index 0000000..a798669
--- /dev/null
+++ b/homework/81319/bfinterpreter/bf/interpreter_test.go
@@ -0,0 +1,58 @@
+package bf
+
+import (
+	"bufio"
+	"io"
+	"os"
+	"testing"
+)
+
+func TestInterpretInstruction(t *testing.T) {
+	var writer io.Writer
+
+	writer = flushingWriter{
+		w: bufio.NewWriter(os.Stdout),
+	}
+
+	src := []instruction{
+		{
+			idx:             0,
+			instructionType: incD,
+		},
+	}
+
+	for i := 0; i < 65; i++ {
+		src = append(src, instruction{
+			idx:             uint(i),
+			instructionType: incD,
+		})
+	}
+
+	src = append(src, instruction{
+		idx:             65,
+		instructionType: outD,
+	})
+
+	intepreterState := state{
+		src:    src,
+		buffer: make([]byte, 1),
+		writer: writer,
+	}
+
+	writer.Write([]byte("hello\n"))
+
+	for i := 0; i < 66; i++ {
+		intepreterState.interpretInstruction()
+	}
+
+	intepreterState.interpretInstruction()
+
+}
+
+func TestInterpreter(t *testing.T) {
+	input := ","
+	interpreter := NewInterpreter(input)
+
+	Run(interpreter)
+
+}
diff --git a/homework/81319/bfinterpreter/bf/mem.go b/homework/81319/bfinterpreter/bf/mem.go
new file mode 100644
index 0000000..8679584
--- /dev/null
+++ b/homework/81319/bfinterpreter/bf/mem.go
@@ -0,0 +1,40 @@
+package bf
+
+const (
+	MEMORY_SIZE uint = 1024
+)
+
+type memoryState struct {
+	memory         [MEMORY_SIZE]cell
+	currentCellIdx uint
+}
+
+func (m *memoryState) incrementPtr() {
+	if m.currentCellIdx == MEMORY_SIZE {
+		return
+	}
+	m.currentCellIdx += 1
+}
+
+func (m *memoryState) decrementPtr() {
+	if m.currentCellIdx == 0 {
+		return
+	}
+	m.currentCellIdx -= 1
+}
+
+func (m *memoryState) incrementCell() {
+	m.memory[m.currentCellIdx].increment()
+}
+
+func (m *memoryState) decerementCell() {
+	m.memory[m.currentCellIdx].decrement()
+}
+
+func (m *memoryState) setCell(value byte) {
+	m.memory[m.currentCellIdx].setValue(value)
+}
+
+func (m *memoryState) getCell() byte {
+	return m.memory[m.currentCellIdx].getValue()
+}
diff --git a/homework/81319/bfinterpreter/bf/repl.go b/homework/81319/bfinterpreter/bf/repl.go
new file mode 100644
index 0000000..e09bcea
--- /dev/null
+++ b/homework/81319/bfinterpreter/bf/repl.go
@@ -0,0 +1,44 @@
+package bf
+
+import (
+	"bufio"
+	"fmt"
+	"os"
+)
+
+type repl struct {
+	interpreter *state
+	reader      *bufio.Reader
+	writer      *bufio.Writer
+}
+
+func NewRepl() repl {
+	intepreter := NewInterpreter("")
+	return repl{
+		interpreter: &intepreter,
+		reader:      bufio.NewReader(os.Stdin),
+		writer:      bufio.NewWriter(os.Stdout),
+	}
+}
+
+func (r *repl) read() {
+	fmt.Print(">>")
+	instructions, err := r.reader.ReadString('\n')
+	instructions = instructions[:len(instructions)-1]
+	if err != nil {
+		panic("not implemented")
+	}
+
+	r.interpreter.addInstructions(instructions)
+}
+
+func (r *repl) eval() {
+	r.interpreter.Run()
+}
+
+func (r *repl) Start() {
+	for {
+		r.read()
+		r.eval()
+	}
+}
diff --git a/homework/81319/bfinterpreter/bf/tokenizer.go b/homework/81319/bfinterpreter/bf/tokenizer.go
new file mode 100644
index 0000000..10a0342
--- /dev/null
+++ b/homework/81319/bfinterpreter/bf/tokenizer.go
@@ -0,0 +1,124 @@
+package bf
+
+import (
+	"bytes"
+	"io"
+)
+
+type token int
+
+const (
+	unkwn token = iota
+	movR
+	movL
+	incD
+	decD
+	outD
+	inD
+	loopS
+	loopE
+)
+
+func tokenize(symbol string) token {
+	switch symbol {
+	case ">":
+		return movR
+	case "<":
+		return movL
+	case ".":
+		return outD
+	case ",":
+		return inD
+	case "+":
+		return incD
+	case "-":
+		return decD
+	case "[":
+		return loopS
+	case "]":
+		return loopE
+	}
+
+	return 0
+}
+
+type tokenizingStream struct {
+	reader io.Reader
+}
+
+func (s *tokenizingStream) Read(p []byte) (int, error) {
+	buffer := make([]byte, len(p))
+
+	count, err := s.reader.Read(buffer)
+	if err != nil {
+		return 0, err
+	}
+
+	for i := 0; i < count; i++ {
+		p[i] = byte(tokenize(string(buffer[i])))
+	}
+
+	return count, nil
+}
+
+func tokenizeInput(input string) []instruction {
+	byteBuff := []byte(input)
+	reader := bytes.NewReader(byteBuff)
+	tokenizingReader := tokenizingStream{
+		reader: reader,
+	}
+
+	bytesRead := make([]byte, 1)
+	instructions := make([]instruction, 0)
+
+	for {
+		_, ok := tokenizingReader.Read(bytesRead)
+		if ok == io.EOF {
+			break
+		}
+		if ok == nil {
+			inst := instruction{
+				instructionType: token(bytesRead[0]),
+			}
+
+			instructions = append(instructions, inst)
+		}
+	}
+
+	return instructions
+}
+
+func parseInput(instructions []instruction) []instruction {
+	stack := make([]instruction, 0)
+
+	for idx, inst := range instructions {
+		instructions[idx].idx = uint(idx)
+
+		if inst.instructionType != loopS && inst.instructionType != loopE {
+			continue
+		}
+
+		if inst.instructionType == loopS {
+			inst.idx = uint(idx)
+			stack = append(stack, inst)
+
+			continue
+		}
+
+		if len(stack) < 1 {
+			panic("input data invalid!")
+		}
+
+		prevInst := stack[len(stack)-1]
+		prevInst.matchingBracketIdx = uint(idx)
+		instructions[prevInst.idx] = prevInst
+
+		inst.idx = uint(idx)
+		inst.matchingBracketIdx = prevInst.idx
+		instructions[idx] = inst
+
+		stack = stack[:len(stack)-1]
+	}
+
+	return instructions
+}
diff --git a/homework/81319/bfinterpreter/main.go b/homework/81319/bfinterpreter/main.go
new file mode 100644
index 0000000..2e76424
--- /dev/null
+++ b/homework/81319/bfinterpreter/main.go
@@ -0,0 +1,8 @@
+package main
+
+import "github.com/geosteffanov/bfinterpreter/bf"
+
+func main() {
+	repl := bf.NewRepl()
+	repl.Start()
+}
diff --git a/homework/81319/bfinterpreter/make_temp_folders.sh b/homework/81319/bfinterpreter/make_temp_folders.sh
new file mode 100755
index 0000000..dc6ac77
--- /dev/null
+++ b/homework/81319/bfinterpreter/make_temp_folders.sh
@@ -0,0 +1,5 @@
+#!/usr/bin/env bash
+
+mkdir -p .tmp/src/github.com/geosteffanov/bfinterpreter
+cp -rf bf .tmp/src/github.com/geosteffanov/bfinterpreter
+cp main.go .tmp/src/github.com/geosteffanov/bfinterpreter
\ No newline at end of file