Arantium Maestum

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

AtCoder Beginners SelectionをOCamlで(後編)

OCamlAtCoderに参加する練習のためにAtCoder Beginners Selectionをやってみた

atcoder.jp

今回は最後の2問、白昼夢 / DaydreamとTravellingの解法とOCamlを使った所感。

ABC049C - 白昼夢 / Daydream

atcoder.jp

ある文字列が、"dream", "erase", "dreamer", "eraser"の四語のどれかを繰り返すことで作られているかを判定する

atcoder.jp

open Batteries

let s = read_line () |> String.explode |> List.rev

let rec f = function
  | [] -> true
  | 'm' :: 'a' :: 'e' :: 'r' :: 'd' :: xs -> f xs
  | 'e' :: 's' :: 'a' :: 'r' :: 'e' :: xs -> f xs
  | 'r' :: 'e' :: 's' :: 'a' :: 'r' :: 'e' :: xs -> f xs
  | 'r' :: 'e' :: 'm' :: 'a' :: 'e' :: 'r' :: 'd' :: xs -> f xs
  | _ -> false

let ans = if f s then "YES" else "NO"
let () = print_endline ans

"dream"と"dreamer"、"erase" "eraser"と先頭から読んでいくと候補が重複してしまう。バックトラックするようなロジックも考えられるが、この四語だったら一番楽なのは後ろからパースすることだろう(後ろから見ると重複する候補はないため)。

OCamlのリストと文字がパターンマッチ可能なことを利用した再帰関数でパースできる。

ABC086C - Traveling

atcoder.jp

格子上の点を特定のスケジュールで移動できるかどうかを判定する。

atcoder.jp

open Batteries

let parse_triplet s =
  Scanf.sscanf s "%d %d %d" (fun a b c -> (a,b,c))

let diff ((_,_,_), (a,b,c)) (x,y,z) =
  ((x-a,y-b,z-c), (x,y,z))

let pred (a, b, c) =
  let d = abs b + abs c in 
  a >= d && a mod 2 = d mod 2

let n = read_int ()
let x =
  Enum.init n (fun _ -> read_line ())
  |> Enum.map parse_triplet
  |> Enum.scanl diff ((0,0,0), (0,0,0))
  |> Enum.map fst
  |> Enum.for_all pred
  
let ans = if x then "Yes" else "No"

let () = print_endline ans

スケジュールは時間順に与えられるので、隣接するスケジュールの差だけを調べていけばいい。

スケジュールの差が可能かどうかの判定は以下の二点:

  1. 移動量は時間内に収まるか
  2. 移動量と時間の偶奇が一致するか(余った時間は2つずつ無駄に消費することが可能なため)

Enum.scanlfoldに似ているけど、foldでいうところの中間結果をすべて要素として持つ遅延リスト。

Enum.scanl f x (a1; a2; a3)(x; f x a1; f (f x a1) a2; f (f (f x a1) a2) a3)となる(ここでは(x;y;z)x``y``zを要素に持つ遅延リストだとする)。

これを使って「差額の遅延リスト」を作成して、すべてが上記の二点を満たしているかをEnum.for_allで判定している。

OCamlAtCoderで使ってみて

OCamlは去年の10月くらいからかれこれ四ヶ月ほど(業務外で・・・)使っていて少しは慣れてきたと思うのだが、主に言語実装系のことばかりしていたので競技プログラミングは勝手がけっこう違った。言語処理系の実装だとASTなどの処理のために「再帰関数でパターンマッチ」が多くなるのだが、AtCoder Beginners Selectionではあまり木構造をどうこうすることもなく、直線的かつフラットにデータ変換のロジックを書いていくことが多かった。

OCaml|>演算子Enumの各関数などで十分そのような書き方もできる言語だとわかったのは嬉しい。

個人的にはOCamlの命令型でも記述できるところはすごく便利だと思っているのだが、振り返ると一度もrefArrayHashtblなどの破壊的代入が可能なデータやforループなどの命令的な構文などを使う必要がなかった。Dynamic Programmingなどでは絶対必要になってくると思うが、Batteriesのモジュールや関数、とくにEnum関連を使いこなせば関数型プログラミングのスタイルだけでもかなりの処理を(しかもそれなりに宣言的に)記述できることも実感できた。個人的にはこれはPythonなどでも感じていたことだが・・・

Pythonとは実行速度が比較にならないほど早い、という点もAtCoder向きだ。

比較のためにOtoshidamaをPythonOCamlで同じ(意図的にアルゴリズムの良さよりも記述の明快さを重視した)ロジックで書いてみた:

Python:

atcoder.jp

OCaml:

atcoder.jp

Pythonの内包表記的なgenerator expressionは記法としてはやはりすごく好きだ・・・ がほぼ完全に一致するロジックのコードで、Pythonが719 ms、OCamlが58 msで十倍以上の差がある。コードが煩雑になるような定数倍最適化を行わなくてはならない、というケースが減りそうでとても魅力的。

というわけでこれからもちょくちょくOCamlAtCoderの過去問を解いていこうと思う。ArrayHashtblなどを使ってDPやUnion Find Treeなどの問題を解いていって、それらの記法にも馴染んできた時点で実際のコンテストにもまた参加したい。まずは最近開催されたEDPCの問題かな・・・

AtCoder Beginners SelectionをOCamlで(中編)

OCamlAtCoderに参加する練習のためにAtCoder Beginners Selectionをやってみた

atcoder.jp

(この記事はSome Sums, Card Game for Two, Kagamimochi, Otoshidamaの4問について)

ABC083B - Some Sums

