任意の区間で任意の整数の倍数を数える

　Codility の問題をいくつか解いてみていて、どうにも解けずに諦めてしまった問題があった。匙を投げて解法を検索してみて、あまりにスマートに解けるものだから、なおさら悔しい思いをしている。そこで供養の意味も込めて振り返りをまとめておく。

　当該の問題は Lesson 5 の count_div である。リンクは以下に貼る。

app.codility.com

　 の3つの整数が与えられ、 ] の区間に含まれる の倍数の個数を数え上げる。

　制約として定式化すると次の通りである。

• 
• 
• 

　A から B までを愚直にイテレートする解がまず思い浮かぶが、これでは計算量が であるから制約に照らすと許容できない。で、自前のテストケースを用意した上で効率化する方法を考えてみるのだが、どうにもうまく仕様を満たせない。 の場合、 の場合、 の場合、 の場合 ... などのケースを同時に満たすことができず、いっけん簡単に見えるにもかかわらず解ききることができずうろたえてしまった。なお利用したテストケースは gist として公開してある。

count_div_test.rb · GitHub

　バグがあるというよりは単に計算の帳尻が合わないということが自分でも痛いほどわかっていて、コーディングスキルというよりも数学的思考の弱さを突きつけられているようで、解いていて本当に辛かった。結局は検索エンジンに頼って正答例を得てしまったわけだが、5行で実装されているその解法をみるにつけても、自分で解答にたどり着けなかった悔しさが募るばかりである。

　そこで、ここでは正当例のコードを基に証明も考えてみた。もちろん証明してから解ければ申し分ないし、本来はそうありたいわけだが、あいにくその力がなかったということで、振り返りも兼ねてまとめる。

証明

定義

• 
• 

とおく。m は A 以下の最大の K の倍数ということになる。

手続き

　] の区間における K の倍数の個数を考える。

1. のとき
   • より ] の区間について考えればよい
2. のとき
   • 便利のためにこの場合も ] の区間を数え上げる。
   • は ] に含まれない倍数であるが、 ] について解を求めて、最後に を加えれば結局 ] についての解が得られる

　というように、 ] の範囲における の倍数を数え上げるという方針で考えればよい。さらにこれを変形して ] としても、範囲内に含まれる倍数の個数は変わらないのは明らかである。

　以上より、問題の条件を求める計算式は となる。 ] の区間には が含まれ、これも の倍数であるから、最後に を加えている。

　コードとしてはこうなる。

def solution(a, b, k)
  r = a % k
  m = a - r
  answer = (b - m) / k + 1
  answer -= 1 if r > 0
  answer
end

おわりに

　こういった整数論的な問題は、僕にとっては明らかな苦手分野だ。問題文をみたときにはすでにこのような思考を組み立てられる頭脳を持つ人もいるのだと思うとまったく恐ろしい。

　同じ土俵で勝負することは到底敵わないわけであるから、こうしてきちんと復習はしつつも、自分の勝てる土俵を見つけないといけない、そしてそこで戦う根性を身につけなければならない、と改めて考えさせられる契機となった。もっとうまくなりたいと思うが、それは当然、もっと修行しなければいけないという意味にほかならない。とはいえこのほかにも学びたいものはたくさんあるわけで、どの優先順位で何をやるかをよく考えて取り組まないと、二兎を追うだけの結果となりかねない。

配列を任意の個数の部分集合に均等に分割するアルゴリズム

　長さ N の配列があり、それを M 個の部分集合に均等に分割したい。

　制約を簡単に定義するとこうなる。

• 0 <= N
• 1 <= M <= 100

TL;DR

active_support/core_ext/array/grouping の Array#in_groups がそのものズバリである。

誤ったロジック

　3年前の自分が実装したロジックをざっくり書くと、それはこんなものであった。仮に N = 10, M = 3 とおいている。

def generate_array(size)
  i = 0
  Array.new(size) { i += 1 }
end

def solve(arr, m)
  group_size = (arr.size + m - 1) / m
  arr.each_slice(group_size).to_a
end

N = 10
M = 3

arr = generate_array(N)
solve(arr, M)
# => => [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10]]

