NoahOrblog

某・福島にある大学のコンピュータ理工学部の大学生のお話。

【レビュー】グッド・マス

Noahです。

積読が溜まりに溜まってどうしようもない、読んでそれっきりだと身にならない、のでレビューなり感想なり書いておこう、という話。

記事としては、とても短いです。(大学の課題を処理する前に書いている)

読んだ本、グッド・マス

グッド・マス ギークのための数・論理・計算機科学

グッド・マス ギークのための数・論理・計算機科学

なお、自分の数学の知識はほぼ皆無です。

高校は商業高校だったので微積でさえ少ししかやっていなく、そもそも高校数学に関しての知識がほぼ全く無いため、大学入学以降、関心はあるのですがいかんせん全く出来ない自分でも、自然数無理数の話から、黄金比、エジプト分数、特に第4部の論理、第5部の集合、第6部の機械じかけの数学、は読んでおいてよかったな、と思います。

よくある数学の堅苦しい専門書とかではなく、さらに初見殺しと言わんばかりの記号が複雑に絡み合うものでもなく、あくまで読みやすく、わかりやすい文章で、自分がもともと以前から関心のあった、群論オートマトンについても浅くではあるがどんなものかを知ることが出来た。

第6部の後半、24章のラムダ計算からは、カリー化や部分関数適用、遅延評価やコンビネータなどのHaskellでおなじみのアレやこれやがふんだんに書いてあったのでとても美味しかった。

おわり

Haskell(というか主に遅延評価)について

この記事はAizu Advent Calendar 2016 18日目の記事です。
前の人は、@lycoris0731 さん、次の人は @nktafuse さんです。


自分のこと

Noahです。学部一年です。
特に好きな分野とかは無いのですが、今回は『Haskellいいぞっ』という点と、Haskellの評価戦略(主に遅延評価と正格評価のこと)を書いていきたいと思います。
自分も初めて半年も経っていないのでわからないことも多いのですが、その点はご了承ください。

Haskell とは

f:id:NoahOrberg:20161217192140j:plain
関数型言語です。関数型言語の定義とは、

何をもって関数型プログラミングとするか、関数型プログラミングを行っているコミュニティ内でも正確な定義や合意というものは存在しないが、一般的には、手続き型プログラミングがコマンド実行の列としてプログラムを記述していくのに対し、関数型プログラミングは複数の式を関数の適用によって組み合わせていくプログラミングスタイルである、ということは広く認められている。 by 関数型言語 - Wikipedia

つまり、Cなどが代表される手続き型言語は、

// nは任意の数
sum = 0;
for (i = 0; i < n; i++){
    sum += i;
} 

このような感じで、命令を並べ、順番に実行するのに対し、関数型言語(今回はHaskell)では

sum' :: Int -> Int  --sum'としたのは、すでにsum関数がすでにPreludeというモジュールに定義されているからです。
sum' 0 = 0
sum' n = n + sum' (n - 1)

このように、関数の適用を組み合わせてプログラミングします。(この例では再帰を利用して0-nまでの合計値を出しています)
forは特にそうなのですが、変数に値を代入する行為、いわゆる副作用を排除した考えを関数型プログラミングでは用います。そのため、for(一応、forのようなものはHaskellに存在はするが)は、基本的にはあまり使いません
Haskellでは変数に値を入れることを束縛といいます。
値を束縛することで、変数を利用します。
一旦束縛したら、中身は変えられません。これは副作用を無くすことで生まれる参照透明性を確保するためです。
そんなの不便じゃないか??と思う方もいらっしゃると思いますが、プログラミングスタイルに慣れればこれは理にかなっているものだと感じられるようになります。

関数色々

Haskellは関数を第一級オブジェクトとして扱います。
つまり、関数を変数に束縛することや、関数の返り値として関数を返すことも可能です。
関数を引数に取る例としてmap関数があります。

map' :: (a -> b) -> [a] -> [b]
map' _ [] = []
map' f (x:xs) = f x : map f xs

一番上に書いてあるものは関数の型宣言です。

f :: Int -> Int  -- Int型を受取り、Int型を返す
g :: (Int -> Int) -> Int -- Intを受け取りIntを返す関数、を受取、Intを返す。 

map関数は、a型を受取りb型を返す関数(f) と、a型のリスト( (x:xs) ) を受取り、a型のリストの中身それぞれに関数を適用した値(b型)をリストにして返す関数です。
rubyなどのmapメソッドと同じ挙動ですね。
ちなみに、関数の型宣言で用いられているIntのように最初の文字が大文字のものは型ですが、aなどのように最初が小文字なものは型変数といい、任意の型(CharやInt, Integerなど)にできます。
更に、リスト (x:xs) で、リストの先頭要素それ以外の要素に分けて名前を付ける事ができます。
(:) はコンスと呼ばれる関数で、Lisp等のconsとおなじだと考えればいいです。

