Hatena::ブログ(Diary)

西尾泰和のはてなダイアリー

2016-12-30

(解決)tmuxにアタッチしようとしたらno sessions

Q: EC2への切断が切れて、再度ログインして、tmuxにアタッチしようとしたがno sessionsと言われてしまう。kill -10でもダメ。プロセスは生きている。何がいけないか?

A: AMIからインスタンスを作った時にデフォルトユーザとして作られた「ubuntu」で作業するのを嫌って別途「nishio」を作って作業していた。tmuxもnishioで立てていた。しかし再ログインした際にubuntuでログインしてしまったのでnishioのtmuxに接続できなかった。というケアレスミス。

2014-02-20

放射線耐性Quineの読解

放射線耐性 Quine (1 文字消しても動く Quine) - まめめも」という頭のおかしい(ほめことば)コードがリリースされていました。

以前「The Qlobe - まめめも」がリリースされた時は、Pythonに移植したら「難読コードを読んでみよう(Python初心者向け解説) - DT戦記(zonu_exeの日記)」という読解エントリーが上がって、書いた本人としても興味深く読ませていただきました。

最近「理解ってなんだろう」ということが気になっていて、人間が理解できていない状態から理解できている状態に変わる過程で何が起きているのかに興味があります。なので自分自身がこの変態コードを理解する過程で何を考えているかを記録してみることにしました。

ちなみに筆者のRubyスキルがどの程度かというと…さっき仕事に使っているVMでyohasebe/wp2txtを使おうとしたらRubyが入っていなくて、apt-get install rubyして再度挑戦したら今度はgemとかいうものが入ってないと言われてapt-getで入らないのでインストール方法をググってましたね。gemは今回初めてインストールしました。(その後ruby1.8を入れてしまってたせいでまたコケた)

-----

さて、まずはざっと眺めます。いくつか目につくキーワードがあります。

at_exit

at_exitはPythonにもatexitってモジュールがあって、これは「終了時に実行する」って機能なので多分似たようなもんなんだろうな。

rescue

rescueはPythonやJavaでいうところのfinallyだという知識があります(注:後でコレが勘違いだと気づきます)

なるほど、

try:
  do_X()
finally:
  do_X()

という形にすれば「エラーは1箇所」というルールからどっちか片方のdo_Xが壊れててもdo_Xは1回確実に実行されるというわけですかね。だけどもtryなどの周辺部が壊れたり、do_Xが構文上おかしい形に壊れてパースの段階で構文エラーになったら実行どころの話じゃないですねぇ。そこんところどうするんだろう。

##

##と二重にしておくことで、どっちか片方が消えても確実にコメントになるというわけですね。

##'

'abc'##'と言う形にすれば、cの後の閉じ引用符が消えた場合でもコメントの後の引用符までが文字列になることで構文エラーを避けられるのだな。でもこれだけじゃaの前が壊れたらダメだなぁ。どうやって回避しているんだろう。

eval eval

うーわ、メソッドのevalと変数のevalは別の名前空間ということですか。

「eval eval if eval==instance_eval」の行は「文字列evalも文字列instance_evalも書き換わっていなければ文字列evalを評価する」ってことね。このコード自体が壊れていた場合にrescueに入るのかな。

その文字列の中身もあんまりRubyコードっぽくない顔をしているなぁ。

gsub

なるほど、gsubで置換して元のコードを復元するのかな。

python> [(chr(n + 65), chr(92 if n < 1 else n+33)) for n in range(7)]
[('A', '\\'),
 ('B', '"'),
 ('C', '#'),
 ('D', '$'),
 ('E', '%'),
 ('F', '&'),
 ('G', "'")]

文字列リテラル

irb> %\aaa\
=> "aaa"

ひえー、こんな文字列リテラルがあるのか。

  • "%\aaa\"" → バックスラッシュが2つ目の引用符をエスケープするのでvalid
  • %\aaa\"" → バックスラッシュが引用符として使われるので"aaa"と""の結合になりvalid

こうやって開き引用符が消えても死なないようにしているんだな。閉じ引用符が壊れた時は先に説明した##'で守っている。

