supoo(旧実装)

これまで業務でも趣味でも Lisp をガリガリ書くということはなく、せいぜい Emacs の設定ファイルを書くことにしか使ったことがありませんでした。 構文は非常にシンプルで、「これなら字句解析も構文解析も自分で書けそうだ。C と Lisp の勉強がてらやってみよう！」と思い立って書いたのが「supoo」です。

はい、考えが甘かったです。

lex や yacc を使わずにそれなりに動く実装を目指していたのですが、いつまで経ってもパーサ周りのエラーと例外処理に悩まされ続け、コードも複雑化してしまいました。C99ベースで正規表現ライブラリも使っていません。

なぜ既存の解析器を用いなかったかというと、単に lex や yacc ファイルの読み書きがあんまり出来なかったからというのも理由の一つですです。こちらが王道というのは薄々気付いていたので、過去にも何度も挑戦しましたが、その度に挫折…。これらを使った電卓レベルの入門ページはインターネットにたくさんあるんですが、それなりにプログラミング言語の形をしたものを作りたい場合はしっかりとマニュアルを読んで、実際に使用している他言語の実装を読まないとダメのようだーと思っていました。

streem

そういうのを書いたことも忘れて半年以上経った最近、まつもとゆきひろさんが一昨年の暮れあたりから開発している新プログラミング言語「streem」のコードを Github で見て、lex.l と parse.y と Makefile を眺めているうちに、自分でも書きたくなっていきました。ここ数年の一般的なツールや概念を用いて、何もないところから言語を組み立てていくところを見学することはとても勉強になります。

プログラミング言語を新しく作るところを見たいだけであれば、古い ML やら CVS やら漁れば色々と見れますが、その当時の歴史的な背景まで知っていなければ「なぜそういう実装になったのか」の経緯を本質的に知ることができないような気もしていました。今、リアルタイムで見るからこそ得るものもありそうです。

streem はパイプで連結してちょっとした処理をささっとこなすことができる「より良いシェル(スクリプト)」のようなものを目指しているのかな、と感じました。 パイプで繋げる考えをそのままにシェルスクリプトのようなものを進化させようとした Windows Power Shell を思い出しましたが、方針だけは評価できるものの、実際に出来上がったものは読みにくて書きにくい ガッカリ残念感の哀愁が漂っていたような印象を受けた覚えがあります（※1）。 WPS と比較するのもアレなんですが、”顧客が本当に必要だったもの” は streem の方ですよね！

さて、そんな streem の lex.l と parse.y と Makefile をひっぱってきて、いろいろといじくり回しているうちに大体の記述は分かるようになってきました。まだパースだけで、式木の構築すらやっていないのですが、入れ子になった括弧を処理して、四則演算を行い、印字する程度のことはできました。

lex と yacc (正確にいうと flex と bison)を使ってなかった旧実装でも、関数定義式(defun)や制御式(if等)まで力技で実装していたので、それに比べたらまだまだラクガキレベルです。 ただ、やっぱり先人の知恵である解析器の便利さを実感することができました。

括弧

Clojure や Scheme を含む Lisp 系の言語は、S式を表現する際に括弧 () を多用します。Lisp 界隈のページを見ると、「括弧が書きづらさや読みにくさにつながって、初心者が寄りつかない」という記事をよく目にします。式木を表現したいだけであれば、Python のようにインデントでも可能ですので、そういう動きも以前からあったようです。

• Lisp:S式の理由

上記リンクでは、Scheme の ML のやりとりが紹介されています。自分も最初は、bison で () に加えてインデントによるネストをサポートしてみようかなと一瞬だけ考えましたが、電卓レベルと言えどちゃんと動いてる構文解析にこれから手を加えるのも億劫になるくらいなので、実用的に動いている実装のパーサから手を入れるのに及び腰になるのは理解できました。

ただ、コミュニティうんぬんの話は置いておいても、何十年も使い続けられている Lisp ですので時代ごとにこういう動きがあったと思いますが、未だに括弧を多用する構文が残っているということは、何か本質的な問題点があったのかもしれません。

supoo.rb