　これだと一見 M 個の部分集合に分割できたようにはみえる。しかし各部分集合に属する要素数は [4, 4, 2] となっている。 [4, 3, 3] と均等に分割したいところである。

　それだけではない。3年越しに見つけた問題点は次である。

N = 0 のとき

　Array#each_slice に 0 を渡すと ArgumentError (invalid slice size) が発生してしまう。

N / group_size != M のとき

　例えば N = 6, M = 4 のときを考えてみよう。

N = 6
M = 4

arr = generate_array(N)
solve(arr, M)
# => [[1, 2], [3, 4], [5, 6]]

　4個の部分集合に分割するはずが、3つにしか分割できていない。group_size を切り上げで計算してしまっているため、部分集合あたりの個数を正しく計算できていないのである。

def solve(arr, m)
  group_size = (arr.size + m - 1) / m
  arr.each_slice(group_size).to_a
end

　要するに、誤ったロジックであるわけである。

　配列の操作であるから、標準 API に便利メソッドがありそうな気がする。で、 ruby-doc.org で Array から Enumerable から、それらしいメソッドを探してひたすら読んでいたが、代替できそうなものは見当たらない。「自前で実装するしかないのか…」と思い始めたとき、 active_support/core_ext にそのものズバリな API を見つけた。

Array#in_groups

　手短に改善後のコードを示すと、こうなる。

require 'active_support/core_ext/array/grouping'

def generate_array(size)
  i = 0
  Array.new(size) { i += 1 }
end

def solve(arr, m)
  arr.in_groups(m, false)
end

　N = 0 で空集合に対して実行しても ArgumentError を吐かずに、M個の部分集合を作ってくれる。

N = 0
M = 4

arr = generate_array(N)
solve(arr, M)
# => [[], [], [], []]

　また先ほどうまく機能しなかった N = 6, M = 4 のケースでも、部分集合の個数はあっているし、きちんと均等に分割されてもいる。

N = 6
M = 4

arr = generate_array(N)
solve(arr, M)
# => [[1, 2], [3, 4], [5], [6]]

　ここで終わってしまってはそれまでだから、せっかくなので Array#in_groups の実装も覗いてみよう。

あるべきアルゴリズム

https://github.com/rails/rails/blob/v6.0.3.4/activesupport/lib/active_support/core_ext/array/grouping.rb#L62-L86

def in_groups(number, fill_with = nil)
  # size.div number gives minor group size;
  # size % number gives how many objects need extra accommodation;
  # each group hold either division or division + 1 items.
  division = size.div number
  modulo = size % number

  # create a new array avoiding dup
  groups = []
  start = 0

  number.times do |index|
    length = division + (modulo > 0 && modulo > index ? 1 : 0)
    groups << last_group = slice(start, length)
    last_group << fill_with if fill_with != false &&
      modulo > 0 && length == division
    start += length
  end

  if block_given?
    groups.each { |g| yield(g) }
  else
    groups
  end
end

　コメントに書かれていることがすべてではあるが、言われてみると「なるほど！」と単純に納得できるだけのシンプルなアルゴリズムである。

  # size.div number gives minor group size;
  # size % number gives how many objects need extra accommodation;
  # each group hold either division or division + 1 items.
  division = size.div number
  modulo = size % number

　配列の長さを分割したい個数で除算して、ひとつの部分集合あたりの要素数を division に定義している。 modulo は剰余であり、この個数にあたる部分集合については、 division + 1 個の要素を持つことになる。

　ところで Integer#/ ではなく Integer#div を使っている。Integer#/ は 引数のクラスに応じて返り値のクラスが決定されるのに対して、 Integer#div は引数のクラスに関わらず Integer が返り値となる。つまりはこういうことである。

4 / 2.0
# => 2.0

4.div 2.0
# => 2

　Integer#div は ActiveSupport の拡張ではなく、 Ruby 標準の API である。これも知らなかった。

　本題に戻ろう。続いてのコードはこうである。

  # create a new array avoiding dup
  groups = []
  start = 0

　分割後の部分集合を格納するための配列と添字を初期化している。 #dup を忌避するとあるが、この後の処理を読めば #dup がないのは妥当であるように思われ、コメントの意図はよくわからない。

  number.times do |index|
    length = division + (modulo > 0 && modulo > index ? 1 : 0)
    groups << last_group = slice(start, length)
    last_group << fill_with if fill_with != false &&
      modulo > 0 && length == division
    start += length
  end