遅延評価と正格評価

Haskellの大きな特徴として、遅延評価を採用している点があります。
CやRubyなどでは、標準で正格評価を行います。
遅延評価が採用されると何が嬉しいかというと、簡単な例では無限リストを扱えます。

ghci > take 3 [1,2..]
[1,2,3]

[1,2..]は、[1,2,3,4,5,...100,...10000000,....]と続く無限リストです。
take関数は、引数として与えたリストから指定された分だけ、先頭要素からリストにして返します。
普通こんなものを扱うと引数のリストを評価するために無限に処理が行われますが遅延評価を評価戦略にしていると、必要な分だけ処理するので、上記の例では先頭要素3つ分だけ評価します。
他の例では、たらい回し関数と言うものが有り、

tarai :: Int -> Int -> Int -> Int
tarai x y z
  | x <= y = y
  | otherwise =tarai (tarai (x - 1) y z) (tarai (y - 1) z x) (tarai (z - 1) x y)

以下にRubyでのコードも記述します。

def tarai(x, y, z)
  x<=y ? y : tarai(tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y))
end

そして、引数として(10, 5, 0)を与えたときのHaskellでの実行時間と、Rubyでの実行時間は以下の通りです。

*Main> tarai 10 5 0
10
(0.01 secs, 90,672 bytes)
% ruby tarai.rb
      user     system      total        real
  0.020000   0.000000   0.020000 (  0.015592)

そんなに変わりませんね。体感時間でも両方一瞬で終わります。
次に引数として(14, 7, 0) を与えたときです。

*Main> tarai 14 7 0
14
(0.01 secs, 99,784 bytes)

Haskellは変わりません。しかしRubyの方は、、、

% ruby tarai.rb
      user     system      total        real
 24.420000   0.090000  24.510000 ( 24.838016)

totalの時間が (10, 5, 0) のときより遥かに大きくなっています。
なぜこうなったかというと、Haskellの遅延評価が上手く効いているのです。
たらい回し関数では関数を実行する際に、引数(x', y', z') = ( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y)) [ 区別を付けるために引数はx', y', z'にしています ] のなかでx', y' を評価し、 y'<=x' となったときは、z'の部分は利用されず評価をしても値を利用することがありません。
遅延評価は、必要になったら評価する評価戦略なので、x'<=y'となったときには評価に不要なz'部分は評価せずに素直にy'を返します。
otherwise、つまりそれ以外になって、z'が必要になったときに初めてz'を評価するのです。


最後に

以上です。少々間違いもあるかもしれませんが、関数型やる人が増えてほしいなと切実に思います。

参考にしたサイトなど

Haskell
時間の計測

おわり

数学ガールとやら

Noahです。

数学ガールを最近ちまちま読んでます。

なにしろ自分は、ここやTwitterに何回書いたか分からないけれど、兎にも角にも数学弱者なので勉強しようと思っても大学講義の微積Iや力学はさっぱりわからなかった。

微積分を高校時代に数IIの範囲までしかやってなかったので地獄を見ることは分かってた。分かってはいたんだ。

一ヶ月くらい前だが、同じクラスの数学好きな某氏に「数学ガール」なる本を勧められて、ちょうど数学のレポートに読書感想文(?)があったので読んでみた。

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)

数学ガール/乱択アルゴリズム (数学ガールシリーズ 4)

その本にコンピュータ理工学らしく「乱択アルゴリズム」を選んだわけだが、

線形探索や、二分探索などのオーダ記法のところは、

応用情報や基本情報の取得の際に覚えはしたものの理屈では分かってないところもあったのだが、やっとこの本で理解できた。

(試験を受けた当時は log n なんていうのも理解はしていなかった。高校生なのに。)

少々難しかったがなんとか最後まで読んだ。(理解しているかはさておき。)

何周かする必要がある。繰り返し大事。


そこで、先日「数学ガールの秘密ノート」シリーズを思い出した。

数学ガールの秘密ノート」シリーズのほうが易しいことは数学好きな某氏や先輩に聞いていたので、長期貸出を行っている大学内の図書館から、

微分を追いかけて」、

数学ガールの秘密ノート/微分を追いかけて

数学ガールの秘密ノート/微分を追いかけて

「数列の広場」、

数学ガールの秘密ノート/数列の広場

数学ガールの秘密ノート/数列の広場

