Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
1

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処理系の実装例（シェルスクリプト／テキストファイル版）

Last updated at Posted at 2020-10-14

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

この記事は，下記拙作記事のシェルスクリプト／テキストファイル版を抜粋・修正したものを利用した，原初LISP処理系（"McCarthy's Original Lisp"）の実装例をまとめたものです．

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

処理系の概要

実行例は次の通り．Ubuntu 18.04＋GNU bash 4.4.20にて確認．

$ ./jmclisp "(car (cdr '(10 20 30)))"
20
$ ./jmclisp "((lambda (x) (car (cdr x))) '(abc def ghi))"
def
$ ./jmclisp "((lambda (f x y) (f x (f y '()))) 'cons '10 '20)"
(10 20)
$ ./jmclisp "
> ((lambda (f x y) (f x (f y '())))
>  '(lambda (x y) (cons x (cons y '())))
>  '10 '20)
> "
(10 (20 ()))
$ ./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
#!/bin/bash
#
# JMC Lisp: defined in McCarthy's 1960 paper,
# with S-expression input/output and basic list processing
#


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

cons () {
  local CN=`cat CONSNUM`
  local CONS=$CN.cons
  echo $1 >  $CONS
  echo $2 >> $CONS
  echo $((CN+1)) > CONSNUM
  echo $CONS
}

car () { head -1 $1; }
cdr () { tail -1 $1; }

atom () {
  if [ -e $1 ]; then
    echo "nil"
  else
    echo "t"
  fi
}

eq () {
  if [ `atom $1` = "nil" -o `atom $2` = "nil" ]; then
    echo "nil"
  elif [ $1 = $2 ]; then
    echo "t"
  else
    echo "nil"
  fi
}

rm -f *.cons
echo 0 > CONSNUM


# S-expreesion output: s_display

s_strcons () {
  local sa=`car $1`
  s_display $sa
  local sd=`cdr $1`
  if [ `eq $sd "nil"` = "t" ]; then
    echo -n
  elif [ `atom $sd` = "t" ]; then
    echo -n " . "
    echo -n $sd
  else
    echo -n " "
    echo -n `s_strcons $sd`
  fi
}

s_display () {
  if [ $1 = "nil" ]; then
    echo -n "()"
  elif [ `atom $1` = "t" ]; then
    echo -n $1
  else
    echo -n "("
    echo -n `s_strcons $1`
    echo -n ")"
  fi
}


# S-expression lexical analysis from $1

L="${1//(/ ( }"
L="${L//)/ ) }"
L="${L//\'/ \' }"
L=($L)


# S-expression syntax analysis: s_syn

