Lispと中置記法 数式処理への応用

はじめに

ISLisp規格の処理系であるEasy-ISlispに中置記法を扱うライブラリであるformulaライブラリを整備しました。このライブラリの仕様、使い方についてご紹介するとともに、これを応用した簡単な数式処理システムについてご紹介します。

仕様

Function Description

• (formula x) Translate infix-notation to prefix-notation and eval it
• (infix-prefix x) Translate infix-notation sexp to prefix-notation
• (prefix->infix x) Translate prefix-notation sexp to infix-notation
• (formulas x) Translate infix-notation-string to prefix-notation and eval it
• (string->infix x) Translate infix-notation-strin to infix-notation s-expression
• (infix->string x) Translate infix-notation-S-expression to infix-notation-string
• (/ x y) (quotient x y)
• (^ x y) (expt x y)

応用例 formula

(formula　s) は中置記法で記述されたS式を前置記法に置き換えるマクロです。

Easy-ISLisp Ver2.39
> (import "formula")
T
> (formula 1 + 2)
3
> 

formulaライブラリを使っておなじみ、フィボナッチ関数を書き直してみます。

(import "formula")

;;前置記法
(defun fib (n)
    (cond ((= n 1) 1)
          ((= n 2) 1)
          (t (+ (fib (- n 1)) (fib (- n 2)))) ))

;;中置記法
(defun fib1 (n)
    (cond ((= n 1) 1)
          ((= n 2) 1)
          (t (formula (fib1 (n - 1)) + (fib1 (n - 2)))) ))

formulaはマクロですので、インタプリタでは都度マクロ展開をするので遅くなります。コンパイルするとコンパイル時にマクロ展開されていますので実行速度は同等です。

Easy-ISLisp Ver2.39
> (load "tests/foo.o")
T
> (time (fib 40))
Elapsed Time(second)=5.411361
<undef>
> (time (fib1 40))
Elapsed Time(second)=5.393482
<undef>
> 

Easy-ISLispは型推論器を有しています。前置記法と同様に型推論、型のヒントを与えることで高速化することが可能です。

(defun fib (n)
    (the <fixnum> n)
    (cond ((= n 1) 1)
          ((= n 2) 1)
          (t (+ (fib (- n 1)) (fib (- n 2)))) ))

(defun fib1 (n)
    (the <fixnum> n)
    (cond ((= n 1) 1)
          ((= n 2) 1)
          (t (formula (fib1 (n - 1)) + (fib1 (n - 2)))) ))

Easy-ISLisp Ver2.39
> (load "tests/foo.o")
T
> (time (fib 40))
Elapsed Time(second)=0.159285
<undef>
> (time (fib1 40))
Elapsed Time(second)=0.160431
<undef>
> 

formulaはマクロで実装されています。次のようにinfix->prefix 関数を利用しています。

(defmacro formula (:rest x)
    (infix->prefix x) )

応用例 formulas

中置記法をS式で表現するとアトムの間にスペースを挿入しなければならず、複雑な数式だとなんとも間抜けな感じになります。

> (a * x ^ 2 + b * x + c)

数学の用法に近い次の記述の方が読みやすいです。

a^2+b*x+c

このために文字列を中置記法のS式に変換するタイプのものも用意しました。

Easy-ISLisp Ver2.39
> (let ((a 1)(b 2)(c 3)(x 4)) (formulas "a*x^2+b*x+c"))
27
> 

formulasは文字列を受け取り、string->infix関数により中置記法のS式に変換します。さらにそのS式を前置記法のS式に変換します。マクロで次のように実装しています。

(defmacro formulas (x)
    (infix->prefix (string->infix x)) )

中置記法のS式を文字列に変換する関数も用意してあります。これを使うと前置記法のS式を数学に近い記法で表示する関数は次のように掛けます。

(defun print* (x)
  (format (standard-output) "~A~%" (infix->string (prefix->infix x))))

数式処理への応用

上記のformulaライブラリのマクロ、関数を使いますとMaximaのような普通の数学記法を受け付ける数式処理システムを書くことができます。最小限の微分積分の機能を持たせたMinimaというものを作りました。

Easy-ISLisp Ver2.39
> (load "example/minima.lsp")
T
> (minima)
Simple symbolic formula manipulation
To quit enter 'end'
M> d(x^2,x) 
2*X
M> d(sin(x),x)
COS(X)
M> int(x,x)
X^2/2
M> 1
1
M> 1+2
3
M> end
T
> 

現在ではPython上に優秀な数式処理ライブラリがありますので実用的にはそれらを使えばよいのですが、自分で微積分の公式を導出、証明を与えつつその公式をlispコードとして与えるというのも学習用として意味があるだろうと思います。

実はこのMinimaは私の数学の勉強用です。リーマン幾何学を理解するためにテンソル計算の機能を追加し、理解を深める助けにしたいと思っています。

終わりに

Lispにおける中置記法については昔から多様な方法が提案されてきました。そして、それぞれ一長一短あり決定打には至っていないと思われます。ここに至り私なりにLispにおける中置記法につき納得のいく結論を導きだしたような気がしています。

上記のコード、ライブラリは最新のEasy-ISLisp ver2.39で動作します。コードはGithubに置いてあります。