I'm quite a basic Go programmer and I've been taking a look at this small Scheme interpreter and I've been trying to understand how it works.
I found it here: https://pkelchte.wordpress.com/2013/12/31/scm-go/
I read the webpage, but I'm still struggling to understand how it works because the source code is obviously written by someone who's a lot more familiar with Go than I am.
Particularly there's these lines that I'm struggling to understand:
e := expression.(type) // Line 73
I'm not sure what the .(type) part means, I thought it was casting but it doesn't look like the casting I've seen before.
switch p := procedure.(type) {
case func(...scmer) scmer:
value = p(args...)
case proc:
en := &env{make(vars), p.en}
switch params := p.params.(type) {
case []scmer:
for i, param := range params {
en.vars[param.(symbol)] = args[i]
}
default:
en.vars[params.(symbol)] = args
}
value = eval(p.body, en)
I don't really understand any of this code to be honest. Lines 73 - 86
*tokens = (*tokens)[1:] // Line 208
I'm not sure what this line means due to it's weird syntax. I get that its pointers and that the parenthesises are because of the *. But I'm not sure what that lines doing.
Finally there's these lines:
token := (*tokens)[0]
*tokens = (*tokens)[1:]
switch token {
case "(": //a list begins
L := make([]scmer, 0)
for (*tokens)[0] != ")" {
if i := readFrom(tokens); i != symbol("") {
L = append(L, i)
}
}
*tokens = (*tokens)[1:]
return L
I don't know what these lines do either. Lines 198 - 209
Here's the complete code if you want it, I realise it's 250 lines long but I'd really appreciate as many explanations about what its doing as possible.
/*
* A minimal Scheme interpreter, as seen in lis.py and SICP
* http://norvig.com/lispy.html
* http://mitpress.mit.edu/sicp/full-text/sicp/book/node77.html
*
* Pieter Kelchtermans 2013
* LICENSE: WTFPL 2.0
*/
package main
import (
"bufio"
"fmt"
"log"
"os"
"reflect"
"strconv"
"strings"
)
func main() {
Repl()
}
/*
Eval / Apply
*/
func eval(expression scmer, en *env) (value scmer) {
switch e := expression.(type) {
case number:
value = e
case symbol:
value = en.Find(e).vars[e]
case []scmer:
switch car, _ := e[0].(symbol); car {
case "quote":
value = e[1]
case "if":
if eval(e[1], en).(bool) {
value = eval(e[2], en)
} else {
value = eval(e[3], en)
}
case "set!":
v := e[1].(symbol)
en.Find(v).vars[v] = eval(e[2], en)
value = "ok"
case "define":
en.vars[e[1].(symbol)] = eval(e[2], en)
value = "ok"
case "lambda":
value = proc{e[1], e[2], en}
case "begin":
for _, i := range e[1:] {
value = eval(i, en)
}
default:
operands := e[1:]
values := make([]scmer, len(operands))
for i, x := range operands {
values[i] = eval(x, en)
}
value = apply(eval(e[0], en), values)
}
default:
log.Println("Unknown expression type - EVAL", e)
}
return
}
func apply(procedure scmer, args []scmer) (value scmer) {
switch p := procedure.(type) {
case func(...scmer) scmer:
value = p(args...)
case proc:
en := &env{make(vars), p.en}
switch params := p.params.(type) {
case []scmer:
for i, param := range params {
en.vars[param.(symbol)] = args[i]
}
default:
en.vars[params.(symbol)] = args
}
value = eval(p.body, en)
default:
log.Println("Unknown procedure type - APPLY", p)
}
return
}
type proc struct {
params, body scmer
en *env
}
/*
Environments
*/
type vars map[symbol]scmer
type env struct {
vars
outer *env
}
func (e *env) Find(s symbol) *env {
if _, ok := e.vars[s]; ok {
return e
} else {
return e.outer.Find(s)
}
}
/*
Primitives
*/
var globalenv env
func init() {
globalenv = env{
vars{ //aka an incomplete set of compiled-in functions
"+": func(a ...scmer) scmer {
v := a[0].(number)
for _, i := range a[1:] {
v += i.(number)
}
return v
},
"-": func(a ...scmer) scmer {
v := a[0].(number)
for _, i := range a[1:] {
v -= i.(number)
}
return v
},
"*": func(a ...scmer) scmer {
v := a[0].(number)
for _, i := range a[1:] {
v *= i.(number)
}
return v
},
"/": func(a ...scmer) scmer {
v := a[0].(number)
for _, i := range a[1:] {
v /= i.(number)
}
return v
},
"<=": func(a ...scmer) scmer {
return a[0].(number) <= a[1].(number)
},
"equal?": func(a ...scmer) scmer {
return reflect.DeepEqual(a[0], a[1])
},
"cons": func(a ...scmer) scmer {
switch car := a[0]; cdr := a[1].(type) {
case []scmer:
return append([]scmer{car}, cdr...)
default:
return []scmer{car, cdr}
}
},
"car": func(a ...scmer) scmer {
return a[0].([]scmer)[0]
},
"cdr": func(a ...scmer) scmer {
return a[0].([]scmer)[1:]
},
"list": eval(read(
"(lambda z z)"),
&globalenv),
},
nil}
}
/*
Parsing
*/
//symbols, numbers, expressions, procedures, lists, ... all implement this interface, which enables passing them along in the interpreter
type scmer interface{}
type symbol string //symbols are represented by strings
type number float64 //numbers by float64
func read(s string) (expression scmer) {
tokens := tokenize(s)
return readFrom(&tokens)
}
//Syntactic Analysis
func readFrom(tokens *[]string) (expression scmer) {
//pop first element from tokens
token := (*tokens)[0]
*tokens = (*tokens)[1:]
switch token {
case "(": //a list begins
L := make([]scmer, 0)
for (*tokens)[0] != ")" {
if i := readFrom(tokens); i != symbol("") {
L = append(L, i)
}
}
*tokens = (*tokens)[1:]
return L
default: //an atom occurs
if f, err := strconv.ParseFloat(token, 64); err == nil {
return number(f)
} else {
return symbol(token)
}
}
}
//Lexical Analysis
func tokenize(s string) []string {
return strings.Split(
strings.Replace(strings.Replace(s, "(", "( ",
-1), ")", " )",
-1), " ")
}
/*
Interactivity
*/
func String(v scmer) string {
switch v := v.(type) {
case []scmer:
l := make([]string, len(v))
for i, x := range v {
l[i] = String(x)
}
return "(" + strings.Join(l, " ") + ")"
default:
return fmt.Sprint(v)
}
}
func Repl() {
scanner := bufio.NewScanner(os.Stdin)
for fmt.Print("> "); scanner.Scan(); fmt.Print("> ") {
fmt.Println("==>", String(eval(read(scanner.Text()), &globalenv)))
}
}
