Lispをあなたの言語にも取り入れる方法

  • このエントリーをはてなブックマークに追加

      2016/03/03

僕はプログラミング言語Lispのファンだ。だが、多くの不慣れなプログラマにとって、その素晴らしいまでの概念的なエレガントさと読みやすさを両立させることは難しい。Lispの基本的なコンセプトは驚くほどシンプルだが、その習得となると、とてもシンプルとは言いがたい。

UZzlqUy

大まかな歴史

Lispというのは、List Processing(リスト処理)という言葉から派生した言葉だ。この言語の基本的な考えは、思想や構成物を、構文ではなく、データ構造として表現するということだ。具体的には、思想や構成物をリストとして表現する。

(print "Hello world!")
  • リストを表示するには ( と ) を使う
  • 引数はスペースで区切る
  • 最初の項目は関数
  • 残りの項目はその引数となる

あなたが見慣れている特殊な構文やキーワードで実装された構成概念は、突如として上の例のようになる。

(if (= 5 5)
  (print "Sanity!")
  (print "Insanity!"))

ifは、条件を評価する特殊関数にすぎず、もしその条件がtrueなら、次の引数を評価し、そうでなければ三つ目の引数を評価する。

このような関数は特殊形式として知られている。構文の中核部分が特殊形式として実装されることはよくあるが、これについて特筆すべき点はない。マクロを使って自分で実装すればいいと思う。Clojureは(多くのLisp言語と同様に)、中核構文の多くがマクロで実装されている。

僕たちは長い間、データを操作するためにコードを書いてきた。コードがデータなら、コードを操作するためのコードも容易に書ける。

だが、この驚くべきものの本質はClojureではない。RacketでもSchemeでもない。これらは全て、code-as-data(データとしてのコード)という考えが姿を変えたものにすぎない。確実に言えるのは、これらの言語が、関数とリストを持つ唯一の言語ではないことだ!

もしデータとしてのコードを、好きな言語で書けるとしたらどうだろう?

実験

見つけるのに少し苦労するが、多くの人気プログラミング言語にはLispが隠れている。自慢にならないことをしなければならないかもしれないが、リストと高階関数のあるプログラミング言語を思いつくことができれば、そこにLispがあるだろう。Javascriptを例にとってみよう。

(print "Hello world!")

上の例からJavascriptへ、単純な構文翻訳の妨げになっているのは何だろうか?

[alert, 'Hello world!']

妨げになるようなものは何もない。むしろ、たいしたことはしていない。Lispの望むやり方で、関数と文字列を含んだ配列を返すだけだ。だがJavascriptのランタイムは、こういうやり方でコードを書かれることを望んでいない。ランタイムがあたかも関数であるかのように、全ての配列を実行するよう求めたとしたら、かなり混乱してしまうだろう。

これを実現させるために、少し作業をしてみようと思う。expression(式)を解釈するeval関数を定義しよう。

function eval(expression) {
  // the first item is the function
  var fn = expression[0];

  // the remaining items are the arguments
  var args = expression.slice(1);

  // call the function with these arguments
  return fn.apply(null, args);
}

そして、実行するとどうなるか見てみよう。

eval([alert, 'Hello world!']);
// alerts 'Hello world!'

以上。(非常にミニマルな)Lispを実装できた。他の組込関数も試してみることができる。より簡略にするため、今からevalの呼び出しは例から省くこととする。

[parseInt, '4.41'] // 4
[isNaN, 103]       // false
[btoa, 42]         // 'NDI='

もしあなたがconsole.logやdocument.writeを使っているなら、eval関数が機能しないのには立派な理由があるので、今はとにかくalertし続けてほしい。

式のあれこれ

7cx4nBz

ここからは、コード内のとしてのリストについて、述べていこうと思う。そうすることで、リストデータ構造と区別するのに役立つだろう。試しに、他の式をすでに含んでいる式を評価したらどうなるだろうか?

[alert, [prompt, "What is your name?"]]

配列かのような内部式を知らせるアラートを受け取る。引数のような式を見つけたら、データとしてではなくコードとして評価すべきだとeval関数に理解させる必要がある。

function eval(expression) {
  // the first item is the function
  var fn = expression[0];

  // the remaining items are the arguments
  var args = expression
    .slice(1)
    .map(function(arg) {
      // if this argument is an expression, treat it as code
      if(arg instanceof Array) {
        return eval(arg);
      } else {
        return arg;
      }
    });

  // call the function with these arguments
  return fn.apply(null, args);
}

今度は再帰を導入した。いい調子だ。この関数は、構造のどの深さであっても、見つけた全ての配列を評価する。

[alert, [prompt, "What is your name?"]]

