Turing Complete FM

カーネギーメロン大学の客員研究員として明日から赴任するるくすくんと、コンピュータのセキュリティや、システムズ系のコンピュータサイエンスの論文などについて話をしました。出演者: るくす (@RKX1209)、Rui Ueyama (@rui314)

https://turingcomplete.fm/31

ハッシュタグは#tcfmです。

TCFMはサポーターの投げ銭によって収益を上げています。このコンテンツに課金してもいいよという方はぜひクリエイター支援サイトPatreonから登録してご協力ください。

イントロ (0:00)

カーネギーメロン大学に明日から行きます (0:47)

Samsung Galaxyのシリアルコンソールを有効にするハードウェアの裏技 (9:00)

iPhoneではアンロックしてから1時間が経過するとUSBデータ通信が完全無効化される (16:00)

メモリアクセスのときに放射される電磁波ノイズでラジオを鳴らす (17:30)

初代XBoxのメモリバスをタップしてデータを取得 (18:54)

るくすくん作成のNintendo Switchエミュレータ公開されました (22:00)

Nintendo SwitchにAndroidを移植 (26:10)

Linus、他人に対する振る舞いを改善するために一時的に公的な立場を退く (27:50)

るくすくん、Kernel/VM関西というイベントを主催 (34:06)

x86ネイティブコードを安全に動かすNaCLの論文 (36:30)

4KiBページを自動的に2MiBのスーパーページに昇格するというFreeBSDの機能 (44:57)

Hans Boehmの「スレッドはライブラリとしては実装できない」という論文 (50:20)

カーネギーメロン大学における生活 (55:59)

エンディング (59:46)

iOSのUSB制限モード

Macbook system bus radio

るくすくんのSwitchエミュレータ

Native Client: A Sandbox for Portable, Untrusted x86 Native Code

Practical, transparent operating system support for superpages (PDF)

Threads Cannot be Implemented as a Library (PDF)

セキュキャンのCコンパイラ自作コースが無事に終わりました。共同講師だったhikaliumと一緒に、コンパイラ自作の要点やコンピュータサイエンスの教え方などについて振り返りました。出演者: hikalium (@hikalium)、Rui Ueyama (@rui314)

https://turingcomplete.fm/30

ハッシュタグは#tcfmです。

TCFMはサポーターの投げ銭によって収益を上げています。このコンテンツに課金してもいいよという方はぜひクリエイター支援サイトPatreonから登録してご協力ください。

イントロ (0:00)

よい寄付先とは (4:47)

セキュキャンのCコンパイラ自作ゼミとは (7:51)

インクリメンタルにCコンパイラを作る (12:21)

左辺値と右辺値 (17:55)

似て非なるものを作るのは努力の重複ではない (19:17)

9cc書き始めました (20:51)

自作コンパイラの性能もそんなに悪くはない (21:18)

Ken Thompsonのログインハック (23:10)

Cコンパイラ、アセンブラ、リンカ、libc関数を全て自前で書く (32:16)

Stanford CS140 (34:59)

Stanford CS140e (37:40)

三億円事件 (40:59)

仮想通貨盗難事件のスケールの大きさ (45:29)

ビットコイン盗難とSIMスワップ攻撃 (48:11)

ハードウェアのセキュリティキー (49:08)

hikalium、Ergodoxキーボードを買う (51:24)

キーボード早打ち対決 (55:35)

国によってキー配列が違う (58:55)

プログラミングを教える時の心構え (1:01:31)

Keithというよい講師の話 (1:05:07)

褒めるときに悪い話をセットにしない (1:07:10)

久しぶりのTCFM (1:11:58)

エンディング (1:14:14)

An Incremental Approach to Compiler Construction (PDF)

Let's Build a Compiler, by Jack Crenshaw

Writing A Compiler In Go

8cc C Compiler

9cc C Compiler

sk2cc

aqcc

Ken Thompsonのハック (PDF)

自作Cコンパイラで Ken Thompson のログインハックを再現してみた

aqccの解説スライド

Rustで書かれたJavaScriptエンジン

Stanford CS140

