カウンタとか加算器とか

このへん説明してみようかと思いました。花嫁修行のお供に。

http://shinh.skr.jp/m/?date=20071104#p06

 seq 1 1000 | sed '
 # : はラベル。なんか知らんけど少なくとも GNU sed は無名ラベルも OK 。
 :
 # 0 があるなら {} の中身を実行。
 /0/{
   # 入力をホールドスペースに退避しつつパターンスペースにホールドスペースを。
   # パターンスペースには数値であらわしたカウンタを入れる予定。
   x
   # 数値に _@0123456789_0 というサフィックスをつける。
   # 19 って数値が入ってたとしたら 19_@0123456789_0
   s/$/_@0123456789_0/
   # も一個ラベル。
   :a
   # 先頭に _ があったら 1 に変える。
   # 最初は空文字だってのと繰上がった後の処理を兼ねる。
   s/^_/1/
   # インクリメントを行う正規表現。
   # サフィックスの左にある文字が今インクリメントしようとしている数値。
   # この数値が \1 に入るんだけど、そのすぐ右には次の数値 (\3) が入ってるので、
   # \1 をその \3 に変えることによってインクリメントができる。
   # \3 の中身が少しややこしいのは \1 が 9 の場合に _0 に置換するため。
   # その場合、 19_@0123456789_0 => 1_0@0123456789_0 => 20@0123456789_0
   # という手順で繰上がりの処理が行われる。
   # 9 だった場合は _0 になるので一つ前の正規表現にひっかかる。
   s/\(.\)_\(.*@.*\1\(_*.\).*\)/\3\2/
   # インクリメントに成功したらさっきの :a に飛ぶ。
   ta
   # 加えてあった @ から先を削除して
   s/@.*//
   # ホールドスペースにしまいつつまた入力を持ってくる。
   x
   # 入力から 0 を一個削除。
   s/0//
   # : の行に飛ぶ。
   b
 }
 # 最終行なら
 ${
   # カウンタ取ってきて
   x
   # 表示。 q とかでもいい。
   p
 }
 # 入力は表示して欲しくないので削除。
 d'

これ とやってること同じだけどまぁ洗練されてる感じ。

これをぐるぐる回せば任意の加算ができるわけだけど、さすがにそれでは遅すぎるので各ケタの計算とかを一気にやる方法を考えることになる。 sed の examples とかに入ってる dc.sed とかはそれをやっていて、アイデアとしては、 Perl で書くと、

 $_='5+2';
 print;
 s/$/;9876543210;9876543210/;
 print;
 s/(.)\+(.);.*\1(.*);(.*\2(.*))/\3\5\4\4/;
 print;
 s/.{19}(.).*/\1/;
 print;

の実行結果の

 i@umu ~/wrk/ag> perl -l adder.pl
 5+2
 5+2;9876543210;9876543210
 432101098765432109876543210
 7

とかを見るとなんとなくわかるんじゃないかなぁと思う。要は数値をうまいこと文字数に変換して、その文字数だけ "98765432109876543210" っていう文字列の左っかわに置くと、 20 番目の数字が足し算の結果になっている、っていう。

で、それに加えて繰上がりの計算とかゴルフとかすると、以下みたいにフィボナッチが sed で求められる、と。

 s/$/1/
 :
 /^18/q
 p
 x
 G
 s/\n/:0/
 s/$/@ 9876543210/
 :a
 s/ .*/&&/
 s/\(.\?\)\(:.*\)\(.\)\(@.*\)\( .*\1\(.*\) \(.*\3\(.*\)\)\)/\2\4\6\8\7\7\5/
 s/\(.*@\).\{19\}\(.\).\{0,9\}\(.\?\).* .* /\2%\1\3 /
 /:@/!ba
 s/^0\|%\|:.*//g
 b

追記: ループ無しでインクリメントってできるんだなーと気付いた。無限精度じゃなくなるけど。

 $_='9199';
 s/$/;0000000000000000/;
 s/(9*);/;\1/;
 s/;.{16}(.*)/;\1/;
 s/$/;01234567891/;
 s/(.?);(.*);.*\1(.).*/\3\2/;
 print;

sed で Quine

あなごるのデッドラインまでに書けたので嬉しかったのでした。

s/^/s_S^_SD_S;h;s!_[S]!_S!g;H;x;s!.s_S^.D!!;H;x;s@D.*[@].s@s@/;h;s!_[S]!/!g;H;x;s!.s/^.D!!;H;x;s@D.*[@].s@s@

