#:g1: Stanford MacLISP: utilの紹介

Posted 2014-11-23 15:00:00 GMT

(LISP Library 365参加エントリ)

 LISP Library 365 の328日目です。

Stanford MacLISP: utilとはなにか

 Stanford MacLISP: utilは、Stanford大学のMacLISPのユーティリティです。恐らく作者は、Richard Gabriel氏だと思われます。

パッケージ情報

パッケージ名Stanford MacLISP: util
参考サイトUTIL.2[AID,LSP]-www.SailDart.org

インストール方法

 上記サイトからダウンロードして適当に動かします。

 Common Lispに移植してみたものがありますので良かったらどうぞ(動作確認できれば良いという程度の移植です)

試してみる

 日付は、1981-04-22なのでMacLISPにしては案外新しいようですが、上記のサイトのソースを眺めてもらうと分かるように、なんだか分からないLisp方言となっています。
異様な見た目の原因は、Richard Gabriel氏が使っていた俺構文なのですが、MacLISPにInterlisp的な構文を取り入れつつASCII以外の文字も使っていることに起因するようです。
例えばletはこう書きます。

(let x ← 42 do
  x)
;=>  42

 またパタンマッチを多用しているのも特徴でマクロもパタンマッチで書けるmatch-macroというものが沢山使われています。
match-macroの大まかな説明をすると、構文要素をパタン変数にマッチさせて、パタン変数以外をクォートするcodeという構文で包んだコードと合体させるという方式になっています。下記のifでは、

(match-macro (if) (*form1 then *form2)
  (cond ((%match '(*form2 else *form3) *form2)
         (code (cond (*form1 *form2)
                     (t *form3))))
        (t (code (cond (*form1 *form2))))))

(let *form1 ← '(pred) do (let *form2 ← '(con) do (let *form3 ← '(alt) do (CONS 'COND (CONS (APPEND *FORM1 (APPEND *FORM2 NIL)) (CONS (CONS 'T (APPEND *FORM3 NIL)) NIL)))))) ;=> (COND (PRED CON) (T ALT))

(let *form1 ← '(pred) do (let *form2 ← '(con) do (CONS 'COND (CONS (APPEND *FORM1 (APPEND *FORM2 NIL)) NIL)))) ;=> (COND (PRED CON))

マッチ具合によって展開が変わります。

 このmatch-macroで使われている%matchですが、ガードが使えるのが1980年当時としてはなかなか先進的な気がします。

(multiple-value-bind (?x *xs ?y) nil
  (%match '(?x *xs) '(1 2 3 4))
  (list ?x *xs))
;=>  (1 (2 3 4))

(multiple-value-bind (?x *xs ?y) nil (%match '(?x *xs ($r ?y evenp)) '(1 2 3 4)) (list ?x *xs ?y)) ;=> (1 (2 3) 4)

(multiple-value-bind (?x *xs ?y) nil (%match '(?x *xs ($r ?y oddp)) '(1 2 3 4)) (list ?x *xs ?y)) ;=> (NIL NIL NIL)

ということで種類ごとに適当に眺めてみます。

制御構文

 ifはthenとelseをキーワードを使います。

(if (zerop (random 2)) then 42 else 32)
;=>  42

 その他、Interlispのselectに影響を受けたselect、select=、select-matchがあります。

(select "foo"
  ("bar" "bar")
  ("foo" "foo")
  "baz")
;=>  "foo"

(select= 42 (42 "bar") (97 "foo") "else") ;=> "bar"

(let ?x ← nil do (let ?y ← nil do (let ?z ← nil do (select-match '(1 2 3) ((?x ?y ?z) (list ?x ?y ?z)) "else")))) ;=> (1 2 3)

繰り返し

 繰り返し構文も大体定番な感じですが、キーワードのdoが特徴的です。単純な繰り返しのrepeat/while/untilの他にInterlispのforに影響を受けた汎用的なforがあります。for x in xsをfor x ∈ xsと書けます。

(repeat 10 do (princ "."))
;>>  ..........
;=>  NIL
              

(until (zerop (random 3)) do (print "foo") return (print "1") (print "2") 10) ;>> ;>> "foo" ;>> "foo" ;>> "foo" ;>> "foo" ;>> "foo" ;>> "1" ;>> "2" ;=> 10 (while (zerop (random 3)) do (print 'foo))

;>> ;>> FOO ;>> FOO ;=> NIL

(let list ← '(1 2 3 4) do (for x ∈ list collect (list x))) ;=> ((1) (2) (3) (4))

(for x from 1 to 5 by 2 do (print x)) ;==> (DO ((X 1 (+ X 2))) ((< 5 X)) (PRINT X)) ;>> ;>> 1 ;>> 3 ;>> 5 ;=> NIL

(for x ∈ '(1 2 3 4) select (oddp x)) ;==> (MAPCAN (LAMBDA (X) (AND (PROGN (ODDP X)) (LIST X))) '(1 2 3 4)) ;=> (1 3)

(for x ∈ '(1 2 3 4) scan (print x)) ;>> ;>> 1 ;>> 2 ;>> 3 ;>> 4 ;=> NIL

(for x ∈ '(1 2 3 4) do (print x)) ;>> ;>> 1 ;>> 2 ;>> 3 ;>> 4 ;=> (1 2 3 4)

末尾再帰を最適化するdefun

 Clojureのloop/recurと似た感じですが、式を分析してgotoに変換します。
Clojureのrecurに相当するのは、tail-recurキーワードです。
実行していることは、Let Over Lambdaのnamed-letとほぼ同じですが、1980年に既にあったというのは面白いですね。

(tail-recursive-defun fib (n a1 a2)
  (cond ((zerop n) a2)
        ((= 1 n) a1)
        (t (tail-recur (1- n) (+ a1 a2) a1))))

(fib 100 1 0) ;=> 354224848179261915075

まとめ

 今回は、Stanford MacLISP: utilを紹介してみました。
現状はコードの断片が残っているのみで、使い方の説明も構文の使われ方の説明もないので、基本的にさっぱり分かりませんが、コードは大体復元して動かして確認してみたので上記の説明で大体合ってるんじゃないかなと思います。

comments powered by Disqus