Java で LISP 的思考を身につけよう - にょきにょきブログ

表題の通り、Java を使って Lisp 的思考を身につけようの巻。
リストの長さを得るとき、list.size() ではなく (length list), リストの中身を足し合わせるには (sum list).

以上のような考え方を身につけるため、Lisp をいきなり使うよりは慣れた開発環境のほうが良かろうということで、Java 上で Lisp 基本5関数を実装し、それらを使って各関数の実装を試みる。

まず Lisp 基本5関数とは。

五つの基本関数とは、
car リストの左値をとり出す。(car[(A . B)] -> A)
cdr リストの右値をとり出す。(cdr[(A . B)] -> B)
cons 二つの値からなるリストを作る。(cons[A;B] -> (A . B))
atom 値がアトムならTを返す。(atom[(A B)] -> nil, atom[nil] -> T)
eq 二つの値が同じ物ならTを返す (eq[A;A] -> T)

他にcond、lambda、defineなど特殊形式（関数ではない）などがある。
以上が最小構成のLISPであり、理論上チューリングマシンと同等の能力（チューリング完全）を持つ。
Wikipedia:純LISP

上記 wikipedia にあるように、car, cdr, cons, atom, eq 関数のことである。これらの関数の意味はwikipediaに任せるとして、Java でこれらの関数を模倣してみよう。

まず大前提となる S 式を表現するためのクラス S と、新規 S 式を生成するメソッド S を実装する。ややこしいが、S( 1,2,3 ) でも S() でも new S() でも S 式を生成すると考えればまぁ妥当だろう。

public class LISP
{
       //新しいS式を生成
       public static S S(Object... objects)
       {
              if( objects == null || objects.length == 0 )
                     return NIL;

              S s = new S();
              for(Object o : objects)
                     s.list.add(o);

              return s;
       }

       //S式を表す。
       public static class S
       {
              private List<Object> list   = new ArrayList<Object>();

              public String toString()
              {
                     if( list.size() == 0 )
                           return "NIL";

                     return list.toString();
              }
       }
}

では上記 S 式に対する基本関数を実装する。

public class LISP
{
       public static final S      NIL    = null;

       public static Object car(S s)
       {
              if(s == null || s.list.size() == 0)
                     return NIL;
              else
                     return s.list.get(0);
       }

       public static S cdr(S s)
       {
              if(s == null || s.list.size() <= 1)
                     return NIL;

              S x = new S();
              x.list = s.list.subList(1, s.list.size());
              return x;
       }

       public static S cons(Object obj1, Object obj2)
       {
              S s = new S();
              s.list.add(obj1);

              if( obj2 == NIL )
                     ;
              else if(atom(obj2))
                     s.list.add(obj2);
              else
                     s.list.addAll(((S)obj2).list);

              return s;
       }

       public static boolean atom(Object obj)
       {
              return !(obj instanceof S);
       }

       public static boolean eq(Object obj1, Object obj2)
       {
              return obj1.equals(obj2);
       }

       ...
}

最後にテストクラスを用意し、LISP クラスを static import する。
これだけで準備OK.

では早速テスト。p関数は単なる System.out.println のエイリアス。

// S 式の生成
p(S()); //-> NIL
p(S(1, 2, 3));       //-> [1, 2, 3]
p(S("abc", "def", "ghi")); //->  [abc, def, ghi]

// ネストした S 式
p(S(S(1, 2), S(3, 4))); //-> [[1, 2], [3, 4]]

S s = S(1, 2, 3, 4, 5);

// car 関数のテスト
p(car(NIL)); //-> NIL
p(car(s)); //-> 1

// cdr 関数のテスト
p(cdr(s)); //-> [2, 3, 4, 5]

// cons 関数のテスト
p(cons(1, 2)); //-> [1, 2]
p(cons(1, S(2, 3))); //-> [1, 2, 3]

// atom 関数のテスト
p(atom(1)); //-> true
p(atom(S(1))); //-> false

// eq 関数のテスト
p(eq(s, s)); //-> true
p(eq(1, 10)); //-> false

うむ基本関数は OK.
ではこの5関数を使って、リストの長さ、合計、指定したインデックスの要素、反転したリストを取得する関数を作ってみよう。
制限は以下の２つ。
・ループは使ってはいけない。
・基本5関数以外の関数(メソッド)を呼び出してはいけない。
この2つの制約を忠実に守って関数を記述すると、随分Lisp脳が鍛えられる。

まず一つ目、リストの長さを取得する関数 length. length 関数は、与えられた S 式が NIL 以外の時に 1 に cdr(s) の長さを足して返してやればよい。

public static int length(S s)
{
      if(s == NIL)
             return 0;

      return 1 + length(cdr(s));
}

p(length(S())); //-> 0
p(length(S(1))); //-> 1
p(length(S(1,2,3))); //-> 3

OK!

次に数値リストの合計を返す sum 関数。考え方は length と同様、 S 式の car に cdr(s) の合計を足して返せば良い。

public static int sum(S s)
{
      if(s == NIL)
             return 0;

      return (Integer)car(s) + sum(cdr(s));
}

p(sum(S()));  //-> 0
p(sum(S(1,2,3))); //-> 6
p(sum(S(-1,-2,3))); //-> 0

OK!

次、リストの指定したインデックスの要素を取得する elementAt 関数。これは、index が 0 の場合は car(s), それ以外は elementAt( cdr(s), --index) する。

public static Object elementAt(S s, int index)
{
      if(s == NIL)
             return NIL;

      if(index == 0)
             return car(s);

      return elementAt(cdr(s), --index);
}


p(elementAt(S("a","b","c"),0)); //-> a
p(elementAt(S("a","b","c"),1)); //-> b
p(elementAt(S(1),-1)); //-> NIL
p(elementAt(S("abc"),100)); //-> NIL

OK!

では最後にリストを反転させる reverse 関数。こいつには補助関数 reverse2 が必要になる。こいつの t に s の先頭の要素から突っ込んでいく関数で、reverse 関数内で要素を突っ込む用のリストを新規に作成している。

public static S reverse(S s)
{
      return reverse2(s, S());
}

private static S reverse2(S s, S t)
{
      if(s == NIL)
             return t;

      return reverse2(cdr(s), cons(car(s), t));
}

p(reverse(S())); //-> NIL
p(reverse(S(1, 2, 3))); //-> [3, 2, 1]
p(reverse(S("abc", "def"))); //-> [def, abc]

OK!

以上で、ループやJavaで用意されているメソッドを使用せず、Lisp 基本5関数のみで length, sum, elementAt, reverse 関数が実装できたことになる。関数を渡すような処理ではなく、S 式のみを引数として受け取るような関数なら大抵は実装できるだろう。Java は関数がファーストクラスオブジェクトではないので関数型言語で使われるような関数( map とか filter とか)を実装するのは困難で、Java の奥義的なテクニックを駆使しなければならない。コード的にも大変美しくないのでそのような処理はスルー。

この基本5関数を利用して関数を作ることで、 Lisp 脳が鍛えられる。使い慣れた言語で、使い慣れた開発環境で Lisp 脳が鍛えられる！なんと素晴らしい！