2010年9月29日水曜日

学者猿コンサル

前回のブログ(コンサル)は, 検討も設計も多少杜撰であった. 改めて考えた描き方はこうだ.

これは2変数関数の値を表示するいわば計算図表みたいなものである. 計算図表には, 変数の変域があるわけで, 今回はそれをxminと, xmaxとする. また2つの変数をx0と, x1とする. つまりxmin≤x0, x1≤xmaxである.



xminとxmaxの基線の上に, x0とx1の点A, Bをとり, それを脚とする長さlの二等辺三角形CABを描く. ACをCで左に135度曲げてDの方向へ長さm(=l/√2)だけ伸ばしDとする. BCをCで右に135度曲げてFの方向へ長さmだけ伸ばしFとする. CD, CFを2辺とする菱形CDEFを作ると, Eが関数の値の場所になり, その座標は(x0+x1)/2, (x1-x0)/2となる.



x座標は誰にでもすぐ分かるが, y座標がかくもきれいな形なのは不思議である. これからは幾何学だが, まず二等辺三角形CABの底角はどちらもαなので, 頂角∠ACB180-2αである. ACの長さはl, ∠ACDは45度, CDはl/(√2)なので, DACは直角二等辺三角形である. DEの線はDから下向きに45-αなので, 菱形で上半分の角度も同じゆえ, ∠CDEは2α-90. 従って, ∠ADEは180-2αとなり, 先程の頂角とおなじである. また, DA=DE=mだから, DAEはCABと1:√2の相似形であった. 従って, AEはABの1/√2であり, 右側も同じなので, EABは直角二等辺三角形である. ゆえにEのy座標, EHはABの半分, つまり(x1-x0)/2である.

y座標は, x0≤x1なら正だが, 反対だと負になり, 基線より下になることに注意しよう.


こうして作った減算表(x1-x0)が次のものだ. 8-3=5と3-8=-5を示している. もうアニメーションを作る必要はないと思う.


2010年9月26日日曜日

学者猿コンサル

2010年9月 Brisbaneで開催されたIFIP WCC2010でHistory of Computingのシンポジウムがあった. そこでオーストラリアのMonash大学のJudy Sheardさんが同大学のコンピュータ博物館を紹介した. そのスライドの中に, おや?と思う絵があった. 一瞬の内に次に進んだが, 同行の山田さんがその絵を写真に撮っておられたので, 頂いた.

Consul, the Educated Monkeyという計算関連の教育玩具である. ウェブページで調べると, 1916年頃にアメリカで売り出されたものらしい.


