簡易LISP処理系の実装例（Java版）

【他言語版へのリンク記事】[簡易LISP処理系の実装例【各言語版まとめ】](https://qiita.com/ytaki0801/items/dcb0fe48cbeab30ac40d)

この記事は，下記拙作記事のJava版を抜粋・修正したものを利用した，簡易LISP処理系（["McCarthy's Original Lisp"](http://paulgraham.com/lispcode.html)）の実装例をまとめたものです．

* ~~[『括弧文字列』簡易パーサ実装例まとめ](https://qiita.com/ytaki0801/items/b8d7d4c778fe98966ce5)~~（Java版はS式入出力を先行作成しました））
* [リスト処理関数（cons,car,cdr,eq,atom）実装例まとめ](https://qiita.com/ytaki0801/items/a11c8143c5c63a406c7f)

最低限の機能をもったLISP処理系の実装の場合，本体である評価器（eval）実装はとても簡単であり，むしろ，字句・構文解析を行うS式入出力やリスト処理実装の方が開発言語ごとの手間が多く，それが敷居になっている人向けにまとめています．

# 処理系の概要
実行例は次の通り．Java 11.0.8にて確認．

```lisp
$ java jmclisp
(car (cdr '(10 20 30)))

20
$ java jmclisp
((lambda (x) (car (cdr x))) '(abc def ghi))

def
$ java jmclisp
((lambda (f x y) (f x (f y '()))) 'cons '10 '20)

(10 20)
$ java jmclisp
((lambda (f x y) (f x (f y '())))
 '(lambda (x y) (cons x (cons y '())))
 '10 '20)

(10 (20 ()))
$ java jmclisp
((lambda (assoc k v) (assoc k v))
 '(lambda (k v)
    (cond ((eq v '()) nil)
          ((eq (car (car v)) k)
           (car v))
          ('t (assoc k (cdr v)))))
 'Orange
 '((Apple . 120) (Orange . 210) (Lemon . 180)))

(Orange . 210)
```

実装内容は次の通り．

* ["McCarthy's Original Lisp"](http://paulgraham.com/lispcode.html)をベースにした評価器
* 数字を含むアトムは全てシンボルとし，変数の値とする場合は`quote`（`'`）を使用
* 構文として`quote`の他，`cond`と`lambda`が使用可能
* 組込関数：`atom` `eq` `cons` `car` `cdr`（内部でコンスセルを作成）
* 真偽値は`t`（真）および`nil`（偽）＝空リスト＝`"nil"`
* エラーチェックなし，モジュール化なし，ガーベジコレクションなし

"McCarthy's Original Lisp"の詳細については[まとめ記事](https://qiita.com/ytaki0801/items/dcb0fe48cbeab30ac40d)を参照．ダイナミックスコープということもあり，実行例ではlambda式を`letrec`（Scheme）や`labels`（Common Lisp）などの代わりに使用しています．

#実装例

##ソースコード一式

```jmclisp.java
//
// JMC Lisp: defined in McCarthy's 1960 paper,
// with S-expression input/output and basic list processing
//

import java.util.Scanner;


class pair {
  private Object x, y;
  public pair(Object car, Object cdr) {
    x = car; y = cdr;
  }
  public Object car() { return x; }
  public Object cdr() { return y; }
}

public class jmclisp {
  // basic list processing: cons, car, cdr, eq, atom
  private static Object cons(Object s1, Object s2) {
    return new pair(s1, s2);
  }
  private static Object car(Object s) { return ((pair)s).car(); }
  private static Object cdr(Object s) { return ((pair)s).cdr(); }
  private static Boolean eq(Object s1, Object s2) {
    if (s1 instanceof String && s2 instanceof String) {
      return ((String)s1).equals((String)s2);
    } else {
      return false;
    }
  }
  private static Boolean atom(Object s) { return (s instanceof String); }

  // S-expression output: s_string
  private static Object s_strcons(Object s) {
    Object sa_r = s_string(car(s));
    Object sd = cdr(s);
    if (eq(sd, "nil")) { return sa_r; }
    else if (atom(sd)) {
      return (String)sa_r + " . " + (String)sd;
    } else {
      return (String)sa_r + " " + (String)s_strcons(sd);
    }
  }
  private static Object s_string(Object s) {
    if      (eq(s, "nil")) { return "()"; }
    else if (atom(s)) { return s; }
    else { return "(" + (String)s_strcons(s) + ")"; }
  }

  // lexical analysis for S-expression: s_lex
  private static String[] s_lex(String s) {
    return s.replace("(", " ( ")
            .replace(")", " ) ")
            .replace("'", " ' ")
            .trim().split(" +");
  }

  // abstract syntax tree generator: s_syn
  private static int posl;
  private static String[] rl;
  private static Object quote(Object x) {
    if ((posl >= 0) && (rl[posl]).equals("'")) {
      posl = posl - 1;
      return cons("quote", cons(x, "nil"));
    } else {
      return x;
    }
  }
  private static Object s_syn() {
    String t = rl[posl];
    posl = posl - 1;
    if (t.equals(")")) {
      Object r = (Object)"nil";
      while (!((rl[posl]).equals("("))) {
        if ((rl[posl]).equals(".")) {
          posl = posl - 1;
          r = cons(s_syn(), car(r));
        } else {
          r = cons(s_syn(), r);
        }
      }
      posl = posl - 1;
      return quote(r);
    } else {
      return quote((Object)t);
    }
  }


  // JMC Lisp evaluator: s_eval

  private static Object caar(Object x) { return car(car(x)); }
  private static Object cadr(Object x) { return car(cdr(x)); }
  private static Object cadar(Object x) { return car(cdr(car(x))); }
  private static Object caddr(Object x) { return car(cdr(cdr(x))); }
  private static Object caddar(Object x) { return car(cdr(cdr(car(x)))); }

  private static Boolean s_null(Object x) {
    if (eq(x, "nil")) { return true; }
    else { return false; }
  }

  private static Object s_append(Object x, Object y) {
    if (s_null(x)) { return y; }
    else {
      Object r = s_append(cdr(x), y);
      return cons(car(x), r);
    }
  }

  private static Object s_list(Object x, Object y) {
    return cons(x, cons(y, "nil"));
  }

  private static Object s_pair(Object x, Object y) {
    if (s_null(x) && s_null(y)) {
      return "nil";
    } else if (!(atom(x)) && !(atom(y))) {
      return cons(s_list(car(x), car(y)),
                  s_pair(cdr(x), cdr(y)));
    } else {
      return "nil";
    }
  }

  private static Object s_assoc(Object x, Object y) {
    if (s_null(y)) { return "nil"; }
    else if (eq(caar(y), x)) { return cadar(y); }
    else { return s_assoc(x, cdr(y)); }
  }

  private static Object s_atom(Object s) { return atom(s) ? "t" : "nil"; }
  private static Object s_eq(Object s1, Object s2) { return eq(s1, s2) ? "t" : "nil"; }

  private static Object s_eval(Object e, Object a) {
    if      (eq(e, "t"))   { return "t"; }
    else if (eq(e, "nil")) { return "nil"; }
    else if (atom(e)) { return s_assoc(e, a); }
    else if (atom(car(e))) {
      if      (eq(car(e), "quote")) { return cadr(e); }
      else if (eq(car(e), "atom"))  { return s_atom(s_eval(cadr(e),  a)); }
      else if (eq(car(e), "eq"))    { return s_eq(  s_eval(cadr(e),  a),
                                                    s_eval(caddr(e), a)); }
      else if (eq(car(e), "car"))   { return car(   s_eval(cadr(e),  a)); }
      else if (eq(car(e), "cdr"))   { return cdr(   s_eval(cadr(e),  a)); }
      else if (eq(car(e), "cons"))  { return cons(  s_eval(cadr(e),  a),
                                                    s_eval(caddr(e), a)); }
      else if (eq(car(e), "cond"))  { return evcon(cdr(e), a); }
      else { return s_eval(cons(s_assoc(car(e), a), cdr(e)), a); }
    } else if (eq(caar(e), "lambda")) {
      return s_eval(caddar(e),
                  s_append(s_pair(cadar(e), evlis(cdr(e), a)), a));
    } else {
      System.out.println("Error");
      return "nil";
    }
  }

  private static Object evcon(Object c, Object a) {
    if (eq(s_eval(caar(c), a), "t")) { return s_eval(cadar(c), a); }
    else { return evcon(cdr(c), a); }
  }

  private static Object evlis(Object m, Object a) {
    if (s_null(m)) { return "nil"; }
    else { return cons(s_eval(car(m), a), evlis(cdr(m), a)); }
  }


  // REP (no Loop): s_rep
  private static void s_rep(String s) {
    rl = s_lex(s);
    posl = rl.length - 1;
    System.out.println(s_string(s_eval(s_syn(), "nil")));
  }

  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    String s = "", i;
    do {
      i = scan.nextLine();
      s = s + i;
    } while (!(i.equals("")));

    s_rep(s);
  }
}
```

##解説

* リスト処理：`cons` `car` `cdr` `eq` `atom`，S式出力：`s_string`
[先の記事](https://qiita.com/ytaki0801/items/a11c8143c5c63a406c7f)より，ほぼそのまま抜粋．Object型を用いてコンスセルを構成．

* S式入力：`s_lex`および`s_syn`
新規に作成．字句解析部`s_lex`は`()`および`'`の識別でひとつの文字列を配列化，抽象構文木生成部`s_syn`は括弧ネスト・ドット対・クォート記号対応とし，リスト処理関数で構文木を生成．

* 評価器：`s_eval`＋ユーティリティ関数
["McCarthy's Original Lisp"](http://paulgraham.com/lispcode.html)をベースに`s_eval`関数およびユーティリティ関数を作成．

* REP (no Loop)：`s_rep`
`s_lex`→`s_syn`→`s_eval`→`s_string`をまとめた`s_rep`を定義．また，`main`関数で空行を入力するまで複数行を入力してひとつの文字列とし，`s_rep`に渡すよう記述．


#備考

##記事に関する補足
* ~~今のところ，アプレット化の予定なし．~~ワンライナー仕様なので，アプリ化に向いているといえば向いているのだけれども．【追記】アプレット廃止されてたの知らんかった…．

##更新履歴
* 2020-10-07：初版公開