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

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

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

処理系の概要

実行例は次の通り．Go 1.11.6にて確認．

$ go run jmclisp.go
(car (cdr '(10 20 30)))

20
$ go run jmclisp.go
((lambda (x) (car (cdr x))) '(abc def ghi))

def
$ go run jmclisp.go
((lambda (f x y) (f x (f y '()))) 'cons '10 '20)

(10 20)
$ go run jmclisp.go
((lambda (f x y) (f x (f y '())))
'(lambda (x y) (cons x (cons y '())))
'10 '20)

(10 (20 ()))
$ go run jmclisp.go
((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（偽）＝空リスト＝Go言語自身のnil
エラーチェックなし，モジュール化なし，ガーベジコレクションなし

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

実装例

ソースコード一式

jmclisp.go

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

package main

import (
  "fmt"
  "bufio"
  "os"
  "strings"
)


// basic list processing: cons, car, cdr, eq, atom

type NODE interface{};
type CONS struct { x NODE; y NODE; };

func cons(x NODE, y NODE) NODE {
  var r CONS; r.x = x; r.y = y;
  return NODE(r);
}

func car(s NODE) NODE { return s.(CONS).x; }
func cdr(s NODE) NODE { return s.(CONS).y; }
func eq(s1 NODE, s2 NODE) bool { return s1 == s2; }

func atom(s NODE) bool {
  if (s == nil) {
    return true;
  } else {
    switch s.(type) {
      case string: return true;
      case bool:   return true;
      default:     return false;
    }
  }
}


// S-expression input: s_lex, s_syn

func s_lex(s string) []string {
  for _, k := range "()'" {
    ks := string(k);
    s = strings.Replace(s, ks, " " + ks + " ", -1);
  }
  r := []string{};
  for _, w := range strings.Split(s, " ") {
    if (w != "") { r = append(r, w); }
  }
  return r;
}

func s_syn(s []string, pos *int) NODE {
  t := s[*pos]; *pos = *pos - 1;
  if t == ")" {
    var r NODE = nil;
    for s[*pos] != "(" {
      if s[*pos] == "." {
        *pos = *pos - 1;
        r = cons(s_syn(s, pos), car(r));
      } else {
        r = cons(s_syn(s, pos), r);
      }
    }
    *pos = *pos - 1;
    if *pos != -1 && s[*pos] == "'" {
      *pos = *pos - 1;
      return cons("quote", cons(r, nil));
    } else {
      return r;
    }
  } else {
    if *pos != -1 && s[*pos] == "'" {
      *pos = *pos - 1;
      return cons("quote", cons(t, nil));
    } else {
      return t;
    }
  }
}


// S-expression output: s_display

func s_strcons(s NODE) {
  s_display(car(s));
  sd := cdr(s);
  if sd == nil {
    fmt.Print("");
  } else if atom(sd) {
    fmt.Print(" . ", sd);
  } else {
    fmt.Print(" "); s_strcons(sd);
  }
}

func s_display(s NODE) {
  if s == nil {
    fmt.Print("()");
  } else if atom(s) {
    fmt.Print(s);
  } else {
    fmt.Print("("); s_strcons(s); fmt.Print(")");
  }
}


// JMC Lisp evaluator: s_eval

func caar(x NODE) NODE { return car(car(x)); }
func cadr(x NODE) NODE { return car(cdr(x)); }
func cadar(x NODE) NODE { return car(cdr(car(x))); }
func caddr(x NODE) NODE { return car(cdr(cdr(x))); }
func caddar(x NODE) NODE { return car(cdr(cdr(car(x)))); }

func s_null(x NODE) bool {
  if eq(x, nil) {
    return true;
  } else {
    return false;
  }
}

func s_append(x NODE, y NODE) NODE {
  if s_null(x) {
    return y;
  } else {
    return cons(car(x), s_append(cdr(x), y));
  }
}

func s_list(x NODE, y NODE) NODE { return cons(x, cons(y, nil)); }

func s_pair(x NODE, y NODE) NODE {
  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;
  }
}

func s_assoc(x NODE, y NODE) NODE {
  if s_null(y) {
    return false;
  } else if eq(caar(y), x) {
    return cadar(y);
  } else {
    return s_assoc(x, cdr(y));
  }
}

func s_eval(e NODE, a NODE) NODE {
  if        eq(e, "t") {
    return true;
  } else if eq(e, "nil") {
     return false;
  } 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 atom(s_eval(cadr(e), a));
    } else if eq(car(e), "eq") {
      return 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 {
    fmt.Println("Error"); return nil;
  }
}

func evcon(c NODE, a NODE) NODE {
  r := s_eval(caar(c), a);
  switch r.(type) {
    case string:
      return s_eval(cadar(c), a);
    default:
      if r.(bool) {
        return s_eval(cadar(c), a);
      } else {
        return evcon(cdr(c), a);
      }
  }
}

func evlis(m NODE, a NODE) NODE {
  if s_null(m) {
    return nil;
  } else {
    return cons(s_eval(car(m), a), evlis(cdr(m), a));
  }
}


// REP (no Loop): s_rep

func s_rep(s string) {
  lr_s := s_lex(s); s_len := len(lr_s) - 1;
  rs := s_syn(lr_s, &s_len);
  r := s_eval(rs, nil);
  s_display(r);
  fmt.Println();
}
 
func main() {
  i := bufio.NewScanner(os.Stdin);
  r := "";
  i.Scan();
  for i.Text() != "" {
    r = r + i.Text()
    i.Scan();
  }
  s_rep(r);
}

解説

リスト処理：cons car cdr eq atom
先の記事よりそのまま抜粋．Go言語版については，S式入出力の元記事でも使用しています．
S式字句解析：s_lex，S式抽象構文木生成：s_syn
先の記事から，字句解析部を()および'の識別に変更．抽象構文木生成部については，元記事でもリスト処理関数でコンスセルによる構文木を生成しており，そこに，ドット対とクォート記号に対応するための記述を追加．
S式出力：s_display
S式出力部はs_displayとして新規に作成．処理結果のS式抽象構文木を表示するだけのものとして実装．
評価器：s_eval＋ユーティリティ関数
"McCarthy's Original Lisp"をベースにs_eval関数およびユーティリティ関数を作成．オリジナルおよび他言語実装版との大きな違いは，『0以外のあらゆるデータ』を真として扱うことができないため，条件式から文字列が返ってきたら真とみなすよう，cond本体の処理を調整していること．
REP (no Loop)：s_repおよびmain関数
s_lex→s_syn→s_eval→s_displayをまとめたs_repを定義．プログラム記述やbufio等を用いた入力の場合，二重引用符で囲んだ（LISP記述としての）文字列を複数行に分けて入力・記述することができないため，空行を入力するまで行単位の文字列入力を行い，結合してs_repに渡すよう記述．

備考

記事に関する補足

評価器のみで約100行／2400バイトほど．全体で約240行／4800バイトほどなので，評価器部は半分程度といったところ．Go言語の場合，if文などで中括弧や改行が省略できないところがあるのと，今回はセミコロンをほぼ全て省略せずに記載したため，特に条件分岐が多い評価器で字数を稼いでしまってるという話が．

更新履歴

2020-09-19：初版公開