今回は「関数」を値として扱うことができるように電卓プログラムを改良し、新しい機能として「匿名関数 (クロージャ)」を追加しましょう。関数を値として扱うことができると、高階関数を使用することができます。また、クロージャをサポートすると、効率を度外視すれば簡単なデータ構造、たとえば「連結リスト」を作ることもできます。
関数を値として扱うため、インターフェース Func の定義を修正します。
リスト : 関数型 Func の定義
type Func interface {
Value
Expr
Argc() int
}
// 組み込み関数
type Func1 func(float64) float64
func (f Func1) Argc() int { return 1 }
func (f Func1) isTrue() bool { return true }
func (f Func1) Eval(_ *Env) Value { return f }
func (f Func1) String() string { return "<Function1>" }
Func にインターフェース Value と Expr を埋め込みます。そして、具体的な関数型 Func1, Func2, FuncV1, FuncV2, FuncU にメソッド isTrue, Eval を追加します。isTrue は true を返し、Eval はレシーバをそのまま返すだけです。これで関数を値として扱うことができます。あとはメソッド String を定義して、Func1 ならば "<Function1>" を返すようにします。また、組み込み関数に関数型を判定する述語 isFunc を追加します。
次は、匿名関数の構文を説明します。
fn(仮引数, ...) 式1, 式2, ... end
匿名関数 (fn 式) はキーワード fn で定義します。let 式と fn 式 を使って局所関数を定義することもできます。構文の最後は end になります。文法は次のようになります。
[EBNF]
因子 = 整数 | 実数 | 文字列 | ("+" | "-" | "not"), 因子 | "(", 式, ")" | 変数 | 関数 | fn式 |
関数, "(", 引数リスト, ")" | 変数, "(", [引数リスト], ")" | fn式, "(", [引数リスト], ")" |
ベクタ生成式 | 変数, "[", 式, "]", {"[", 式, "]"} |
if式 | begin式 | while式 | let式.
fn式 = "fn", "(", [仮引数リスト], ")", 式, { ",", 式 }, "end".
変数 = 識別子
仮引数リスト = 変数, { ",", 変数 }.
引数リスト = 式, { ",", 式 }.
[注意] 数値と識別子の定義は省略
今回は変数名のあとに左カッコがある場合、それも関数呼び出しと判断することにします。実行時に変数を評価して、その値が「関数」でなければエラーを送出します。また、匿名関数 (fn式) の場合も、end の後ろに左カッコがあると、それを関数として呼び出します。また、関数のあとにカッコが付いていない場合、つまり関数呼び出しでなければ、その関数の値を返すことにします。これで、組み込み関数やユーザ定義関数を変数にセットしたり、関数の引数に渡すことができます。
関数は値なので変数 (引数) だけではなくベクタにも格納することができます。今回の関数呼び出しの方法では、ベクタに格納された関数を呼び出すとき、ベクタの値を変数に取り出してから、その関数を呼び出すことになります。それでは面倒なので、fn 式といっしょに「call 式」を追加することにします。call 式の構文を示します。
call(式, 引数1, 引数2, ...)
call 式は第 1 引数の式を評価して、それが関数値であれば、残りの引数をその関数に渡して評価します。call 式は呼び出した関数の返り値をそのまま返します。式は変数でも関数でもベクタのアクセスでもかまいません。もしも、その結果が関数値でなければエラーを送出します。これは Common Lisp の関数 funcall と同じ機能です。
次は字句解析を修正します。
リスト : キーワードとトークンの追加
// キーワード
const (
DEF = -(iota+10)
・・・省略・・・
LET
IN
FN
CALL
)
// キーワード表
var keyTable = make(map[string]rune)
func initKeyTable() {
keyTable["def"] = DEF
・・・省略・・・
keyTable["let"] = LET
keyTable["in"] = IN
keyTable["fn"] = FN
keyTable["call"] = CALL
}
キーワード fn を表すトークンが FN で、call を表すトークンが CALL です。あとは keyTable に FN と CALL をセットするだけです。
次は構文解析の処理を修正します。
リスト : 構文解析の処理
// 因子
func factor(lex *Lex) Expr {
switch lex.Token {
・・・省略・・・
case FN:
lex.getToken()
xs := getParameter(lex)
body := makeBegin(lex)
clo := newClo(xs, body)
if lex.Token == '(' {
ys := getArgs(lex)
if len(xs) != len(ys) {
panic(fmt.Errorf("wrong number of arguments: fn"))
}
return newAppV(clo, ys)
}
return clo
case CALL:
lex.getToken()
xs := getArgs(lex)
if len(xs) == 0 {
panic(fmt.Errorf("wrong number of arguments: call"))
}
return newAppV(xs[0], xs[1:])
・・・省略
case scanner.Ident:
name := lex.TokenText()
lex.getToken()
if name == "quit" {
panic(name)
}
v, ok := funcTable[name]
if ok {
if lex.Token == '(' {
xs := getArgs(lex)
if len(xs) != v.Argc() {
panic(fmt.Errorf("wrong number of arguments: %v", name))
}
return newApp(v, xs)
} else {
// 関数値をそのまま返す
return v
}
} else if lex.Token == '[' {
return newRef(Variable(name), getIndex(lex))
} else if lex.Token == '(' {
// 変数に格納されている関数を呼び出す
return newApp(Variable(name), getArgs(lex))
} else {
return Variable(name)
}
default:
panic(fmt.Errorf("unexpected token: %v", lex.TokenText()))
}
}
トークンが FN ならば匿名関数の生成を表す構造体 Clo を返します。最初に、getParameter で仮引数リストを求めて変数 xs にセットし、makebegin を呼び出して本体を求めて変数 body にセットします。そして、xs と body を関数 newClo に渡して Clo を生成し、変数 clo にセットします。
次のトークンが '(' の場合、匿名関数の呼び出しです。getArgs で実引数リストを求めて変数 ys にセットします。実引数と仮引数の個数が合わない場合は panic でエラーを送出します。そうでなければ、clo と ys を newAppV に渡して構造体 AppV を生成して返します。
構造体 AppV は App のフィールド変数 fn の型を Func から Expr に変更したものです。AppV は fn を Eval で評価して、それが関数値であれば、App と同様に関数を呼び出します。Clo は Func ではありませんが、Clo を評価すると「クロージャ (closure)」が生成されるので、それを関数として呼び出します。関数呼び出しではない場合は clo をそのまま返します。
トークンが Call の場合、カッコの中の引数を getArgs で取り出します。もしも、引数の個数が 0 の場合は panic でエラーを送出します。そうでなければ、引数 xs を先頭要素と残りの要素に分けて newAppV に渡します。
トークンが scanner.Indent で識別子 name が関数の場合、name の後ろにカッコがない場合は、関数の値 v をそのまま返します。name が関数ではなく、その後ろにカッコがある場合、それを関数呼び出しとして扱います。name を変数に変換して実引数リストといっしょに newApp に渡します。
次は匿名関数の実体 (クロージャ) を生成する処理を作ります。
リスト : fn 式の処理
// クロージャ
type Clo struct {
xs []Variable
body Expr
}
func newClo(xs []Variable, body Expr) *Clo {
return &Clo{xs, body}
}
func (a *Clo) Eval(env *Env) Value {
return &FuncC{a.xs, a.body, env}
}
type FuncC struct {
xs []Variable
body Expr
env *Env
}
func (f *FuncC) Argc() int { return len(f.xs) }
func (_ *FuncC) isTrue() bool { return true }
func (f *FuncC) Eval(_ *Env) Value { return f }
func (_ *FuncC) String() string { return "<Closure>" }
構造体 Clo のフィールド変数 xs が仮引数リスト、body が関数本体を格納します。構造体 FuncC が匿名関数の実体で、これが「クロージャ (closure)」になります。フィールド変数 xs が仮引数リスト、body が関数本体、env が匿名関数を生成したときに有効な局所変数の環境です。メソッド Eval はレシーバ a の xs, body と環境 env を FuncC に格納して返すだけです。FuncC は関数なので、必要なメソッド Argc, isTrue, Eval, String を定義します。
次は関数を評価するための構造体 AppV を作ります。
リスト : 関数の評価
type App struct {
fn Func
xs []Expr
}
func newApp(fn Func, xs []Expr) *App {
return &App{fn, xs}
}
type AppV struct {
fn Expr
xs []Expr
}
func newAppV(fn Expr, xs []Expr) *AppV {
return &AppV{fn, xs}
}
// クロージャ用
func addBindingClo(xs []Variable, es []Expr, env, clo *Env) *Env {
for i := 0; i < len(xs); i++ {
clo = newEnv(xs[i], es[i].Eval(env), clo)
}
return clo
}
// 評価
func appFunc(fn Func, xs []Expr, env *Env) Value {
switch f := fn.(type) {
case Func1:
x := valueToFloat(xs[0].Eval(env))
return Flt(f(x))
case Func2:
x := valueToFloat(xs[0].Eval(env))
y := valueToFloat(xs[1].Eval(env))
return Flt(f(x, y))
case FuncV1:
return f(xs[0].Eval(env))
case FuncV2:
return f(xs[0].Eval(env), xs[1].Eval(env))
case *FuncU:
return f.body.Eval(makeBinding(f.xs, xs, env))
case *FuncC:
return f.body.Eval(addBindingClo(f.xs, xs, env, f.env))
default:
panic(fmt.Errorf("%v is not function", f))
}
}
func (a *App) Eval(env *Env) Value {
return appFunc(a.fn, a.xs, env)
}
func (a *AppV) Eval(env *Env) Value {
v := a.fn.Eval(env)
fn, ok := v.(Func)
if !ok {
panic(fmt.Errorf("%v is not function", v))
}
if fn.Argc() != len(a.xs) {
panic(fmt.Errorf("wrong number of arguments"))
}
return appFunc(fn, a.xs, env)
}
構造体 AppV はフィールド変数 fn の型が Expr に変わっただけです。App の Eval の処理は関数 appFunc で行います。組み込み関数とユーザ定義関数の処理は今までと同じです。*FuncC の場合、クロージャに格納されている環境 f.env に、新しい変数束縛を追加します。
関数 addBindingClo はクロージャの環境 clo に新しい変数束縛を追加して返すだけです。これでクロージャ内に保存された環境にアクセスすることができます。なお、es の式を評価するときの環境は第 3 引数の env であることに注意してください。
AppV の Eval は、最初にフィールド変数 fn を Eval で評価し、その値 v を型アサーションでチェックします。関数はでない、または引数の個数が合わない場合は panic でエラーを送出します。あとは、appFunc を呼び出すだけです。
あとの修正は簡単なので説明は割愛します。詳細はプログラムリストをお読みください。
それでは実際に試してみましょう。
Calc> sqrt; <Function1> Calc> atan2; <Function2> Calc> isFunc(sqrt); 1 Calc> a = sqrt; <Function1> Calc> a(10); 3.1622776601683795 Calc> b = 10; 10 Calc> b(1); 10 is not function Calc> fn(a, b) a + b end; <Closure> Calc> fn(a, b) a + b end(10, 20); 30 Calc> let add = fn(a, b) a + b end in add(100, 200) end; 300 Calc> def add(a, b) a + b end add Calc> c = [sqrt, add]; [<Function1> <add>] Calc> call(c[0], 10); 3.1622776601683795 Calc> call(c[1], 10, 20); 30
関数の値を取り出して変数にセットし、それを呼び出すことができます。fn 式で関数 (クロージャ) が生成し、それを直接呼び出すこともできます。また、let 式の局所変数に匿名関数で生成したクロージャをセットすることで、局所関数として呼び出すこともできます。call 式も正常に動作していますね。
高階関数も簡単に定義できます。
Calc> def map(f, xs) let ys = vector(len(xs), 0), i = 0 in while i < len(xs) do ys[i] = f(xs[i]), i = i + 1 end, ys end end map Calc> map(fn(a) a * a end, [1,2,3,4,5]); [1 4 9 16 25] Calc> map(sqrt, [1,2,3,4,5]); [1 1.4142135623730951 1.7320508075688772 2 2.23606797749979]
最後にクロージャらしい機能を使ってみましょう。
Calc> def makeAdder(x) fn(y) x + y end end makeAdder Calc> add10 = makeAdder(10); <Closure> Calc> add10(20); 30 Calc> add10(200); 210 Calc> add100 = makeAdder(100); <Closure> Calc> add100(200); 300 Calc> add100(1000); 1100
makeAdder は x を足し算する関数を生成して返します。makeAdder(10) の返り値を add10 にセットすると、add10 は引数に 10 を加算する関数になります。また、makeAdder(100) は引数に 100 を加算する関数を返します。どちらも正常に動作していますね。
今回はここまでです。次回はクロージャを使って「連結リスト」を作ってみましょう。
//
// calc7.go : 電卓プログラム (関数値、匿名関数を追加)
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import (
"fmt"
"os"
"math"
"text/scanner"
)
// キーワード
const (
DEF = -(iota+10)
END
IF
THEN
ELSE
NOT
AND
OR
EQ
NE
LT
GT
LE
GE
BGN
WHL
DO
LET
IN
FN
CALL
)
// キーワード表
var keyTable = make(map[string]rune)
func initKeyTable() {
keyTable["def"] = DEF
keyTable["end"] = END
keyTable["if"] = IF
keyTable["then"] = THEN
keyTable["else"] = ELSE
keyTable["and"] = AND
keyTable["or"] = OR
keyTable["not"] = NOT
keyTable["begin"] = BGN
keyTable["while"] = WHL
keyTable["do"] = DO
keyTable["let"] = LET
keyTable["in"] = IN
keyTable["fn"] = FN
keyTable["call"] = CALL
}
// 値
type Value interface {
isTrue() bool
}
// 変数
type Variable string
// 局所変数の環境
type Env struct {
name Variable
val Value
next *Env
}
// 構文木
type Expr interface {
Eval(*Env) Value
}
// 数
type Num interface {
Value
Expr
neg() Value
sign() int
add(Value) Value
sub(Value) Value
mul(Value) Value
div(Value) Value
}
// 比較
type Cmp interface {
compare(Value) int
}
//
// 数値
//
type Int int64
type Flt float64
// エラー
func errorNum(mes string, v Value) error {
return fmt.Errorf("%sNumber required, %v", mes, v)
}
func errorInt(mes string, v Value) error {
return fmt.Errorf("%sInteger required, %v", mes, v)
}
// Value の実装
func (n Int) isTrue() bool { return n != 0 }
func (n Flt) isTrue() bool { return n != 0.0 }
// Expr の実装
func (e Int) Eval(_ *Env) Value { return e }
func (e Flt) Eval(_ *Env) Value { return e }
// 符号の反転
func (n Int) neg() Value { return -n }
func (n Flt) neg() Value { return -n }
// 符号を求める
func (n Int) sign() int {
switch {
case n > 0: return 1
case n < 0: return -1
default: return 0
}
}
func (n Flt) sign() int {
switch {
case n > 0.0: return 1
case n < 0.0: return -1
default: return 0
}
}
// 四則演算
func (n Int) add(x Value) Value {
switch m := x.(type) {
case Int: return n + m
case Flt: return Flt(n) + m
}
panic(errorNum("+, ", x))
}
func (n Flt) add(x Value) Value {
switch m := x.(type) {
case Int: return n + Flt(m)
case Flt: return n + m
}
panic(errorNum("+, ", x))
}
func (n Int) sub(x Value) Value {
switch m := x.(type) {
case Int: return n - m
case Flt: return Flt(n) - m
}
panic(errorNum("-, ", x))
}
func (n Flt) sub(x Value) Value {
switch m := x.(type) {
case Int: return n - Flt(m)
case Flt: return n - m
}
panic(errorNum("-, ", x))
}
func (n Int) mul(x Value) Value {
switch m := x.(type) {
case Int: return n * m
case Flt: return Flt(n) * m
}
panic(errorNum("*, ", x))
}
func (n Flt) mul(x Value) Value {
switch m := x.(type) {
case Int: return n * Flt(m)
case Flt: return n * m
}
panic(errorNum("*, ", x))
}
func (n Int) div(x Value) Value {
switch m := x.(type) {
case Int: return n / m
case Flt: return Flt(n) / m
}
panic(errorNum("/, ", x))
}
func (n Flt) div(x Value) Value {
switch m := x.(type) {
case Int: return n / Flt(m)
case Flt: return n / m
}
panic(errorNum("/, ", x))
}
// Cmp の実装
func (n Int) compare(x Value) int {
switch m := x.(type) {
case Int: return (n - m).sign()
case Flt: return (Flt(n) - m).sign()
}
panic(errorNum("compare, ", x))
}
func (n Flt) compare(x Value) int {
switch m := x.(type) {
case Int: return (n - Flt(m)).sign()
case Flt: return (n - m).sign()
}
panic(errorNum("compare, ", x))
}
//
// 文字列
//
type Str string
// エラー
func errorStr(mes string, v Value) error {
return fmt.Errorf("%sString required, %v", mes, v)
}
// Value, Expr, Cmp の実装
func (_ Str) isTrue() bool { return true }
func (s Str) Eval(_ *Env) Value { return s }
func (n Str) compare(x Value) int {
m, ok := x.(Str)
if !ok {
panic(errorStr("compare, ", x))
}
switch {
case n > m: return 1
case n < m: return -1
default: return 0
}
}
//
// 配列
//
type Vec []Value
// エラー
func errorVec(mes string, v Value) error {
return fmt.Errorf("%sVector required , %v", mes, v)
}
// Value の実装
func (_ Vec) isTrue() bool { return true }
// ベクタ生成用構文木
type Crv struct {
xs []Expr
}
func newCrv(xs []Expr) *Crv {
return &Crv{xs}
}
// ベクタの生成
func (a *Crv) Eval(env *Env) Value {
v := make(Vec, len(a.xs))
for i := 0; i < len(a.xs); i++ {
v[i] = a.xs[i].Eval(env)
}
return v
}
// ベクタの参照
type Ref struct {
name Variable
idxs []Expr
}
func newRef(name Variable, idxs []Expr) *Ref {
return &Ref{name, idxs}
}
// アクセス位置を求める
func getPos(a *Ref, env *Env) *Value {
v := a.name.Eval(env)
for k := 0; ; k++ {
xs, ok := v.(Vec)
if !ok {
panic(errorVec("", v))
}
y := a.idxs[k].Eval(env)
i := toInt(y)
if j := int(i); j < 0 || j >= len(xs) {
panic(fmt.Errorf("Out of Range, %v, %v", xs, j))
} else if k == len(a.idxs) - 1 {
return &xs[j]
} else {
v = xs[j]
}
}
}
// 評価
func (a *Ref) Eval(env *Env) Value {
return *getPos(a, env)
}
// ベクタの更新
type Udt struct {
ref *Ref
val Expr
}
func newUdt(ref *Ref, val Expr) *Udt {
return &Udt{ref, val}
}
// 評価
func (a *Udt) Eval(env *Env) Value {
x := getPos(a.ref, env)
v := a.val.Eval(env)
*x = v
return v
}
//
// 変数と環境
//
// 環境の生成
func newEnv(name Variable, val Value, env *Env) *Env {
return &Env{name, val, env}
}
func makeBinding(xs []Variable, es []Expr, env *Env) *Env {
var env1 *Env
for i := 0; i < len(xs); i++ {
env1 = newEnv(xs[i], es[i].Eval(env), env1)
}
return env1
}
// 局所変数を環境に追加
func addBinding(xs []Variable, es []Expr, env *Env) *Env {
for i := 0; i < len(xs); i++ {
env = newEnv(xs[i], es[i].Eval(env), env)
}
return env
}
// クロージャ用
func addBindingClo(xs []Variable, es []Expr, env, clo *Env) *Env {
for i := 0; i < len(xs); i++ {
clo = newEnv(xs[i], es[i].Eval(env), clo)
}
return clo
}
// 局所変数の探索
func lookup(name Variable, env *Env) (Value, bool) {
for ; env != nil; env = env.next {
if name == env.name {
return env.val, true
}
}
return Int(0), false
}
// 局所変数の更新
func update(name Variable, val Value, env *Env) bool {
for ; env != nil; env = env.next {
if name == env.name {
env.val = val
return true
}
}
return false
}
// 大域的な環境
var globalEnv = make(map[Variable]Value)
// 変数の評価
func (v Variable) Eval(env *Env) Value {
// 局所変数の探索
val, ok := lookup(v, env)
if ok {
return val
}
// 大域変数の探索
val, ok = globalEnv[v]
if !ok {
panic(fmt.Errorf("unbound variable, %v", v))
}
return val
}
//
// 単項演算子
//
type Op1 struct {
code rune
expr Expr
}
func newOp1(code rune, e Expr) Expr {
return &Op1{code, e}
}
// bool を Value に変換する
func boolToValue(x bool) Value {
if x {
return Int(1)
} else {
return Int(0)
}
}
// 型変換とチェック
func toNum(v Value) Num {
n, ok := v.(Num)
if !ok {
panic(errorNum("", v))
}
return n
}
// 評価
func (e *Op1) Eval(env *Env) Value {
v := e.expr.Eval(env)
switch e.code {
case '-': return toNum(v).neg()
case '+': return v
case NOT: return boolToValue(!v.isTrue())
default:
panic(fmt.Errorf("invalid Op1 code"))
}
}
//
// 二項演算子
//
type Op2 struct {
code rune
left, right Expr
}
func newOp2(code rune, left, right Expr) Expr {
return &Op2{code, left, right}
}
// 型変換とチェック
func toInt(v Value) Int {
n, ok := v.(Int)
if !ok {
panic(fmt.Errorf("Integer required, %v", v))
}
return n
}
func toCmp(v Value) Cmp {
n, ok := v.(Cmp)
if !ok {
panic(fmt.Errorf("%v is uncomparable type", v))
}
return n
}
// 評価
func (e *Op2) Eval(env *Env) Value {
x := e.left.Eval(env)
y := e.right.Eval(env)
switch e.code {
case '+': return toNum(x).add(y)
case '-': return toNum(x).sub(y)
case '*': return toNum(x).mul(y)
case '/': return toNum(x).div(y)
case '%': return toInt(x) % toInt(y)
case EQ: return boolToValue(toCmp(x).compare(y) == 0)
case NE: return boolToValue(toCmp(x).compare(y) != 0)
case LT: return boolToValue(toCmp(x).compare(y) < 0)
case GT: return boolToValue(toCmp(x).compare(y) > 0)
case LE: return boolToValue(toCmp(x).compare(y) <= 0)
case GE: return boolToValue(toCmp(x).compare(y) >= 0)
default:
panic(fmt.Errorf("invalid Op2 code"))
}
}
//
// 短絡演算子
//
type Ops struct {
code rune
left, right Expr
}
func newOps(code rune, left, right Expr) Expr {
return &Ops{code, left, right}
}
// 評価
func (e *Ops) Eval(env *Env) Value {
x := e.left.Eval(env)
switch e.code {
case AND:
if x.isTrue() {
return e.right.Eval(env)
}
return x
case OR:
if x.isTrue() {
return x
}
return e.right.Eval(env)
default:
panic(fmt.Errorf("invalid Ops code"))
}
}
//
// if
//
type Sel struct {
testForm, thenForm, elseForm Expr
}
func newSel(testForm, thenForm, elseForm Expr) *Sel {
return &Sel{testForm, thenForm, elseForm}
}
func (e *Sel) Eval(env *Env) Value {
if e.testForm.Eval(env).isTrue() {
return e.thenForm.Eval(env)
}
return e.elseForm.Eval(env)
}
//
// while
//
type Whl struct {
testForm, body Expr
}
func newWhl(testForm, body Expr) *Whl {
return &Whl{testForm, body}
}
func (e *Whl) Eval(env *Env) Value {
for e.testForm.Eval(env).isTrue() {
e.body.Eval(env)
}
return Int(0)
}
//
// begin
//
type Bgn struct {
body []Expr
}
func newBgn(xs []Expr) *Bgn {
return &Bgn{xs}
}
func (e *Bgn) Eval(env *Env) Value {
var r Value
for _, expr := range e.body {
r = expr.Eval(env)
}
return r
}
//
// let
//
type Let struct {
vars []Variable
vals []Expr
body Expr
}
func newLet(vars []Variable, vals []Expr, body Expr) *Let {
return &Let{vars, vals, body}
}
func (e *Let) Eval(env *Env) Value {
return e.body.Eval(addBinding(e.vars, e.vals, env))
}
//
// 代入演算子
//
type Agn struct {
name Variable
expr Expr
}
func newAgn(v Variable, e Expr) *Agn {
return &Agn{v, e}
}
func (a *Agn) Eval(env *Env) Value {
val := a.expr.Eval(env)
if !update(a.name, val, env) {
globalEnv[a.name] = val
}
return val
}
//
// 関数
//
type Func interface {
Value
Expr
Argc() int
}
type Func1 func(float64) float64
func (f Func1) Argc() int { return 1 }
func (f Func1) isTrue() bool { return true }
func (f Func1) Eval(_ *Env) Value { return f }
func (f Func1) String() string { return "<Function1>" }
type Func2 func(float64, float64) float64
func (f Func2) Argc() int { return 2 }
func (f Func2) isTrue() bool { return true }
func (f Func2) Eval(_ *Env) Value { return f }
func (f Func2) String() string { return "<Function2>" }
type FuncV1 func(Value) Value
func (f FuncV1) Argc() int { return 1 }
func (f FuncV1) isTrue() bool { return true }
func (f FuncV1) Eval(_ *Env) Value { return f }
func (f FuncV1) String() string { return "<FunctionV1>" }
type FuncV2 func(Value, Value) Value
func (f FuncV2) Argc() int { return 2 }
func (f FuncV2) isTrue() bool { return true }
func (f FuncV2) Eval(_ *Env) Value { return f }
func (f FuncV2) String() string { return "<FunctionV2>" }
// ユーザ定義関数
type FuncU struct {
name string
xs []Variable
body Expr
}
func newFuncU(name string, xs []Variable, body Expr) *FuncU {
return &FuncU{name, xs, body}
}
func (f *FuncU) Argc() int { return len(f.xs) }
func (f *FuncU) isTrue() bool { return true }
func (f *FuncU) Eval(_ *Env) Value { return f }
func (f *FuncU) String() string { return fmt.Sprintf("<%s>", f.name) }
// クロージャ
type Clo struct {
xs []Variable
body Expr
}
func newClo(xs []Variable, body Expr) *Clo {
return &Clo{xs, body}
}
type FuncC struct {
xs []Variable
body Expr
env *Env
}
func (f *FuncC) Argc() int { return len(f.xs) }
func (_ *FuncC) isTrue() bool { return true }
func (f *FuncC) Eval(_ *Env) Value { return f }
func (_ *FuncC) String() string { return "<Closure>" }
func (a *Clo) Eval(env *Env) Value {
return &FuncC{a.xs, a.body, env}
}
//
// 関数呼び出し
//
type App struct {
fn Func
xs []Expr
}
func newApp(fn Func, xs []Expr) *App {
return &App{fn, xs}
}
type AppV struct {
fn Expr
xs []Expr
}
func newAppV(fn Expr, xs []Expr) *AppV {
return &AppV{fn, xs}
}
func valueToFloat(v Value) float64 {
switch x := v.(type) {
case Int: return float64(x)
case Flt: return float64(x)
default:
panic(errorNum("", v))
}
}
// 評価
func appFunc(fn Func, xs []Expr, env *Env) Value {
switch f := fn.(type) {
case Func1:
x := valueToFloat(xs[0].Eval(env))
return Flt(f(x))
case Func2:
x := valueToFloat(xs[0].Eval(env))
y := valueToFloat(xs[1].Eval(env))
return Flt(f(x, y))
case FuncV1:
return f(xs[0].Eval(env))
case FuncV2:
return f(xs[0].Eval(env), xs[1].Eval(env))
case *FuncU:
return f.body.Eval(makeBinding(f.xs, xs, env))
case *FuncC:
return f.body.Eval(addBindingClo(f.xs, xs, env, f.env))
default:
panic(fmt.Errorf("%v is not function", f))
}
}
func (a *App) Eval(env *Env) Value {
return appFunc(a.fn, a.xs, env)
}
func (a *AppV) Eval(env *Env) Value {
v := a.fn.Eval(env)
fn, ok := v.(Func)
if !ok {
panic(fmt.Errorf("%v is not function", v))
}
if fn.Argc() != len(a.xs) {
panic(fmt.Errorf("wrong number of arguments"))
}
return appFunc(fn, a.xs, env)
}
//
// 組み込み関数の初期化
//
var funcTable = make(map[string]Func)
// 値の表示
func print(x Value) Value {
fmt.Print(x)
return x
}
func println(x Value) Value {
fmt.Println(x)
return x
}
// ベクタの生成
func makeVector(n, x Value) Value {
k := toInt(n)
xs := make(Vec, int(k))
for i := 0; i < int(k); i++ {
xs[i] = x
}
return xs
}
func length(v Value) Value {
xs, ok := v.(Vec)
if !ok {
panic(errorVec("len, ", v))
}
return Int(len(xs))
}
func isInt(v Value) Value {
_, ok := v.(Int)
return boolToValue(ok)
}
func isFlt(v Value) Value {
_, ok := v.(Flt)
return boolToValue(ok)
}
func isVec(v Value) Value {
_, ok := v.(Vec)
return boolToValue(ok)
}
func isStr(v Value) Value {
_, ok := v.(Str)
return boolToValue(ok)
}
func isFunc(v Value) Value {
_, ok := v.(Func)
return boolToValue(ok)
}
func initFunc() {
funcTable["sqrt"] = Func1(math.Sqrt)
funcTable["sin"] = Func1(math.Sin)
funcTable["cos"] = Func1(math.Cos)
funcTable["tan"] = Func1(math.Tan)
funcTable["sinh"] = Func1(math.Sinh)
funcTable["cosh"] = Func1(math.Cosh)
funcTable["tanh"] = Func1(math.Tanh)
funcTable["asin"] = Func1(math.Asin)
funcTable["acos"] = Func1(math.Acos)
funcTable["atan"] = Func1(math.Atan)
funcTable["atan2"] = Func2(math.Atan2)
funcTable["exp"] = Func1(math.Exp)
funcTable["pow"] = Func2(math.Pow)
funcTable["log"] = Func1(math.Log)
funcTable["log10"] = Func1(math.Log10)
funcTable["log2"] = Func1(math.Log2)
funcTable["print"] = FuncV1(print)
funcTable["println"] = FuncV1(println)
funcTable["len"] = FuncV1(length)
funcTable["vector"] = FuncV2(makeVector)
funcTable["isInt"] = FuncV1(isInt)
funcTable["isFlt"] = FuncV1(isFlt)
funcTable["isStr"] = FuncV1(isStr)
funcTable["isVec"] = FuncV1(isVec)
funcTable["isFunc"] = FuncV1(isFunc)
}
//
// 字句解析
//
type Lex struct {
scanner.Scanner
Token rune
}
func (lex *Lex) getToken() {
lex.Token = lex.Scan()
switch lex.Token {
case scanner.Ident:
key, ok := keyTable[lex.TokenText()]
if ok {
lex.Token = key
}
case '=':
if lex.Peek() == '=' {
lex.Next()
lex.Token = EQ
}
case '!':
if lex.Peek() == '=' {
lex.Next()
lex.Token = NE
} else {
lex.Token = NOT
}
case '<':
if lex.Peek() == '=' {
lex.Next()
lex.Token = LE
} else {
lex.Token = LT
}
case '>':
if lex.Peek() == '=' {
lex.Next()
lex.Token = GE
} else {
lex.Token = GT
}
}
}
//
// 構文解析
//
// 仮引数の取得
func getParameter(lex *Lex) []Variable {
e := make([]Variable, 0)
if lex.Token != '(' {
panic(fmt.Errorf("'(' expected"))
}
lex.getToken()
if lex.Token == ')' {
lex.getToken()
return e
}
for {
if lex.Token == scanner.Ident {
e = append(e, Variable(lex.TokenText()))
lex.getToken()
switch lex.Token {
case ')':
lex.getToken()
return e
case ',':
lex.getToken()
default:
panic(fmt.Errorf("unexpected token in parameter list"))
}
} else {
panic(fmt.Errorf("unexpected token in parameter list"))
}
}
}
// 引数の取得
func getArgs(lex *Lex) []Expr {
e := make([]Expr, 0)
if lex.Token != '(' {
panic(fmt.Errorf("'(' expected"))
}
lex.getToken()
if lex.Token == ')' {
lex.getToken()
return e
}
for {
e = append(e, expression(lex))
switch lex.Token {
case ')':
lex.getToken()
return e
case ',':
lex.getToken()
default:
panic(fmt.Errorf("unexpected token in argument list"))
}
}
}
// if 式の解析
func makeSel(lex *Lex) Expr {
testForm := expression(lex)
if lex.Token == THEN {
lex.getToken()
thenForm := expression(lex)
switch lex.Token {
case ELSE:
lex.getToken()
elseForm := expression(lex)
if lex.Token != END {
panic(fmt.Errorf("if, 'end' expected"))
}
lex.getToken()
return newSel(testForm, thenForm, elseForm)
case END:
lex.getToken()
return newSel(testForm, thenForm, Int(0))
default:
panic(fmt.Errorf("if, 'else' or 'end' expected"))
}
} else {
panic(fmt.Errorf("if, 'then' expected"))
}
}
// begin 式の解析
func getBody(lex *Lex) []Expr {
body := make([]Expr, 0)
for {
body = append(body, expression(lex))
switch lex.Token {
case ',':
lex.getToken()
default:
return body
}
}
}
func makeBegin(lex *Lex) Expr {
if lex.Token == END {
panic(fmt.Errorf("invalid begin form"))
}
body := getBody(lex)
if lex.Token != END {
panic(fmt.Errorf("'end' expected"))
}
lex.getToken()
return newBgn(body)
}
// while 式の解析
func makeWhile(lex *Lex) Expr {
testForm := expression(lex)
if lex.Token == DO {
lex.getToken()
return newWhl(testForm, makeBegin(lex))
} else {
panic(fmt.Errorf("'do' expected"))
}
}
// let 式の解析
func makeLet(lex *Lex) Expr {
vars := make([]Variable, 0)
vals := make([]Expr, 0)
for {
e := expression(lex)
a, ok := e.(*Agn)
if !ok {
panic(fmt.Errorf("let: invalid assign form"))
}
vars = append(vars, a.name)
vals = append(vals, a.expr)
if lex.Token == IN {
break
} else if lex.Token != ',' {
panic(fmt.Errorf("let, 'in' or ',' expected"))
}
lex.getToken()
}
lex.getToken()
return newLet(vars, vals, makeBegin(lex))
}
// 添字の取得
func getIndex(lex *Lex) []Expr {
xs := make([]Expr, 0)
lex.getToken()
for {
e := expression(lex)
if lex.Token != ']' {
panic(fmt.Errorf("']' expected"))
}
xs = append(xs, e)
lex.getToken()
if lex.Token != '[' {
return xs
}
lex.getToken()
}
}
// 因子
func factor(lex *Lex) Expr {
switch lex.Token {
case '(':
lex.getToken()
e := expression(lex)
if lex.Token != ')' {
panic(fmt.Errorf("')' expected"))
}
lex.getToken()
return e
case '[':
lex.getToken()
xs := getBody(lex)
if lex.Token != ']' {
panic(fmt.Errorf("']' expected"))
}
lex.getToken()
return newCrv(xs)
case '+':
lex.getToken()
return newOp1('+', factor(lex))
case '-':
lex.getToken()
return newOp1('-', factor(lex))
case NOT:
lex.getToken()
return newOp1(NOT, factor(lex))
case IF:
lex.getToken()
return makeSel(lex)
case BGN:
lex.getToken()
return makeBegin(lex)
case WHL:
lex.getToken()
return makeWhile(lex)
case LET:
lex.getToken()
return makeLet(lex)
case FN:
lex.getToken()
xs := getParameter(lex)
body := makeBegin(lex)
clo := newClo(xs, body)
if lex.Token == '(' {
ys := getArgs(lex)
if len(xs) != len(ys) {
panic(fmt.Errorf("wrong number of arguments: fn"))
}
return newAppV(clo, ys)
}
return clo
case CALL:
lex.getToken()
xs := getArgs(lex)
if len(xs) == 0 {
panic(fmt.Errorf("wrong number of arguments: call"))
}
return newAppV(xs[0], xs[1:])
case scanner.Int:
var n int64
fmt.Sscan(lex.TokenText(), &n)
lex.getToken()
return Int(n)
case scanner.Float:
var n float64
fmt.Sscan(lex.TokenText(), &n)
lex.getToken()
return Flt(n)
case scanner.String:
var s string
fmt.Sscanf(lex.TokenText(), "%q", &s)
lex.getToken()
return Str(s)
case scanner.Ident:
name := lex.TokenText()
lex.getToken()
if name == "quit" {
panic(name)
}
v, ok := funcTable[name]
if ok {
if lex.Token == '(' {
xs := getArgs(lex)
if len(xs) != v.Argc() {
panic(fmt.Errorf("wrong number of arguments: %v", name))
}
return newApp(v, xs)
} else {
// 関数値をそのまま返す
return v
}
} else if lex.Token == '[' {
return newRef(Variable(name), getIndex(lex))
} else if lex.Token == '(' {
// 変数に格納されている関数を呼び出す
return newAppV(Variable(name), getArgs(lex))
} else {
return Variable(name)
}
default:
panic(fmt.Errorf("unexpected token: %v", lex.TokenText()))
}
}
// 項
func term(lex *Lex) Expr {
e := factor(lex)
for {
switch lex.Token {
case '*':
lex.getToken()
e = newOp2('*', e, factor(lex))
case '/':
lex.getToken()
e = newOp2('/', e, factor(lex))
case '%':
lex.getToken()
e = newOp2('%', e, factor(lex))
default:
return e
}
}
}
// 式
func expr3(lex *Lex) Expr {
e := term(lex)
for {
switch lex.Token {
case '+':
lex.getToken()
e = newOp2('+', e, term(lex))
case '-':
lex.getToken()
e = newOp2('-', e, term(lex))
default:
return e
}
}
}
// 比較演算子
func expr2(lex *Lex) Expr {
e := expr3(lex)
x := lex.Token
switch x {
case EQ, NE, LT, GT, LE, GE:
lex.getToken()
return newOp2(x, e, expr3(lex))
default:
return e
}
}
// 論理演算子
func expr1(lex *Lex) Expr {
e := expr2(lex)
for {
x := lex.Token
switch x {
case AND, OR:
lex.getToken()
e = newOps(x, e, expr2(lex))
default:
return e
}
}
}
func expression(lex *Lex) Expr {
e := expr1(lex)
if lex.Token == '=' {
switch x := e.(type) {
case Variable:
lex.getToken()
return newAgn(x, expression(lex))
case *Ref:
lex.getToken()
return newUdt(x, expression(lex))
default:
panic(fmt.Errorf("invalid assign form"))
}
}
return e
}
// ユーザ関数の定義
func defineFunc(lex *Lex) string {
lex.getToken()
if lex.Token != scanner.Ident {
panic(fmt.Errorf("invalid define form"))
}
name := lex.TokenText()
lex.getToken()
xs := getParameter(lex)
v, ok := funcTable[name]
if ok {
switch f := v.(type) {
case *FuncU:
if len(f.xs) != len(xs) {
panic(fmt.Errorf("wrong number of arguments: %v", name))
}
body := newBgn(getBody(lex))
if lex.Token != END {
panic(fmt.Errorf("'end' expected"))
}
f.xs = xs
f.body = body
default:
panic(fmt.Errorf("%v is built-in function", name))
}
} else {
// 再帰呼び出し対応
f := newFuncU(name, xs, nil)
funcTable[name] = f
f.body = newBgn(getBody(lex))
if lex.Token != END {
delete(funcTable, name)
panic(fmt.Errorf("'end' expected"))
}
}
return name
}
// ライブラリのロード
func loadLib(name string) {
var lex Lex
file, err := os.Open(name)
if err != nil {
fmt.Fprintln(os.Stderr, err)
os.Exit(1)
}
defer func(){
err := recover()
file.Close()
if err != nil {
fmt.Fprintf(os.Stderr, "%s: %v, %s\n", name, err, lex.Position)
os.Exit(1)
}
}()
lex.Init(file)
for {
lex.getToken()
if lex.Token == scanner.EOF {
break
} else if lex.Token == DEF {
defineFunc(&lex)
} else {
e := expression(&lex)
if lex.Token != ';' {
panic(fmt.Errorf("invalid expression"))
}
e.Eval(nil)
}
}
}
// 式の入力と評価
func toplevel(lex *Lex) (r bool) {
r = false
defer func(){
err := recover()
if err != nil {
mes, ok := err.(string)
if ok && mes == "quit" {
r = true
} else {
fmt.Fprintln(os.Stderr, err)
for {
c := lex.Peek()
if c == '\n' { break }
lex.Next()
}
}
}
}()
for {
fmt.Print("Calc> ")
lex.getToken()
if lex.Token == DEF {
fmt.Println(defineFunc(lex))
} else {
e := expression(lex)
if lex.Token != ';' {
panic(fmt.Errorf("invalid expression"))
} else {
fmt.Println(e.Eval(nil))
}
}
}
return r
}
func main() {
initKeyTable()
initFunc()
for _, name := range os.Args[1:] {
loadLib(name)
}
var lex Lex
lex.Init(os.Stdin)
for {
if toplevel(&lex) { break }
}
}