government / eval / eval.go

@ fa08368c0d3c24c336bb3fd79706c46fc8e2fd77 | 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.
type specialForm func(operands []sexpr.Value, env *Env) (sexpr.Value, error)

var specialForms map[sexpr.Symbol]specialForm

func init() {
	specialForms = map[sexpr.Symbol]specialForm{
		"quote": evalQuote,
		"if":    evalIf,
	}
}

// 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.
func Eval(expr sexpr.Value, env *Env) (sexpr.Value, error) {
	switch x := expr.(type) {
	case sexpr.Symbol:
		return evalSymbol(x, env)
	case *sexpr.Pair:
		return evalList(x, env)
	}
	return expr, nil
}

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)
	}
	v, ok := env.Lookup(name)
	if !ok {
		return nil, errorf(ErrUnbound, "no statute for symbol %s", name)
	}
	return v, nil
}

func evalList(list *sexpr.Pair, env *Env) (sexpr.Value, error) {
	items, ok := properList(list)
	if !ok {
		return nil, errorf(ErrSyntax, "cannot evaluate improper list %s", sexpr.Print(list))
	}
	if head, ok := items[0].(sexpr.Symbol); ok {
		if form, ok := specialForms[head]; ok {
			return form(items[1:], env)
		}
	}
	return evalCall(items, env)
}

// evalCall evaluates the head, then the arguments left to right, then
// applies the function. 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.Value, error) {
	head, err := Eval(items[0], env)
	if err != nil {
		return nil, err
	}
	f, ok := head.(sexpr.Function)
	if !ok {
		return 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, err
		}
	}
	return apply(f, args)
}

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

// (if c a b) evaluates a unless c is F, else b. (if c a) gives () when c is
// F. Only the chosen branch is evaluated.
func evalIf(operands []sexpr.Value, env *Env) (sexpr.Value, error) {
	if len(operands) != 2 && len(operands) != 3 {
		return nil, errorf(ErrSyntax, "if takes 2 or 3 operands, got %d", len(operands))
	}
	c, err := Eval(operands[0], env)
	if err != nil {
		return nil, err
	}
	if isTrue(c) {
		return Eval(operands[1], env)
	}
	if len(operands) == 3 {
		return Eval(operands[2], env)
	}
	return sexpr.Nil, 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.
func properList(v sexpr.Value) ([]sexpr.Value, bool) {
	var items []sexpr.Value
	for {
		switch x := v.(type) {
		case sexpr.Empty:
			return items, true
		case *sexpr.Pair:
			items = append(items, x.Car)
			v = x.Cdr
		default:
			return nil, false
		}
	}
}