golisp

.gitignore

*.swp

main.go

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

// REPL like client
// The user can enter a lisp, it will be parsed into a AST
// Now: the AST will be printed, in lisp style
// TODO: instead of just printing the AST, evaluate it
func main() {
	cli := bufio.NewReader(os.Stdin)
	for {
		fmt.Print("golisp> ")

		input, err := cli.ReadString('\n')
		if err != nil {
			panic(err)
		}

		switch strings.TrimSpace(input) {
		case "q", "quit", "x", "exit":
			fmt.Println("Have a nice day!")
			return
		default:
			parsed, err := ParseLisp(input)
			if err != nil {
				fmt.Println(err)
			} else {
				fmt.Println(parsed)
			}
		}
	}
}

parse.go

package main

import (
	"errors"
	"strings"
)

// A lisp should either be a string or a list of other lisps
// ie, one of these values should be empty
type lisp struct {
	list  []*lisp
	token string
}

// NewToken encapsulates a string into a lisp.
func NewToken(token string) *lisp {
	return &lisp{nil, token}
}

// ParseLisp recursively parses a string, returning the lisp represented.
// If the string does not represent a valid lisp, an error will be returned
func ParseLisp(str string) (*lisp, error) {
	l := &lisp{}
	l.list = make([]*lisp, 0)

	str = strings.TrimSpace(str)
	if strings.HasPrefix(str, "(") && strings.HasSuffix(str, ")") {
		str = str[1 : len(str)-1]
	}

	if !validateLisp(str) {
		return nil, errors.New("unbalanced parens")
	}

	token := ""
	// add the current token to the list and reset the token
	addToken := func() {
		if token != "" {
			l.list = append(l.list, NewToken(token))
			token = ""
		}
	}

	for i := 0; i < len(str); i++ {
		c := str[i : i+1]
		switch c {
		case ")":
			addToken()
			return l, nil
		case " ":
			addToken()
		default:
			token += c
		case "(":
			close := strings.Index(str[i:], ")")
			// below should never occur:
			if close == -1 {
				panic("no ')' found even though lisp was validated: " + str)
			}

			// remove the last character, which should be the closing ')'
			nest, err := ParseLisp(str[i:])
			if err != nil {
				return nil, err
			}

			l.list = append(l.list, nest)
			i = i + close // skip parsing the nested lisp again
		}
	}
	addToken()
	return l, nil
}

// String prints a lisp according to normal standards
// space separated tokens are surrounded by parens
// Nested lisps take the place of a token and recursively call this function.
func (a lisp) String() string {
	if a.IsToken() {
		return a.GetToken()
	} else {
		str := ""
		for i, s := range a.list {
			space := " "
			if i == len(a.list)-1 {
				space = ""
			}
			str += s.String() + space
		}
		// if lisp is only parens, empty it
		if strings.Trim(str, "()") == "" {
			str = ""
		}
		return "(" + str + ")"
	}
}

// IsToken indicates whether the lisp has a token value
func (a lisp) IsToken() bool {
	return a.GetToken() != ""
}

// GetToken retrieves the token value of a lisp. It ignores excessive
// parens. Thus, (((25))) will return 25.
func (a lisp) GetToken() string {
	ls := a
	for len(ls.list) == 1 {
		ls = *ls.list[0]
	}
	return ls.token
}

// ensures that the parenthesis are properly balanced
func validateLisp(str string) bool {
	stack := ""

	for _, s := range str {
		if s == '(' {
			stack += "("
		} else if s == ')' {
			if strings.HasSuffix(stack, "(") {
				stack = stack[:len(stack)-1]
			} else {
				return false
			}
		}
	}
	return stack == ""
}

parse_test.go

package main

import (
	"fmt"
	"testing"
)

func TestParens(t *testing.T) {
	badParens := []string{"(+ 1", ")(", "((((((", "(()", "((()())))"}

	for _, s := range badParens {
		_, err := ParseLisp(s)
		if err == nil {
			t.Fatalf("Parsing %s did not produce an error", s)
		}
	}
}

func TestInternalWhitespace(t *testing.T) {
	input := "(   5   6     9      )"
	expected := "(5 6 9)"
	actual, _ := ParseLisp(input)

	if fmt.Sprint(actual) != expected {
		t.Fatal("whitespace is not properly stripped from %s when parsing, %s should be %s", input, actual, expected)
	}
}

func TestExternalWhitespace(t *testing.T) {
	input := "   (   5   6     9      )    "
	expected := "(5 6 9)"
	actual, _ := ParseLisp(input)

	if fmt.Sprint(actual) != expected {
		t.Fatalf("whitespace is not properly stripped from %s when parsing, %s should be %s", input, actual, expected)
	}
}

func TestIsToken(t *testing.T) {
	res, err := ParseLisp("((((((25))))))")

	if err != nil {
		t.Fatalf("error while testing, failed to parse %s: %s", res, err)
	}

	if !res.IsToken() {
		t.Fatalf("%s is not recognized as a token", res)
	}
}

func TestIsNotToken(t *testing.T) {
	res, err := ParseLisp("(1 2 3 4)")

	if err != nil {
		t.Fatalf("error while testing, failed to parse %s: %s", res, err)
	}

	if res.IsToken() {
		t.Fatalf("%s is incorrectly recognized as a token", res)
	}
}

func TestEmptyLisp(t *testing.T) {
	res, err := ParseLisp("((((((()))))))")

	if err != nil {
		t.Fatalf("error while testing, failed to parse %s: %s", res, err)
	}

	if res.String() != "()" {
		t.Fatalf("%s is not reduced to \"()\"", res)
	}

	res, err = ParseLisp("")

	if err != nil {
		t.Fatalf("error while testing, failed to parse %s: %s", res, err)
	}

	if res.String() != "()" {
		t.Fatalf("%s is not reduced to \"()\"", res)
	}
}