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_expif 式を扱う 節を追加することになる.テストする式の値は Objective Caml 上では int型ではなく IntV コンストラクタが付加された値として表されているので, パターンマッチを使ってコンストラクタを外さなければならない.

syntax.ml:

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


parser.mly:

...
%token IF
...
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 5  [必修課題] mini Scheme2 インタプリタを作成し,テストせよ.


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


Exercise 7  [難易度 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