2016年12月24日土曜日

この世界の片隅に 映画を見てきた

はじめに

『この世界の片隅に』は原作のファンだ。こうの史代さんのファンだ。ぼおるぺん古事記も読んだ。最近の作品がフォローしきれていないのが残念だ。

クラウドファウンディングをしていたのは知っていた。やり方を知らなかったし、成果の見えないものに投資するっていうのがなんか抵抗があったのでしなかったが、今になって「ああ、こういう結果につながるのか」と思ってなんかぐっときた。応援いいなと思った。

感想

  • 漫画とは違う。だが、どちらもよい。
    • 原作を知っていて、調べが半端じゃないということを知っているからだろう
      ”ああ、あの作品がこんな立派な姿になって、、、”という感動があった
  • 万人には勧めがたい。アクションやラブシーン、急展開があるなどの
    映画的にわかりやすいシーンが少ない。
    どこまでいっても、どこを切り取っても”日常”が描かれている。
    • あ、そうでもないか。ひげもじゃの人とか、座敷童とか、非現実要素もある
    • メリハリがはっきりした作品が好みの人は”ぼんやりしてたなあ”って思うかも
    • 戦時中の話で、広島で、、、だが、それを含めても”日常”であった

漫画と映画との主な違い

  • (当然のことながら)いくつかのサブストーリー、重要なシーンがカットされている
    • りんさんをめぐる話の大幅カットは印象的
      • 漫画読まずにあの紅の意味が分かる人おらんやろ
      • 逆に、漫画につなぐ伏線?
  • 漫画のようなわかりやすい切り替えがないため、オチがわかりづらくなっている
    • 憲兵さんのシーンを見て、苦笑いしかない
    • 漫画だと「クスッ」ってなるシーンと思うのだが
  • 感情の動きがとらえやすくなっている
    • 生々しい動きや声の与える印象はやばいですわ、、、
  • 各所で”考証や調査をこれでもかとばかりにしています”と喧伝しているだけあって
    風景や状況描写をみて、ああ、こういうふうなのか、、、と実感できる気がする

事前に勉強しておくとより楽しめるかも?

※ 二度目以降に鑑賞するとき、かも
※ 原作は読むか読まないか好きにしたらいい
  • 呉に停泊する戦艦の略歴と時期
    • 大和、利根、青葉、龍鳳、伊勢、他
    • とくに駆逐艦は名前すら出てこない、のに、船の数など調べこまれている
  • 呉の地形図、写真
    • 現代のものでよい
    • 戦前、空襲被害のものがあるとなおよい
  • 呉への空襲とその被害状況
    • 作中に描かれる空襲警報や空襲の一覧が多すぎてビビる
    • 絨毯爆撃を受けるようになったのはいったいいつごろからなんだろう

最後に

そもそも映画の評判を探してこのサイトにたどり着く人などいないだろうがそれでも言いたい

この、リアルタイムに上映しているという、変な熱気があるうちに、見ておいたほうがいいよ

と。


近況メモ

このところしていること興味を持っていることやっていることメモ

技術面

  • LINE bot award を知ったのをきっかけにpythonを始めた (2か月)
    • ライブラリの充実感がやばい
    • ネット上の情報量がやばい
    • 落とし穴の少なさがやばい
      • ある程度ほかの言語を知っているからかな?
      • ないわけではない。一つはまってる
      • 日本語関連がドツボ、なんだバイト文字列とユニコード文字列って
  • 個人的なデータ整頓の嗜好性にマッチ思想だったので Neo4jを始めた(1週間)
    • だがどう活用するかは検討中
  • DeepLearningについて学ぶ機会が増えた(期間3~4か月、手をほとんど動かしていない)

遊びほか

  • 艦これACにドはまりした、ただ、消耗も激しく、もういいかな感がすごい(3~4か月)
  • 艦これACがきっかけで艦娘と戦艦と史実に興味を持ち始めた
    • pixivのフォロー数が1000超えた。ワッハッハッハッは
    • いくつかの人気作品(おおいときたかみ、The last one week、リョーサン氏の作品)や
    • そして「史実で艦これ」がどっぷりのきっかけだった。そういう人意外と多いのでは?
  • 艦これがきっかけで、以前からやってみたかった”お絵かき”を練習し始めた
    • 下積みがないのでさしあたり5年後にプロ並みを目指そうかと
    • 下手なりに作品を出す、、、のが怖いのでそこをどうしようか困っている
    • 出したことが”やめるきっかけ”になることが個人的に多い