構文と名前

今のところ順調だ。だが、計算はどうやるのだろう?

[+, 5, 5]

好き嫌いはさておき、これだと間違いなく構文エラーになる。

Lispを理解している言語を選ぶ真のメリットの一つは、構文が簡潔なおかげで識別子名に使える文字が豊富にあることだ。例えば、Clojureでは+はただの関数名にすぎないが、たまたま数字を足すという役割を担っている。

構文に重きが置かれる言語に、こうした言語超越的な概念を取り入れたい時は、もうひと仕事しなければならない。

function add(a, b) {
  return a + b;
}

[add, 5, 5] // 10

これは確かにエレガントなのだが、落とし穴がある。代わりにこうしてみよう。

['+', 5, 5] // Error: '+' is not a function

ネイティブ関数をいくつか定義しよう。

var native = {
  '+': function(a, b) {
    return a + b;
  },
  '-': function(a, b) {
    return a - b;
  }
};

[native['+'], 5, 5] // 10

やや冗長な感じは否めないが、少し微調整すればマシになる。第2引数として、ネイティブオブジェクトをevalに引き渡してみよう。

function eval(expression, native) {
  // the first item is the function or it's name
  var fnName = expression[0];

  // resolve the function from native if necessary
  var fn = typeof fnName === 'string' ? native[fnName] : fnName;

  // the remaining items are the arguments
  var args = expression
    .slice(1)
    .map(function(arg) {
      // if this argument is an expression, treat it as code
      if(arg instanceof Array) {
        return eval(arg, native);
      } else {
        return arg;
      }
    });

  // call the function with these arguments
  return fn.apply(null, args);
}

['+', 5, 5] // 10

これを見て、あなたがLispの”the zen of simplicity (シンプルさの精神)”っぽくないと感じていたらいいのだが。そう、あなたは正しい。”the zen of simplicity”っぽくないのだ。だが、シンプルを望むなら、よく分かっていないプログラミング言語におけるその場しのぎのlispの実装について読んで一体何がしたいのか、自分の胸に問いかけてみるといい。

23mGq6v

これは、僕たちが理不尽なことをするためのサンドボックスだ。こうした類のハックを見逃していては、せっかくの機会を無駄にする。さあ、+、 -、 *、 /、=やその他ネイティブ関数に使えそうな演算子を実行してみよう。これらは後で使うので。

変数

変数のない言語は難しいので、変数を実装しようと思う。

function def(name, value) {
  window[name] = value;
}

[def, a, 5]

このdef関数は、変数名と値を取得して割り当て、windowオブジェクト(Javascriptのグローバルスコープ)と関連付ける。しかしながら、この式には見て見ぬふりのできない重要な問題がある。式の中の変数値を解決できなくても僕たちに責任はない。Javascriptの実装がやってくれるのだ。

これは、a.の値を解決しようとする。僕たちはこれについて宣言していないので、エラーが返される。そのうえ、下手すると宣言していたとしても、初期化していなければ結局、undefinedのname引数として終わる。もちろんJavascriptには、これに対処する素晴らしい方法がある。undefinedを無理やり文字列にし、常にキーとして使うのだ(Oh、Javascriptよ…)。

まぁいいだろう。分かり切った解決策は、代わりに文字列として名前を引き渡すことだ。

[def, 'a', 5]
[alert, ['+', a, a]]

素晴らしい。まだ動かないことを除けば。2番目の式は、最初のを解釈する前にランタイムによって評価される。前回どうやって解決しただろうか?代わりに文字列を使うのだ。

スコープ

[def, 'a', 5]
[alert, ['+', 'a', 'a']]

今僕たちは、すべての文字列引数を試し、変数として解決しなければならない。また、関数についても同様にしなければならなくなる。変数をリストの最初のアイテムとして使うためだ。

さて、我慢してシンプルなスコープを紹介するとしよう。そうすれば全ての文字列にその中の値を参照させることができる。文字列が値を参照しなかったら、rawの値を使えばいいだけだ。

nativeオブジェクトを第2引数として受け入れる代わりに、scopeオブジェクトを受け入れよう。このようにして、ネイティブオブジェクトを、ルートスコープオブジェクトとして引き渡すことができるので、何も壊れない。

function eval(rawExpr, scope) {

  // if the expression isn't a list, just return it
  if(!(rawExpr instanceof Array)) {
    return rawExpr;
  }

  // use existing local scope or create a new one
  scope = scope || {};

  // resolve all our new string names from our scope
  var expression = rawExpr.map(function(symbol) {
    if(symbol in scope) {
      return scope[symbol];
    } else {
      return symbol;
    }
  });

  // the first item is the function
  var fn = expression[0];

  // the remaining items are the arguments
  var args = expression
    .slice(1)
    .map(function(arg) {
      // if this argument is an expression, treat it as code
      if(arg instanceof Array) {
        return eval(arg, scope);
      } else {
        return arg;
      }
    });

  // call the function with these arguments
  // and expose scope as this
  return fn.apply(scope, args);
}