文字列の中身が壊れた場合は?

rescue

よく見ると"aaa".rescue x rescue 42という形になっているから一つ目のrescueは文字列のメソッドだなぁ。調べよう。Class: String (Ruby 1.9.2)にはrescueの記述がないからObjectに生えているのか?おや、Class: Object (Ruby 1.9.2)にもないぞ?

irb> "".rescue
NoMethodError: undefined method `rescue' for "":String

これはわざとNoMethodErrorを起こして次のrescueで捕まえるのか?

(この辺を調べる過程でrescue==finallyではなくrescue==catchだと気づきました。)

irb> "".rescue x rescue 42
42

しかしそれだと「eval eval if eval==instance_eval」がうまく行かなかった時のセーフティネットはどうやって実現するんだ?てっきり文字列のrescueメソッドを呼ぶと文字列がevalされるのかと思ったがそうではないようだ。

セーフティネット探し

eval != instance_evalの時には後半は実行されないからeval=...以降(以下、この部分を「後半」と呼ぶ)を全部削って実行してみよう。おっと、これでも出力される。

ははー、なるほど。文字列リテラル内へのコードの埋め込みか。

irb> "#{1+1}"
=> "2"

それでat_exitなわけか。このコードに突然変異が入っている場合、ここで実行されてエラーになっては困る。一方、ここに突然変異が入っているということは後半には入っていないわけだから「eval eval if eval==instance_eval」は確実に成功する。だからexit!0が入ってるのか。at_exitの仕様は知らないけど、exit!0したらat_exitで登録されたものが実行されないで即座に終了するんだろう。

rescue

irb> "#{abc}"
NameError: undefined local variable or method `abc' for main:Object

なるほど。前半部のコードに突然変異が入った場合にはat_exitがa_exitになるとか起こりえるので、そこでrescueで握りつぶしていあるんだな。42ってのは単に片方消えて4でも2でもvalidなリテラルになるってことで整数リテラルの都合が良かったんだろうな。

と、ここまでで昼休み1時間を使い切ってしまったので続きは仕事が終わってから。「Pythonでできるのかどうか」に関しては「任意引用符での文字列リテラル」がないところがかなり辛そう。

続き:目的の明確化

「だいたいわかった」ような気になってきたので、ここらで目的を明確にしておきましょう。いままで目的を明確化できていませんでしたが、いくつかそれらしきものがあります。

  • Pythonに移植できるかどうか判断する
  • 「人間が理解できていない状態から理解できている状態に変わる過程で何が起きているのか」の情報収集

前者は「できない」という結論が濃厚。後者はよく考えてみると「どこまでやれば終わりか」が明確でない「悪い目標設定」ですね。「理解できている状態」に変わったことを確認するためには、やっぱ何かを作って検証するのがよいのですけど、少なくともPython実装を作るのはあんまり現実的ではなさそう。じゃあ「解説」を作るのを目標にしようかな。今のところ「だいたいどこが壊れてもエラーにはならない」ぐらいのモヤッとした説明だけど、「どこが壊れてもエラーにならず、必ず壊れる前のソースコードを出力する」を、場合分けしてQEDするのを目標にするかな〜。

あと、ひと通り終わってからこのログを見なおして、僕が理解の過程で何をしているかを検証する感想戦的エントリーも書こう。

eval evalの動作の確認

eval evalが実行されればこのコードが再現されることを念のため確認しておきましょう。

まずはsがこうやって決まります。

s=%(B%A  C{at_exit{ZGQG##G

}}}ABB.rescue x rescue 42##B

Z=GQG##G

instance_Z=GQG##G

Z Z if Z==instance_Z
).gsub ?Z,%[eval]

%(...)が文字列リテラルで、それをgsubしてZをevalに置き換えています。置き換えた結果はこう

B%A  C{at_exit{evalGQG##G

}}}ABB.rescue x rescue 42##B

eval=GQG##G

instance_eval=GQG##G

eval eval if eval==instance_eval