「ベクトルの真実」

上記三冊を借りることに成功。

それが今日の昼過ぎくらいの出来事だったが、未だ選んだ一冊目の「微分を追いかけて」の2章程度までしか読んではいない。

が、最初の最初から教えてくれるのが自分のような人間には、本当にありがたい。

一ヶ月は借りれるので何周か周って読めると思う。…思う。

資格試験とか大学とか

Noahです

推薦入試で某コンピュータ理工学の公立大学に入って、なんとなしに半年程度過ごしてきましたけど、

プログラミングを高校時代、趣味の範囲でやってるだけで高校ではCOBOLとかいう化石を触ってたのでそもそも大して出来るわけではないですが、なんとかCからやっていけてるので安心。

先輩方のすごいHな本(すごいHaskellたのしく学ぼう!)の読書会に参加したり、オブジェクト指向としてや、TwitterAPIを叩くためにRubyを触ったりしながら、最近はとにかくプログラミングしかやってませんけど、

友人がそういえばIPA情報処理技術者試験受けると言っていたので、自分の体験記として、高校時代を忘れないように備忘録しておきます

動機

そもそもこの試験を知ったのは高校1年でした。

高校2年で、公益財団法人全国商業高等学校協会の主催する地方大会、全国大会でそこそこいい成績残せてたので、なし崩し的に基本情報を受けることに。

基本情報技術者試験は、午前試験、午後試験とに区分が分かれており、両方で合格する必要がある。

午前は小問80題、四択のマークシートであり、60%正答で合格。

分野は、テクノロジ系、マネジメント系、ストラテジ系などで試験範囲は広い。そして浅い。

午後は大問13題から7題解く。午前と同じく60%正答で合格。

具体的には、大問1はセキュリティ問題で必須。配点は12点

大問2-7は、DB、ネットワーク、ソフトウェア設計、などなどから4題選択。配点はそれぞれの大問で12点

大問8は擬似言語。必須。配点は20点と高い

大問9-13は各種プログラミング言語表計算は楽。COBOLムズい(あくまで個人的感想)。配点は20点。

基本情報では、自分は一回落ちてます。COBOLで受けてはいけない。合格したいなら表計算だ。

因みに配点はうろ覚えなのであまり参考にしないでください。

使用した参考書

平成28年度【春期】【秋期】基本情報技術者 合格教本

平成28年度【春期】【秋期】基本情報技術者 合格教本

最初は合格教本をサラッと読んで、あとは過去問ばかりやるだけ。

一回目の受験までで大体5ヶ月程度かけて、一日三時間程度過去問と向き合って、

一回コケてからは一日1時間は過去問と向き合って知識忘れないように半年継続して勉強。

正直、午前は過去問ばかり出されるので、過去問をやってれば(暗記してしまえば)大して心配することはないが、

午後は少しひねられる上に、擬似言語で躓くときが多々あるので注意。

しかし結局午後も問題に慣れれば本番で躓くこともないと思われます。

応用情報

そして基本情報は合格した後、部活の顧問に次のレベルの応用情報技術者試験を勧められ、某コンピュータ理工学の公立大学に入ろうとこの頃に決めていたので受験。

基本情報をやってだいたい情報処理技術者試験の出題傾向がわかったので、難しいことはなかった。

応用情報技術者試験は基本情報と同じで、午前試験、午後試験の両方に合格する必要がある。

午前試験は、基本情報の午前試験に少し深いところまで突っつく感じのレベル。基本情報もだが、過去問をそつなくこなせるようになれば受かることだけはできる。60%正答で合格。

問題は午後試験だが、午後試験は、大問11題から5問選択。それぞれおそらく配点は各20点だと思われる(自己採点ではそのように採点した)。60%正答で合格。

大問1はセキュリティ。必須問題。

大問2-11では、経営戦略、プログラミング、DB、ネットワーク、ソフトウェア開発、マネジメントなど、多くの中から4題選択。

基本情報に比べ問題数が少ないが、大半の問題は「記述式」である。

国語力が試される試験なのかコレ、と、疑問になるが国語力は重要。

文字数制限の有る記述式なので、簡潔に、分かりやすく書く必要がある。

使用した書籍

(PDF・スマホ単語帳付)徹底攻略 応用情報技術者教科書 平成28年度(2016年度)

(PDF・スマホ単語帳付)徹底攻略 応用情報技術者教科書 平成28年度(2016年度)

2016 応用情報技術者 午後問題の重点対策 (午後対策シリーズ)

2016 応用情報技術者 午後問題の重点対策 (午後対策シリーズ)

