インストール
インタプリタ
FSharpでは代数データ型とパターンマッチングを使う事でインタプリタを以下のように書く事が出来ます。
以下のプログラムは (1 + 2) * 3を計算して出力する物です。
Eが式を表し、ELdが数値をEAddが足し算、ESub,EMul,EDivがそれぞれ引き算、かけ算、割算を表します。
オブジェクト指向で考えれば、EというabstractなクラスとEを継承したクラスがELd,EAdd,ESub,EMul,EDivを定義した感じです。
evalが値を評価する関数でEを受け取って計算をする関数です。
F#では再帰的関数を定義するときはlet recを使って定義します。
match構文を使う事で、Eの全てのパターンについて書き下す事が出来ます。
また、バインディングの機能を使う事で、各変数メンバに名前を付けてアクセスする事が出来るように書く事が出来ます。この機能のおかげで、とくに定義を見に行かなくても、関数のその場所だけ見れば、どのような事が行われるかが直感的に理解出来ます。
また、FSharpはPythonやHaskellのように、ネストに寄るブロックいわゆるオフサイドルールを使って関数を書く事が出来るので、かっこを書かなくて済みます。
関数はreturnと書かなくても、数値がそのまま返却されます。たとえば、main関数はuintを返却する必要があるのですが、0とだけ最後に書けば0が返ります。
open System
type E =
| ELd of int
| EAdd of E * E
| ESub of E * E
| EMul of E * E
| EDiv of E * E
let rec eval(e:E):int =
match e with
| ELd(i) -> i
| EAdd(a,b) -> eval(a) + eval(b)
| ESub(a,b) -> eval(a) - eval(b)
| EMul(a,b) -> eval(a) * eval(b)
| EDiv(a,b) -> eval(a) / eval(b)
let i = eval(EMul(EAdd(ELd(1),ELd(2)),ELd(3)))
Console.WriteLine i
パーサ
FSharpの場合はFsLexとFsYaccやFParsec等のコンパイラコンパイラ(コンパイラを作る為のツール)があります。高速で、フォーマルな文法を決めてパーサを書きたい場合はこれらのツールを使うと良いです。
しかし、これらのツールを使うのは慣れるまでは直感的ではないので難しいところがあります。
そこで、ここでは、再帰下降型のパーサを紹介します。
再帰関数としてパーサを書くので直感的に把握しやすいはずです。
open System
open System.Text.RegularExpressions
type E =
| ELd of int
| EAdd of E * E
| ESub of E * E
| EMul of E * E
| EDiv of E * E
let rec eval(e:E):int =
match e with
| ELd(i) -> i
| EAdd(a,b) -> eval(a) + eval(b)
| ESub(a,b) -> eval(a) - eval(b)
| EMul(a,b) -> eval(a) * eval(b)
| EDiv(a,b) -> eval(a) / eval(b)
let parse(str:String):E =
let (|ParseRegex|_|) regex str =
let m = Regex(regex).Match(str)
if m.Success
then Some (List.tail [ for x in m.Groups -> x.Value ])
else None
(**
* 予測されたトークンを取り除く
*)
let rec eat(es:(E * string), eatStr:string):(E * string) =
let eatReg = "^[ \\r\\n\\t]*"+eatStr+"(.*)$"
match es with
| (a,ParseRegex eatReg [str]) -> (a, str)
| _ -> raise (Exception "error")
(**
* 足し算かterm
*)
let rec exp(str:string):(E * string) =
let rec exp2(es:(E * string)):(E * string) =
match es with
| (a, ParseRegex "^[ \r\n\t]*\\+(.*)$" [str]) ->
let (b, str2) = term(str)
exp2(EAdd(a, b), str2)
| (a, ParseRegex "^[ \r\n\t]*-(.*)$" [str]) ->
let (b, str2) = term(str)
exp2(ESub(a, b), str2)
| _ -> es
exp2(term(str))
(**
* 掛け算か、fact
*)
and term(str:String):(E * String) =
let rec term2(es:(E * String)):(E * String) =
match es with
| (a, ParseRegex "^[ \r\n\t]*\*(.*)$" [ str]) ->
let (b, str2) = fact(str)
term2(EMul(a, b), str2)
| (a, ParseRegex "^[ \r\n\t]*/(.*)$" [ str]) ->
let (b, str2) = fact(str)
term2(EDiv(a, b), str2)
| _ -> es
term2(fact(str))
(**
* 数字あるいは( exp )
*)
and fact(str:String):(E * String) =
match str with
| ParseRegex "^[ \r\n\t]*([0-9]+)(.*)$" [i;str] -> (ELd( Int32.Parse(i) ) ,str)
| ParseRegex "^[ \r\n\t]*(\\()(.*)$" [str] -> eat(exp(str), "\\)")
| _ -> raise (Exception "error")
// expの呼び出しとエラーの処理
match exp(str) with
| (a, ParseRegex "^[ \r\n\t]*$" []) -> a
| _ -> raise (Exception "error")
let e = parse ("1+2*3")
let i = eval(e)
Console.WriteLine i
スタックマシンコンパイラ
インタプリタは作れましたので、スタックマシンとスタックマシンのコンパイラを作ってみましょう。スタックマシンは例えば、ForthやJava、.Net Framework、PostScript等で採用されています。
プログラムの操作をスタックに対して行うようにする事で、構造化されたプログラムを直列的に扱う事が出来ます。
また、レジスタ割り付けも必要ありません。
また、スタックをリストとして表すと、VMをとてもスッキリ書く事が出来ます。
type Code =
| CAdd
| CMul
| CSub
| CDiv
| CLd of int
let compile (e:E):Code list =
let rec comp(e:E,codes:Code list):Code list =
match e with
| ELd(i) -> CLd(i) :: codes
| EAdd(a,b) -> CAdd :: comp(a, comp(b, codes))
| ESub(a,b) -> CSub :: comp(a, comp(b, codes))
| EMul(a,b) -> CMul :: comp(a, comp(b, codes))
| EDiv(a,b) -> CDiv :: comp(a, comp(b, codes))
List.rev (comp(e, []))
let vm(codes:Code list):int =
let rec f(s:int list, c:Code list):int =
match (s, c) with
| (a::s, []) -> a
| (s,CLd(i)::c) -> f(i::s, c)
| (a::b::s, CAdd::c) -> f(a+b::s, c)
| (a::b::s, CSub::c) -> f(a-b::s, c)
| (a::b::s, CMul::c) -> f(a*b::s, c)
| (a::b::s, CDiv::c) -> f(a/b::s, c)
| (_, _) -> 0
f([], codes)
let e = parse ("1+2*3")
let codes = compile(e)
Console.WriteLine(codes)
Console.WriteLine(vm(codes))
x86コンパイラ
次はネイティブコンパイラをつくります。
// test.c
# include <stdio.h>
int add(int a, int b) { return a + b; }
int sub(int a, int b) { return a - b; }
int mul(int a, int b) { return a * b; }
int div(int a, int b) { return a / b; }
print_i(int a) { printf("%d¥n", a); }
int main() {
int a = add(1,2);
print_i(a);
}
というプログラムを作って
gcc -S test.c
と実行して出来た、test.sを見ますと
gcc -S -m32 test.c
で重要な所だけ見ますと、addlが足し算、sublが引き算、imullがかけ算、cltdとidivlで割算になります。
で、うまく、print_iを呼び出す所を書き換えてやればうまく行くはずです。
で、pushl,poplでマシンスタックに値を入れたり、出したり出来るので、その辺を考えてうまい事プログラムしてやれば良いはずです。
で、とりあえず、習うより慣れろです。
以下のプログラムをコピペして、mainを書き換えて実行してみましょう。
asmは、ファイル出力の為のモジュールで、execがプロセス実行のモジュールです。emitがx86へ出力する関数です。
```fsharp:
open System
open System.Text.RegularExpressions
type E =
| ELd of int
| EAdd of E * E
| ESub of E * E
| EMul of E * E
| EDiv of E * E
let rec eval(e:E):int =
match e with
| ELd(i) -> i
| EAdd(a,b) -> eval(a) + eval(b)
| ESub(a,b) -> eval(a) - eval(b)
| EMul(a,b) -> eval(a) * eval(b)
| EDiv(a,b) -> eval(a) / eval(b)
let parse(str:String):E =
let (|ParseRegex|_|) regex str =
let m = Regex(regex).Match(str)
if m.Success
then Some (List.tail [ for x in m.Groups -> x.Value ])
else None
(**
* 予測されたトークンを取り除く
*)
let rec eat(es:(E * string), eatStr:string):(E * string) =
let eatReg = "^[ \\r\\n\\t]*"+eatStr+"(.*)$"
match es with
| (a,ParseRegex eatReg [str]) -> (a, str)
| _ -> raise (Exception "error")
(**
* 足し算かterm
*)
let rec exp(str:string):(E * string) =
let rec exp2(es:(E * string)):(E * string) =
match es with
| (a, ParseRegex "^[ \r\n\t]*\\+(.*)$" [str]) ->
let (b, str2) = term(str)
exp2(EAdd(a, b), str2)
| (a, ParseRegex "^[ \r\n\t]*-(.*)$" [str]) ->
let (b, str2) = term(str)
exp2(ESub(a, b), str2)
| _ -> es
exp2(term(str))
(**
* 掛け算か、fact
*)
and term(str:String):(E * String) =
let rec term2(es:(E * String)):(E * String) =
match es with
| (a, ParseRegex "^[ \r\n\t]*\*(.*)$" [ str]) ->
let (b, str2) = fact(str)
term2(EMul(a, b), str2)
| (a, ParseRegex "^[ \r\n\t]*/(.*)$" [ str]) ->
let (b, str2) = fact(str)
term2(EDiv(a, b), str2)
| _ -> es
term2(fact(str))
(**
* 数字あるいは( exp )
*)
and fact(str:String):(E * String) =
match str with
| ParseRegex "^[ \r\n\t]*([0-9]+)(.*)$" [i;str] -> (ELd( Int32.Parse(i) ) ,str)
| ParseRegex "^[ \r\n\t]*(\\()(.*)$" [str] -> eat(exp(str), "\\)")
| _ -> raise (Exception "error")
// expの呼び出しとエラーの処理
match exp(str) with
| (a, ParseRegex "^[ \r\n\t]*$" []) -> a
| _ -> raise (Exception "error")
type Code =
| CAdd
| CMul
| CSub
| CDiv
| CLd of int
let compile (e:E):Code list =
let rec comp(e:E,codes:Code list):Code list =
match e with
| ELd(i) -> CLd(i) :: codes
| EAdd(a,b) -> CAdd :: comp(a, comp(b, codes))
| ESub(a,b) -> CSub :: comp(a, comp(b, codes))
| EMul(a,b) -> CMul :: comp(a, comp(b, codes))
| EDiv(a,b) -> CDiv :: comp(a, comp(b, codes))
List.rev (comp(e, []))
open System.IO
open System.Text
module Asm =
let mutable writer:StreamWriter = null
let openFile(file:string): unit =
writer <- new StreamWriter(file, false, Encoding.UTF8)
let p(str:string):unit =
writer.WriteLine(str)
let p__(str:string):unit =
writer.WriteLine(" "+str)
let close() =
writer.Close()
open System.IO
open System.Text
open System.Diagnostics
open System.Text.RegularExpressions
open System.Collections.Generic
module Exec =
let readAll(filename:string):string =
File.ReadAllText(filename, Encoding.UTF8)
let run (cmd:string):(int * string * string) =
let mutable args = Regex.Split(cmd, "[ \t]+", RegexOptions.IgnoreCase)
let program = args.[0]
let proc = new Process()
proc.StartInfo <- new ProcessStartInfo()
proc.StartInfo.FileName <- program
proc.StartInfo.Arguments <- System.String.Join(" ", Array.sub args 1 (args.Length-1) )
proc.StartInfo.UseShellExecute <- false
proc.StartInfo.RedirectStandardOutput <- true
proc.StartInfo.RedirectStandardError <- true
proc.Start() |> ignore
proc.WaitForExit()
(proc.ExitCode, proc.StandardOutput.ReadToEnd() ,proc.StandardError.ReadToEnd())
module Emit =
let emit(file:string, codes:Code list):unit =
let rec f(c:Code):bool =
match c with
| CLd(i) ->
Asm.p__("pushl $"+i.ToString())
| CAdd ->
Asm.p__("popl %eax")
Asm.p__("popl %ecx")
Asm.p__("addl %ecx, %eax")
Asm.p__("pushl %eax")
| CSub ->
Asm.p__("popl %eax")
Asm.p__("popl %ecx")
Asm.p__("subl %ecx, %eax")
Asm.p__("pushl %eax")
| CMul ->
Asm.p__("popl %eax")
Asm.p__("popl %ecx")
Asm.p__("imull %ecx, %eax")
Asm.p__("pushl %eax")
| CDiv ->
Asm.p__("popl %eax")
Asm.p__("popl %ecx")
Asm.p__("cltd")
Asm.p__("idiv %ecx")
Asm.p__("pushl %eax")
true
Asm.openFile(file)
Asm.p("""
.globl _print_i
.align 4, 0x90
_print_i:
pushl %ebp
movl %esp, %ebp
subl $24, %esp
call L5$pb
L5$pb:
popl %eax
movl 8(%ebp), %ecx
movl %ecx, -4(%ebp)
movl -4(%ebp), %ecx
movl %esp, %edx
movl %ecx, 4(%edx)
leal L_.str-L5$pb(%eax), %eax
movl %eax, (%edx)
call _printf
movl -8(%ebp), %eax
addl $24, %esp
popl %ebp
ret
.globl _main
.align 4, 0x90
_main:
pushl %ebp
movl %esp, %ebp
subl $24, %esp
""")
List.forall f codes |> ignore
Asm.p("""
popl %eax
movl %eax, (%esp)
call _print_i
movl -4(%ebp), %eax
addl $24, %esp
popl %ebp
ret
.section __TEXT,__cstring,cstring_literals
L_.str:
.asciz "%d\n"
""" )
Asm.close()
let e: E = parse ("1+2*3")
let codes: Code list = compile(e)
Console.WriteLine(codes)
Console.WriteLine(Emit.emit("e.s", codes))
Console.WriteLine(Exec.readAll("e.s"))
Console.WriteLine(Exec.run("gcc -m32 e.s"))
Console.WriteLine(Exec.run("./a.out"))
LLVMコンパイラ
スタックマシン的なアプローチでは、それなりに動作するプログラムは作れますが、push,pop,push,popと大量にあるので、プログラムサイズが肥大化してしまいます。そこで、レジスタアロケーションという処理をする事で、無駄なスタック操作を無くして、出来るだけメモリは使わずに、レジスタ内で済ませられる事なら済ませるようにすると良いです。
しかし、このレジスタアロケーションの処理をまじめにやろうとすると非常に大変です。また、複数CPUに対して同じような事をしようとしたら更に大変です。
そこで、もう諦めてLLVMを使って任せてしまいましょう。