Arantium Maestum

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

EoPLのLetlangをocamllex/menhir/duneで実装してみた

前回の記事の構成に従って、簡単な言語のインタプリタを実装してみた。

Essentials of Programming Languagesという本の最初に出てくるLETという言語で、機能としては整数値の引き算、0チェック、if式による分岐、let式による変数束縛。関数定義などはできない。

一例:

let x = 5 in
  let y = if zero?(x) then 1 else 2 in
    -(x, y)

これは3に評価される。

ディレクトリ構成は以下の通り:

├── bin
│   ├── dune
│   └── ex.ml #ライブラリを呼び出して実行するプログラム
├── dune-project
└── src #ライブラリ部分
    ├── dune
    ├── env.ml #変数環境の実装
    ├── env.mli #変数環境のインタフェース
    ├── eval.ml #評価器の実装
    ├── eval.mli #評価器のインタフェース
    ├── exp.mli #AST式の型定義
    ├── lexer.mll #OCamllexを使ったLexer
    ├── parser.mly #Menhirを使ったParser
    ├── val.ml #評価結果である「値」の実装
    └── val.mli #「値」のインタフェース

LETには文は存在せず、式しかない。のでASTもすべて式だけで表現できる。

その式の型はsrc/exp.mliに定義されている:

type t =
  | Const of int #数値リテラル
  | Diff of t * t #二つの式の評価値の差
  | ZeroP of t #式の評価値が0| If of t * t * t #If| Var of string #変数
  | Let of string * t * t #letによる変数束縛

Expモジュールはこの一つの型のためのみに存在するので、モジュール内で定義される型はOCamlの慣習に則ってtype tである。Expモジュールの外からはExp.tなどとモジュールを指定して使う。

また、Expモジュールには型の定義しか存在しないので、インタフェースである.mliだけが書かれている。

式を評価した結果の値を表現する型はsrc/val.mlisrc/val.mlで定義されている。

val.mli:

type t =
  | Num of int
  | Bool of bool

val to_str: t -> string

val.ml:

type t =
  | Num of int
  | Bool of bool

let to_str = function
  | Num n -> string_of_int n
  | Bool b -> if b then "True" else "False"

型定義が.ml.mliで重複するのはよくあることらしい。

LET言語では、式を評価した結果は数値か真偽値のみとなる。それを表現する型と、それを文字列に変換する関数。

Parser

src/parser.mly:

%token <int> INT
%token <string> ID
%token DIFF
%token LPAREN
%token RPAREN
%token COMMA
%token ZERO
%token IF
%token THEN
%token ELSE
%token LET
%token EQ
%token IN
%token EOF

%start <Exp.t> f

%%

f : e = expr; EOF { e }

expr :
  | n = INT { Exp.Const n }
  | DIFF; LPAREN; e1 = expr; COMMA; e2 = expr; RPAREN { Exp.Diff (e1, e2) }
  | ZERO; LPAREN; e = expr; RPAREN { Exp.ZeroP e }
  | IF; e1 = expr; THEN; e2 = expr; ELSE; e3 = expr { Exp.If (e1, e2, e3) }
  | v = ID { Exp.Var v }
  | LET; v = ID; EQ; e1 = expr; IN; e2 = expr { Exp.Let (v, e1, e2) }

これは普通のOCamlではなく、Menhirというパーサジェネレータに与えるOCamlチックな独自表記である。なのでファイル拡張子もmlyである。まずparser.mlyが普通のOCamlに変換されてから全体がコンパイルされる。(そういったbuild指定はduneファイルで行われる)

Lexerから受け取れるトークンをまず指定し、そのトークンの組み合わせのパターンマッチでExp.t型の戻り値を返す(パターンマッチは当然再帰的)。

最終的に%start <Exp.t> ff : e = expr; EOF { e }の部分で定義されているfがパーサ関数となる。

Lexer

LexerはOcamllexを使う。Parserと同じく、OCamlではなく独自表記の.mll拡張子。

src/lexer.mll:

{
open Parser
}