そのほか印象的だった出来事

  • VPN環境を作ってリモートから自宅サーバーにアクセスできるようにした
  • 投資で、インデックス投資や低位株さがしをやめて、うねり取りを始めた
    • ボロ負け中、まだまだこれから
  • 上野は東京国立博物館にて「禅」展を見に行った。
    • 絵や彫像がもろに宣伝や教材っぽい
    • だがその中にも”すごみ”や”執念”とか”美しさ”も感じられた
    • あと、禅画っていうテンプレがあるっていうのも面白かった
  • つい最近:この世界の片隅に、を見に行った。
そのうちまた面白いものを作って公開したい、、、という予定。技術系の記事はここじゃなくてQiitaに投稿しようかなって思うよ。かけそうならね。

2016年6月22日水曜日

第05期の区切り、またしばらくブログはお休み

第05期は、自分にとってLispと人工知能の時期でした

Lispに関する記事で初めて他の人に役に立つ情報を発信出来た。やったぜ。

bloggerに書いたこと以外でしていたこと

  • 人工知能の勉強を始めた。全部AlphaGoが悪い。成果は上がっていない。
  • やっと仕事に対する態度を自分なりに変えることができた。
  • PS4で遊んでいる。Witcher3, GravityDaze, MirrorsEdgeCatalyst,,, 堪能している。
  • ダイソンの掃除機を買った。吸いまくる。超楽しい。
  • インラインスケートとボルダリングを始めた。これはじっくり楽しい。
  • 投資の実践がやや進んだ。売買に慣れてきた。
  • 考え方とか対人関係の関係とか、そっち方面の自己啓発に足を突っ込んでみた。

期間情報

開始日:2015/08/15
終了日(宣言上):2016/04/29
日数:258日(約8か月)

最後の記事:2016/03/25

記事の更新はしていないのだが、Lispはちょっと続けていた。また何か情報を発信できるように頑張ってみたいが、無理はしない。

2016年3月25日金曜日

人工知能学習の参考図書:100万人の人工知能

初めに

ここのところ、Lispを少し離れて、人工知能について勉強している。AlphaGoやDeepLearning,TensorFlowの流れを受けて興味を持ったのだが、私自身の興味について考えるうちに、機械学習、深層学習ではなく、いわゆる「第五世代コンピュータ」の古い世代の人工知能、というより、知識の表現方法に興味を持った。

そこで各種の古い本を、図書館で借りては読んでみているのだが、その中でもこの本は、平易で、プログラミングやprologについての知識が多少あれば、古き良き人工知能の入門書としてとても良いのではないか感じた。


本の特徴

Prolog, Lisp による人工知能の開発が盛んだったころの入門書だったと思われる。主な話題は、Prolog言語による人工知能の実装について、基盤となる技術や考え方が書かれている。

簡単な例を多く取り上げて話が進められる。一つ一つの考え方やPrologでの処理の進み方を丁寧に追いかける。巻末にスリット式のステップ実行サンプルがついているという念の入りようである。s読者に考えを促す「Think」と書かれたコーナーが数多く準備されている。著者の回答が上下反転した文章で印刷されているのが印象的である。

本の中で取り上げられている話題と例

  • 第一部
    • 意味ネットワークとProlog 言語による表現
    • Prolog言語にその内容について質問する方法
      • 4人の男女の「好き・嫌い」をProlog言語で表現してみる
    • 連鎖する知識から結論を引き出す「規則」の定義
    • 新しい知識をコンピュータ(Prolog)に覚えさせる方法
      • キスをした4人の男女とカゼの連鎖
    • 再帰的な規則の定義方法
      • 病気持ちの家系図から「おたふくかぜ」持ちの親戚を持つ人を探す
    • 簡易版エキスパートシステムの実装
    • リストによる知識の扱い方の基礎
      • 羽をもち、長い首を持ち、飛ばない動物は?
  • 第二部
    • 知識を条件として持つ知識の扱い方
      • オペレーターチャート(?)
        • これが何か説明はできないが、していることはわかる、、、
    • 確率を伴う知識の扱い、ベイジアン、ファジイ、
      • ライトが切れているスクーターのバッテリーが上がっている確率は?
    • 簡単な黒板システムの実装
      • 今ミサイルを発射すべきか?
    • 学習の基礎、パターンから事実を推論する方法
      • 日焼けしやすい肌の色と髪の毛を事実から推論できるか?
        • コード例はなし。残念。
  • 第三部
    • 実際に動いているシステムの概念紹介、いずれも概念説明のみ
      • STRIPS
      • ABSTRIPS
      • MOLGEN
      • SAVOIR
      • HEARSAY
      • EXPERT-EASE
      • AM, EURISKO
      • ACT
    • 知識工学用のトゥール(13章)
      • 言語、エキスパート・システム、知識獲得用トゥール、知識工学の環境
  • 第四部
    • コンピュータは知的な生き物か?
    • いずれも「知識」とは何かの説明で難解である