次に7.times{|n|s.gsub! (n+65).chr,(n<1?92:n+33).chr}でA〜Gを置換します。置換テーブルを再掲

[('A', '\\'),
 ('B', '"'),
 ('C', '#'),
 ('D', '$'),
 ('E', '%'),
 ('F', '&'),
 ('G', "'")]

置換結果はこう

"%\  #{at_exit{eval'Q'##'

}}}\"".rescue x rescue 42##"

eval='Q'##'

instance_eval='Q'##'

eval eval if eval==instance_eval

なんでこんなことをしたかというと、特殊な意味を持つ#{...}だの%\...\の2つ目のバックスラッシュだのが発動してしまうのを避けたかったからですね。

最後にQを置換します。s.gsub ?Q,%[(eval q=%(]+q+%[))#]。あれ?このqはどこから…

あ、そうか。Rubyの文字列は破壊的変更ができるんだった。(追記:これは脇道にそれています)

irb> x=y="aaa"
=> "aaa"
irb> y[1] = ?A
=> "A"
irb> x
=> "aAa"

時系列での処理の流れでは、まずq=%(s=%(...))でqに文字列が入り、それからeval qでそれが評価される。

qの中身はこちら

s=%(...).gsub ?Z,%[eval]
7.times{|n|s.gsub! (n+65).chr,(n<1?92:n+33).chr}
puts s.gsub ?Q,%[(eval q=%(]+q+%[))#]
$stdout.flush
exit!0

qの中身では同一の文字列の一部をsと名づける。ここでgsub!ではなくgsubが呼ばれることで、新しい文字列インスタンスができている。(追記:これは勘違いです。元から別インスタンス)それからsに対して置換を行っているけど、qとは別のインスタンスになっているからsへの破壊的変更の影響はqには及ばない。最後にQと書かれている部分にqの内容を埋め込んで出力、標準出力をフラッシュしてexitする、と。

後半部破壊調査

さて、まず前半部at_exitの前の#を削って、セーフティネットが動かないようにして、後半部がどう壊れたらどうなるかを見てみましょう。

まずこの条件比較が壊れたらNameError

eval eval if eval==instance_eva
↓
quine.rb:48:in `<main>': undefined local variable or method `instance_eva' for main:Object (NameError)

==が=になっちゃったらtrueになるけど、この場合他の場所はこわれてないのでeval evalで期待通りの挙動をする。

ifやその周辺の空白が壊れてもNameError。evalや周辺の空白が壊れてもNameError。

文字列の中身が壊れても問題ないことは確認済み。

閉じ引用符が壊れたら文字列末尾のコメントが増えてeval==instance_evalが不成立になってセーフティネット行き。

ここの文字列の開き引用符が壊れたら?

instance_eval='(eval ...)#'##'

なんということでしょう。その瞬間evalが発動するので比較を待つまでもなく正常に出力してexitする。

ここの代入が壊れたら?エラーになってセーフティネット…かと思ったら違うや。instance_evalが文字列を引数として受け取ってevalするのでやはり比較を待つまでもなく正常に出力してexit。

変数名が壊れたら比較のタイミングでミスマッチになってセーフティネット行き。

セーフティネット調査

残るはここの部分

"%\  #{at_exit{eval'(eval q=%(s=%(B%A  C{at_exit{ZGQG##G

}}}ABB.rescue x rescue 42##B

Z=GQG##G

instance_Z=GQG##G

Z Z if Z==instance_Z
).gsub ?Z,%[eval]
7.times{|n|s.gsub! (n+65).chr,(n<1?92:n+33).chr}
puts s.gsub ?Q,%[(eval q=%(]+q+%[))#]
$stdout.flush
exit!0))#'##'

}}}\"".rescue x rescue 42##"

このゾーンに突然変異が入ったら、#{at_exit...}で登録された終了時命令が実行される前に、突然変異の入っていないはずの後半部が正常に出力してプログラムを終了させるはず。そうならない例外はこのゾーンに入った突然変異のせいで構文エラーが起きて実行フェーズが始まらない場合と、このゾーンの実行でエラーが起きてat_exitの登録が完了する前に死んでしまう場合。どちらも存在しないことを確認しよう。