let digit = ['0'-'9']
let number = '-'? digit digit*
let whitespace = ['\t' ' ' '\n']
let char = ['a'-'z' 'A'-'Z']
let identifier = char (char|digit)*

rule tokenize = parse
  | whitespace+ { tokenize lexbuf }
  | number as n { INT (int_of_string n ) }
  | "-" { DIFF }
  | "(" { LPAREN }
  | ")" { RPAREN }
  | "," { COMMA }
  | "zero?" { ZERO }
  | "if" { IF }
  | "then" { THEN }
  | "else" { ELSE }
  | "let" { LET }
  | "=" { EQ }
  | "in" { IN }
  | identifier { ID (Lexing.lexeme lexbuf) }
  | eof { EOF }

このソースがOcamllexに変換されてOCamlコードになると、rule tokenize = parse ...tokenizeがlexer関数名となる。(これもfでもよかったかも・・・)

変数環境

LETにはlet式による変数束縛があるので、式の中で変数が出てきた場合、なんの値に束縛されているかを評価時に調べなくてはいけない。

そのため、式の評価には式そのものの他に変数環境が必要である。src/env.mlisrc/env.mlに定義されている。

env.mli:

type t

val empty: t

val find: t -> string -> Val.t option
val extend: t -> string -> Val.t -> t

env.ml:

type t = (string * Val.t) list

let empty = []

