中置記法を前置記法に変換するマクロを生成するCommon Lispライブラリを作った

Nextremer Advent Calendar 2017 7日目の記事です。

中置記法を前置記法のS式に変換するマクロを生成する Common Lisp ライブラリを作ったので紹介します。

前置きはいいからリポジトリを見せろと言う方はこちら: https://github.com/carrotflakes/Poler
(英語ですが詳細が書いてあります)

前置き

Lisp といえば前置記法を強要される言語として有名です。
前置記法というのはオペレータ(演算子)を、オペランド(演算される値)の前に書く記法のことで、例えば 1 + 2 * 3 という数式を Lisp で書こうとすると (+ 1 (* 2 3)) と書きます。
この記法、なれない人には読みづらいですよね？

これに問題意識を持つ人は多く、「Lisp 中置記法」などとググれば腐るほど情報がでてきます。
なのでここではオレオレライブラリの紹介だけします。

概要

このライブラリ Poler は、演算子の定義を与えると「中置記法で書かれたS式を前置記法に変換するマクロ」を定義するマクロを提供します。
なんだかわからないと思うので、コードを見ましょう。

(ql:quickload :poler)

;; arithmetic という名前のマクロを定義
(poler:define-poler arithmetic
  (+ :infixl 1)
  (- :infixl 1)
  (* :infixl 2)
  (/ :infixl 2))

;; 上で定義したマクロを使えば、 1 + 2 * 3 という式が中置記法で書ける！
(arithmetic 1 + 2 * 3)
; => 7

;; macroexpand すると、前置記法に変換されているのがわかる
(macroexpand '(arithmetic 1 * 2 / (3 + 4 + 5)))
; => (/ (* 1 2) (+ (+ 3 4) 5))

poler:define-poler マクロに演算子の定義を与えれば、変換するためのマクロが定義されるよ、というノリです。

以下、重要なところだけ説明していきます(ほぼ README の翻訳です)。

演算子の定義

上記のコードでいうと (+ :infixl 1) などが演算子の定義にあたります。
以下のような形式で定義します。

(name type precedence [replace-name | format])

• name は演算子の名前(symbol)
• type は演算子の結合性
• precedence は優先順位、高いほど強く結合する
• [replace-name | format] には replace-name か format をオプショナルで指定することができます。説明は後述

type : 演算子の結合性

演算子には結合性という概念があり、これによって変換のされ方が異なります。
Poler は以下の type をサポートします。

:infixl

左結合中置演算子

(1 + 2 + 3) => (+ (+ 1 2) 3)

:infixr

右結合中置演算子

(1 + 2 + 3) => (+ 1 (+ 2 3))

:infix

Non-associative な中置演算子

(1 + 2 + 3) => (+ 1 2 3)

:prefix-n (n は自然数)

n 個のオペランドを取る前置演算子

; In the case of :prefix-3.
(+ 1 2 3) => (+ 1 2 3)
(+ 1 2)   => Illegal.

:prefix-*

可変個のオペランドを取る前置演算子

(+ 1 2 3) => (+ 1 2 3)
(+ 1 2)   => (+ 1 2)

:postfix

1つのオペランドを取る後置演算子

(1 +) => (+ 1)

replace-name

演算子の名前を変えたいときは replace-name を指定します。

例:

(poler:define-poler arithmetic
  (+ :infixl 1 add)
  (* :infixl 2 mul))

(macroexpand '(arithmetic 1 + 2 * 3)) ; => (add 1 (mul 2 3))

format

普通、Poler は (operator operand1 operand2 ...) の形に変形しますが、任意の形に変形させることも可能です。
format にその形を書いてください。
format の中の $1, $2, ... は operand1, operand2, ... に変換されます。
format の中の $whole は (operand1 operand2 ...) に変換されます。

例:

(poler:define-poler combine-string
  (+ :infix    1 (concatenate 'string . $whole))
  (* :infixl   2 (apply #'concatenate 'string (make-list $2 :initial-element $1))))

(macroexpand '(combine-string "Ha" + " ha" * 3))
; => (CONCATENATE 'STRING "Ha" (APPLY #'CONCATENATE 'STRING (MAKE-LIST 3 :INITIAL-ELEMENT " ha")))

他の機能

Poler には、括弧が入れ子になっているときの挙動を指定するオプションや、演算子にプレフィックスを付けるオプションも備わっています。
もっと知りたい方は README をどうぞ:
https://github.com/carrotflakes/Poler/blob/master/README.markdown#apis

最後に実用的な(?)例を貼っておきます

(defun fact (n)
  (if (< 0 n)
      (* n (fact (1- n)))
      1))

(poler::define-poler arithmetic
  (+   :infix   1)
  (-   :infix   1)
  (*   :infix   2)
  (/   :infix   2)
  (%   :infixl  2 mod)
  (^   :infixr  3 expt)
  (!   :postfix 4 fact))

(arithmetic 3 ! ^ 2 / 3 - 2)
; => 10

あとがき(感想)

• API 設計が綺麗にできたなと思っています。満足。
• 自分自身はこのライブラリを使ってないので需要があるのか謎です。
  • 同僚の Common Lisper からは、「他言語から Common Lisp へのコードの移植の際に数式をS式へ変換するのが楽になるのではないか」という意見をいただきました。
• この記事、Lisp アドカレの方に書きたかったのですが、会社の方のネタがなかったので 株式会社Nextremer 枠となりました。
• メタプログラミングは楽しい。Lisp たのしい！