まず、qの中身はどうなってもただの文字列だから問題ない。以下のコードで正常にat_exitが登録される。

"%\  #{at_exit{p 12345}}}\"".rescue x rescue 42##"

頭の引用符が消えた時、先に確認したように%\...\が文字列リテラルに化けるので問題なし。

#より前の文字が消えた時、単に文字列の変化だから問題なし。

#や{が消えた時、at_exitが実行されなくなるが、文字列に変わるだけだからエラーは起こらず、後半部が正常に働く。

at_exit{...}が壊れた時、実行時エラーや構文エラーが発生する。しかしこれは先に見たように2つ目のrescueが握りつぶすので問題ない。

irb> "#{at_exi}"
NameError: undefined local variable or method `at_exi' for main:Object
irb> "#{at_exit{}"
SyntaxError: (irb):33: syntax error, unexpected tSTRING_BEG, expecting '}'

at_exit{...}のとじかっこが壊れた時のために1つ余計に付けてある。これは "#{" だと2つ目の引用符が文字列の終了ではなく#{}の中身だと思ってパースを続けてしまい、rescueなどを突き破って構文エラーになるから。

引用符前のバックスラッシュが壊れたら?

"%\  #{at_exit{p 12345}}}"".rescue x rescue 42##"

この場合、".rescue x rescue 42##"が文字列リテラルに化ける。エラーが起こらず後半部が正常に稼働する。閉じ引用符が1個消えた時も同じ。行末まで文字列に化けるだけ。

.rescueのピリオドが消えたら?この場合「エラーを起こす存在しないメソッド呼び出し」だった.rescueが、制御構文のrescueに化ける。結果 "aaa" rescue x となるので文字列リテラルはエラーを吐かないからrescue xが実行されない。

rescueが壊れた場合はNameErrorになって2つ目のrescueが握りつぶす。

xと2つ目のrescueの間の空白が死んだ時には握りつぶせないNameErrorが出るが、その際には正常に登録されているat_exitが先に発動してexitさせるので問題ない。rescueと42の間の空白が消えた時も同様。

"%\  #{at_exit{p 12345}}}\"".rescue xrescue 42##"
↓
12345
quine.rb:1:in `<main>': undefined method `xrescue' for main:Object (NoMethodError)
# at_exitの処理の後に未キャッチ例外によるスタックトレース表示が起きている

42の片方が消えても数値リテラルであることは変わらない。##の片方が消えてもコメントが始まることに変わりない。#の後の"が消えてもコメントだから問題ない。

説明完了。ふー、疲れた。

まとめ

  • しょっぱなからrescueの意味を勘違いしていて普段Rubyに全然触れていないことを如実に表していますね。gem初めて入れた話なんかなくても良かったのではw
  • 実はエントリーを書く前はデバッガとか構文木を表示することが必要になるだろうと思ってたんだけども、ならなかった。
  • 1〜2時間で終わらせるつもりだったけど、結局4時間掛かってしまった。あ、確定申告の準備しなきゃいけないんだった…。

追記

ここでgsub!ではなくgsubが呼ばれることで、新しい文字列インスタンスができている。(追記:これは勘違いです。元から別インスタンス)

irb(main):038:0> eval x="y=%[hoge];y[1]=?a"
=> "a"
irb(main):039:0> x
=> "y=%[hoge];y[1]=?a"
irb(main):040:0> y
=> "hage"

gsubに!がついてたりついてなかったりするのは関係なかった。

2013-06-27

クイズ:一つのスイッチを押すと全部のLEDが消灯する

この前の日曜日、FPGAにつなごうと思ってこんなコントローラーを作っていたんです。左半分(十字ボタン)の配線が終わったところで、動作をチェックしようと思い、DE0のGPIOに接続して入力をLEDに出してみたのですが、なぜか「一つのスイッチを押すと全部のLEDが消灯する」という現象が起きました。その理由が面白かったのでクイズ形式でブログの記事にしました。

f:id:nishiohirokazu:20130627122756j:image

出題編

