Shoeisha Technology Media

CodeZine(コードジン)

記事種別から探す

JavaScriptでつくるSchemeインタプリタの基礎の基礎

JavaScriptによるSchemeの実装

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2006/12/12 00:00

本稿ではJavaScriptを用いてSchemeのインタプリタを作成します。もともと関数型に近いJavaScriptを使用するため、比較的簡単にSchemeインタプリタを作成することができます。

目次

はじめに

 現存するプログラミング言語の中で2番目に古いのがLispです。生まれは古くても、いまだに使われ続け、また、Rubyなどの新しい言語にも影響を与えています。そのLispの派生であり、シンプルさが売りなのがSchemeです。

 ここではSchemeの簡単なインタプリタをJavaScriptで作ってみます。

対象読者

 本稿はLispやSchemeは少し触ったことはあるけど、インタプリタは書いたことがないという方を読者対象としています。また、JavaScriptの文法や、簡単なデータ構造についての知識を前提とし、説明は省きます。

必要な環境

 テキストエディタと、JavaScriptが動くWebブラウザがあれば十分です。他に特に用意するものはありません。

概要

作成するインタプリタについて

 インタプリタのコードはJavaScriptで書き、HTMLのフォームを使って、Schemeのプログラムの入力および、結果の表示を行います。説明の簡略化のため、マクロ、末尾再帰の最適化、継続などの実装は省きます。また、説明の上では「関数適用」などといった関数型言語独特の言葉はできるだけ避けるようにしています。

Schemeのプログラム

 Schemeではプログラムはリストからなります。Schemeのリストは、

(要素1 要素2 ... 要素n)

 と表されます。これをインタプリタに入力し、実行すると、「要素1を関数」、「要素2~要素nまでを引数」として関数の呼び出しが行われます。つまり数学で、sin(0)と書くものを、Schemeでは(sin 0)と表します。また、'(e1 e2 e3)といったように、頭に引用符を付けてやると、これを「リストそのもの」と見て(e1, e2, e3)というデータとして扱います。

 これでは分かりにくいの実例を出してみます。

