Common Lisp に中置記法を入れようとしたら C 言語もどきになった

ストーリー

あるデータ構造を、 Common Lisp で実装しようと思い立ちました。そのデータ構造には、既に C 言語での実装があったので、「まあ元々の論文を読むのは面倒だし、とりあえずアルゴリズムをコピペするか」と思っていました。

そこで私は思ったのです: Common Lisp の配列参照は面倒すぎる!

例えば、以下の C の式を考えます:

x[i] = y[ z[i + 1] + 1 ] - 1;

これが、 Common Lisp だと:

(setf (aref x i)
      (1- (aref y (1+ (aref z (1+ i))))))

Common Lisp 版は、なんだかよく分からない気がします。配列参照についてくらい、DSL的な感じで C 言語の構文を取り入れられないかしら、と思ったのです。

というわけで何かいろいろやっていたら・・配列参照以外も、結構な C の構文が食えるようになってしまいました。

書いたもの: with-c-syntax マクロ

Hello, World!

(with-c-syntax ()
{
   print \( "Hello, World!" \) \;
})

with-c-syntax とつけて括弧で囲めば、その中では C 言語的な構文が使い放題。そんなマクロです。
( ) ; という文字は、 Lisp では特殊な意味があるのでエスケープを付けています。

値を返してみる

(defun test-add-args (x y)
  (with-c-syntax ()
    {
    return x + y \;
    })
  )

(test-add-args 1 2) ; => 3

lexical に見えている変数なら、そのまま参照することが出来ます。

for ループで、 1 から 100 まで足そう

(defun test-for-loop ()
  (let ((i 0) (sum 0))
    (with-c-syntax ()
      {
      for \( i = 0 \; i < 100 \; ++ i \)
         sum += i \;
      })
    sum))

(test-for-loop) ; => 5050

for ループ, 代入演算子 (= と +=), 二項演算 (<), インクリメントも使えます。

ループを break したり continue したり Lisp 式を混ぜたり

;; 50 未満の偶数の和を取る
(defun test-loop-continue-break ()
  (with-c-syntax ((i 0) (sum 0))
   {
    for \( i = 0 \; i < 100 \; ++ i \) {
      if \( (oddp i) \) ; Lisp 関数 oddp
        continue \;
      if \( i == 50 \)
        break \;
      sum += i \;
      (format t "i ~A, sum ~A~%" i sum) \; ; Lisp 関数 format
    }
   return sum \;
   }))

(test-loop-continue-break) ; => 600

C 系言語でお馴染みの continue, break は、みなさんご存知の挙動をします。
Lisp 式を混ぜ込むことも可能です。括弧をエスケープしなければ、 Lisp の括弧として解釈されます。

switch-case しよう

(defun test-switch ()
  (flet ((fun (x)
           (with-c-syntax ((x x))
    {
      format \( t \, "[~A] " \, x \) \;
      switch \( x \) {
      case 1 \:
        (format t "case 1~%") \;
        break \;
      case 2 \:
        (format t "case 2~%") \;
        (format t "fall-though 2->3~%") \;
      case 3 \:
        (format t "case 3~%") \;
        break \;
      case 4 \:
        (format t "case 4~%") \;
        break \;
      default \:
        (format t "default~%") \;
      }
    })))
    (loop for i from 0 to 5
       do (fun i))))

(test-switch)
;; 以下のように印字される
#|
[0] default
[1] case 1
[2] case 2
fall-though 2->3
case 3
[3] case 3
[4] case 4
[5] default
|#

switch - case もそのままに。 switch 文で break を忘れると fall through しちゃうのもそのまま再現!!

goto 無双

(defun test-goto ()
  (with-c-syntax ()
    {
      goto d \;
    a \:
      princ \( "a" \) \;
    b \:
      princ \( "b" \) \;
      goto e \;
    c \:
      princ \( "c" \) \;
      return \;
    d \:
      princ \( "d" \) \;
      goto a \;  
    e \:
      princ \( "e" \) \;
      goto c \;
    })
  )