午前問題は過去問をそつなくこなせるようになればいいので、午後を重点的に勉強する。

自分の場合、問題慣れする必要があるので、最低でも3年分、6回はこなした。

教科書というものは補助的に使い、ほとんどは過去問をこなす。

基本情報である程度インプットしていたので、今回はインプットはそんなにしなく、ひたすらアウトプットばかりしたのでノートはかなり消費した。

12月から勉強を始めたので実質勉強時間は4ヶ月で一日4時間程度。

過去問をやりすぎると問題を見た瞬間に答えが浮かぶようになるが、それでは本質を理解できてないので理解するまでこなす。

おかげで応用情報は一発で取れた。


以下の書籍も少々使った。が、応用情報の取得には過去問をやるのが一番なので軽く触れる。

マスタリングTCP/IP 入門編 第5版

マスタリングTCP/IP 入門編 第5版

マスタリングTCP/IP 情報セキュリティ編

マスタリングTCP/IP 情報セキュリティ編

ネットワークの知識を得るため。当初はネスペ、セスペを高校時代で合格することが目標(いや今も取れてないけど)だったので、購入。ネットワークまわりの知識が得られる。大きい本。

プログラマのための論理パズル 難題を突破する論理思考トレーニング

プログラマのための論理パズル 難題を突破する論理思考トレーニング

これは、午後問は頭をつかうので頭の体操にと購入。

しかし、試験を受けた当初はまだ自分のレベルが足りてない上にこの本は難しい事この上ないので現在積み中。いずれ解くぞ。


こんな感じで書いててふと思ったけど大学に入ってからは、やれ微積だ、やれ線形代数だ、やれ力学だのと数学関連で血反吐を吐くはめになったのだが、これは紛れも無く商業高校から理工系大学にはいった宿命とも思われる。

その度に高校時代俺何やってたんだろうな…と思うことも多々あるので、某コンピュータ理工学の公立大学に推薦入試で入学を考えている商業高校の受験生の方々は基本情報や応用情報を勉強する前に数学Ⅲまでをしっかり履修するべきだと思います。

(あ、でも資格ないと推薦もらえないっけ…?)

iTunesでCD読み込めない

先日MacBookProを購入しました

f:id:NoahOrberg:20160324204603p:plain

早速iTunesに音楽を入れようと、外付けのドライブでCD読み込もうにも

”no error

と、ダイアログが出るだけでトラック名とか諸々読み込めない

いろいろ調べてプロキシがなんとかとかやったけどできなくて、最終的に以下のコマンド実行してファイル消せば出来た。

cd ./Library/Preferences/
rm com.apple.iTunes.*

ハッカーと画家

立ち読みしてたらなかなか面白かったから購入。

買ったのはちょっと前で、読んだのも最近だけど。

あまり考えずにさらさらと読んだから、あまり、理解はしていないけど、ただ、Lispが素晴らしいという事は理解できた。

Lispみたいな妙な構文を持っているものはあまり触りたくないし、ましてやEmacsならまだしもVim使ってるから余計関わりがない。

でも、絵の線を描く時みたいに適当なコード作っては走らせて改良してまた走らせてまた改良して…っていうのは、確かにわかる気がする。

高校の授業では、『まず流れ図(フローチャート)を作り〜』から始まって、『コーディングをして〜』という方式で、その時はそれが普通だと思い込んでたけど、内心『それくらいの処理なら直接コーディング出来ることない?!』とか思ってたけど、それから徐々に試作的なものを作って形作る方式に変えてったな…

授業ではCOBOLだったからかどうかわからないけど、実行する機会は殆どなくてコーディング用紙とか言う紙にコード書いて、後は先生のチェックとかそんなんだったし(笑)


とか書いてて色々高校生活であった事を思い出したりしなかったり。

大学から出てる課題終わらそー、、、

yacc/lex覚え書き part1

なーんかYaccとLexについて書いている所が少ないので、備忘録として書いておく。

Yaccとは何かというと、

YaccYet Another Compiler Compiler、ヤック)はパーサジェネレータの一つである。1970年代にAT&TUNIX用にステファン(スティーブ)・ジョンソン英語版が開発した。--Yacc - Wikipedia より

んで、Lexはというと、

Lex(レック、レックス)はレキシカルアナライザ(字句解析プログラム、字句解析器)を生成するプログラムである。コンパイラの作成のためにパーサジェネレータyaccとともに使用されることも多い。 --Lex - Wikipedia より

という事らしい。

要は、コンパイラの処理手順の、"字句解析"をLexが、"構文解析"を、Yaccが行っている

それぞれの書き方はまた次回。