Previous Up Next
3.4 mini Scheme2 --- 条件分岐の導入

さて，次に条件分岐の機能を追加した mini Scheme2 を定義する．そのために， 条件判定式と比較プリミティブ =, < を追加する． 条件判定式は (if <式1> <式2> <式3>) で表され，<式1> の値が0でなければ <式2> を評価し，その値を全体の式の値とし，0であれば <式3> の値を全体の値とするようなものである． (= <式1> <式2>) は 両式の値が等しければ，1 を，そうでなければ 0 を 返すプリミティブである．同様に， (< <式1> <式2>) は <式1> の値が<式2> の値より小さければ 1，そうでなければ 0 を返す．

以下に，mini Scheme2プログラムの実行例を示す． 

⇒ (< 5 4)
0
⇒ (if (< (+ 3 5) (- 9 18)) v x)
10
⇒ (+ (= 3 3) 5)
6
全体としての文法は，
<プログラム> ::= <式>
<式> ::= …
  | (if <式1> <式2> <式3>)
<プリミティブ> ::= … | = | <
となる．また，セマンティクスに関する定義は，真偽値も整数で表現しているので， Expressed Value, Denoted Valueともにそのままである．

3.4.1 プリミティブの追加

まずは，プリミティブの追加の方法を見る．まず，構文的な側面に関しては， このインタプリタではプリミティブをキーワードとし，文法においても特別扱 いしているため，抽象構文の定義，構文解析のトークン宣言，字句解析のキー ワードリストの変更が必要である．また，当初の字句解析規則では =, < にマッチする規則がなかったので規則の変更も必要である．
syntax.ml:
type prim = Plus | Minus | Mul | Add1 | Sub1 | Eq | Lt

parser.mly:
...
%token EQ LT
...
PrimOp:
  ...
  | EQ { Eq }
  | LT { Lt }

lexer.mll:
let reservedWords = [
  ...
  ("=", Parser.EQ);
  ("<", Parser.LT);
] 

rule main = parse
  ...
| ['a'-'z'] ['a'-'z' '_' '0'-'9' '']*
| ['+' '-' '*' '=' '<']
  ...

core.ml:
let apply_prim p args =
  match p, args with
    ...
  | (Eq, [IntV i; IntV j]) -> if i = j then IntV 1 else IntV 0
  | (Eq, _) -> failwith "Arity mismatch: ="
  | (Lt, [IntV i; IntV j]) -> if i < j then IntV 1 else IntV 0
  | (Lt, _) -> failwith "Arity mismatch: <"

Figure 7: 比較プリミティブの追加

また，core.ml は，プリミティブを追加したのだから， Syntax.prim 型に関わる部分，つまり，apply_prim を変更すればよい．

3.4.2 if 式の追加

if 式は，if をキーワードとして追加し，式の構文に if 式の追加が行われる．解釈部に関しては，eval_exp で if 式を扱う 節を追加することになる．テストする式の値は Objective Caml 上では int型ではなく IntV コンストラクタが付加された値として表されているので， パターンマッチを使ってコンストラクタを外さなければならない．
syntax.ml:

type exp = 
    ...
  | If of exp * exp * exp


parser.mly:

Exp :
  ...
  | LPAREN IF Exp Exp Exp RPAREN { If ($3, $4, $5) }


lexer.mll:

let reservedWords = [
  ...
  ("if", Parser.IF);
]


core.ml

let rec eval_exp env = function
  ...
  | If (e1, e2, e3) ->
      let IntV test = eval_exp env e1 in
      if test <> 0 then eval_exp env e2
      else eval_exp env e3

Figure 8: if式の追加


Exercise 3  [必修課題] mini Scheme2 インタプリタを作成し，テストせよ．

Exercise 4  [難易度 1] 論理値演算プリミティブ and, or, not を追加せよ．

Exercise 5  [難易度 2] 真偽値を整数で代用するのではなく，新たな mini Schemeの値として 導入せよ．つまり，
Expressed Value = 整数 (…, -2, -1, 0, 1, 2, 3, …) + 真偽値 (true, false)
Denoted Value = 整数 + 真偽値
とする．ヒントとして，core.ml の変更点を示す． 

type exval = 
    IntV of int
  | BoolV of bool
また，true, false はキーワードもしくは，大域環境に束縛された変数と して導入する．以下は，実行例である． 


⇒ true
true
⇒ (> 3 5)
false
⇒ (if (> 5 (+ 2 4)) x i)
1
(ヒント: この問題は，mini Scheme4までやってから戻るとやりやすい)

Previous Up Next