最小化演算子

μx.f(x,y) は y |-> Min{ x | f(x, y) == 0 } の意味．そのようなxが存在しなければ値はボトムとなる（解なし，停止しない）．Schemeでそれっぽいものを実装してみた．
使用例：

gosh> (define-M (sqrt-int (mu x) x2) ; μx を (- (* x x) x2) に作用させた
        (- (* x x) x2))
sqrt-int
gosh> (sqrt-int 9)
3
gosh> (sqrt-int 100)
10
gosh> (sqrt-int 5)
（ボトム，ってか単に帰ってこないのでCTRL-Cをタイプ）
*** ERROR: unhandled signal 2 (SIGINT)
Stack Trace:
_______________________________________

やってる処理は単なるwhileループなのだが，いかに「それっぽく」書くかという話．構文を追加するような，いわゆるメタプログラミングにおいては，LispはOcamlやHaskellよりも一日の長がある．
実装：

(define-syntax define-M
  (syntax-rules ()
    ((define-M (f args ...) e)
     (define-M (f args ...) () e))
    ((define-M (f arg args ...) (reversed ...) e)
     (define-M (f args ...) (arg reversed ...) e))
    ((define-M (f) (reversed ...) e)
     (define-M-aux f (reversed ...) () () e))))

(define-syntax define-M-aux
  (syntax-rules (mu)
    ((define-M-aux f () () (normal ...) e)
     (define (f normal ...) e))
    ((define-M-aux f () (minimized) (normal ...) e)
     (define (f normal ...)
       (let loop ((minimized 0))
         (if (= e 0)
             minimized
             (loop (+ minimized 1))))))
    ((define-M-aux f ((mu arg) args ...) (minimized ...) (normal ...) e)
     (define-M-aux f (args ...) (arg) (normal ...) e))
    ((define-M-aux f (arg args ...) (minimized ...) (normal ...) e)
     (define-M-aux f (args ...) (minimized ...) (arg normal ...) e))))

実装の上でマクロの使用法に関して参考になる議論：

• Scheme:マクロ内でのループ

健全なマクロは使いづらい... Schemeとは独立した，正規順序の謎言語だもんなぁ．