1

プログラミング言語

Polemyの設計と実装
http://www.kmonos.net/repos/polemy
メタプログラミングの会 2010
しゃべる人k.inaba

2

あるいは

3

メタプログラマ
は度走る

２

4

メタプログラマは度走るｎ5Polemy って何ですか？

6

Polemy って何ですか先月できた新しい言語です[作者] k.inaba[目的] 今日話すネタを作るため$ ./polemy
Welcome to Polemy 0.1.0>>
ポレミちゃん(仮)7

何系の言語？
関数型？論理型？
オブジェクト指向？

8

9Twitterに貼るとreply飛びまくる系言語10

冗談はさておき
大部分は普通の言語です

print(“Hello, World”);
def pow(x, n) {if n==0 then 1 else
( var y = pow(x*x, n/2);
if x%2==0 then y else y*x )}

11

FAQ
“ない” - “です”
• 静的型システムは？
• オブジェクトは？ JS や Lua 的に…
var obj = {table: “が”, aru: “ので”}; obj.ganbare• 第一級の関数は？
let K = fun(x){fun(y){x}} in K(“あります”)(“よ”)• パターンマッチは？
case lst when {car: x, cdr: xs}: “ある”• 破壊的代入は (作者怠慢のため) まだない

12

本題

13

MetaProgrammingin Polemy

14

発想の元は• 型レベルプログラミング– in C++, Haskell, Scala, D, …

15

例: C++
vector<int> xs = …;
nth(rev_iter(xs.end()), 5);
末尾を指すイテレータを計算+ と – の意味を逆転したイテレータに変換
5 歩進めた先の値取得

16

どこに型レベル計算が？

？

？

17

例: C++
vector<int> xs = …;
nth(rev_iter(xs.end()), 5);vector<int> から int* を計算

int* を reverse_iterator<int*> に変換
int*からintを取得※注： 正確には、int* とは限りません。vector<int>::iterator です18

静的型付け言語では
コードは2 つの意味で2 度走る

19

２つの視点
template<class T>class vector {T arr[]; int siz;T* end() {return arr+siz;}}template<class It>
iterator_traits<It>::value_type
nth(It it int n){ return *(it+n); }20値レベルの視点
template<class T>class vector {T arr[]; int siz;T* end() {return arr+siz;}}template<class It>
iterator_traits<It>::value_typenth (It it, int n){ return *(it+n); }21

型レベルの視点
template<class T>class vector {T arr[]; int siz;T* end() {return arr+siz;}}template<class It>
iterator_traits<It>::value_type
nth(It it, int n){ return *(it+n); }22• vector<T>::end() は– 値レベルでは、arr+siz を計算して返す関数– 型レベルでは、T* を返す定数関数• nth(It it, int n) は、– 値レベルでは *(it+n) を計算して返す関数– 型レベルでは iterator_traits<It> というサブルーチンを呼び出して、イテレータの指す型を計算する関数

23

さらに！

24

２つのレベルの交叉• この場合、nth(it,n) の値レベル動作は
return *(it+n);vector<int> xs = …;
nth(rev_iter(xs.end()), 5);• この場合、nth(it, n) はwhile(n-->0) ++it; return *it;list<int> xs = …;
nth(rev_iter(xs.end()), 5);

型レベル計算の結果で、値レベルの挙動を決める

25

template<typename It>
iterator_traits<It>::value_type
nth(It it, int n) {iterator_traits<It>::ry_category がrandom_access_iterator_tag ならreturn *(it+n);
forward_iterator_tag ならwhile(n-->0) ++it; return *it;}26

ここまでのポイント• 静的型付け言語では1つのコードが2つの意味/計算を表す– “Static Semantics” と “Dynamic Semantics”• C++er や Haskeller はよくご存じですがこれは便利

27

1つのコードにsemantics

2 つの意味28

なぜ２つなのか

29

３つじゃ
ダメ
なんですか

30

それと31

これ別に型の上でやらんでもいいよね！

32

そこで Polemy>> @value( 1 + 2 )3>> @church( 1 + 2 )fun(s,n){s(s(s(n)))}>> @type( 1 + 2 )“int”>> @nihongo( 1 + 2 )“いちたすに”

33

Polemy って何ですか• 型レベル計算の本質（と私が思うもの）「１つのコードを複数の意味で解釈」

これだけを取り出した言語• 本質と思わないもの– 型によって• プログラムの正しさを保証• プログラムを高速化– これは型レベル計算でできることの一例• ぶっちゃけ、型はどうでもいい34

レイヤ指定実行
Expr ::= … | “@” LAYERID “(“ Expr “)”>> @value( 1 + 2 )3• コード 1+2 を「@value レイヤ」で実行– “1” や “+” や “2” の意味を「値レベルで」で解釈＆実行– @value はデフォルトで用意されてる言語組込レイヤです35

