オレオレF#コンパイラを作って集合論の記号（∩とか∪とか）の演算子が使えるようにする

投稿日: 2014/03/13 作成者: masuda

を同時に実践しようと思って、F#のコンパイラを半日ほどいじってみました。

F# のコンパイラのソースコードは↓でダウンロードができます。

F# PowerPack with F# Compiler Source Drops – Source Code
https://fsharppowerpack.codeplex.com/SourceControl/latest

中身が見れるということは、修正できるということで、修正できるということは何かあったら自分で修正しろって訳ですね。たぶん。

■なぜ、コンパイラを弄るのか？

F# の場合、演算子は記号の組み合わせで作ります。この記号の組み合わせで、多用な演算子が作れるわけですが「+++」とか「—」とか一定の記号の組みあわせしかできないんですよね。

F# で Fizz-Buzz 番外編 – 新しい演算子の作成と、パイプライン演算子 : @jsakamoto
http://devadjust.exblog.jp/11067474/

を見たあたりから「残念、F# って記号の組み合わせしかダメなのか」と思っていたわけですが、Scala ができるわけだから（できるというのはつい先日知りました。正確には先のオレオレF#コンパイラを作った後に知りました）、F# でできない訳はないだろうってことです。
ただし、Scala の場合は、「演算子」を統一的にメソッドに置き換えるのですが、F# の場合は関数に括弧を入れないので、演算子と関数（キーワード）とは別に管理しているようです。まあ、カリー化をすると、これはこれでいいような気がします。表面的には演算子を関数としても使えるようです。

少しコンパイラを齧った方は分かると思うのですが、コンパイラを作るときには lex と yacc を使って文字解析と構文解析をします。F# には fslex と fsyacc という F# 実装のものがあります。となると、演算子を記号縛りにしているのは lex か yacc あたりを見れば OK と見当がつきます。

集合にはなっていませんが、集合の記号だけ使うと、以下のように演算子を定義しますが…∪のところでエラーになります。

open System
let (∪) x y = x + y
let (∩) x y = x - y

let ans1 = 10 ∪ 20
let ans2 = 10 ∩ 20
printfn "ans1:%A" ans1
printfn "ans2:%A" ans2

なので、代わりに下のような「代替」の演算子を作るわけですが…これって、数式をプログラムに直すときに無駄なギャップになるんですよね。

open System
let (+++) x y = x + y
let (---) x y = x - y

let ans1 = 10 +++ 20
let ans2 = 10 --- 20
printfn "ans1:%A" ans1
printfn "ans2:%A" ans2

できることならば、紙に書いた数式からプログラムコードに平たく直したいのです。そうするほうが、バグが混入しにくくなりますよね。wxMaxima と同じ発想です。

となると、演算子を記号のみにしてしまっている lex の部分に「∩」や「∪」を入れればなんとなるんではないかと。

■F#コンパイラを自前ビルドする

F# PowerPack with F# Compiler Source Drops – Source Code
https://fsharppowerpack.codeplex.com/SourceControl/latest

からソースコードをダウンロードして、compiler\3.1\Nov2013\README.html にある通りに、proto comiler を作ります。開発用のコマンドラインを「管理者権限」で実行して、以下を実行。

  cd src
  gacutil /i ..lkg\FSharp-2.0.50726.900\bin\FSharp.Core.dll
  msbuild fsharp-proto-build.proj
  ngen install ..Protonet40binfsc-proto.exe

これをやらないと、Visual Studio で F# プロジェクトがロードできません。
コンパイラ自体は、Fsc プロジェクトです。文字解析、構文解析の部分は、FSharp.Compiler プロジェクトの
lex.fsl と pars.fsy になります。それぞれ、ビルドを実行すると、fslex と fsyacc が使われます。

ひとまず Fsc をビルドします。結構時間が掛かりますが（10分ぐらい？）ビルドができて、自前のF#コンパイラができます。

