とりとめのないことを書いております。
by tempurature
カテゴリ
全体
プログラミング
scheme
verilog
未分類
以前の記事
2016年 04月
2016年 03月
2016年 02月
2016年 01月
2015年 12月
2015年 11月
2015年 10月
2015年 09月
2015年 08月
2015年 07月
2015年 06月
2015年 03月
お気に入りブログ
PHPで競技プログラミング
メモ帳
最新のトラックバック
ライフログ
検索
タグ
人気ジャンル
ブログパーツ
最新の記事
情報処理技術者試験 お疲れ様..
at 2016-04-17 18:55
基本情報技術者試験 平成27..
at 2016-04-14 04:48
基本情報技術者試験 平成27..
at 2016-04-13 23:03
苦い薬(ハーブ、サプリメント..
at 2016-04-09 14:03
「おバカ度チェックリスト」を..
at 2016-03-24 09:54
外部リンク
ファン
記事ランキング
ブログジャンル
画像一覧
<   2016年 01月 ( 27 )   > この月の画像一覧
B.メイヤー「オブジェクト指向入門」6.10 演習問題を解く(4)
E6.11

TYPES
- DISPENSER[S, G] -- S as structure
- STACK[G] = DISPENSER[STACK, G]
- QUEUE[G] = DISPENSER[QUEUE, G]
FUNCTIONS
- put : DISPENSER[S, G] x G -> DISPENSER[S, G]
- remove : DISPENSER[S, G] |> DISPENSER[S, G]
- item : DISPENSER[S, G] |> G
- empty : DISPENSER[S, G] -> BOOLEAN
- new_stack : STACK[G]
- new_queue : QUEUE[G]
AXIOMS
任意のx:G, s:STACK[G], q:QUEUE[G], d:DISPENSER[S, G]に対して
[A1] empty(new_stack)
[A2] empty(new_queue)
[A3] not empty(put(d, x))
[A4] item(put(s, x)) = x
[A5] remove(put(s, x)) = s
[A6] if empty(q) then item(put(q, x)) = x
[A7] put(remove(q), x) = remove(put(q, x))
[A8] if empty(q) then empty(remove(put(q, x)))
PRECONDITIONS
- remove(d) require not empty(d)
- item(d) require not empty(d)

E6.12

TYPES
- BOOLEAN
FUNCTIONS
- true : BOOLEAN
- false : BOOLEAN
- or : BOOLEAN x BOOLEAN -> BOOLEAN
- and : BOOLEAN x BOOLEAN -> BOOLEAN
AXIOMS
任意のa, b : BOOLEANに対して
[A1] true = true -- true, falseで生成されるBOOLEANオブジェクトは
[A2] false = false -- 単一元であることを示す
[A3] or(true, b) = or(a, true) = true
[A4] or(false, false) = false
[A5] and(false, b) = and(a, false) = false
[A6] and(true, true) = true

E6.13
E6.14

数学的な内容なので断念


[PR]
by tempurature | 2016-01-10 18:54 | プログラミング
B.メイヤー「オブジェクト指向入門」6.10 演習問題を解く(3)
E6.6

TYPES
- TEXTFILE
FUNCTIONS
- open : TEXTFILE x STRING |> TEXTFILE
- isopen : TEXTFILE -> BOOLEAN
- save : TEXTFILE -> TEXTFILE x BOOLEAN
- saveAs : TEXTFILE x STRING -> TEXTFILE x BOOLEAN
- close : TEXTFILE -> TEXTFILE
- lines : TEXTFILE |> INTEGER
- line : TEXTFILE x INTEGER |> STRING
- modify : TEXTFILE x INTEGER x STRING |> TEXTFILE
- delete : TEXTFILE x INTEGER |> STRING
- add : TEXTFILE x INTEGER x STRING |> TEXTFILE
- ismodified : TEXTFILE |> BOOLEAN
- undo : TEXTFILE |> TEXTFILE
AXIOMS
任意のt : TEXTFILE, i, j : INTEGER, s : STRINGに対して
[A1] not isopen(close(t))
[A2] line(modify(t, i, s), j) = (if i = j then s else line(t, j))
[A3] line(delete(t, i), j) = (if j < i then line(t, j) else line(t, j-1))
[A4] if (j < i) then line(add(t, i, s), j) = line(t, j)
[A5] line(add(t, i, s), i) = s
[A6] if (j > i) then line(add(t, i, s), j) = line(t, j-1)
[A7] lines(modify(t, i, s)) = lines(t)
[A8] lines(delete(t, i)) = lines(t) - 1
[A9] lines(add(t, i, s)) = lines(t) + 1
[A10] if isopen(open(t, s)) then not ismodified(open(t, s))
[A11] if (snd save(t)) then not ismodified(fst save(t))
[A12] if not (snd save(t)) then ismodified(fst save(t)) = ismodified(t)
[A13] if (snd saveAs(t, s)) then not ismodified(fst saveAs(t, s))
[A14] if not (snd saveAs(t, s)) then ismodified(fst saveAs(t, s)) = ism..d(t)
[A15] ismodified(modify(t, i, s))
[A16] ismodified(delete(t, i))
[A17] ismodified(add(t, i, s))
[A18] not ismodified(undo(modify(t, i, s))
[A19] not ismodified(undo(delete(t, i))
[A20] not ismodified(undo(add(t, i, s))
PRECONDITIONS
open(t) requires not isopen(t)
lines(t) requires isopen(t)
line(t, i) requires isopen(t)
modify(t, i, s) requires isopen(t)
delete(t, i) requires isopen(t)
add(t, i, s) requires isopen(t)
ismodified(t) requires isopen(t)
undo(t) requires isopen(t) and ismodified(t)

E6.7

TYPES
- HOUSE_BUYER
FUNCTIONS
- new : NONE -> HOUSE_BUYER
- find_property : HOUSE_BUYER -> HOUSE_BUYER
- property_found : HOUSE_BUYER -> BOOLEAN
- get_loan : HOUSE_BUYER -> HOUSE_BUYER
- loan_approved : HOUSE_BUYER -> BOOLEAN
- sign_contract : HOUSE_BUYER |> HOUSE_BUYER
- isdone : HOUSE_BUYER -> BOOLEAN
AXIOMS
任意のh : HOUSE_BUYERに対して
[A1] not property_found(new)
[A2] property_found(find_property(h))
[A3] property_found(get_loan(h)) = property_found(h)
[A4] property_found(sign_contract(h)) = property_found(h)
[A5~7] loan_approved...
[A8~10] isdone...
PRECONDITIONS
sign_contract(h) requires property_found(h) and loan_approved(h)

E6.8

TYPES
- STACK[G]
FUNCTIONS
- put : STACK[G] x G -> STACK[G]
- remove : STACK[G] |> STACK[G]
- item : STACK[G] |> G
- empty : STACK[G] -> BOOLEAN
- new : STACK[G]
- count : STACK[G] -> INTEGER
- change_top : STACK[G] x G |> STACK[G]
- wipe_out : STACK[G] -> STACK[G]
AXIOMS
任意のx : G, s : STACK[G]に対して
[A1] item(put(s, x)) = x
[A2] remove(put(s, x)) = s
[A3] empty(new)
[A4] not empty(put(s, x))
[A5] if empty(s) then count(s) = 0
[A6] count(put(s, x)) = count(x) + 1
[A7] change_top(s, x) = put(remove(s), x)
[A8] empty(wipe_out(s))
PRECONDITIONS
- remove(s:STACK[G]) require not empty(s)
- item(s:STACK[G]) require not empty(s)
- change_top(s:STACK[G], x:G) require not empty(s)

E6.9

TYPES
- STACK[G]
FUNCTIONS
- put : STACK[G] x G |> STACK[G]
- remove : STACK[G] |> STACK[G]
- item : STACK[G] |> G
- empty : STACK[G] -> BOOLEAN
- new : STACK[G]
- count : STACK[G] -> INTEGER
- capacity : INTEGER
AXIOMS
任意のx : G, s : STACK[G]に対して
[A1] item(put(s, x)) = x
[A2] remove(put(s, x)) = s
[A3] empty(new)
[A4] not empty(put(s, x))
[A5] if empty(s) then count(s) = 0
[A6] count(put(s, x)) = count(x) + 1
[A7] capacity >= 0
PRECONDITIONS
- put(s:STACK[G], x:G) require count(s) < capacity
- remove(s:STACK[G]) require not empty(s)
- item(s:STACK[G]) require not empty(s)

E6.10

TYPES
- QUEUE[G]
FUNCTIONS
- put : QUEUE[G] x G -> QUEUE[G]
- remove : QUEUE[G] |> QUEUE[G]
- item : QUEUE[G] |> G
- empty : QUEUE[G] -> BOOLEAN
- new : QUEUE[G]
AXIOMS
任意のx : G, q : QUEUE[G]に対して
[A1] if empty(q) then item(put(q, x)) = x
[A2] put(remove(q), x) = remove(put(q, x))
[A3] if empty(q) then empty(remove(put(q, x)))
[A4] empty(new)
[A5] not empty(put(q, x))
PRECONDITIONS
- remove(q) require not empty(q)
- item(q) require not empyt(q)

[スタックとキューの類似点]
・保持している個数は同じなので、emptyの公理、remove, itemの事前条件は同じ

[スタックとキューの相違点]
・スタックではput, removeが逆操作であるが、キューではそうでなく、
 putとremoveの関係を表すのに可換則や打ち消しルールが必要になった。

(※Exciteブログの制約によりopen, isopenをopen, isopenと表記している箇所があります)

[PR]
by tempurature | 2016-01-10 16:39 | プログラミング
Exciteブログでは本文中に「open()」ないし「open(...)」などと書けない
タイトルのとおりです。Exciteブログにソースコードを掲載するのはもうやめにしようかと考えているところです。
[PR]
by tempurature | 2016-01-10 01:35
B.メイヤー「オブジェクト指向入門」6.10 演習問題を解く(2)
E6.3

TYPES
- BANK
- ACCOUNT
FUNCTIONS
- deposit : ACCOUNT x INTEGER |> ACCOUNT
- withdraw : ACCOUNT x INTEGER |> ACCOUNT
- balance : ACCOUNT -> INTEGER
- holder : ACCOUNT -> STRING
- changeName : ACCOUNT x STRING -> ACCOUNT
- new : STRING x INTEGER |> ACCOUNT
- open : BANK x ACCOUNT |> BANK
- close : BANK x ACCOUNT |> BANK
- exists : BANK x ACCOUNT -> BOOLEAN
AXIOMS
任意のb : BANK, a : ACCOUNT, c : INTEGER, s : STRINGに対して、
[A1] balance(deposite(a, c)) = balance(a) + c
[A2] balance(withdraw(a, c)) = balance(a) - c
[A3] holder(new(s, c)) = s
[A4] balance(new(s, c)) = c
[A5] holder(changeName(a, s)) = s
[A6] exists(open(b, a), a)
[A7] not exists(close(b, a), a)
PRECONDITIONS
deposit(a, c) requires c > 0
withdraw(a, c) requires c >= balance(a)
new(s, c) requires c > 0
open(b, a) requires not exists(b, a)
close(b, a) requires exists(b, a)

(※exciteブログの制限で、一部openをopenと表記しています)

E6.4

TYPES
- MAIL_MESSAGE
- MAIL_ADDRESS
- FILE_PATH
FUNCTIONS
- body : MAIL_MESSAGE -> STRING
- title : MAIL_MESSAGE -> STRING
- to : MAIL_MESSAGE -> LIST[MAIL_ADDRESS]
- cc : MAIL_MESSAGE -> LIST[MAIL_ADDRESS]
- bcc : MAIL_MESSAGE -> LIST[MAIL_ADDRESS]
- attachedFiles : MAIL_MESSAGE -> LIST[FILE_PATH]
- new : LIST[MAIL_ADDRESS] x LIST[MAIL_ADDRESS] x LIST[MAIL_ADDRESS] x STRING x STRING x LIST[FILE_PATH] -> MAIL_MESSAGE
- newReplyMessage : MAIL_MESSAGE x STRING x LIST[FILE_PATH] -> MAIL_MESSAGE
- newForwardMessage : MAIL_MESSAGE x LIST[MAIL_ADDRESS] x LIST[MAIL_ADDRESS] x LIST[MAIL_ADDRESS] -> MAIL_MESSAGE
- removeMe : LIST[MAIL_ADDRESS] -> LIST[MAIL_ADDRESS]
AXIOMS
任意のa, b, c : LIST[MAIL_ADDRESS], s, t, r : STRING, f, g : LIST[FILE_PATH] m : MAIL_MESSAGEに対して
[A1] (bodyに関する)
[A2] (title...)
[A3] (to...)
[A4] (cc...)
[A5] (bcc...)
[A6] (attachedFiles...)
[A7] body(newReplyMessage(m, s, f)) = s
[A8] title(newReplyMessage(new(a, b, c, s, t, f), s, g)) = "Re: " ++ s
[A9] to(newReplyMessage(new(a, b, c, s, t, f), s, g)) = removeMe(a)
[A10] cc(newReplyMessage(new(a, b, c, s, t, f), s, g)) = b
[A11] bcc( ... ) = c
[A12] attachedFiles( ... ) = f
[A13] body(newForwardMessage(m), a, b, c) = body(m)
[A14] title(...) = "Fw: " ++ title(m)
[A15] to(...) = a
[A16] cc(...) = b
[A17] bcc(...) = c
[A18] attachedFiles(...) = attachedFiles(m)

E6.5

TYPES
- NAME
FUNCTIONS
- newAngloSaxonPerson : STRING |> NAME
- newJapanesePerson : STRING |> NAME
- newChinesePerson : STRING |> NAME
- tostring : NAME -> STRING
AXIOMS
任意のn : NAME, s : STRINGに対して
[A1] tostring(newAngloSaxonPerson(s)) = s
[A2] tostring(newJapanesePerson(s)) = s
[A3] tostring(newChinesePerson(s)) = s
PRECONDITIONS
newAngloSaxonPerson(s) requires match(/^\S+ (\S\. )*\S+$/, s)
newJapanesePerson(s) requires match(/^\S+ \S+$/, s)
newChinesePerson(s) requires match(/^\S+ \S+(| \S+)$/, s)


[PR]
by tempurature | 2016-01-10 01:31 | プログラミング
B.メイヤー「オブジェクト指向入門」6.10 演習問題を解く(1)
E6.1

TYPES
- POINT
FUNCTIONS
- nearlyEqual : REAL x REAL -> BOOLEAN
- x : POINT -> REAL
- y : POINT -> REAL
- rho : POINT -> REAL
- theta : POINT -> REAL
- rotate : POINT x REAL -> POINT
- move : POINT x REAL x REAL -> POINT
- distanceToOrigin : POINT -> REAL
- distance : POINT x POINT -> REAL
- newFromXY : REAL x REAL -> POINT
- newFromPolar : REAL x REAL -> POINT
AXIOMS
任意のa,b,c,d : REAL, p, q : POINTに対して、
[A1] nearlyEqual( x(p), rho(p) * cos(theta(p)) )
[A2] nearlyEqual( y(p), rho(p) * sin(theta(p)) )
[A3] nearlyEqual( rotate( newFromPolar(a, b), c ), newFromPolar(a, b+c) )
[A4] nearlyEqual( move( newFromXY(a, b), c, d ), newFromXY(a+c, b+d) )
[A5] nearlyEqual( distanceToCenter(p), sqrt( x(p)*x(p) + y(p)*y(p) ) )
[A6] nearlyEqual( distance(p, q), sqrt( (x(p)-x(q))^2 + (y(p)-y(q))^2 ) )
[A7] nearlyEqual( x( newFromXY(a, b) ), a )
[A8] nearlyEqual( y( newFromXY(a, b) ), b )
[A9] nearlyEqual( rho( newFromPolar(a, b) ), a )
[A10] nearlyEqual( theta( newFromPolar(a, b) ), b)
[A11] nearlyEqual( a, a )
[A12] if (abs(a-b) > 1) then not nealyEqual( a, b )
PRECONDITIONS
(none)

E6.2

TYPES
- ADT_LEAGUE
- BOXER
- GAME
- WINNER_ENUM := {DEFENDER, NONE, CHALLENGER}
FUNCTIONS
- renew : ADT_LEAGUE x GAME -> ADT_LEAGUE
- better : ADT_LEAGUE x BOXER x BOXER -> BOOLEAN
- makeGame : ADT_LEAGUE x BOXER x BOXER x WINNER_ENUM -> GAME
AXIOMS
任意のa : ADT_LEAGUE, b, c, d : BOXERに対して、
[A1] better(renew(a, makeGame(a, b, c, CHALLENGER), c, b)
[A2] if better(a, b, c) then better(renew(a, makeGame(a, b, d, CHALLENGER)), d, c)
[A3] if better(a, b, c) then better(renew(a, makeGame(a, c, d, CHALLENGER)), b, d)
[A4] better(renew(a, makeGame(a, b, c, DEFENDER)), b, c)
[A5] better(renew(a, makeGame(a, b, c, NONE)), b, c)
PRECONDITIONS
makeGame(a, b, c, e) requires better(a, b, c)


[PR]
by tempurature | 2016-01-10 01:23 | プログラミング
ISE EiffelStudio GPL Editionをインストールしました
無料で使えるEiffelを探して入れました。最初、GPLのEiffelであるSmart EiffelとLiberty Eiffelを試してみましたが、エラーが発生してWIndowsにもUbuntuにもインストール出来ませんでした。

そこで、Eiffelの商用製品であるISE Eiffelの無料版がGPLライセンスであるということで、早速インストールしました。


最初、Windows8にインストールしたのですが、対応バージョンがWindows7までということで、正しく動作してくれませんでした。

次に、Ubuntuにインストールしました。こちらのほうは正しく動作してくれたので満足です。それにしても、EiffelStudioの起動は不気味なくらい速くて、感心しました。

(追記) Windows8でもWindows7モードで動作することを確認しています。

[PR]
by tempurature | 2016-01-08 01:04 | プログラミング
オブジェクト指向入門の第35章を読みかじった(2)
35章を読了しました。

前にも一回読んだことがあるかもしれませんが、この章は格別おもしろいです。メイヤー教授の毒舌プログラミング言語談話。ちょっと紹介しておきます。

Simula : 大絶賛
Smalltalk : ゴミ(動的型付けonly→効率悪い)
Lisp : 敬遠(メイヤー教授がS式を受け入れられていたら、Eiffelを作ってなかったと思う)
Objective-C : 普通
C++ : 嘲笑
Java : 上から目線
Sather : スルー

ちょっと誇張が入っています。

オブジェクト指向入門は、買って損はないですよ。
(エイホとタネンバウムも古漬けにしているんだよなー)


[PR]
by tempurature | 2016-01-06 19:29 | プログラミング
プログラミングHaskellの第8章「関数型パーサー」を読解中(1)
hugsで、プログラミングHaskellのp.92、連結演算子(>>=)のところまでコンパイルを通しました。だがしかし、この先のコンパイルが通らない!!

{- p.93の下のほうにある式。コンパイルが通らない。
p' :: Parser (Char, Char)
p' = do x <- item
        item
        y <- item
        return' (x, y)

{- これも通らない。
p'' :: Parser [(Char, [Char])]
p'' = do x <- item
         return' x
-}

-- そこで、上記の意味をdo, >>=を使わずに読み解いてみました。
-- パーサーpの構造がこのようになっていることはわかったのですが…
p'' :: Parser (Char, Char)
p'' init = [((v1, v3), snd (head p3))]
           where
            p1 = item init
            v1 = fst (head p1)
            p2 = item (snd (head p1))
            v2 = fst (head p2)
            p3 = item (snd (head p2))
            v3 = fst (head p3)

-- とにかく第8章は一筋縄ではいかなそうです。もう少し頑張って見ます


[PR]
by tempurature | 2016-01-06 00:25 | プログラミング
プログラミングHaskellの第8章「関数型パーサー」の替え歌を考えてみた
プログラミングHaskellのp.91には、次の詩が紹介されていました。

A parser for things
Is a function from strings
To lists of pairs
Of things and strings

パーサーは関数
文字列をもらって
結果と文字列をもどす
組のリストでもどす

この詩はDr. Seussの替え歌らしいのですが、私にはなじみがないのでなんの面白みもなかったです(あたりまえ)。

なので、自分なりにパーサーの歌を考えてみました。


パーサーや
言の葉をそぎとし
合いの子桐箱へ


つまりこういうことです。

パーサーや type Parser =
言の葉を String ->
そぎとし a
合いの子 (a, String)
桐箱へ [(a, String)]

type Parser a = String -> [(a, String)]


こんな感じです。気に入りましたら使ってやってください。

[PR]
by tempurature | 2016-01-05 23:05 | プログラミング
オブジェクト指向入門の第35章を読みかじった(1)
Bertrand Meyerの「オブジェクト指向入門 第2版 方法論・実践」の第35章以降が面白そうなので、ちょっと読んでみました。

その中で最初に紹介されていた言語がSimula67なのですが、Simula67のコンパイラがなかなか見つからなくて困りました。

具体的にはCygwinにもapt-getにもない。オープンソースではGnu Cimというのが使えるみたいなので、Ubuntuにインストールしました。すんなりインストールできました。

[Gnu Cimの配布元サイト]

wikiで、一番短いsimulaのソースコードは、

Begin
End;

という2行の記述らしいので、こいつをコンパイルしてみました。
ワーニングがどっさり出ましたが、コンパイルと実行をさせることができました。


[PR]
by tempurature | 2016-01-05 00:43 | プログラミング