レイヤ指定実行
Expr ::= … | “@” LAYERID “(“ Expr “)”>> @type( 1 + 2 )int• コード 1+2 を「@type レイヤ」で実行– @type はユーザ定義のレイヤです。頑張って作ります– “1” や “+” や “2” の意味を「型レベルで」で解釈＆実行36

レイヤの作り方 (1)• リテラルの「意味」を与えるリフト関数

Expr ::= …
| “@@” LAYERID “=“ Expr “;” …
@@type = fun(x){if( _isint(x) ) “int”
else “ERRORRRR!!!!”};

int 専用超絶手抜き型検査

37

レイヤの作り方 (2)• @type レイヤでは 1 の意味は “int”• @type レイヤでは 2 の意味は “int”• @type レイヤでは “a” の意味は “ERRORRRR!!!!”@@type = fun(x){if( _isint(x) ) “int”
else “ERRORRRR!!!!”};

38

レイヤの作り方 (3)• レイヤ指定変数定義で既存変数の意味をExpr ::= …
| “@” LAYERID VAR “=“ Expr “;” …
var + = <primitive_plus>;@type + = fun(x,y) {if (x==“int” && y==“int”)“int”
else “ERRORRRR!!!!”};

39

レイヤの作り方 (3)• レイヤ指定変数定義で既存変数の意味をExpr ::= …
| “@” LAYERID VAR “=“ Expr “;” …
var + = <primitive_plus>;@type + = fun(x,y) {if (x==“int” && y==“int”)“int”
else “ERRORRRR!!!!”};

40

レイヤの作り方 (4)@type + = fun(x,y) {@value(if ( @type(x)==“int”&& @type(y)==“int” )“int”
else “ERRORRRR!!!!”)};

41

できました
>> @type( 1 + 2 )int>> 1 + “orz”[<REPL>:10:1] type mismatch on the argument 2 ofnative function +. polemy.value.IntValue required but
orz passed.

>> @type( 1 + “orz” )ERRORRRR!!!!

値レベルで動かさないでも静的？に型検査42できました• ユーザ定義関数は勝手に意味を持ちます（再帰の処理にはちょっとトリックが必要）• @valueレベル関数  @typeレベル関数>> def f(x,y,z) { x + y + y }>> @type(f(1,2,”orz”))
int>> @type(f(1,”orz”,2))
ERRORRRR!!!!

43「複数の意味」はできました。
>> @type( 1 + 2 )int>> @value( 1 + 2 )344「１つのコードに複数の意味」は？
nth(rev_iter(xs.end()), 5);45• レイヤ指定引数を使います
def next(it @type @value, n) {if( @type(it).tag == “RandomAccess” )it + nelse
if n==0 then it else next(it.next, n-1)}
next( 1+2, 5 );

46

他の例

47

たらいを回す48

無駄に関数を呼びまくる関数
def tarai(x,y,z) {if x<=y thenyelsetarai(tarai(x-1,y,z),tarai(y-1,z,x),
tarai(z-1,x,y) )};>> tarai(12,6,0)
終わらない49

遅延評価がすごく効く関数
def tarai(x,y,z) {if x<=y thenyelsetarai(tarai(x-1,y,z),tarai(y-1,z,x),
tarai(z-1,x,y) )};まったく同じtaraiのコードを遅延評価な意味で実行したい>> @lazy(tarai(12,6,0))()12

50

