Skip to content

Instantly share code, notes, and snippets.

@shkmr shkmr/ika-intro.txt Secret
Created Jan 3, 2016

Embed
What would you like to do?
;; -*-Scheme-*-
;;
;; === 楽しい ika プログラミング ===
;;
;;; 1. ika とは
;;;
;;; 機械語のプログラミングは実行したら即暴走するプログラムが簡単に書けます。
;;; ika はそんな刺激的な火遊びをしてみたい、いけない子のアセンブラです。
;;;
;;; ika プログラミングをしていると通常滅多に御目にかかることのない VM
;;; レジスタのダンプリストなどを拝むことができます。
;;;
;;; 2. 遊び方
;;;
;;; まずはコマンドラインにて、
;;;
;;; $ git clone shkmr.github.gom/taco
;;; $ cd taco
;;; $ make
;;;
;;; すると vmhack モジュール、insn.html ができます。
;;;
;;; 次に、Emacs で ika-intro.scm (このファイルのソース)を開き
;;; M-x run-scheme (もちろん gosh が起動しますよね? ね!)
;;; して、順番に C-x C-e して様子をみてみましょう。
;; まずは読み込み
(begin
(add-load-path ".")
(add-load-path "vmhack")
(use ika)
(use vmhack))
;=> #<undef>
;; ika->vm-code は ika プログラムをアセンブルして実行可能な
;; <compiled-code> を作ります。
(ika->vm-code '(%toplevel (0 0)
(CONST) 2
(RET)
))
;=> #<compiled-code %toplevel@0x101835b40>
;; %toplevel (0 0) は後ほど 5. で説明するとして、このプログラムは
;; アキュムレータ(val0)に定数 2 をロードしてリータン、つまり、
;; 単に 2 を返すプログラムです。 これを test1 としておきましょう。
(define test1 (ika->vm-code '(%toplevel (0 0)
(CONST) 2
(RET)
)))
;=> test1
;; <compiled-code> を実行するには vmhack モジュールの
;; vm-code-execute! に渡せばオッケイ。
(vm-code-execute! test1 (interaction-environment))
;=> 2
;; ちゃんと 2 が返ってきました。
;; 第二引数には (interaction-environment) の代わりに
;; モジュールを渡して構いません。 今後変わるかもしれないけど。
(vm-code-execute! test1 (find-module 'user))
;=> 2
;;; 3. Gauche VM の機械語その1
;;;
;;; Gauche VM の機械語のフォーマットは次の6種類です。
;;;
;;; 1. OPCODE
;;; 2. OPCODE OBJ
;;; 3. OPCODE ADDR
;;; 4. OPCODE CODE
;;; 5. OPCODE OBJ ADDR
;;; 6. OPCODE CODES
;;;
;;; OBJ は任意の Scheme オブジェクト、 ADDR はアドレス、 CODE は
;;; <compiled-code>、 CODES は <complied-code> のリストです。
;;; アドレスは Scheme オブジェクトではないので、ika プログラムでは
;;; label 擬似命令で指定します。
;;;
;;; OPECODE にはパラメータを一つか二つ取るものがあり、例えば
;;; パラメータなしの (CONST) に対してパラメータを一つ取る (CONTI n)
;;; があります。パラメータは小さめの整数でその範囲は1 integer-fits-insn-arg?
;;; で確認できます。
;;;
;;; 1. の $ make でできた insn.html は機械語の命令(insn)の一覧です。
;;; Gauche VM には複合命令(combined insn)という、頻出する複数の命令
;;; を一つにまとめたものがあります。 例えば CONST-PUSH は CONST と PUSH
;;; を一つにまとめたものです。 ika プログラミングにおいては、これらを直接
;;; 使うこともできますが、ika が呼び出す complied-code-builder (cc_builder) が
;;; 自動的にまとめてくれるので、とりあえずは基本形だけを使っていれば十分
;;; かと思います。
;; 先ほどの test1 を見てみましょう。
(vm-dump-code test1)
;|=== main_code (name=%toplevel, code=0x10181ab40, size=2, const=0 stack=0):
;|args: #f
;| 0 CONSTI(2)
;| 1 RET
;=> #<undef>
;; リスト形式で
(vm-code->list test1)
;=> ((CONSTI 2) (RET))
;; ika プログラムでは 2語の (CONST) 2 としたところが 1語の (CONSTI 2)
;; に変わっています。
;; また、文字列定数を返すプログラムは
(vm-dump-code (ika->vm-code '(%toplevel (0 0)
(CONST) "abracadabra"
(RET))))
;|=== main_code (name=%toplevel, code=0x10181a9b0, size=2, const=1 stack=0):
;|args: #f
;| 0 CONST-RET "abracadabra"
;=> #<undef>
;; のように (CONST) operand (RET) が (CONST-RET) operand に変換さてれます。
;; 今回はオペランドが命令に埋め込める物ではないので代わりに複合命令(CONST-PUSH)
;; になりました。
;;; 機械語は Gauche のコンパイラに教えてもらうのが手っ取り早いと思います。
;;; ika を use すると Gauche のコンパイラも使えるようになります。
;;; コンパイラは <compiled-code> を返します。
;; 例えば先ほどの 2 を返すプログラムは
(vm-dump-code (compile 2 (interaction-environment)))
;|=== main_code (name=%toplevel, code=0x10181a920, size=2, const=0 stack=0):
;|args: #f
;| 0 CONSTI(2)
;| 1 RET
;=> #<undef>
;; vm-code->list で得られるリストに (%toplevel (0 0)) をくっつけると
;; ika プログラムになります。
(ika/pp `(%toplevel (0 0)
,@(vm-code->list (compile 2 (interaction-environment)))))
;|(%toplevel (0 0)
;| 0 (CONSTI 2)
;| 1 (RET)
;=> #t
;; ika/pp は ika プログラムを見やすくインデントして表示します。
;; 左端の数字はアドレスです。
;;; ところで、後ほど 5. で説明しますが、ika プログラムには
;;; アドレスは不要なので出力は ika プログラムにはなってません。
;;; これら complie と ika/pp の呼び出しをまとめた c という関数が ika
;;; モジュールの中にあるのでいろいろ試してみましょう。
;; c は export されてないので取り込みます。
(define c (with-module ika c))
;=> c
(c 2)
;|
;|(%toplevel (0 0)
;| 0 (CONSTI 2)
;| 1 (RET)
;|
;=> #<undef>
(c 654321)
;|
;|(%toplevel (0 0)
;| 0 (CONST-RET) 654321
;|
;=> #<undef>
(c "abracadabra")
;|
;|(%toplevel (0 0)
;| 0 (CONST-RET) "abracadabra"
;|
;=> #<undef>
(c #t)
;|
;|(%toplevel (0 0)
;| 0 (CONST-RET) #t
;|
;=> #<undef>
(c #f)
;|
;|(%toplevel (0 0)
;| 0 (CONSTF-RET)
;|
;=> #<undef>
(c '())
;|
;|(%toplevel (0 0)
;| 0 (CONSTN)
;| 1 (RET)
;|
;=> #<undef>
(c '(+ 1 2))
;|
;|(%toplevel (0 0)
;| 0 (CONSTI 3)
;| 1 (RET)
;|
;=> #<undef>
(c '(+ x y))
;|
;|(%toplevel (0 0)
;| 0 (GREF-PUSH) #<identifier user#x.18b1da0>
;| 2 (GREF) #<identifier user#y.18b1d60>
;| 4 (NUMADD2)
;| 5 (RET)
;|
;=> #<undef>
(c '(print "abracadabra"))
;|
;|(%toplevel (0 0)
;| 0 (CONST-PUSH) "abracadabra"
;| 2 (GREF-TAIL-CALL 1) #<identifier user#print.18bfa60>
;| 4 (RET)
;|
;=> #<undef>
(c '(define (fact n)
(if (= n 1)
1
(* n (fact (- n 1))))))
;|
;|(%toplevel (0 0)
;| 0 (CLOSURE) (fact (1 0) ; #<compiled-code fact@0x1018c1e40>
;| 0 (LREF0)
;| 1 (BNUMNEI 1) 5
;| 3 (CONSTI 1)
;| 4 (RET)
;| 5 (LREF0-PUSH)
;| 6 (PRE-CALL 1) 11
;| 8 (LREF0-NUMADDI-PUSH -1)
;| 9 (GREF-CALL 1) #<identifier user#fact.18ceba0>
;| 11 (NUMMUL2)
;| 12 (RET)
;| )
;| 2 (DEFINE 0) #<identifier user#fact.18ced20>
;| 4 (RET)
;|
;=> #<undef>
;;; 4. <compiled-code>
;;;
;;; <compiled-code> には次ような(Schemeからアクセス可能な)スロットがあります。
;;;
;;; parent ; 親 <compiled-code>
;;; arg-info ; ソースコードにおける引数(シンボル、またはシンボルのリストまたは #f)
;;; info ; ソースコードの情報、code 内の相対アドレスと対応するソースコードの alist
;;; required-args ; 必須引数の数
;;; optional-args ; 省略可能な引数の数
;;; name ; 名前、シンボルまたは #f
;;; full-name ; 親の名前を含む名前
;;; size ; code のワード数
;;; max-stack ; 使用するスタックのワード数
;;; intermediate-form ; inline 展開するときに使われる何か(よく調べてない)
;;;
;;; 機械語のプログラムは vm-code->list で取り出すことができます。
;;;
;;; ika->vm-code は ika プログラムにしたがってこれらのスロットを設定します。
;;;
;;; 5. ika の文法その1
;;;
;;; ika プログラムは
;;;
;;; (name code-spec body)
;;;
;;; というリストです。 name はシンボル code-spec は基本的には
;;;
;;; (required-args optional-args)
;;;
;;; という形式で、オプションの kv-list でいくつかの <complied-code> スロット
;;; を設定することができます。(が私自身あまり試してません。)
;;;
;;; (required-args optional-args :key val ...)
;;;
;;; 現在指定可能なのは :arg-info :parent :intermediate-form です。
;;;
;;; 例えば、先に見た test1 の場合は
;;;
;;; name = %toplevel
;;; code-spec = (0 0)
;;; body = (CONST) 2 (RET)
;;;
;;; となります。
;;;
;;; それではもう少し複雑な ika のプログラムを組んでみましょう。
;; 3. の終わりに示した
(c '(print "abracadabra"))
;|
;|(%toplevel (0 0)
;| 0 (CONST-PUSH) "abracadabra"
;| 2 (GREF-TAIL-CALL 1) #<identifier user#print.18f7440>
;| 4 (RET)
;|
;=> #<undef>
;; に相当する ika プログラムは
(define ika1 `(%toplevel (0 0)
(CONST) "abracadabra"
(PUSH)
(GREF) ,(make-identifier 'print (find-module 'user) '())
(TAIL-CALL 1)
(RET)))
;=> ika1
;; となります。 ここで、(GREF) のオペランドは識別子(identifier)なので
;; make-identifer で user モジュールの識別子を作っています。
;; これを ika->vm-code でアセンプルすると
(vm-dump-code (ika->vm-code ika1))
;|=== main_code (name=%toplevel, code=0x10143b0c0, size=5, const=2 stack=0):
;|args: #f
;| 0 CONST-PUSH "abracadabra"
;| 2 GREF-TAIL-CALL(1) #<identifier user#print.190c840>
;| 4 RET
;=> #<undef>
;; となりめでたくコンパイラの出力と同等になりました。
;; ここでは vm-dump-code を使いましたが、もちろん、先ほどと同様に
(ika/pp `(%top-level (0 0) ,@(vm-code->list (ika->vm-code ika1))))
;|(%top-level (0 0)
;| 0 (CONST-PUSH) "abracadabra"
;| 2 (GREF-TAIL-CALL 1) #<identifier user#print.190c840>
;| 4 (RET)
;=> #t
;; としても構いません。
;;; 擬引用は煩わしいので ika では user モジュールの識別子を作る擬似命令 mkid
;;; を用意しています。(これは将来互換性破る形で変更するかもしれません。)
(define ika2 '(%toplevel (0 0)
(CONST) "abracadabra"
(PUSH)
(GREF) (mkid print)
(TAIL-CALL 1)
(RET)))
;=> ika2
(vm-dump-code (ika->vm-code ika2))
;|=== main_code (name=%toplevel, code=0x10143b000, size=5, const=2 stack=0):
;|args: #f
;| 0 CONST-PUSH "abracadabra"
;| 2 GREF-TAIL-CALL(1) #<identifier user#print.192ec20>
;| 4 RET
;=> #<undef>
;; 実行してみましょう
(vm-code-execute! (ika->vm-code ika2) (interaction-environment))
;|abracadabra
;=> #<undef>
;;; 余談ですが、(CONST) (PUSH) -> (CONST-PUSH) などの合成は ika が
;;; やってるのではなく、Gauche の cc_builder がやってくれてます。
;;; ありがたや、ありがたや。
;;; 6. Gauche VM の機械語その2
;;;
;; 次に手続きの定義を見てみましょう。
(c '(define (foo) (print "foo")))
;|
;|(%toplevel (0 0)
;| 0 (CLOSURE) (foo (0 0) ; #<compiled-code foo@0x1018c1840>
;| 0 (CONST-PUSH) "foo"
;| 2 (GREF-TAIL-CALL 1) #<identifier user#print.1936540>
;| 4 (RET)
;| )
;| 2 (DEFINE 0) #<identifier user#foo.19365c0>
;| 4 (RET)
;|
;=> #<undef>
;; 手続き本体は <compiled-code> となって (CLOSURE) のオペランドに
;; なっています。その結果クロージャが val0 にロードされます。
;; そして (DEFINE 0) で foo の束縛します。
;; vm-dump-code すると 2つの <complied-code> があるのがわかりやすいです。
(vm-dump-code (compile '(define (foo) (print "foo")) (interaction-environment)))
;|=== main_code (name=%toplevel, code=0x10103c240, size=5, const=2 stack=0):
;|args: #f
;| 0 CLOSURE #<lambda 0> ; (lambda () (print "foo"))
;| 2 DEFINE(0) #<identifier user#foo.1950d00>; (define (foo) (print "foo"))
;| 4 RET
;|=== closure:0 (name=foo, code=0x10103c270, size=5, const=2 stack=4):
;|args: ()
;| 0 CONST-PUSH "foo"
;| 2 GREF-TAIL-CALL(1) #<identifier user#print.1950c80>; (print "foo")
;| 4 RET
;=> #<undef>
;;; DEFINE のパラメータは 0 が通常の define、SCM_BINDING_CONST が
;;; define-constant、SCM_BINDING_INLINABLE が define-inline に
;;; 相当するんだと思います。 (まだ、あまり試してません Gauche/src/vminsn.scm 参照)
;;; ここで重要なのは機械語の DEFINE は Scheme のトップレベルの define
;;; に相当するということ。 Scheme 手続き内の define はコンパイラによって
;;; ローカル変数への代入に変換されます。
;; ここでもう一度階乗を見てみましょう。
(c '(define (fact n)
(if (= n 1)
1
(* n (fact (- n 1))))))
;|
;|(%toplevel (0 0)
;| 0 (CLOSURE) (fact (1 0) ; #<compiled-code fact@0x1018c1600>
;| 0 (LREF0)
;| 1 (BNUMNEI 1) 5
;| 3 (CONSTI 1)
;| 4 (RET)
;| 5 (LREF0-PUSH)
;| 6 (PRE-CALL 1) 11
;| 8 (LREF0-NUMADDI-PUSH -1)
;| 9 (GREF-CALL 1) #<identifier user#fact.195b760>
;| 11 (NUMMUL2)
;| 12 (RET)
;| )
;| 2 (DEFINE 0) #<identifier user#fact.195b8e0>
;| 4 (RET)
;|
;=> #<undef>
;;; fact には引数が1つあるので (fact (1 0) ...) となってます。
;;; 引き数(ローカル変数)の参照は (LREF depth offset) で行います。
;;; (LREF0) は (LREF 0 0) に相当するショートカット命令です。
;;; ローカル変数の指定はスタックフレームをある程度理解しないとできないので、
;;; insn.html にリンクを張った shiro さんによるドキュメントを
;;; 読んで勉強しましょう。 実のところ、私はさらっと読んだだけだと
;;; よくわからず、実際に実装してみてようやくどういう構造になっているか
;;; 理解した感じです。(mgvm.scm) 要は時間をかけて一つずつ解きほぐす。
;;; さて、(BNUMNEI 1) のオペランドはアドレスで相当する位置は
;;; 左側の数字が 5 の (LREF0-PUSH) がある所です。
;;; (PRE-CALL 1) のオペランドも同様です。
;;; ika ではアドレスは label 擬似命令で指定します。
;; というわけで、fact を ika で書くとこうなります。
(define fact.ika '(%toplevel (0 0)
(CLOSURE) (ikafact (1 0)
(LREF 0 0)
(BNUMNEI 1) (label 1)
(CONST) 1
(RET)
(label 1) (LREF 0 0)
(PUSH)
(PRE-CALL 1) (label 2)
(LREF 0 0)
(NUMADDI -1)
(PUSH)
(GREF) (mkid ikafact)
(CALL 1)
(label 2) (NUMMUL2)
(RET))
(DEFINE 0) (mkid ikafact)
(RET)
))
;=> fact.ika
(vm-dump-code (ika->vm-code fact.ika))
;|=== main_code (name=%toplevel, code=0x10143bcc0, size=5, const=2 stack=0):
;|args: #f
;| 0 CLOSURE #<lambda 0>
;| 2 DEFINE(0) #<identifier user#ikafact.1927160>
;| 4 RET
;|=== closure:0 (name=ikafact, code=0x101957d20, size=13, const=1 stack=0):
;|args: #f
;| 0 LREF0
;| 1 BNUMNEI(1) 5
;| 3 CONSTI(1)
;| 4 RET
;| 5 LREF0-PUSH
;| 6 PRE-CALL(1) 11
;| 8 LREF0-NUMADDI-PUSH(-1)
;| 9 GREF-CALL(1) #<identifier user#ikafact.1927180>
;| 11 NUMMUL2
;| 12 RET
;=> #<undef>
;; 実行すると
(vm-code-execute! (ika->vm-code fact.ika) (interaction-environment))
;=> ikafact
;; ikafact が定義され、
(ikafact 5)
;=> 120
;; 階乗が計算できました。
;;; おしまい
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.