government / eval / eval.go

@ 844f0e3dd48aea4963c188d8ad2ed9749ed3e7f0 | history


package eval

import "government/sexpr"

// specialForm receives its operands unevaluated and decides itself which of
// them to evaluate. That is the whole difference from a function, and the
// reason if cannot be one: a function's arguments are all evaluated before
// it runs, so both branches would run.
//
// A form finishes either with a value or with a tail expression: the
// expression whose value is the form's value, such as the chosen branch of
// an if. Eval evaluates a tail expression by looping rather than by calling
// itself, which is what makes tail calls proper.
type specialForm func(operands []sexpr.Value, env *Env) (outcome, error)

type outcome struct {
	value sexpr.Value
	tail  sexpr.Value // if non-nil, continue with tail in env
	env   *Env
}

func done(v sexpr.Value) (outcome, error) { return outcome{value: v}, nil }

func tailIn(expr sexpr.Value, env *Env) (outcome, error) {
	return outcome{tail: expr, env: env}, nil
}

var specialForms map[sexpr.Symbol]specialForm

func init() {
	specialForms = map[sexpr.Symbol]specialForm{
		"quote":  evalQuote,
		"if":     evalIf,
		"lambda": evalLambda,
		"define": evalMisplacedDefine,
		"and":    evalAnd,
		"or":     evalOr,
	}
}

// Eval evaluates expr in env.
//
// Atoms other than symbols evaluate to themselves. A symbol evaluates to its
// binding. A non-empty list is either a special form, chosen by its head
// symbol, or a function call.
//
// Expressions in tail position (an if branch, the last operand of and/or,
// the last form of a closure body) replace expr and env and go round the
// loop again. A tail-recursive function therefore runs in constant Go
// stack: each call reuses this frame instead of nesting a new one. Only
// conditions, arguments and non-final body forms are evaluated by nested
// calls, and those return before the loop continues.
func Eval(expr sexpr.Value, env *Env) (sexpr.Value, error) {
	for {
		var list *sexpr.Pair
		switch x := expr.(type) {
		case sexpr.Symbol:
			return evalSymbol(x, env)
		case *sexpr.Pair:
			list = x
		default:
			return expr, nil
		}

		items, ok := properList(list)
		if !ok {
			return nil, at(errorf(ErrSyntax, "cannot evaluate improper list %s", sexpr.Print(list)), list)
		}
		if head, ok := items[0].(sexpr.Symbol); ok {
			if form, ok := specialForms[head]; ok {
				out, err := form(items[1:], env)
				if err != nil {
					return nil, at(err, list)
				}
				if out.tail == nil {
					return out.value, nil
				}
				expr, env = out.tail, out.env
				continue
			}
		}

		f, args, err := evalCall(items, env)
		if err != nil {
			return nil, at(err, list)
		}
		switch f := f.(type) {
		case *Builtin:
			if err := checkArity(f, len(args)); err != nil {
				return nil, at(err, list)
			}
			v, err := f.fn(args)
			return v, at(err, list)
		case *Closure:
			if expr, env, err = enterClosure(f, args); err != nil {
				return nil, at(err, list)
			}
		default:
			panic("eval: unknown function type")
		}
	}
}

func evalSymbol(name sexpr.Symbol, env *Env) (sexpr.Value, error) {
	if _, ok := specialForms[name]; ok {
		return nil, errorf(ErrSpecialForm, "%s is a special form, not a value", name)
	}
	b := env.binding(name)
	switch {
	case b == nil:
		return nil, errorf(ErrUnbound, "no statute for symbol %s", name)
	case b.pending:
		return nil, errorf(ErrUnbound, "%s is used before its definition is complete", name)
	}
	return b.value, nil
}

// evalCall evaluates the head, then the arguments left to right. Every
// argument is evaluated before the call; special forms exist for the cases
// where that is wrong.
func evalCall(items []sexpr.Value, env *Env) (sexpr.Function, []sexpr.Value, error) {
	head, err := Eval(items[0], env)
	if err != nil {
		return nil, nil, err
	}
	f, ok := head.(sexpr.Function)
	if !ok {
		return nil, nil, errorf(ErrNotAFunction, "%s is not a function", sexpr.Print(head))
	}
	args := make([]sexpr.Value, len(items)-1)
	for i, item := range items[1:] {
		if args[i], err = Eval(item, env); err != nil {
			return nil, nil, err
		}
	}
	return f, args, nil
}

// (quote d) returns d without evaluating it.
func evalQuote(operands []sexpr.Value, env *Env) (outcome, error) {
	if len(operands) != 1 {
		return outcome{}, errorf(ErrSyntax, "quote takes 1 operand, got %d", len(operands))
	}
	return done(operands[0])
}

// (if c a b) continues with a unless c is F, else with b. (if c a) gives ()
// when c is F. Only the chosen branch is evaluated, and it is in tail
// position.
func evalIf(operands []sexpr.Value, env *Env) (outcome, error) {
	if len(operands) != 2 && len(operands) != 3 {
		return outcome{}, errorf(ErrSyntax, "if takes 2 or 3 operands, got %d", len(operands))
	}
	c, err := Eval(operands[0], env)
	if err != nil {
		return outcome{}, err
	}
	if isTrue(c) {
		return tailIn(operands[1], env)
	}
	if len(operands) == 3 {
		return tailIn(operands[2], env)
	}
	return done(sexpr.Nil)
}

// isTrue implements Scheme truthiness: F is the only false value.
func isTrue(v sexpr.Value) bool {
	b, ok := v.(sexpr.Bool)
	return !ok || bool(b)
}

// properList returns the elements of a list that ends in (), or false if
// the list ends in anything else. It runs on every list the evaluator
// meets, so it measures the list first and allocates once.
func properList(v sexpr.Value) ([]sexpr.Value, bool) {
	n := 0
	rest := v
	for {
		p, ok := rest.(*sexpr.Pair)
		if !ok {
			break
		}
		n++
		rest = p.Cdr
	}
	if rest != sexpr.Value(sexpr.Nil) {
		return nil, false
	}
	items := make([]sexpr.Value, n)
	for i := range items {
		p := v.(*sexpr.Pair)
		items[i] = p.Car
		v = p.Cdr
	}
	return items, true
}