(出典http://www.rechenwerkzeug.de/consul.htm)

使い方はこうだ. 猿の両足を, 図のように下の目盛の3と9に合わせると, 猿の手が示す枠の中に積の27が現れるのである. 目盛の右端の12の右には四角が見えるが, 片足をそこに合わせると, 他方の足の自乗が現れる.

これは乗算表であるが, この表は差し換えられ, 加算にも使える.

こういうものがあると知ったら, プログラムしたくなるのは当然である.

http://playground.iijlab.net/~ew/consul/consul.htmlを見て欲しい. これは十六進の乗算表である. 下の目盛は0からfまであり, 目盛に乗っている足の辺りをマウスで横に動かすと, リンク機構がつられて動き, 赤印の交点の直ぐ上に積が現れるようになっている.


多少の設計ミスで, 0とfの積などでは, 赤印が頭の上に行ってしまうのは, ご愛敬である.

なお, Consulのシミュレータもウェブにあった.

http://www.edumedia-sciences.com/de/a572-consul-the-educated-monkey

2010年9月16日木曜日

入れ子のかっこ

前回のブログの点記法の続きである. とりあえず練習をしよう. 私の手元のPaul Rosenbloom, The Elements of Mathematical Logic (Dover 1950)に点記法の論理式が沢山出てくる. それでテストしてみた. まずSchemeでBoole値が0と1のnot, or, impを定義する.

(define (not p) (- 1 p))
(define (or p q) (quotient (+ p q 2) 3))
(define (imp p q) (or (not p) q))

テストをするには, mapが便利.

(map not '(0 1)) => (1 0)
(map or '(0 0 1 1) (0 1 0 1)) => (0 1 1 1)
(map imp '(0 0 1 1) '(0 1 0 1)) => (1 1 0 1)


上の本では, 沢山並ぶ -> には特にかっこを(点で)示さない. -> はleft associativeであって, (p -> q -> r) は ((p -> q) -> r) なのだ.

ではやってみよう.

I4 p -> .q -> r. -> .p -> q -> .p -> r
かっこに変えると
((p -> (q -> r)) -> ((p -> q) -> (p -> r)))
Schemeの定義は
(define (i4 p q r)
(imp (imp p (imp q r)) (imp (imp p q) (imp p r))))
実行
(map i4 '(0 0 0 0 1 1 1 1) '(0 0 1 1 0 0 1 1)
'(0 1 0 1 0 1 0 1))
=> (1 1 1 1 1 1 1 1)

もう1つ.

T2 q -> r -> .p -> q -> .p -> r
かっこに変えると
((q -> r) -> ((p -> q) -> (p -> r)))
Schemeの定義は
(define (t2 p q r)
(imp (imp q r) (imp (imp p q) (imp p r))))
実行
(map t2 '(0 0 0 0 1 1 1 1) '(0 0 1 1 0 0 1 1)
'(0 1 0 1 0 1 0 1))
=> (1 1 1 1 1 1 1 1)

とうまくいく.

かっこ記法と点記法の変換だが, まずかっこから点へは, すべての2項演算子をかっこでくくることにし, つまり

<primary>==<letter>|(<expression>)
<expression>==<primary>|<expression>*<expression>

だけとする. expressionの例は a, a * b, (a * b) * c, ...など.

expression * expression を点記法にするには, expression' lp * rp expression とする. expression'はexpressionを点記法に変えたものである. lpとrpは, 左右のexpressionをひとまとまりにする点である. lpは左のexpression'で使った最大の右点の数より多く, rpは右のexpressionで使った最大の左点の数より多くなければならない. 従って, 下請けの変換は, expression'を返すと同時に, 自分の使った右点, 左点を返すことにする.

letterの場合は, letterの他に, 右点,左点として, 0,0を返す.

* の場合は, 左の式を変換て置き, その右点+1の左点を置き, 演算子を置き, 右の式を変換し, その左点+1の右点を置き, 右の式を置く. また自分で使った左点, 右点も返す.

(define (dotconv exp)
(display (list exp))
(if (symbol? exp) (list '(0 0) exp)
(let* ((l (dotconv (car exp)))
(r (dotconv (caddr exp)))
(op (cadr exp))
(rlp (+ (cadar l) 1))
(le (cadr l))
(lrp (+ (cadar r) 1))
(re (cadr r)))
(list (list rlp lrp)(list le rlp op lrp re)))))


(dotconv 'a) => ((0 0) a)
(dotconv '(a * b)) => ((1 1) (a 1 * 1 b))
(dotconv '((a * b) * c)) => ((2 1) ((a 1 * 1 b) 2 * 1 c))
(dotconv '((a * b) * (c * d))) =>
((2 2) ((a 1 * 1 b) 2 * 2 (c 1 * 1 d)))

この後は ((a 1 * 1 b) 2 * 2 (c 1 * 1 d)) を a * b . * . c * d にしたい. flattenし, 整数はそれ引く1の点を出力する.

(flatten '((a 1 * 1 b) 2 * 2 (c 1 * 1 d))) => (a 1 * 1 b 2 * 2 c 1 * 1 d)

(define (convstream l)
(apply string-append (apply append
(map (lambda (x)
(list (if (number? x) (make-string (- x 1) #\.)
(symbol->string x)) " "))
(flatten l)))))

(convstream '((a 1 * 1 b) 2 * 2 (c 1 * 1 d)))

(define (par->dot exp) (convstream (cdr (dotconv exp))))

(par->dot 'a) => "a "
(par->dot '(a * b)) => "a * b "
(par->dot '((a * b) * c)) => "a * b . * c "
(par->dot '((a * b) * (c * d))) => "a * b . * . c * d "


一方, 私の考えた逆変換はこうだ.


1.(((a * b) * (c * d)) * ((e * f) * (g * h)))
2."a * b . * . c * d .. * .. e * f . * . g * h "

1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8
3.(a 0 * 0 b 1 * 1 c 0 * 0 d 2 * 2 e 0 * 0 f 1 * 1 g 0 * 0 h)
4.29
5.((-1 5) (-1 13) (15 21) (23 29) (15 29) (7 13))
6.(< < < a * b > * < c * d > > * < < e * f > * < g * h > > >)
7.(((a * b) * (c * d)) * ((e * f) * (g * h)))


上の例で, 1. は元のかっこ記法の式. 2. はそれを点記法にしたもの. 逆変換はここから始まる. まず各演算子に左点と右点があるものとし, 3のように変換する. その上の2行は, 各要素の位置を示す. 0から28まであるから, lengthをとると, 4. のように, 29.

位置 1,5,9,..のように, 4を法として1の位置は左点. 3の位置は右点である. さらに, 演算子は2(mod 4), 変数は0(mod 4)である.

次に各右点>0にはこの右方にある相棒の左点を探し, また左点>0にはこの左方にある右点を探し, 対にする. 上の例では 5. が対のリストである. この読み方は, 5の位置の左点を越える右点は, 左方にはないので, -1とし, (-1 5)とする. 13の位置の左点も同じ. 21の位置の左点は, 15の位置の右点の方が大きいので, スコープはここまでとなり, (15 21)が出来る. 3. と5. の情報から, 6. を作るのだが, (-1 5)のような対があれば, -1に左かっこ, 5に右かっこを置く. この挿入で, 位置がずれると困るから, 挿入は番号の多い右端から行う. 右かっこと左かっこの区別は, 4を法とした剰余の1か3で決る. まだこの段階は記号列であるが, 通常のかっこを記号として挿入すると, 分かり難いから, 角かっこを使っている. 出来たのは6. である.後は, 入れ子の式の読込みルーチンを書けばよい. それにより, 7. が得られる.

(define (iconv s) ;2. -> 3.
(define (char->symbol c)
(string->symbol (list->string (list c))))
(define (reads n s)
(cond ((null? s) s)
((char=? (car s) #\Space) (reads n (cdr s)))
((char=? (car s) #\.) (reads (+ n 1) (cdr s)))
(else (cons n
(cons (char->symbol (car s)) (reads 0 (cdr s)))))))
(let ((ss (string->list s)))
(cons (char->symbol (car ss)) (reads 0 (cdr ss)))))

(define (makepair s) ;3. -> 5.
(let ((len (length s)) (ps '()))
(do ((i 3 (+ i 4))) ((>= i len))
(let ((r (list-ref s i)) (k len))
(do ((j (- len 4) (- j 4))) ((< j i))
(let ((l (list-ref s j)))
(if (< r l) (set! k j))))
(if (> (- k i) 2) (set! ps (cons (list i k) ps)))))
(do ((i (- len 4) (- i 4))) ((< i 0))
(let ((l (list-ref s i)) (k -1))
(do ((j 3 (+ j 4))) ((> j i))
(let ((r (list-ref s j)))
(if (> r l) (set! k j))))
(if (> (- i k) 2) (set! ps (cons (list k i) ps)))))
ps))

(define (makestr ps s len) ;5. 3. (length 3) -> 6.
(define (insert l n a)
(if (<= n 0) (cons a l)
(cons (car l) (insert (cdr l) (- n 1) a))))
(set! ps (sort (apply append ps) >))
(for-each (lambda (x) (set! s (insert s x
(if (= (modulo x 4) 3) '< '>)))) ps)
(append '(<) (filter symbol? s) '(>)))

(define (str->sexp str) (define i 0) ;6. -> 7.
(define (getch) (let ((ch (list-ref str i)))
(set! i (+ i 1)) ch))
(define (read) (let ((ch (getch)))
(cond ((eq? ch '<) (readtail))
((eq? ch '>) '())
(else ch))))
(define (readtail) (let ((x (read)))
(if (null? x) x (cons x (readtail)))))
(read))

2010年9月5日日曜日

入れ子のかっこ

Lispの好きな人は, かっこだらけのS式を何とも思わない. 反対にhtmlのようなタグでの入れ子には耐えられない.

しかし, S式を声を出して読む時, 「かっこ開く」「かっこ閉じる」や「左かっこ」「右かっこ」というのは煩わしい. 私は昔から,左かっこを「かっこ」, 右かっこを「こっか」と読むことにしている. (Algol 68で, 添字に使う [ と ] を, sub symbol, bus symbolと呼んでいたのをまねした.)

ところで, 今回の話題は, 自然言語の構文解析である. 構文解析木を図で表わすのは容易だが, かっこ付きでも表わせる.

Time flies like an arrow は 光陰矢の如し と構文解析するのが普通だが, 時間の蝿は矢が好きだ という笑い話もある. 前者は Time (flies (like an arrow)), 後者は (Time flies) like an arrow と表現すればよい.

SICPに簡単な自然言語解析の話がある. その問題4.45は, The professor lectures to the student in the class with the cat を5通りに構文解析せよ, だ. やってみると

1 ((the professor)
(((lectures
(to (the student)))
(in (the class)))
(with (the cat))))
2 ((the professor)
((lectures
(to (the student)))
(in ((the class)
(with (the cat))))))
3 ((the professor)
((lectures
(to ((the student)
(in (the class)))))
(with (the cat))))
4 ((the professor)
(lectures
(to (((the student)
(in (the class)))
(with (the cat))))))
5 ((the professor)
(lectures
(to ((the student)
(in ((the class)
(with (the cat))))))))

それぞれの和訳は

1 教授は(猫を連れて(教室で(学生に講義する)))
2 教授は((猫を連れた教室)で(学生に講義する))
3 教授は(猫を連れて((教室の学生)に講義する))
4 教授は((猫を連れた(教室の学生))に講義する)
5 教授は(((猫を連れた教室)の学生)に講義する)

猫を連れているのは, 1と3は教授. 2と5は教室. 4は学生である.

ウェブを眺めていて, H.B.Curryの書いたページを見つけた. ただで見られるのは1ページ目だけだが, 今はそれだけ見られれば充分である.

論理の式には, かっこの代りに点が打ってあるものがある. 件のページには, その提案が書いてある.

Let us suppose that a group of dots on the right of an operation or prefix denotes the beginning of a bracket which extends to the right until it meets a group with an equal or larger number of dots on the left of an operation; and that the scope of a group of dots on the left of an operation shall extend to the left unitl it reaches a larger group of dots on right of some operation.


つまり,
p -> q . -> . q -> r .. -> . p -> r

((p -> q) -> (q -> r)) -> (p -> r)
のことである.

この方式を何と言うか知らないが, dot notation つまり 点記法ということにする.

上の和訳の入れ子のかっこ構造から, 点記法を使い, かっこを外したい. それには, 演算子がどれか決めたい. 演算子は左かっこの右, 右かっこの左にあるのだから,

教授猫を連れ教室学生講義する

の赤字の助詞類を演算子と考える. (猫を連れた, 教室の は形容詞句の時で, 副詞句の時は, 猫を連れて, 教室で になる.)

すると, それぞれの例文は

1 教授は . 猫を連れて . 教室で . 学生に講義する
2 教授は .. 猫を連れた教室 . で . 学生に講義する
3 教授は . 猫を連れて .. 教室の学生 . に講義する
4 教授は ... 猫を連れた . 教室の学生 .. に講義する
5 教授は .. 猫を連れた教室 . の学生 . に講義する

となる.

この点を , 2点を ,, に変えると
1 教授は, 猫を連れて, 教室で, 学生に講義する
2 教授は,, 猫を連れた教室, で, 学生に講義する
3 教授は, 猫を連れて,, 教室の学生, に講義する
4 教授は,,, 猫を連れた, 教室の学生,, に講義する
5 教授は,, 猫を連れた教室, の学生, に講義する
のようになる.

点記法に慣れると, これで読めなくもない. では声を出して読むにはどうするか.

Shakespeareの時代, 劇の台本には句読点が何種類かあり, それぞれで間の取り方が違うという話を読んだことがある. そのように, カンマ2つはカンマ1つより長く間をとれば, この例は構文木が分かるのではないかと考えるが, どうだろうか.