Stanford CS140e

三億円事件 (Wikipedia)

Yubikey

Kinesis keyboard

Ergodox keyboard

Cコンパイラ制作の夏期集中コースが思っていた以上にうまくいった話

セキュキャンのCコンパイラ作成コースの話、CGでよくでてくるティーポットの実物を入手した話、hikaliumの中学生時代のOS自作の話をしました。出演者: hikalium (@hikalium)、Rui Ueyama (@rui314)

https://turingcomplete.fm/29

ハッシュタグは#tcfmです。

TCFMはサポーターの投げ銭によって収益を上げています。このコンテンツに課金してもいいよという方はぜひクリエイター支援サイトPatreonから登録してご協力ください。

イントロ (0:00)

セキュキャン事前学習始まりました (1:33)

「低レイヤを知りたい人のためのCコンパイラ作成入門」（仮題）、現在7万字 (3:58)

Cの不可解な言語仕様のルーツを知るために1972年の最初期のCコンパイラのコードを読んでみた (6:07)

符号拡張とマイナス2進数 (13:04)

コース参加者のコードのほうが8ccのコードよりきれい (17:57)

一番最初のコンパイラは構文解析が非常に苦労した (20:23)

CGでよくでてくる例のティーポットを買いました (22:07)

元々はボストンのコンピュータ博物館で展示されていた (25:15)

Frieslandという会社が今でも同じティーポットを作っている (26:03)

ユタ・ティーポットはなにがCGに適しているのか (28:27)

ユタ・ティーポットと南部鉄器の類似性 (30:31)

内輪ネタとしてのユタ・ティーポット (33:14)

ユタ大学のUtah Teapot Rendering Competition (34:00)

画像処理の標準テストイメージとしてよく使われる女の人Lennaの話 (37:57)

ユタ・ティーポットは日本からも普通に買えるはず (41:47)

hikaliumのOS自作入門 (43:28)

hikaliumの小学生時代のホームページ (44:21)

30日OS自作入門本のOSのファイルシステム (48:00)

GUIの多色対応 (51:36)

30日OS自作入門本のmalloc (55:29)

K&R mallocを自力で発明して実装 (58:10)

テキストボックスを実装 (1:00:33)

ARMの実行のみできるページ（読めない）という新しい機能 (1:03:17)

x86のページテーブルがいつの間にか5段くらいに深くなっている件 (1:06:32)

lldでEFIバイナリのブートローダを簡単に作成 (1:08:01)

lldはクロスのビルドを簡単にするつもりで作っている (1:09:48)

hikaliumのOS次回作のテーマ (1:12:07)

Window Systemでウィンドウを入れ子にする (1:15:04)

クリックした場所を検出しようとすると必ずマウスカーソル自身になる問題の回避法 (1:18:58)

MIDIファイルを読んでPCのビープ音で再生する機能を実装 (1:20:48)

無理やりなコードでも動くものを一回書くと学べることが多い (1:25:00)

Intelのマニュアルを読んで16ビットモードのエミュレータの作成を試みる (1:26:42)

中学生の夏休みの頃はひたすらコードを書いていたりしていた (1:31:38)

エディタはWindowsのメモ帳だった (1:32:18)

いまからみると稚拙なコードを書いていた中学生時代 (1:37:50)

エンディング (1:39:57)

1973年前後のCコンパイラのソースコード

2の補数 (Wikipedia)

8cc C Compiler

ユタ・ティーポット (Wikipedia)

購入したユタ・ティーポットの写真

コンピュータ・ヒストリー・ミュージアムに収められている「本物」のユタ・ティーポット

南部鉄器 (Wikipedia)

Utah Teapot Rendering Competition

画像の標準テストイメージとしてよく使われるLenna

Frieslandのティーポット注文ページ

Frieslandのティーポット注文ページ（中）

Frieslandのティーポット注文ページ（オリジナルの大きいサイズ）

30日でできる! OS自作入門（書籍）

ARM execute-only memory

プログラミング言語C（通称K&R本）