Schemeのプログラムの例
(car '(1 2 3))

 これは、 car'(1 2 3) からなるリストです。上記のルールに従うと、「carが関数」、「'(1 2 3)が引数」として扱われます。carは、第1引数のリストの先頭の要素を返す関数であり、'(1 2 3)は、引用符があるので、要素1、2、3からなるリストのデータです。したがって、このプログラムの結果は「1」となります。

 プログラム自身と、データであるリストが同じ書き方であるのは一見ややこしいですが、これこそがSchemeの強みなのです。Schemeは、プログラムとデータを等価に扱えます。データをプログラムとして扱ったり、プログラムを書くプログラムなんてものも書けます。また、C言語やJavaでは書けないような「関数を引数に取る関数」や「関数を返す関数」なども簡単に記述できます。

追記
 Cでも関数を返す関数などは作れるとコメントを頂きました。
 たしかに、関数ポインタを使えば可能ですが、それはあくまでも「あらかじめ作ってある関数へのポインタ」でしかありません。
 Schemeでは動的に新たな関数を作ることが可能です。本稿の最後の方にあるサンプルのクロージャにて例を載せてあります。
 

インタプリタの概要

 Schemeインタプリタの処理は以下の3つの部分から成り立ちます。

  • 入力された文字列をインタプリタの内部形式に変換する処理
  • 内部形式のデータをSchemeのプログラムとして実行する処理
  • プログラムの実行によって得られた結果を表示する処理

 これらの処理を繰り返すことによりSchemeインタプリタは動作します。

オブジェクト

インタプリタが扱うデータ

 本来Schemeは、ベクタや、文字列、複素数といったさまざまなデータを扱えますが、ここでは簡単なインタプリタを作るのが目的なので扱うデータ型は下記のものだけとします。

  • シンボル
  • 数値
  • コンス
  • 関数(後述)

シンボル

 シンボルとは、「hoge」、「foo03」、「car」といった文字の集合です。ただし、同一の名前のものが2回以上作られることはなく、1度作ったシンボルを再利用します。

数値

 数値とは、「0」、「123」、「-456」といった数字の集合です。こちらは同じ数を何度でも生成できます。

コンス

 コンスとは、リストをなすための土台で、CARCDRと呼ばれる2つのポインタを持ったデータです。

コンスは2つのポインタを持っている
コンスは2つのポインタを持っている

 (1 2)というリストは2つのコンスからなり、次のように値が格納されます。

  • 1つ目のコンスのCAR部には数値1のアドレスが、CDR部には2つ目のコンスのアドレスが格納
  • 2つ目のコンスのCAR部には数値2のアドレスが、CDR部にはリストの終端を表すもの(nil)へのアドレスが格納
値の格納1
値の格納1

 同様に、(a (b))というリストは、3つのコンス(X、Y、Zと呼ぶことにします)からなり、次のように値が格納されます。

  • XのCAR部にはシンボルaのアドレス、CDR部にはコンスYのアドレスが格納
  • YのCAR部にはコンスZのアドレス、CDR部にはnilが格納
  • ZのCAR部にはシンボルbのアドレス、CDR部にはnilが格納
値の格納2
値の格納2

 これら3つをSchemeの「オブジェクト」と呼ぶことにします。Schemeではすべてのオブジェクトは等価であり、関数も「ただのオブジェクト」として扱えます。

オブジェクトの準備

 では、上記で説明した3つのオブジェクトを実際に作ってみます。

オブジェクトの定義
var TAG_CONS = 0;
var TAG_SYMBOL = 1;
var TAG_NUM = 2;

function Symbol(str) {
  this.tag = TAG_SYMBOL;
  this.name = str;
}

function Num(val) {
  this.tag = TAG_NUM;
  this.num = val;
}

var nil = /* 後述 */;

function Cons() {
  this.tag = TAG_CONS;
  this.car = nil;
  this.cdr = nil;
}

 これで、hoge = new Cons();などと書くことにより、オブジェクトが生成できます。しかし、シンボルは同一の名前のものを2つ以上作ってはいけないので、工夫が必要です。

シンボルの作成
var symbol_set = new Array();

function CreateSymbol(str) {
  var i;
  for (i=0; i<symbol_set.length; i++) {
    if (symbol_set[i] == str)
      return symbol_set[i];
  }
  symbol_set[i] = new Symbol(str);
  return symbol_set[i];
}

 これにより、(少々強引ですが)同じ名前のシンボルを2回生成しないようになりました。また、nilは「nil」という名前のシンボルとして表すので、変数nilvar nil = CreateSymbol("nil");と初期化します。コンスや数値はnew Cons()などでオブジェクトを作成します。シンボルだけCreateSymbol()で作成する形では統一性がないので、他のオブジェクトも同様に作れるようにします。

オブジェクトの作成
function CreateNum(n) {
  return new Num(n);
}

function CreateCons() {
  return new Cons();
}

 これで一応オブジェクトは完成です。ただし、このままでは直接プロパティにアクセスする必要があります。これが個人的には嫌いなので、操作の多いものはオブジェクトの内容を設定/取得する関数を作っておきます。

Geter/Seter関数
function GetNum(n) {
  return n.num;
}

function CAR(x) {
  if (x == nil)
    return nil;
  return x.car;
}

function CDR(x) {
  if (x == nil)
    return nil;
  return x.cdr;
}

function SetCAR(x, val) {
  x.car = val;
}

function SetCDR(x, val) {
  x.cdr = val;
}

 内容はソースを見れば大体分かってもらえると思います。CARCDRnilを受け取ったときにnilを返すというのはLispの伝統です。nilというのは、実体はシンボルですが、Lisp上の意味としては空のリスト(要素のないリスト)です。リストの終端として使われたり、特別扱いされるので注意してください。

 ちなみに、Schemeではnilはただの変数であり(car nil)(cdr nil)はエラーとなりますが、Lispの伝統にあわせた方が色々と楽なので、こちらにあわせました。

対リストとクォート

 リストは(b1 . b2)(c1 . (c2 . c3))といった書き方ができます。前者は、1つのコンスからなり、CAR部にb1、CDR部にb2が入っています。後者は、2つのコンスからなり、次のように値が格納されます。

  • 1つ目のCAR部にはc1、CDR部には2つ目のコンスのアドレスが格納
  • 2つ目のCAR部にはc2、CDR部にはc3が格納
値の格納3
値の格納3

 このようにドットを用いることにより、CDR部を自分で設定でき、nil以外が終端のリストを作れます。このようなリストを「対リスト」と言います。

 リストをデータとして扱うには、'(d1 d2 d3)と頭に「'」をつけて記述すると最初に説明しましたが、これは、特殊な構文などではありません。実行する前に(quote (d1 d2 d3))に変換されます。quoteは第1引数を「触らず」にそのまま返す関数なので、結果としてリストがそのまま返ります。


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

著者プロフィール

  • zick(zick)

    授業をサボってプログラミング。 そんな駄目大学生。

おすすめ記事

All contents copyright © 2006-2017 Shoeisha Co., Ltd. All rights reserved. ver.1.5