すべてのプログラマーが挑戦すべきプロジェクト（2019）
(austinhenley.com)- サイドプロジェクト選びに迷うなら、テキストエディタ、2Dゲーム、コンパイラ、ミニOSのように、繰り返し作るほど学びの幅が広がるプロジェクトがよい出発点になる
- テキストエディタでは、文書の保存構造、カーソルの挙動、取り消し/やり直し、行の折り返しを自分で実装しながら、データ構造と抽象化を身につけられる
- Space Invadersのようなシンプルな2Dゲームでも、画面描画、入力処理、ゲームループ、オブジェクトの状態管理、敵AI、サウンド、シェーダー、ネットワーキングに至るまで、ゲームプログラミングの基本構造が見えてくる
- Tiny BASICコンパイラとミニOSでは、それぞれレキシング・パース・意味解析・コード生成、クロスコンパイル・ブートローディング・メモリ管理・スケジューリングといった低レベルの概念を直接扱うことになる
- スプレッドシートとコンソールエミュレータは、これまでのプロジェクトの難しさを組み合わせ、実際の動作をまねる仮想マシンまで作ってみる段階へと発展する
繰り返し作ってみる価値のあるプロジェクト
- サイドプロジェクトが必要なときや、新しいプログラミング言語・フレームワークを学びたいとき、同じプロジェクトを何度作っても、そのたびに違うことを学べる
- おすすめのプロジェクトは、難易度も学習領域もそれぞれ異なる
- テキストエディタ: データ構造、カーソルの挙動、取り消し/やり直し、画面表現
- 2Dゲーム: 画面描画、入力処理、ゲームループ、オブジェクトと状態の管理
- コンパイラ: レキシング、パース、意味解析、コード生成
- ミニOS: 起動、メモリ管理、スケジューリング、ファイルシステム
- スプレッドシートとコンソールエミュレータ: 先のプロジェクトの概念を、より大きな構造へ統合する
テキストエディタ
- テキストエディタは毎日使うツールだが、標準のテキストボックスコンポーネントなしで自分で実装すると、カーソル移動、選択、挿入、削除の細かな挙動を扱うことになる
- 最大の課題は、テキスト文書をメモリ上にどう保存するかである
- 単純な配列は、文書末尾以外の位置にテキストを挿入すると性能が悪い
- 比較できる構造として、配列、rope、gap buffer、piece tableがある
- カーソルは単に上下に動くだけではない
- 短い行へ移動すると可能な位置まで移動し、その後十分に長い行が出てくると元の列へ戻ろうとする列記憶の挙動がある
- 基本的なエディタの後には、取り消し/やり直しと行の折り返しを追加してみることができる
- 参考資料
2Dゲーム - Space Invaders
- シンプルなゲームでも、固有のデータ構造やデザインパターンが必要になる
- 大規模なゲームエンジンよりも、SDL、SFML、PyGameのような基本的な2Dグラフィックスライブラリを使うと、面白い部分が隠れない
- ゲームは画面を消去し、各要素を高速に描き直すことで、物体が動いているような効果を作る
- 実際の流れは、ゲームループの中で描画、ユーザー入力の受け取り、ゲームロジックの処理を繰り返す構造である
- 入力処理では、キーやマウスボタンの最初の押下、押し続けている状態、離した状態、ダブルクリックといった細かな動作を考慮する必要がある
- 入力だけを確認し続けると、ゲームの他の部分が停止した状態になる
- ゲームオブジェクトと状態管理も自分で扱わなければならない
- 動的に増える敵を生成するには、factory patternが役立つ
- 敵AIには状態機械を適用できる
- 基本的なゲームの後には、タイトルメニュー、ゲームオーバー画面、コンピュータが違っても同じ速度で実行されるようにする処理、より面白い敵AIを追加できる
- さらに拡張すれば、シェーダー効果、サウンド、オンラインマルチプレイヤーまで実装してみることができる
- 参考資料
コンパイラ - Tiny BASIC
- コンパイラは、他の人がさらに多くのものを作れるようにするツールを作るプロジェクトである
- 小さなBASIC系言語であるTiny BASICを対象に、よく知っている別の言語へ出力するコンパイラを一から書いてみることができる
- たとえばPythonでTiny BASICコンパイラを作り、C#コードを出力できる
- アセンブリやCを出力しなければ、コンパイラそのものにより集中できる
- 実装の流れは、言語処理の工程を段階的にたどる
- 入力コードをトークンに分割するlexical analysis
- 入力構造を確認し、木構造の表現を作るsyntactic analysis
- recursive descent parsing
- abstract syntax tree
- コードが意味的に正しく、型規則に従っているかを確認するsemantic analysis
- optimization passes
- code generation
- 単純なコンパイラなら数日で完成でき、その後、標準ライブラリ、最適化パス、エラーメッセージの改善を追加できる
- PeayBASICには、簡単な2Dグラフィックス機能が標準ライブラリとして追加されている
- 参考資料
ミニOS
- OSのアルゴリズムやデータ構造は、教室では抽象的だったり役に立たなそうに見えたりすることがあるが、ゲームや人間行動の予測モデルなど、さまざまな領域にも応用できる
- 自分で実装してみると、OS内部で何が起きているのかをより深く理解できる
- ハードウェア依存性のため開始のハードルと学習曲線はあるが、本やチュートリアルに従えば、自作プログラムを実行できる起動可能なOSを作れる
- 学習項目は次のとおり
- Cross compiling
- Bootloading
- BIOS interrupts
- x86 modes
- メモリ管理とページング
- Scheduling: たとえばround robin
- File systems: たとえばFAT
- 参考資料
より難しいプロジェクト: スプレッドシートとコンソールエミュレータ
- スプレッドシートアプリケーションは、Excelのように、テキストエディタの課題とコンパイラの課題を組み合わせたものになる
- セルの内容をメモリ上で表現する必要がある
- 数式で使われるプログラミング言語用のインタプリタを実装する必要がある
- スプレッドシートの参考資料
- ビデオゲームコンソールエミュレータは、コンパイラ、OS、ゲームエンジン実装の難しさを一つにまとめたプロジェクトである
- 実際のコンソールをエミュレートするには、CPUや他のハードウェア構成要素のように動作する仮想マシンを書かなければならない
- この仮想マシン上で、そのコンソール用のゲームを実行できる
- 出発点としては、実際のコンソールより単純な仮想コンソールCHIP-8のエミュレーションが推奨される
- NES、SNES、Gameboy、Gameboy Advanceもエミュレーション可能で、ドキュメントやオープンソースエミュレータもかなりあるが、各コンソールには興味深い特異点がある
- 特定のゲームは、特定ハードウェアの文書化されていないバグや機能に依存している場合がある
- PICO-8は収益性のある「fantasy」コンソールになった
- エミュレータの参考資料
追加で提案されたプロジェクト
- Hacker News、Reddit、Twitter、メールから追加のプロジェクトアイデアが集まった
- 一から作るデータベース
- レイトレーサー
- MS Paintクローン
- ベクターグラフィックスエディタ
- 画像デコーダ
- チャットルームWebアプリ
- 円周率の桁計算機
- grepのような一般的なターミナルユーティリティ
- FTPクライアントとサーバー
1件のコメント
Hacker Newsの意見
テキストエディタ、コンパイラ、オペレーティングシステム、レイトレーサーを作れば、より優れたプログラマーにはなれるかもしれないが、より優れたソフトウェアエンジニアになれるわけではない
むしろ破滅的な「Not Invented Here」主義を身につけてしまい、ソフトウェアエンジニアリングの面では悪化することすらあり得る
ハッカーはビッグオー、データ構造、HoTTのような高度に理論的なものに執着するが、実際のエンジニアリングに不可欠な「自分で作るべきものとライブラリを使うべきものの判断」「良いライブラリやフレームワークの見極め」「最適化する価値のある箇所の判断」「数年後でも読めるコードを書くこと」「ソフトウェアと非ソフトウェアの依存関係を含む大規模な複雑系としてプロジェクトを見ること」は、ほとんど議論も練習もされない
そこで代替課題としてWeb検索エンジンを提案する。文字列マッチングアルゴリズムのようなものはすでに他人がやっているので気にせず、最初はWebの一部と同時ユーザー1人だけをサポートするものでも、実際に動く検索エンジンとクローラーを「とにかく」作ってみればよい
テキストエディタ、コンパイラ、オペレーティングシステム、レイトレーサーでも、同じ活動をすべて鍛えられる
複数の長編映画で使われたレイトレーサーに関わった立場から言うと、上に挙げられた項目はそのプロジェクトにもすべて当てはまった
結局、小さくて楽しいものをやるか、それとも会社でお金をもらってやるような魂を削る制約をそのまま適用して楽しさをなくすかの違いに近い
第一に、用意されたブロックはたいていひどい場合のほうがはるかに多く、その結果ソフトウェアもそのひどさを反映し、人生はソフトウェアを使うことではなく、そのひどいものたちを保守し、なだめることになる
第二に、たとえブロックの品質が良くても、作れるソフトウェアの種類を制限する。理想的には、望む動作を想像し、それを実現するようにソフトウェアを書き、その過程でブロックを作るべきだ
用意されたブロックだけを使うと、優れたソフトウェアのかなりの部分はそもそも作れず、実際に周囲に優れたソフトウェアがあまり多くない理由もそこにあると思う
「いつも見慣れたものとほとんど同じソフトウェア」を作るなら、二つ目の問題はあまり当てはまらず、一つ目も主にハッピーパスだけを使うので対処可能かもしれない。だが、そうしたソフトウェアはやがて人間ではなくAIが使うようになるだろう
そうした技術も重要だが、どこかの時点で基礎力を伸ばす必要があり、より優れたプログラマーになることは、上に挙げた技術全般にも確かに役立つ
個人的には、ソフトウェアエンジニアリングは請求書を支払うためにやっていることで、プログラミングは楽しいから始めたことだ
この記事のプロジェクトは、時間があれば趣味でやってみたい類のものだ
UI/Web方面の観点なら、データフローシステムを理解するのに非常に有用なスプレッドシートのほかに、こうしたものを勧める
UnityやUnrealで簡単なビデオゲームを作ってみると、30〜60fpsが重要なゲームにおける性能制約を理解でき、Webを含む他の場所でも高速なインターフェースを作る助けになる
Reactに似た簡単なJavaScriptフレームワークを作ると、データフローとイベント処理の理解に役立つ
XMLHTTPRequestをラップするHTTPライブラリを自作すれば、今はfetchがあるとしても、HTTPリクエストを送って読む仕組みを一から理解でき、後でCORSの問題やOPTIONSリクエストのようなデバッグに役立つ
当時も議論されていた
Challenging projects every programmer should try - https://news.ycombinator.com/item?id=21790779 - Dec 2019 (297 comments)
関連記事もある
More challenging projects every programmer should try - https://news.ycombinator.com/item?id=25489879 - Dec 2020 (223 comments)
ミニOSに+1
アプリケーション開発者はメモリ管理、ファイルシステムなど多くのOS機能に依存しており、結局「裏側ではこうしたものはどう動いているのだろう？」と考えるようになる
そこで余暇にxv6（https://github.com/mit-pdos/xv6-public）を触ってみた
教科書で複数のプロセススケジューリングアルゴリズムを学ぶのと、実際に実装するのとはまったく違い、多くを学べた
モバイルアプリ開発者として、この知識が仕事に関係する可能性はほぼ0に近いが、間違いなく楽しい
エンジンなしで2Dゲーム開発をやってみたことは、コンピュータがどれほど信じられないほど速くなったのかを思い知らされる、もっとも謙虚な気持ちにさせられる経験だった
すごく遅くなるに違いないと思うことをやっても、Game Boy でさえ毎秒100万回の演算をするので、そのまま動いてしまう。100万という数字は思った以上に大きかったのだ
「ちょっと待って、毎回すべてのスプライトを探して描画するの？ 変更すべきものだけを把握する賢い差分計算もなく、前フレームを参照して作業を減らすための2つ目のバッファもないの？」と思っていたら、こうした手法を実際に使い始めた、はるかに複雑なゲームを見るとさらに驚く
たとえばスプライトアトラスは、こうしたデータ構造が活用される典型的な方法だ。通常、予測可能な形でレンダリングされる複数のスプライトを毎回アップロードする理由はないので、大きな画像を1枚アップロードして、その一部をサンプリングすればよい
今日の基準ではその通りだ。普及価格帯の市販ハードウェア、ゲーミングPCですらなくても、15年ほど前のほぼすべてのものは、シーンを描いて描き直すという力技のレンダリングで処理できる
純粋なハードウェアとアセンブリだけだったので、グラフィックス、サウンド、入力、メモリ管理などをすべて手作業でやる必要があった
初心者プログラマがこうしたものをすべて扱って2Dゲームを作れる一方で、動かすための過度な負担は取り除いた、簡略化された環境があれば理想的な入門になりそうだ
Space Invaders を作るのにファクトリパターンが必要だと思うなら、何かがおかしい
オリジナルにそんな設計概念が入っていた可能性はほとんどないと思う
脳がそれに感染すると、感染を広げる方法を探し始める
私たちは別の記事を読んだのだろうか？
ロボット、自動操縦ドローン、プログラム可能なGNCパラメータを持つ宇宙機の飛行力学の高精度シミュレーションのような、もっと物理寄りのものをやってみたい
Bate、Mueller らの “Fundamentals of Astrodynamics” を持っていて、この休暇シーズンに何かやってみたい
それ以外は費用がかなりかかりそうなので、シミュレーションの話をしている。ロボットの GNC 面に本当に興味があり、よい資料のおすすめがあればうれしい
倒れたり机の外へ飛び出したりせず、その場に立っていられる Segway のようなものを指している
マイクロコントローラ、IMU、ステッピングモータコントローラ、モータ、LEGO の車輪、場合によっては木片が1つ必要になりそうだ
自分でやったわけではないので、推測がかなり外れているかもしれない
その本がどんな内容なのか、どんなプロジェクトができそうなのか、もっと聞いてみたい
一日中ソフトウェアを扱った後は、物理的な物体に向かって作業するのが本当にいい
小さな玩具的なレイトレーサーも、取り組む価値のある素晴らしい課題だと思う
球といくつかの光源、拡散反射と鏡面反射を処理して、ビットマップグラフィックスを出力する程度でよい
あまり過度に大きくしなければ、比較的スコープをうまく限定できるプロジェクトになり得る
グラフィックスをレンダリングしようとすると、幾何学とデータ構造をどれほど酷使できるのかを本当にたくさん学ぶことになる
https://austinhenley.com/blog/morechallengingprojects.html
https://raytracing.github.io/
https://raytracing-iow.shuttleapp.rs
興味深いリストで、個人の性向や状況によるだろうが、アイデアを探しているならよい出発点だ
すべてのプログラマが何をやるべきだ、とまでは言わないが、個人的に選んできたものだけを書いてみる
Sinclair ZX Spectrum では音楽の五線譜エディタとトラッカーを非常に粗雑に作り、2Dゲームとして侵略者が1体だけの Space Invaders を作った
そのコンピュータは自分のものですらなかった。初めてのコンピュータだった 386 では、Huffman圧縮器、DBase/Clipper より速かった B-Tree インデックス、オブジェクト指向のフォーム生成器、複数の DOS バックグラウンドプログラムを作り、そのうち1つは後に大企業のインストール処理に使われた
数年後にはダイヤルアップ用のメールチェッカー、構文ハイライト用の手書きパーサ、スプレッドシートのようなものまで作り、今もそれをやっている。抜けているものもきっとあると思う
良いリスト。時間とともに一緒に発展させられるよう、生きたリストとして維持するとよさそう
2つ追加したい
軽量な memcached を作ると、基本的なアルゴリズムと優れたシステム設計の実践が組み合わさって必要になる。「単純な」問題ではあるが、無効化、並行性、メモリ管理など、さまざまな角度からよく考える必要がある
自分だけの Docker を作ってみるのもよい。聞こえるほど複雑ではなく、最近のエンジニアが日常業務であまり使わないオペレーティングシステムプログラミングの基礎を理解する機会を与えてくれる