@ 9691322d33532d2feea494209d4df63e32ee99be | history
package eval
import (
"nmyk.io/government/builtin"
"nmyk.io/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
}
// form is a special form's implementation with its spec, which says how
// many operands it takes.
type form struct {
spec builtin.Spec
run specialForm
}
var specialForms map[sexpr.Symbol]form
// init pairs each special form in package builtin with its
// implementation. (It cannot be a plain initializer: the implementations
// call Eval, which reads specialForms.)
func init() {
impls := map[string]specialForm{
"quote": evalQuote,
"if": evalIf,
"lambda": evalLambda,
"define": evalMisplacedDefine,
"and": evalAnd,
"or": evalOr,
}
specialForms = map[sexpr.Symbol]form{}
for _, spec := range builtin.All {
if spec.Kind != builtin.SpecialForm {
continue
}
run, ok := impls[spec.Name]
if !ok {
panic("eval: special form " + spec.Name + " has no implementation")
}
specialForms[sexpr.Symbol(spec.Name)] = form{spec, run}
}
if len(specialForms) != len(impls) {
panic("eval: an implemented special form is not in package builtin")
}
}
// checkOperands applies a special form's operand count from its spec.
func checkOperands(spec builtin.Spec, n int) error {
if err := spec.CheckCount(n, "operand"); err != nil {
return errorf(ErrSyntax, "%v", err)
}
return nil
}
// 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 {
if err := checkOperands(form.spec, len(items)-1); err != nil {
return nil, at(err, list)
}
out, err := form.run(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) {
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) {
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
}