　length で次の部分集合の要素数を決定している。 modulo 個の部分集合は division + 1 個の要素を持つという冒頭のコメントの実装である。 Array#slice で length 個分の部分集合を添字ベースで切り出したものを、変数 last_group として定義し、ただちに groups に代入している。次行では、各部分集合の要素数を揃えるために、 fill_with を last_group に破壊的に追加している。あらかじめ last_group にこの処理を施しておくのではなく、 groups << last_group を実行した後で last_group << fill_with としているのが面白い。 if fill_with != false とあるように、 #in_groups の第二引数に false を渡しておけば、要素数は埋められない。説明は省略したが、上で書いたコードについても fill_with = false としてある。最後に start += length ですでに分割した要素数だけ添字をずらして、イテレートブロックは終了である。

  if block_given?
    groups.each { |g| yield(g) }
  else
    groups
  end

　最後にブロックを与えられたときの動作が定義されているが、これは触れるまでもないだろう。

　計算量は部分集合の個数を M として O(M) である。冒頭で制約は 1 <= M <= 100 と与えたから、配列がいくら長くてもこのアルゴリズム単体としては十分問題なく動作できる。

　と、 Array#in_groups のアルゴリズムをみて思ったことを徒然なるままに書いた。結論として、表題のアルゴリズムを Ruby で実装するのであれば ActiveSupport のサポートを借りれば十分であるし、別言語で実装するのであっても ActiveSupport の実装を参考にすれば十分満足のいくアルゴリズムができるだろう。

ruby-doc のバグを報告した

　ruby-doc.org が一部落ちていたので報告した。正しい報告先を探すのがたいへんだったので備忘録で書いておく。

　落ちていたのは ruby 2.7.2 の標準ライブラリのドキュメントで、 stringio や time などいくつかのページが 404 を返していた。それから HTML の title 要素が Ruby 2.7.7 と誤って記載されていた。

　これはコントリビュートのチャンス？　と思ってリソースを探したが、報告先として指示されている documenting-ruby.org は 2016 年で更新が止まっているし、リンク先の github リポジトリ（ documenting-ruby/ruby  ）も 2015 年以来停止している。他にもあらゆるリンクが死んでしまっていてどうにもならない。

　仕方がないのでメールを書いた。バグ報告のリンクが運用停止されている以上、報告したところでなしのつぶてだろうな...と思っていた。ところが予想を裏切ってその日の夜（アメリカ時間の朝かな？）には返信がきて、次の朝（日本時間）には直っていた。

　というわけで、メールの到達率を過小評価してはならない、という教訓をえた。きちんと書けば読んでもらえるし、すぐに対応してもらえることもあるようだ。

　もっとも本記事の執筆時点ではまだスタイルシートが 404 を返してしまっているみたい。自動生成の doc をホストするだけなのになんでこうもろもろ壊れているのかは謎のまま。メールでその辺りも尋ねてみたのだが、華麗にスルーされた。

コンパイラ概論で遭遇した用語集まとめ

　The Elements of Computing Systems を読み進めている。今週からいよいよ大詰めのコンパイラ編に突入した。

The Elements of Computing Systems: Building a Modern Computer from First Principles (The MIT Press)

　概念としてのコンパイラのはたらきには、言語学の知識が絡んできていてとても面白い。たしか学部2年生のころに言語学入門の講義を履修したのであった。必ずしも優秀な生徒であった自信はないが、計算機科学の観点から言語学にアプローチするのは、ジョブズにとってのカリグラフィよろしく、点と点がいままさに線になろうとしているようでたいへん面白い。

　とはいえ、スッと飲み込むにはやはり難しい。まずは用語集を整理しなければ理解のスタートラインにすら立てない気がしている。そこでゼミの予習のような気持ちに立ち返って、まずは用語集を作ってみることにした。

　基本的にテキストに沿って整理している。英語のテキストをきちんと読み下して、日本語で整理している格好である。