スコープをthisとして各関数にさらすために、僕たちは.applyの最初の引数を使用した。実行中のthisの状態を見せるため、defの新たなネイティブバージョンを定義しよう(ダジャレで失礼)。

var native = {
  def: function(name, value) {
    return this[name] = value;
  },
  print: console.log.bind(console)
};

万が一、アラートを使うのにうんざりしているのなら、printメソッドを追加することもできる。試してみよう。

['print', ['def', 'a', 5]]

今までに見た最も美しいコードではないかもしれないが、動く。

特殊形式

僕たちは評価可能な式を得たが、それらを管理する方法は得ていない。条件文、関数、または複数の式を同時に実行する方法についての判断力もない。

このeval関数は現在、目に入った式すべてを解釈しようとしている。関数のいくつかは、自分の引数の評価を処理する特殊形式であることを示しておく必要があるだろう。

function SpecialForm(fn) {
  fn.__isSpecialForm__ = true;
  return fn;
}

それから、特殊形式で引数となる式の評価を避けるためにeval関数を微調整する。

// ...
// the first item is the function
var fn = expression[0];

// the remaining items are the arguments
var args = expression
  .slice(1)
  .map(function(arg) {
    // don't evaluate the expression if it is a special form!
    if(arg instanceof Array && (!fn.__isSpecialForm__) {
      return eval(arg, scope);
    } else {
      return arg;
    }
  });
// ...

Do

新しい特殊形式を試して、doを実装してみよう。これは、引数を全て評価するため、複数の式を順番に評価することができる。

これまでのLispでは:

(do
  (print "Hello")
  (print "World!"))

新しいネイティブ関数としてこれを加える。

var native = {
  'do': SpecialForm(function() {
    var exprs = [].slice.call(arguments);
    return exprs.reduce(function(_, expr) {
      return eval(expr, this);
    }.bind(this), null);
  }
};

最後の式の値が返されるかどうか確認するために、reduceを使った良い手もある。

上の例を新しい構文に翻訳して実行してみよう。

['do',
  ['print', 'Hello'],
  ['print', 'World!']]

// Hello
// World!

If/Else

条件文のないプログラミング言語の何が良いのだろうか?次の挑戦はif命令文の実装だ。しかしながら、「新しい特殊形式では」つまらないものになるだろう。

var native = {
  if: SpecialForm(function(condition, success, failure) {
    var passed = eval(condition, native, this);
    return eval(passed ? success : failure, native, this);
  }
};

以上。コード3行のif/elseだ。

['if', ['=', 3, 3],
  ['print', 'true'],
  ['print', 'false']]

// true

これがあなたにとって初めてのLisp実装なら、これは特別な瞬間に違いない。条件付き制御フローをデータとして実装したのだから。

関数

関数は、ここでの最後の難関だ。関数には、実際様々なことができる言葉がある。しかし、かなりの障害となる。

より従来型のLispでは、関数はこのように見える。

(def shout
  (fn [name planet]
    (print planet name)))

これは実際、defのローカル変数に結び付く無名関数だ。defの実装はすでにしているので、今やることはfnの実装だけだ。

引数をfnまで分解してみよう。

最初のものは引数のリストで、2番目のものが式(もしくは関数本体)だ。

var native = {
  fn: SpecialForm(function(defArgs, expr) {
    return function() {
      var callArgs = arguments;

      // create a distinct new scope
      var childScope = Object.create(this);

      // use the arguments definition to bind each call arg
      // to the appropriate scope variable.
      defArgs.forEach(function(argName, index) {
        childScope[argName] = callArgs[index];
      });

      // evalue the function body
      return eval(expr, code, childScope);
    }
  })
};

これだ。動的結合してレキシカル・スコープになった。原型的な継承がすごいということについて、同意する時間を取ろうじゃないか?

['do',
  ['def', 'shout',
    ['fn', ['planet', 'greeting'],
      ['print', 'greeting', 'planet']]],
  ['shout', 'hello', 'world']]

// hello world

これで間違いなく冗長さがマシになっただろうから、他のLispからヒントを得てdefnも作成しよう。

var native = {
  defn: SpecialForm(function(name, args, expr) {
    var fn = native.fn.call(this, args, expr);
    return native.def.call(this, name, fn);
  })
};

単純に、既存のdefの実装をfnに結び付ける。

['do',
  ['defn', 'shout', ['planet', 'greeting'],
    ['print', 'greeting', 'planet']],
  ['shout', 'hello', 'world']]

// hello world

ずっと良くなった。

言語に関数がある以上、可能性は無限だ。

["defn", "fib", ["n"],
  ["if", [">", "n", 1],
    ["+",
      ["fib", ["-", "n", 1]],
      ["fib", ["-", "n", 2]]],
    1]]

あらゆるまともな関数プログラミングのデモは、非メモ化再帰フィボナッチの実装のような酷く非効率なデモを伴う。これに例外はない。

["print", ["fib", 8]]
// 34

考察

もう気づいているかもしれないが、僕たちのコードはJSONに準拠している。僕たちは、プリミティブとリストを使っている。つまり実際、僕たちの使用する言語にソースファイルとしてJSONを使うことができる。

なんだって?つまり、JSON内に第一級関数を使った言語を組み込めるっていうのか?そう、できるのだ。

僕たちの使っている言語は、標準ライブラリという点では、現場ではまだ不十分だ。僕たちはデータ構造、ネームスペース、例外、デバッグやマクロについても、あまり考えていなかった。

結論

僕はこのJavascript Lispの実装とREPL、増え続ける一連のネイティブ関数をGithubにまとめている。リファレンスとして自由に使ってほしい。忘れてはならないのは、これはおもちゃ、つまり学習のためのサンドボックスだということだ。決して真に受けるものではないし、間違っても本物のシステムに使うべきではない。非効率で安全でないからだ。

ここに実行中のREPLを映した短いビデオがある。

何よりも、プログラミング言語の実装は、(それがどれほど小規模でおかしくても)実装に使用している言語を学ぶには素晴らしい方法だ。一般的に、言語デザインはかなり目からうろこの体験であり、このことがあなたにとって、シンプルかつパワフルなLispの性質に目覚めるきっかけとなればいいと思っている。

僕は将来的にこの言語をもう一度見直して、マクロ実装のプロセスについて話したいと思う。その後で、この言語のネイティブコードについて可能な限り展開していきたい。

さあ、すぐにエディタを開いて他の言語でもう一度やってみよう。うまくいったらtweetで僕に教えてほしい!

原文:http://danthedev.com/2015/09/09/lisp-in-your-language(2016-2-29)
※元記事の筆者には直接翻訳の許可を頂いて、翻訳・公開しております。

 -Tech, ,

FAworksではプロのコンサルタントが案件をお探しします

  関連記事

【カテゴリ別】海外エンジニアたちに人気の英語Techメディア・Techブログ50選(2016年版)

    日々目まぐるしい速さで変化していくIT業界。特にエンジニアという職種にお

Twitterはどうやって1秒に3,000もの画像を処理しているのか

Twitterはどうやって1秒に3,000もの画像を処理しているのか

現在、Twitter は1秒間あたり3,000枚の画像(約200GB)を作成し持続している。 しかし

エンジニアの作業効率を一気に上げてくれる、無料Google Chrome拡張機能おすすめ20選

ちょっとした時短の積み重ねが作業時間を減らしてくれる 情報収集やブラウザチェック、ルーティーンワーク

webを利用してイケてるガールにデプロイする方法

webを利用してイケてるガールにデプロイする方法

エンジニアに出会いはない。 彼らが業務で関わりを持つのは、チームのメンバーとPCのみ。 そしてそのメ

Crystalの紹介:Cのように速く、Rubyのように滑らか

Crystalの紹介:Cのように速く、Rubyのように滑らか

僕は、Rubyistだ。Rubyと、そのコミュニティ、その生産性など、Rubyにまつわる多くのものが

何が彼女をボットづくりに没頭させるのか?ボットの魅力と可能性/Emma Winston氏インタビュー

ボット初心者の方ですか?私たちは、今度主催するイベント「The Art of Bots」に先駆けて、

100万ppsを受信するプログラムを書くのはどのくらい難しいのか?【翻訳】CloudFlare ブログ

無料枠が充実していることでも人気なコンテンツデリバリネットワーク (CDN) を提供するCloudF

これから必ず伸びる!最低限抑えておきたい技術トレンド3つ(2015年度版)

※この記事は2015年度版です。最新の技術トレンド情報は下記の記事をご覧ください。 『「AIって何?

Node vs. Go : Roadomatic の実装における比較

目次 概要 サーバ運用 ラウンド1: リクエスト処理 UDPソケット リクエストの検証 ラウンド2:

エンジニアとして実力を持って生きていくなら絶対取るべき資格

エンジニアとして何年か生きているのですが、そんな中で「これは受けて良かった! 勉強して良かった!」と