M.Hiroi's Home Page

お気楽 Go 言語プログラミング入門

電卓プログラムの作成 (4)


Copyright (C) 2014-2021 Makoto Hiroi
All rights reserved.

はじめに

今回は電卓プログラムに論理演算子、比較演算子、条件分岐の機能を追加してみましょう。

●論理演算子と比較演算子の優先順位

論理演算子と比較演算子を使う場合、真偽値を表すデータが必要になります。電卓プログラムのデータは実数しかないので、0.0 を偽、それ以外を真と定義することにしましょう。論理演算子と比較演算子は、結果が真であれば 1.0 を、偽であれば 0.0 を返すことにします。電卓プログラムで使用する論理演算子と比較演算子を表に示します。

表 : 論理演算子
操作意味トークン
not x, ! x x の否定（真偽の反転）NOT
x and y x が真かつ y が真ならば真AND
x or y x が真まはた y が真ならば真OR

表 : 比較演算子
演算子意味トークン
== 等しいEQ
!= 等しくないNE
< より小さいLT
> より大きいGT
<= より小さいか等しいLE
>= より大きいか等しいGE

論理演算子は not (!), and, or で、not は単項演算子になります。比較演算子は ==, !=, <, >, <=, >= の 6 種類で、Go 言語の比較演算子と同じです。演算子の優先順位ですが、他のプログラミング言語のように細かく分けることはしないで、次のように設定することにしました。 

優先順位 (高)
単項演算子 (+, -, not)
乗法演算子 (*, /)
加法演算子 (+, -)
比較演算子 (==, !=, <, >, <=, >=)
論理演算子 (and, or)
代入演算子 (=)
優先順位 (低)

●条件分岐

条件分岐は「文」として定義することもできますが、今回は簡単な電卓プログラムなので「if 式」として組み込むことにします。if 式の構文を示します。 

if 条件式 then 式a else 式b end
if 条件式 then 式a end

if は条件式が真であれば式a を実行し、その結果が if 式の値になります。条件式が偽であれば 式b を実行して、その結果が if 式の値になります。else 節が省略されていて、かつ条件式が偽の場合、if 式は実数 0.0 を返すことにしましょう。

●文法の修正

文法を EBNF で表すと次のようになります。 

[EBNF]
   文    = 関数定義 | 式.
関数定義 = "def", 関数, "(", [仮引数リスト], ")", 式, "end".
   式    = 代入式 | 式１.
 代入式  = 変数, "=", 式.
  式１   = 式２, { ("and" | "or"), 式２}.
  式２   = 式３, ("==" | "!=" | "<" | "<=" | ">" | ">="), 式３.
  式３   = 項, { ("+" | "-"), 項 }.
   項    = 因子, { ("*" | "/"), 因子 }.
  因子   = 数値 | ("+" | "-" | "not"), 因子 | "(", 式, ")" | 変数 | 関数, "(", [引数リスト], ")" | if式.
  if式   = "if", 式, "then", 式, ["else", 式], "end".
  変数   = 識別子
  関数   = 識別子

仮引数リスト = 変数, { ",", 変数 }.
引数リスト   = 式, { ",", 式 }.

[注意] 数値と識別子の定義は省略

論理演算子と比較演算子の処理は、文法をそのままプログラムするだけなので簡単です。if 式も構文木に変換すると簡単にプログラムすることができます。

●データ型の定義

データ型の定義は次のようになります。 

リスト : データ型の定義

// キーワード
const (
    DEF = -(iota+10)
    END
    IF
    THEN
    ELSE
    NOT
    AND
    OR
    EQ
    NE
    LT
    GT
    LE
    GE
)

// キーワード表
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
}

// 短絡演算子
type Ops struct {
    code rune
    left, right Expr
}

func newOps(code rune, left, right Expr) Expr {
    return &Ops{code, left, right}
}

// if
type Sel struct {
    testForm, thenForm, elseForm Expr
}

func newSel(testForm, thenForm, elseForm Expr) *Sel {
    return &Sel{testForm, thenForm, elseForm}
}

トークンに論理演算子 (NOT, AND, OR)、比較演算子 (EQ, NE, LT, GT, LE, GE)、if 式を表す IF, THEN, ELSE を追加します。そして、KeyTable に and, or, not, if, then, else を追加します。比較演算子は関数 getToken で記号をトークンに変換します。

構造体 Ops は and と or を「短絡演算子」として機能させるために用意しました。if 式を表す構造体が Sel です。フィールド変数 testForm が条件式、thenForm が then 節、elseForm が else 節を表します。