　用語の日本語訳については wikipedia の多言語ページを参照している。ほとんどの項目について wikipedia に詳細な解説もあるが、直接の引用は行っていない。難しすぎて理解が及ばないのである。そのためまずはテキストに固執してきちんと精読している。

「計算機科学大辞典」のような、学者向けに重要概念や用語をコンパイルした文献があればだいぶ便利だったはず。ネット検索で出てくるのは玉石混交な情報ばかりで、きちんと頼れる情報源が見つけられなかった。 wikipedia をつい引用したくなる学部生の気持ちはとても共感できる。

　大学図書館あたりで文献を調べてみるというのはありなのかもしれないが、あいにくもはや自由に出入りできる身分ではないし、パンデミックな時節柄、一般利用者として押しかけるのも迷惑だろうから、それは控えた。いずれ機会があればきちんと調査してみたいなとは思っている。

　前口上はこれまでで、以下が用語集である。学生のノートを覗き見るような気持ちで眺めてみてほしい。

formal language - 形式言語

　人工的に単純化され、形式化された言語のこと。プログラミング言語を含むが、それにとどまらない。

　形式言語において自然言語の複雑さは捨象され、シンタックスの構造を精確に形式立てることができる。一般にプログラミング言語は、「文脈自由文法（ context-free grammar ）」と呼ばれる規約によって規則づけられる（後述）。

lexical analysis - 字句解析

　scanning, tokenizing とも。コンパイラの文脈においては、プログラムのソースコードを解析して、その文字列を分割可能な最小単位まで分割することを意味する。分割可能な最小単位のことをトークンとも呼ぶため、「トークン化（ tokenizing ）」とも呼ばれる。

terminals and non-terminals - 終端記号と非終端記号

「終端記号（ terminal ）」は「トークン」と同じ意味で、それ以上分割不能な最小単位のことを指す。対して「非終端記号（ non-terminal ）」とは、「終端記号」の組み合わせによって生ずる、より高次な表現である。

　例として、プログラミング言語における count, <=, 100 といった表現はそれぞれ、これ以上分解できない「終端記号」である。これらが集合し、 count <= 100 という表現を構成するとき、この要素は「非終端記号」である。

context-free grammer - 文脈自由文法

　形式言語における文法規則のこと。 count, <=, 100 という「終端記号」を利用して、 count <= 100 という「非終端記号」を表現できると上に書いたが、この count <= 100 が有効なことは当然、文法によって保証されていなければならない。

　あらゆる文脈自由文法は、「どのように終端記号を組み合わせて非終端記号を構成できるか」というボトムアップな指向性と、「どのように非終端記号を終端記号に分解できるか」というトップダウンな指向性の両面を規約する。

parsing - 構文解析

　入力されたテキストが文法に適っているかどうかを検証する行為のこと。

　コンパイラが構文解析を行うとは、与えられたソースコードの文字列に文法規則との完全な対応関係を与えるということである。またコンパイルエラーとは、ソースコードを文法規則に当てはめることに失敗したということに他ならない。

parse tree - 構文木

　構文解析の結果を表現するデータ構造のこと。文法規則は一般に階層構造をとるため、それを表現するにおいても階層構造をもつ木構造が利用される。

recursive descent parsing - 再帰下降構文解析

「構文木」を作成するアルゴリズムのうち、トップダウンに実行されるアルゴリズムのひとつに「再帰下降構文解析」がある。

　構文解析プログラムが「非終端記号」に遭遇するたびに、それを「終端言語」に再帰的に解析しつづけることで、すべてのトークンをもれなく処理しきることができることとなる。

LL(1) parser - LL(1) 構文解析

　再帰的に構文解析する際には、解析前に解析対象の中身を知る必要がしばしば生じる。

　例えばこれから解析しようとしている表現が while 文であるのか if 文であるのかによって、解析の仕方は異なる。そこであらかじめ解析対象の表現の先頭のトークンを覗き見て判断を下すのが、 LL(1) と呼ばれる方式である 。要するに、先頭のトークンが while であれば表現全体が while 文であることは明らかであるし、 if についても同様である、ということになる。

　先頭から k 個のトークンを先読みして初めて構文解析が可能な言語も成立しうる。こうして一般化される構文解析の方式のことを LL(k) と呼ぶ。ただし k が 1 に近いほど構文解析が容易であることは言うまでもない。