■演算子を増やしてみる

最終的には、自由な演算子を作りたいのですが、暫定的に「∩」や「∪」だけを追加します。どうもカリー化の関係で文字解析部分で演算子を記号にしないとうまくいかなそうなのですが、F#の場合、関数定義などは前方参照のみなので、構文解析側（pars.fsy）をうまく修正すれば、回避できそうかなと。再帰関数の rec も外せそうな気がします。

lex.fsl を開いて、174行目あたり

let op_char = '!'|'$'|'%'|'&'|'*'|'+'|'-'|'.'|'/'|'<'|'='|'>'|'?'|'@'|'^'|'|'|'~'|':'
	|'あ'|'い'|'う'|'え'|'お'
	|'∪'|'∩'

な感じで、使いたい演算子を追加します。この部分は [‘あ’-‘ん’]のように範囲指定できるかもしれません（試していない）。

237行目あたりで、以下のように演算子の解析を入れます。

rule token args skip = parse
 | ignored_op_char* ('あ'|'い'|'う'|'え'|'お'|'∪'|'∩') op_char* { checkExprOp lexbuf; PLUS_MINUS_OP(lexeme lexbuf) }
 | ident
     { Keywords.KeywordOrIdentifierToken args lexbuf (lexeme lexbuf) }

キーワードを解析している Keywords.KeywordOrIdentifierToken の前に入れてしまうのがミソです。token を PLUS_MINUS_OP にしていますが、これは何でもOKです。どうせ再定義してしまうので。

これでビルドをしてから、先の F# コードをオレオレF#コンパイラでコンパイルしてみてください。うまくビルドができて、実行できます。ぱちぱちぱち。

open System
let (∪) x y = x + y
let (∩) x y = x - y

let ans1 = 10 ∪ 20
let ans2 = 10 ∩ 20
printfn "ans1:%A" ans1
printfn "ans2:%A" ans2

演算子は「あいうえお」のように複数でも定義できるし「あ+あ+あ」のように元の記号と組み合わせもできます。このあたりは、論理記号、集合論の記号を入れておきたいところです。

数学記号の表 – Wikipedia
http://ja.wikipedia.org/wiki/%E6%95%B0%E5%AD%A6%E8%A8%98%E5%8F%B7%E3%81%AE%E8%A1%A8

■演算子とキーワードをデバッグする

演算子のチェックは checkExprOp で、キーワードのチェックは KeywordOrIdentifierToken で行っているので、ここにデバッグログを入れておきます。

演算子チェックは、lex.fsl 内

let checkExprOp (lexbuf:UnicodeLexing.Lexbuf) =
    printfn "exprOp %A" (lexeme lexbuf)
    if String.contains (lexeme lexbuf)  ':' then
        deprecatedWithError (FSComp.SR.lexCharNotAllowedInOperatorNames(":")) lexbuf.LexemeRange;
    if String.contains (lexeme lexbuf)  '$' then
        deprecatedWithError (FSComp.SR.lexCharNotAllowedInOperatorNames("$")) lexbuf.LexemeRange

キーワードチェックは lexhelp.fs 内

    let KeywordOrIdentifierToken args (lexbuf:UnicodeLexing.Lexbuf) s =
        printfn "keyword %A" s
        if not permitFsharpKeywords && List.mem s unreserveWords then
...

これを入れた状態でF#コードをコンパイルすると、演算子/キーワードの状態がわかります。
あとは、集合論の記号あたりを入れて、ざっと実装していくということで。

カテゴリー: F# パーマリンク

オレオレF#コンパイラを作って集合論の記号（∩とか∪とか）の演算子が使えるようにする への1件のコメント

  1. masuda のコメント:
    2014/03/13 3:19 pm

    lex.fsl と pars.fsy を保存するときは、UTF-8 に変更して保存すること。そのまま保存するとSJISになるので。

コメントは停止中です。