2. 処理系の構成とデータ型
- Web 閲覧用ソース (再掲)
- Copyright.txt
著作権表示: Lisp 関数
(copyright)で表示される。 - Help.txt
概要説明: Lisp 関数
(help)で表示される。 - Lib_AssemblyInfo.cs L2LispLib.dll のアセンブリ情報
- Lib_Funcs.cs L2LispLib.dll の構成要素: 組込関数の実装
- Lib_Interp.cs L2LispLib.dll の構成要素: インタープリタ本体
- Lib_Reader.cs
L2LispLib.dll の構成要素:
(read)の実装 - Lib_Types.cs L2LispLib.dll の構成要素: 様々な型の定義
- Main.cs L2Lisp.exe の構成要素
- Main_AssemblyInfo.cs L2Lisp.exe のアセンブリ情報
- Makefile
Mono 用: .NET Framework では
nmake CSC=cscとして使う。 - Prelude.l
初期化 Lisp スクリプト: Lisp 関数
(prelude)で表示される。 - PreludeExtra.cs 利用者定義の組込関数の例
- Copyright.txt
著作権表示: Lisp 関数
1.1 節で示したように，本処理系は同一ディレクトリに置かれた 実行ファイル L2Lisp.exe，ライブラリ L2LispLib.dll および Prelude.l などの補助的なファイルから構成される。 インタープリタ機能のほとんどはライブラリにあり， これを利用することで .NET あるいは Mono プログラムに Lisp スクリプティング機能を与えることができる。
$ ls Copyright.txt L2Lisp.exe Prelude.l Help.txt L2LispLib.dll PreludeExtra.dll $
2.1 Main メソッド
Tcl/Tk の tclsh, wish と同じく，実行ファイル L2Lisp.exe は，ライブラリ L2LispLib.dll を利用する C# プログラムのサンプル実装を兼ねる。 実行ファイルの実質的なソース・ファイル Main.cs の内容を下記に示す。
using L2Lisp; class L2LispMain { static int Main(string[] args) { Interp interp = new Interp(); interp.LoadNatives(interp); interp.Run(Lines.FromFile(LL.PathTo("Prelude.l"))); if (args.Length == 0) interp.Run(); else foreach (string file_name in args) if (file_name == "-") interp.Run(); else interp.Run(Lines.FromFile(file_name)); return 0; } }
他の L2 Lisp の実装と同じく Interp
クラスのインスタンス interp がインタープリタの本体である。
Main
メソッドの interp.LoadNatives(interp) は，カスタム属性 LispFunction
を持つ公開メソッドを引数 (ここでは interp 自身) から検索し，Lisp
の組込関数として登録する。
例えば Lisp の代表的な組込関数 car は次のようなメソッドとして Interp
に定義されており，この LoadNatives 呼出しによって Lisp から利用可能になる。
[LispFunction("car")]
public static object Car(object list) {
return (list == null) ? null : ((Cell) list).car;
}
LL.PathTo("Prelude.l") は，実行ファイルと同じディレクトリにある初期化 Lisp スクリプト
Prelude.l の絶対パス名を返す。
Main
メソッドは，そのファイルの行ごとの内容 Lines.FromFile(LL.PathTo("Prelude.l")) を
interp.Run に与えて Prelude.l を実行する。
Prelude.l は，defun, let, if などのマクロと
caar, equal などの関数を，スペシャルフォームと組込関数から組み立てて定義する。
下記に Prelude.l の最初の 12 行を示す。
;;; Prelude.l H20.7/17 (鈴) -*- coding: utf-8 -*- (setq defmacro (macro (name args &rest body) `(progn (setq ,name (macro ,args ,@body)) ',name))) (defmacro defun (name args &rest body) `(progn (setq ,name (lambda ,args ,@body)) ',name)) (defun caar (x) (car (car x)))
それから Main メソッドは interp.Run を無引数で呼び出して
Lisp の対話セッションを開始する，またはコマンド行引数をファイル名と見なしその行ごとの内容を与えて
Lisp スクリプトを実行する。
2.2 public クラスとそのソース・ファイル
Interp クラスは，Lisp 組込関数として登録される前述の Car メソッド等を収めた
Lib_Funcs.cs と，それ以外を収めた Lib_Interp.cs の２ファイルから構成される。
ライブラリ L2LispLib.dll
の他のクラスは，Lib_Reader.cs が構文解析器を，Lib_Types.cs が種々の型定義を分担する。
これらのファイルの各クラスは同一アセンブリとして相互に internal なクラスやメンバを参照する。
public クラスの一覧を下記に示す。
$ grep public *.cs | grep 'class\W' Lib_Funcs.cs: public partial class Interp Lib_Interp.cs: public partial class Interp Lib_Reader.cs: public static class Lines Lib_Reader.cs: public class InteractiveInput: IEnumerable<string> Lib_Reader.cs: public class Reader: IDisposable Lib_Reader.cs: public class SyntaxException: Exception Lib_Types.cs: public static class LL Lib_Types.cs: public sealed class LispFunctionAttribute: Attribute Lib_Types.cs: public class EvalException: Exception Lib_Types.cs: public class LispThrowException: EvalException Lib_Types.cs: public sealed class Symbol Lib_Types.cs: public sealed class Cell: IEnumerable<object> Lib_Types.cs: public sealed class Promise $
例外と属性のクラスを除くこれらのクラスの見取り図を下記にスケッチする。 色分けは，そのクラスを定義するソース・ファイルを示す。 赤が Lib_Interp.cs， 緑が Lib_Reader.cs， 青が Lib_Types.cs である。
Lisp スクリプトや対話セッションの入力は，１行ごとの文字列の列挙子を作り出す
IEnumerable<string> として抽象化され，
Reader の Read メソッドで読み取られる。
Reader や InteractiveInput
のインスタンスは Interp 内で暗黙裏に構築されるから，前述の Main.cs
には出現していないが，もしもそうしたければ Interp
とは独立に構築することもできる。
Interp インスタンスが評価し，結果とする Lisp 式の型には object が使われる。
Lisp 独特のデータ型を表すために object の派生クラスとして
Symbol や Cell が定義される。
もちろん，実際には C# のあらゆる型が暗黙のうちに object の派生クラスであり，
そうしたければ Interp インスタンス自身を Lisp 式として扱うこともできる。
そういったクラスやクラス間の関係の厳密な描写は図を著しく煩雑にするから，ここには描いていない。
こまごまとした必要のために多数定義されている internal クラスもすべて省略している。
このクラス図はあくまで処理系の構成を概観するための見取り図である。
2.3 Lisp の型と C# の型
前述の見取り図が示すように，また他の L2 Lisp の実装と同じく，本処理系は Lisp の数や文字列として，処理系を実装する言語 (ここでは C#) の数や文字列をそのまま使う。 シンボルと cons セルについては対応する型がないから，Lib_Types.cs で新しく定義する。 Lisp の nil として C# の null を使う。
| 数 | ⇒ | int (System.Int32),
double (System.Double)
|
| 文字列 | ⇒ | string (System.String)
|
| シンボル | ⇒ | L2Lisp.Symbol
(大域変数値は L2Lisp.Interp の SymbolTable プロパティが持つ)
|
| cons セル | ⇒ | L2Lisp.Cell
|
| nil | ⇒ | null |
| 約束 | ⇒ | L2Lisp.Promise
|
| 組込関数 | ⇒ | L2Lisp.NullaryFunction,
L2Lisp.UnaryFunction,
L2Lisp.BinaryFunction,
L2Lisp.NAryFunction
|
遅延評価の「約束」は，Let Little Lambda Lisp be a Little Lazy - 3.1 約束クラス Promise
(Ruby 版実装) と同じく Promise クラスで表現する。
ただし，具体的なクラス定義は より実用的な L2Lisp.rb 以降の改訂版に準ずる。
組込関数を表す型として Lib_Types.cs で下記のように delegate を宣言する。
/// <summary> 組込みの 0 引数 Lisp 関数の型
/// </summary>
public delegate object NullaryFunction ();
/// <summary> 組込みの 1 引数 Lisp 関数の型
/// </summary>
public delegate object UnaryFunction (object arg);
/// <summary> 組込みの 2 引数 Lisp 関数の型
/// </summary>
public delegate object BinaryFunction (object x, object y);
/// <summary> 組込みの N 引数 Lisp 関数の型
/// </summary>
public delegate object NAryFunction (IList args);
2.4 Symbol クラス
Lisp のシンボルを実装する Symbol クラスの定義を下記に示す。
Java による Symbol クラスの定義と同じく，コンストラクタを隠蔽し，
文字列からシンボルへの表 (ここでは dict) をひそかに使う静的メソッド
Symbol.Of(string name) を公開することによって，同じ名前に対して必ず同じシンボルを得ることを保証する。
/// <summary>Lisp シンボル
/// </summary>
public sealed class Symbol
{
private readonly string name;
private static Dictionary<string, Symbol> dict
= new Dictionary<string, Symbol> ();
private Symbol (string name) {
this.name = name;
}
/// <summary>印字名
/// </summary>
public string Name {
get { return name; }
}
/// <summary>同じ印字名に対し，同じシンボルを返す
/// </summary>
public static Symbol Of(string name) {
lock (dict) {
Symbol s = null;
if (! dict.TryGetValue(name, out s)) {
s = new Symbol (name);
dict[name] = s;
}
return s;
}
}
/// <summary>Lisp のシンボルの文字列表現として，印字名をそのまま返す
/// </summary>
public override string ToString() {
return name;
}
} // Symbol
2.5 Cell クラス
Lisp の cons セルを実装する Cell クラスの主要部分を示す。
Java による Cell クラスの定義と同じく，セルの要素の型は
object つまり System.Object である。
これは，Lisp としてリテラルが用意されている値のほかにも，任意のオブジェクトを格納できることを意味する。
/// <summary>cons セル
/// </summary>
public sealed class Cell: IEnumerable<object>
{
internal object car;
internal object cdr;
/// <summary>Lisp の (cons car cdr) に相当
/// </summary>
public Cell (object car, object cdr) {
this.car = car;
this.cdr = cdr;
}
/// <summary>第１要素
/// </summary>
public object Car {
get { return car; }
set { car = value; }
}
/// <summary>第２要素
/// </summary>
public object Cdr {
get { return cdr; }
set { cdr = value; }
}
/// <summary>非ジェネリック版インタフェース実装
/// </summary>
IEnumerator IEnumerable.GetEnumerator() {
return GetEnumerator();
}
/// <summary>Lisp のリストとして各要素を与える
/// </summary>
public IEnumerator<object> GetEnumerator() {
object j = this;
for (;;) {
Cell jc = j as Cell;
if (jc == null)
break;
yield return jc.car;
j = jc.cdr;
if (j is Promise)
j = ((Promise) j).Deliver();
}
if (j != null)
throw new ProperListExpected (this);
}
…略…
} // Cell
Java 版実装の public Iterator<Object> iterator()
メソッドと異なり，Python 版実装 の __iter__(self)
メソッドと類似して，C# の public IEnumerator<object> GetEnumerator()
メソッドは要素を列挙するためにメソッド本体でループする。
どのメソッドも使われ方は同様であり，for 文または foreach 文で (Lisp のリストとしての)
要素を列挙するときに暗黙裏に呼び出される。
foreach (object x in cell) {
Console.WriteLine(x);
...
}
このとき GetEnumerator()
のメソッド本体は，概念上は，新しいスレッドで実行される。そして yield return
jc.car の地点でサスペンドし，jc.car の値を元のスレッドのループ制御変数 x に引き渡す。
しかし，実装上は，yield return の地点でスタック・フレームの積み上げがないから，
スレッドのようなコストのかかる実行時支援機能を必要とせず，Java の iterator()
のような原始的な方式と同等の効率で実行される。
Python の __iter__(self) も同様である。
今は The C# Language [MSDN] にある C# Language Specification 3.0 (ファイル名 CSharp Language Specification.doc) の第 10.14 節 Iterators に同様の実装例が記述されています。
基本的に GetEnumerator() のメソッド本体は，cdr
で連結されたリストを順にたどるだけだが，その中で下記の処理が異質にみえる。
if (j is Promise)
j = ((Promise) j).Deliver();
これは cdr をたどった先，つまり，リストの残りが遅延評価の約束 (promise) だった場合に，それを評価して結果の値を得る，つまり，約束をかなえる (deliver the promise) 処理である。
Cell クラスも同様です。
L2 Lisp に遅延評価を導入した当初，Ruby による L2 Lisp 4.2
から Java による L2 Lisp 5.0
までは，このような処理のために EagerList というクラスを設けていました。
2.6 IronPython による Cell の操作
独自の型体系の構築ではなく，object を基本とする既存の型体系への追加であるため，
Symbol クラスと Cell クラスは汎用の .NET (または Mono) クラスとして利用できる。
下記は IronPython からCell クラスを使って
Lisp の car, cdr, cons の操作と，リストに対する for
文イテレーションを実行した例である。
car 操作は Car プロパティの参照，
cdr 操作は Cdr プロパティの参照，
cons 操作は Cell のコンストラクションにそれぞれ置き換えられる。
$ ls
l2lisp-8.2/
$ ipy2
IronPython console: IronPython 2.0A5 (2.0.11011.00) on .NET 2.0.50727.42
Copyright (c) Microsoft Corporation. All rights reserved.
>>> import clr
>>> clr.AddReferenceToFileAndPath("l2lisp-8.2/L2LispLib.dll")
>>> from L2Lisp import *
>>> dir()
['BinaryFunction', 'Cell', 'EvalException', 'InteractiveInput', 'Interp', 'LL',
'Lines', 'LispFunctionAttribute', 'LispThrowException', 'NAryFunction', 'Nullary
Function', 'Promise', 'Reader', 'Symbol', 'SyntaxException', 'UnaryFunction', '_
_builtins__', '__doc__', '__name__', 'clr']
>>> x = Cell(1, Cell(2, Cell(3, None)))
>>> x
<L2Lisp.Cell object at 0x000000000000002B [(1 2 3)]>
>>> x.ToString()
'(1 2 3)'
>>> x.Car
1
>>> x.Cdr
<L2Lisp.Cell object at 0x000000000000002C [(2 3)]>
>>> y = Cell("テスト", x.Cdr)
>>> y
<L2Lisp.Cell object at 0x000000000000002D [("テスト" 2 3)]>
>>> y.ToString()
u'("\u30c6\u30b9\u30c8" 2 3)'
>>> for e in y: print e
...
テスト
2
3
>>>
ここで x = Cell(1, Cell(2, Cell(3, None))) としているのは
C# での Cell x = new Cell(1, new Cell(2, new Cell(3, null)))
に相当する。
このようなリスト構築を行うには LL.List を使うとよい。
/// <summary>大域的な定数と関数の置き場
/// </summary>
public static class LL
{
…略…
/// <summary>Lisp の list 関数に相当
/// </summary>
public static Cell List(params object[] args) {
return ListFrom(args);
}
/// <summary>引数の各要素を要素とする Lisp のリストを作る
/// </summary>
public static Cell ListFrom(IEnumerable args) {
if (args == null)
return null;
Cell z = null;
Cell y = null;
foreach (object e in args) {
Cell x = new Cell (e, null);
if (z == null)
z = x;
else
y.cdr = x;
y = x;
}
return z;
}
…略…
} // LL
実行例を示す。
2.7 他の処理系
IronScheme 15332 (2008年 7月)
は cons セルとして public sealed class Cons: ICollection, IEnumerable<object>
を定義する。car 部，cdr 部ともに object 型である。
car 部，cdr 部ともに小文字で始まる名前の public フィールドとして定義される
(つまり，将来，C# の標準的な命名規則に合致する public プロパティにそのまま置き換えられない)
点を除けば，完璧に近い作りである。
IEnumerable<object> に加えて ICollection インタフェースを実装するため，
汎用データ型としての利便性は高い。
ただし，(当然ながら) L2 Lisp と異なり，R5RS §6.4 で言及されている「約束」に対する implicit forcing の機能はない。
実装全体は R6RS に適合することを目指した極めて本格的な処理系である。
L Sharp.NET 1.21 (2006年 1月)
は cons セルとして public class Cons: IEnumerable を定義する。
car 部，cdr 部ともに object 型である。
最終更新は 2006 年 1 月だが C# 2.0 の IEnumerable<object> は実装しない
(一方，IEnumerable<object> は IEnumerable
の派生インタフェースであり，IEnumerable を兼ねる)。
このため，例えば
IList<object> または IList へ変換するために単に
new List<object> (this) とすることができない。
object[] への ad hoc な変換メソッドを用意している。
Car, Cdr はプロパティではなくメソッドとして定義され，若干煩雑である。
IronPython での実行例を示す。
IronPython console: IronPython 2.0A5 (2.0.11011.00) on .NET 2.0.50727.42
Copyright (c) Microsoft Corporation. All rights reserved.
>>> import clr
>>> clr.AddReferenceToFile("LSharp.dll")
>>> from LSharp import *
>>> x = Cons(1, Cons(2, Cons(3, None)))
>>> x
<Cons object at 0x000000000000002B>
>>> x.ToString()
'LSharp.Cons'
>>> x.Car()
1
>>> x.Cdr()
<Cons object at 0x000000000000002C>
>>> x.Cdr().Car()
2
>>> for e in x: print e
...
1
2
3
>>> a = x.ToArray()
>>> a
System.Object[](1, 2, 3)
>>>
DotLisp 0.6 (2003年 7月)
は cons セルとして public class Cons: IEnumerable を定義する。
car 部の型は object だが，cdr 部の型が Cons
であり，任意の点対を表現することができない。
funadoLisp (2003年11月) は言語仕様が非常に小さい Lisp だが，その cons セルの car 部と cdr 部は S 式 (S-expression) インタフェースを実装したものに限られる。
public class Cell
{
public Sexp car; // car part
public Sexp cdr; // cdr part
public Cell()
{
car = (Sexp)Nil.NIL; // initial value is NIL
cdr = (Sexp)Nil.NIL; // initial value is NIL
}
}
public interface Sexp
{
void print() ;
string serialize();
}
public class List : Cell, Sexp
{
/**
* car, cdr が NIL のセルを生成
*/
public List() : base() {} // セルの生成
/**
* Cons
*/
public List(Sexp kar, Sexp kdr) : base()
{
base.car = kar;
base.cdr = kdr;
}
…略…
}
C#ベンチマーク で使われている「lisp インタプリタもどき」(2003年 1月？) も
Cons クラスの car 部と cdr 部は abstract class LispList
に限られる。