Go で仮想マシンを作った

　アセンブラを実装した前回の記事に続いて、 The Elements of Computing Systems にしたがって仮想マシンを実装した。その所感を本記事にまとめる。

　以下でも述べるが、仮想マシンとはいっても VirtualBox のような代物ではない。より限定的な意味における仮想マシンであるし、実装も学習用のものにすぎない。異なる目的を持ってこの記事を訪れていただいた方は注意のこと！

TL;DR

　レポジトリを作成して公開している

github.com

利用するテクスト

　The Elements of Computing Systems は Nand2Tetris という愛称でも親しまれている、コンピューター・サイエンスの著名な教科書である。

The Elements of Computing Systems: Building a Modern Computer from First Principles (The MIT Press)

www.nand2tetris.org

　基礎回路の設計から初めて、論理演算、CPU設計、機械語、アセンブリ、コンパイラそしてOSと、演繹的な手順でコンピューターを実装する過程が演習として読者に与えられる。

コンピュータシステムにおける仮想マシンの位置付け

　高級言語を機械語にコンパイルするにあたって、「直接機械語にコンパイルし、マシンに実行させる」というやり方が考えられるが、これではプラットフォームの数だけコンパイラを実装しなければならないことになる。

　そこで、いちど中間コードにコンパイルした上で、機械語にコンパイルし直す方式を考える。簡単にいえば、中間コードをインターフェイスとして定義することで、モノリシックなアーキテクチャを二つの疎結合なプログラムに分離するわけだ。こうすることで、プラットフォーム間の移植にあたっても、コンパイラを丸ごと作り直すのではなく、中間コードのインタプリタだけを実装すれば良くなる。端的にいって、より手軽に移植可能になるわけである。

　このようにして要請される、中間コードのインタプリタのことを仮想マシンと呼ぶ。このパラダイムは70年代に pascal 言語が切り拓いた領域で、90年代以後に Java と C# がおのおののコンパイル方式に採用したことで、揺るぎない影響力をもつようになったのだそう。

　今回はテキストが提供する Hack と呼ばれる言語の仕様に沿って、その中間コードを実行する仮想マシンを実装した格好となる。

なぜ Go を選んだか

　アセンブラの実装に Go を選択した前回の記事をもっぱら踏襲している。

jnsato.hateblo.jp

実装

　テキストの指示に従って、スタックで実装している。このスタックひとつのおかげで、ネストした関数の秩序正しい処理や、再帰呼び出しの制御が適切にコントロールできている。この魔法のような仕組みを実装を通して学べたのが最大の収穫である

　実装の詳細についていうと、プログラムは構文解析を行う parser パッケージと、解析された構文からアセンブリを自動生成する codewriter パッケージの二つからなる。 parser については、もっぱら空白文字と改行文字だけを区切りとみなす仕様の明快さによって、簡単に処理系を作成することができる。

　問題は codewriter によるアセンブリコード生成の自動化である。レジスタとメモリを操作するコードを泥臭く書いていくのだが、しょっちゅうアドレスを取り違えてはプログラムがクラッシュしたり、無限ループを脱出できなくなるなど、大変な目にあった。

　デバッグするにも1クロックごとにハードウェアが何をどう実行しているのか愚直に調べるほか手掛かりを得られず、何度も心が折れそうになりながら実装していた。数百行におよぶ低レベルの生成コードを読んで、どこで何を間違えたのか探し当てようとする作業は、目隠しをされたまま終わりの見えないトンネルを進むような心地だった。これは人生で一番辛いデバッグ作業のひとつに数えても遜色ない。

　無事追えられたことが奇跡のようにすら思える、それくらい苦しく、厳しい実装だった。もちろん、それを終えられた達成感も滅多に味わえない甘美なものである。

反省点

CodeWriter 構造体の設計

　構造体に内部状態を保存するためにプロパティをどんどん追加してしまったのはあまり満足のいく実装ではない。 Go の作法としてもバッドプラクティスだろうと直感している。洗練度に欠ける設計ではあるが、アセンブリの生成に精力を奪われて、コードの良し悪しにまで気をはらう余裕を失ってしまっていたし、それをリライトする元気も最後には残らなかった。

