scheme処理系の実装

67 %
33 %
Information about scheme処理系の実装
Technology

Published on March 9, 2014

Author: bobuhiro11

Source: slideshare.net

Description

VM型schemeインタプリタ処理系の実装

scheme処理系の実装 のぶさん@bobuhiro11

だれ?? • のぶさん@bobuhiro11 • 大学3回 • security camp 2013 • Linux Security Module • UNIX V6読書会 • 7回目で止まってる • 参加者の方々ごめんなさい 2

話の内容 • schemeの処理系 • 昨年12月頃 • 第一弾を作った • 純粋なインタプリタ • マクロなし,GCなし,継続なし • もうこれschemeちゃうやん • 現在 • 第二弾を作った • VM型インタプリタ • 伝統的マクロあり,GCあり,継続あり • それっぽい 3

構成 • コンパイラ • schemeで実装 • 字句解析 → マクロ展開 → CPS変換・クロージャ変換 → バイトコード生成 • VM • C言語で実装 • スタックマシン 4

CPS変換 (if E1 E2 E3) C → E1 (lambda (r1) (if r1 E2 E3)) C C 5

VM • 6つレジスタ stack pointer → arg pointer closure pointer • accumulator return address • program counter TAG: end-of-frame • frame pointer arg pointer → • arg pointer : • closure pointer • stack pointer arg1 argn frame pointer → frame pointer arg pointer closure pointer 成長 return address TAG: end-of-frame arg1' arg2' frame pointer' 6

データ表現 • プリミティブ • 整数,文字,定数 • 1 wordで表現 • typedef intptr_t vm_data; • 下位2bitにタグ情報を入れる number 00 char 00001 true 00101 false 01001 nil 01101 eof 10001 undef 10101 object 11 • オブジェクト • ペア,クロージャ,文字列,ボックス • ヒープへ 7

バイトコード >>(disasm ((lambda (x) (* x 2)) 10)) === code === 0 0x12000002 ;FRAME 14 0x01000002 ;REFER_LOCAL 1 0x00000060 ;24 15 0x00000000 ;0 2 0x25000002 ;CONSTNUM 16 0x13000002 ;ARGUMEMT 3 0x00000028 ;10 17 0x03000002 ;REFER_GLOBAL 4 0x13000002 ;ARGUMEMT 18 0x095b5313 ;* 5 0x06000002 ;CLOSE 19 0x14000002 ;SHIFT 6 0x00000000 ;0 20 0x00000008 ;2 7 0x0000002c ;11 21 0x00000004 ;1 8 0x0000005c ;23 22 0x15000002 ;APPLY 9 0x15000002 ;APPLY 23 0x00000008 ;2 10 0x00000004 ;1 24 0x27000002 ;DISASM 11 0x25000002 ;CONSTNUM 25 0x00000002 ;HALT 12 0x00000008 ;2 13 0x13000002 ;ARGUMEMT 8

GC...の前に シンボルテーブル x y スタック 100 200 : * 20 + 10 end-of-frame cons : コード ヒープ : : : NUATE : : : レジスタ nil 2 23 30 9

GC • cheney's copy GCを採用 • cheney → copy GCの中で,幅優先のもの allocate FROM TO allocate TO FROM GC TO FROM 10

cheney's copy GC • 良いとこ • デフラグがいらない • 幅優先のため,うまくやるとマシンスタックを余計に使わない • 悪いとこ • 幅優先なので,キャッシュが効きにくい • 近似的に深さ優先にする手法もあるみたい • 保守的GCと相性が悪い • 今回はオブジェクトかどうかexactに判定できるから問題無し 11

残りのトピック • 末尾呼び出し最適化 • 不必要にフレームを作らない • 代わりにSHIFT命令で,引数を調節する • 末尾再帰は問題なし • マクロ • Gaucheの力を使って,コンパイル時に展開 • 伝統的マクロ(展開ルールを素直に記述したもの)のみ • 多値 • やってない • Gaucheからの自立 • コンパイラ自身をセルフコンパイルすればおk • でも大変 12

デモ

参考 • Three Implementation Models for Scheme • http://www.cs.indiana.edu/~dyb/papers/3imp.pdf • The 90 Minute Scheme to C compiler • http://www.iro.umontreal.ca/~boucherd/mslug/meetings/20041020/9 0-min-scc/90-min-scc.pdf • Mona OS developers Wiki • http://wiki.monaos.org/ 14

Add a comment

Related presentations

Related pages

Schemeの実装におけるスタックフレーム(Draft)

Schemeの実装における ... これはあくまで実装の一例であって、詳細は言語処理系のデザインに任されて ...
Read more

Scheme 入門 1. Scheme 処理系のインストール

Scheme の仕様と処理系 ... R 5 RS が 言語のコアしか規定していなかったため、実装ごとに異なる拡張機能が生じ、実装 ...
Read more

((schemeっぽい処理系)を書いてみた) - bobuhiro11's diary

schemeっぽい処理系 ... ただ,あくまでもオレオレ実装なのでRnRSには 対応していません. schemeは,処理系の ...
Read more

おすすめのScheme R7RS処理系は? - ja.stackoverflow.com

その処理系の R7RS ... 事実上の参照実装という立場で ... Gaucheコードを他のScheme処理系に 移植する ...
Read more

Goで小さなScheme、Gigueを実装しました - Qiita

全国のGopherのみなさんこんばんは! SICPを昨年読み終え、Scheme以外でも処理系を書いてみようと考えていました ...
Read more

つくって学ぶ - tatsu-zine.com

Ruby によるScheme 処理系の実装 ... 第5 章 次のステップ 29 5.1 Scheme in ... 「プログラミング言語の処理系 ...
Read more

Schemeを作ろう 第1回 - internet JAH

Scheme処理系の制作 第1 ... ここまででできれば全部できたも同然です。後はゆっくり、オブジェクトの未実装の ...
Read more

つくって学ぶプログラミング言語 RubyによるScheme処理系の実装 - 達人出版会

... の近道は、プログラミング言語を実装してみること。Schemeの ... RubyによるScheme処理系の実装.
Read more

お気楽 Scheme プログラミング入門 - geocities.jp

今回は最小の Lisp にならって、次に示す関数を持つ小さな Scheme 処理系 ... 実装 が難しい機能 ... の Lisp 処理系です ...
Read more

Scheme 処理系実装 (Ruby) - 実装の為の準備

実装の準備. これから実装するSchemeインタプリタの仕様を決定します。大体は、手元の gosh の挙動を確認しながら ...
Read more