継続の実装は

Unlambdaのソースを読め。

うは。その手があったか!!SKK!!SKK!!

以下激しく読みずらい作業メモ。後でまとめます。

コード読み

やっぱり、C版をちょっと読む。

• 906行。僕のschemeよりも長いかも(笑
• GNU式に書かれてるので、ちと読みずらい。
• なので、mainから手動でコード整形していくことにする。
• main
  • 標準入力か、ファイルからソース読み込み、その後パーサーへ。
• 基本的な流れは、main > パーサー > run > eval < - > applyらしい。 <- 後述
• パーサ。
  • struct expression_s *parse()となってるので、expression_sが構文木になるっぽい。
  • 構造体expression_sは関数、function_s又はexpression_s2個が入るらしい。
  • 意味わかんないマクロをガリガリ削除。800行に削減。
  • `があったら左右を見に行くらしい。後は関数登録。
  • 大文字小文字どっちでもいいみたい。
  • なんかすげー単調。もうちょっとすっきり書けそうなソース。半分以下になるよ。絶対。
  • はい。構文木できあがり。
• run
  • なんかタスクという奴があるらしい。
  • とりあえずEVALを進んでみる。
  • また削除。765行に削減。
  • おっといきなり、獲物発見。タスク構造体の中に、継続あり。
• invoke,apply,eval
  • あんま見てないけど、タスク構造体を返す。
  • タスク構造体がUnlambdaのコンテキストになるらしい。

整形完了。

中間報告

獲物を見つけた所でとりあえず満足(おいおい

• びっくりするくらい単調なコードが多いので、半分以下で書けそうな予感がする。
• どうやら、Unlambdaのタスク回りを読めば、少し継続がわかりそうだ。

このままじゃなんともならないので、とりあえずデバッグ方法を探ろう。あと継続の使いかた(汗

めしめし。

コード読み2

Scheme版。

• 162行。実質は100行ほど。当たり前だけど、短い。
• MzSchemeでは、mzscheme -f unlambda.scm -e '(main)'で動く。
• 流れはmain > 継続の保存 > バーサ > eval < - > apply
• パーサでリストを作って。
  • うは。caseが便利杉。
• evalして、applyなんだけど!!
• applyって言うほどapplyしてなくて、リスト操作してるだけというシンプルさ!!

継続以外はホントにラムダが無い・・・UnLamada!!

第二中間報告

「ラムダが無くても関数型言語は作れる」

では、早速

Scheme版の真似をして、skを実装していく。

(define (un-eval ex)
  (if (pair? (car ex))
      (un-apply (un-eval (car ex)) (un-eval (cdr ex)))
      ex))

(define (un-apply ex arg)
  (case (car ex)
        ((k)  (list 'k1 arg))
        ((k1) (cadr ex))
        ((s)  (list 's1 arg))
        ((s1) (list 's2 (cadr ex) arg))
        ((s2) (un-eval (cons (cons (cadr ex) arg)
                             (cons (caddr ex) arg))))))

(un-eval '(((k) . (k)) . (k)))         ; ``kkk -> k
(un-eval '((((s) . (k)) . (k)) . (k))) ; ```skkk -> k

Unlambda完成〜(早)

どうやら、クロージャもリストで実装しているようだ。ラムダの要らない訳がわかった。

s1,s2とかがクロージャ状態。クロージャがリストで、手続きがが対。クロージャが見れるってのが新鮮です。

パーサ書き

そういえばSchemeでパーサを書くのはじめて。文字列ポートopen-input-stringを使って書いてみる。

(define (un-parse input-port)
  (let ((ch (read-char input-port)))
    (if (eof-object? ch)
        (error "eofで終わることは無い。ハズ。")
        (case ch
              ((#\`) (cons (un-parse input-port)
                           (un-parse input-port)))
              ((#\k) '(k))
              ((#\s) '(s))
              (else
                (error "そんなの知らない" ch))))))

(define (test str)
  (un-eval (un-parse (open-input-string str))))

出来た!!

関数は一つの引数しか取れないという純粋なλ演算の形を採用しているので、括弧すら要らない。Schemeならconsで実現可能。

Unlambdaの場合、ツリーを一個しか読まないという特徴があるので、構文木も一個しか作らない。その後は何を打ち込んでも無反応。ツリーを読んだら次にファイルを読み込むフェーズが無いので、インタプリタに制御が移る。もう一回(main)を打ち込んで再開させるらしい。

おもろいなぁ。後は拡張機能を付け足していけばいい。

フィボナッチが動いた

displayとiを加えて、フィボナッチを動かす。

(test "```s``s``sii`ki`k.*``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`kr``s`k`sikk`k``s`ksk")

おぉ(無限ループ)

誰がどう見てもフィボナッチには見えない!!

遅延評価の実装

うぅん。別に遅延評価を組み込む必要は全く無い気がするんだけど。

実装方法は、

• `d 関数だったら、評価せず約束として保存
• `約束 引数が表れたら約束を評価して、引数を評価する。

イマイチありがたみがわからない。

第三中間報告

継続以外は大体実装完了。
ミニ言語処理系の中では一番面白い題材だと思う。作るよりも使う方が大変なんだけど・・・。

とりあえずScheme組込みの継続を使って実装していこう。

継続も実装完了

組込みの継続を入れた。コピッペなんだけど。

疑問点

継続渡しがあればなんとかなりそうなので、Unlambdaに継続を実装しても「あんまり意味が無い」ような気がする。

もし、skだけでなんでも出来るなら、継続や遅延評価は必要ないはずなんだ。うぅん。謎だ謎。

Cバージョンを作り中

とりあえずSKコンビネータ作り。

#include <stdio.h>
#include <stdlib.h>
#include <gc.h>

enum {T_EXPRESSION, T_FUNCTION};
enum {F_CLOSURE, F_K, F_S};

typedef struct object_t object;

typedef struct pair_t {
    object *car;
    object *cdr;
} pair;

typedef pair expression;

typedef struct {
    int t;
    object *o;
    object *args;
} function;

struct object_t {
    int type;
    union {
        expression e;
        function f;
    } data;
};

object *car(object *o);
object *cdr(object *o);

void display(object *o);
object *eval(object *o);

object *new_object(int type)
{
    object *o = (object *) GC_malloc(sizeof (object));

    o->type = type;

    return o;
}

object *new_function(int type, object *obj)
{
    object *o = new_object(T_FUNCTION);

    o->data.f.t = type;
    o->data.f.o = obj;
    o->data.f.args = NULL;

    return o;
}

object *get_args(object *o)
{
    return o->data.f.args;
}

object *new_expression(object *l, object *r)
{
    object *o = new_object(T_EXPRESSION);

    o->data.e.car = l;
    o->data.e.cdr = r;

    return o;
}

object *car(object *o)
{
    return o->data.e.car;
}

object *cdr(object *o)
{
    return o->data.e.cdr;
}

object *cons(object *a, object *d)
{
    return new_expression(a, d);
}

object *parse(char **s)
{
    int c = **s;

    switch (c) {
    case '`' :
        {
            object *l, *r;

            (*s)++;
            l = parse(s);
            (*s)++;
            r = parse(s);
            return new_expression(l, r);
        }
    case 'k':
        return new_function(F_CLOSURE ,new_function(F_K, NULL));
    case 's':
        return new_function(F_CLOSURE, new_function(F_CLOSURE ,new_function(F_S, NULL)));
    case '\0':
        fprintf(stderr, "EOF ERROR\n");
    default:
        fprintf(stderr, "まだ。\n");
    }
    exit(EXIT_FAILURE);
}

void display(object *o)
{
    if (o->type == T_EXPRESSION) {
        printf("(");
        display(o->data.e.car);
        printf(" ");
        display(o->data.e.cdr);
        printf(")");
    } else if (o->type == T_FUNCTION) {
        switch (o->data.f.t) {
        case F_K:
            printf("K");
            break;
        case F_S:
            printf("S");
            break;
        case F_CLOSURE:
            printf("C-");
            display(o->data.f.o);
            break;
        }
        object *args = get_args(o);
        for (;args != NULL;args = cdr(args)) {
            printf("[");
            display(car(args));
            printf("]");
        }
    }
}

object *apply(object *op, object *arg)
{
    switch (op->data.f.t) {
    case F_CLOSURE:
        {
            object *new;

            new = op->data.f.o;
            new->data.f.args = cons(arg, get_args(op));
            return new;
        }
    case F_K:
        return car(get_args(op));
    case F_S:
        return eval(new_expression(new_expression(car(cdr(get_args(op))) , arg),
                                   new_expression(car(get_args(op)), arg)));
    }
}

object *eval(object *o)
{
    if (o->type == T_EXPRESSION)
        return apply(eval(car(o)), eval(cdr(o)));
    else
        return o;
}

int main(void)
{
    GC_INIT();

    char *s = "``skk";
    object *o = parse(&s);

    display(o);
    printf("\n");
    display(eval(o));

    printf("\n");

    return EXIT_SUCCESS;
}

実行すると、

% ./unlambda
(((C-C-S C-K) C-K) C-K)
C-K

ま、なんとか動いてるカンジ。Cってタイヘンデスネ・・・。

k1,s1,s2とか状態クロージャを持つのが嫌だったので、フツーにクロージャを作成しました。

freeが面倒になってきたので、GC使うことに(サボり)

大体いいかな。

またコードリーディング

というより、修正。679行まで削減。200行削った!!

init_ptr呼びすぎ。ナンダコレ。

init_ptrは参照カウントを増やしつつ、代入するメソッドらしい。GCってこうやるのか。ふむふむ。

で、650行に削減。減らし方のコツを掴んできた(笑)

まだまだ減らすよ。

620行まで減った。ふふ。しかし、これ以上減らすには奥の手しかない。

#include <gc.h>

コレダ。さよなら参照カウント・・・。

487行。init_ptrが無くなったのでガンガン短くできそうだ。やっとデータ構造が見えてきた。

わーい

450行。半分にまで削減したぞ!!

やっとapplyがすっきりしてきた。これからは増えそうなヨカン。

もしかすると

継続を実装したUnlambdaは再帰無しで書ける。

というか、

もう再帰無しになってたり。

mainの一番最後を書き直すと、

    for (; task->t != TASK_FINAL ; task = run(task))
        ;

構文木が、線形リストになった!!

驚きだ。

構造体について

さて、プログラムがすっきりしてきたので、データ構造を見ていこう。

• generic_s
  • 参照カウント方式によるGCの為の構造体。
  • 以下の構造体は、こいつを継承してる形になる。今回本題ではないので、削除した。
• function_s
  • 関数を入れる。値(文字)も一緒に入ってる。
• expression_s
  • 構文木。
  • 関数か、構文木が入る。
• continuation_s
  • 継続。
  • 後で行う関数が入ってる。
  • 線形リストになってるのがポイント。
• task_s
  • 今やるべき事。
  • タスク構造体は1個しか存在しない。
  • evalすると、タスク構造体が帰ってくる。

となってる。今回のポイントは、どのようにして継続を作り出すかということに注力する。

タスク

タスク(今やるべきこと)は4つのフェーズに分かれる。

• (構文木)
• (関数 構文木)
• (関数 関数)
• 終了

という状態を持つ。runメソッドによって条件を分岐する。

• (構文木)なら、eval
• (関数 構文木)なら、右側をeval
• (関数A 関数B)になってたら、関数Aに関数Bをapplyする
• 終了ならプログラムを終了する。

最適化した構造体は、こうなる。

struct task_s {
  enum { TASK_EVAL, TASK_APP1, TASK_APP, TASK_FINAL } t;
  union {
    struct {
      struct expression_s *expr;
    } task_eval_v;
    struct {
      struct function_s *erator;
      struct expression_s *rand;
    } task_app1_v;
    struct {
      struct function_s *erator,
                        *erand;
    } task_app_v;
  } d;
  struct continuation_s *cont;
};

すっきりした。もうちょっとすっきりしそうな気もする。

eval

次にevalを見ます。タスクを返すだけです。

evalは2つのフェーズを持ってます。関数か、構文木か

• 関数だった場合、次にやるべき事は関数を作用させること。つまり、タスクに、applyしてくれ。と頼みます。
• 構文木だった場合はとりあえず右側を継続に投入して、左側を見に行く事をタスクに頼みます。

evalが線形になってるのがポイント。

apply

実際に関数を適用するフェーズ。

• クロージャなら、継続を見に行く。
• 関数の実体なら適用する。

invoke

継続を見て、次にやることを決定する。

継続にするとなにがいいのか

再帰が無くなるので、最適化しやすい。call/ccはその過程で生まれた副産物。

継続って何?

プログラム全体を継続渡しにしたもの。

大雑把にいうと、スタック。

でも、スタックの中に関数が入ってたり、構文木が入ってたりして一般的なスタックの概念では無い。

プログラム全体を「ゴッソリ」スタックの中に押し込んでしまったのが、継続だ!!

プログラム全体を継続渡しにしてやれば、gotoと等価になる。つまり、末尾呼び出しの最適化が出来る。

ふふ。理解はしたが、とんでもない概念だ。意味不明過ぎるぜぃ!!

後でまとめよう。

またコード修正

430行まで減ってきた。

クロージャー化が必要そう。

call/ccの実装は

call/cc自体は継続を戻すだけなので、驚くほど簡単に実装出来る。クロージャ並に簡単。

問題は継続を作り出す事だ。

むむぅ

継続に状態を持たなければいけないというのが現在抱える問題。

(apply (eval 左) (eval 右))

右と左を見なければいけないというのが面倒だ。左のeval継続、右のeval継続、applyする継続。

Unlambdaのapplyは必ず継続を2個消費するので、右と左を共通化出来そうな気がする。

むむぅ。

とりあえず

schemeで。

(define ((k x) y) x)
(define (((s x) y) z) ((x z) (y z)))
(define (i x) x)

(define (un-apply op arg)
  (eval `(,op ,arg)))

(define (un-eval cont)
  (if (null? cont)
      `END
      (let ((op (car cont))
            (arg (cdr cont)))
        (if (pair? op)
            (un-eval (cons (car op) (cons (cadr op) arg)))
            (if (null? arg)
                op
                (let ((operand (car arg)))
                  (if (pair? operand)
                      (un-eval (cons op (cons (car operand)
                                              (cons (cadr operand)
                                                    (cdr arg)))))
                      (un-eval (cons (un-apply op operand)
                                     (cdr arg))))))))))

(define (main ex)
  (un-eval (list ex)))

(main '((((s k) k) ((s k) k)) i))

結果は正しく表示されるけど、実はうまくいってなかったり。

skk skk iだと、i skk iのとき、iにsを代入してしまう。iiiにならなければいけないのに。

例えば、(s (k (k i)))となってたとき、

sはまだ。kはまだ。kiオケーそのあとだだっと、左へ進む事になる。

面倒だから、sにそのまま代入してしまうと、遅延評価になるんだろうな。

左へ進むという奴をどう表現するか。

スタック <- 現在 -> 継続

違うな。Unlambdaは,

現在 -> 継続

なんだよな。やっぱりタスクが無いとだめそうか。