冗長なボイラープレート

　スタックに対する push/pop の操作をあちらこちらで頻繁にアセンブリで記述している。決まり切った表現と知りつつも、レジスタの状態に依存していつでも動作が狂いうる手前、DRY原則に沿って整理する勇気を持てなかった。

　結果として、似たような記述が乱立しており、行儀のいいコードとは評価しがたいだろう。他方で、仮に似た記述を整理したとして、それによってかえって出力コードを予期しづらくなるだろうという思いもあった。実際、似た記述と思って一箇所にまとめた結果、あとから判明したバグによって、再度別のルーチンとして分離し直さなければならないような場面もあった。

　要するに、実装途中の段階で早々にコードをまとめるよりも、最後まで実装してみることを優先した格好である。よりよい手法もあるのだろうが、個人的には、ボイラープレートを量産してでもひとつひとつの構成要素がまとまりを持つ方が好みであると改めて実感した。ちょうど React コンポーネントの定義時に、その都度ボイラープレートを書いていく必要がどうしても出てしまうのも、同じ背景ではないだろうかと考えた。

文字列の扱いのぎこちなさ

　文字列を組み立てるのがどうにもぎこちない思いであったが、これは Go の仕様上そうする他ないと割り切った。それは次のようなコードである。

initializeSP := "@256\n" +
    "D=A\n" +
    "@SP\n" +
    "M=D\n"

　 codewriter パッケージをのぞいてもらえれば一目瞭然だろう。生成される行の単位で文字列を結合していっているわけだが、改行文字はつけ忘れるし、+の打ち忘れでコンパイラに怒られるしで、お世辞にも書きやすいとはいえなかった。

　ヒアドキュメント的なものがあればいいなと何度も思ったが、標準パッケージには見受けられなかったので、文字列の結合で押し通した。とはいえもっといいやり方がないかはぜひ知りたいところである。

終わりに

　もっとも基本的なデータ構造としてとうに知った気になっていたスタック構造が、高級言語のフロー制御をもっぱら一手に引き受けて管理しているということを知るのは、目からウロコの思いだった。それを実装してみて、ハードウェアが確かに期待した通りの動作を自律的に行っているのを眺めていると、人類の発明は偉大だという感慨に打たれた。

　そしてそれを他ならない自分の手で実装できたのだという達成感は、初めての Hello World! を遥かにしのぐ驚きと喜びを与えてくれるものだった。テキストに従って進めただけとはいえ、無事にやり遂げられたことを誇りに思う。

　一方で、学習用途の、限定された機能セットしか持たない言語の実装ですら、たいへん難渋するものだということがよくわかった。

「複雑なスキームを実現するためには、誰かがハードワークを背負わなければならない。つまり高級言語でより抽象的な表現を可能にするために、低級言語のレイヤでより複雑な実装を行うのだ」という記述がテキストに述べられていた。

　日ごろは高級言語のレールに沿って仕事をしている。複雑な仕様であってもそれなりに難なく実装できるし、バグが起こってもロジカルに影響範囲を切り分けて対処することができる。しかしその平穏は、まさに今回実装したような、低レイヤにおける驚くべき着想と恐ろしく手のこんだ実装のおかげで実現せられているのだという学びが、今回の収穫である。

　こうしたパラダイムそのものを考案してくれた先人たち（とりわけ Pascal の設計者である ニクラウス・ヴィルト氏 ）、そして今日でもこうした低レイヤでの実装を行ってくれている、世界のどこかの技術者たちに、心からの敬意を持つ。そして彼らが用意してくれた仕組みのおかげで、パワフルな高級言語の恩恵に浴することができるという幸福をよく自覚して、最大限に無駄のない、エレガントなコードを書きたいものだと思いを新たにもしている。

Go でアセンブラを作ってみた

　先週のポストで、プライベートの学習がうまく進められていないことを書いた。不思議なもので、言語化してアウトプットしてみたら気が楽になったのか、ここ一週間はだいぶ調子がよくなってきている。

　で、先月来少しずつ読み進めている The Elements of Computing Systems にそって、アセンブラを実装したので、この記事ではそれを紹介しようと思う。

