@ 60772087cdbbe3e7543eaf73a6f0ffc9a26570c7 | history
package eval
import (
"math"
"government/sexpr"
)
// The numeric tower has two levels: Int below Float. An operation on two
// Ints gives an Int; if either operand is a Float, both are treated as
// Floats and so is the result. Each step of a fold is promoted separately,
// so (+ 1 2 3.0) adds 1 and 2 as Ints, then 3 and 3.0 as Floats.
//
// Results never wrap or go non-finite: integer overflow, division by zero
// and NaN or infinite floats are all errors.
type binaryOp struct {
name string
ints func(a, b int64) (int64, bool) // false on overflow
floats func(a, b float64) float64
}
func add(args []sexpr.Value) (sexpr.Value, error) {
return fold(opAdd, sexpr.Int(0), args)
}
func multiply(args []sexpr.Value) (sexpr.Value, error) {
return fold(opMul, sexpr.Int(1), args)
}
// (- x) is 0 - x; with more arguments, - subtracts from the first.
func subtract(args []sexpr.Value) (sexpr.Value, error) {
if len(args) == 1 {
return foldFrom(opSub, sexpr.Int(0), args, 0)
}
return foldFrom(opSub, args[0], args[1:], 1)
}
// (/ x) is 1 / x; with more arguments, / divides the first by the rest.
func divide(args []sexpr.Value) (sexpr.Value, error) {
if len(args) == 1 {
return foldFrom(opDiv, sexpr.Int(1), args, 0)
}
return foldFrom(opDiv, args[0], args[1:], 1)
}
var (
opAdd = binaryOp{"+", checkedAdd, func(a, b float64) float64 { return a + b }}
opSub = binaryOp{"-", checkedSub, func(a, b float64) float64 { return a - b }}
opMul = binaryOp{"*", checkedMul, func(a, b float64) float64 { return a * b }}
opDiv = binaryOp{"/", checkedDiv, func(a, b float64) float64 { return a / b }}
)
func fold(op binaryOp, start sexpr.Value, args []sexpr.Value) (sexpr.Value, error) {
return foldFrom(op, start, args, 0)
}
// foldFrom combines acc with each of args in turn. offset is the position
// of args[0] in the original call, so type errors name the right argument.
func foldFrom(op binaryOp, acc sexpr.Value, args []sexpr.Value, offset int) (sexpr.Value, error) {
if offset == 1 {
if err := checkNumber(op.name, 0, acc); err != nil {
return nil, err
}
}
for i, arg := range args {
if err := checkNumber(op.name, offset+i, arg); err != nil {
return nil, err
}
var err error
if acc, err = applyBinary(op, acc, arg); err != nil {
return nil, err
}
}
return acc, nil
}
func applyBinary(op binaryOp, a, b sexpr.Value) (sexpr.Value, error) {
ai, aIsInt := a.(sexpr.Int)
bi, bIsInt := b.(sexpr.Int)
if aIsInt && bIsInt {
if op.name == "/" && bi == 0 {
return nil, errorf(ErrArith, "division by zero")
}
r, ok := op.ints(int64(ai), int64(bi))
if !ok {
return nil, errorf(ErrArith, "integer overflow in %s", op.name)
}
return sexpr.Int(r), nil
}
af, bf := toFloat(a), toFloat(b)
if op.name == "/" && bf == 0 {
return nil, errorf(ErrArith, "division by zero")
}
r := op.floats(af, bf)
if math.IsInf(r, 0) || math.IsNaN(r) {
return nil, errorf(ErrArith, "float overflow in %s", op.name)
}
return sexpr.Float(r), nil
}
func checkNumber(fn string, position int, v sexpr.Value) error {
switch v.(type) {
case sexpr.Int, sexpr.Float:
return nil
}
return errorf(ErrType, "argument %d of %s must be a number, got %s", position+1, fn, sexpr.Print(v))
}
func toFloat(v sexpr.Value) float64 {
if i, ok := v.(sexpr.Int); ok {
return float64(i)
}
return float64(v.(sexpr.Float))
}
// Overflow checks without a wider integer type. A signed sum overflows
// exactly when both operands have the same sign and the result's sign
// differs; the XOR expressions test that with the sign bit.
func checkedAdd(a, b int64) (int64, bool) {
s := a + b
return s, (a^s)&(b^s) >= 0
}
func checkedSub(a, b int64) (int64, bool) {
d := a - b
return d, (a^b)&(a^d) >= 0
}
func checkedMul(a, b int64) (int64, bool) {
if a == 0 || b == 0 {
return 0, true
}
if (a == -1 && b == math.MinInt64) || (b == -1 && a == math.MinInt64) {
return 0, false
}
p := a * b
return p, p/b == a
}
// Integer division truncates toward zero: (/ -7 2) is -3. The only
// overflowing case is MinInt64 / -1, whose true result is MaxInt64 + 1.
func checkedDiv(a, b int64) (int64, bool) {
if a == math.MinInt64 && b == -1 {
return 0, false
}
return a / b, true
}