let rec find env s = match env with
  | [] -> None
  | (s', v)::env' -> if s = s' then Some v else find env' s

let extend env s v = (s, v)::env

変数環境の実装は単なる(変数名 * 値)のタプルのリストで、初期値emptyと関数findextendが定義されている。.mliではtype tとしか定義されていないのでEnvモジュールの外では(string * Val.t) listVal.t型として扱うことはできない(型の実装が隠蔽されている)。

評価器

LET言語の評価器はsrc/eval.mlisrc/eval.mlで定義されている。

eval.mli:

val f: Exp.t -> Val.t

eval.ml:

let rec eval' env = function
  | Exp.Const n -> Val.Num n
  | Exp.Diff (e1, e2) -> (match eval' env e1, eval' env e2 with
      | Val.Num n, Val.Num m -> Val.Num (n - m)
      | _ -> failwith "Diffing non-numeric values")
  | Exp.ZeroP e -> (match eval' env e with
      | Val.Num n -> Val.Bool (n = 0)
      | _ -> failwith "Zero-checking non-numeric value")
  | Exp.If (e1, e2, e3) -> (match eval' env e1 with
      | Val.Bool b -> eval' env (if b then e2 else e3)
      | _ -> failwith "If-condition on non-boolean value")
  | Exp.Var s -> (match Env.find env s with
      | Some x -> x
      | None -> failwith "Variable not in environment")
  | Exp.Let (s1, e1, e2) ->
      let v1 = eval' env e1 in
      let env' = Env.extend env s1 v1 in
      eval' env' e2

let f = eval' Env.empty

Evalモジュールは一つの関数fのみを外部に提供する。内部実装としては、式とともに変数環境を引数にとる再帰関数eval'をまず定義し、eval'に空の変数環境を渡したものがfになる。

Build指示

Buildの指示は前述の通りsrc/duneに書いてある:

(menhir
  (modules parser))

(ocamllex lexer)

(library
  (name letlang)
  (modules_without_implementation exp))
  • Parserはmenhirで前処理すること
  • Lexerはocamllexで前処理すること
  • Expモジュールはインタフェース.mliのみであること
  • ライブラリ全体の名前はLetlangであること

が指定されている。

実行プログラム

bin/ex.ml:

open Letlang

let _ =
  Lexing.from_channel stdin
  |> Parser.f Lexer.tokenize
  |> Eval.f
  |> Val.to_str
  |> print_endline

stdinをパーサに渡し(パーサはParser.fにLexer.tokenizeを第一引数として渡したもの)、評価し、結果を文字列化して出力する。

これのbuild指示はbin/duneにある:

(executable
  (name ex)
  (libraries letlang))

それ以外

ついでにsrcbinの上のディレクトリにdune-projectというファイルがある:

(lang dune 1.0)
(using menhir 1.0)

duneとmenhirのバージョン指定。

実行

実行するにはdune execというコマンドを使う。

たとえば

> echo "let x = 5 in -(x, 1)" | dune exec bin/ex.bc
4

あるいは記事冒頭にあるサンプルプログラムのtest.txtファイルを作って:

let x = 5 in
  let y = if zero?(x) then 1 else 2 in
    -(x, y)

catで流し込む:

> cat test.txt | dune exec bin/ex.bc
3

成功。

OCamlで言語処理系覚え書き ocamllex/menhirパーサをduneでビルドする

OCamlでocamllexとmenhirを使ったパーサを書き、duneでビルドする場合の構成を調べていて、ようやく少しわかってきたので備忘録的に書き留めておく。

例として整数のたし算をパースして評価する非常に簡単な計算プログラムを実装する。

ディレクトリ構成

.
├── dune-project
├── src
│   ├── ast.ml
│   ├── parser.mly
│   ├── lexer.mll
│   └── dune
└── bin
    ├── ex.ml
    └── dune

トップレベ

dune-projectが以下のように定義されている:

(lang dune 1.0)
(using menhir 1.0)

srcディレクトリ内

src/ast.mlでAST定義:

type expr =
  | Int of int
  | Plus of expr * expr

そのAST定義を使ってMenhir Parserをsrc/parser.mlyで定義:

%{
open Ast
%}

%token LPAREN
%token RPAREN
%token EOF
%token <int> INT
%token PLUS

%left PLUS

%start <Ast.expr> prog

%%

prog:
  | e = expr EOF { e }

expr:
  | LPAREN; e = expr; RPAREN { e }
  | i = INT { Int i }
  | e1 = expr; PLUS; e2 = expr { Plus (e1, e2) }

parserで定義されているtokenを出力するsrc/lexer.mll:

{
open Parser
}

let digit = ['0'-'9']
let number = '-'? digit digit*
let whitespace = ['\t' ' ' '\n']

rule tokenize = parse
  | whitespace+ { tokenize lexbuf }
  | "(" { LPAREN }
  | ")" { RPAREN }
  | "+" { PLUS }
  | number as n { INT (int_of_string n ) }
  | eof { EOF }

srcディレクトリにあるast.mlparser.mlylexer.mlladderというライブラリとしてビルドするためのsrc/duneファイル:

(menhir
  (modules parser))

(ocamllex lexer)

(library
  (name adder))

binディレクトリ内

adderライブラリを使うmain関数的なものが定義されているex.ml:

open Adder

let rec pprint = function
  | Ast.Int n -> string_of_int n
  | Ast.Plus (n, m) -> Printf.sprintf "(Plus %s %s)" (pprint n) (pprint m)

let rec eval = function
  | Ast.Int n -> n
  | Ast.Plus (n, m) -> eval n + eval m

let _ =
  let lexbuf = Lexing.from_channel stdin in
  let expr = Parser.prog Lexer.tokenize lexbuf in
  Printf.printf "%s = %d\n" (pprint expr) (eval expr)

bin/duneファイル:

(executable
  (name ex)
  (libraries adder))

実行

shellで:

> echo '1+2+(3+4)+5' | dune exec bin/ex.bc
(Add (Add (Add 1 2) (Add 3 4)) 5) = 15

参考資料

qiita.com

github.com

lambda関数だけのPython世界で四則演算

お察しかもしれないがラムダ計算についての話である。

最近あったPyConで気になるチュートリアルがあった:

www.youtube.com

このブログでも何回か話題にしたことがあるDavid Beazleyが教えているチュートリアルで、

Pythonのlambdaキーワードで作る無名関数だけで、ラムダ計算の世界をのぞいてみよう

という趣旨。

かなり面白かったので、備忘録的にメモってみる&内容を少しだけ発展させて自然数のわり算まで実装してみる。

ルール

Pythonのlambda関数しかない世界。

なのでできるのはlambda関数の作成と呼び出しのみ。

さらにいうと単一引数のみ。

例えばこんな感じ:

X = lambda x: x
Y = lambda y: y(X)
Z = lambda x: lambda y: lambda z: z(x)(y)

Z関数ではcurryingにより、単一引数ながらも複数の値を入力として受け取る関数が定義できることがわかる。記述がややこしくなるのを避けるため、今後このようなcurryingされている関数のことを「ある関数がn個の引数をとる」「ある関数の第一引数、第二引数」などという表現をする。

便宜上トップレベルでは変数への代入をしているが、あくまで名前付けのためのみ許される。

言い換えると、変数を値の式ですべて書き直すことが可能である必要がある。

このルールでどうすれば計算を表現することができるか。

真偽値

まずはTRUE/FALSE:

TRUE = lambda x: lambda y: x
FALSE = lambda x: lambda y: y

この世界では

  • 「真」は「引数xとyを順番に受け取り、xを返す関数」
  • 「偽」は「引数xとyを順番に受け取り、yを返す関数」

に対応づけられる。

そうするとNOT, AND, ORも以下のように定義できる:

NOT = lambda x: x(FALSE)(TRUE)
AND = lambda x: lambda y: x(y)(x)
OR = lambda x: lambda y: x(x)(y)

データ構造

複数のデータをひとつのオブジェクトとしてまとめて、単一引数に渡せるようにしたい。

LispでもおなじみのCONSセルの出番である:

CONS = lambda x: lambda y: lambda f: f(x)(y)
CAR = lambda x: x(TRUE)
CDR = lambda x: x(FALSE)

CONSは引数二つをとって、ある関数を返す。その関数にTRUEを与えるとCONSの第一引数、FALSEを与えると第二引数を返す。

CARとCDRはその関数を受け取ってTRUE/FALSEを与えるだけ。

数字

ここから数字と対応づけられる関数が何か、を考えていく。話を簡単にするために0からはじまる自然数のみ。

考えていく、と言ったがそれは嘘で、昔から知られているチャーチ数を使うだけ。

ZERO = lambda f: lambda x: x
ONE = lambda f: lambda x: f(x)
TWO = lambda f: lambda x: f(f(x))

数字はすべて二つの引数をとる関数で、「第二引数に第一引数をn回適用した結果を返す関数」を自然数nに対応させる。

任意の自然数を作れるように、「ある数より1大きい数を作る関数」SUCCを定義する:

SUCC = lambda n: lambda f: lambda x: f(n(f)(x))

fが適用される回数が一回上がる。

SUCCを使えばたし算ができる:

ADD = lambda n: lambda m: n(SUCC)(m)

この関数は実は少し単純化できる:

ADD = lambda n: n(SUCC)

というのも、この世界だとすべてのものが関数なので、以下の等式が(ほとんどの場合)あてはまる:

lambda x: X(x) = X

(先行評価・遅延評価の関連であてはまらないケースについては後述する)

なので

lambda n: lambda m: n(SUCC)(m) = lambda n: n(SUCC)

となる。

たし算を使ってかけ算を定義:

MUL = lambda n: lambda m: n(ADD(m))(ZERO)

次にひき算を定義したいのだが、そのためには「一個前の数」を返すPRED関数が必要になる。

ここで以前定義したCONSを使う:

PRED = (
  lambda n: 
    CDR
      (n(lambda x: CONS(SUCC(CAR(x)))(CAR(x)))
        (CONS(ZERO)(ZERO))))

(横幅が足りなくなってきたので()内では複数行に分割できるというPython構文を利用している)

この定義は:

自然数n-1は(0, 0), (1, 0), (2, 1), (3, 2), (4, 3), ...という無限列のn番目のCONSセルのCDR

という考察がベースとなっている。ちなみにこの定義だとZEROのPREDはZEROのままであることに注意。

PREDがあればSUBは簡単:

SUB = lambda n: lambda m: m(PRED)(n)

さらに比較用の関数:

ISZERO = lambda n: n(lambda _: FALSE)(TRUE)
LE = lambda n: lambda m: ISZERO(SUB(n)(m))
EQ = lambda n: lambda m: AND(LE(n)(m))(LE(m)(n))
LT = lambda n: lambda m: AND(LE(n)(m))(NOT(LE(m)(n)))

さて、残る四則演算はわり算のみとなったのだが・・・

考え方としては

nからmを繰り返し引いていって、残った数がmより小さくなるまでの回数

を返す関数を作りたい。この「繰り返し」を実装するために再帰ができるようにしたい。

再帰

まずはルール違反な例を挙げる:

BADFACT1 = lambda n: ISZERO(n)(ONE)(MUL(n)(BADFACT1(PRED(n))))
BADFACT2 = lambda n: ISZERO(n)(ONE)(lambda _: MUL(n)(BADFACT2(PRED(n)))(_))

BADFACT1はそもそも無限再帰になってしまいうまくいかない。ISZERO(n)(m)(p)でIF分岐しているのだが、nもmもpもすべて評価してからnの値によってmかpかを選ぶ、という評価戦略になっているのが理由だ。

無限再帰を避けるため、BADFACT2では

lambda x: X(x) = X

があてはまらないケースを利用している。関数の中に入れることでXの評価を遅延させることができる。最終的にすべて評価されれば値は同じになるはずだが、これだと無限再帰を起こさない。

しかし、このようにBADFACT2の定義の中でBADFACT2という名前を利用するのはルール違反である。

この定義を「名前なしで」書こうとするとやはり無限ループが起きて、式の長さが無限になってしまう。

ルール内で再帰を実現するためにはYコンビネータを使う:

Y = (
  lambda f: 
    (lambda x: lambda _: f(x(x))(_))
    (lambda x: lambda _: f(x(x))(_)))

Yコンビネータに関しては解説できるほど理解が進んでいないのであらかた割愛するが、一点だけ。

普通はYコンビネータといえばlambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))のような形で出てくるのだが、やはり遅延評価して無限再帰を回避するために追加でlambda _: ...というステップを追加している。