TL;DR

レポジトリを公開している。

github.com

利用するテキスト

　The Elements of Computing Systems は Nand2Tetris という愛称でも親しまれている、コンピューター・サイエンスの著名な教科書である。

The Elements of Computing Systems: Building a Modern Computer from First Principles (The MIT Press)

www.nand2tetris.org

　基礎回路の設計から初めて、論理演算、CPU設計、機械語、アセンブリ、コンパイラそしてOSと、演繹的な手順でコンピューターを実装する過程が演習として読者に与えられる。

コンピュータシステムにおけるアセンブラの位置付け

　アセンブラを実装するのは上記テキストの第6章になる。これに先立つ第5章までにハードウェアの論理回路の実装は終えられており、ソフトウェア層の実装の嚆矢として与えられる課題がアセンブラということになる。

　アセンブリ言語で記述されたコードをCPUに理解可能な機械語に変換するアセンブラこそ、ソフトウェアとハードウェアの架け橋となるソフトウェアだという位置付けが与えられている。

なぜ Go を選んだか

　テキストでは API 仕様書だけが与えられ、実装についてはどの言語で行ってもいいと指示されている。つまり C で実装してもいいし、 Ruby で実装してもよかったわけである。

　アセンブラの実装、と書くと高いハードルに感じられても、本質的にはテキスト処理プログラムにすぎない。手慣れた Ruby で実装してもよかったのだが、特に実装スピードを重視したい訳でもないし、手癖で実装しても勉強になるだろうかという思いがあった。

　他方で Go については、以前より文法を学んで簡単なプログラムを作ったりしていたが、

• まとまりのあるパッケージを作成したことがない
• 文字列やストリームの処理をやったことがない

という未熟さを、アセンブラのテキスト処理の実装を通して克服できそうな期待があり、これを選択した。

実装

　API の外形的な振る舞いは仕様としてテキストに与えられているので、それをひとつずつ実装していけばそれでよかった。API の命名、入力、出力の型が明確に仕様化されているため、命名に呻吟する必要はないし、 Go らしいテーブル駆動テストで進めやすく、非常にやりやすい。一部入力チェックでエラーが起こりうるようなところだけエラーを返すような設計に変更したが、 API ごとにテスト駆動でガシガシ進められるのは快感であった。

　またモジュールレベルで十分にテストができたおかげで、それらモジュールを呼び出すメインパッケージのコーディングもだいぶ楽に進められた。逆にメインパッケージのテストの粒度やテスト項目に何を定義すべきかで迷ってしまうくらいであった。ほとんどの入出力がモジュールレベルでテスト済みのとき、呼び出し元でもう一度統合テストのようなものを書くべきなのか？　とか、もし統合テストを書くのであれば、テーブル駆動テストではなく、もっとそれに適したやり方があるのではないか？　などの迷いである。

　とはいえ、単体の API をテスト駆動で開発するサイクルをいくつも繰り返す形で、わかりやすい進捗を残しながら開発できたため、プライベートの開発にしてはずいぶん効率的に進められた満足感はある。

動作

　レポジトリの README に書いた通りにはなるが、テキストに沿って次のような動作確認をしている。

1. テキストが提供するアセンブリコードを自作アセンブラに入力し、出力を保存する
2. テキスト付属のアセンブラに同じアセンブリコードを入力し、出力を比較する

例えば、 testdata/Add.asm に配置した足し算プログラムを機械語に変換するには

the-hack-assembler < testdata/Add.asm

とファイル内容を標準入力として与えることを想定している。

反省点

不器用なストリーム処理

　仕様上、入力されたストリームを二回舐める必要があるのだが、 Ruby の IO#rewind に相当する API が Go にはなさそうで、仕方なくストリームを先頭から読み直すためだけに入力を文字列として内部に保持してしまっている。

　具体的には、入力されたストリームを ioutil.ReadAll() で全行スキャンした上で、それを文字列として内部に保持しつつ、 parser.Reset() が呼び出されるごとに新しい io.Reader として定義し直すことで、複数回読み取ることができるようにしている。

　しかし例えば数万行のアセンブラを変換するとなったときに、せっかくストリームで受け取れる入力をわざわざ文字列に変換して、プログラムが終了するまでずっとメモリにのせておくのは効率が悪いなあと思っている。