この本の良かった点、そうでもない点

まず良い点は
  • 古き良き人工知能についての基礎知識を与えてくれる。その一部は今でも古びない
    • ベイジアンとか。
    • 知識ツリーとか。
    • 学習の基礎とか。
  • たいへん平易な例で作られているため、読み進めやすい。
    • 入門書としてとても良いように思われる。
  • 昔に存在した人工知能関連のシステムについて情報を得ることができる
    • 参照が3ページ
    • 知識工学用ツールの提供企業の名前と住所が載っている!
それからそうでもない点は
  • 2016年現在最新の話題には触れる気配もない
    • 深層学習、機械学習(少々触れてはいるが)
  • 後半部については今では古びていて生かすのは難しい
    • 古いシステムについての解説、解説だけなのでまた生かしづらい
    • 第四部に至っては実装や知見よりも「哲学」に近いのではないかと思う内容

この本の役立て方

この本をうまく使える人は果たしてどのような人かと想像すると
  • 人工知能について興味はあるが断片的な知識しか持っていない
  • 古い人工知能の実装に興味がある
  • 古い人工知能の研究について興味がある
  • 今書店に残っている本や情報が難しすぎると感じている、実装例が足りないと感じている
  • もっとPrologでプログラミングをしてみたいが、どの本も難しすぎる
である!、、、。あまり最近の人工知能の学習書をちゃんと呼んだわけではないし、こんな読者本当に居るのだろうか、、、?

とりあえず私が言えることは、図書館で見つけたらぜひ立ち読みしていただきたい一冊である。ということである!


2016年3月2日水曜日

CommonLisp の負の数のビット表現、ドはまりした話

初めに

