読者です 読者をやめる 読者になる 読者になる

crubyのFloatにFast inverse square rootを(モンキーパッチで)追加する話

Fast inverse square root自体については「30のプログラミング言語でFast inverse square rootを実装してみました!」( http://itchyny.hatenablog.com/entry/2016/07/25/100000 )を参照してください。

せっかくの高速な手法ですから、高速な実装を考えてみます。Rubyの場合、まっとうに実装するのであれば Math モジュールに追加するべきですが、性能のことを考えると関与するオブジェクトが少ないほうが良いですから、Float クラスにモンキーパッチで追加することにしました。

こんな感じになります。

#include <stdint.h>
#include <float.h>
#include "ruby.h"

static VALUE
fast_inv_sqrt(VALUE v)
{
  double d = RFLOAT_VALUE(v);
  if ((d > 0.0) && (d <= DBL_MAX)) {
    //NOP
  } else {
    rb_raise(rb_eFloatDomainError, "out of domain");
  }
  union u_di {
    double d;
    uint64_t i;
  } d_i;
  d_i.d = d;
  d_i.i = 0x5fe6eb50c7b537a8ULL - (d_i.i >> 1);
  double d2 = d / 2.0;
  double g = d_i.d;
  d_i.d = g * (1.5 - d2*g*g);
#if 0
  d_i.i += 0x4e1c39a47a8ULL;
  g = d_i.d;
  d_i.d = g * (1.5 - d2*g*g);
  d_i.i += 0x14b9e8a78ULL;
#endif
  g = d_i.d;
  return DBL2NUM(g);
}

void
Init_fisqrt(void)
{
  rb_define_method(rb_cFloat, "fast_inv_sqrt", fast_inv_sqrt, 0);
}

ポイントとなる点をいくつか説明してゆきます。

まず Init_fisqrt が拡張ライブラリのエントリポイントで、これは見たままかと思います。

関数 fast_inv_sqrt が本体で、最初と最後にある VALUE と double の相互変換は拡張ライブラリの書き方の定番通りです。

続いて引数の範囲チェックですが、浮動小数点数のチェックは「真になる条件」でチェックするのがセオリーです(比較に NaN が関わるると偽になるため)。

ビットパターンを保存した浮動小数点数と整数の変換に union を使っているのも、この手のトリックの定番と言っていいでしょう(標準において、未定義ではなく処理系定義のため、気休め程度だがマシ)。

単精度の時の 0x5f3759df に相当するマジックナンバーは、妥当と思われる方法で私が探索(詳細は略)したものです。

#if 0 でコメントアウトしてある部分は、せっかくなので高精度化を図ってみたコードですが、これがあると **(-0.5) で正確な値を計算するよりも遅くなってしまったのでコメントアウトしました。単にニュートン法をもう1回繰返すだけではなく、誤差で必ず負の側に予測可能な範囲でズレることがわかっているので、それを調整する加算も入れてあります。

続いてベンチマークに使ったスクリプトを示します。

#! /usr/local/bin/ruby23

require 'benchmark'

require_relative 'fisqrt'

a = 1.0

result = Benchmark.realtime {
  (0..10000000).each {|i|
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
  }
}
print "result: #{result}s\n"

result = Benchmark.realtime {
  (0..10000000).each {|i|
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
  }
}
print "result: #{result}s\n"

result = Benchmark.realtime {
  (0..10000000).each {|i|
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
  }
}
print "result: #{result}s\n"

次のようになります。わずかですが速いという結果が出ています。

result: 6.402902246918529s
result: 7.31780265388079s
result: 9.100973834982142s

4004のブートストラップキャパシタ

この記事で言及する「ブートストラップ」は、電気(電子)回路の技法のそれであり、コンピュータの電源投入時やリセット時などの起動シーケンスのことではありません。

(回路技法の)ブートストラップとは

既にご存じの方は飛ばしてください。

以下の2つの回路図は、『定本 トランジスタ回路の設計』(ISBN:9784789830485)の、第8章の 図2 と 図21 ですが、


赤い線で囲んだ部分に注目すると、1つめの回路ではグランド(0V)が基準となって動作する部分が、2つめの回路では自分自身の動作によって電位が決まる部分が基準になって動作するようになっています。

このように「自分自身の動作を利用して、動作電位が決まるような、電気(電子)回路の技法」は「ブートストラップ」と呼ばれています。語源はコンピュータの起動時の動作を指すそれとほぼ同じと思われますが、コンピュータのほうはプログラム内蔵方式のコンピュータができた戦後の頃にできた言葉であるのがほぼ確実であるのに対し、こちらはどうも戦時中(真空管回路)に、おそらくレーダーの研究開発などといったような秘密の下で考案されたものではないだろうかと思うのですが、由来を先日ざっと追ってみたものの、よくわかりませんでした。*1

最初に示した例はカスコード(cascode)方式の増幅回路のベース-エミッタ間の電位差を一定にするものでしたが、他に、ブートストラップの技法が使われる例としては、スイッチング電源のハイサイドがあります。

パワーMOSFETを電源などドライバ回路に使う場合、グランド側はNチャネルMOSFETを使えば、ゲート電圧が Vdd に近ければオン、グランド(Vss)に近ければオフ、という動作になるのでそれで良いわけですが、ハイサイド(電源側、Vdd 側)をそれと対称に構成しようとすると、PチャネルMOSFETが必要になります。しかし、Pチャネルは良い特性があまり得られず、品種も少ないですから、ハイサイドもNチャネルMOSFETで構成するわけですが、そうするとそのFETのソースの電位が Vdd に近くなっても十分に駆動するには、ゲートを駆動する電圧について Vdd + 2V~3V 程度のゲタを履かせる必要があります。

MOSFET のゲートですから、電流(電力)はたいして必要ないので、簡単なDCDCコンバータで電圧を作ったりするわけですが(『定本 続 トランジスタ回路の設計』の第10章に例があります)、スイッチング電源の場合は常に矩形波でパタパタしている電力を扱うわけですから、それをうまくキャパシタで利用してやる方法があります。

電源用モジュールの製品などで、外付け部品としてキャパシタが必要なものがありますが(ロームによるスイッチングレギュレータの解説 http://micro.rohm.com/jp/techweb/knowledge/dcdc/dcdc_sr/dcdc_sr01/829 や、TIによる降圧型スイッチングDCDCコンバータの解説 http://www.tij.co.jp/analog/jp/docs/analogsplash.tsp?contentId=54765 を参照)、そのキャパシタは「0V <=> Vdd」の矩形波を利用して「Vdd <=> Vdd+α」というような電圧を作ってやるのに使われているわけです。

1970年代のMOSプロセス

21世紀の現代ではもっぱらCMOSが使われているわけですが、1970年代~1980年代、なじみのある製品でいうと電卓戦争の時代から8~16ビットマイクロプロセッサの時代は、初期のメタル1層から2層へ、ロジックも PMOS → NMOS → CMOS と変遷があり、表向きにはスペックの向上として現れていますが、その裏にはいくつかのプロセスにおける変革があります(嶋さんによるこちらのコラム http://itpro.nikkeibp.co.jp/article/Watcher/20060323/233069/ が具体例に詳しい証言になっている)。

インテル4004(以下、ICの名前は単に4004等と呼ぶ)では、まだPMOSの時代で、しかもイオン注入によって部分的にディプリーション(ノーマリーオン)のMOSFETを作ることができるようになったのはもっと後であり(前述の嶋さんのコラムを参照。8080でもNMOSになっただけであり、イオン注入はZ80で採用された)*2、ブートストラップ方式によるちょっとしたトリックのような回路が使われています。

4004のブートストラップキャパシタ

4004では負電源とPMOSだったわけですが、それでは慣れない我々には少々非直感的なので、以下では正電源・NMOSで考えることにします。

相補型(CMOS)でないMOSで一般的な論理方式は ratioed logic と呼ばれるもので、NMOSの場合はハイサイドに小さめのトランジスタを置いて、プルアップする能動負荷とし、反対側に大きめのトランジスタでnotやnandやnorといった論理を作るものになります。

こんな感じです。上の能動負荷となっているFETについてですが、ディプリーション型であればゲートはソースかグランドに直結するわけですが、ここではエンハンスメント型ですから Vdd に直結されます。すると、出力が Low の時はロジック側の大きなトランジスタで引き下げられるわけですから問題ないわけですが、出力が High の時のプルアップが問題で、Low の時の電圧が上がりすぎないように小さめのトランジスタで駆動している上に、ゲート-ソース間の電圧として Vth 程度の電圧が必要ですから、Vdd まで出力を引き上げることができない、いわゆるフルスイングでない出力ということになってしまいます。

それでも問題ないように論理を工夫したりする方法もあるわけですが、4004では、以下で説明するようなちょっとトリックっぽいブートストラップの手法で、一時的に電源を越えるような電位を作って問題を回避しています。

4004の回路図は3枚に分かれていますが、そのうちの1枚「4004 ADDRESS REGISTER, INCREMENTER AND INDEX」というタイトルの図の片隅に、次のような注記があります。

ここで重要なのは下の2つで、プルアップ抵抗のように描かれているのは、実際にはMOSFETによる能動負荷だよ、ということを示すものです。上にあるほうは前述のような、単純にゲートをドレインに短絡したFETですが、トリックがあるのは下のFET2個とキャパシタを組み合わせたものです。「B」という記号は「ブートストラップ」の意でしょう。

この信号は時分割のバスなど、常に(矩形波による)オンオフがある信号であることが前提です。4004はレジスタに静的ではない回路を使っているため、動作をハードウェア的に完全に止めてしまうことはできない、完全には静的でない論理回路ですが、(実は)この部分も完全に静的ではなくある程度の動作が常に必要です。

まず、出力が Low で定常的だとする所から始めます。上のFETにより下のFETのゲートは Vdd-Vth 程度の電位になっています。出力は Low で、下のFETのゲート-ソース間電圧は十分にありますから、下のFETもオンになっていますが、前述のように ratioed logic のためにロジック側で出力は Low に引き下げられている、というような状態になっています。キャパシタがあるわけですが、ICの中に作れる程度ですから、定常状態で放置されれば電荷はそう長くは保ちません。

次に、ロジックの入力が変化して、出力が High に変化し始めた、とします。するとキャパシタが、いわゆる「スピードアップコンデンサ」のそれと似たような働きをすることになって、上のFETのソース=下のFETのゲートの電位が、出力電圧の変化に合わせて上がってゆき、2*Vdd-Vth 程度まで上がることになります。これにより下のFETがオンに保たれるため、普通であれば Vdd まで上がらないはずの出力が、Vdd まで上がります。

また、上のFETはゲート電圧よりもソース電圧のほうが高いため、オフ状態になります。

(普通のディスクリートMOSFETで似たような回路を作ろうとした場合、ソース電極がサブストレート(バルク)にも接続されていて寄生ダイオードが存在するため(よく使われる右のような記号はそれを表現したものです)、ソースの電位をドレインより上げても電荷が抜けていってしまいますが、ICの中ではソースとサブストレートを別にすることができます)

以上のようにして、4004ではブートストラップの手法により、動的な一部の信号線の( High への)駆動力が強化されています。

実装

マスクパターンでは、以上で説明したキャパシタが、余計な面積を必要としないように巧妙に形成されているはずです(が、力不足で説明できる所まで理解できていません)。

文献

嶋さんの本、

マイクロコンピュータの誕生―わが青春の4004

マイクロコンピュータの誕生―わが青春の4004

には、この手法に関して直接的な言及はありません。嶋さんは4004チップに関して論理設計だけでなく回路やマスクの作業もやっておられますから、それ自体については承知のはずですが、おそらく、フェデリコ・ファジンさんの功績であることから(自分のそれと混同されることを避けるために)言及しなかったのかもしれません。Z80においてイオン注入法を採用したことで、ディプリーション負荷FETが使えるようになった、という間接的言及といえる記述はあります(イオン注入法がデッドコピー対策のトラップのためにも使われた、という記述も興味深い所です)。

近年出たドキュメンタリー、

インテル 世界で最も重要な会社の産業史

インテル 世界で最も重要な会社の産業史

には、次のような記述があります( p. 183 )。

このなかでいわば「副産物」*3のように生まれた発明が、やがて半導体史上シリコンゲートと並ぶ意義を持つことになった。ファジンは個々のゲートを、相方となるトランジスタの上側にブートストラップしたのだ。それまで不可能と思われていたことである。この手法はすぐに普及し、それから四〇年にわたってほぼすべての種類のチップに利用された。(この段落後略)

というようにあるのですが、ここまでで説明したように4004で使われたブートストラップは、イオン注入法によるディプリーション負荷FETが使えるようになるまでの「つなぎ」的な色の濃い手法であり、CMOSになってからは忘れられたような手法ではないかと思いますので、何か違う感じもします。もしかしたら翻訳の際の影響かもしれませんが、もうひとつの鍵となった技術である buried contact が関係あるかもしれません。

なお同書は、(『電子立国』ではあまり語られなかったため、日本などではあまり知られていない)当時の、また他の多くの時代のインテルの内情が書かれており、「マイクロプロセッサは誰の功績か」などといった話題についても(他社への言及が無い点を除けば)フェアかつ背景に踏み込んだ記述もあり、必読の1冊ではないかと思います。

*1:1955年に出願された特許の中に出てくるのが確認できるのだが、あたりまえの技術として言及されているように見える https://www.google.com/patents/US2850629

*2:4004の回路の素子について、デプレッション型、と言及している記事があるが http://www.atmarkit.co.jp/fsys/zunouhoudan/139zunou/4004_40thanv.html 誤解ではないかと思われる。

*3:原文では傍点

情報処理学会発足の頃の話

これはハードコピーを見せたほうがインパクトがある、だろうと判断して持っていったところ、興味を持っていただけたのですが、


この「情報処理学会の発足は1960年、昭和でいうと35年」というのは、電気系6学会あたりに居る人でも(最近は? あるいは情報処理以外の所属だと)あまり知られてないようで、そのあたりの情報へのポインタとかを書いてみようと思います。

創設秘話、といったようなものは(某学SF研の創設の言葉は「闇あれ」だったと伝え聞いておりますが…脱線)、後々になってから面白い話が出てきたりもするものですが、情報処理学会の場合は古いほうに興味深いものがあり、現在「50年史」の附属資料として配布されている「学会30年のあゆみ」中の「30年の軌跡」の冒頭部分をまず読んでみるのが良いように思われます。

(PDF) http://www.ipsj.or.jp/50anv/50nenshi/data/pdf/0101.pdf (PDF)

そこに「発足 情報処理学会は事実上,山下英男(所属:略),和田弘(所属:略)によって創設された.」と端的に書かれていますように(所属については当該2次文献執筆時のものであるため略した)、先見的なヴィジョンを持った少数のリーダーシップにより設立されたというように伺えます。

両先生については、情報処理学会のコンピュータ博物館(バーチャル博物館)にある「日本のコンピュータパイオニア」にある記事も参考になるでしょう( http://museum.ipsj.or.jp/pioneer/h-yama.html http://museum.ipsj.or.jp/pioneer/h-wada.html )。

また、2010年に『情報処理』に掲載された和田弘先生のインタビュー(インタビューは2004年 http://id.nii.ac.jp/1001/00069850/ )も参考になると思います。これはもうほんとに『電子立国』の世界で、あと、アスキーから出ていた本『計算機屋かく戦えり』にもインタビューが収録されていますが、そちらについては電子化という噂を聞いたような気もしますがどうなっているのかな……

Gauche の util.stream の stream-delay はなぜあるのか、どういう場合にどのように使うものなのか?

All problems in computer science can be solved by another level of indirection. (David John Wheeler)
But that usually will create another problem.

これは、デビッド・ホイーラーさん*1wikipedia:デビッド・ホイーラー)による格言ですが、遅延データ構造はインダイレクション(定訳は無い気もしますが「間接化」でしょうか)による御利益が最もよくわかるものの一つではないでしょうか。

Gauche の util.stream( http://practical-scheme.net/gauche/man/?l=jp&p=util.stream )では stream-delay というマクロが提供されています。このライブラリは SRFI-40( http://srfi.schemers.org/srfi-40/srfi-40.html )準拠ですから詳細はそちらを読めば全て書いてありますが、なぜ用意されていて、どういう場合にどう使うものか、ざっとまとめておく意味はあるように思いますので、以下にそれを書きます。

リファレンスマニュアルの記述

Gauche のリファレンスマニュアルには次のようにあります。

Macro: stream-delay expr

    [SRFI-40] exprの遅延形式であるストリームを返します。

    原則として、ストリームを生成する関数はすべからく結果を stream-delayでラップすべきです。

「結果を」とありますが、関数の返す値が常に delay されたリスト、すなわちストリームであるべき、ということであれば、ストリームの構成子である stream-cons(と、stream-null )の返す値がそうなっていれば良いはずで、実装が表に出てしまっているように見える stream-delay がなぜ存在するのか、いまいちわかりにくく感じられるかもしれません。

実際にはこれは「ストリームを生成する関数」の「結果だけ」ではなく、それ自体の振舞いに関係していて、SRFI-40 を実装したライブラリには必須のマクロです。

遅延プリミティブ

まず、ここでの議論のための実装のために、以下のような遅延プリミティブを使うこととします。

(define-syntax delay
  (syntax-rules ()
    ((_ val)
      (lambda () val))))

(define (force thunk) (thunk))

全くナイーブに実装した delay と force です。本格的にはメモ化とかを実装すべきでしょうが、ここでの議論にはこれで十分です。

oddストリーム

SRFI-40 中では、ストリームを実装する戦略について、oddとevenの2通りの戦略がある、と分類しています。oddとevenという名前の理由については後で説明します。SICP の本文中で示されている(日本語版では p. 189 にある)実装はoddで、SRFI-40 のストリームはevenです。oddストリームの実装は次のようになります(ここで、単に cons car cdr とあるのは、実装基盤のScheme処理系のそれを使うという意味になります)。SRFI-40 中の解説では cons1 などのように "1" というサフィックスが付いています。

(define-syntax odd-cons
  (syntax-rules ()
    ((_ elem strm)
      (cons elem (delay strm)))))

(define (odd-car strm)
  (car strm))

(define (odd-cdr strm)
  (force (cdr strm)))

見てわかるように、cdr-partだけを遅延させています。force / delay はそれぞれ1箇所に入り、実装の詳細は綺麗に掩蔽されていて、一見エレガントなように見えます。

しかし実際には問題があります。odd-cons はマクロですので、それ自体ではcar-partにあたる引数 elem を評価しませんが、展開結果に cons が直接あり、その引数として直接 elem を渡してしまっていますから、結果として odd-cons があると、そこで car-part の実引数は評価されてしまいます。これは「cons should not evaluate its arguments」という、遅延ストリームの基本に反しています。

わざとらしいですが、簡単な例で示します。

(define (my-take n strm)
  (if (= n 0)
      '()
      (cons (odd-car strm) (my-take (- n 1) (odd-cdr strm)))))

(define (stream-from-n n)
  (print n)
  (odd-cons n (stream-from-n (+ n 1))))

(print (my-take 4 (stream-from-n 0)))

実行すると次のように出力されます。

$ gosh sample-odd.scm
0
1
2
3
4
(0 1 2 3)

ここで my-take が odd-cons でストリームを作っていれば問題は無いわけですが、このように普通の cons でリストを作ろうとすると「その中身にアクセスされることはないが、odd-cdr によってforceされてしまうconsセル」は作ってしまうため、そのconsセルのcar-partに相当する評価は起きてしまいます。SRFI中では、ある種の off-by-one errorhttp://catb.org/jargon/html/O/off-by-one-error.html )だ、と言っています。

ストリームがこのような「oddストリーム」であるため、SICPの本文中のコードには、陽に delay を使っているものがあり、なぜそうしなければならないかという練習問題になっています。

evenストリーム

SRFI-40 では、以上のようなoddストリームの問題が解決された手法として、evenストリームというものが示されています(他にもう一つの考え方としては、cdr-part だけでなく car-part も遅延させる、という方法もあると考えられます。Haskellなどの、任意の値が遅延されるスタイルに近いのはそちらとも言えます)。

evenストリームの実装を示します。SRFI-40 中の解説では cons2 などのように "2" というサフィックスが付いています。

(define-syntax even-cons
  (syntax-rules ()
    ((_ elem strm)
      (delay (cons elem strm)))))

(define (even-car strm)
  (car (force strm)))

(define (even-cdr strm)
  (cdr (force strm)))

こちらでは、even-cons の展開結果の最上位に delay がありますから、consセルに含まれる要素(consセルが要素として指すもの)ではなく、consセル自身が遅延されたものになっています。その代わり、carを取るにもcdrを取るにも、まず force する必要があるように、force / delay があらゆる場所に必要になっています。言い換えると、このモデルは、oddストリームからバグを除いたという良い特性の代わりに、掩蔽が綺麗にできないものになっている、ということになります(ここでは議論しませんが、実用的な実装では force / delay のメモ化も重要になるでしょう)。

ここで、mapについて考えてみます。evenストリームによるmapの実装は次のようになります。

(define (even-map f strm)
  (delay (force
    (if (even-null? strm)
      even-null
      (even-cons
        (f (even-car strm))
        (even-map f (even-cdr strm)))))))

「 (delay (force 」とあるのは一見無意味なように見えます、が、無意味ではなく、「evenストリームとして正しい」mapは、このようになっている必要があります。以下でそれを説明します。

evenストリームにおける even-cons の定義から、その cdr-part である strm は、even-cons の時点では評価されず、後でforceされた時点で初めて評価される、ということがわかります。evenストリームにおいては、他の「ストリームを受け取り、そのストリームに何かをして返す」というような関数では全て原則として同様に、引数として渡されたリストの評価は、その関数が返した値がforceされるまで遅延されなければならない、ということになります。

even-map のコードを見ればあきらかと思いますが、もし「 (delay (force 」が無ければ、渡されたストリームは even-null? によってforceされ評価されてしまいますから、このように全体が遅延されるように囲ってやる必要があるわけです。

Gauche の util.stream など、SRFI-40 の実装では明示的なforceが要らないようになっているので、このコードにおける delay の側だけが stream-delay として残るということになるわけですが、それがなぜ要るかという理由は以上のようになります。

名前について

oddとevenという名前は、oddストリームの挙動は少し変だ(oddだ)ということにも掛けられていますが、SRFI-41( http://srfi.schemers.org/srfi-41/srfi-41.html )にわかりやすい表現があります。

すなわち、oddストリームのその実際の構造は次のようになってます。

(cons 1 (delay (cons 2 (delay (cons 3 (delay '()))))))

ここで、終端されているリストであれば、構成子 {delay, cons, '()} の数が、常に奇数(odd number)個になるはずです。

一方、evenストリームは、その前にもう1個 delay が付いて、

(delay (cons 1 (delay (cons 2 (delay (cons 3 (delay '())))))))

のようになり、常に偶数(even number)個になるはずだ、ということから、それぞれの名前となっています。

SRFI-41 との関係

SRFI-41 をそんなに読み込めてないのですが)SRFI-40 では、以上のように「実装が掩蔽し切れないdelay」について、ユーザにはプリミティブである stream-delay のみを提供するというスタイルとしていますが、ユーザの負担が大きいという判断か、SRFI-41 は、より多い機能を提供するものになっているようです。

SRFI-45 と lazy

Gauche のマニュアルに「Delayとforceとlazy」として記述がありますが( http://practical-scheme.net/gauche/man/?l=jp&p=Delay%E3%81%A8force%E3%81%A8lazy )、この記事で説明したように「 (delay (force 」を重ねるのは、ある種のスペースリークとも言えますので、それを潰したようなプリミティブが lazy で SRFI-45 で議論されています( http://srfi.schemers.org/srfi-45/srfi-45.html )。

*1:ブロックソートにおける「BW変換」の W の由来であり、古いコンピュータに詳しい人であれば Wheeler Jump の名も出てくるでしょう。

Macr055で順列の生成

マクロ(GPM)

続き。 http://parametron.blogspot.jp/2015/04/christopher-stracheygpm_27.html にある、順列の生成。

{m55_define|p2|$1$2$3
}{m55_dnl}
{m55_define|p3|`{p2|$1|$2|$3}{p2|$1|$3|$2}'}{m55_dnl}
{m55_define|p4|`{p3|$1$2|$3|$4}{p3|$1$3|$2|$4}{p3|$1$4|$2|$3}'}{m55_dnl}
{m55_define|p5|`{p4|$1$2|$3|$4|$5}{p4|$1$3|$2|$4|$5}{p4|$1$4|$2|$3|$5}{p4|$1$5|$2|$3|$4}'}{m55_dnl}
{p5||a|b|c|d}{m55_dnl}

Macr055でNクイーン

マクロ(GPM)

前回の4クイーンを元に一般化して「マクロを生成するマクロ」によるNクイーン問題( http://parametron.blogspot.jp/2015/04/christopher-stracheygpm.html )。

エスケープが妖しいことになってて、もしかしたら無駄な展開とか起きてるかもしれませんが、一応ちゃんと動いて、正しい結果は出ています。

リスト中では N = 8 を定義してエイトクイーンになっていますが、macr055 は awk で実装しているうえに効率とか考えていないので流石に遅く、手元の環境で実行し(他の作業もしていましたので安定したものではないですが)time で確認したところ3時間ちょっとかかりました。

{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|-|`{$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|or|`{$1|
  {m55_define|$1|t}
  {m55_define|f|$2}}'}{m55_dnl}
{m55_define|?|`{{lt|$1|$2}|
  {m55_define|t|`{{-|$2|$1}|
    {m55_define|{-|$2|$1}|f}
    {m55_define|$3|t}}'}
  {m55_define|f|`{{-|$1|$2}|
    {m55_define|{-|$1|$2}|f}
    {m55_define|$3|t}}'}}'}{m55_dnl}
{m55_define|gen1|`{$1|
  {m55_define|$1|``|$$$$$1'{gen1|{1+|$1}|$2}'}
  {m55_define|{1+|{1+|$2}}}}'}{m55_dnl}
{m55_define|gen2|`{$1|
  {m55_define|$1|````|$$$$$1'''{gen2|{1+|$1}|$2}'}
  {m55_define|{1+|{1+|{1+|$2}}}}}'}{m55_dnl}
{m55_define|gen3|`{$2|
  {m55_define|$2|```{or|{?|$$$$$1|$$$$1|0}|{or|{?|$$$$$1|$$$$1|$2}|''{gen3|{1+|$1}|{1-|$2}}'```}}'''}
  {m55_define|1|```{or|{?|$$$$$1|$$$$1|0}|{?|$$$$$1|$$$$1|1}}'''}}'}{m55_dnl}
{m55_define|gen4|`{$1|
  {m55_define|$1|````|$$$$$1'''{gen4|{1+|$1}|$2}'}
  {m55_define|{1+|{1+|$2}}|````|$$$$1|$$$$$1''''}}'}{m55_dnl}
{m55_define|gen_q|`{$1|
  {m55_define|$1|`{m55_define|q$1|`{qq$1|0'{gen1|1|$1}`}'}{m55_dnl}
{m55_define|qq$1|`{$$$$1|
  {m55_define|$$$$1|`{''{gen3|2|$1}``|
    {m55_define|f|`{q{1+|$1}'''{gen4|2|$1}```}{qq$1|{1+|$$$$1}'''{gen2|2|$1}```}'}
    {m55_define|t|`{qq$1|{1+|$$$$1}'''{gen2|2|$1}```}'}}'}
  {m55_define|$$$$'{1+|{1+|$1}}`|}}'}{gen_q|{1-|$1}}{m55_dnl}'}
  {m55_define|0}}'}{m55_dnl}
{m55_dnl}
{m55_define|N|8}{m55_dnl}
{m55_dnl}
{m55_define|gen5|`{m55_define|q$1|{gen6|1|$1}}'}{m55_dnl}
{m55_define|gen6|`{$1|
  {m55_define|$1|``$$$$$1 '{gen6|{1+|$1}|$2}'}
  {m55_define|$2|``$$$$$1
''}}'}{m55_dnl}
{gen5|{N}}{m55_dnl}
{gen_q|{1-|{N}}}{m55_dnl}
{m55_define|q0|`{qq0|0|$1}'}{m55_dnl}
{m55_define|qq0|`{$1|
  {m55_define|$1|`{q1|$1|$2}{qq0|{1+|$1}|$2}'}
  {m55_define|$2|}}'}{m55_dnl}
{q0|{N}}{m55_dnl}

Macr055で4クイーン

マクロ(GPM)

カレンダーは面倒そうな割にマクロ内で完結しなくてあまり面白くなさそうだったので、その次の http://parametron.blogspot.jp/2015/04/4.html 4クイーンから。

{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|-|`{$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|or|`{$1|
  {m55_define|$1|t}
  {m55_define|f|$2}}'}{m55_dnl}
{m55_define|?|`{{lt|$1|$2}|
  {m55_define|t|`{{-|$2|$1}|
    {m55_define|{-|$2|$1}|f}
    {m55_define|$3|t}}'}
  {m55_define|f|`{{-|$1|$2}|
    {m55_define|{-|$1|$2}|f}
    {m55_define|$3|t}}'}}'}{m55_dnl}
{m55_define|q4|$1 $2 $3 $4
}{m55_dnl}
{m55_define|q3|`{z|0|$1|$2|$3|$4}'}{m55_dnl}
{m55_define|z|`{$1|
  {m55_define|$1|`{{or|{?|$2|$1|0}|{or|{?|$2|$1|3}|{or|{?|$3|$1|0}|{or|{?|$3|$1|2}|{or|{?|$4|$1|0}|{?|$4|$1|1}}}}}}|
    {m55_define|f|`{q4|$2|$3|$4|$1|$5}{z|{1+|$1}|$2|$3|$4|$5}'}
    {m55_define|t|`{z|{1+|$1}|$2|$3|$4|$5}'}}'}
  {m55_define|$5|}}'}{m55_dnl}
{m55_define|q2|`{y|0|$1|$2|$3}'}{m55_dnl}
{m55_define|y|`{$1|
  {m55_define|$1|`{{or|{?|$2|$1|0}|{or|{?|$2|$1|2}|{or|{?|$3|$1|0}|{?|$3|$1|1}}}}|
    {m55_define|f|`{q3|$2|$3|$1|$4}{y|{1+|$1}|$2|$3|$4}'}
    {m55_define|t|`{y|{1+|$1}|$2|$3|$4}'}}'}
  {m55_define|$4|}}'}{m55_dnl}
{m55_define|q1|`{x|0|$1|$2}'}{m55_dnl}
{m55_define|x|`{$1|
  {m55_define|$1|`{{or|{?|$2|$1|0}|{?|$2|$1|1}}|
    {m55_define|f|`{q2|$2|$1|$3}{x|{1+|$1}|$2|$3}'}
    {m55_define|t|`{x|{1+|$1}|$2|$3}'}}'}
  {m55_define|$3|}}'}{m55_dnl}
{m55_define|q0|`{w|0|$1}'}{m55_dnl}
{m55_define|w|`{$1|
  {m55_define|$1|`{q1|$1|$2}{w|{1+|$1}|$2}'}
  {m55_define|$2|}}'}{m55_dnl}
{q0|4}{m55_dnl}

例によってローカルな再帰ができないため、そのへんの書き方が違っている。