(test-goto)
;; 以下のように印字される
#|
dabec
|#

Common Lisp においても、 goto はとても重要な制御構文です。

Duff's Device

(defun test-duff-device (to-seq from-seq cnt)
  (with-c-syntax ((to-seq to-seq) (from-seq from-seq) (cnt cnt)
                  to from n)
    {
    to = & to-seq \;          ; produces a pointer
    from = & from-seq \;      ; (same as above)

    n = \( cnt + 7 \) / 8 \;
    n = floor \( n \) \;                ; CL:/ produces rational. cast it.
    switch \( cnt % 8 \) {
    case 0 \:   do {    * to ++ = * from ++ \;
    case 7 \:       * to ++ = * from ++ \;
    case 6 \:       * to ++ = * from ++ \;
    case 5 \:       * to ++ = * from ++ \;
    case 4 \:       * to ++ = * from ++ \;
    case 3 \:       * to ++ = * from ++ \;
    case 2 \:       * to ++ = * from ++ \;
    case 1 \:       * to ++ = * from ++ \;
      } while \( -- n > 0 \) \;
    }
    })
  to-seq)

#| 
実行例

CL-USER> (setf arr1 (make-array 20 :initial-element 1))
#(1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)
CL-USER> (setf arr2 (make-array 20 :initial-element 2))
#(2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2)
CL-USER> (test-duff-device arr1 arr2 10)
#(2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1)
CL-USER> arr1
#(2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1)

こんな とんでもなく曲がりくねった コードだって使えてしまいます。

現在の実装の進捗

式 (Expression) と、文 (statement) は、ほぼ何でも処理できます。未対応なのは、 sizeof と, キャスト演算だけです。

一方、宣言 (declaration) は一切使えません。そのため、 with-c-syntax 内部で変数を作れないという重大な制限があります。これは直します。

また、 Lisp リーダが独自の解釈をする文字にはエスケープが必要だったり、くっついてしまう文字には空白を入れて離す必要があったりします。これは適切なリーダーマクロを用意することによって解決できる予定です。

コード

コードはこちら

蛇足: 実装詳細

大枠

1. C の BNF を拾う
2. cl-yacc に掛けて、パーザを作る。
3. パーザを使い、 C 言語的シンボル列を Lisp 式に変換して吐かせる。
4. マクロでユーザの渡した式を受けとれるようにする。

以下、変換例とともに、実装を解説します。

式 (expression) の変換

単純な式

単項演算子や二項演算子について、その文法の読みかえをすることが大部分の仕事です。
そしてこれは、 cl-yacc にちょっとアクションを仕込むだけで終わりです。

以下のような感じです:

x + y     // -> (+ x y)
x < y     // -> (< x y)
x || y    // -> (or x y)   ;; CL:or も短絡的なのでそのまま使用

x ? y : z // -> (if x y z) ;; CL:if をそのまま使用

!x        // -> (not x)

x[y]      // -> (aref x y) 
x(y)      // -> (x y)      ;; x を関数だと思って呼び出し
x.y       // -> (y x)      ;; y を構造体の reader function と思って呼び出し

代入演算子, インクリメント, デクリメント

これらは、 代入先は setf 可能な場所である と決め打ちして、 setf に展開しています。

x = 2     // -> (setf x 2)
x++       // -> (incf x)

+= などは、 let で中間結果をバインドするように展開します:

x += 2    // -> (LET ((#:G1016 X)) (SETF X (+ #:G1016 2)))

これについては、 define-modify-macro を使って、もっと実装上の記述を簡単にする手段はありそうです。

インクリメントとデクリメントには、それぞれ incf, decf を使用しています。
しかしいわゆる post-increment は、 let を使用する形で展開しています。

