OCamlで48 Hour Schemeをやってみる　その２　（第三章後半）

前回から続いてWrite Yourself a Scheme in 48 Hours第三章。

primitive関数適用の評価まで実装する。

src/eval.mlというモジュールを新たに作った。

open Exp

(* 省略 *)

let rec f e = match e with
  | String _ -> e
  | Number _ -> e
  | Bool _ -> e
  | List [Atom "quote"; e2] -> e2
  (* 省略 *)
  | _ -> failwith "Evaluation not implemented"

まずはこんな感じに文字列、数字、真偽値は評価されてもそのままであると定義。(quote x)のようなリストはxに評価される。

これをbin/ex.mlから使うようにする：

open Lisp

let _ =
  Lexing.from_channel stdin
  |> Parser.f Lexer.f
  |> Eval.f
  |> Exp.to_string
  |> print_endline

ここまでは簡単。次はeval.mlを拡張してprimitive関数適用を評価できるようにする。

まずはLisp式を整数値に変換する関数：

let rec to_int = function
  | Number n -> n
  | String s -> (try int_of_string s with Failure _ -> 0)
  | List [e] -> to_int e
  | _ -> 0

Number型は単純なのだが

文字列は変換できれば変換する
単一の要素を持つリストはその要素を整数値に変換する
それ以外の式はすべて0として扱う

というなんとも「弱い型」な評価方法。

二項演算子とLisp式のリストをとり、Lisp式を整数に変換してfoldするnumeric_binop関数：

let numeric_binop op params =
  let n = match List.map to_int params with
    | [] -> 0
    | x :: xs -> List.fold_left op x xs
  in
  Number n

primitive関数をnumeric_binopで定義してstring Mapに入れておく：

module P = Map.Make(String)
let primitives = P.empty
  |> P.add "+" (numeric_binop (+))
  |> P.add "-" (numeric_binop (-))
  |> P.add "*" (numeric_binop ( * ))
  |> P.add "/" (numeric_binop (/))
  |> P.add "mod" (numeric_binop (mod))

これで関数適用のためのapplyが書ける：

Lisp式リストのCARがprimitiveに合致するかどうかをチェック
もし合致していたらその関数をリストのCDRに適用する

let apply func args = match P.find_opt func primitives with
  | None -> Bool false
  | Some f -> f args

Eval.f関数内では、まずCDRの個々の要素を評価してからapplyを使う：

let rec f e = match e with
  (* 省略 *)
  | List (Atom func :: args) ->
      List.map f args
      |> apply func
  (* 省略 *)

これで

> echo "(- 54 10 2)" | dune exec bin/ex.bc
42

となる。

次回はエラーハンドリング。

Arantium Maestum

プログラミング、囲碁、読書の話題

OCamlで48 Hour Schemeをやってみる　その２　（第三章後半）