遅延評価がすごく効く関数@@lazy = fun(x){fun(){x}};@lazy - = fun(x,y){fun(){@value(@lazy(x)()-@lazy(y)()}};
def tarai(x,y,z){@lazy <= = fun(x,y ){fun(){@value(@lazy(x)()<=@lazy(y)()}};@lazy if = fun(c,t,e){fun(){@value(if @lazy(c)() then@lazy(t())() else @lazy(e())())};

if x<=y thenyelsetarai(tarai(x-1,y,z),tarai(y-1,z,x),
tarai(z-1,x,y) )};>> @lazy(tarai(12,6,0))()
12

51

余談

52

@joke(Polemy.言語名の由来)

プﾛｸﾞﾗﾐﾝｸﾞ言語 P
俺々言語oleマイ言語my53@wikipedia(言語名の由来)

メタプログラミングの会に「論争状態」を巻き起こしたいですね！

54@truth(言語名の由来)

長いので、これを適当に縮めました

55

実装

56

D言語でできています57

実装• D のメタプログラミングの発表が無いみたいなのでちょっとだけ Polemyの実装からメタっぽい部分の紹介（たいしたことはしてません）

58

文字列で頑張る• unittest ライブラリにて– 文字列 mixin ≒「コンパイルタイム eval」
void assertOp(string op,A,B)(A a, B b) {if( !mixin("a"~op~"b") )throw new AssertError(text(a," !",op," ", b));}assertOp!(“==”)(123, 456); // Error: 123 !== 456

59コンパイル可能性チェック
class Token {immutable LexPosition pos;
immutable stringstr;
immutable boolquoted;}
assert(!__traits(compiles, (new Token).str=“foo") );// std.range (本当はis(typeof(…))を使っている)

template isInputRange(R){enum isInputRange = __traits(compiles,{R r;auto _ = r.front;
r.popFront; if(r.empty){}
});
}

60

型情報
e.addPrimitive( “+”, (IntValue a, IntValue b){return new IntValue(a.data + b.data);});// ↑こう書いたら↓こういう関数を登録(Value[] args){
if( args.length != 2 ) throw …;
if( args[0] is not IntValue ) throw …;
if( args[1] is not IntValue ) throw …;
return 上記の関数(cast(IntValue)args[0], cast(IntValue)args[1]);}61

コンパイル時リフレクション
T polemy2d(T)(Value v) {… static if(is(T == class))
foreach(mem; T.tupleof)
mem = v.get(mem.stringof); …
}
class Hoge { int foo; string bar; }auto x = polemy2d!Hoge(eval(`{foo: 100, bar: “hello”}`));

62

マクロ

63

プログラムをデータ（構文木）と見なして読んだり書いたり64「プログラム」を「構文木」と見る• 一つのコードを>> 1 + 2
3• 複数の意味で！
>> @macro( 1 + 2 ){ pos:…, is: App,fun: {pos:…, is:Var, name:+}args: [ {pos:…, is:Int, data:1},{pos:…, is:Int, data:2} ] }65Polemy の実行ステップ
入力されたソース@macroレイヤで実行@valueレイヤで実行

66

とりあえず
「コードを実行するとその構文木を作る」
ように、インタプリタ組み込みで実装@macroレイヤで実行67

その瞬間にマクロ機能完成

68

レイヤ指定変数定義@macroLetItBe = fun(b, expr){var it = b; expr};
LetItBe(1+2, print(it));

69

レイヤ指定引数@macrorep = fun(n@value, e@macro) {@value(if n==1 then@macro(e)else(@macro(e); rep(n-1, e)))};
rep(100, print(“MACRO!!”));

70

それ○ ○でできるよ「レイヤ」に似てるもの大集合71

コンテキスト指向プログラミング (COP)

Classbox

Classboxes: A Minimal Module Model
Supporting Local Rebinding[Bergel&Ducasse&Wuyts 2003]
機能としてはだいたい同じじゃないかと。
Polemyの方が根本的に世界を変える指向selector namespace

Refinement

Ruby 2.0: Classboxes, nested methods, and real private methods
http://www.slideshare.net/ShugoMaeda/rc2010-refinements

72

多重世界機構超時空プログラミングシステム
Uranus [中島 1985]
これらも「根本的に世界を変える」違い。
・ lift function でリテラルの意味まで変える
・ 基本的には「世界」を継承しない

Worlds/JS
Worlds: Controlling the Scopeof Side Effects [Warth 2009]

73

ActiveS式

Ziggurat: Static-Analysis for Syntax Objects[Fischer&Shivers 2006]
マクロが、単なるS式に展開されるのでなく・「展開」メソッドを呼び出すとS式を返す
open classのオブジェクトになってる・ノードにメソッド足せる
・静的解析のためにオーバーライドすると、元の式レベルに意味を展開しないで解析が！！

“完全に別の static semantics” を好き勝手足すという意味ではこれが近い。
自分で定義したマクロ以外の意味もオーバーライドしたいよね？というのがPolemy

74

準クオート
これを @macro と @value 以外に quasiquote ` == @macro
unquote , == @value
一般化した感じscala.reflect.code
C#の式木

Perlのリスト/スカラ

もっと色々激しく「コンテキスト」増やしましょう75

Pluggable Types
Pluggable Type Systems[Bracha 2004]
JSR 308: Annotations on Java Types
色んな（静的）セマンティクスを好きなだけ足そう、というスピリットはここから来ている

C#やJavaの
ただ、単に「構文木」を扱うメタプログラム
Annotation
じゃなくて、「関数 is 関数」「変数 is 変数」パラダイムで、できるだけ元のプログラムをそのまま”実行”する形でやりたい

76

HOAS
Higher Order
Abstract Syntax
構文木を「関数は関数」で表現

抽象解釈をユーザコードレベルで色々定義できるようにしたもの、としてPolemy を使えるかも、と思ったけど、有限性を利用した停止性をメモ化だけで実現しようとしているのでかなり無理がある

値を抽象化した状態で計算することで、コードの色んな性質を静的に解析する技法

Abstract
Interpretation
モナドモナド

77

おわり

78

Cast

PowerPoint のクリップアートにいた素敵な髪型の女の子

URL

名称未設定

http://www.kmonos.net/repos/polemy

Slogan 「１つのコードに複数の意味」
Todo• 「レイヤを使ったコードを別レイヤで実行する」（≒ @type を使ったコードの @type での型検査） が全然うまくいってない• 作った値を過去に遡ってレイヤ評価できた方がいいかも（var x = e; @lay(x) で e を見たい） 遅延評価？