Gauche Schemeの作者の川合史朗さんと言語処理系についての話をしました。GaucheのCコードとの互換性を保ちつつ無限リストを導入するために採用したトリックや、Gauche自身で書かれているGaucheを過去のバージョンでビルドするために気をつけていることなどの話をしました。出演者: 川合史朗 (@anohana)、Rui Ueyama (@rui314)

https://turingcomplete.fm/28

ハッシュタグは#tcfmです。

TCFMはサポーターの投げ銭によって収益を上げています。このコンテンツに課金してもいいよという方はぜひクリエイター支援サイトPatreonから登録してご協力ください。

イントロ (0:00)

電卓そろばん対決の動画存在しました (2:28)

Gaucheとそのほかのプログラムのリリースプロセス (3:33)

コンパイラのブートストラッピング問題とバージョン間の互換性 (4:51)

GCCやClangにおけるブートストラッピング問題 (18:08)

Goでは言語仕様がフリーズされていてGo 1の間は変更されない (19:41)

Webブラウザの6週間のリリースサイクルは短いのか長いのか (20:35)

FirefoxもClangとlldにスイッチ (21:32)

Gaucheがstdioを使わずに独自bufferred IOを実装している理由 (22:58)

FILE構造体の内部にアクセスする（移植性のない）実装 (26:41)

プログラム終了時にバッファをフラッシュしないといけない (27:13)

stdioではstdinを読もうとしたらstdoutがフラッシュされる (28:24)

遅延シーケンス（無限リスト） (31:05)

Cレベルでの互換性を保ったままconsセルを遅延シーケンスにするトリック (34:52)

遅延シーケンスをどこで使っているのか (37:29)

遅延シーケンスのパフォーマンス最適化 (38:45)

Clojure言語のTransducerという仕組み (42:07)

カリー化とは何か (46:06)

キーワードとシンボル (48:09)

キーワードをシンボルのサブクラスにして発生した問題 (54:27)

Scheme言語仕様にはキーワードはない（シンボルで十分？） (56:08)

現在仕様策定中のScheme言語仕様R7RS (58:27)

R6RSの言語仕様は振り返ってみて良いものといえるのだろうか？ (1:00:12)

標準化委員会が作る言語仕様と個人の作品としての言語仕様 (1:03:55)

Goの言語仕様の変更のプロポーザル (1:05:09)

Schemeでは言語仕様を実験的に拡張して良さそうなら標準化するというのがよくある流れ (1:06:51)

言語仕様策定の投票権は全員平等なのが本当によいのか (1:09:19)

Schemeは誰でも参加できるところがよいところ (1:10:02)

C++のトライグラフの廃止に最後まで反対していたのはIBMとカナダ (1:11:14)

エンディング (1:13:22)

Running for Grace （Shiroさんの出ている映画）

Gauche Scheme

Consセル (Wikipedia)

stdioにおけるバッファのフラッシュのルール

Go言語仕様

Clojure言語

Transducers

カリー化 (Wikipedia)

Haskell (Wikipedia)

ハスケル・カリー (Wikipedia)

SRFI（サーフィー）

R6RS（現行の最新のScheme言語仕様）

トライグラフ (Wikipedia)

今週は歴史回です。僕からは、終戦の翌年の東京で、日本のそろばん名人が米軍代表の電卓オペレータと大規模な公開マッチを行って、そろばん名人が勝利したという知られざるエピソードを紹介します。うどんくんからは、第二次世界大戦のドイツ軍の暗号がどう破られたのかという話をします。出演者: うどん (@kw_udon_)、Rui Ueyama (@rui314)

https://turingcomplete.fm/27

ハッシュタグは#tcfmです。

TCFMはサポーターの投げ銭によって収益を上げています。このコンテンツに課金してもいいよという方はぜひクリエイター支援サイトPatreonから登録してご協力ください。

イントロ (0:00)

コンピュータ歴史博物館 (0:40)

そろばん対決の当時の新聞記事を図書館で探す (4:22)

星条旗新聞の一次資料を発見 (8:24)

日本側挑戦者は逓信省に勤めるマツザキ・キヨシさん (9:50)