最初の s/// の中に書けない / を _S としておいて後から頑張って復元するんだけど、全ての _S を / にしちゃうと、今度はエスケープのままになってるべき部分とかも / になっちゃってムキーなのでホールドバッファを使ったり。あとはバックスラッシュを使うとそれもエスケープしにゃならんくなって長くなるのでそれを意地でも回避する。

あと最後の

s@D.*[@].s@s@

って正規表現中にセパレータ含めるってのはすごいと思いました。 Perl にも Ruby にもできない芸当でござる。なんかどっちかっていうとそれはバグじゃないかとか思ってしまうけど。 GNU awk もできるみたいだ。

i@colinux ~> echo / | awk '/[/]/ {print}'
/

mawk はだめみたいだ。

i@colinux ~> echo / | mawk '/[/]/ {print}'
mawk: line 1: regular expression compile failed (bad class -- [], [^] or [)
[
mawk: line 1: syntax error at or near ]

最近のあなごる sed 編

sed はいいよね、と思い出した。んで主に sed でちょっと複雑なことしてるものを。最近どの問題見てもまず sed で解くには…とか考えてる気がする。なんていうかただ解くだけでそれなりにカタルシスが得られて良いです。

http://golf.shinh.org/p.rb?LCS#sed

問題文を一部流用するという話。

1h
1d
/B/s/....\(.\{32\}\)/\1/
/a/{x
s/aa/a/
s/ar/a/}
/A\|a/!s/\(.\{51\}\).*/\10100001000001010011010000101000001100000000001111110001001000010101010011001011000111101010000010001101111/
  • transpose.sed

http://golf.shinh.org/p.rb?transpose+lines#sed

行と列を入れ替える問題。 emokenさんに1B負けてる。まーちょっと冗長な気はする。

H
${:l
g
s/\n\(.\).*/\1/gm
p
x
s/^.//gm
x
tl}
d

http://golf.shinh.org/p.rb?show+the+way#sed

あまり解いた覚えがないのだけど、普通に回答埋め込みぽい。これも emoken さんに負けてるなぁ。

s/3/ABC/
s/6/BADCBA/
s/9/DABADCBAB/
s/A/right\n/g
s/B/bottom\n/g
s/C/left\n/
s/D/top\n/g
q

http://golf.shinh.org/p.rb?FizzBuzz#sed

1-100を表示するのだけど、3の倍数はFizzに、5の倍数はBuzzに、15の倍数はFizzBuzzに変える、という問題。 sed でカウンタ作るのは 昔思ってたより はるかに簡単だなぁとい話。倍数の判定はカウンタとは別に ;;;; みたいなのをどんどん増やしていって、この数で判定している。

s/$/@Z;1234566789@01/
:l

s/\(.\?\)@\(.*;.*\1\(.0*\)\)/\3\2/
tl

h

/Z\(;;;\)*1/s/../FizzZ/
s/[^z]*Z\(;;;;;\)*1/BuzzZ/
s/Z.*//

p
g
/00/d
s/Z/@Z;/
bl

http://golf.shinh.org/p.rb?judge+Janken#sed

ジャンケンの判定問題。ボロ負け。まぁこの問題は回答埋め込みだろうなぁ。

s/P[^ ]*/5/g
s/Guu\|Rock/0/g
s/[A-z]\+/2/g
s/5 2\|2 0\|0 5/</
s/\(.\) \1/=/
s/...*/>/

http://golf.shinh.org/p.rb?delete+duplicate+lines#sed

重複行を取り除く問題。最初大差ついてたのに負けてるなあ。

G
/^\(.*\)\n.*\1/d
s/\n.*//
H

http://golf.shinh.org/p.rb?palindromize

はもうちょい様子見ますか。

む、 Perl の方 ySas さんが追い付いてるってことは同じ回答かな。

なぜか断続的に sed の話を書いています

返事を書こうとして忘れていたのでした。

http://www.tees.ne.jp/~sin-x/200610b.html#2001

セパレータですが。手で書く場合は面倒なのですが、適当にコントロールコードつっこんでやればいいと思います。たしか \x00 はダメですが、他のはたいてい大丈夫だったような。さっき ssed の @ を ^S にしてみましたが問題なかったです。「"^S" は使っちゃうけません」なら制約としてはカスみたいなもんですね。ただこれだとコード生成はできないのですが。

sed with variable 構想

http://d.hatena.ne.jp/shinichiro_h/20061010#1160420878

の続きです。前回、 sed ってなにか…?という解いに対して、 sedVM です、という回答を提示しました。 VM つーかマシン語をいじっていてめんどくさいのは、要するにレジスタなりスタック、 sed VM の場合レジスタの管理、これがめんどくさいのです。それならやるべきことは一つです。さぁ太郎君なんでしょう!?

使わなーい

そう! sed VM 向けコンパイラを書けばいいんです!というかぶっちゃけ変数さえあればいいです。メモリの使いかた(決してホールドスペースなどと呼ばないように。初心者が混乱する元です)が sed の難解さの根源なので、他はまぁみんな大人だし自分でできます。 sed の人は sed で変数をうまく扱えるライブラリを作ろうとかそんなこと考えてるみたいですが、本当に必要なのはマクロアセンブラじゃなくてコンパイラじゃないでしょうか…と。

というわけで…なの、ですが、これがヒジョーにめんどくさい。中途半端ですがまぁできた範囲で。続きは宿題です。

http://shinh.skr.jp/tmp/ssed.rb

i@u ~/wrk/bf> ruby ssed.rb hello.ssed > out.sed
i@u ~/wrk/bf> echo | sed -f out.sed
Hello
world!
Hello world!
Hello
Hello world!

echo | がいる理由は…まぁ sed だし。コードは以下みたいなもの。

# 代入
$h = "Hello "
$w = "world!"
$a = $h
$a += $w

# それぞれ表示する
p $h
p $w
p $a

# world! 以外はマッチするはず
$h =~ /Hello/ {
  p $h
}
$w =~ /Hello/ {
  p $w
}
$a =~ /Hello/ {
  p $a
}

生成されるコードは全部はると長いので、 $a += $w の部分だけを。

# $a += $w
g
s/[^@]*@\([^@]*\)@[^@]*/\1/
G
s/\(.*\)\n\([^@]*\)@[^@]*@[^@]*/\2\1/
G
s/\(.*\)\n[^@]*@\([^@]*\)@\([^@]*\)/\1@\2@\3/
h

こんな正規表現人間がイチイチ書けねーとわかっていただけますでしょうか。ちなみに @ を変数のセパレータにしてます。

ちなみにやる気なくなったのは私の脳内にある遠大すぎるロードマップが原因だと思います。

どうでもいいですけどさっきフト気付いたことがあります。 sed で bf コンパイラ書いてわーい大文字を小文字にする echo ができたぞー と喜んでいたんですが、これで終わりだということが判明しました。

i@u ~/wrk/bf> sed y/ABCDEFGHIJKLMNOPQRSTUVWXYZ/abcdefghijklmnopqrstuvwxyz/
AHO
aho
boke
boke
Ahi
ahi

y ってこういう目的で使うんですね!ラクにカウンタ作るためのものだと思ってたよ!

sed ってなんなの?

あーなんか言語紹介といえばこんなのがあったのでした。sed ってなんなのかという、とてもよくある疑問に対して私なりの回答です。まず実用を考えると、

sed 's/hoge/hage/'

このためだけに存在している言語です。メリットは perl -pe 's/hoge/hage/' より 4byte 短くてすむことだけです。これ以外の機能はスクリプト言語で十分なように思います。たまに勘違いしてる人がいる気がしますが、 y コマンドはカウンタを作るために存在しています。小文字を大文字に変換する、などと考えるとどのような時に使うのか皆目検討もつかず、ドツボにはまることうけあいです。気をつけましょう。ちょうど OOP を犬とか猫で教えるような話に似てるかもしれません。

で、 sed in depth 。 sed とはなにか? 誰がなんと言おうと、 sedVM です。以下に VM の仕様を示します。

命令セット(レジスタやメモリの移動系)

x
メモリとレジスタの入れ替え
h
レジスタからメモリにコピー
g
メモリからレジスタにコピー
H
レジスタからメモリのケツに追加
G
メモリからレジスタのケツに追加
d
レジスタをクリア

はい、どう見ても VM です。これ以降の命令はあんまり VM ぽくないので適当に。 :label で label ってラベルを作れて、 b label でそこに飛べます。おおアセンブラぽい。直前のマッチに成功していたらジャンプ、というのが t label でできます。えーとあとは p(rint) とか q(uit) とかはわかるかと。 print がある VM ってめずらしいねというツッコミは却下です。なぜなら ICFPC の UM はあったから。

で、とにかく重要なのは、普段 s/hoge/hige/ とかでやってる処理はレジスタでの処理だということです。で、 CISCアセンブラ書く人はわかってると思いますが、レジスタなんつーものは極めて短命です。 sed VM でも例外じゃないです。というかなんせ、1個しかレジスタが無いのですから、その大事度合いは x86 の 6 倍くらいになると予想されます。そこでメモリ領域があるのですが、恐ろしいことにこれも 1 つしかありません。しかし幸い、レジスタもメモリも文字列領域なので、基本的に無限長です。そこで、 1 つの空間を複数にわけて活用することになります。

そこまでわかっちゃえば、後は適当にメモリ内の 1行目はあの情報、2行目はあの情報、というような約束を決めて、毎回メモリから全データコピー→適当に正規表現で必要な情報を切り出す→処理→メモリのトップに返す→またメモリから拾ってる→とりあえずトップに返した情報を正しい位置に置く→メモリに返す、というサイクルを繰り返せば、とりあえず割と普通にプログラムができます。あとはエルフヘッダの知識と無駄に消費するための時間、ちょっとした工夫くらいがあればコンパイラも書けます!

で、えーと一応お約束なので。

$ {
 i Hello world!
}

どっちも説明してねー機能だった…

本気で sed で brainf*ck コンパイラ

前回、 bf => asm なコンパイラsed で書いたのですが、「bf のコンパイラとは bf の逆アセンブラのこと」であるという主張を読んで、ああ全くその通りだなぁうまいこと言うなぁと思うと同時に、じゃあ実行できるバイナリ吐けば単なる逆アセ扱いされないよね☆ということで根性で作りました。

http://shinh.skr.jp/koneta/bfx.sed

i@u ~/wrk/bf> time ./bfx.sed < hello.bf > hello
./bfx.sed < hello.bf > hello  4.29s user 0.03s system 98% cpu 4.390 total
i@u ~/wrk/bf> chmod 755 hello
i@u ~/wrk/bf> ./hello
Hello World!
i@u ~/wrk/bf> time ./bfx.sed < echo.bf > echo
./echo./bfx.sed < echo.bf > echo  18.81s user 0.03s system 99% cpu 18.932 total
i@u ~/wrk/bf> chmod 755 echo
i@u ~/wrk/bf> ./echo
abcDEFgh123
abcdefgh123

見ての通り、本気でコンパイル遅いです。 Hello world に 4秒かかるのは GHC にタメをはれるどころかそれより遅い自信があります。えへん。 echo.bf は k.inabaさん作 のものです。自作のヤツだと負の数を [-] でリセットしてる部分があったので、これは 255 でループかましてない処理系だとすんごい遅いので。まぁそのくらい実装はラクなのですが、実に飽きたのでもう終わりです…

あと普通のコンパイラにできて sed にできないことが一つありまして、なんと chmod ができません!これはとても残念なことです。

実装方針はですね…

  • めげない
  • バイナリ入ってる文字列置換をやろうとすると、途中で変な挙動したり改行入ったりと大変なので、まずASCIIで処理して、最後にまとめてバイナリに置換するといい。あと s/NUMFF/\xff/g が何故か終わらない処理になったのでループでごまかした。
  • あと別にプレースホルダはいらんかった。
  • アドレス計算必要な部分が3個所ある。プログラムヘッダのファイルサイズを記述する部分と、 [ の飛び先、 ] の戻り先。
    • まず [ が出てきたら適当に決めた CmpJ@FFF7 とかを埋めておく。あとファイルサイズの部分もヘッダとかを足した数値である CmpJ@0169 とかを埋めておく。
    • />$/ s/.$/Add3/ などとして、 > があったら Add3 とかに置換する。 3 は命令サイズ。
    • 前回書いた足し算処理の要領でアドレスを加算。要はさっきセットした 3 が 0 になるまでループしつつ全部の CmpJ@xxxx 。 の xxxx 部分をインクリメントしていく。
    • ] が出てきたらさあ大変。一番ケツの CmpJ@xxxx を CmpJexxxx に変えて、 xxxx をケツにくっつける。そんでからケツにくっつけた xxxx を引き算しながら、戻るべきアドレスを計算する。
  • とかごちゃごちゃやってから最後に ASCII をバイナリに変換してやる。

もう sed は金輪際さわらん。

ちなみに実行ファイルサイズは非常に小さいです。

i@u ~/wrk/bf> LA hello
-rwxr-xr-x 1 i i 1060  9月 22 17:11 hello
i@u ~/wrk/bf> LA echo
-rwxr-xr-x 1 i i 1406  9月 22 17:12 echo
なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h