さて、そうは言ってもやっている事自体勉強＆趣味なので、車輪の再発明上等でインデントでS式を書けるようにしてみました。

次のようなアプローチです。

1. supoo はまだ電卓レベルなので parse.y を使いません。評価には GNU Common Lisp (clisp) を使います。
2. 仮にちゃんと動いていても、yacc 構文では書きません。オレオレなインデント記法→ Lisp 記法を実現するフィルタとして実装します。

フィルタのスクリプト(supoo.rb)は次のようになりました。

supoo.rb (Gist)

$indent = 2

class Array;
  def nest; self[0] end
  def nest=(val); self[0]=val end
  def value; self[1] end
  def value=(val); self[1]=val end
  def comment; self[2] end
  def comment=(val); self[2]=val end
end

def nestlv(s)
  /^( *)/.match(s).captures.first.size / $indent
end

def exsplit(s)
  s.scan(/("[^"]*")|('[^']*')|([^ ]+)/).flatten.select{|m|m}
end

s = STDIN.read.gsub(/\\\n/, '').split(/\r?\n/).map(&:chomp)
s.map!{|c| [nestlv(c), c.gsub(/ *;.*$/, "").strip, c.gsub(/^.*?( *;.*)?$/, '\1')] }
s.push [0, "()"]

s.each_cons(2) do |c, n|
  if /^\s*$/ =~ c.value
    printf "%s%s\n", c.value, c.comment
    next
  end
  cont = c.nest < n.nest # continue to next line
  if !/^'?(?<p>\((?:[^()]|\g<p>)*\))$/.match(c.value)
    if exsplit(c.value).size > 1 && !cont
      c.value = "(%s)" % c.value
    end
  end
  printf " " * $indent * c.nest
  if cont
    printf("(" * (n.nest - c.nest))
  end
  printf "%s%s", c.value, c.comment
  if c.nest > n.nest
    printf(")" * (c.nest - n.nest))
  end
  printf "\n"
end

中身はただのテキスト・プロセッサーです。要はインデントレベルを検知しながら、必要に応じて ( や ) を突っ込んでいるだけ。

次のように使います。

# 実行
ruby supoo.rb < indended-lisp.supoo | clisp -q -

# 通常の Lisp 構文に変換
ruby supoo.rb < indended-lisp.supoo > general-syntax.lisp

例えば、次のようなインデント記法のスクリプトがあったとします。

indended-lisp.lisp (Gist)

; ookiihou wo kaesu max kansuu
defun ooki (x y)
  if (> x y)
    x
    y

; fibonacchi suu wo kaesu
defun fib (n)
  if (< n 2)
    n
    + (fib (- n 1)) (fib (- n 2))

dotimes (i 5)
  princ (fib i)
  format t " "

setq hoge
  cons 1 'a

print hoge

format t "~%--- TEST ---~%"

setq list '(1 2 3 4 5)
dolist (j list)
  princ j
  format t " "

前置記法は変わらないですが、インデントによるS式のネスティングをしています。 必要以上に改行とインデントを入れなくても良いように、通常の () 構文も使えるようにしています（※2）。

このスクリプトを supoo.rb に食わせると

sample.lisp (Gist)

; ookiihou wo kaesu max kansuu
(defun ooki (x y)
  (if (> x y)
    x
    y))

; fibonacchi suu wo kaesu
(defun fib (n)
  (if (< n 2)
    n
    (+ (fib (- n 1)) (fib (- n 2)))))

(dotimes (i 5)
  (princ (fib i))
  (format t " "))

(setq hoge
  (cons 1 'a))

(print hoge)

(format t "~%--- TEST ---~%")

(setq list '(1 2 3 4 5))
(dolist (j list)
  (princ j)
  (format t " "))

という Common Lisp なコードが印字されます。

clisp で実行すると

$ ruby supoo.rb < indended-lisp.supoo | clisp -q -
0 1 1 2 3
(1 . A)
--- TEST ---
1 2 3 4 5

のように正しく実行することができました。

1. 結局 bash on Windows の提供という選択肢をとる Microsoft も最近では憎めないですが。 

2. リストを各要素1行ずつに分けて書きたくないですよね。