新聞の興行としての計算勝負 (12:52)

会場はアーニー・パイル・シアター（旧東京宝塚劇場） (14:55)

アメリカ側挑戦者はGHQ財務局のThomas Nathan Wood二等兵 (16:32)

モータを内蔵した機械式計算機 (17:19)

勝負の予想は半々に割れる (18:40)

日本側からNHKや新聞が取材に来ていてフィルムも残っているはず (20:39)

マツザキさんが勝利 (21:27)

マツザキさんの勝利を報じる星条旗新聞 (23:35)

この計算対決があったことはほとんど知られていない (24:35)

エニグマ暗号機 (27:24)

大昔のコンピュータを、現役学生時代にMITでハックしていた人がデモしてくれる (27:56)

エニグマの基本構造 (29:46)

シーザー暗号やヴィジュネル暗号との比較とその解読法 (33:29)

ワンタイムパッドとは (38:56)

バベッジとバベッジの階差機関 (41:05)

エニグマの基本構造と鍵空間の大きさ (43:24)

エニグマはいつ解読されたのか (46:54)

分散コンピューティングで解読する現代の試み (49:32)

ポーランドが暗号化手順の脆弱性を発見してエニグマのレプリカを作ることに成功 (51:02)

ソ連のページが重複した「乱数表」でアメリカが通信解読に成功していた事件 (1:06:30)

ポーランド侵攻の直前にイギリスのチューリングのチームに成果を引き継いだ (1:07:38)

チューリングを描いた映画「イミテーション・ゲーム」 (1:11:10)

クリブを元に全探索する装置Bombe (1:12:10)

ドイツ軍は連合国の暗号解読を試みたのか (1:16:05)

アメリカ軍の暗号解読により山本五十六海軍長官が殺害される (1:17:52)

タイガー手回し計算機 (1:19:26)

物量の差で負けた戦争と、そろばん電卓対決 (1:22:29)

テレビ番組化希望 (1:23:47)

未解読の暗号文を解読する現代の試み (1:24:58)

最近も新しい暗号文が解読されている (1:29:21)

エニグマのレプリカ自作 (1:31:01)

歴史回はどうだったか (1:32:21)

サイモン・シン「暗号解読」 (1:33:02)

エンディング (1:35:04)

NHKの持っていたそろばん対決のフィルムの抜粋

コンピュータ・ヒストリー・ミュージアム

コンピュータグラフィックスのデモでよくでてくるティーポッド (Wikipedia)

そろばん対決のWired日本語版の記事

そろばん対決のWired英語版の記事

そろばん対決についての短い説明 (Wikipedia)

東京宝塚劇場 (Wikipedia)

風船爆弾 (Wikipedia)

星条旗新聞 (Wikipedia)

Ancestry

モンロー計算機のデモ (YouTube)

エニグマ暗号機 (Wikipedia)

エニグマの解読 (Wikipedia)

バベッジの階差機関

エニグマについての詳しい日本語スライド

ヴィジュネル暗号 (Wikipedia)

エドガー・アラン・ポーの「黄金虫」 (Wikipedia)

ポーランドが内部の配線を特定するのに成功した手法の説明 (Wikipedia)

欠陥のある乱数表によりソ連の暗号を解読するプロジェクト

映画「イミテーション・ゲーム」 (Wikipedia)

チューリングによる暗号解読機Bombe (Wikipedia)

イギリスによる海底ケーブル網

山本五十六海軍大将の戦死 (Wikipedia)

サイモン・シン「暗号解読」（書籍）

How Polish Mathematicians Deciphered the Enigma (PDF)

分散コンピューティングで解読するプロジェクト Enigma@Home

Frode Weierudさんによる エニグマ暗号まとめサイト

Frode Weierudさんによるエニグマ暗号解読についての最近の進歩についての論文 (PDF)

チャールズ・バベッジ (Wikipedia)

タイガー計算機

計算機屋かく戦えり（書籍）

追記

そろばん対決では四番勝負と言っていますが正しくは加減乗除とその全てのコンビネーションの五番勝負です。