POS=${#L[@]}
POS=$((POS-1))
echo $POS > SYNPOS

s_quote () {
  local P=`cat SYNPOS`
  local t=${L[$P]}
  if [ $P -ge 0 ]; then
    if [ $t = "'" ]; then
      P=$((P-1))
      echo $P > SYNPOS
      local c=`cons $1 "nil"`
      echo `cons "quote" $c`
    else
      echo $1
    fi
  else
    echo $1
  fi
}

s_syn0 () {
  local P=`cat SYNPOS`
  local t=${L[$P]}
  if [ $t = "(" ]; then
    P=$((P-1))
    echo $P > SYNPOS
    echo $1
  elif [ $t = "." ]; then
    P=$((P-1))
    echo $P > SYNPOS
    local r=`s_syn`
    local a=`car $1`
    local c=`cons $r $a`
    echo `s_syn0 $c`
  else
    local r=`s_syn`
    local c=`cons $r $1`
    echo `s_syn0 $c`
  fi
}

s_syn () {
  local P=`cat SYNPOS`
  local t=${L[$P]}
  P=$((P-1))
  echo $P > SYNPOS
  if [ $t = ")" ]; then
    local r=`s_syn0 "nil"`
    echo `s_quote $r`
  else
    echo `s_quote $t`
  fi
}


# JMC Lisp evaluator: s_eval

caar () { local r=`car $1`; echo `car $r`; }
cadr () { local r=`cdr $1`; echo `car $r`; }
cadar () { local r=`car $1`; echo `cadr $r`; }
caddr () { local r=`cdr $1`; echo `cadr $r`; }
caddar () { local r=`car $1`; echo `caddr $r`; }

s_null () { echo `eq $1 "nil"`; }

s_append () {
  if [ `s_null $1` = "t" ]; then
    echo $2
  else
    local a=`car $1`
    local d=`cdr $1`
    local r=`s_append $d $2`
    echo `cons $a $r`
  fi
}

s_list () {
  local c=`cons $2 "nil"`
  echo `cons $1 $c`
}

s_pair () {
  if [ `s_null $1` = "t" -a `s_null $2` = "t" ]; then
    echo "nil"
  elif [ `atom $1` = "nil" -a `atom $2` = "nil" ]; then
    local a1=`car $1`
    local d1=`cdr $1`
    local a2=`car $2`
    local d2=`cdr $2`
    local r1=`s_list $a1 $a2`
    local r2=`s_pair $d1 $d2`
    echo `cons $r1 $r2`
  else
    echo "nil"
  fi
}

s_assoc () {
  local a2=`car $2`
  local aa2=`car $a2`
  if [ `eq $aa2 $1` = "t" ]; then
    local da2=`cdr $a2`
    local ada2=`car $da2`
    echo $ada2
  else
    local d2=`cdr $2`
    local r=`s_assoc $1 $d2`
    echo $r
  fi
}

s_atom () {
  local a1=`car $1`
  echo `atom $a1`
}

s_lambda () {
  local aa1=`caar $1`
  echo `eq $aa1 "lambda"`
}

s_eval () {
  if   [ `eq $1 "t"` = "t" ]; then
    echo "t"
  elif [ `eq $1 "nil"` = "t" ]; then
    echo "nil"
  elif [ `atom $1` = "t" ]; then
    echo `s_assoc $1 $2`
  elif [ `s_atom $1` = "t" ]; then
    local a1=`car $1`
    if   [ `eq $a1 "quote"` = "t" ]; then
      echo `cadr $1`
    elif [ `eq $a1 "atom"`  = "t" ]; then
      local ad1=`cadr $1`
      local re=`s_eval $ad1 $2`
      echo `atom $re`
    elif [ `eq $a1 "eq"`    = "t" ]; then
      local ad1=`cadr $1`
      local add1=`caddr $1`
      local re1=`s_eval $ad1 $2`
      local re2=`s_eval $add1 $2`
      echo `eq $re1 $re2`
    elif [ `eq $a1 "car"`   = "t" ]; then
      local ad1=`cadr $1`
      local re=`s_eval $ad1 $2`
      echo `car $re`
    elif [ `eq $a1 "cdr"`   = "t" ]; then
      local ad1=`cadr $1`
      local re=`s_eval $ad1 $2`
      echo `cdr $re`
    elif [ `eq $a1 "cons"`  = "t" ]; then
      local ad1=`cadr $1`
      local add1=`caddr $1`
      local re1=`s_eval $ad1 $2`
      local re2=`s_eval $add1 $2`
      echo `cons $re1 $re2`
    elif [ `eq $a1 "cond"`  = "t" ]; then
      local d1=`cdr $1`
      echo `evcon $d1 $2`
    else
      local r=`s_assoc $a1 $2`
      local d1=`cdr $1`
      local c=`cons $r $d1`
      echo `s_eval $c $2`
    fi
  elif [ `s_lambda $1` = "t" ]; then
    local d1=`cdr $1`
    local r1=`evlis $d1 $2`
    local ada1=`cadar $1`
    local r2=`s_pair $ada1 $r1`
    local r3=`s_append $r2 $2`
    local adda1=`caddar $1`
    echo `s_eval $adda1 $r3`
  else
    echo "nil"
  fi
}

evcon () {
  local aa1=`caar $1`
  if [ `s_eval $aa1 $2` == "t" ]; then
    local ada1=`cadar $1`
    echo `s_eval $ada1 $2`
  else
    local d1=`cdr $1`
    echo `evcon $d1 $2`
  fi
}

evlis () {
  if [ `s_null $1` == "t" ]; then
    echo "nil"
  else
    local a1=`car $1`
    local d1=`cdr $1`
    local r1=`s_eval $a1 $2`
    local r2=`evlis  $d1 $2`
    echo `cons $r1 $r2`
  fi
}


# REP (no Loop)

rs=`s_syn`
re=`s_eval $rs "nil"`
s_display $re
echo

##解説

  • リスト処理：cons car cdr eq atom，S式出力：s_display
    先の記事のシェルスクリプト群を関数化して組み込み．コンスセルおよびその連番管理はテキストファイルで実現．

  • S式入力：
    新規に作成．字句解析部は，( ) 'の識別によって，ひとつのS式文字列をbashの配列に置き換え（この配列を使うためにbashを使用．その他の処理は/bin/shでもおそらく可能）．抽象構文木生成部s_synは括弧ネスト・ドット対・クォート記号対応とし，リスト処理関数でコンスセルによる構文木を生成．ただし，再帰処理（や繰り返し処理）の際に大域変数の局所化が起こるため，パース位置をテキストファイルに保存して対応．

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

  • REP (no Loop)
    第1引数として指定したS式文字列について，字句解析→s_syn→s_eval→s_displayを順次実行．

#備考

##記事に関する補足

  • いやあ，自分でやっといてなんだけど，テキストファイル経由とはいえ，まさかシェルスクリプトでLISP処理系が実装できるとは…．ちなみに，愚直にコーディングしていることもあって，処理速度は遅いです．ワンライナー仕様だし，最適化する理由があんまりないのだよなあ．
  • ちなみに，最後の実行例（連想リスト処理）を実行した後のカレントディレクトリの惨状は次の通り．
$ ls
0.cons    17.cons  26.cons  35.cons  44.cons  53.cons  62.cons  71.cons  80.cons  9.cons   99.cons
1.cons    18.cons  27.cons  36.cons  45.cons  54.cons  63.cons  72.cons  81.cons  90.cons  CONSNUM
10.cons   19.cons  28.cons  37.cons  46.cons  55.cons  64.cons  73.cons  82.cons  91.cons  SYNPOS
100.cons  2.cons   29.cons  38.cons  47.cons  56.cons  65.cons  74.cons  83.cons  92.cons  jmclisp
11.cons   20.cons  3.cons   39.cons  48.cons  57.cons  66.cons  75.cons  84.cons  93.cons
12.cons   21.cons  30.cons  4.cons   49.cons  58.cons  67.cons  76.cons  85.cons  94.cons
13.cons   22.cons  31.cons  40.cons  5.cons   59.cons  68.cons  77.cons  86.cons  95.cons
14.cons   23.cons  32.cons  41.cons  50.cons  6.cons   69.cons  78.cons  87.cons  96.cons
15.cons   24.cons  33.cons  42.cons  51.cons  60.cons  7.cons   79.cons  88.cons  97.cons
16.cons   25.cons  34.cons  43.cons  52.cons  61.cons  70.cons  8.cons   89.cons  98.cons

##更新履歴

  • 2020-10-17：『シェルスクリプト／テキストファイル版』に名称変更
  • 2020-10-15：初版公開
1
1
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
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?