●字句解析の修正

それではプログラムを作りましょう。まず最初に、関数 getToken を修正します。 

リスト : トークンの切り出し

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
        }
    }
}

lex.Token が '=' の場合、次の記号が '=' かチェックします。次の記号は Scanner のメソッド Peek を使うと求めることができます。このとき、Peek で求めた記号は読み捨てていないことに注意してください。'=' であれば、Scanner のメソッド Next で '=' を読み捨てて、lex.Token を EQ に書き換えます。あとは同様に記号 '!', '<', '>' を処理するだけです。

●構文解析の修正

次は構文解析の処理を修正します。論理演算子の処理は次のようになります。 

リスト : 論理演算子の処理

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 == '=' {
        v, ok := e.(Variable)
        if ok {
            lex.getToken()
            return newAgn(v, expression(lex))
        } else {
            panic(fmt.Errorf("invalid assign form"))
        }
    }
    return e
}

式を評価する expression から関数 expr1 を呼び出します。expr1 は and と or の処理を行います。最初に関数 expr2 を呼び出して、返り値を変数 e にセットします。トークンは変数 x にセットします。x が AND または OR であれば、expr2 を呼び出して右辺を求め、左辺 e と右辺を Ops に格納し、それを変数 e にセットします。AND, OR でなければ、変数 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
    }
}

関数 expr2 は比較演算子の処理を行います。最初に、expr3 を呼び出して、その返り値を変数 e にセットします。トークンは変数 x にセットします。そして、トークンが比較演算子であれば Op2 を生成して返します。

次は factor に not と if の処理を追加します。 

リスト : 因子の処理

func factor(lex *Lex) Expr {
    switch lex.Token {

    ・・・省略・・・

    case NOT:
        lex.getToken()
        return newOp1(NOT, factor(lex))
    case IF:
        lex.getToken()
        return makeSel(lex)

    ・・・省略・・・

}

if の処理は関数 makeSel で行います。NOT は Op1 を生成して返すだけです。

●条件分岐の処理

次は if 式を組み立てる関数 makeSel を作ります。 

リスト : 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("'end' expected"))
            }
            lex.getToken()
            return newSel(testForm, thenForm, elseForm)
        case END:
            lex.getToken()
            return newSel(testForm, thenForm, Value(0.0))
        default:
            panic(fmt.Errorf("'else' or 'end' expected"))
        } 
    } else {
        panic(fmt.Errorf("'then' expected"))
    }
}

最初に expression を呼び出して条件式を読み込み、変数 testForm にセットします。次に、トークンが THEN であることを確認し、 expression で then 節を読み込み、変数 thenForm にセットします。トークンが ELSE の場合、同様に else 節を読み込みます。トークンが END であることを確認したら Sel を生成して返します。END でない場合はエラーを送出します。else 節がない場合は else 節のかわりに Value(0.0) を Sel に格納して返します。

●式の評価

次は式の評価を行うメソッド Eval を修正します。 

リスト : 式の評価

// bool を電卓の真偽値に変換する
func boolToValue(x bool) Value {
    if x {
        return 1.0
    } else {
        return 0.0
    }
}

// 真か
func isTrue(x Value) bool {
    return x != 0.0
}

// 偽か
func isFalse(x Value) bool {
    return x == 0.0
}

// 単項演算子の評価
func (e *Op1) Eval(env *Env) Value {
    v := e.expr.Eval(env)
    switch e.code {
    case '-': return -v
    case '+': return v
    case NOT: return boolToValue(isFalse(v))
    default:
        panic(fmt.Errorf("invalid Op1 code"))
    }
}

関数 boolToValue は引数 x が true ならば 1.0 を、false ならば 0.0 を返します。単項演算子 NOT の処理は簡単です。expr を評価した値 v が偽であるか関数 isFalse で判定し、その結果を boolToValue に渡すだけです。 

リスト : 二項演算子の評価

func (e *Op2) Eval(env *Env) Value {
    x := e.left.Eval(env)
    y := e.right.Eval(env)
    switch e.code {
    case '+': return x + y
    case '-': return x - y
    case '*': return x * y
    case '/': return x / y
    case EQ: return boolToValue(x == y)
    case NE: return boolToValue(x != y)
    case LT: return boolToValue(x < y)
    case GT: return boolToValue(x > y)
    case LE: return boolToValue(x <= y)
    case GE: return boolToValue(x >= y)
    default:
        panic(fmt.Errorf("invalid Op2 code"))
    }
}

