MicroHsを読む

(2026/3/22)

フォークしたものを手元にclone

% git clone git@github.com:nobsun/MicroHs.git

コード読み用ブランチ

% git switch -c reading

最初のコミットを復元

% git log --reverse | head -1

commit ccb31388776cb2a844de440939665a118932d206

% git restore -s ccb31388776cb2a844de440939665a118932d206 .

% ls

Lam.hs* Makefile eval.c

% cat Makefile

code:Makefile

test: eval nfib.comb

./eval nfib.comb

eval: eval.c

gcc -O3 eval.c -o eval

nfib.comb: Lam

./Lam > nfib.comb

Lam: Lam.hs

ghc Lam.hs -o Lam

clean:

rm -f *.hi *.o eval Lam

code: console

% make test

gcc -O3 eval.c -o eval

ghc Lam.hs -o Lam

In the use of ‘head’

(imported from Data.List, but defined in GHC.List):

"This is a partial function, it throws an error on empty lists. Use pattern matching or Data.List.uncons instead. Consider refactoring to use Data.List.NonEmpty."

|

| ^^^^

./Lam > nfib.comb

./eval nfib.comb

((Y (((C' C) ((B (S (> 2))) (((C' (C' +)) (((S' (S' +)) ((C B) (-' 1))) ((C B) (-' 2)))) 1))) 1)) 35)

29860703

node size=24, heap size=100000

1045124618 reductions, 1944 GCs

% ls

Lam* Lam.hi Lam.hs* Lam.o Makefile eval* eval.c nfib.comb

% cat nfib.comb

((Y (((C' C) ((B (S (> 2))) (((C' (C' +)) (((S' (S' +)) ((C B) (-' 1))) ((C B) (-' 2)))) 1))) 1)) 35)

Lam.hs

code:haskell

main :: IO ()

main = do

code:haskell

data Exp

= Var Ident

| App Exp Exp

| Lam Ident Exp

| Int Integer

| Comb String

| Prim String

deriving (Show, Eq)

コア式がこれ ↑ かな。

こいつを

コンパイル（変数とλ抽象を除去）：コンビネータ適用式を生成し

という流れ。

コンパイルは SKIBC に加えて S'C'B'TY を加えたコンビネータ式にコンパイル。

Lam.hs に動作確認用のコードがコメントアウトされて残っているでそれを有効にする CPP プラグマをいれて動かしてみた。

Make fileの追加エントリ

code:Makefile

LamD: Lam.hs

ghc -DDEBUG Lam.hs -o LamD

Lam.hs の main 部分 CPP のプラグマ追加

code:haskell

main = do

let c1 = compile e1

c1' = improve c1

r1' = reduce (App c1 (Var "k"))

r1'' = reduce (App c1 (Int 5))

pp e1

pp c1

pp c1'

pp r1'

pp r1''

pp $ reduce (App c1' (Int 6))

let c2 = compile e2

c2' = improve c2

pp e2

pp c2

pp c2'

pp $ reduce $ App2 c2 (Int 2) (Int 10)

pp $ App2 c2' (Int 2) (Int 10)

pp $ reduce $ App2 c2' (Int 2) (Int 10)

pp $ reduce $ App2 c2' (Var "x") (Var "y")

pp $ improve $ compile e3

pp $ improve $ compile $ App (Lam "x" (App2 (Var "x") (Int 10) (Int 2))) (Prim "-")

% make LamD; ./LamD

code:console

(\x. + x x)

S (S (K +) I) I

S + I

+ k k

10

12

(\x. (\y. - y x))

S (K -') I

-'

-' (I 2) 10

-' 2 10

-' 2 10

-' x y

T

C (C I 10) 2

ふむ。ふむ。