LoginSignup
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@ytaki0801(Yozo TAKIZAWA)

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

Last updated at Posted at 2020-10-07

【他言語版へのリンク記事】簡易LISP処理系の実装例【各言語版まとめ】

この記事は，下記拙作記事のJava版を抜粋・修正したものを利用した，簡易LISP処理系（"McCarthy's Original Lisp"）の実装例をまとめたものです．

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

処理系の概要

実行例は次の通り．Java 11.0.8にて確認．

$ 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"をベースにした評価器
  • 数字を含むアトムは全てシンボルとし，変数の値とする場合はquote（'）を使用
  • 構文としてquoteの他，condとlambdaが使用可能
  • 組込関数：atom eq cons car cdr（内部でコンスセルを作成）
  • 真偽値はt（真）およびnil（偽）＝空リスト＝"nil"
  • エラーチェックなし，モジュール化なし，ガーベジコレクションなし

"McCarthy's Original Lisp"の詳細についてはまとめ記事を参照．ダイナミックスコープということもあり，実行例では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
    先の記事より，ほぼそのまま抜粋．Object型を用いてコンスセルを構成．

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

  • 評価器：s_eval＋ユーティリティ関数
    "McCarthy's Original Lisp"をベースにs_eval関数およびユーティリティ関数を作成．

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

#備考

##記事に関する補足

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

##更新履歴

  • 2020-10-07：初版公開
1
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?