比較演算子の処理も簡単です。トークンに対応する演算子で x と y を比較して、その結果を boolToValue に渡すだけです。

次は Ops を評価する処理を作ります。 

リスト : 短絡演算子の評価

func (e *Ops) Eval(env *Env) Value {
    x := e.left.Eval(env)
    switch e.code {
    case AND:
        if isTrue(x) {
            return e.right.Eval(env)
        }
        return x
    case OR:
        if isTrue(x) {
            return x
        }
        return e.right.Eval(env)
    default:
        panic(fmt.Errorf("invalid Ops code"))
    }
}

左辺 e.left の評価結果を変数 x にセットします。AND の場合、x が真であれば右辺 e.right を評価し、その結果を返します。偽であれば expr2 を評価せずに x を返します。OR の場合、x が真であれば右辺 e.right を評価しないで x を返します。偽の場合は e.right を評価してその結果を返します。

次は if 式を評価するプログラムを作ります。 

リスト : if 式の評価

func (e *Sel) Eval(env *Env) Value {
    if isTrue(e.testForm.Eval(env)) {
        return e.thenForm.Eval(env)
    }
    return e.elseForm.Eval(env)
}

if 式の処理 Sel も簡単です。最初に条件式 e.testForm を Eval で評価し、その返り値が真であれば then 節 (e.thenForm) を、偽であれば else 節 (elseForm) を Eval で評価するだけです。

●再帰呼び出しの対応

さて、電卓プログラムで if 式が使えるようになると、関数の再帰呼び出しが可能になります。ところが、前回作成したプログラムでは、関数の再帰呼び出しに対応していません。たとえば、階乗を求める関数は次のようになります。 

リスト : 階乗の計算

def fact(n)
    if n == 0 then 1 else n * fact(n - 1) end
end

電卓プログラムは funcTable に登録されている識別子を関数と判断します。def 文 は式を構文木に変換する expression を実行したあとに fact を funcTable に登録するので、expression を実行する段階では、fact を関数ではなく変数として認識してしまいます。これでは関数の再帰呼び出しができません。そこで、expression を実行する前に、funcTable に関数を登録し、expression を評価したあと値を書き換えることにします。

関数 defineFunc の修正は次のようになります。 

リスト : 関数定義の修正

func defineFunc(lex *Lex) {
    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 := expression(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 = expression(lex)
        if lex.Token != END {
            delete(funcTable, name)
            panic(fmt.Errorf("'end' expected"))
        }
    }
    fmt.Println(name)
}

関数名と仮引数リストを取得したあと、関数が定義されているかチェックします。未定義の場合、newFuncU で FuncU を生成して funcTable にセットします。このとき、フィールド変数 body にはダミーデータとして nil をセットします。それから expression で本体を取得してフィールド変数 body にセットします。トークンが END で終わっていない場合は funcTable から関数を削除して panic でエラーを送出します。

プログラムの大きな修正はこれだけです。あとは簡単なので説明は割愛します。詳細はプログラムリストをお読みください。

●実行例

それでは簡単な実行例を示します。 

Calc> not 0;
1
Calc> not 1;
0
Calc> not 1.1;
0
Calc> !0;
1
Calc> !1;
0
Calc> 0 and 0;
0
Calc> 1 and 0;
0
Calc> 1 and 2;
2
Calc> 0 or 0;
0
Calc> 2 or 0;
2

Calc> 0 or 3;
3
Calc> 2 == 2;
1
Calc> 2 != 2;
0
Calc> 1 < 2;
1
Calc> 1 <= 2;
1
Calc> 2 <= 2;
1
Calc> 1 > 2;
0
Calc> 1 >= 2;
0
Calc> 2 >= 2;
1

論理演算子と比較演算子は正常に動作しているようです。次は論理演算子と比較演算子を組み合わせてみましょう。 

Calc> not 1 or not 0;
1
Calc> not 1 or not 1;
0
Calc> not 0 or not 1;
1
Calc> not 0 and not 0;
1
Calc> not 0 and not 1;
0
Calc> 1 < 2 and 2 < 3;
1

Calc> 1 > 2 and 2 < 3;
0
Calc> 1 < 2 and 2 > 3;
0
Calc> 1 < 2 or 2 < 3;
1
Calc> 1 > 2 or 2 < 3;
1
Calc> 1 > 2 or 2 > 3;
0

これも正常に動作しているようです。次は if 式を試してみましょう。 

