インストール

インタプリタ

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を使って任せてしまいましょう。