【x86_64コンパイラ自作】関数合成が出来る程度のLISPを作る

きっかけ

ここ最近ずっとWASMにコンパイルする言語を作っていましたが、ちょっと行き詰まったので息抜きにx86_64コンパイラを作ろうと思いました。せっかくなのでLISPで関数合成とか関数型パラダイムみたいな挙動ができることを目標にしました。

抽象構文木

これがプログラムの構造です。

enum Expr {
    List(Vec<Expr>),
    Atom(Atom),
}

enum Atom {
    Symbol(String),
    Integer(i64),
}

パーサー

プログラムの文字列(S式)を再帰的にASTに変換します。
シンボルはNASMの予約語と被らないように_を付けておきます。

impl Expr {
    pub fn parse(source: &str) -> Option<Self> {
        let source = source.trim();
        if let Some(Some(source)) = source.strip_prefix("(").map(|x| x.strip_suffix(")")) {
            Some(Expr::List(
                tokenize(source)?
                    .iter()
                    .map(|x| Expr::parse(x))
                    .collect::<Option<Vec<_>>>()?,
            ))
        } else {
            Some(Expr::Atom(Atom::parse(source)?))
        }
    }
}

impl Atom {
    pub fn parse(source: &str) -> Option<Self> {
        let source = source.trim();
        if let Ok(n) = source.parse::<i64>() {
            Some(Atom::Integer(n))
        } else {
            Some(Atom::Symbol("_".to_string() + source))
        }
    }
}

コード生成器

ASTからx86_64アセンブリ(NASM)を組み立てます。この際、compile メソッドはコンパイラのctx（コンテキスト）を可変参照として受け取り、NASMコード返します。

Compiler's Context

struct Compiler {
    lambda_id: usize,
    functions: Vec<String>,
    variables: Vec<String>,
}

lambda_idは、ラムダ式を識別するIDで、functionsはユーザー定義関数のコード、variablesは変数初期化のコードです。

アトム

アトムのうち数値は、それをraxレジスタに格納するコードとします。
シンボルは変数として、相対アドレスで読み込みます。

impl Atom {
    pub fn compile(&self, _ctx: &mut Compiler) -> Option<String> {
        match self {
            Atom::Integer(number) => Some(format!("\tmov rax, {number}\n")),
            Atom::Symbol(name) => Some(format!("\tmov rax, [rel {name}]\n")),
        }
    }
}

スペシャルフォーム lambda

引数を変数として定義します。

let Expr::List(list) = expr.get(1)? else {
    return None;
};
let mut args = vec![];
for arg in list {
    let Expr::Atom(Atom::Symbol(name)) = arg else {
        return None;
    };
    ctx.variables.insert(format!("\t{name} dq 0\n"));
    args.push(name);
}

引数を受け取ります。

let receiver = args
    .iter()
    .enumerate()
    .map(|(id, name)| format!("\tmov [rel {name}], r{}\n", id + 8))
    .collect::<Vec<_>>()
    .concat();

名前と全体のコードを生成し、関数ポインタを返します。

let body = &expr.get(2)?.compile(ctx)?;
let name = format!("lambda_{}", ctx.lambda_id);
ctx.lambda_id += 1;
ctx.functions
    .push(format!("{name}:\n{receiver}\n{body}\tret\n\n"));
Some(format!("\tlea rax, [rel {name}]\n"))

成果物

関数合成をするコード

ここでは、compose関数でinc関数とdup関数を合成してincdup関数を作り、それを3で呼び出しています。

(var compose (lambda (f g) (lambda (x) (f (g x)))))
(var inc (lambda (x) (+ x 1)))
(var dup (lambda (x) (* x 2)))
(var incdup (compose inc dup))
(incdup 3)

生成されたアセンブリ

section .text
	align 16
	global _start

_start:
	lea rax, [rel lambda_1]
	mov [rel _compose], rax
	lea rax, [rel lambda_2]
	mov [rel _inc], rax
	lea rax, [rel lambda_3]
	mov [rel _dup], rax
	mov rax, [rel _inc]
	mov r8, rax
	mov rax, [rel _dup]
	mov r9, rax
	mov rax, [rel _compose]
	call rax
	mov [rel _incdup], rax
	mov rax, 3
	mov r8, rax
	mov rax, [rel _incdup]
	call rax

	mov rdi, rax
	mov rax, 0x2000001
	syscall

lambda_0:
	mov [rel _x], r8

	mov rax, [rel _x]
	mov r8, rax
	mov rax, [rel _g]
	call rax
	mov r8, rax
	mov rax, [rel _f]
	call rax
	ret

lambda_1:
	mov [rel _f], r8
	mov [rel _g], r9

	lea rax, [rel lambda_0]
	ret

lambda_2:
	mov [rel _x], r8

	mov rax, [rel _x]
	push rax
	mov rax, 1
	mov rdx, rax
	pop rax
	add rax, rdx
	ret

lambda_3:
	mov [rel _x], r8

	mov rax, [rel _x]
	push rax
	mov rax, 2
	mov rdx, rax
	pop rax
	imul rax, rdx
	ret


section .data
	_compose dq 0
	_dup dq 0
	_f dq 0
	_g dq 0
	_inc dq 0
	_incdup dq 0
	_x dq 0

まとめ

まだ加筆していきます。
最後までご覧頂きありがとうございました！