advertisement

scheme処理系の実装

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

Published on March 9, 2014

Author: bobuhiro11

Source: slideshare.net

Description

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

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

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

In this presentation we will describe our experience developing with a highly dyna...

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

Un recorrido por los cambios que nos generará el wearabletech en el futuro

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

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