目次へ

2. 処理系の構成とデータ型


1.1 節で示したように,本処理系は同一ディレクトリに置かれた 実行ファイル L2Lisp.exeライブラリ L2LispLib.dll および Prelude.l などの補助的なファイルから構成される。 インタープリタ機能のほとんどはライブラリにあり, これを利用することで .NET あるいは Mono プログラムに Lisp スクリプティング機能を与えることができる。

$ ls
Copyright.txt           L2Lisp.exe              Prelude.l
Help.txt                L2LispLib.dll           PreludeExtra.dll
$ 
ライブラリ化され,容易に他のプログラムに組込み可能なインタープリタとしては, Tcl/Tk が昔からあるものとして有名です。 Tcl/Tk はライブラリ libtcl, libtk, 組込みの方法を説明するためのサンプル実装を兼ねた実行ファイル tclsh, wish および補助的なファイル群から構成されます。

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)))
L2 Lisp はその最初期から defun 等のごく基本的な部品も組込みにせずに初期化 Lisp スクリプトで定義してきました。 今では (効率上の観点から) progn をはじめからスペシャルフォームとして用意したり, (実用上の観点から) バッククォート式を解釈する機能を用意したりと若干の変更はありますが,基本的な方式は 標準 Pascal によるモダンな Lisp の小さな実装 - 6. いろいろな関数定義とマクロ定義 から変わっていません。

それから Main メソッドは interp.Run を無引数で呼び出して Lisp の対話セッションを開始する,またはコマンド行引数をファイル名と見なしその行ごとの内容を与えて Lisp スクリプトを実行する。

2.2 public クラスとそのソース・ファイル

Interp クラスは,Lisp 組込関数として登録される前述の Car メソッド等を収めた Lib_Funcs.cs と,それ以外を収めた Lib_Interp.cs の2ファイルから構成される。 ライブラリ 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 スクリプトや対話セッションの入力は,1行ごとの文字列の列挙子を作り出す IEnumerable<string> として抽象化され, ReaderRead メソッドで読み取られる。 ReaderInteractiveInput のインスタンスは Interp 内で暗黙裏に構築されるから,前述の Main.cs には出現していないが,もしもそうしたければ Interp とは独立に構築することもできる。

Interp インスタンスが評価し,結果とする Lisp 式の型には object が使われる。 Lisp 独特のデータ型を表すために object の派生クラスとして SymbolCell が定義される。

もちろん,実際には 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.InterpSymbolTable プロパティが持つ)
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);
前述の Interp の Car メソッドの引数と戻り値の型が上記の UnaryFunction と合致することに注意してください。 Interp の LoadNatives メソッドは,リフレクション機能を使って Car メソッドから UnaryFunction インスタンスを生成し,SymbolTable プロパティに Symbol.Of("car") をキーとして格納します。詳しくは後述します。

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
Python による Symbol クラスの実現の場合と異なり, インスタンスの割付けと構築の過程そのものをカスタマイズしてクラス内部にカプセル化できない点は,Python と比較したときの Java と C# の残念なところです。 Ruby は 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>第1要素
        /// </summary>
        public object Car {
            get { return car; }
            set { car = value; }
        }

        /// <summary>第2要素
        /// </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) も同様である。

手もとにある csharp 2.0 specification_sept_2005.doc の第 22 章 Iterators には,コンパイル時に Java 版実装のような従来型のプログラム構造に完全に展開する実装例が示されています。 ただし,この文書は以前は Microsoft の Web ページの分かりやすい場所にあったはずですが,現在は消えている模様です。
今は 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) 処理である。

L2 Lisp 6.0 以降の Ruby 版や Python 版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 のコンストラクションにそれぞれ置き換えられる。

これは Mono 1.9.1 での実行例です。 プレビュー版である Mono 2.0_0 では,二つめの import でエラーが発生する模様です。 .NET Framework 上の IronPython 1.1.1 を使うときは clr.AddReferenceToFileAndPath の引数を完全パスにしてみてください。
$ 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 に適合することを目指した極めて本格的な処理系である。

本処理系の C# ファイルの総行数が約 2500 行なのに対し, IronScheme は約 9 万行です。 1人が片手間に2週間で Python/Ruby スクリプトから移植したものと比べ,土俵が違います…。

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 に限られる。

このように C# 上の他の Lisp 処理系をまとめて調べたのは L2 Lisp を移植した1週間後 >_< ですが,こうしてみると本処理系は最近の技術的流行に乗ったものになっているようです ;-)


目次へ 3.へ


Copyright (c) 2008 OKI Software Co., Ltd.