++x       // -> (incf x)
x++       // ->  (LET ((#:G1017 X)) (SETF X (+ #:G1017 1))

ポインタ

私の知るかぎり、 Common Lisp には、任意の場所を指すことが出来て、しかも整数型を同じような演算が出来るような型がありません。

仕方がないので、 pseudo-pointer なるものを自作しています。
詳細は、稿を改めて書く予定です。

キャスト, sizeof

これらは、現在は実装できていません。

キャストの実装には、 C 言語の宣言の構文を解釈し、対応する型を引き出す必要があります。
sizeof の実装には、さらにそれらが占めるメモリ領域を知る必要があります。

宣言の構文を解釈することが出来れば、キャストは実装できるでしょう。
しかし、 sizeof は面倒そうです。

文 (statement) の変換

goto

いきなり goto からです。これをサポートすることが、この実装の大枠に影響しています。

Common Lisp で goto といえば、 tagbody と go であり、今回の実装もそれを使っています。
tagbody では、 lexical に見えている go tag に go して飛ぶことが出来ます。

さて、 C 言語の goto ラベルは、恐るべきことに関数全体にスコープがあります。そのため、 goto は複文の中でもどこにでも飛べなければなりません。つまりこれを tagbody で実装するには、全ての複文をフラットに展開して、 go tag が tagbody から見えるようにする必要があるのです! これが、この後の全てに影響しています。

例:

(with-c-syntax ()
  {
    goto d \;

  a \:
    princ \( "a" \) \;

  b \:
    princ \( "b" \) \;
    goto e \;

  c \:
    princ \( "c" \) \;
    return \;

  d \:
    princ \( "d" \) \;
    goto a \;  

  e \:
    princ \( "e" \) \;
    goto c \;
  })

展開結果では、暗黙的な tagbody を含む prog を使っています。

(PROG ()
   (GO D)
  A
   (PRINC "a")
  B
   (PRINC "b")
   (GO E)
  C
   (PRINC "c")
   (RETURN (VALUES))
  D
   (PRINC "d")
   (GO A)
  E
   (PRINC "e")
   (GO C))

if

if は、そのまま Common Lisp の if にすればいいかと思われますが、 if の節の中に goto ラベルが含まれていることが考えられるため、 tagbody を使う形に展開されます。
then 節 と else 節のそれぞれについて gensym で go tag を付け、冒頭でそこへの go をします。

例:

(with-c-syntax ()
  {
  if \( x \) {
    1 + 2 \;
  } else {
    2 + 4 \;
  }
  })

展開結果:

(PROG ()
  (IF X
      (GO #:|(if then)1053|)
      (GO #:|(if else)1054|))
 #:|(if then)1053|
  (+ 1 2)
  (GO #:|(if end)1055|)
 #:|(if else)1054|
  (+ 2 4)
  (GO #:|(if end)1055|)
 #:|(if end)1055|))))

ループ構文

ループも tagbody を使う形に展開します。以下の場所に飛ぶ可能性があるので、 go tag を仕込んで展開します:

• ループの条件節 (ループの本体から、もしくは while, for ループの初回と、 continue)
• ループの本体 (ループの条件節から、もしくは do-while の初回)
• ループの出口 (ループの条件節から、もしくは break)

(展開結果は、長いので略)

switch と case

こんな感じです:

• case や default を見つけたら、 go tag を gensym する。それをスペシャル変数に貯めておく。
• switch を見つけたら、値を計算して go するジャンプテーブルを作る。
• break での飛び先を gensym して展開する。

(展開結果は、長いので略)

return

これには、 Common Lisp の return をそのまま使っています。展開された構文全体を、名前が nil の block で囲うことで、 return で脱出できます。

ここでは、 tagbody と 名前が nil の block で囲うことの両方の機能を持つ prog を使っています。

例:

  (with-c-syntax ()
    {
    return 1 + 2 \;
    })

展開結果:

(PROG () (RETURN (+ 1 2)))