LoginSignup
5
0

More than 3 years have passed since last update.

NextremerAdvent Calendar 2019Day 3nextremer
@t-sin

shigoto-lisp: はじめてLispを実装するときに 〜 適用編

Last updated at Posted at 2019-12-02

この記事はNextremer Advent Calendar 2019の3日目の記事です。

また、この記事は以下3つのような連作記事の3つめです。

前回のあらすじ

言語実装の知識があると、自作プログラムのためにちょっとした設定言語を設計し、それをパースしたり実行したりできるのでとってもよいです。前回の記事では言語実装の入門としてLispプログラム(S式)の評価器を充実させ、分岐や値の束縛をできるようにしました。

この記事では

評価器に関数っぽいものを追加します。組い込みの関数に自作楽器とかパフォーマンスっぽ加え、ユーザが関数を定義できるようにします。本記事では以下の5、6、7を実装します。

  1. 入力文字列をそのまま出力するだけのREPLをつくる (パース編)
  2. 数値をパースし評価する (パース編)
  3. シンボルをパースし評価する (パース編)
  4. リストをパースし評価する (パース編)
  5. 特殊形式を評価する (評価編)
  6. シンボルを値に束縛する (評価編)
  7. 組み込み関数を適用する (適用編)
  8. 関数オブジェクトを作成し適用する (適用編)

ちなみに成果物の処理系はこちらです(社内勉強会でつくったためこの記事とつくった順番が違います。コミットログは参考程度に参照してください)。
https://github.com/nextremer/shigoto-lisp

それではやっていきましょう。

7. 組み込み関数を適用する

ここまでつくってきた処理系はささやかではありますが条件分岐ifとdefineによる代入があります。しかしそのほかのオペレータを持っていないため計算すらできません。そこでこの節では計算するための道具を追加します。追加する関数は以下の6つです。

  • +: 加算
  • -: 減算
  • *: 乗算
  • /: 除算
  • =: 等値判定
  • .: 値の出力

これらを導入すると(+ 1 (* 2 3))のようなちょっとした計算ができるようになります。

組み込み関数の実現方法でもっとも単純なのは、実装に使用している言語の関数オブジェクトをそのまま使うことです。組み込みのオブジェクトを実現するには、初期状態の束縛bindingsの中に予め放り込んでおけばよいです。ですので、加算用の組み込み関数の実装イメージは以下のようになります。

var bindings = {
  '+': () => {},  // どんな仕様の関数にするかはこれから決める
};

関数の実行には何が必要かということを考えてみます。いつも関数に渡しているものといえば、引数がありますね。あと引数をどう処理するか、つまり関数本体の処理が必要です。

これから定義したい組み込み関数の引数は、+は2個ですが.は1個です。3個などもありうるので引数全体を配列で渡すことにしましょう。つまりこのような関数呼び出し(fn 1 2 3 4 ...)があったときは、引数全体の配列[1, 2, 3, 4, ...]を渡します。先ほどの定義はこのように変わります。

var bindings = {
  '+': (args) => {},  // どんな処理をするかはこれから決める
};

では、関数本体の処理はどうしましょう。引数の配列が渡されているので、それを用いて返り値を計算し必要であれば値を返すだけでよいです。そうすると+はこんなふうに定義すればよさそうです。

var bindings = {
  '+': (args) => (args[0] + args[1]),
};

さあ、これを実行できるようにしていきます。いままでの評価器ではオペレータ呼び出しの名前はswitch分に直接書かれていましたが、switch文にない場合「bindingsから関数を取得し呼び出す」ということをしなければなりません。そこでswitch文にdefault節を追加します。取得した関数の呼び出しは、JavaScriptの機構を用いて単に呼び出します1。

これによってsl_evalは以下のようになります。

// 式を評価する。
const sl_eval = (form) => {
  if (Array.isArray(form)) {
    // オペレータ呼び出しのときの処理
    const name = form[0];
    switch (name) {
      case 'if':
        if (sl_eval(form[1]) !== []) {
          return sl_eval(form[2]);
        } else {
          return sl_eval(form[3]);
        }

      case 'define':
        let val = sl_eval(form[2]);
        bindings[form[1]] = val;
        return val;

      // 関数の適用。束縛から名前で取ってきて残りの引数を渡して呼び出す。
      // もちろん、関数以外のものが入っていたらエラーになるので注意。
      default:
        let fn = bindings[form[0]];
        let args = form.slice(1);
        // 引数を評価するのを忘れずに…。
        return fn(args.map(arg => sl_eval(arg, env)));

    }
  } else if (typeof form === 'number') {
    return form;
  } else if (typeof form === 'string') {
    return bindings[form];
  }
};

この状態でREPLを立ち上げ(+ 1 2)などと実行してみてください。足し算ができるようになったはずです。

あとは節の冒頭で述べた組み込み関数群を以下のように実装します。

var bindings = {
  '+': (args) => (args[0] + args[1]),
  '-': (args) => (args[0] - args[1]),
  '*': (args) => (args[0] * args[1]),
  '/': (args) => (args[0] / args[1]),
  '=': (args) => (args[0] === args[1] ? 't' : []),
  '.': (args) => console.log(args[0]),
};

8. 関数オブジェクトを作成し適用する

最後に、ユーザが関数を定義して使えるようにします。これにてミニプログラミング言語が一応の完成を見ます。

まず「ユーザが関数を定義する」とはどういうことか考えてみましょう。前の節でも述べましたが引数の情報と関数本体で行う処理の情報が必要です。ユーザ定義関数はユーザが入力した文字列をもとに作らるので、関数本体の情報とはユーザが入力したプログラムそのものです。これを評価器sl_evalに渡して実行するのです。

