関数型言語勉強の一環として、比較的簡単なSchemeのインタプリタをいつも使ってるPHPで実装してみることを考えたのですが、参考になる書籍がなかったのでネットで探したところ以下のページを見つけました。
((Pythonで) 書く (Lisp) インタプリタ)
http://www.aoky.net/articles/peter_norvig/lispy.htm
このページのプログラムはPythonで書かれています。PythonとPHPはかなり違う言語なので、なぜかPythonの勉強もしてしまいましたｗ
評価器以外には特に苦労しなかったので、評価器以外を直接見たい場合はこの記事一番下からダウンロードしてください。
■評価器（Evaluator）
評価器は標準入力から入力されたS式（Lisp系言語のプログラムのこと）を読取り器から得るシンボルや定数の列を受け取って解釈しプログラムを実行するものです。
以下具体的に見ていきます。実際のPythonプログラムは上のページを見てください。
評価器は再帰関数になってて、Schemeのスペシャルフォーム（評価器が式の内容全てを評価しない式のこと）の処理と、普通の式を処理するかなり簡単なプログラムです。
が、これをPHPにコンバートするのに苦労しました。以下が自分の書いた評価器プログラムです。
・コンバートしたPHPプログラム
/**
定数、シンボルまたはシンボルの配列を評価する。再帰関数。
@param $symbols 定数、シンボル、またはシンボルの配列
@param $env 環境オブジェクト。指定されない場合はトップレベル環境。
*/
public static function lisp_eval( $symbols, $env = null )
{
// 環境が指定されていないときはトップレベルの環境を指定
if( $env == null ) {
global $global_environment;
$env = $global_environment;
}
// シンボルの場合
if( is_a( $symbols, 'Symbol' ) ) {
return $env->get( $symbols->value );
// 定数の場合
} elseif( is_scalar( $symbols ) ) {
return $symbols;
// 以降リストの場合
} elseif( $symbols[ 0 ]->value == 'quote' ) { // (quote exp)
list( $quote, $exp ) = $symbols;
return $exp;
} elseif( $symbols[ 0 ]->value == 'if' ) { // (if test conseq alt)
list( $if, $test, $conseq, $alt ) = $symbols;
if( self::lisp_eval( $test, $env ) ) {
return self::lisp_eval( $conseq, $env );
} else {
return self::lisp_eval( $alt, $env );
}
} elseif( $symbols[ 0 ]->value == 'define' ) { // (define var (lambda exp))
list( $define, $var, $exp ) = $symbols;
$env->add( $var->value, self::lisp_eval( $exp, $env ) );
} elseif( $symbols[ 0 ]->value == 'lambda' ) { // (lambda vars exp)
list( $lambda, $vars, $exp ) = $symbols;
$str_lambda = '$args = func_get_args();' . "\n";
$str_lambda .= '$env = array_pop( $args );' . "\n";
$str_lambda .= '$vars = unserialize( stripslashes( ' . "'" . addslashes( serialize( $vars ) ) . "'" . ' ) ); ' . "\n";
$str_lambda .= '$exp = unserialize( stripslashes( ' . "'" . addslashes( serialize( $exp ) ) . "'" . ' ) ); ' . "\n";
$str_lambda .= '$new_env = new Environment( &$env );' . "\n";
$str_lambda .= '$new_env->zip( $vars, $args );' . "\n";
$str_lambda .= 'return Evaluator::lisp_eval( $exp, $new_env );' . "\n";
$lambda_function = create_function( '', $str_lambda );
return $lambda_function;
} elseif( $symbols[ 0 ]->value == 'begin' ) { // (begin exps)
each( $symbols );
foreach( $symbols AS $symbol ) {
$val = self::lisp_eval( $symbol->value, $env );
}
return $val;
} else { // 関数評価
$exps = array();
foreach( $symbols AS $symbol ) {
$exps[] = self::lisp_eval( $symbol, $env );
}
$proc = array_shift( $exps );
/*
小細工
関数が使う環境オブジェクトを関数の引数として渡す。
*/
array_push( $exps, $env );
$ret = call_user_func_array( $proc, $exps );
return $ret;
}
}
Pythonの評価器には「S式をリスト構造に直した」リストと、環境オブジェクト（後述）が渡されるようですが、PHPにはリストのように扱える組み込みデータ構造が用意されていません。
この関数のためにいちいちリスト構造を実装するのも面倒なので、配列をリストの代わりにしました。
引数の「$symbols」がその配列です。この配列に対して「each」「array_shift」「list」などを使えば、案外簡単に配列をリストのように扱えます。
・環境オブジェクトのこと
環境オブジェクト（以下環境）はトップレベルやレキシカルな環境を実現するためにあります。評価器に渡される環境オブジェクトには現在自分がいる階層の変数、関数が見えています。
また、環境には1つ外側の環境のポインタを持っていて、「あるシンボルを参照したいときに自分のいる環境に無い場合はひとつ外側の環境を参照する」という再帰メソッドが定義されています。
自分のいる階層の環境には自由に関数やシンボルを登録することができますが、自分より下（よりレキシカルな）環境にはアクセスできません。
・関数定義と環境オブジェクトに関する小細工
評価器にはS式のリストと環境が渡されます。リスト内に関数定義があると、評価する際微妙な問題を起こしました。
Pythonのプログラムは普通にクロージャ内に直接実行時の環境を渡せるのですが、自分が使っているPHP（Ver5.1.4）のクロージャには現在の環境をそのままでは渡せません。
なので、関数実行時に「関数の引数とともに現在の環境を押し込む」というなんともチカラ技なプログラムになってしまいました。
そんな感じなので、クロージャでは「引数のチェック」なんてものはしてませんｗ
こんな感じです。
Pythonのプログラムページに載っている以下のプログラムも「遅い」ですけど、一応動作します。
lis.py> (define area (lambda (r) (* 3.141592653 (* r r))))
lis.py> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))
lis.py> (define first car)
lis.py> (define rest cdr)
lis.py> (define count (lambda (item L) (if L (+ (equal? item (first L)) (count item (rest L))) 0)))
PHPのソース全部は以下からダウンロード可能です。
http://www.tagajo.tv/lisphp_1.0.zip
■使い方
シェルに以下のように入力してください。
$ php -f lisphp.php