Calc> if 1 < 2 then 10 else -10 end;
10
Calc> if 1 > 2 then 10 else -10 end;
-10
Calc> if 1 > 2 then 10 end;
0
Calc> def abs(n) if n > 0 then n else - n end end
abs
Calc> abs(10);
10
Calc> abs(-10);
10
Calc> abs(11 - 10);
1
Calc> abs(10 - 11);
1

正常に動作していますね。条件分岐があると、再帰呼び出しで繰り返しを実現することができます。階乗を求める関数 fact とフィボナッチ数列を求める関数 fibo は次のようになります。 

Calc> def fact(n) if n == 0 then 1 else n * fact(n - 1) end end
fact
Calc> fact(9);
362880
Calc> fact(10);
3.6288e+06
Calc> fact(20);
2.43290200817664e+18

Calc> def fibo(n) if n == 0 or n == 1 then n else fibo(n - 1) + fibo(n - 2) end
end
fibo
Calc> fibo(5);
5
Calc> fibo(6);
8
Calc> fibo(7);
13
Calc> fibo(8);
21
Calc> fibo(9);
34
Calc> fibo(10);
55

関数 fibo は二重再帰ですが、累積変数を使って末尾再帰に変換することができます。 

Calc> def fiboi(n, a, b) if n == 0 then a else fiboi(n - 1, b, a + b) end end
fiboi
Calc> fiboi(5, 0, 1);
5
Calc> fiboi(10, 0, 1);
55
Calc> fiboi(20, 0, 1);
6765

電卓プログラムは末尾再帰最適化を行わないので繰り返しに変換することはできませんが、二重再帰よりも高速にフィボナッチ数列を求めることができます。

このように、再帰呼び出しは簡単にできますが、「相互再帰」を実現しようとするとちょっとした工夫が必要になります。相互再帰とは、関数 foo が関数 bar を呼び出し、bar でも foo を呼び出すというように、お互いに再帰呼び出しを行っていることをいいます。今回の電卓プログラムでは、foo から bar を呼び出そうとしても、bar が未定義の場合は bar を関数ではなく変数として認識してしまいます。

この場合、次のようにダミーの関数 bar を定義してから関数 foo を定義し、そのあとで関数 bar を再定義することで相互再帰を実現することができます。 

Calc> def bar(n) n end
bar
Calc> def foo(n) if n == 0 then 1 else bar(n - 1) end end
foo
Calc> def bar(n) if n == 0 then 0 else foo(n - 1) end end
bar
Calc> bar(3);
1
Calc> bar(2);
0
Calc> bar(1);
1
Calc> foo(3);
0
Calc> foo(2);
1
Calc> foo(1);
0

結果を見ればおわかりのように、foo は n が偶数のときに真を返し、bar は n が奇数のときに真を返します。なお、このプログラムはあくまでも相互再帰の例題であり、実用的なプログラムではありません。

今回はここまでです。次回は複数の式を順番に実行する begin 式、式を繰り返し実行する while 式、局所変数を定義する let 式を追加してみましょう。

●参考文献

  1. 松田晋, 『実践アルゴリズム戦略 解法のテクニック 再帰降下型構文解析』, C MAGAZINE 1992 年 9 月号, ソフトバンク
  2. 水野順, 『スクリプト言語を作ろう』, C MAGAZINE 2000 年 5 月号, ソフトバンク
  3. 松浦健一郎, 『コンパイラの作成』, C MAGAZINE 2003 年 1 月号, ソフトバンク
  4. 高田昌之, 『インタプリタ進化論』, ＣＱ出版社, 1992
  5. 久野靖, 『言語プロセッサ』, 丸善株式会社, 1993

●プログラムリスト

//
// calc4.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
)

// キーワード表
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
}

// 値
type Value float64

// 局所変数の環境
type Env struct {
    name Variable
    val  Value
    next *Env
}

func newEnv(name Variable, val Value, env *Env) *Env {
    return &Env{name, val, env}
}

// 構文木の型
type Expr interface {
    Eval(*Env) Value
}

// 局所環境の生成
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 lookup(name Variable, env *Env) (Value, bool) {
    for ; env != nil; env = env.next {
        if name == env.name {
            return env.val, true
        }
    }
    return 0.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
}

// 評価
func (e Value) Eval(_ *Env) Value {
    return e
}

// 単項演算子
type Op1 struct {
    code rune
    expr Expr
}

func newOp1(code rune, e Expr) Expr {
    return &Op1{code, e}
}

