Macr055でフィボナッチ他

次の http://parametron.blogspot.jp/2015/02/christopher-stracheygpm.html の記事に移って、フィボナッチ他。

フィボナッチ数

{m55_define|1+|`{1|2|3|4|5|6|7|8|9|10|
  {m55_define|1|$$$1}}'}{m55_dnl}
{m55_define|1-|`{-1|0|1|2|3|4|5|6|7|8|
  {m55_define|-1|$$$1}}'}{m55_dnl}
{m55_define|+|`{$1|
  {m55_define|$1|`{1+|{+|{1-|$1}|$2}}'}
  {m55_define|0|$2}}'}{m55_dnl}
{m55_define|fib|`{$1|
  {m55_define|$1|`{+|{fib|{1-|$1}}|{fib|{1-|{1-|$1}}}}'}
  {m55_define|1|1}
  {m55_define|0|0}}'}{m55_dnl}
{fib|0}, {fib|1}, {fib|2}, {fib|3}, {fib|4}, {fib|5}, {fib|6}

階乗

{m55_define|1+|`{1|2|3|4|5|6|7|8|9|10|
  {m55_define|1|$$$1}}'}{m55_dnl}
{m55_define|1-|`{-1|0|1|2|3|4|5|6|7|8|
  {m55_define|-1|$$$1}}'}{m55_dnl}
{m55_define|+|`{$1|
  {m55_define|$1|`{1+|{+|{1-|$1}|$2}}'}
  {m55_define|0|$2}}'}{m55_dnl}
{m55_define|*|`{$1|
  {m55_define|$1|`{+|{*|{1-|$1}|$2}|$2}'}
  {m55_define|0|0}}'}{m55_dnl}
{m55_define|!|`{$1|
  {m55_define|$1|`{*|$1|{!|{1-|$1}}}'}
  {m55_define|0|1}}'}{m55_dnl}
{!|0}
{!|1}
{!|2}
{!|3}

中央値、というか3要素の「場合分けによるソート」までですが、{m55_define|snd|$2} というようなマクロを使って2番目を取り出すようにするのはトリビアルな改造でしょう。

{m55_define|1-|`{-1|0|1|2|3|4|5|6|7|8|
  {m55_define|-1|$$$1}}'}{m55_dnl}
{m55_define|lt|`{$1|
  {m55_define|$1|`{p|$1|$2|
    {m55_define|p|`{lt|{1-|$1}|$2}'}}'}
  {m55_define|-1|t}
  {m55_define|$2|f}}'}{m55_dnl}
{m55_define|med|`{{lt|$2|$1}|
  {m55_define|t|`{{lt|$3|$1}|
    {m55_define|t|`{{lt|$3|$2}|
      {m55_define|t|$3,$2,$1}
      {m55_define|f|$2,$3,$1}}'}
    {m55_define|f|$2,$1,$3}}'}
  {m55_define|f|`{{lt|$3|$2}|
    {m55_define|t|`{{lt|$3|$1}|
      {m55_define|t|$3,$1,$2}
      {m55_define|f|$1,$3,$2}}'}
    {m55_define|f|$1,$2,$3}}'}}'}{m55_dnl}
{med|0|0|0}
{med|0|0|1}
{med|0|0|2}
{med|0|1|0}
{med|0|1|1}
{med|0|1|2}
{med|0|2|0}
{med|0|2|1}
{med|0|2|2}
{med|1|0|0}
{med|1|0|1}
{med|1|0|2}
{med|1|1|0}
{med|1|1|1}
{med|1|1|2}
{med|1|2|0}
{med|1|2|1}
{med|1|2|2}
{med|2|0|0}
{med|2|0|1}
{med|2|0|2}
{med|2|1|0}
{med|2|1|1}
{med|2|1|2}
{med|2|2|0}
{med|2|2|1}
{med|2|2|2}

GCD

{m55_define|1-|`{-1|0|1|2|3|4|5|6|7|8|
  {m55_define|-1|$$$1}}'}{m55_dnl}
{m55_define|-|`{$2|
  {m55_define|$2|`{-|{1-|$1}|{1-|$2}}'}
  {m55_define|0|$1}}'}{m55_dnl}
{m55_define|lt|`{$1|
  {m55_define|$1|`{p|$1|$2|
    {m55_define|p|`{lt|{1-|$1}|$2}'}}'}
  {m55_define|-1|t}
  {m55_define|$2|f}}'}{m55_dnl}
{m55_define|gcd|`{$2|
  {m55_define|$2|`{{lt|$1|$2}|
    {m55_define|f|`{gcd|{-|$1|$2}|$2}'}
    {m55_define|t|`{gcd|$1|{-|$2|$1}}'}}'}
  {m55_define|$1|$1}}'}{m55_dnl}
{gcd|2|4}, {gcd|5|3}, {gcd|6|3}

Macr055でハノイの塔

引き続いて http://parametron.blogspot.jp/2015/01/cristopher-stracheygpm.html にある「ハノイの塔」。（ハノイの塔は高機能テキストマクロプロセッサの標準課題らしく m4 にも hanoi.m4 というテストサンプルが付いています）

{m55_define|1-|`{-1|0|1|2|3|4|5|6|7|8|
  {m55_define|-1|$$$1}}'}{m55_dnl}
{m55_define|hanoi|`{$4|
  {m55_define|$4|`{hanoi|$1|$3|$2|{1-|$4}}$1 ==> $3
{hanoi|$2|$1|$3|{1-|$4}}'}
  {m55_define|0|$1 ==> $3
}}'}{m55_dnl}
{hanoi|a|b|c|0}{m55_dnl}
--
{hanoi|a|b|c|1}{m55_dnl}
--
{hanoi|a|b|c|2}{m55_dnl}
--
{hanoi|a|b|c|3}{m55_dnl}
--
{hanoi|a|b|c|4}{m55_dnl}

Macr055で基本演算

拙作のテキストベースマクロプロセッサMacr055（ https://github.com/metanest/macr055 ）で、和田先生のブログにあるマクロの例題（ http://parametron.blogspot.jp/search/label/Christopher StracheyのGPM ）をやってみたので、情報共有などのため記録として載せます。

まず http://parametron.blogspot.jp/2015/01/cristopher-stracheygpm.html にある「基本演算」から。

{m55_define|1+|`{1|2|3|4|5|6|7|8|9|10|
  {m55_define|1|$$$1}}'}{m55_dnl}
{m55_define|1-|`{-1|0|1|2|3|4|5|6|7|8|
  {m55_define|-1|$$$1}}'}{m55_dnl}
{m55_define|+|`{$1|
  {m55_define|$1|`{1+|{+|{1-|$1}|$2}}'}
  {m55_define|0|$2}}'}{m55_dnl}
{m55_define|-|`{$2|
  {m55_define|$2|`{-|{1-|$1}|{1-|$2}}'}
  {m55_define|0|$1}}'}{m55_dnl}
{m55_define|*|`{$1|
  {m55_define|$1|`{+|{*|{1-|$1}|$2}|$2}'}
  {m55_define|0|0}}'}{m55_dnl}
{m55_define|lt|`{$1|
  {m55_define|$1|`{p|$1|$2|{m55_define|p|`{lt|{1-|$1}|$2}'}}'}
  {m55_define|-1|t}
  {m55_define|$2|f}}'}{m55_dnl}
{m55_define|r|`{{lt|$1|$2}|
  {m55_define|t|$1}
  {m55_define|f|`{r|{-|$1|$2}|$2}'}}'}{m55_dnl}

本家GPM、あるいは和田先生の手元の実装と、m55ではクウォートの掛かりかたが違っていて、m55ではm4と同様に、どれだけ深いクウォートの中であっても変数の $1 などは置換されるため、この程度のマクロの場合は、一部で$$$のように多重エスケープが必要になるものの、全体的には記述が単純になる傾向があるようです（もっと後で出てくる複雑なマクロになると、どちらが有利か、だいぶわからなくなってきます）。

『アポロ計画でプログラムコードを開発した女性エンジニア「マーガレット・ハミルトン」がソースコードの隣に立っている写真』について

「コーディング教育」とか言われるようになってきたためか、最近時々バズるこの話題について。

マーガレット・ハミルトンさんが、グレース・ホッパーさんやフラン・アレンさんとともに、偉大なコンピュータ黎明期のパイオニアのお一人であることは確かですし、この記事は、おとしめる意図ではありません。しかし、話題になっている写真にはいくつか疑問点等があるので、それらについてメモとして残します。

この話題がネット上で見られるようになったのはいつからか？

threefingeredfox 氏のブログ Three Fingered Fox の、こちらの Margaret Hamilton, lead software engineer, Project Apollo | Three Fingered Fox ブログエントリ、およびそれのミラーである、Medium のこちら Margaret Hamilton, lead software engineer, Project Apollo — Medium の記事が初出のようです（2014年12月上旬。もしこれより古く、この写真について話題になっていた場がありましたら、お教えいただければ幸いです）。

また、このエントリを受けて取材をされ、同月末に公開された、こちら Margaret Hamilton, the Engineer Who Took the Apollo to the Moon — Medium の記事により、この写真は Here, Margaret is shown standing beside listings of the software developed by the team she was in charge of, the LM and CM on-board flight software team. である、とオーソライズされたという感じ、になっています。

この写真のソースと、ネットに現れるまでの経緯はどうか？

前述の取材中に Taken by the Draper Lab photographer in 1969 (during Apollo 11). とあるので、ソースはそういう（ドレイパー研究所の写真家が撮ったもの。当時はMITの関連組織ということになるはず）ことになります。

しかしその後、どういうルートでネットに出たのかはよくわかりません。threefingeredfox 氏のブログエントリには単に I just ran across on the internets. としかありません。ウィキメディアコモンズの https://commons.wikimedia.org/wiki/File:Margaret_Hamilton.gif ではNASAの画像として自由であるというカテゴリ付けがされています。しかし、NASAの画像サービスなどをあたってみても、関連する写真（アポロの操縦システムの操作を検討しているっぽい写真や、後年にパソコンの前に座っている写真）は出てきますが、この写真は見つけられていません（やはりこちらも見つけられた方がおられましたら、ご連絡ください）。

この紙の山が全て、Apollo Guidance Computer (AGC) のソースコードなのか？

詳細は水城徹さんによる、『宇宙の傑作機 No.10 アポロ誘導コンピュータ』にありますが、AGCは1ワードが16ビットで、RAMが2キビワード、ROMが4万ワード弱、というコンピュータでした（ひところは「アポロはファミコンと同程度のコンピュータで月に行った」とバズったものでしたが、そういえば最近あまり耳にしなくなった気もします）。

もちろん時代が20年も後の、6502（ファミコンの石。正確にはファミコンはそれのカスタム版を搭載している）のように整理されたアーキテクチャではなく、また開発環境も当時のマシンだったわけですから、その開発工数は、たとえば http://web.mit.edu/aeroastro/news/magazine/aeroastro6/mit-apollo.html には 1400 man-years というおそろしい数字が挙げられています。そのチーフというのが猛烈な仕事であっただろうことは想像を絶します。

前述のように、ROMが4万ワード弱のコンピュータという定量的事実はあります。しかし、アポロ宇宙船が月に行くのを支えたコンピュータはAGCだけでもありませんし、ソースコード以外にも、AGCの設計・運用のための資料は膨大であることは想像されます（『電子立国』において、シャープのエンジニアがロックウェル流の設計手法を伝授されるくだりで、現代で言う論理シミュレータのようなものが60年代にはもうあったというような話があったと思います）。

従ってこの写真について、アポロ宇宙船、あるいは特にAGC関連のプリントアウトや書類類であろうというのは確かとしてよいと思いますが、この写真の書類の山を、「ソースコードを頭から尻尾まで一通り出力したもの」と解するのは問題があり（たとえば、当時はフルスクリーンエディタなんてものは夢のまた夢でしたから、それだけハードコピーを取ることも頻繁だったはずです）、ましてや「1人で書いたもの」というような誤解をミスリードするような文言はダメということになるかと思います。

チューリングマシンはどう偉大なのか、チューリングはどう偉大なのか

現代哲学キーワード (有斐閣双書キーワード)

こちらの本を先日買いました。

我々計算機屋などが煙に巻かれがちな哲学のキーワードについて、対立する概念を対照させるスタイルを主としてよくまとまっている良書のように思われます（流石に専門でないので断言はできない）。

ですが、チューリングとチューリングマシンについて触れている所で、少し気になる記述がありました。

彼はチューリングマシンのアイディアを提示するだけではなく計算機として実装し，現在の計算機の基盤を築いた。（p. 31）

この部分については、執筆者の意図と逆に、チューリングの過少評価につながりかねない記述です。

「アイディア」「実装」という語が意図している所を私が誤解しているかもしれませんが、チューリングマシンの偉大なところは（たとえばいわゆる「ノイマンの草稿」とは違い）proof of conceptなど必要ないと自明なほどきっちりと形式化されていることであり、その実装はトリビアルな作業に過ぎません（万能チューリングマシンや停止問題といった応用も重要ですがここでは略す）。

チューリングマシンという計算モデルを提示したことと、それが（こんにちのコンピュータであたりまえの概念となっている）プログラム内蔵方式などの原形を含んでいたということは、別々のこととして評価されるべきです。

また、チューリングが関わった実機のコンピュータについてはいずれも、数理論理的な点すなわちチューリングマシンとの関連よりも、実践的な面に注目すべき点があると指摘されています。

まず暗号解読について。先日公開された映画の最後のあたりにあった字幕による解説にも誤解がありましたが、暗号解読機械 Bombe はチューリングマシンとは全く違う機械で無関係と言ってよく（先行機であるポーランドの bomba にオリジンがあると考えるべきか微妙な点もありますが）、星野力先生が著しているように、むしろ我々が無条件に所与のものと考えているシーケンシャルなディジタル計算機に縛られない発想があるという評価があります。

また戦後の ACE についても（英語版Wikipediaですら要出典が多く実際にこころもとない記述が多くて悩みますが）、1977年に The Computer Journal 誌に掲載された The other Turing machine（ http://dx.doi.org/10.1093/comjnl/20.3.269 ）などにあるように、「チューリングマシンのアイディアを」「計算機として実装し」たもの、という表現は当たりません。（一方で、あまりそれが有名でない、という事実は、後世への影響は、たとえば英国のマシンでは EDSAC やその設計者ウィルクスなどのほうが大きかった、ということでもあります）

OS X で NASM を使っている人は、バージョン 2.11.08 を回避してください

こちらのバグ、Bug 3392306 - Issue with relative addressing and data section （ http://bugzilla.nasm.us/show_bug.cgi?id=3392306 ）のために、OS X で NASM 2.11.08 はまともに使えません。

Homebrew を使っている場合は nasm21106 で 2.11.06 が入りますのでそちらを使いましょう。あるいは git から最新版の NASM も使えるかもしれません（試してない）。

松屋ジェネレータジェネレータによる、よりカオスなメニューの生成

この記事は(略

松屋の思い出

学生時代、東小金井駅前の松屋ができる前から、武蔵小金井の松屋まで歩いて行ってはよく食べていたものでした。食券制に慣れてしまいうっかり宝華で無銭飲食（勘定忘れ）をやりかけたことが一度あります。ですが国分寺ではスタ丼（「すた丼」ではない）からんぷ亭に行くことがもっぱらでした。らんぷ亭のとうふ麺はいつか復活してほしいものです。

松屋ジェネレータジェネレータ

作ったのは、松屋ジェネレータtoshi-a.hatenablog.comのようなものですが、松屋のウェブページからデータを取ってきて、ジェネレータのためのデータも自動生成させています。ソースコードは以下。

部分ごとに解説します。

open('index.html'){|file|
  file.each_line {|line|
    if (line =~ %r!\A\<noscript\>\n\z!)..(line =~ %r!\A\</noscript\>\n\z!) then
      if m = %r!\A\<li\>\<a href\=\"\/menu\/([^/]+)\/!.match(line) then
        dirnames << m[1]
      end
    end
  }
}

index.html から各メニューへのリンクの情報を取り出しています。最初は REXML で解析しようとしたのですがvalidでないということでエラーになるので諦めました。

begin
  Dir.mkdir 'menu'
rescue Errno::EEXIST
  STDERR.write "directory already exist: ignored\n"
end
path_base = Pathname('menu')
dirnames.each {|dirname|
  sub_path = path_base + dirname
  begin
    sub_path.mkdir
  rescue Errno::EEXIST
    STDERR.write "directory already exist: ignored\n"
  end
}

ダウンロード先にするためのディレクトリを作っています。

dirnames.each {|dirname|
  ofile_path = path_base + dirname + 'index.html'
  url_str = "http://www.matsuyafoods.co.jp/" + ofile_path.to_s.gsub(Pathname::SEPARATOR_PAT){'/'}
  pid = spawn({}, ['/usr/bin/fetch', 'fetch'], '-o', ofile_path.to_s, url_str)
  Process.waitpid pid
  sleep(10+rand(10))
}

各サブメニューのHTMLを fetch で取ってきます。

menus = []
Dir.glob('menu/*/index.html').each {|path|
  open(path){|file|
    file.each_line {|line|
      if m = %r|\A\<h4\>(.+)\<\/h4\>\<\!\-\- [1-9][0-9]* \-\-\>\n\z|.match(line) then
        menus << m[1]
      end
    }
  }
}

やはりad hocな感じでメニュー文字列を取り出します。一番長いのは「肉カレーうどん（プレミアム牛めし使用）ミニプレミアム牛めしセット」でしたが、そんなメニューが実在するのですね。

bigram = {}
menus.each {|menu_str|
  last_char = :START
  menu_str.each_char {|c|
    bigram[last_char] ||= {}
    bigram[last_char][c] ||= 0
    bigram[last_char][c] += 1
    last_char = c
  }
  bigram[last_char] ||= {}
  bigram[last_char][:FIN] ||= 0
  bigram[last_char][:FIN] += 1
}

全てのメニュー（文字列）について、「ある文字の次に、別のある文字が現れるのはいくつか」をカウントします。順方向のバイグラムという奴です。

本格的な自然言語処理では、ここで事前処理を頑張るわけですが、ここでは手抜きをして、生データのまま、次の生成に使ってしまいます。

rand_gen = Random.new
loop {
  current_char = :START
  loop {
    next_hash = bigram[current_char]
    total = next_hash.values.inject :+
    r = rand_gen.rand total
    keys = next_hash.keys.sort_by! {|c|
      if c == :FIN then
        Float::INFINITY
      else
        c.ord
      end
    }
    keys.each {|k|
      r -= next_hash[k]
      if r < 0 then
        current_char = k
        break
      end
    }
    break if current_char == :FIN
    print current_char
  }
  puts
}

分析の逆で、「この文字の次に現れる文字はこれとこれとこれで、確率は...」というデータにもとづいてメニュー文字列を生成しています。実際に生成させてみると、たとえば次のような感じになります。

オリジナルカレミニ牛めしポンソージエッグW定食
おろし
きつねうどんミアム牛めし
肉カルビ丼
大根お子
きつねうどん
肉使用）
プレミアム牛皿＜選べる小鉢＞
豚汁変更
ブラス
オリルチキム牛肉カレーグセット
焼鮭
お新香
とろろし
納豆（プレミニラウング定食
プレートマト
とろたま
オリジルチキンバーうどん
きつねうどん（関西風だし）＜選べる小鉢＞
ビ焼肉カレーグセット
生野菜100000000%使用）
プレミナ豚テト
みそ汁
肉使用）
ビビ焼鮭
ミナ豚テト券
ミニ牛めし
焼肉定食
プラ焼定食
オリジナルチセット
大根お子
肉使用）ミアムカレンソーうどん（関西風だし
冷やっこ＜選べる小鉢＞
ネギ付）
焼きつねうどん（プレーうどん（プレミアム牛めしセット券
とろたまト
ビビビ焼肉使用）＜選べる小鉢＞
ソーセッグW定食
ビビ焼肉カレーうどん（関西風だし）
アム牛めし）ミニプレーグセー
定食
牛めしプレミアムチキムチキン酢牛めしセーグ定食
プレー

カッコの特別扱いとかをしていないので、対応していないカッコがちょっと不気味ですね。あと100000000%とかいう変なパーセントが出ています（逆に "生野菜10%使用" とかいうと残り90%はなんなんだ、という感じですね）。