atcoder.jp

0~Nまでの数で、各桁の合計がa以上b以下になるものを合計する。

atcoder.jp

open Batteries

let add_digits x =
    string_of_int x
    |> String.explode
    |> List.map (fun x -> int_of_char x - 48)
    |> List.fold_left (+) 0

let n, a, b = Scanf.scanf "%d %d %d" (fun n a b -> n, a, b)
let ans =
  Enum.range 1 ~until:n
  |> Enum.filter (fun x -> let y = add_digits x in a <= y && y <= b)
  |> Enum.reduce (+)
  |> string_of_int
  
let () = print_endline ans

問題をそのままコード化できたように思うがどうだろうか。

ABC088B - Card Game for Two

atcoder.jp

交互に数字の書いてあるカードをとっていくゲームで、お互いに最善を尽くした場合の点差を計算する。

atcoder.jp

open Batteries

let rec diff_two n = function
  | [] -> n
  | [x] -> n + x
  | x :: y :: zs -> diff_two (n + x - y) zs;;

let _ = read_line ()
let ans =
  read_line ()
  |> String.split_on_char ' '
  |> List.map int_of_string
  |> List.sort (flip compare)
  |> diff_two 0
  |> string_of_int
  
let () = print_endline ans

降順にソートされた数字の奇数番と偶数番の和の差。