// bool を電卓の真偽値に変換する
func boolToValue(x bool) Value {
    if x {
        return 1.0
    } else {
        return 0.0
    }
}

// 真か
func isTrue(x Value) bool {
    return x != 0.0
}

// 偽か
func isFalse(x Value) bool {
    return x == 0.0
}

func (e *Op1) Eval(env *Env) Value {
    v := e.expr.Eval(env)
    switch e.code {
    case '-': return -v
    case '+': return v
    case NOT: return boolToValue(isFalse(v))
    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 (e *Op2) Eval(env *Env) Value {
    x := e.left.Eval(env)
    y := e.right.Eval(env)
    switch e.code {
    case '+': return x + y
    case '-': return x - y
    case '*': return x * y
    case '/': return x / y
    case EQ: return boolToValue(x == y)
    case NE: return boolToValue(x != y)
    case LT: return boolToValue(x < y)
    case GT: return boolToValue(x > y)
    case LE: return boolToValue(x <= y)
    case GE: return boolToValue(x >= y)
    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 isTrue(x) {
            return e.right.Eval(env)
        }
        return x
    case OR:
        if isTrue(x) {
            return x
        }
        return e.right.Eval(env)
    default:
        panic(fmt.Errorf("invalid Ops code"))
    }
}

// if - then - else
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 isTrue(e.testForm.Eval(env)) {
        return e.thenForm.Eval(env)
    }
    return e.elseForm.Eval(env)
}

// 変数
type Variable string

// 大域的な環境
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 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 {
    Argc() int
}

type Func1 func(float64) float64

func (f Func1) Argc() int {
    return 1
}

type Func2 func(float64, float64) float64

func (f Func2) Argc() int {
    return 2
}

// ユーザ定義関数
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)
}


// 関数呼び出し
type App struct {
    fn Func
    xs []Expr
}

func newApp(fn Func, xs []Expr) *App {
    return &App{fn, xs}
}

func (a *App) Eval(env *Env) Value {
    switch f := a.fn.(type) {
    case Func1:
        x := float64(a.xs[0].Eval(env))
        return Value(f(x))
    case Func2:
        x := float64(a.xs[0].Eval(env))
        y := float64(a.xs[1].Eval(env))
        return Value(f(x, y))
    case *FuncU:
        return f.body.Eval(makeBinding(f.xs, a.xs, env))
    default:
        panic(fmt.Errorf("function Eval error"))
    }
}

// 組み込み関数の初期化
var funcTable = make(map[string]Func)

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)
}


// 字句解析
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("'end' expected"))
            }
            lex.getToken()
            return newSel(testForm, thenForm, elseForm)
        case END:
            lex.getToken()
            return newSel(testForm, thenForm, Value(0.0))
        default:
            panic(fmt.Errorf("'else' or 'end' expected"))
        } 
    } else {
        panic(fmt.Errorf("'then' expected"))
    }
}

// 因子
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()
        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 scanner.Int, scanner.Float:
        var n float64
        fmt.Sscan(lex.TokenText(), &n)
        lex.getToken()
        return Value(n)
    case scanner.Ident:
        name := lex.TokenText()
        lex.getToken()
        if name == "quit" {
            panic(name)
        }
        v, ok := funcTable[name]
        if ok {
            xs := getArgs(lex)
            if len(xs) != v.Argc() {
                panic(fmt.Errorf("wrong number of arguments: %v", name))
            }
            return newApp(v, xs)
        } 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))
        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 == '=' {
        v, ok := e.(Variable)
        if ok {
            lex.getToken()
            return newAgn(v, expression(lex))
        } else {
            panic(fmt.Errorf("invalid assign form"))
        }
    }
    return e
}

// ユーザ関数の定義
func defineFunc(lex *Lex) {
    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 := expression(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 = expression(lex)
        if lex.Token != END {
            delete(funcTable, name)
            panic(fmt.Errorf("'end' expected"))
        }
    }
    fmt.Println(name)
}

// 式の入力と評価
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 {
            defineFunc(lex)
        } else {
            e := expression(lex)
            if lex.Token != ';' {
                panic(fmt.Errorf("invalid expression"))
            } else {
                fmt.Println(e.Eval(nil))
            }
        }
    }
    return r
}

func main() {
    var lex Lex
    lex.Init(os.Stdin)
    initKeyTable()
    initFunc()
    for {
        if toplevel(&lex) { break }
    }
}
初版 2014 年 5 月 4 日
改訂 2021 年 12 月 22 日