Common Lisp のビット演算について調べていた私は、lognot 関数の出力を確かめようと (format t "~b" (lognot #b10110100)) のようなコードを書いていた。
しかし、その結果が -10110101 となっているのを見て、一瞬納得しかけたが、、、おかしい。本当は 01001011 ではないのか。いやまて。これは明らかにおかしい。思っていたのと違う!違うやろ?
いったい何が起こっているのか?謎を解くために私は調査に乗り出した。

概要(ネタバレ注意)

  • format 関数は、負の数値をバイナリ表示する際、
    通常の整数同様に符号部と整数部に分け、整数部のバイナリで表示する
    • ((format t "~b" (lognot #b10110100))) ;-> -10110101
    • 期待しているのは、あくまで2の補数として表現した場合の値
    • ((format t "~b" (lognot #b10110100))) ;期待は... 01001011
  • format 関数の定義では、~Dと同じに出す、基数だけ2にすると書いてある
    • その原因はおそらく、Common Lisp の”普通の整数は無限に桁が続く”仕様にあると思われる
  • 自分なりに負の数もビット表現できるような方法を考えた
  • ビット反転を伴う計算をするときぐらいにしか、おそらく問題にはならないだろう。
  • 脳内で何とかする方法として:表示された値に対して、ビット反転した値 + 1 を求め、そこに 最上位ビット 1 を加えた値が本来表示したい値である。
    • -10110101 -> 反転 -> 01001010 -> +1 -> 01001011 -> 後は最上位ビットを加える

参照

format関数でのバイナリ値の表示

最初に気付いたのは、すでに書いているが、lognot関数 の値をformat 関数に与えると、思っていたのと違う値として表示されることだった。例えば次のようになる。ちなみに、この記事は全体に SBCL 1.2.13 で動作を確認している。

* (defun show-bin (value) (format t "~b" value))

SHOW-BIN
* (show-bin 128)
10000000
NIL
* (show-bin (lognot 128))
-10000001
NIL
* #b10000001

129
* (show-bin -129)
-10000001
NIL
* (show-bin #b10110100)
10110100
NIL
* (show-bin (lognot #b10110100))
-10110101
NIL

うーん。いくつか結果を出して、その結果を計算してみて分かったのだが、どうも、format 関数は符号と整数部を分けて表示している感じがする。いや、している。
うーん。うーん。なるほどね!そうだよね、数値は符号と整数部に分けられるからね!そうだよね!。。。ちがわい。期待しているのは、ビット反転した値だわ。表示されているのは負の符号と、整数部の正のビットの値だわ。そうじゃないだわ。

~b表示 期待する表示 補足
128 10000000 0000 1000 0000
(lognot 128) -10000001 1111 0111 1111 = -129
-128 -10000000 1111 1000 0000
(lognot -128) 1111111 0000 0111 1111 = 127
-3 -11 1101
3 11 0011

こうだろ!?そうだろ!?CとかC#だったらそうしてくれるんじゃないかね!?

確認結果:format関数の仕様だった

ま、しかし、こういう挙動が起こった場合、それはCommonLisp においては「仕様を知らないだけだがね」ってなる。今回の場合も、おそらく仕様だろうと決め打って調査を開始した。
そしたら案の定だわ。format 関数の定義の一部に、~bの表示の仕様というページがあり、そこには次のように書かれていた。

~D のように表示しますが、基数のみ 2 とします。

と書いてある。~D は、意識することはないが、普通にしていたらたしかに「符号」と「整数部は正の整数で」出してくれる。すなわち、負の数値はあくまで - を付け、整数部は正の整数で表示するという仕様である。負の数値のビット表現については、とくに考慮しない。~dの表示の仕様 も確認してみたが、負の数のビット表現に関する記載は、見つけられなかった。

他に、他の表示関数 write や、表示の帰趨を決定するスペシャル変数 *print-base*を確認してみたが、負の値を私が求めているようなビット列として表示する方法に関する仕様は見つけられなかった。

なんでそうなるのか?ビット演算と2の補数に関して

Common Lisp は私が生きているよりずっと長く、私よりもはるかに賢い人たちにもまれた言語である。今は漬け込まれている。(その存在に気付いた人がおいしく食べていく)したがって、そうしているのには理由があると思われた。あるいは、”そうしないと決めた理由がどこかにあるだろう”と想像された。

ここまでの調査でひとまずわかったこととして。負の値となるような計算結果について、format 関数が、あるいは私の調べた範囲のCommonLisp の標準仕様が、思い通りの挙動をしてくれないことはわかった。しかし、どうしてこのような挙動をするのだろうか?調べていったところ、Common Lisp の整数値は、無限に桁数を持つことができる、という仕様がかかわっているように思われた。

無限に桁数を持つ整数と、負の値の表現

CommonLisp で、SBCLで初めて ビット演算を試したとき、どうやら私は暗黙に有限桁数のビット列を想像していたようである。16ビットなり、8ビットなり、64ビットなりで表現された数値を想像している。そして、暗黙にsigned, unsigned について区別して考えている。そうした場合、負の数はたった一つの表現を得ることになる。符号なしであれば、符号ありの場合に負の数にあたるビット表現に対しては、正の整数が与えられる。しかし、CommonLispの整数は違う。無限の桁数を持っている。無限に桁数を持つということはどういうことか?考えてみるにそれは、有限桁で区切ると、「そのビットより上位側のビットが0なのか、1なのかわからなくなる」ということである。

例えば、整数値を8ビットで表現してみました!といって次のような表を出すとする。

数値 下位8ビット分
1 0000 0001
127 0111 1111
180 1011 0100
-1 1111 1111
-127 1000 0000
64 1000 0000

私の頭の中では今回の例を試したとき、このような感じの頭になっていた。だが、冷静になってから見てみると、何かがおかしい。この整数の型は、なんだ?気付いてみるとものすごい違和感を覚える。-127と64が同じ表現になっていて混乱しないのか問いただしたくなる。180という数値もしれっと混ざっているが、本当に8bit整数ならunsigned じゃないと表現できないだろう、、、。型がある言語であればその上限・下限に強く意識を持つものだが、境界を持たないという定義を持つ環境では、具体的なビット表現に思いを寄せることがなくなっているのに気づく。。結局これらの値は果たして、signed なのか unsigned なのか?そもそもこの数値は、本当に8ビットで考えているのか?若干怪しい。いや、だいぶおかしい。それでいて違和感を覚えないのは、今何をしているか、どのような結果になるかについて、”内部の表現に考えを寄せることなく”想像できているためなのだろう。

さて、ビット表現の話に戻そう。たとえばバイナリ表現 1000 0000 は、次のように解釈できる。

  • signed の 8bitの値で、-127 を表している
  • unsigned の 8bitの値で、64 を表している

しかし、ビット列が上位側へ無限につながっているとしたら、次のような場合も考えられる。

  • 暗黙に 8bit以上ある値として、この後の上位ビットには 0 が続く。したがって 64 を表している
  • 表示上の最上位ビットが 1 なのだから負の値である、したがって上位ビットは1が続き、-127 を表している

そして、「いずれも正解である」と言える。単に表示に対する解釈が違うだけである。前提がはっきりしていない(もしくは自分の中でだけはっきりしている)ので一つに決められるだけではないか。

このおかしさに気付くと、そもそも負の数のビット表現ってどうやってするのだったかを思い出すことになる。先の例のいずれの整数も 16bitあればsignedの値として正常に表現できることだろう。しかし、無限に桁数があるとすれば、、、?

数値 4bit? 8bit ? signed 16 bit signed 32bit (上位24bitを省略)
1 0001 0000 0001 0000 0000 0000 0001 0..0 0000 0001
127 不可 0111 1111 0000 0000 0111 1111 0..0 0111 1111
180 不可 1011 0100 0000 0000 1011 0100 0..0 1011 0100
-1 1111 1111 1111 1111 1111 1111 1111 1..1 1111 1111
-127 不可 1000 0000 1111 1111 1000 0000 1..1 1000 0000
64 不可 1000 0000 0000 0000 1000 0000 0..0 1000 0000

無限に長さを持つということは、何ビット目を見ても、まだ上位側にビットが続いているということである。もちろん、どこかで「あるビットからは、どの上位ビットを見ても0だらけ(正)か1だらけ(負)」である状態になるのだが。

また、表示するうえでは無限にビット列を表示するわけにもいかないため、有限桁数で止めることになる。その場合に、その後続く上位側のビットが1なのか0なのか、区別がつかない可能性が残るということである。たとえば、上記の例では64 と -127 が8bit表示したところで止めてしまった場合、同じ表現に見えるということである。

そして Common Lisp の format 関数は、これらの表現とは別の表現を用いることにしているようである。符号+整数部(負であれば正の値に符号反転した値)で表現する。無限にビットが続くということを考えると、よい割り切り方だと思う。しかし、整数部をそのままビット値で表してくれるのは、、、使ってみると悩ましい。そうじゃねえ、そうじゃねえだわ。結果的に予期せぬ落とし穴になっていた。

ところで。 無限に続く上位ビットの表現に関して。

上記の例の32bit表記の際にも用いたが、便宜上 正の値は 0..0 で上位側の 0 を省略し、負の値は 1..1 で上位側の 1 を省略している。今後もそのように表記するし、表示用のコード例も同じようにしている。

どうやったらビット列を思ったような表現にできるのだろうか。

ここまでで、何が起こっているか、何を間違っていたかはおおむね分かった。だが、目的のビット表現は。今後も私は符号と整数部が分かれたformat 関数の表現を使い続けるのか。いやまあ、関数とか作ることができるだろう。format関数は、負の整数は思ったのと違う結果になるが、正の整数については正常に値を表示するのだから。単に、無限に桁数を考えたときの表示を考えてやればよいだけの話である。
手掛かりは、format関数のビット表現である。ビット表現が全くできないわけではない。正の整数であれば、思った通りの値を表示できる。では、負の数をビット表示した場合に、上位側ビットがすべて1になる前の部分を正の整数として表現できれば、何とかなる。つまり、次のように考えられる。

  • (lognot #b10110100) の値は、ビット列としては 1..101001011 と表現できる
    • #b10110100 は 180, 1..101001011 は -181
  • 整数値として、 101001011 (あるいは 0..0101001011) の値を持つ値が計算できれば、表示ができるようになる
    • 最終的なビット列表示が正しければよいので、1101001011, 11101001011,, でも間違ってはいない
    • ちなみに 0..0101001011 の値は 331, 0..01101001011 の値は 843

それを考えるには、そもそも負の値はどのようなビット列になるのか?それを10進数で表示すると一般的にはどうなるのか?考える必要がある。

2の補数について

log*系関数はいずれも2の補数であることを前提とした処理となっている。Hyperspec にも書いてある。バイナリによる負の数の表現には、2の補数を用いることが多い。負の値のビット表現は知らずのうちに2の補数による表現になっていることがある。知識として1の補数(負の数は、正の数ビット表現に対するビットごとのxorの結果に等しい)が言及されることもあるが、今回は関係ない。

2の補数とは?

その最上位ビット (MSB) よりひとつ上のビットが1で、残りが全て0であるような値
(8ビットの整数であれば、100000000(二進) = 256)から、
元の数を引いた数が2の補数である。

(Wikipedia)

他にも次の性質がある。
- 正の整数 A と、対応する負の整数(補数) -A について、足すと 最上位ビットのみ1、それ以外は0となる
- A + -A => 0..010..0 (2^n となる整数)
- 正の整数 A から、そのビット反転 ~A を求め、1 を足すことで 対応する負の整数(補数) -A となる
- -A = ~A + 1

おお、、なるほど、、、どれを使えばいいんだろう、、、。

2の補数の具体例

たとえば8ビットの値で符号ありの値を考える場合、正の値に対応する負の値は次のように表せる

正の値 正の2進数 負の値 負の2進数 正と負の値を足した結果 (9bit目あり)
127 0111 1111 -127 1000 0001 1 0000 0000
3 0000 0011 -3 1111 1101 1 0000 0000

これで無限にビット列があると想定した場合も、例えば次のように表せる。

正の値 正の2進数 負の値 負の2進数 正の値の反転
127 0..0 0111 1111 -127 1..1 1000 0001 1..1 1000 0000
3 0..0 0000 0011 -3 1..1 1111 1101 1..1 1111 1100

ほしい負の整数値のビット表現を得るために必要な正の整数値

補数についてわかったところで、今のところ現時点での目的であるビット表現に考えを戻してみる。求めたい値は何だろうか?それがほしい負の整数値のビット表現を得るために必要な正の整数値である。

う、、うん。何がほしいんだろう?えーっと。無限にビット列が続く負の値 -127 (= 1..1 1000 0000) があったとしよう。これを黙ってformat 関数に与えると、結果は -111111 (※ 127 = 0..0 0111 1111) となる。それは期待する結果ではない。そこで、一度 ビット列 1..1 1000 0000 に対して、表現だけ考えると 0..0 1000 0000 (= 64) あるいは 0..0 0001 1000 0000 (= 384),,, などを求めれば、format 関数は少なくとも一部は思った通りの値として表示できる。

数値 ビット表現 format 関数の表示
-127 1..1 1111 1000 0000 -1111111
64 0..0 0000 1000 0000 10000000
384 0..0 0001 1000 0000 110000000

あとは、format 関数の出力にしれっと 1..1 とつけてやれば、思った通りのビット表現を得られる。
残る問題は、このビット列で表現したい負の整数値(例の場合 -127)に対して、ほしいビット表現を得るための正の整数(例の場合 64, 384など)をどのように計算するかである。

ここで2の補数の定義を思い出す。CommonLispの整数値は無限に桁を持てるのだ。だから、ある整数を超える 2^n 乗の整数は容易に求められる。

  • ある負の整数値 -A のビット長 が L であるとする
    • integer-length 関数 を用いた
    • そのビットより上位ビットはすべて1であるようなビットまでの最下位からの長さ と定義できる
  • -A という整数が「あたかも (L+1) bit幅の符号付き整数値である」かのように考えてみると、、、
  • -A = 2^(L+1) - A
    • もしビット長が制限されていれば、L = ビット長、のときにこの計算で得られる値は負の値を表すビット列になる
  • Common Lisp では、ビット長に制限はないため、常に L+1 は A より大きな正の整数である。
    • 2^(L+1) - A もはやり正の整数である
  • 結果、”正の整数だが、Aの2の補数に相当するビット表現を持つ値”が得られる

負の値のビット表現をおおむね思った通りにできる関数

そうやって結論にたどり着いて最終的にできたものがこちら。

(defun show-binary (value)
  (if (>= value 0)
      (format nil "0..0~b" value)
      (let* ((sign-inverted-value (* -1 value))
             (bigger-2-power (ash 1 (+ 1 (integer-length sign-inverted-value))))
             (display-value (- bigger-2-power sign-inverted-value)))
        (format nil "1..~b" display-value))))

出力したものがこちらである。

出力 補足
-128 1..110000000 = (lognot 127)
128 0..010000000
127 0..01111111 = (lognot -128)
-3 1..101
0 0..00
3 0..011

- 128 + (-128) = 最上位ビット以外は0という関係になる値となっている
- 127 と (lognot 127) のビット値が、確かに反転した値とみえる

うん。満足した。これだってこれ!これだわ!そうやろ?

改善できそうな点の考察

  • format 関数への組み込み?
  • 固定桁数での表示
  • 4ビット・8ビットで区切ってほしいかな
  • 16進数への対応

ちなみに:脳内補完する方法

この際 format 関数での負の値の表現を使用し続けることにした場合の脳内での計算方法について。ビット反転による2の補数の定義を使うことができる。

  • format 関数の出力を見る
    • -10110101
  • 符号を消してビット反転する
    • 01001010
  • +1 する
    • 01001011

これで何も問題ない。

ところで、この関数を使うタイミングはいつなのか?について

Common Lisp を勉強していてありがちな現象が、「それ、XXに書いてあるよ」 である。今回遭遇した負の値の表現に関しても、その現象が起こらないかなと思う部分がある。自分で書いたコードは、自分なりには努力したが、なんだか、おさまりがすごく悪いような気がしている。感覚なのでうまく言えないのだが、、、。ただ、仕様文書にも、いくつかのキーワードでの検索結果でも見つけられなかったことから見るに、検索性の悪い話題であることは間違いない。
そもそも、この問題は実際いつ発生する問題なのか?話題にならない程度に問題のおこらない現象なのではないか?今のところ自分としての見解は、「ビット反転を使用しない限りは発生しない」 のではないかということである。

単に計算をしているときに「負の値のビット表現がほしい!」と思うだろうか?思わないと思う。そもそも16進数にせよ2進数にせよ、必要とされるのはビット演算がかかわってくる場合に限られるように思われる。
ビット演算をしているときに、負の値がふつう現れるか?基本的には現れないように思う。今自分が思いつく限り、ビット演算を必要とする計算のほとんどは、正の整数のまま処理ができるように思われる。

  • バイナリファイル、バイナリストリーム(ネットワークとか)の読み書き - ldb関数が使える
  • データに対するマスク処理、パターンマッチ - and, or, あるいは bit-vectorを用いる

ふとした瞬間に「負の値」が現れるのは、ビット反転を行ったときだけである。くどいようだがCommonLispの整数は無限に桁を持つことができ、有限桁数の値であれば正の数のまま処理ができる。and も or(ior) も、xor もだ。唯一の例外が、ビット反転を伴う計算をした時である。上位側まで無限に続く1のビットを表現するために、内部的に負の整数となる値を得ることになる。

(show-binary #b10110100)                     ;=> "0..010110100"
(show-binary (logand #b10110100 #b11110000)) ;=> "0..010110000"
(show-binary (logior #b10110100 #b11110000)) ;=> "0..011110100"
(show-binary (logxor #b10110100 #b11110000)) ;=>  "0..01000100"
(show-binary (lognot #b10110100))            ;=> "1..101001011"

回避策:ash 関数を用いたビット幅の制限

負の値を負の値のままビット演算したいという場合は、どうしても無限に続いているということを意識する必要がある。よく注意して扱えばなんとかなる。
反面、正の値のままで扱う方法もある。lognot による反転の代わりに、2の補数の計算をすることでそれができる。

(show-binary (lognot #b10110100))      ;=>  "1..101001011"
(show-binary (- (ash 1 9) #b10110100)) ;=> "0..0101001100"

できるとは書いたが、私は使わないだろうと思う。ビット幅が制限されるのも、どうにも都合が悪い。型の宣言をすれば必要なかったりしないだろうか?

終わりに

この調査を始める前に、ビット演算の方法を調査していた。その中で lognot の出力がどうにもおかしいことに気付いた。その原因は何だと調べていたら、format関数とビット値の表現方法の問題だとわかった。思った通りの表示の方法を得るために、工夫をした。大変面白い体験となった。
また、この記事の内容は、実用的にはおそらく必要性が低いと思われる。読み物として楽しんでいただければ幸いである。返事は遅くて内容もお礼だけになる気もするが、、、コメントいただければ幸いである。

CommonLisp のビット演算を調べた話

ことのあらまし

Lispの勉強用サイトとして、SBCL をサポートしているプログラミング問題サイト HackerRankを愛用している。

その挑戦の中で、ビット演算を必要とする問題があり、いざどのようにするかを調べてみたのだが、最初探し方がまずくて見つけられなかった。というか、最近真っ先に逆引きCommonLispを参照するクセをつけているのだが、探して見つからなかった。

というわけで、調べ、おおむね逆引きにまとめたのだが、整数が”無限の長さを持つ”ことによる”負の整数のビット表現”でドはまりした。やってみるとパズル的で面白いのだが、初めて使った人は同じ罠にはまらないかな、、とも思った。初心者バイバイ感あった。

というわけで、

この記事では、調べたことを逆引きに書いたよという単なる報告と、ドはまりした負の整数とビット演算の関係について別の記事 に書いたことの報告を書く。あまりに長くなったので分けた。

概要

  • CommonLispにおけるビット演算について調べた
  • 整数のビット演算をする log*系関数 を知った
    • それと等価な演算ができる boole 関数があることを知った
  • 今回は書いていない:bit-vector によるビット演算があることを知った
    • 処理は log-*系関数 で行う
    • こちらはまだ試していないのでこの記事にも逆引きにも書かない
    • ライブラリや実例のリンクだけ。
  • 本題:log* 系関数でのビット演算と負の数値について
    • あまりに長かったので次の記事にする

参照

全カットでお送りします

CommonLisp における整数値のビット演算 -> log*系関数, boole関数

logand, logior (or演算), logxor, lognotなどビット演算処理が一通りそろっている。逆引きのビット演算の項目として書いた

あと、boole 関数はlog関数と同じことを「オペレータを指定して」できる。よく見ると、boole のほうが少し処理の種類が多い。なんとなく、遺伝プログラムとか人工知能などといったプログラム生成の論理処理用に作られたのでは?と想像した。データとして演算が扱えるということで。逆引きのビット演算の項目の中に一緒に書いた。

bit-vectorを使うという選択肢 -> bit-*系関数

bit-vector についてはそこまで調べていない。

  • ビットベクターのリテラル表記は #*10110100 のように、 #* から始める
  • bit-vector 同士の演算は、bit-*系関数 を使う
    • ほぼすべての種類の演算がそろっている
    • vector なので、シーケンス関連の関数が一通り使える
  • ビットベクターと整数との相互変換を扱う標準の方法は、無いといってよい
    • coerce 関数 を使う方法があるらしいことはわかった
  • ライブラリ bit-smasher がある
    • 整数値、文字列、ビットベクタとの相互変換ライブラリ

log* 系関数でのビット演算と負の数値について

まとめというには長い記事になったので、別の記事 としてまとめた。

概要としては

  1. なんで (format t "~b" (lognot 8)) ;-> -1001 となるのだろう?
    • 自分が表示してほしい値は 1011 とか 1111 1011 なのだが?
  2. あ、整数値は無限に長いので表現が無理なのか、え?でも 1001 と 1011 ではだいぶ違うけど、、
  3. ああ、、、符号部と整数部が分かれて表示されているのか、、、
  4. これは、、仕様っぽい、、、しょうがない、ちょっと考えるか、、、

そういうわけでいろいろ考えた結果、負の整数値でもビット値として表示できる次の関数を作ってみた。

(defun show-binary (value)
  (if (>= value 0)
      (format nil "0..0~b" value)
      (let* ((sign-inverted-value (* -1 value))
             (bigger-2-power (ash 1 (+ 1 (integer-length sign-inverted-value))))
             (display-value (- bigger-2-power sign-inverted-value)))
        (format nil "1..~b" display-value))))

この関数を使った時の表現は, 正の値には 0..0 を、負の値には 1..1 を付けて表示する。
負の符号の整数値は、上位ビット側に無限に 1 のビットがあることを表現しているつもり。

value binary 補足
-128 1..11110000000 = (lognot 127)
128 0..010000000
127 0..01111111 = (lognot -128)
-3 1..11101
0 0..00
3 0..011

とはいえこの関数では

  • format 関数に統合したい
  • lognot のビット反転の値と反転前の値の桁数が現状そろわない
  • 固定桁数での表示をしたい

などいくつかの自分ニーズに応えられていないので、今後の改良が待たれる。

Written with StackEdit.
Written with ATOM