List.sort (flip compare)で逆順ソートになるのは思いつけてよかった。(fun a b -> - (compare a b)とか書くのかなー、いやだなーと思っていたので・・・

逆に再帰diff_twoを書いているのは少し不満がある。なんらかの高階関数を組み合わせて表現できないものか・・・

今ふとこんな解も思いついたが

let ans =
  read_line ()
  |> String.split_on_char ' '
  |> List.map int_of_string
  |> List.sort (flip compare)
  |> List.fold_left (fun (n, m) x -> (n + (m * x), - m)) (0, 1)
  |> fst
  |> string_of_int

これはちょっと問題固有の部分に引きずられすぎているだろうか?あまりテクニックとして汎用性がなさそうにも見える。

ABC085B - Kagami Mochi

atcoder.jp

いくつかの直径の餅を「下にある餅は必ず上にある餅よりも直径が大きい」という制約でいくつ積み重ねることができるか。

atcoder.jp

open Batteries
module S = Set.Make(Int)

let n = read_int ()
let ans =
  List.init n (fun _ -> read_int ())
  |> S.of_list
  |> S.cardinal
  |> string_of_int

let () = print_endline ans

ユニークな直径の数を求めればいいのでSetを使う。OCamlだとSetはFunctor(モジュールをうけとりモジュールを返す「関数」)なので、Batteriesで定義されているIntモジュールを渡すことで整数を要素にとる集合を表すことができる。

あとはList.init n (fun _ -> read_int ())n行に渡る整数の入力値をリスト化し、S.of_listで集合化し、S.cardinalで要素数を数えてstring_of_intで文字列化する。

ABC085C - Otoshidama

atcoder.jp

10000円札、5000円札、1000円札を合計N枚使ってY円を作ることができるか。

atcoder.jp

open Batteries
open Enum.Infix

let n, y = Scanf.scanf "%d %d" (fun n y -> (n, y))

let f i =
  let z = (y - 10000*i - 1000*(n-i)) / 4000 in
  (i, z, n - i - z)
  
let p (a, b, c) = 
  y = a * 10000 + b * 5000 + c * 1000
  && 0 <= a && 0 <= b && 0 <= c

let xs = Enum.map f (0--(y / 10000))
let ans = 
  let a, b, c = 
    try Enum.find p xs 
    with Not_found -> (-1, -1, -1)
  in
  Printf.sprintf "%d %d %d" a b c

let () = print_endline ans

5000円札、1000円札を合計N枚使ってY円を作る」というのはつるかめ算的なサムシングなので、それをまずf関数で表す。

ただし、5000円札A枚、1000円札B枚のAとBが整数でなかったり片方が負数だったりする場合を排除しないといけないので、そのためのp述語を定義する。

あとはEnum.Infixに定義された--演算子rangeを手軽に表したものにfmapし、`tryEnum.find pで合致する要素を探し、見つからなかった場合はNot_foundをキャッチして(-1, -1, -1)を返している。Enum.Infixは継続して使うか少し悩むところだ・・・ (関数でも同じことができるのと、ぱっと見で理解しやすいか微妙な気がするため)

あと今回も入力が一行のみなのでScanf.scanfを使っている。

やはり長くなってきたので後編に続く。

AtCoder Beginners SelectionをOCamlで(前編)

OCamlAtCoderをやってみたいなーと考えている。

以前DP問題を解いてみたこともあったように、親和性は高いように思う。

具体的には、関数型・命令型どちらでも表現力が高く、実行過程の予想がつきやすく、コンパイルされるので早い、という利点がある。いろんな方面から嫌がられそうな表現だが、「早いPythonとして使えそう」というのが個人的な思惑。

とはいってもいろいろと文法もライブラリも流儀も違うので、練習のためにまずAtCoder Beginners Selectionをやってみた

atcoder.jp

PracticeA - はじめてのあっとこーだー(Welcome to AtCoder

atcoder.jp

まずはAtCoderでの入出力を試す練習問題。

OCamlだと入出力関数にread_int, read_line, Scanf, print_int, read_endline, Printfなどいろいろあってどれをどう使うのがいいか、ちょっと考えどころかもしれない。

とりあえず現在の自分のスタイルだとこんな感じ:

atcoder.jp

let n = read_int ()
let a, b = Scanf.sscanf (read_line ()) "%d %d" (fun a b -> (a, b))
let s = read_line ()

let ans = Printf.sprintf "%d %s" (n + a + b) s
let () = print_endline ans

Scanf.scanfという直接stdinから文字列をとってパースする関数もあるのだが、入力が複数行に渡る場合よく問題が起きるので使わないことにしている。多分改行のパースなどでエッジケースがあったりするのではないかと思うのだが・・・

なので単一の整数を取る場合はread_int、複数の場合はいったんread_lineとった文字列をScanf.sscanfでパースするようにする。

Scanf.sscanfは第三引数に関数を取り、パースした値をさらにどのようにでも加工できる。が、それはできるだけ使わないほうが読みやすいと思う。単にタプルを返すようにして、そのタプルから変数束縛したものをさらに処理していく。

あと最終的に答えをlet () = ...で出力するのだが、そこはほぼ決め打ちでlet () = print_endline ansにして、その上の方でansの文字列を作成するようにしている。print_intなども使いたくなるが、それだと改行が入らないのでどうせもう一手間必要になる。それよりは文字列を作成して、それを最後の行でprint_endlineで出力することに決めた方が考えることを減らせていい。

ABC086A - Product

atcoder.jp

一行の入力に含まれている二つの整数の積の偶奇を判定する。

atcoder.jp

let x = Scanf.scanf "%d %d" (fun a b -> a * b)
let ans = if x mod 2 = 0 then "Even" else "Odd"
let () = print_endline ans

はやくも自分の言った

単一の整数を取る場合はread_int、複数の場合はいったんread_lineとった文字列をScanf.sscanfでパースするようにする。

Scanf.sscanfからは)単にタプルを返すようにして、そのタプルから変数束縛したものをさらに処理していく。

という考えを破っているが、まあこれくらいはいいのではないか。受け取る入力が一行だけで、それに対する処理も一目でなにが起きているかわかるし。

ABC081A - Placing Marbles

atcoder.jp

三つの文字が1の値をとる回数を数える。

atcoder.jp

open Batteries

let ans =
  read_line ()
  |> String.explode
  |> List.map (fun c -> int_of_char c - 48)
  |> List.fold_left (+) 0
  |> string_of_int
  
let () = print_endline ans

文字が取り得る値が0か1なので各桁を足し合わせればいい。

  1. 入力を受け取り
  2. 文字列を文字のリストに変換し
  3. 各文字を数値に変換し
  4. 足し合わせ
  5. 数字を文字列化する

あとは今までどおりその文字列を出力するだけ。

OCamlの標準ライブラリ拡張のひとつであるBatteriesがAtCoderでも使えるので、open BatteriesしてString.explodeint_of_charを利用する。あと|>パイプ演算子でできるだけ直線的に計算の流れを表す。

ABC081B - Shift only

atcoder.jp

複数の数字を2で割り切りつづけられる回数を数える。

まずは再帰を使った解:

atcoder.jp

open Batteries

let _ = read_line ()
let xs = read_line ()
  |> String.split_on_char ' '
  |> List.map int_of_string
  
let rec f n =
  let m = Int.pow 2 (n+1) in
  if List.for_all (fun x -> x mod m = 0) xs then f (n+1) else n
  
let ans = string_of_int @@ f 0
let () = print_endline ans

入力を変更はせず、2 ** (n+1)ですべての数が割り切れたら次のnを調べる、という意味の

List.for_all (fun x -> x mod m = 0) xs then f (n+1) else n

がキモになっている。

つぎに再帰ではなく無限の遅延リストを使った解:

atcoder.jp

open Batteries

let _ = read_line ()
let xs = read_line ()
  |> String.split_on_char ' '
  |> List.map int_of_string
  
let p n =
  let m = Int.pow 2 (n+1) in
  not (List.for_all (fun x -> x mod m = 0) xs)
  
let ans =
  Enum.range 0
  |> Enum.find p
  |> string_of_int
let () = print_endline ans

Batteriesで定義されている遅延リストEnumを利用している。

  1. Enum.range 0で0からはじまる無限の数列を作る
  2. Enum.findでその無限リストからnot (List.for_all (fun x -> x mod m = 0) xs)があてはまる最初の数を見つける

この問題だとまだそこまで有り難みがないが、無限リストとそれに対する処理、無限リストから他のデータ構造への変換などを多く定義しているEnumモジュールはかなり便利。Pythonでいうところのgeneratorとitertoolsにあたる概念である。

ABC087B - Coins

atcoder.jp

500円A枚、100円B枚、50円C枚から合計X円になる組み合わせ方は何通りあるか。

atcoder.jp

open Batteries

let a = read_int ()
let b = read_int ()
let c = read_int ()
let x = read_int ()

let p n = n mod 50 = 0 && n / 50 <= c
  
let count n =
  Enum.init (b+1) (fun i -> n - i*100)
  |> Enum.take_while ((<=) 0)
  |> Enum.filter p
  |> Enum.hard_count
  
let ans =
  Enum.init (a+1) (fun i -> x - i*500)
  |> Enum.take_while ((<=) 0)
  |> Enum.map count
  |> Enum.reduce (+)
  |> string_of_int
  
let () = print_endline ans
  1. 「50円C枚からX円を作ることができるか」を判定する関数pを作成
  2. pを使って「100円B枚、50円C枚からX円を作る組み合わせ方の数」を計算する関数countを作成
  3. countを使って「500円A枚、100円B枚、50円C枚からX円を作る組み合わせ方の数」を計算

この解ではEnumの各種関数を多用している。

  • Enum.init n f(f 0, f 1, ... f (n-1))という遅延リストを作成
  • Enum.take_while p xsで遅延リストxsの先頭から述語pを満さない初めの要素までを含む新しい遅延リストを返す。(述語pを満さない要素は含まれない)
  • Enum.filter p xsで遅延リストxsの述語pを満たす全ての要素を含む新しい遅延リストを返す
  • Enum.hard_count xsで遅延リストxsの要素数を返す。
  • Enum.map f xsで遅延リストxsの各要素に対して関数fを適用した新しい遅延リストを返す
  • Enum.reduce f xsxsの第一要素を初期値としてfold的にf関数を累積的に適用した値を返す

と遅延リストやストリームでおなじみの関数群を使っている。

これらや他の遅延リスト関連の関数については

batteries.forge.ocamlcore.org

に詳細が載っていて、このページをずっと読み返しながら解いていた。はやく自然と使いこなせるようになりたい。

長くなってきたので後編中編に続く。

Concepts, Techniques and Models of Computer Programmingを読みはじめた

過去何回かぱらっとめくったくらいで置いておいたConcepts, Techniques and Models of Computer Programmingという本を去年の終わりあたりに少し真面目に読み始めた。

なぜか時々「ポストSICP」と言われる本で、CSの根幹部分の一つを書き表した大作・名著である。関数型や論理型やオブジェクト指向などのいわゆるプログラミング言語パラダイム、あるいは並行性などの実行モデルなどが、どのような言語機構の組み合わせで可能になり、どのようなより粒度の細かい分類が可能で、どのような特性があり、どのような書き方・問題へのアプローチを可能とするのか、について書かれている。

どこらへんが「ポストSICP」なのかは個人的には謎だが。SICPと扱うテーマの範囲も違うし、プログラミング初心者向けとは到底思えないし、SICPを読み終わった後に必ず読むべき!という順序もあまりぴんとこないし・・・ 別に例えば先にCLRS読んでもいいしPAIP読んでもいいし、CTMCPSICPの次にくるべき理由は思い当たらない・・・

ともあれCTMCPは面白そうな本である。

マルチパラダイム言語Ozとその実行環境Mozartを使って様々なプログラミング概念を提示しているのだが、そのOzというのも

  • 抽象機械によるoperational semanticsが与えられている仕様が小さいOz kernel language
  • Oz kernel languageの上にsyntax sugarを重ねた実用言語

の二層にわかれている。章を追うごとにkernel languageを拡張、あるいはsyntax sugarを追加していくことで新しいパラダイムに対応していく。それによってどのような原子的な言語要素から各言語機構が立ち上がってくるのかを明確にしている。

よっしゃとりあえずまずは実装だ!ということで例によってOCamlでkernel languageを書き始めている。

github.com

今のところ数字と関数定義のところまでできていて、次はレコードの実装。それが済んだら第2章で説明されているもっとも簡単なkernel languageはできあがる。その後はsyntax sugarを載せてみたり、先の章のkernel language extensionを実装したりしてみる。

とりあえずレコードができたら実装内容や言語の特徴についていったん振り返ってまた記事を書きたい。

自作言語Xemono

去年の終わり頃からReason MLよろしくOCamlシンタックスをいじった言語の仕様を考えている。

github.com

今のところ新規性はまったくなく、OCamlと100%互換性がある言語仕様を目指している。(ただし今のところオブジェクト関連の機能についてはまったくノータッチ・・・)semantics的にはOCamlは本当に個人的な理想に近いと感じる。

なので変えているのはガワだけ。

外見的な部分はかなりPythonからとっている。(各方面から嫌がられそうだけど・・・)

その最たる部分は定幅インデントによるブロックわけでスコープが決まって、変数束縛には=、関数定義には:を使う(letはなし)

returnなしでスコープの一番下の式の値がスコープ全体の値になるのはどちらかというとLisp(かRuby)に似ている。関数型言語をブロックで表現しようとすると結構自然とこうなる気がする。

行末の:+インデントによるブロック以外では、主にPEP20の思想に強く影響を受けている。

あとHaskellから$whereをもらってきた。

実装

まだない。OCaml + Menhirでやる。

パースに関しては

と指摘をいただいたように、Context Free Grammarではないのでその依存性をどう解決するかが一つのポイント。

lexerとparserの間にインデントルールの解釈をするコードを挟んで、EOL/INDENT/DEDENTトークンとして挿入していくのが良さそうだと現在は考えている。

ASTにしてしまえばそこから対応するOCamlに変換するのは簡単だと思う。とりあえず当面はOCamlコンパイルすることを目指す。(その次はcmmかな)

近いうちに着手したい。

長期的には「modular implicitsをXemono言語側で実装できたら・・・」という思いがある。その場合は型推論OCaml側に頼れないので、その実装からだが・・・

コード例

仕様をある程度試すために、Real World OCamlのサンプルコードをXemonoでちょこちょこ書いてみた:

github.com

細かいところで気になる点があったり、思わないところで大きな仕様漏れがあったり、となかなか役に立った。OCaml自体の仕様についても少し理解が深まっていくので、それもかなりうれしい。これからも継続してサンプルコードを翻訳してはレポジトリにあげていくつもり。

気になっている点

  • 関数定義と分岐条件の見た目が同じでコンテキスト依存
    • 関数定義にdefキーワードを導入するか悩み中
    • 分岐条件やパターンマッチにcaseキーワードを入れるのは文法が重くなる気がする
  • モジュールの最上層でのlet x = y;let x = y in ...の違いがlet/inを使わない分理解しにくくなっている?
    • これはドキュメントで説明するのが大事なだけかも
  • :だと見た目が弱いので、一行でパターンマッチとその結果を記述する時などに条件と結果の境目が一目で判別しにくい
    • 試行錯誤の結果、:の後にスペースを二つ入れると問題がかなり緩和されることがわかった

名前について

便宜上自分の中で言語Xと呼んでいたのだが、Xerxesをクセルクセスと読むことに気づいて、自然と決まった。

今後

とりあえず仕様はある程度固まってきたのでぼちぼち実装をはじめる。近いうちにModern Compiler Implementation in Xemonoみたいな企画ができるといいな。

100 Days of Codeをやってみた

ツイッターで100 Days Of Codeというチャレンジがたまに流れていて、面白そうだったのでやってみた。今年も終わりに近づいているので今更ながら振り返ってみる。

100 Days Of Code概要

ルールは簡単:

  • なるべく毎日1時間以上、業務外のコードを書く
  • githubに載せる
  • twitterで進捗をつぶやく

途中で風邪をひいて寝込んだりいわゆるライフイベントが発生したりして合計で5日ほど空いてしまったが、8月14日にはじめて11月26日に終わった。

積ん読していた本をある程度消費したい、という欲求もあり、100日間基本的に本に載っているコードや演習問題、オンラインのチュートリアルなどをやって過ごした。自前のプロジェクトを立ち上げたりしなかったのですこし寂しい気もする。近いうちに自作言語に手を出したい。

やったこと(というか読んだ本)

Essentials of Programming Languages 第1章〜第7章

Paradigms of Artificial Intelligence 第1章〜第4章

Structure and Interpretation of Computer Programs 第2章

500 Lines or Less - Python Bytecode Interpreter

Types and Programming Languages OCamlでの実装章

Implementing Programming Languages 第2章

Kaleidoscope LLVM Tutorial

MinCaml compiler

Essentials of Programming Languages

github.com

github.com

この本がここ1年ほど一番読みたいと思っていた本だった。ものすごく簡単な言語からはじめて、Racketでインタプリタをいろいろ実装していくという本。

などといったプログラミング言語の基礎概念の多くを実際に自分の手で作っていくのはすごく面白かったし勉強になった。とりあえずRacketで実装していって、その後OCamlで書き直してみたりしたのもよかった。(とくに代数的データ型の便利さを実感できた点で)

まだ章はいくつか残っているので今後もまた戻ってきたい。

Paradigms of Artificial Intelligence

github.com

こちらはちょっと手をつけた程度。Common Lispに没入するに至らず、不完全燃焼気味。絶対に読みたい本の一つなので2019年に持ち越し。

Structure and Interpretation of Computer Programs

github.com

カマイルカさん(@lagenorhynque)とOpt Technologiesの皆様のご好意で読書会にオンライン参加させてもらっていた。ここ二ヶ月ほど事情があって参加できず悲しい。近いうちにまた是非参加したい。

Schemeで問題を解いていって解けた人からコードをSlackにあげていくというなかなか楽しい会。Lispに興味がある人はガンガン参加するといいと思う。進むペースはすこしゆったりめか。

500 Lines or Less

github.com

The Architecture of Open Source Applicationsというシリーズがある。いろんなオープンソースのプログラムの設計思想などをその開発者が解説するというなかなか素敵なもの。その中の500行以下のプログラムをピックアップした刊が500 Lines or Lessだ。

章のひとつがPythonで実装するPython Bytecode Interpreterの解説で、これを追いながら写経していった。スタックマシンの実装の理解やバイトコードに対する慣れなど、得るものは多かったと思う。正直書かれていたコードはそこまで好きなスタイルではなかったが・・・

Types and Programming Languages

github.com

何回か流し読みしたことはあるのと最初の方はるじゃんどるさん(@Lugendre)の読書会でやったことはあるのだが、正直ちゃんと納得できるレベルで読めたとは言えない状態だった。

以前読んだ時はそもそもプログラミング言語についての前提知識が不十分だったように思う。Essentials of Programming LanguagesやConcepts, Techniques, and Models of Computer Programmingなどといった「プログラミング言語関連のトピックを俯瞰的に提示する本」を読んだ上で挑戦するのがちょうどいいのではないか。

今回もそこまで真面目に読んだ感じではなく、実装について触れている章を写経するのがメインだった。近いうちにまたちゃんと読み込みたい。

Implementing Programming Languages

github.com

C++のサブセット的な言語をJava Bytecodeやマシン語コンパイルする話が主体になる本。パーサに関する演習問題などを(本が推奨するパーサジェネレータではなく)OCamllexとMenhirで実装していった。

Kaleidoscope LLVM Tutorial

github.com

Kaleidoscopeという小さな言語をLLVMコンパイルするチュートリアルC++OCamlのものがあり、当然OCamlを選んだ、のだが。古いチュートリアルLLVMがどんどん発展している技術ということもあり、サンプルコードの多くが動かない。というかOCamlではLLVMJITコンパイラにアクセスするのがすごく大変そう(チュートリアルが書かれた頃に存在したAPIがごっそりDeprecatedになっていた)。

けっこう機能面でも思い切って削った(主に前述のJIT)コンパイラを実装。はじめてOCamlコードのデバッグやライブラリコードを必死に読むという経験をしたので、結果オーライか。

MinCaml compiler

github.com

東北大学の住井先生のMinCamlというOCamlサブセットをSPARC命令セットにコンパイルするOCamlプログラムを写経。

http://esumii.github.io/min-caml/paper.pdf

K正規化、α変換、β簡約などの関数型言語らしいコンパイラ最適化に触れつつそれなりの分量のOCamlコードを理解しながら写経していくというのは大変勉強になった。残念だったのはそもそも私がSPARCの命令セットを全く知らないので、最後の方の工程があまり理解できていない点・・・ 実はMinCamlのさらに限定的なサブセットからはじめて、少しずつ言語機能を追加していく感じでMinCamlコンパイラまで戻っていく、というような過程もやってみたいと思ってはじめたのだが前述の問題で失速してしまった。アセンブリ力が高まったら再度挑戦してみたい。

総括

というわけで、興味の赴くままにいろいろと触っていったらだんだん言語処理系沼にはまり込んでいった感がある。使う言語としては最初はLisp系やPythonだったのだが、後半はほぼOCaml。セマンティクス的にはかなり自分にとってしっくりくる言語だった(でもmodular implicitsはほしい・・・)のでこれからも積極的に使っていきたい。

100 Days of Codeという試みはなかなか面白かった。毎日なるべくちょこっとでも本を読んではPCに向かってコードを書く、さらには書いたコードはなるべくgithubにあげる、という習慣は、無駄に草を生やしているだけのように見えてこれでなかなか蓄積になっている、気がする。なんだかんだいって100日終わった後も継続的に趣味コード書いてはあげてるし。

コードはそれなりの量を書き散らかしたがプロダクト開発ではなく自分の知識獲得のためのものばかりだった。予想どうりだったとは言え今見返すとちょっと極端だったように思う。2019年は趣味でもすこしプロダクト的なものも書いていきたい。どこかのタイミングでまた100 days of codeやるかも。

SECDマシンとLispあれこれ

時には昔の話をしようか、ということでPeter LandinのSECDマシンについて。Lisp Advent Calendar 2018 23日目の記事。

はじめに

最近、長らく積読してたThe Architecture of Symbolic Computersという本を読んでいる。

There is a revolution looming in computer science … the basic von Neumann model of computing, which has ruled unchallenged for the last 40 years, is encountering not one but several potentially heavy weight challengers. … Achieving ... (the book's) ... goals should give the reader the ability to follow, or better yet participate in, construction of the languages and computing systems that will become the everyday computational tools of tomorrow.

と序文冒頭からかなり熱く語る本で、関数型言語と論理型言語の計算モデルのoperational semanticsを与えうる抽象機械の説明にかなりの分量を割いている。

HaskellのようなCall-by-Needな遅延評価戦略をとる関数型言語の抽象機械であるG machine(グラフ簡約マシン?)やPrologなどの論理型言語の抽象機械であるWarren machineなどにまじって、ラムダ計算とS式のための抽象機械、SECD machineについての解説がある。

このSECD machineがLispといろいろと関係深いのと、実装が比較的簡単だった上に言語処理系を開発してみたい人には面白い題材になりそうだったので紹介したい。

SECDの歴史的背景とLisp

SECDは前述のようにラムダ計算を実行できる抽象機械である。Peter Landinの論文Mechanical Evaluation of Expressionsでラムダ計算と実際的なプログラミングを直接結びつけるためのモデルとして提唱されている。この論文が出たのは1964年。

McCarthyがRecursive Functions of Symbolic Expressions and their Evaluation by MachineでLispを世に出した4年後で、当然LandinはLispを相当意識していた。

Mechanical Evaluation of Expressionsの終わりに挙げられている参考文献の9つのうち4つは数学・論理学のもの、2つはDijkstraのもの、そして3つはLisp関係(うち2つはMcCarthyのもの)である。ただ、その時期のLispがかなり実装を反映した「機械寄り」のものだった(そもそもContents of Address Register, Contents of Decrement Registerというワードからして機械寄りだ)のに対して、より抽象的なモデルを提唱する意味があったのであろう。

その後Landinはさらに有名なThe Next 700 Languagesという論文で、Lispよりも数学的記述に近い記法が使える関数型言語ISWIMを打ち出した。ISWIMは実用のための実装はされなかったものの、その後の関数型言語Lisp系やML系)の発展に大きく寄与したことで知られている。

WikipediaによるとこのISWIMのoperational semanticsをSECDマシンで定義しているとあるのだが、The Next 700 Languages自体にはSECDはでてこない・・・ ただThe Mechanical Evaluation of Expressionsで重要な概念であるApplicative ExpressionがISWIMのさらに下にあるものとして紹介されているので、ISWIMを作り上げた時にSECDマシンのことも念頭にあったのはたしかだろう。ちなみにNext 700 LanguagesにはLispの話もたくさん出てくる。あとlet式の初出。

その後1980年にPeter HendersonがSECDマシンを実際のインタプリタとしてLispKit Lispを作成、配布する。その頃大抵の大学のマシンに載っていたPascalで書かれたSECDマシンと純LISPからそのマシンの命令セットへのコンパイラで、純粋関数型言語でいろいろな言語仕様の研究などができたようだ。

LispKit LispについてはHenderson自身の書いた「Functional Programming Application and Implementation」が詳しい。(こちらの本も今回の記事のネタ本の一つなのだが、つい先週入手したばかりなのでまだちゃんと読み込めていない・・・)

SECDマシンの特徴と実装

とりあえずThe Architecture of Symbolic Computersの記述をベースに、抽象機械そのものと「純LISPに近いもののASTからSECDマシン命令へのコンパイラ」を実装してみた。

github.com

ただしLisp Advent Calendarなのに実装言語はOCamlである・・・ (最近自分が勉強中という理由) まあRich Hickeyも「静的型付き関数型言語は言語実装するときにはぴったり」と言っていたことだし大目に見てほしい。ちなみにSchemeやCでの実装はこちらに詳しい。QiitaにはHaskellでの実装もあった。

軽く実装を見ていきながらSECDマシンの特徴を追っていきたい。

SECDマシンのメモリモデルは以下二つのデータタイプで表現できる:

type t =
  | Int of int
  | Cons of int * int

「なんらかの値を表す整数」、「ポインタを表す整数を二つ持つConsセル」の二つだけ。これでプログラムもデータもすべて表現できる。このミニマルさがLispっぽい。

その簡単な二種類のデータがずらっと並んでいる配列がSECDマシンのメモリのすべてだ:

let cells = Array.make 100000 (Int 0)

(ここではとりあえずInt 0で初期化したものを10万用意している)

そしてそのメモリ配列のインデックスをもつ5つのレジスタ

let s = ref 0;
let e = ref 0;
let c = ref 0;
let d = ref 0;
let f = ref 1;

これらはすべてメモリセルのどこかを指している。SECDマシンの名前ははじめの四つのレジスタから来ている。Fレジスタかわいそう・・・

SレジスタはStack。SECDはスタックマシンで、Sレジスタが指しているリストの先頭からデータをとってプロセスしてまたそのリストの先頭に載せる、という挙動でデータが変更されていく。

EレジスタはEnvironment。変数の値を保持する環境を表すリストを指している。ちなみに環境はrib cage representationな連想リストをde Bruijn index化したもの。

CレジスタはControl。プログラムがSECDマシン命令にコンパイルされたあと、Consリスト化されメモリにロードされる。そのロードされたプログラム上で次実行するべき命令が載っているメモリセルを指すのがCレジスタだ。

DレジスタはDump。条件分岐や関数呼び出しがある場合、スタックや環境、コントロールをいったん別のものに変え、分岐や呼び出しが終了した時点で現在の場所に戻ってきたい。そのための「現在のS、E、Cレジスタの値を一時退避させておくリスト」をDレジスタが指す。

FレジスタはFree Cellから(多分)。未使用のメモリセルの位置を指している。新しいセルを使いたい時にはFレジスタの指す位置を使い、レジスタの数値はインクリメントする。多分一番仕様頻度は高いレジスタなのだがマシンの名前には入れてもらえなかった。Fレジスタかわいそう・・・

ただ、Fレジスタはよく使われるが、コード上で現れることは珍しい。すぐに関数によって隠蔽されてしまうからだ:

let makeInt i =
  let n = !f in
  (cells.(n) <- Int i; f := n + 1; n)

let makeCons i j =
  let n = !f in
  (cells.(n) <- Cons (i, j); f := n + 1; n)

新しい値やコンスセルを作る場合、かならずFree Cellから作るのでそのロジックを隠蔽する。そしてこれ以外でFree Cellを直接参照する必要がない。さらばFレジスタ

他のレジスタの指すリストの先頭から値を取ったり、逆に値を追加したりする関数:

let popR r = match cells.(!r) with
  | Cons (i, j) -> (r := j; i)
  | _ -> failwith "Register points to a non-cons cell"

let pushR r i =
  r := makeCons i !r

こういったヘルパー関数を使って、コントロールから一つずつ命令をとってきて実行していく(停止命令に遭遇するまで再帰でループ):

let runOneStep () = match cells.(popR c) withlet rec run () =
  if !c = 0 then ()
  else (runOneStep (); run ())

私が実装したこのSECDマシンを走らせるキモとなるのはrunOneStep関数で、Cレジスタの指すリストの先頭のConsセルのCARの指すIntの値を命令として認識して場合分けして実行する:

let runOneStep () = match cells.(popR c) with
  | Int 0 (* STOP *) -> c := 0
  | Int 1 (* NIL *) -> pushR s 0

例えばCレジスタの先頭(おもいっきり略した表現)がInt 0であるならば停止命令STOPとして認識し、Cレジスタを0番地(NILとして扱う)を指すようにする。

Int 1ならNILとして認識し、sスタックの先頭がNILへのポインタになるようにする(スタックをNILにするのではないことに注意)。

SECDにはSTOPやNILのような命令がいくつかある。資料によってその数字がまちまちなのはご愛嬌だ。(そもそもLandinの論文ではPrimitiveが存在することは明言してあってもそのPrimitiveが何かは書いていないので・・・) The Architecture of Symbolic Computersも実はすべてのPrimitiveを提示してくれないので、他をあたる必要がある。

私のSECDの場合は命令セットはSTOP, NIL, LDC, LD, CAR, CDR, ATOM, CONS, EQ, LEQ, ADD, SUB, MUL, DIV, REM, SEL, JOIN, LDF, AP, RTN, DUM, RAPの22個。

特筆すべきものをいくつかピックアップすると: * LDCで定数を、LDで変数をスタックにロードする * SELとJOINで条件分岐と分岐終了 * LDFで関数をその環境と一緒にスタックにロード、APでその関数を実行 * RAPで再帰関数の実行(DUMでその再帰関数のための「書き換え用の環境」を作って、LDFで再帰関数とその環境をスタックに乗せ、そしてRAPで実行する)

一番実装がややこしいのはRAPで、すでに何かが書き込まれたセル(Fレジスタからとってこなかったセル)に破壊的代入をするのはここだけ。他の命令の実装はすべて純粋関数でも書けるはず(書いている言語のメモリマネジメントにただのりする前提であれば)。

  | Int 21 (* RAP *) ->
      let fe = popR s in
      let func = car fe in
      let nenv = cdr fe in
      let arg = popR s in
      begin
        pushR d !c;
        c := func;
        pushR d (cdr !e);
        e := rplaca nenv arg;
        pushR d !s;
        s := 0;
      end; ()

C、E、Sレジスタの順番にDレジスタに値を移してから変更していく様が伝わると嬉しい。rplaca関数でnenvの先頭にargへのポインタを破壊的代入する。

個々の命令やLispから命令へのコンパイラの説明はまた別の機会に。

ちなみに実装中に使った文献はThe Architecture of Symbolic Computersだったのだが、この本はどちらかというと思想を含めたアイディアと背景を語ってくれる本で、実装のための情報はちょっと薄かった。ある程度想像を働かせてコードに変換していく必要がある。さらにRAP命令の説明に関しては間違いがあって、その部分では半日実装せずに悩んでしまった。(SECDマシンの状態遷移表のRAPの項目で、Eレジスタの内容の結果がrplaca((nil.e),v)になるはずがrplaca((nil.e),v).eになっている。一番ややこしいところで表記ミスがあるのはつらい・・・)

実装のための資料としてはHendersonのFunctional Programming Application and Implementationのほうがすぐれていそうだ。前述の通り、こちらはLispKit Lispという純粋関数型LispをSECDマシンで実装する詳細が載っている。

AoSCにはそれ以外の部分で価値が十分すぎるほどあるが。例えば今回話せなかった最適化やガベージコレクション各種、Call-by-Need化などの話題も載っている。そしてさらにLispLisp Machineへと話が続いていく。

Lisp Machine

古のLispの話をする場合大抵ノスタルジアとともに語られるトピックが「Lispマシン」だ。有名どころで言えばTexas Instruments社やXerox社、専業だとSymbolics社とLMI社が出していた、ハードウエアレベルでLispをサポートするコンピュータ。今でもインターネットの隅で「そのIDEの『新機能』、80年代にLisp MachineのSymbolics Generaで使ってたよ」的なコメントがつくのを散見することがある。Lispの強力さと先進性のひとつの現れだろう(そしてもしかすると弱点も、かも)

その源流はLisp発祥の地であるマサチューセッツ工科大学人工知能研で開発されたCONSマシンとその後継機であるCADRマシン(「次に来るもの」の意)にある。ちなみにCONSマシンは開発者Thomas Knightの修士論文の題材だったようだ。楽しい修士論文だな・・・

The Architecture of Symbolic ComputersではこのCADRマシンについてある程度詳しく解説している(といっても実装の雰囲気くらいまでだが)。実は個人的にはこれが最大の目的で読んでいた。

CADRのアーキテクチャはSECDマシンに非常に近いようだ。IntやConsといったデータタグのついたメモリと、そのタグごとひとつのワードとして処理できるだけの容量をもったプロセッサチップ。SECDマシンをハードウエア化するとこのような形になるだろうか、と思わせるところがある。

いくつかの顕著な違いとしては

  • タグの種類が多い。さすがにIntとConsだけというのは現実的には難しく、ハードウェアサポートとともにFloatだとか「文字列へのポインタ」とかのタグが多数用意されていた
  • すべてのデータをメインメモリに持つモデルではなく、スタックやコントロールなどの上位にあるデータを置くキャッシュ的な機構、Push Down Listというものが用意されていた
  • Consだけではなく、連続したメモリ空間にデータを載せることもでき、「あるデータが連続したメモリに載っている」という情報をタグで持たせることでデータアクセスの効率化(上記のSECDマシン実装だといたるところでデータアクセスがLinear timeになってしまう)

といったものがあるようだ。

命令セットについてもmicrocode、macrocodeそしてMacLispでプログラムが書けるようになっており、microcodeやmacrocodeとSECD命令セットの関係はAoSCではあまりはっきりとは書いていない(macrocodeがより一般的なスタックマシンの命令セットに近いものである、という記述はある)。

さらにCADRマシンの開発レポートであるMIT AI Memo 528 - CADRではSECDマシンへの言及がない。実際どの程度この仮想マシンを意識してCONSマシン、CADRマシンが開発されたのかは残念ながら不明なようだ。

AoSCはLisp machineの実装のおおまかな雰囲気を追うには十分だが、もしある日あなたが天啓を受けてLisp machineを現代に蘇らせようと思った時はこれ以外の文献も多分必要になると思う。

最後に

抽象機械SECDは実装も比較的簡単なうえ、純LispやISWIMなどの関数型言語コンパイル先として楽なので、言語実装で遊んでみたい人にはオススメだと思う。さらにLispや計算機科学の歴史に浸った気分になれるというボーナス付き。

またThe Architecture of Symbolic ComputersにはSECDマシン以外にもCall-by-NeedなGraph ReductionベースのGマシン、論理型プログラミングと推論をサポートするWarrenマシンなど、von Neumannモデルとは一線を画す実行モデルを持った抽象機械がいくつも紹介されている。機会があったら是非(大学図書館などで)手に取ってみてほしい。

参考文献

The Architecture of Symbolic Computers Peter M. Kogge

Functional Programming Application and Implementation Peter Henderson

The Mechanical Evaluation of Expressions - Peter J. Landin

The Next 700 Languages - Peter J. Landin

AI Memo 528 - CADR Thomas F. Knight, Jr., David Moon, Jack Holloway, Guy L. Steele, Jr.

LispKit Lisp - Think Stitch - PRINCIPIA

SECDマシン - Qiita

SECD machine - Wikipedia