スイッチは、信号線とGNDの間に入っていて、信号線とVccをプルアップ抵抗でつないである、というオーソドックスなやり方です。4つのスイッチがブレッドボード上に実装されていて、ブレッドボードのGNDとVccを、それぞれDE0ボードのGNDおよび3.3Vのピンにジャンパーケーブルで接続しています。各スイッチの信号線も同様にDE0のGPIOピンに接続しています。

FPGA上ではGPIOのピンの値を読んで、それをそのままLEDの点灯消灯で出力しています。スイッチが押されると信号線がGNDと接続されるので入力の値がLOになり、LEDが消灯するという仕組みです。もちろん、押したスイッチに対応するLEDだけが消灯することを期待していました。しかし実際には全部のLEDが消滅します。

問:なぜこのような現象が起きたのでしょう?

ヒント1

ヒントは問題の解決に関係ないものも含めて全部で9つあります。

抵抗は4.7KΩのものが手元になかったので7.5KΩのを使いました。これは問題ないはず。

ヒント2

7.5KΩだと思っている抵抗が実は何を間違えたか75Ωくらいで、1個スイッチを押しただけでVccの電圧が低下してしまう…とか考えてカラーコードを確認してみましたが、紫緑赤金だったので抵抗値が間違っているという線は消えました。

ヒント3

スイッチを引きぬいて確実に開放状態にした上でも、1つのスイッチを押すとすべてのLEDが消灯します。信号線自体を引き抜くとそれに対応したLEDだけ消灯しなくなります。というわけでソフト側ではなくハード側の問題だとは思いましたが…

ヒント4

4つのスイッチを十字に配置するために配線がグネグネしているので、そこで何か間違っている可能性を考え、シンプルに2個のスイッチX、Yをつないでみましたが、やはりXを押してもYを押しても、XとY両方のLEDが消灯します。

諦めてジャンパーケーブルを抜いて片付けました。

ヒント5

「信号線の電圧をテスターで測ってみたら?」という提案を受けて、もう一度GNDとVccをそれぞれジャンパーケーブルをで接続してGNDと抵抗の足元との電位差を計測。スイッチを押していない状態で3.3V、スイッチを押した状態で0V、その時押されていない隣のスイッチは3.3V、と至極まっとうな状態でした。

ヒント6

ところがこの状態から信号線をジャンパーケーブルでDE0のGPIOに接続すると、スイッチXを押した時にはLED Xだけが消灯します。おやおや?「何もしてないのに直った」だなんて結論では満足出来ませんよ…。

ヒント7

スイッチYを押した時には何も消灯しません。スイッチYをつないでいるジャンパーケーブルを別のものに交換すると、スイッチYを押した時にLED Yだけが消灯する、本来の期待通りの挙動になりました。

ヒント8

元の十字スイッチを復元してみたところ、問題なく4つのボタンそれぞれを押した時にだけそのスイッチに対応するLEDが消灯するようになりました。

ヒント9

試しにその状態からVccをつないでいるジャンパーケーブルを抜いてみたところ、当初のような「どのスイッチを押しても4つのLED全部が消灯する」という現象が再現しました。

解答編

最初に作った十字スイッチ回路の、Vccをつなぐのに使ったジャンパーケーブルは実は断線していました。そのためブレッドボードのVccはどこにも繋がっていない状態でした。スイッチが一つでも押されると、そのスイッチの信号線がGNDに接続されてLOになるだけではなく、プルアップ抵抗と「Vccだと思い込んでいるただの配線」を通ってすべての信号線がGNDに接続されてLOになるわけです。

感想

ソフトウェアとハードウェアの大きな違い: ソフトウェアの部品は、一つのインスタンスが仕様通りに動くことを確認したら、どのインスタンスでも仕様通りに動く。ハードウェアの部品は、たまに仕様通りに動かないインスタンスが混ざっている。

ソフトウェアでは「あ、この代入演算子、断線してますね」なんてことがありえないので、そこを疑うコストを割かずに実装ができるわけです。とても恵まれています。

2013-05-31

再帰呼び出しを再帰呼び出しなしで実現