コードレビューを受けたかった

　上記の件のみならず、基本的なグッドプラクティスもよく知ることができないままに Go を書いてしまっている。メンターとして頼れる知人がいないため、独自実装で進め切ってしまったが、できればコードレビューを受けながら進めたいところだった。

終わりに

　以上、アセンブリ言語のコードを機械語に翻訳するプログラムを Go で作成した話を書かせてもらった。

　学部生向けのテキストにのっとって実装しているわけだが、そもそもアセンブラってなんだっけ？　というレベルから改めて知識を整理した上で、実装まで行うことでその知識を血肉化するという意味で、非常に有意義な勉強ができたと思っている。

　情報系専攻の学生は学部時代にこんなことをやっているんだなあ、というのがわかるのもよい。もっとも、学ぶ意欲においては並の学部生を圧倒しているはずと自信を持って、無意味なルサンチマンは持たないようにする。

　Go についていうと、最初の10行を書く上ではゆっくりと手探りしながら着手したが、通常のテスト駆動開発のサイクルに軌道を乗せてからあとは、非常に楽に進められた。標準パッケージの知識が少ないため、例えば文字列の簡単な操作にしても逐一ドキュメントを見ながらの開発になったわけだが、そのせいで劇的に作業が遅くなったとは思わない。テストを書くために RSpec のような独自 DSL を学ぶ必要がないのも魅力的だし、とてもいい印象だけ得られた。

　強いていえば、上述した IO#rewind の件のように、 Ruby の API はやっぱり開発体験優位に設計されているのだなあというのは感じた。しかしまあ、これは別言語が別 API を備えているというだけの当たり前の話で、特に優劣の判断材料とするには及ばない。

　今回学んだアセンブラ以後の章ではバーチャルマシンとコンパイラ、そして OS を作成することになっている。それらも同じように Go で開発してみたいなと思っている。

AtCoder のレートが茶色になった

　週末の ABC179 にてようやく茶色コーダーになれた。9度目の参加にしての昇級であった。

atcoder.jp

　戦績を振り返ってみると、初参加が5月3日の ABC166 で、ここまで四ヶ月半かかっている。そしてその5月こそ毎週参加できていたが、その後は忙しさがこうじて参加数が落ちている。月に一度参加するくらいの頻度だ。

　過去問を解く「精進」についても、6月から8月にかけては毎日続けられていたけれど、仕事にかまけてある日断絶してしまい、その後は遠ざかっている。心が折れた...というよりは、突然『真田丸』にハマってしまって、終業後の優先順位を奪い取ってしまったのが根幹だったりする。

　競技に対する手応えでいうと、慣れのおかげでパフォーマンスを出せているにすぎず、アルゴリズム構築能力としてはそれほど成長できているかは疑わしい。

　C問題までの、自分の能力で確実に解ける問題を短時間で確実に解く、という意味では安定しており、そのおかげでレーティングを伸ばせてはいる。他方で、D問題以降の、ストレッチしないと解けない問題に対しては、手も足も出ないことも多い。終了後に解説を見れば腑に落ちることも多いため、自分の能力をはるかに超えた考察が要求されているのではないはずと思っている。実装についても問題はない。ただ、自分の頭で着想を生み出すことがどうにも難しい。

　悔しいと思うこともある。その悔しさをバネに「精進」にのめり込むのが成長の近道なのだろうが、現状そうできていないのは、「まあこんなものだろう」という諦めなのだろうか。そうであれば、嫌な大人になってしまったなあと思わざるをえない。

　とはいえ、可処分時間の半分は労働に費やさねばならないのは揺るぎない制約であるし、残りの時間をどう配分するかにも限度はある。学生時代に出会えていればまた違った付き合い方もあったのだろうが、それは悔いてもどうしようもないことなので、慌てずに自分なりのやり方で付き合っていく他ないのだろう。

　いずれ、いまからトッププレイヤーを目指すわけでもあるまいし、今後も変わらず趣味としてのんびりと取り組んでいくつもりである。次の目標としては、緑を目指すのはさておき、D問題の解答率を伸ばせるようにすることかな、と思っている。