引数の情報は、組み込み関数のときには実際の値のリストでした。ユーザ定義関数のときは事情が異なります。関数本体のコードはsl_evalに実行してもらうことになるので、sl_evalが触れる形にしてやらなければなりません。そう、引数もまた束縛の形にしてあげなければならないのです。

shigoto-lispでの関数オブジェクトはJSのオブジェクトで次のような構造をもつものと決めましょう。

{
  args: [...],  // 引数の変数名リスト
  code: [...],  // パースされた式のうち関数本体の部分
}

関数定義からこの情報を抜き出してJSオブジェクトをつくり、実行の時点で引数を全て評価して関数実行用の束縛をつくってsl_evalに渡します。

関数本体を実行するときの引数の束縛作成ですが、グローバルな束縛や、関数の外側の束縛も触れるようにしなければなりません。たとえば以下のように振る舞ってくれると自然な感じがします。

(define n 42)

(define fn1 (lambda () n))
(fn1)  ; => 42 となってほしい (グローバルな束縛)

(define fn2 (lambda (n) n))
(fn2 3)  ; => 3となってほしい (ローカルな束縛)
n  ; => 42となってほしい (ローカルな束縛は独立)

そのため、入れ子になった環境というものを考えます。`関数適用の本体の処理が動きだす度に深くなっていく束縛をつくるのです。ここでは以下のような構造で環境を表します。


var global_env = {
  parent: null,  // 上の環境
  bindings: {
    '+': (args) => (args[0] + args[1]),
    ...
  },
};

// 環境を探索して名前に対応する値を見つける。
const sl_find = (name, env) => {
  if (env === undefined) {
    return undefined;
  }
  let val = env.bindings[name];
  if (val === undefined) {
    return sl_find(name, env.parent);
  }
  return val;
}

親の環境(グローバルな環境ではnull)と束縛を持つJSのオブジェクトです。また、与えられた環境から値を引いてくる関数sl_findも用意しました。指定されたnameで環境を調べて値があれば返し、なければundefinedを返します。

これを用いて評価器を改造します。改造ポイントは束縛のデータ構造変更対応を除くと3つです。

  1. 引数に環境を取れるようにする (指定なしだとグローバル環境を使う)
  2. switch文にlambdaの節を追加
    • (lambda (引数 ...) 本体コード)で関数オブジェクトを作成できる
  3. switch文にdefault節を追加
    • (関数名 引数 ...)の式のとき、組み込み関数かユーザ定義関数を呼ぶ処理をする

1と2は大丈夫だと思うので、3について説明します。前の節でJSの関数オブジェクトを利用した組み込み関数を定義しましたが、ここでユーザ定義関数用の処理で上書きしてしまうと組み込み関数のほうが動かなくなってしまいます。さいわい組み込み関数はfunctionですがユーザ定義関数はobjectなので、それを調べて両者を識別できます。

ユーザ定義関数の実行には4つの段階を踏みます。

  1. 新しい環境の作成
  2. 引数の式を事前に全て評価して、実引数の値を決定
  3. 関数オブジェクトの引数情報に従って、仮引数と実引数の束縛を作成
  4. sl_evalに関数のコードと作成した環境を渡して実行

以上をコードにすると、以下のようになります。

// 式を評価する。
// 束縛のデータ構造が変わったので追従した。
// また、ユーザ定義関数の作成`lambda`と呼び出しが可能になった。
const sl_eval = (form, env=global_env) => {
  if (Array.isArray(form)) {
    const name = form[0];
    switch (name) {
      case 'if':
        // 配列の等価比較はできないのでこの雑ハックを使いました
        if (JSON.stringify(sl_eval(form[1], env)) !== JSON.stringify([])) {
          return sl_eval(form[2], env);
        } else {
          return sl_eval(form[3], env);
        }

      case 'define':
        let name = form[1];
        let val = sl_eval(form[2]);
        env.bindings[name] = val;
        return val;

      case 'lambda':
        return { args: form[1], code: form[2] };

      default:
        let args = form.slice(1);
        let fn = sl_find(form[0], env);
        if (typeof fn == 'function') {
          return fn(args.map(arg => sl_eval(arg, env)));
        } else {
          // 1. 新しい(空の)環境の作成
          let new_env = { parent: env, bindings: {} };
          // 2, 3. 引数の式を全て評価し、仮引数と実引数の束縛を作成
          fn.args.forEach((arg, i) => { new_env.bindings[arg] = sl_eval(args[i], env) });
          // 4. 関数本体のコードを新しい環境の下で評価
          return sl_eval(fn.code, new_env);
        }
    }
  } else if (typeof form === 'number') {
    return form;
  } else if (typeof form === 'string') {
    return sl_find(form, env);
  }
};

さあどうでしょう。試しに階乗を計算する関数を書いて動作をテストしてみましょう。

> (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))
undefined
> (fact 10)
3628800

Wolfram Alphaによると答えは同一のようで、成功です！

10.png

おわりに

この連作記事では、JavaScriptの基礎知識がある人向けに言語実装の初めの一歩を踏み出せるよう、ミニLispのつくりかたを解説してみました。これ以降は、この処理系を拡張したりエラー処理をちゃんとしてそれっぽい言語にするのもいいですし、言語処理系の本はたくさん出ていますのでそちらで理論の勉強をするのも楽しいです。また、自作アプリにちょっとした言語を生やしてみるのもたのしいですよ。

  1. 関数オブジェクトのない言語だったり、実装言語の関数オブジェクトを用いない場合だったりのときには「関数の呼び出し」そのものを自作しなければならいため、この言い方をしています。 ↩

5
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
0