拙著「コーディングを支える技術」の第5章「関数」では、P.50で「再帰呼び出しを使っているプログラムは、再帰呼び出しを使わなくても書くことができる」と説明しました。この件に関してここで補足記事として解説することにしました。

P.53の簡単な再帰呼び出しの例(total関数)をターゲットにします。これは空行とコメントを除くと8行の簡単な例です。このコードから、挙動を変えずに再帰呼び出しを取り除いてみましょう。腕に自身のある人はは続きを読む前に自分で実装してみるとよいでしょう。

チャレンジする人向けの注意点

今回の対象では再帰呼び出しをしながら行う処理が「要素の足し算」でした。足し算は順番を入れ替えても結果が同じです。なので、うっかり計算の順番を変えてしまっても、結果からは間違いに気付けません。例えば深さ優先探索を幅優先探索に変えてしまうと、[1, [2, 3], 4]が本来の1, 2, 3, 4という順番ではなく、1, 4, 2, 3という順番で足されるようになります。実は今回のケースでは幅優先探索に変えてしまうコードの方がシンプルになります。しかしこれは題意を満たさないものとします。

また、今回のケースではresultをすべての関数から読み書きできるところに置いてしまうことができます。これは元のコードでローカル変数であったresultをグローバル変数に変えてしまうことに相当します。これをやると「値をどうやって返すのか」の考察が抜けてしまうので、減点対象ということにします。

最後に、元コードはPythonで書かれていたので、筆者も最初Pythonで実装しました。しかしPythonにはgotoがない為、whileで代用するなどトリッキーなコードになってしまいました。これは解説の都合上よろしくないので、gotoのある言語(C++)で書き直しました。読者のみなさんにもgotoのある言語で試すことをオススメします。

C++への移植

まずはP.50のサンプルコードを、なるべく逐語訳でC++11に移植してみました。

int total(const many& xs){
  int result = 0;
  for(const boost::any& x : xs){
    if(is_integer(x)){
      result += any_cast<int>(x);
    }else{
      result += total(any_cast<many>(x));
    }
  }
  return result;
}

is_integerの定義、C++でPythonのリストと同様の「型を気にしないリスト」を作るために使われているboost/any.hppについては今回の記事のスコープではないので割愛します。要望があればまた別途。

foreachの除去

さて、このコードでは「for x in xs」や「BOOST_FOREACH」というforeach構文が使われています。これは「与えられたリストの各要素についてループする」という構文なので、中断したり再開したりすることが難しいです。そこで、まずはこれを普通のfor文に書き換えました。

int total2(const many& xs){
  int i;
  boost::any x;
  int result = 0;

  for(i = 0; i < xs.size(); i++){
    x = xs[i];
    if(is_integer(x)){
      result += any_cast<int>(x);
    }else{
      result += total2(any_cast<many>(x)); // 次はこれを書き換える
    }
  }
  return result;
}

この関数のローカル変数は、xs, i, x, resultの4つですね。

さて、次はこの関数の中での「自分自身の呼び出し」を無くしていくことにします。


スタックを作る

P.48を読んでみましょう。「あとで元の値に戻せるように保存する」を実現するために、スタックを使うのでした。

本では「戻り先のアドレス」を保存するためにスタックを使っていましたが、ここではローカル変数を保存するために使います。

*1

普通にプログラムを買いている時には自分でこの「スタック」を管理することはありません*2が、今回は本物の関数呼び出しを使わずに「関数呼び出しと同じこと」を実現したいわけなので、自分で管理することにします。

とはいえ、それほど大げさなことではありません。空のstd::stackを作って、そこにデータを保存していくことにします。

また、関数からの返り値を入れる変数も作っておきます。

typedef std::tuple<many, int, boost::any, int> frame_t;
std::stack<frame_t> stack;

int function_result;
スタックに保存するべき値は何か

スタックに保存する値は、この関数のローカル変数xs, i, x, resultの4つの値です。そこで先程のコードでは「typedef std::tuple<many, int, boost::any, int> frame_t;」と4つの値を入れるための型を作っています。

