また、星田さんの記事に対して注釈。
なかなかに苦労している模様。
> 2021/10/25
Scheme入門で再帰。結局特定の文字列を抜かしてリストを返すという問題、模範解答が理解できてなかったのが引っかかっていたので、考え直す。
文字列、じゃなくってシンボル(あるい定数)かな。
まずこの画像が素晴らしい。
分かんなくなったらデバッガに頼る、ってなぁ大正解。
星田さんはセンスがいい。
うぬぬぬ・・・lambda (y) y は分かる。何もせずにそのまま返しておけと。で、lambda (y) (cons h y) のyの部分だけで (cons (h (h (h (h (h と積んでるのを表してる・・って事でオッケイか（まだ再帰が曖昧だ）
実は、紫藤さんは結構ここでははっちゃけた解を書いている。
; 3
(define (remove x ls)
(if (null? ls)
'()
(let ((h (car ls)))
((if (eqv? x h)
(lambda (y) y)
(lambda (y) (cons h y)))(remove x (cdr ls))))))
ホントはこれはScheme初心者に対しては次の解の方が易しい。
(define (remove x ls)
(if (null? ls)
'()
(let ((h (car ls)))
(if (eqv? x h)
(remove x (cdr ls))(cons h (remove x (cdr ls)))))))
ただ、この辺本当は説明が欲しいトコではあるんだけど、かなり重要なテクニックで書かれてはいるのね。
それは「ラムダ式を振り分ける」ってテクニック。
ここだ。
((if (eqv? x h)
(lambda (y) y)(lambda (y) (cons h y)))
なんかカッコが多くね?とか違和感を覚えた貴方は正解。
当然、ここの条件節の返り値は(lambda (y) y)か(lambda (y) (cons h y))って事になる。
つまり、ここで形成される式は最終的には
((lambda (y) y) (remove x (cdr ls)))
ないしは
((lambda (y) (cons h y)) (remove x (cdr ls)))
になる、って事。
「ウソ?こんなんあり得るの?」とか思うでしょ?
あり得るのがSchemeの怖さ、なのだ(笑)。
lambda式が形作る部分が関数になり、リストの第0引数になり、そしてその引数として(remove x (cdr ls))を取ってる。
んで、本当の事を言うと、これはかなり由緒正しいLispでの書き方なんだよな。
今はあんまやらない。何故ならletがあるから。
実は歴史的な事を言うと、Lispにはずーっとletが無かったの(笑)。
だから他の言語みたいに、局所的に変数を定義したい、って場合、紫藤さんが示したような書き方しかなかったわけ(笑)。マジで(笑)。
だから星田さんが、この前日に、
糖衣構文って言葉は覚えてるのでこれはリリカルLISPで糖衣構文の説明の時に出てきたと思われる
ってのは大正解で、紫藤さんのこのページに従うと、件のプログラムは、letを使って
(define (remove x ls)
(if (null? ls)
'()
(let ((h (car ls)))
(let ((y (remove x (cdr ls)))) ;; ここで局所変数yに再帰を束縛
(if (eqv? x h)
y
(cons h y))))))
と書くことも可能だ、と言う事。
lambda式とシンタックスシュガー(構文糖衣)であるletとの対応を見てみよう。
結果「同じ事をやってる」って事が分かるでしょ?
んで、実は紫藤さんのページに書いてある
(let ((p1 v1) (p2 v2) ...) exp1 exp2 ...)⇒
((lambda (p1 p2 ...) exp1 exp2 ...) v1 v2)
ってのが実はletそのものの定義で、Schemeではdefine-syntaxを使って定義出来る、事実上マクロなのです。
(define-syntax my-let
(syntax-rules ()
((_ ((p v) ...) exp ...)
((lambda (p ...) exp ...) v ...))))
つまり、シンタックスシュガー(構文糖衣)はマクロとして定義出来る、と言うか、define-syntaxが構文糖衣を作る為にある、って考えて良いです。
そして星田さんが「✗✗書くのがちょっとメンド臭い」と思った時には自分で構文糖衣を作っちゃって良い、って事です。
さて、ここでちと脱線。
上のロジック(紫藤さんが元々書いたコード)は実はそのままだとANSI Common Lispには活かせない。
(defun my-remove (x ls)
(if (null ls)
'()
(let ((h (car ls)))
((if (eql x h)
(lambda (y) y)
(lambda (y) (cons h y)))
(my-remove x (cdr ls))))))
まず、ANSI Common Lispにはremoveって関数がビルトインで定義されてるので、removeと言う関数名にすると怒られます(笑)。
だから代わりにmy-removeにしときますが、これは上手く動かない。
CL-USER> (my-remove 7 '(9 8 7 7 9 8 11))
; Evaluation aborted on #<SB-INT:COMPILED-PROGRAM-ERROR {1003346233}>.
CL-USER>
何故かと言うと、Schemeの場合は「リストの第0要素はクオートしない限り問答無用に関数として解釈される」と言うルールがあるけど、生憎ANSI Common Lispにはそういうルールがありません。
ANSI Common Lispの場合、
- 何らかが関数として使われる場合、それを関数として呼び出す為にはfuncallと言う関数を使わないとならない。
- たとえlambda式だろうと、「これは関数です」と言う意図としてfunctionと言う特殊形式を伴わないとならない。
つまり、紫藤さんが提示したようなコードはANSI Common Lispだと次のように書かないといけないんです。
(defun my-remove (x ls)
(if (null ls)
'()
(let ((h (car ls)))
(funcall (if (eql x h) ;; ここのリストの第0要素はfuncallになる
#'(lambda (y) y)
#'(lambda (y) (cons h y)))
(my-remove x (cdr ls))))))
ここで、例えば#'(lambda (y) y) ってのは (function (lambda (y) y))の省略記法です。
上のように書けばANSI Common Lispでも同じ結果を得る事が出来る。
CL-USER> (my-remove 7 '(9 8 7 7 9 8 11))
(9 8 9 8 11)
CL-USER>
紫藤さんのSchemeのコードで「あれ?」とか思うのなら、ひょっとしてfuncallをリストの第0要素に置くANSI Common Lispの書き方の方がピンとくるかもしんない。いわば高階関数の書き方ですし。
さて、二つの言語、ANSI Common LispとSchemeで、どうしてここで書き方に違いを生じるのか。実はここがANSI Common LispとSchemeの間で好き嫌いが分かれる、ある意味最大の原因です。
Schemeの場合、リストの第0要素に「何か」を置いた時、それが問答無用に「関数」だと解釈される、って話をしました。
例えば、
> (define a 1)
> (a 3)
. . application: not a procedure;
expected a procedure that can be applied to arguments
given: 1
>
aと言うシンボルを1と定義した場合、(a 3)と3を付けて呼び出せば、aはリストの先頭なので、問答無用に関数だとして評価される。ただし、実はこれは1と束縛されてて、関数じゃないので、実行しようとするとエラーになるわけです。
次のようにset!を使って何らかのテキトーな関数と束縛すれば問題なく動くわけです。
> (set! a (lambda (x) x))
> (a 3)
3
>
この時点で、元々あったaの性質は消えています。何故ならaと言うシンボルは同時に数値と関数と言う性質を持てない。関数になった時点でaは関数なのです。
言い換えると、Schemeには名前空間が一つしかない。要するに変数用の名前空間と関数用の名前空間は共有されてる。
大多数のプログラミング言語は大体こういう仕組みで、これを通称、Lisp以外の言語でもそうなんですが、Lisp-1と呼びます。
Schemeの場合、だからシンボルに複数の属性を持たせる事が不可能なんで、紛れがない。故にリストの第0要素に置かれた時は、「関数なんだろ」と決め打ちが出来るわけです。そうじゃなかったらエラーにするだけですしね。
ところがANSI Common Lispはそうじゃない。なんとコイツは次のような事が出来る。
CL-USER> (defparameter a 1)
CL-USER> (defun a (x) x)
A
CL-USER> a
1
CL-USER> (symbol-function 'a)
#<FUNCTION A>
CL-USER>
分かるかしら?
ANSI Common Lispの場合、aが同時に1を格納した変数であり、なおかつ関数でもあるの。つまりシンボルaは二つの役割を持っている。
言い換えると、ANSI Common Lispでは変数用の名前空間と関数用の名前空間が分かれている。
そしてこんな言語は他にはほぼ存在しません。
こういう「名前空間が変数用と関数用に分かれている」プログラミング言語を、一般に、Lisp以外でもLisp-2と呼びます。
んで、ANSI Common Lispはじゃあ名前空間は2つもあるのか、だからLisp-2なのか、と思うかもしれないけど、さにあらず、最低でもANSI Common Lispが持ってる名前空間はなんと7つはあります(笑)。
つまり、ANSI Common Lispが持ってるシンボルはSchemeのように単純に変数なのか関数なのかは判定が付かない。
従って、「リストの第0要素に置いた」っつってもどういう機能を持たされてるのか確定出来ない。
故に、関数として使いたいのならfunctionあるいは#'(シャープクオートと呼ぶ)を伴わせ、funcallで機能を呼び出す、とプログラマ側が指定しないと何だか良く分かんない事になっちゃうわけです。
さて、PythonもLisp-1なんですね。故に関数用の名前空間と変数用の名前空間は同じです。
だから前書いたように、ビルトインの関数名を変数として使えば再定義されちゃってダメだ、と言う話をした。
ところが、一転して、ANSI Common Lispなら全然O.K.です。なんせ名前空間が分かれてるんで、ビルトイン関数の名前を変数名にしようと構わないわけです。
(defparameter list '(70 89 90 32 35 65 76 21 45 78 22)) ;; List を変数名にする
;; 件の Python コードをANSI Common Lispに翻訳
(loop for k in (loop for n from (1- (length list)) above 0 collect n)
do (loop for j in (loop for m from 0 below k collect m)
when (> (nth j list) (nth (1+ j) list))
do (rotatef (nth j list) (nth (1+ j) list))
(format t "~A~%" list)))
実行した後、listを関数として使っても問題なく動作します。
(70 89 32 90 35 65 76 21 45 78 22)
(70 89 32 35 90 65 76 21 45 78 22)
(70 89 32 35 65 90 76 21 45 78 22)
(70 89 32 35 65 76 90 21 45 78 22)
(70 89 32 35 65 76 21 90 45 78 22)
(70 89 32 35 65 76 21 45 90 78 22)
(70 89 32 35 65 76 21 45 78 90 22)
(70 89 32 35 65 76 21 45 78 22 90)
(70 32 89 35 65 76 21 45 78 22 90)
(70 32 35 89 65 76 21 45 78 22 90)
(70 32 35 65 89 76 21 45 78 22 90)
(70 32 35 65 76 89 21 45 78 22 90)
(70 32 35 65 76 21 89 45 78 22 90)
(70 32 35 65 76 21 45 89 78 22 90)
(70 32 35 65 76 21 45 78 89 22 90)
(70 32 35 65 76 21 45 78 22 89 90)
(32 70 35 65 76 21 45 78 22 89 90)
(32 35 70 65 76 21 45 78 22 89 90)
(32 35 65 70 76 21 45 78 22 89 90)
(32 35 65 70 21 76 45 78 22 89 90)
(32 35 65 70 21 45 76 78 22 89 90)
(32 35 65 70 21 45 76 22 78 89 90)
(32 35 65 21 70 45 76 22 78 89 90)
(32 35 65 21 45 70 76 22 78 89 90)
(32 35 65 21 45 70 22 76 78 89 90)
(32 35 21 65 45 70 22 76 78 89 90)
(32 35 21 45 65 70 22 76 78 89 90)
(32 35 21 45 65 22 70 76 78 89 90)
(32 21 35 45 65 22 70 76 78 89 90)
(32 21 35 45 22 65 70 76 78 89 90)
(21 32 35 45 22 65 70 76 78 89 90)
(21 32 35 22 45 65 70 76 78 89 90)
(21 32 22 35 45 65 70 76 78 89 90)
(21 22 32 35 45 65 70 76 78 89 90)
CL-USER> (list 1 2 3)
(1 2 3)
CL-USER>
まぁこういう大雑把な事はANSI Common Lispだから出来る、って言って良いでしょう。母乳が飛びまくりなので。
フツーのプログラミング言語ではこういうのは通常は許されません。
なお、ANSI Common Lispでも実装によっては警告を出したり、パッケージ・ロックをかけて、解除しないと実行してくれない処理系もあります。
(CLISPは素直に「仕様通り」実行してくれます)。
あとはもう全然Perfectです。
特に「自分で問題改変して」解くとか素晴らしいですね。
こ、これが末尾再帰（多分）！
うん、全部キチンと末尾再帰になってます。
再帰で「今書いてる関数」だけを直接呼び出してれば末尾再帰なんで大丈夫ですよ。
> 2021/10/26
(- n 1)が二箇所にあるのはちょっとダサめだけど。
うん、実は(- n 1)が二箇所にあるのがダサいかどうか、ってのは関係がなくって。
ここで星田さんが書いたようにすると、実質そのまま(- n 1)が二回計算されてしまうのです。
この時代、CPUも速いんで大した差はこのケースだと生まないんですが、紫藤さんがやってるように(- n 1)を一旦mに束縛すれば計算は一回で済んで、あとはその計算結果を参照すれば済みます。
前書いたけど、手続き型言語だと
a = foo()b = bar(a)c = baz(b)
みたいにバカの一つ覚えみたいにして、1回しか計算しないのに、何でも変数に束縛してみっともない、って話は書きました。関数型言語なら
baz(bar(foo))
みたいにヘーキで書くのになぁ、と。
ただ、このケースのように、「同じ計算が二回以上行われる」のなら変数に束縛する意味があります。計算量を減らすため、ですね。
逆に言うと、関数型言語の場合、変数に束縛するのに「同じ計算を行わせない」と言う確固とした理由が一つある、と言う事です。
プログラム内で同じ何かを参照して同じ計算を行ってる場合は要注意です。その時には変数で束縛する価値があります。
「変数の参照は計算より速い」と言うのがその理由です。
> ぬぅ・・第一引数のnが-1されてるから共用されるのかと思ったら独立してるんですねぇ（関数言語だから？）。
あ〜〜。
星田さん、発想がいいなぁ。
凄いトコに目をつけてる。
うん。
ええと、そういう現象っつーか機構を前方参照とか前方照応って言うんですけど。ある値を確定する時にその前の値を参照して決める、って言うのをね。
でもプログラミング言語は通常、引数ではそういう前方参照とか前方照応ってのは許されてません。関数型言語か否かに関わらず。
っつーかそういう風には普通設計しないのです。
何故か?それはそういう設計だと引数が破壊的に変更されるのを許容するからです。
(facti (- n 1) (* n p))
↑このnが前方参照で1減ってたとしたらn自体が書き換えられた事を意味する
このケースだけ、ならいいけど、仮に関数本体でnを参照しなきゃいけない場合。破壊的変更される前の値が欲しいのか後の値が欲しいのか?
ちょっとこれはヤバいんですよ。どこで計算ロジックがおかしくなるか分からなくなる。バグるのが目に見えてますよね。
ただ、このケースの場合、一応「自由度が高い」Schemeだとこういう書き方は出来るちゃ出来ますが。
(define (facti n p)
(if (= n 1)
p
(facti (begin (set! n (- n 1)) n) (* n p))))
↑ここでnを破壊的変更し、ついでにそのnを返す
ただまぁ、コードが長くなるし、あまりメリットはないですよねぇ。
「やれるよ」ってだけです。
ちなみに、2世代前のR5RSだと実はSchemeでは引数の評価順序が規定されてなかったんで、つまり、引数が左から順番に評価されるのか右から順番に評価されるのか、は決まってませんでした。
従って、上のコードは、仮に「右から評価する」処理系だったら上手く動かない、と言う事になります・・・あれ、現行のR7RSだったらどうだっただろ(笑)。
まぁ、もっとも、既にRacketはR7RSには関係ないですけどね(Scheme方言だから)。