Yコンビネータを使えばFactorialやFibonacciがルール内で以下のように書ける:

FACT = (
  Y
    (lambda f: lambda n: 
      ISZERO(n)
        (ONE)
        (lambda _: MUL(n)(f(PRED(n)))(_))))

FIB = (
  Y
    (lambda f: lambda n: 
      LE(n)(TWO)
        (ONE)
        (lambda _: ADD
          (f(PRED(n)))
          (f(PRED(PRED(n))))(_))))

わり算

これでピースは全て揃った。あとは書くだけ:

DIV = (
  lambda n: lambda m: 
    Y
      (lambda f: lambda x: 
        LT(CAR(x))(m)
          (CDR(x))
          (lambda _: f(CONS(SUB(CAR(x))(m))(SUCC(CDR(x))))(_)))
      (CONS(n)(ZERO)))

考え方としては前述の通り

nからmを繰り返し引いていって、残った数がmより小さくなるまでの回数

を返す関数。初期値がnとZEROのCONSセル(p, k)に対して再帰的に(p-m, k+1)に変えていき 、pがm未満になった時点でkを返す。

普通のPythonで書くならこんなロジック:

def divide(n, m):
  def f(p, k):
    return k if p < m else f(p-m, k+1)
  return f(n, 0)

使ってみる

まずは他にいくつか数字を定義しておく:

THREE = ADD(ONE)(TWO)
FIVE = ADD(TWO)(THREE)
TEN = ADD(FIVE)(FIVE)
HUNDRED = MUL(TEN)(TEN)

この世界の数字に対応するPythonの数字をプリントする関数を定義:

def show(n):
    print(n(lambda x: x+1)(0))

この関数はラムダ計算世界の結果を、我々が理解できるように出力するためだけに使う(演算には使われていない)。のでルール外の存在。

この関数を使ってFACT, FIB, DIVを使った計算結果を出力してみる:

>>> show(FACT(FIVE))
120

>>> show(FIB(TEN))
55

>>> show(DIV(HUNDRED)(THREE))
33

成功。

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を実装したりしてみる。

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