「xは保存する必要がない」と思った人はいますか?それは正解です。ただし、それは「xは関数呼び出しから戻った後で読み出されることがない」というこの関数特有の事情を使って最適化をしていることになりますね。


「関数の呼び出し」とは何か

さて、次は「関数の呼び出し」とは何をすることか考えてみましょう。

  • 1: 今のローカル変数をスタックに保存して、後で戻せるようにする
  • 2: 引数xsを書き換える
  • 3: 関数冒頭にジャンプ

やるべきことはこの3つです。*3

そこでまず、関数冒頭にジャンプのためのラベルを作ります。

int total3(many& xs){
 ENTRYPOINT:
  int i;
  boost::any x;
  int result = 0;

そして関数の呼び出しはこうなります。

    if(is_integer(x)){
      result += any_cast<int>(x);
    }else{
      // 1: 現在のローカル変数をスタックに保存する
      stack.push(make_tuple(xs, i, x, result));
      // 2: 引数xsを書き換える
      xs = any_cast<many>(x);
      // 3: 関数冒頭へジャンプ
      goto ENTRYPOINT;

値を返す

ループが終わったら何をすればよいでしょうか。元のコードでは return result; していました。これは何でしょうか。

  • 4: 返り値を「返り値を置く場所」に置く。(これは人間が呼び出し規約で決めたもので、x86上でC++を書いているならEAXレジスタになる。今回はfunction_resultという変数を作った)
  • 5: 関数呼び出しの直後にジャンプ

やるべきことはこの2つです。

まずはジャンプのためのラベルを作っておいて…

      goto ENTRYPOINT;

    RETURNPOINT: // 6: 呼び出された関数からreturnするとここに戻ってくる

関数の最後でそこへジャンプするようにします。

    // 4: 返り値を決められた場所に保存
    function_result = result;
    // 5: 関数呼び出し直後(上記6)に戻る
    goto RETURNPOINT;

戻ってきた後に何をするか

関数呼び出しから戻ってきたあとには何をすればよいでしょうか。

  • 7: スタックに保存しておいた値を復元する
  • 8: 関数の返り値を使う

やるべきことはこの2つです。

長々と話しているうちに忘れてしまったかもしれないので再掲しますが、 いまやろうとしていることは「result += total(…);」を関数呼び出し無しで実現することでした。関数を呼び出し、その後で返り値をローカル変数のresultに足す必要があります。

    RETURNPOINT: // 6: 呼び出された関数からreturnするとここに戻ってくる
      // 7: スタックに保存しておいた値を復元する
      frame_t f = stack.top();
      stack.pop();
      xs = std::get<0>(f);
      i = std::get<1>(f);
      x = std::get<2>(f);
      result = std::get<3>(f);

      // 8: 関数の返り値を使う
      result += function_result;

全体

全体のソースコードはこちら。

https://github.com/nishio/learn_language/blob/master/langbook/extra/recursive/recursive.cpp

筆者の環境(Mac OS X 10.7.5)ではこんな感じで実行出来ます。

$ clang++ -std=c++11 -stdlib=libc++ -Wall -DVERBOSE recursive.cpp && ./a.out

一応期待通りには動いていますが、これは筆者にとって初めてのC++11プログラミングなので、なにかおかしなところがあればぜひご指摘下さい。

Q&A

なぜ再帰呼び出しをなくしたいのか ?

「なぜ再帰呼び出しをなくしたいのか」というご質問がありました。拙著では「普段あたりまえのように使っている構文の裏側がどのように動いているか」を理解するために4章で

  • if文のelse節を使わずに、同じ挙動を実現する(P.32)
  • while文を使わずに、同じ挙動を実現する(P.36)
  • for文を使わずに、同じ挙動を実現する(P.37)

という説明をしました。これはその続編です。5章で「関数がどう動いているか」の説明をしたので、これも「関数呼び出しを使わずに、同じ挙動を実現する」をやってみました。

そういえば昔「クラスを使わずに『インスタンスの作成』『継承』を実現する」をやったことがありました。これも改めて解説すると良いかもしれませんね。 (thanks: id:thujikun)

末尾再帰最適化ではスタックを使わないのでは?

「末尾呼び出しが最適化されている場合はとかスタックを使わないのでは」というご質問がありました。そうですね。

この記事では以下のように書きました。

「xは保存する必要がない」と思った人はいますか?それは正解です。ただし、それは「xは関数呼び出しから戻った後で読み出されることがない」というこの関数特有の事情を使って最適化をしていることになりますね。

今回の対象コードは関数呼び出しの後、いくつかの変数を使います。なので復元できるようにこれらをスタックに積む必要があったわけです。一方、末尾呼び出しは「関数の末尾」に関数呼び出しがあるわけですから、「関数呼び出しの後で使う変数」がありません。なので積むべき変数がないわけです。

今回の対象コードでは「xは使わないから積まなくてもいいよね」という最適化ができるわけですが、これがもっと進んで「何も使わないから何も積まなくていいよね」になったのが末尾呼び出しの最適化というわけです。(thanks: id:bouzuya)


拙著「コーディングを支える技術」の読者から頂いた質問など対して、こんな感じで補足記事を書いて行きたいと思っています。質問・感想はおきがねなくどうぞ。

この解説は拙著の第5章「関数」のP.56あたりに挿入されるのが適切かと思います。

拙著に関する他のエントリーは「「コーディングを支える技術」著者公式ページ」からたどれるようにします。

*1:脚注:実際にx86上のCでの関数呼び出しをした際にどうスタックに積まれているかを表示したりしてコラムにする?呼出規約の話に触れる?

*2:アセンブリ言語を使う場合はもちろん別

*3:呼出規約によっては引数xsを書き換えるのは呼び出された側の仕事、という点を補足するべきか

2013-03-06

Scalaのtraitはmixinか?

Rubyのmixin(モジュール)、Squeakのtrait、Scalaのtraitそれぞれについて:

Q1: メソッドの実装を持てる?

はい、はい、はい

Javaのクラスは「はい」、インターフェイスは「いいえ」、C++とPythonのクラスは「はい」

Q2: クラスがそれを複数個継承できる?

はい、はい、はい

Javaのクラスは「いいえ」、インターフェイスは「はい」、C++とPythonのクラスは「はい」

Q3: インスタンスを作れる?

いいえ、はい、いいえ

C++とPythonのクラスは「はい」

Q4: 複数個継承した際に名前が衝突しました、どうなる?

しれっと上書き、エラー(*)、エラー

(*) Squeakはクラス定義時には例外を投げず、衝突したメソッドを「衝突した旨の例外を投げるメソッド」に置き換える。ユーザが衝突に気づくのは、クラスブラウザでメソッドを確認した時か、そのメソッドを呼んだ時になる。

Q5: 継承パスに参加する?

する(?)、しない、する(?)

継承パスに参加しているかどうかの検証の仕方や、プログラミング言語のユーザにどういう影響をあたえるのか、がイマイチよくわからない。

Q6: それを継承したクラスが特定のメソッドを持つことを型で強制できる?(Scalaのself type annotation)

いいえ、いいえ、はい

Q7: あるクラスがそれと別のクラスとを継承している場合に、親クラスとそれとの間で名前が衝突したらどうなる?

それの定義で上書き、それの定義で上書き、エラー

まとめ

Q1 Y, Y, Y
Q2 Y, Y, Y
Q3 N, Y, N
Q4 O, E, E
Q5 Y, N, Y
Q6 N, N, Y
Q7 O, O, E

まあ、要するに「3つそれぞれ別物」だね。id:sumimさんの主張(Scalaのトレイトは実はトレイトじゃなくただのミクスイン)はQ5に関してScalaのtraitはmixinみたいなものということだし、id:kmizushimaさんの主張はQ4とかQ6のことを考えるとmixinとは違うだろということだろう。個人的にはQ3でSqueakが「はい」な点にギョッとした。

ソースコード: https://github.com/nishio/learn_language/tree/master/trait

気が向いたらC++とかPythonとかも追加しよう。