<< 前 ホーム

bakaid: 20130122

sl3.cにはもう一つ唸った点があります。S式の解析の処理
です。

sl3.cのS式解析は、次の2つの関数がポイントになります:

obj *readobj() {
  char *token;

  token = gettoken();
  if (!strcmp(token, "("))
    return readlist();
  ...
  return intern(token);
}

obj *readlist() {
  char *token = gettoken();
  obj *tmp;
  if (!strcmp(token, ")"))
    return nil;
  ...
  putback_token(token);
  tmp = readobj(); /* Must force evaluation order */
  return cons(tmp, readlist());
}

ポイントに集中しやすいように、プロパーリストとシンボル
以外の部分は省略しました。

パッと見てわからなかったのが、readlistで呼ばれている
putback_tokenです。これは、ungetcのトークン版といえる
もので、putback_tokenされたトークンが次のgettokenで
取り出されます。

readlistの処理は、空リストならnilを返し、そうでなけ
ればputback_tokenで戻したcar部をreadobjで解析し、
cdr部をreadlistで再帰するという感じです。

このやり方、Lispのイディオムを踏まえたものという見方
もできますね。Lispの入門書でよく見かける次のような
コード:

(defun mycopy (lst)
  (if (null lst)
      nil
    (cons (car lst) (mycopy (cdr lst)))))

これはネストされてないリストのコピーですけど、こうした
再帰のイディオムを思い起こさせます。

S式の解析も、コンスセルの実装と同じように、個性が出る
部分です。よく見かけるのは、最後にリストをひっくり返す
パターンです。(1 2 3)というS式なら、(3 (2 (1 ()))と
なるようにつないでいき、最後にひっくり返す。

ひっくり返すパターンはAwklispで見られます:

https://github.com/darius/awklisp

他には、そもそもコンスセルを使わずに、実装言語の配列
を使ってしまうという豪快なやり方もあります。lis.pyが
それです:

http://norvig.com/lispy.html
http://norvig.com/lispy2.html

sl3.cのトークンを戻すというやり方は、単純でありながら
Lispっぽさが残っていて面白いと思ったのでした。

本家Permlink

<< 前 ホーム


Copyright © 1905 tko at jitu.org

バカが征く on Rails