LISP事始め
- Emacs LISPもちょっとやってみた。『素数夜曲』と合っていないこともあり、超難航!
- Racket, Scheme R5RSでやることに変更(前の記事)
- Lisp Cabinetというのが比較的簡単な環境のようなのでダウンロードすることにする(こちらがダウンロードサイト)。ひたすらOKするだけ
- 表向きはEmacsというのが入るようで
- Lisp Cabinetというフォルダがプログラムのところにできて、その下に
- という5つがあることがわかる。それぞれを起動できる
- Emacsというのはテキストエディタが表層にあって、それで文書を作ったり管理したりしながら、コマンドライン的な色々をしてくれるものらしく、このLisp Cabinetには、Lispを動かすためのもろもろもつけてある、ということらしい
- また、Lispはいくつもの方言があるらしいのだが、Clozure CL, Legacy SLIME, SBCLというのはそれらに対応するらしい
- まだ判然としなくて、この先もわからないままに放置するかもしれないけれど、Clozure CLを立ち上げて、こんな画面になったら
Scheme事始め13:数学的な例を関数を作りながらみてみる(2)
- ペアノ的自然数定義。1を0,1,2,...個要素とするリスト vの操作として表すsuccessorのsucc,predecessorのpred
- consは1を先頭に付け加えること、cdrは先頭を除くこと
> (define succ (lambda (v) (cons 1 v))) > (define pred (lambda (v) (cdr v))) > (succ ()) . #%app: missing procedure expression; probably originally (), which is an illegal empty application in: (#%app) > (succ '()) (1) > (succ (succ '())) (1 1) > (succ (succ (succ '()))) (1 1 1) > (pred '(1 1 1 1)) (1 1 1) > (pred (pred '(1 1 1 1))) (1 1) > (pred (pred (pred '(1 1 1 1)))) (1) > (pred (pred (pred (pred '(1 1 1 1))))) () > (pred (pred (pred (pred (pred '(1 1 1 1)))))) . . mcdr: contract violation expected: mpair? given: ()
- はとをペアにして、が0になるまで繰り返す、と考えると以下が加算処理になる
> (define plus (lambda (x y) (if (null? y) x (succ (plus x (pred y)))))) > (plus '(1 1) '(1 1 1)) (1 1 1 1 1)
-
- 1のリストを整数値に返るとすると、"null?"のチェックを"zero?"にして「足す1」「引く1」の関数をsucc,predに換えればよい
> (define add1 (lambda (x) (+ x 1))) > (add1 0) 1 > (define sub1 (lambda (x) (- x 1))) > (sub1 4) 3 > (define plus-num (lambda (x y) (if(zero? y) x (add1 (plus-num x (sub1 y)))))) > (plus-num 3 4) 7
-
- 1のリストとして表したものを数値にするときに、関数の骨格は変わらなかった。もう一度1のリストに戻して、今度は、数値にするのではなくて演算を加算から乗算にすることにする。0を足したらxは変わらない、と言う点は、0をかけたら0になる、と書きかえる必要がある。0より大きい自然数をかけるのは、xをy回連結する、と見る
> (define mult (lambda (x y) (if(null? y) '() (plus x (mult x (pred y)))))) > (mult '(1 1) '(1 1 1)) (1 1 1 1 1 1)
-
- 乗算はy回の加算だった。べき乗はy回の乗算だ、と見れば:0乗は1なので
> (define pows (lambda (x y) (if(null? y) '(1) (mult x (pows x (pred y)))))) > (pows '(1 1) '(1 1 1)) (1 1 1 1 1 1 1 1)
- 再帰部分を独立させる
- 加算処理を次のように書き直す
> (define plus (lambda (x y) (if(zero? y) x (+ 1 (plus x (- y 1)))))) > (plus 3 4) 7
-
- よく見ると、再帰部分が(+1 (plus (-y 1)))となっていて、plusという関数の再帰の中に、plusという関数と1を足す、という関数が入っていることがわかる
- これを変えるのにもう一つ変数を持ち込むと、次のようになる。yを減らすたびにpを増やして、最後にx+pをしている、ということで、そんなことなら最初からx+yをすればいいだろう、という感じだが、ここでは、「計算の構造」のことを考えるため、ということで、その点は無視します。こうすると、yを減らしながら、計算を表すリストの入れ子を深くする代わりに、yとpの値の間でバーターをするだけにできるという(メモリ上の)メリットがあるし、再帰関数が純化しているというメリットもある
- 再帰部分を純化して、最後にやりたいことを実現する方法ともいえるが、この方法を末尾再帰形式と言うそうだ
> (define plus2 (lambda (x y p) (if(zero? y) (+ x p) (plus2 x (- y 1) (+ p 1))))) > (plus2 3 4 0) 7
Scheme事始め5:関数のカリー化
- 複数の変数からなる関数があったとき、その変数を1つずつ(プログラムの中で)扱うことをカリー化と言う(らしい)
- のようなこと
- Schemeで書くとこんな感じ?下がカリー化風?
> ((lambda (x y z) (+ x y z)) 2 3 4) 9 > ((lambda (z) (+ z ((lambda (y) (+ y ((lambda (x) (+ x)) 2) )) 3 ))) 4 ) 9
Scheme事始め6:無駄に仰々しく耳慣れない単語たち
- ラムダ記法(ただの関数)、car(かー)とcdr(くだー)、アルファ変換、ラムダさん方、ベータ簡約、イータ変換、関数適用、関数抽象…
- 耳慣れない単語が続くと疲れる
- 疲れるけれど、まぎれなくするための「わざわざの耳慣れなさ」と思って受け入れておこう
- たとえば
- 変数衝突を避けるには変数有効範囲を明確にするのがよい、と考えられ、それをせずにはプログラムが書けない仕組みにしたのがラムダ記法であって、そのラムダ記法に耳慣れない単語を使うのは、耳慣れた単語にすると、変数衝突が起きるかもしれないから、だという
- car, cdrもプログラムの仕組みに関わるものなので、それの呼び名は耳慣れないものとしている…、という具合に
Scheme事始め14:高階手続
- 手続きを引数として取る手続き
- apply
> (define iota (lambda (min max) (if (> min max) '() (cons min(iota (+ min 1) max))))) > (iota 0 9) (0 1 2 3 4 5 6 7 8 9) > (define num0-9 (iota 0 9)) > (apply + num0-9) 45 <|| --map >|lisp| > (map - num0-9) (0 -1 -2 -3 -4 -5 -6 -7 -8 -9)
- 組み合わせ列挙
> (define (double n) (apply append (map (lambda (i) (map (lambda (j) (list i j)) (iota 1 (- i 1)))) (iota 1 n)))) > (double 4) ((2 1) (3 1) (3 2) (4 1) (4 2) (4 3))
Scheme事始め7:ラムダ算法
- という関数があって、という関数があったとする
- という関数を考えることができる
- これはyについて関数g()を処理してそれをf()に渡して、という風に入れ子になっているし、1個ずつの変数処理なので、カリー化してある、と言えるもの
- という新たな関数ができるわけだけれど、ととの2つの書き方ができてしまう。同じものなのに…。じゃあ、一番良い形、というのを定めてやって、それにしてから考える、というのは普通の発想。それが(ベータ)正規形(このように同じ働きをする関数は同じ表記になるようにするのがイータ変換:これも、『必要だから無駄に難しく聞こえる耳慣れない用語』のひとつ
- ただし、渡してやるものは、分類して考えておく方が良いかもしれない
- 変数が与えられるか、関数が与えられるか、値が与えられるか、に分けられる
- ここで「変数」が与えられる、というのは、の変数とは違う変数に書き換えたりすることを含む
- ここで「関数」が与えられる、というのは、ですでに使っている変数で出来た関数を与えること(らしく)
- ここで「値」が与えられる、というのは、いわゆる「値」の代入。ただし、数値の関数の変数への値の代入は「自然数そのものがリストで作られているSchema」では、「値」を代入しているわけではなく、「変数」「関数」を与えていることと変わらない
- 変数が与えられるか、関数が与えられるか、値が与えられるか、に分けられる
- とまあ、変数も関数も値もみんなリストで扱っている「この世界」で、うまく回るような関数の取扱いのルールが、ラムダ算法、ただし、基幹部ではラムダ関数を使っているのが前提条件
- たとえば、がある特定の値であるとすると、それはのxに値を代入することと同じことなわけだけれど、その場合も、きっちり簡単にしてもよいでしょう。たとえばのにを代入したらでもよいけれど、でもよいわけで、どちらかにした方がよくて、どちらにするかと言えば、を(ベータ)正規形にした場合と同じルールで一番良い形にするのが自然な発想
- で、のに値を代入して「よい形」にすることをベータ簡約と定めた後で、関数を組み合わせたときの正規形作成もそれと同じルールにしたという発展の歴史のため??に「ベータ正規形」と言うらしい
Scheme事始め8:プログラム言語としてのSchemeのルール
- Schemeの基礎
- すべては()表記する(Listで表す)。自然数もListで表す
- 関数は「ただの関数」というラムダ関数
- カリー化は変数を1つずつ扱う方法で()だけで実現できる
- ベータ簡約・イータ変換・ベータ正規形が関数の同等性や計算手続きの計算機実行を保証するとともに、プログラムの実装方法にルールを与える
- これらのScehmeの基礎があればプログラムは書けるのだが、さすがにそれだけだと書く気が起きないので、いくつかの決め事が登場する
- 少なければそれだけ覚えることはすくないし、計算機に近いが、繰り返し作業や、『言わなくてもわかるでしょ、人間なら』という部分が肥大化する
- 多ければ便利だが、覚えないといけないし、作った決め事間の整合性に気を遣う必要が出る
- 特殊形式
- define
- lambda関数を手軽に定義することができる
- lambda
- ラムダ関数
- let
- 対応付け??
- quote
- ただの引用
- set!
- 定義し直し、強制上書き
- if
- 真偽で2分岐
- define
- ひたすら例をなぞってたたいてみよう
> a 2.3 > (* 2 a) 4.6 > (define f_2x+3 (lambda (x) ((lambda (a b) (+ (* a x) b)) 2 3) )) > (f_2x+3 5) 13 > (define f_2x+3 (lambda (x) (let ((a 2) (b 3)) (+ (* a x) b)))) > (f_2x+3 5) 13
> (quote Gauss) gauss > (quote (+ 2 3)) (+ 2 3) > (eval (quote (+ 2 3)) (interaction-environment)) 5
- Listからの要素取り出し
> (car (list + - * /)) #<procedure:+> > (cadr (list + - * /)) #<procedure:-> > (caddr (list + - * /)) #<procedure:*> > (cadddr (list + - * /)) #<procedure:/> > ((car (list + - * /)) 5 3) 8 > ((cadr (list + - * /)) 5 3) 2 > ((caddr (list + - * /)) 5 3) 15 > ((cadddr (list + - * /)) 5 3) 1 2/3
- 「そのままのquote」はしばしば使うので便利になっている
> (cons (quote b) (quote ())) (b) > (cons (quote a) (cons (quote b) (quote ()))) (a b) > '(+ 2 3) (+ 2 3) > (list 'a 'b 'c) (a b c) > (append '(a b) '(c d)) (a b c d)
- カウンタ
> (define count (lambda () (set! n (+ n 1)))) > (define n 0) > (count) > n 1 > (count) > n 2 > (count) > n 3
-
- 内部使用のnのカウンタは大域のnの値を変えずにカウンタ機能を内部で発揮
> (define count ((lambda (n) (lambda () (set! n (+ n 1)))) 0)) > (count) > n 3 > (count) > n 3
> (if (> 5 3) "yes" "no") "yes"
> (define fact (lambda (n) (if (zero? n) 1 (* n (fact (- n 1)))))) > (fact 3) 6
Scheme 最小限LISP Scheme事始め0:教育的環境
- 作者: 吉田武
- 出版社/メーカー: 東海大学出版会
- 発売日: 2012/06/01
- メディア: 単行本
- 購入: 6人 クリック: 266回
- この商品を含むブログ (17件) を見る
- この本の後半を参考に:
- LISPについてまったく何も知らない状態でWindowsノートPCが目の前にあるが、LISPの文法を数学っぽいことに試してみたい、という動機から。
- LISPをWindowsでやろうというのがそもそも面倒のもとらしいことがウェブサーチでわかったが…
- 初めはEmacsを使った。そこではCommon Lispが入っていた。『素数夜曲』p382によれば、現在のLISPはCommon LispとSchemeに2大分されているそうで、商業的開発に使われるべく、いろいろなものが入ったCommon Lispと最小限化を志向したScheme(R5RS)に分かれるという
- どうも『素数夜曲』の解説はR5RSに沿っているようなので、その環境を入れなおすことにする
- Racketと呼ばれる環境の1つとしてR5RSがあるようだ
- Racketのダウンロードサイト(こちら)
- こちらにも似たような情報がかいつまんで書いてあります
- ダウンロードは少し時間がかかるが、そのうち入る。あとは立ち上げて、R5RSを選ぶ。ツールバーのLanguageから"Other languages"を選択し、R5RSをハイライトすればよいらしい
- Racketは教育用を標榜しているだけあって、エラーの表示などとてもよい!
Scheme事始め9:Scheme 型
- 非数値データ型
> (define type-check (lambda (x) (define form (lambda (str) (display "This is ") (display str))) (cond ((procedure? x) (form "a procedure: ") x) ((number? x) (form "a number: ") x) ((pair? x) (form "a pair: ") x) ((null? x) (form "a the empty: ") x) ((symbol? x) (form "a symbol: ") x) ((string? x) (form "a string: ") x) ((char? x) (form "a character: ") x) ((boolean? x) (form "a boolean: ") x) ((vector? x) (form "a vector: ") x) (else (display "may be a special form: ") x) ))) > (type-check +) This is a procedure: #<procedure:+> > (type-check car) This is a procedure: #<procedure:mcar> > (type-check 1.3) This is a number: 1.3 > (type-check (- 3 3)) This is a number: 0 > (type-check 'a) This is a symbol: a > (type-check #(3 5)) This is a vector: #(3 5) > (type-check if) . if: bad syntax in: if
- 数値データ型
> (define type-of (lambda (x) (define form (lambda (str) (display str) (display "/ "))) (display "This is ") (cond ((number? x) (display "a number: ") (cond ((and (real? x ) (not (negative? x))) (form "real/ nonnegative")) ((and (real? x ) (negative? x)) (form "real/ negative")) (else (form "complex"))) (cond ((and (integer? x) (odd? x)) (form "integer/ odd")) ((and (integer? x) (even? x)) (form "integer/ even")) (else (form "noninteger"))) (cond ((exact? x) (form "exact")) (else (form "inexact"))) x ) (else (display "a string: ") x) ))) > (type-of 2+5i) This is a number: complex/ noninteger/ exact/ 2+5i > (type-of 2+3.0i) This is a number: complex/ noninteger/ inexact/ 2.0+3.0i > (type-of 1) This is a number: real/ nonnegative/ integer/ odd/ exact/ 1 > (type-of 1.0) This is a number: real/ nonnegative/ integer/ odd/ inexact/ 1.0 > (type-of 0) This is a number: real/ nonnegative/ integer/ even/ exact/ 0 > (type-of -0.3) This is a number: real/ negative/ noninteger/ inexact/ -0.3 > (type-of 'symbol) This is a string: symbol > (type-of 2/3) This is a number: real/ nonnegative/ noninteger/ exact/ 2/3 > (type-of (exp (exp 0))) This is a number: real/ nonnegative/ noninteger/ inexact/ 2.718281828459045
Scheme事始め10:構文拡張
- 最低限の特殊形式では不便だ、となれば、拡張してやることもできる。そんな構文例が「拡張の塊」となると「LISP方言」のようなものになる
- 構文の拡張も自作関数もある意味では同じ…
Scheme事始め12:数学的な例を関数を作りながらみてみる(1)
- インクレメントとデクレメント
> (define ++ (lambda (i) (+ i 1))) > (++ 3) 4 > (define -- (lambda (i) (- i 1))) > (-- 5) 4
- 冪
> (define ** (lambda (a b) (expt a b))) > (** 2 3) 8
- 割り算関係。商、剰余、法数
> (define // (lambda (a b) (quotient a b))) > (// 23 4) 5 > (define /@ (lambda (a b) (remainder a b))) > (/@ 23 4) 3 > (define /: (lambda (a b) (remainder a b))) > (/: 23 4) 3
- 整数の偶奇判断
> (define parity-of (lambda (p) (if (odd? p) -1 1))) > (parity-of 3) -1 > (parity-of 6) 1 > (parity-of 4.3) . . odd?: contract violation expected: integer given: 4.3
- 変数の入れ替えでをに、をになどをする。演算子を与える形にする
> (define proc-swap (lambda (proc a b) (let* ((dummy a) (a b) (b dummy)) (proc a b)))) > (proc-swap - 3 4) 1 > (- 3 4) -1 > (proc-swap / 3 4) 1 1/3 > (/ 3 4) 3/4 > (proc-swap ** 2 3) 9 > (** 2 3) 8
- 四捨五入
- 組み込み関数でいかにも四捨五入っぽい関数roundは次のように「一番近い整数だけれど、ちょうど真ん中だったら偶数を返す」というちょっと困るルールになっているという
> (round 1.5) 2.0 > (round 2.5) 2.0
-
- この不具合を解消するために、与えた値の絶対値以下であってかつそれに一番近い整数を返すという組み込み関数truncateを使って、任意のケアでの四捨五入を定義したのが以下。与えるのは四捨五入したい値と桁数。四捨五入したい値の正負で調整のために加える値をに分け、桁数に応じて倍して加えて除して元に戻す
> (define adjust-of (lambda (x digit) (let ((slide (if (positive? x) 1/2 -1/2))) (/ (truncate (+ slide (* x digit))) digit) ))) > (adjust-of 1.2994 100) 1.3 > (adjust-of 1.2994 1000) 1.299 > (adjust-of 1.2994 10) 1.3 > (adjust-of 1.2994 10000) 1.2994 > (adjust-of -1.2994 10) -1.3 > (adjust-of -1.2994 100) -1.3 > (adjust-of -1.2994 1000) -1.299 > (adjust-of -1.2994 10000) -1.2994
- 2つの値の範囲である値から初めて等間隔の数列を発生させてみる。Rで言えば
seq(from=a,to=b,by=t)
> (define seq-by (lambda (a b t) (if (> a b) '() (cons a (seq-by (+ a t) b t)) ))) > (seq-by 1 5 1) (1 2 3 4 5) > (seq-by 1 5 0.7) (1 1.7 2.4 3.0999999999999996 3.8 4.5) > (seq-by 1 5 1/3) (1 1 1/3 1 2/3 2 2 1/3 2 2/3 3 3 1/3 3 2/3 4 4 1/3 4 2/3 5)
-
- ただし、aからtずつ増やしてbを越える手前まで、というルールなので、b-aの符号とtの符号が一致していないと終わらなくなる、その点のケアをしたのが以下の関数定義(符号が合わない場合には、最初の値のみを返す)
> (define seq-by2 (lambda (a b t) (if(> (* (- b a) t) 0) (if (> a b) '() (cons a (seq-by (+ a t) b t)) ) (cons a '()) ))) > (seq-by2 1 5 0.7) (1 1.7 2.4 3.0999999999999996 3.8 4.5) > (seq-by2 1 5 -0.7) (1)
Scheme事始め1:リストがすべて
- 集合からn-タプル、ペアノの自然数
- まだなんとなくしっくりこないところがある。リストの要素は2つとして考えてあとは順番に右に向かって剥いていく、というのがLISPの原則のようだが、"( )"を使った表現では第1要素とその他の要素があって、その他の要素は複数だったりするので…。このあたりは、LISP表記の読み取り方、という側面と、構文解析、という側面との見方・解釈の仕方の違い、であって、どちらも正しい、ということのように、少なくとも今は見える
- List
- Listの要素の取扱い
- Listは原則2個の要素を持つが、左側を優先して取り扱う(左側をCar(『かー』Contents of the Address part of the Register)、右のその他をCdr(『くだー』Contents of the Decrement part of the Register)と呼ぶ
- LISPでのListの取扱い
- "( )"で囲ったものがList、囲まれたものが要素で、要素の区切りは空白文字
Scheme事始め2:「ただの関数」
- 関数
- 関数っていうのは、のようなもの
- これをって、そう書かないといけない理由もないので、と書くことにする
- さらにの記号は、は関数を定義するんだよ、という意味だと知っていれば、わざわざ書かなくても用は足りるのでと書くことにする
- さらにのも空白文字で代用すればとできる
- ただしと言うとき、これはの関数であることはわかるけれど、この関数が特になんという関数なのか、というのは決められない。それはを「関数ですよ」としか宣言していないから
- このように「関数である」ということだけを宣言する方法があるのは便利じゃない、ということで、このような「ただの関数」であることを示す記号と「ただの関数」ですよ、という名称を決めることにした
- それが「ラムダ関数〜ただの関数」という呼び名であって、と言う記法である
- Schemeではというコマンドに相当する
(lambda (a b x ) ( + (* a x) b))
- 「ただの関数」が仰々しく『ラムダ』と呼ばれるのは、きちんと手続きとして計算機上で動くように構成するには、色々な決め事を持たせないといけないのだけれど、その背負っている決め事の重みを感じさせるため(のようなもの)
Scheme事始め3:RacketでSchemeを扱ってみる
- リストでない形で渡すとそれを値評価する。数値はそのやり方がOK、文字列は""で囲む
> 123 123 > "Gauss" "Gauss"
> () . #%app: missing procedure expression; probably originally (), which is an illegal empty application in: (#%app)
-
- 要素を1つ入れるとき、その要素は「特別な要素〜第1の要素」なので、きちんと評価される場合とそうでない場合とがある
> (7) . . application: not a procedure; expected a procedure that can be applied to arguments given: 7 arguments...: [none] > ("apple") . . application: not a procedure; expected a procedure that can be applied to arguments given: "apple" arguments...: [none] > (+) 0 > (-) . . -: arity mismatch; the expected number of arguments does not match the given number expected: at least 1 given: 0 > (*) 1
- 四則演算その1
> (+ 5) 5 > (- 5) -5 > (* 5) 5 > (/ 5) 1/5
- 四則演算その2
> (+ 2 5) 7 > (- 2 5) -3 > (* 2 5) 10 > (/ 2 5) 2/5
- 四則演算その3。演算の繰り返し
> (+ (+ (+ 1 2) 3) 4) 10 > (+ 1 2 3 4) 10
- 四則演算その5.一般的な計算
> (- (+ (* (/ 1 2) 3) 4) 5) 1/2
- いくつかの基本関数
> (sqrt 3) 1.7320508075688772 > (log 2) 0.6931471805599453 > (log (exp (exp 0))) 1.0
- 字下げする
> (- (+ (* (/ 1 2) 3) 4) 5) 1/2
Scheme事始め4:自作関数
- ラムダ関数(ただの関数)は「関数である」ことしか決めないので、それに名前をつけてとっておくには、そのための方法が必要になる
> (define linear (lambda (a b x ) (+ (* a x ) b))) > (linear 2 3 4) 11
-
- これは、「定義しましょう、linear というものを、「ただの関数として、ただし、それは3つの変数a,b,xを使って次のような関係式として」と読める
- また同じことは
> (define (linear a b x) (+ (* a x ) b))
-
- とすることもできる。あえてこれに別の『訳文』をつけるとすれば、「定義しましょう、「linear a b x」とは「(+ (* a x ) b)」と同じである、と」となる
- 訳文解釈上は別に見えるが、これをどちらで書いても、計算機としては同じものとして扱っていることになる
Scheme事始め5:四則演算を統一的に扱う
- 四則演算をラムダ関数として扱いなおしてみる
- "+,-,*,/"の4演算はすべて2項演算なので、「演算記号」を"#"とでも表すとすれば
(# 3 4)
- のように書くこともできる
- 問題は、どうやって統一的に扱うのにどうするか
- 以下はその例。infixという関数をラムダ関数定義する。そのラムダ関数は2項とその間の演算子をそれぞれ、a bとprocとして定める
> (define infix (lambda (a proc b) (proc a b ))) > (infix 3 + 4) 7 > (infix 3 * 4) 12 > (infix 3 - 4) -1 > (infix 3 / 4) 3/4