2016-06-21

TL/1 の呼出規約を予想する

cdecl か PASCAL か

プログラミング言語 TL/1 について、呼出規約は cdecl か PASCAL を使っているものだろうと先日は予想した。では cdecl と PASCAL のどちらなのだろうか。それを検証するためにこのようなプログラムを実際に (TL/1 の実装のひとつである TL/1-FM で) コンパイルして動作させてもらった。

FUNC FOO

BEGIN
  WRITE(0: FOO(1, 2))
END

FOO(X)
BEGIN
  RETURN X
END

呼出規約が素朴な cdecl か PASCAL のどちらかであるという前提の元で、このプログラムが 1 を表示するようなら cdecl で 2 なら PASCAL である。その理由についてはここでは説明しないが、呼出規約の詳細はウェブ上に情報があるのでそれを参照してもらいたい。

結果は 1 であったとのことで cdecl だろうと予想された。

反例

ところが追加の検証で以下のようなプログラムの実行例をもらった。

PROC ZERO,ONE,TWO

BEGIN
  ZERO(12,23)
  ONE (34,45)
  TWO (56,67)
END

ZERO
VAR X,Y
BEGIN
  WRITE(0:X," ",Y,CRLF)
END

ONE(X)
VAR Y
BEGIN
  WRITE(0:X," ",Y,CRLF)
END

TWO(X,Y)
BEGIN
  WRITE(0:X," ",Y,CRLF)
END

実行結果は以下のようになるのだという。

12 23
34 45
56 67

この情報をくれたはりせん氏はローカル変数と引数渡しの領域がかぶっているのだろうと述べているが、 cdecl ならそんなことはありえない。 TL/1 (の処理系のひとつである TL/1-FM) が cdecl を呼出規約として使っているという予想は間違いだったということだ。

また、このような結果を生みだすようなスタックの利用方法を思い付かないでいる。実際のコンパイル結果を見れれば手っ取り早いのだが…。

C コンパイラはこうしている

では、 TL/1-FM コンパイラ以外はどうやっているのか。調べてみたところ gcc の MC6809 (FM-7 などが採用しているプロセッサ) 版があり、それを用いて上述の TL/1 コードと同等のコード、すなわち以下のようなコードをコンパイルしてみた。

#include <stdio.h>

void zero();
void one();
void two();

int main(void) {
  zero(12, 23);
  one(34, 45);
  two(56, 67);
}

void zero(void) {
  int x, y;
  printf("%d %d\n", x, y);
}

void one(int x) {
  int y;
  printf("%d %d\n", x, y);
}

void two(int x, int y) {
  printf("%d %d\n", x, y);
}

コンパイルされたコードは以下のようなものであった。

;;; gcc for m6809 : Mar 28 2010 21:13:35 [no tag]
;;; 4.3.4 (gcc6809)
;;; ABI version 1
;;; -mint16
	.module	test.c
	.area .text
	.globl _main
_main:
	pshs	u
	leas	-2,s
	leau	,s
	ldx	#23
	pshs	x	;movhi_push: R:x
	ldx	#12
	jsr	_zero	;CALL: (VOIDmode) (2 bytes)
	leas	2,s
	ldx	#45
	pshs	x	;movhi_push: R:x
	ldx	#34
	jsr	_one	;CALL: (VOIDmode) (2 bytes)
	leas	2,s
	ldx	#67
	pshs	x	;movhi_push: R:x
	ldx	#56
	jsr	_two	;CALL: (VOIDmode) (2 bytes)
	leas	2,s
	leas	2,s
	puls	u,pc
LC0:
	.ascii "%d %d\n\0"
	.globl _zero
_zero:
	pshs	u
	leas	-4,s
	leau	,s
	ldx	2,u
	pshs	x	;movhi_push: R:x
	ldx	,u
	pshs	x	;movhi_push: R:x
	ldx	#LC0
	pshs	x	;movhi_push: R:x
	jsr	_printf
	leas	6,s
	leas	4,s
	puls	u,pc
	.globl _one
_one:
	pshs	u
	leas	-4,s
	leau	,s
	stx	,u
	ldx	2,u
	pshs	x	;movhi_push: R:x
	ldx	,u
	pshs	x	;movhi_push: R:x
	ldx	#LC0
	pshs	x	;movhi_push: R:x
	jsr	_printf
	leas	6,s
	leas	4,s
	puls	u,pc
	.globl _two
_two:
	pshs	u
	leas	-2,s
	leau	,s
	stx	,u
	ldx	6,u
	pshs	x	;movhi_push: R:x
	ldx	,u
	pshs	x	;movhi_push: R:x
	ldx	#LC0
	pshs	x	;movhi_push: R:x
	jsr	_printf
	leas	6,s
	leas	2,s
	puls	u,pc

基本的には cdecl だが、最初の引数だけは x レジスタ経由で渡していることがわかる。いわゆる fastcall の一種といえるだろう。しかしこれでは TL/1-FM の挙動と同じではなく、参考にならない。

今回、この出力結果を読み解くにあたって MC6809 の命令セットなどを調べたのだが、興味深いことに MC6809 はふたつのスタックポインタを持っている。 S レジスタが基本的なスタックポインタとして用いられるが、 U レジスタも S レジスタと同じ能力を持っている。サブルーチンの呼出の際にリターンアドレスを積むときは S レジスタの方が使われるということだけしか差がないようだ。 gcc の MC6809 版では U レジスタを X86 でいうところの BP レジスタと同じようにしか使っていないが、もっと変則的な使い方もできるのかもしれず、それを活用した効率的な呼出規約があるのかもしれない。

Document ID: fdfa7c554d56db3aa97fba03d48a38fe

2016-06-20

TL/1 のエッジケース

プログラミング言語 TL/1 について、予約語と同じ名前の変数 (または関数や手続き) を宣言して使うことが可能であるということは以前に紹介した。その規則には仕様書からは読み取れない若干の曖昧さがあるのではないかという意見を述べていたところ、当時の実際の処理系 (TL/1-FM) で様々な例を試した結果をコメントで貰ったのでひとつひとつ検証していこうと思う。

うまく動く例１

VAR VAR
ARRAY ARRAY[2]
BEGIN
  ARRAY[1]:=123
  ARRAY[2]:=234
  VAR:=ARRAY[1]+ARRAY[2]
  WRITE(0:VAR,CRLF)
END

これについては基本的な動作であり、特に考察が必要な要素はない。 ARRAY という名前の配列が宣言された時点でそれ以後は ARRAY は配列名として解釈される。

うまく動く例２

VAR VAR
ARRAY VAR[2]
BEGIN
  VAR[1]:=123
  VAR[2]:=234
  VAR[0]:=VAR[1]+VAR[2]
  WRITE(0:VAR[0],CRLF)
END

名前 VAR は単変数と配列の両方で宣言しているが、このとき単変数ではなく配列として機能する。これも仕様通りの動作で、特に疑問なことはない。

以前に取り上げているが、複数の意味で宣言されているときにどれが優先されるかは仕様に明記されていて、単変数よりは配列が優先される。

TL/1 の変なところ (名前解決) - 主題のない日記

コンパイルエラーの例１

VAR VAR
ARRAY VAR[2]
BEGIN
  VAR[1]:=123
  VAR[2]:=234
  VAR:=VAR[1]+VAR[2]
  WRITE(0:VAR,CRLF)
END

エラーの内容

VAR VAR
ARRAY VAR[2]
BEGIN
VAR[1]:=123
VAR[2]:=234
VAR:=
Error : in 60

VAR を配列ではなく単変数で扱おうとしている個所でエラーになっている。上で述べたように、単変数より配列としての解釈が優先されるので仕様通りであり、不自然なところはない。

コンパイルエラーの例２

VAR ARRAY
ARRAY FOO[2]
BEGIN
  FOO[1]:=123
  FOO[2]:=234
  ARRAY:=FOO[1]+FOO[2]
  WRITE(0:ARRAY,CRLF)
END

エラーの内容

VAR ARRAY
ARRAY FOO[
Error FOO in 20

これについては仕様からは読み取れなかった挙動である。宣言がいつから有効になるのかという点について、個人的には BEGIN の直後からとするのが曖昧さが少ないと考えていたのだが、実際には宣言の直後からだったようだ。

コンパイルエラーの例３

VAR ARRAY
ARRAY:=123
BEGIN
 FOO[1]:=123
 FOO[2]:=234
 ARRAY:=FOO[1]+FOO[2]
 WRITE(0:ARRAY,CRLF)
END

エラーの内容

VAR ARRAY
ARRAY:=123
BEGIN

Error ARRAY in 30

これについては興味深い。 ARRAY:=123 に相当するオブジェクトコードは正しく生成されているそうなので、そこまでは正しいプログラムだとしてコンパイラは許容しているということになる。おそらくは、複文 (仕様書にない用語だがBEGIN/END 、またはその他の文括弧で囲んだ複数の文を便宜上こう呼ぶことにする) の扱いについて仕様に書かれていない解釈が存在するのだと思う。

複文は複数の文をまとめたひとつの文であるので、文が現れることが出来る個所にはどこにでも現れることが出来る。しかし、主プログラムや副プログラムの本体部分はたとえ文がひとつであろうとも BEGIN/END で囲まなければならず、他の文括弧を用いることもできない。それが仕様書から読み取れる仕様である。

しかし、実際の挙動は主プログラムや副プログラムの本体部分は単に「文」であればなんでも良いのではないか。他の文括弧を使った複文でも通りそうな気がする。

引数なし関数呼び出しの次の行の解釈でうまく動く例１

FUNC FOO
VAR X
BEGIN
  X:=FOO
  (X)
  WRITE(0:X)
END
FOO
BEGIN
 RETURN 2
END

実行結果

TL/1 は行指向ではない (改行は単に無視される) ので、関数名と引数の間に改行を入れても関係なく引数として渡されると解釈すべきで、定義より多く引数を渡す分には変数が参照されることはないのだから問題なく動作するのだろう。

引数なし関数呼び出しの次の行の解釈

FUNC FOO
VAR X
BEGIN
 X:=FOO
 {X:=1}
 WRITE(0:X)
END
FOO
BEGIN
 RETURN 2
END

実行結果

{} のかわりに () を文括弧として使った場合

FUNC FOO
VAR X
BEGIN
 X:=FOO
 (X:=1)
 WRITE(0:X)
END
FOO
BEGIN
 RETURN 2
END

エラーの内容

FUNC FOO
VAR X
BEGIN
X:=FOO
(X:=
Error : in 50

関数名の直後の開き丸括弧は常に引数の開始であると解釈するようだ。当時のコンピュータの能力を考えると少ない先読みでトークンの意味を確定しようとする設計は合理的と言える。おそらく TL/1 の文法を分類するなら LL(1) の範疇に収まるのではないかと思う。一方で、そもそも丸括弧を式括弧にも文括弧にも引数にも用いようとしているのが解釈し難さの原因でもあるので最初から分けておくべきだったとも思う。

引数付関数呼び出しを2行に分けて記述してうまく(?)動く例

FUNC FOO
VAR X
BEGIN
  X:=FOO
  (1)
  WRITE(0:X)
END
FOO
VAR Y
BEGIN
 RETURN 2+Y
END

実行結果

これは少しばかり奇妙な挙動だと思う。スタックレイアウトが想像できない。

Document ID: 6ed36823564fc58efd50e2fd7816e296

2016-06-20

響き

言葉というものについて、その意味を忘れて響きだけを感じたときに全く別の印象を持つことがある。まるで外国の言葉のようにも感じられたりする。たとえば2ちゃんねるの「ドイツっぽく便意を伝えたい」というスレッドで「フンバルトデルベン」というネタが高評価であった。確かにドイツ語らしい響きを感じる。

私が常々ドイツ語らしい響きのある言葉だと思っているのは「立憲君主」だ。カタカナでリッケンクンシュと書くとドイツを感じる。首脳会議をシュノー会議と書くとシュノーという地名がフランスあたりにありそうな気持ちになる。古民家などはロシア風に感じる。おそらくはトロイカの響きと似ているからだろう。

逆に外国で日本らしい響きと感じられる音もあるようだ。外国の (外国語の) 小説に登場する日本人の名前が実際にはとてもありそうにない、しかし響きは日本風であるという事例をいくつか見たことがある。まあ日本語の場合はわかりやすいだろう。基本の音は常に子音と母音が合わさっていて、拗音や促音が少し混ざる感じだ。要は母音がいっぱい入っていれば日本語風になる。 (実際には母音がかなり弱く発音される場合もあるが。)

特に外国語に詳しいわけでもないのにそういう印象が生じてしまうのは面白い現象だと思う。

Document ID: a7c80f3b0f3b75a876b0209ae527e98f

2016-06-19

TL/1 の呼出規約

私は以前にプログラミング言語 TL/1 のトランスレータを作った。その他、 TL/1 の面白いと思った部分を取り上げて何度か記事にしている。私が TL/1 を紹介するにあたって根拠にしているのは月刊 ASCII の 1981 年 1 月号であり、その号には TL/1 のサンプルとして連珠のプログラムが載っていて、自作のトランスレータでその連珠を変換できることも確認している。

TL/1 トランスレータ - 主題のない日記

しかし、確認するにあたって、掲載されていた連珠のプログラムに明らかな間違いがあることも発見している。仮引数が二個の関数を実引数なしで呼び出している個所が存在するのだ。

状況を単純化した例としてこのようなものを考えよう。

FUNC SQUARE

BEGIN
  WRITE(0: SQUARE)
END

SQUARE(X)
BEGIN
  RETURN X*X
END

関数 SQUARE は引数をひとつ取る関数であるにもかかわらず呼出側では実引数を与えていない。 TL/1 では最初に関数を宣言する段階では引数の情報を持たないので、パーサは SQUARE を呼び出している個所をエラーにすることは出来ない。コンパイラがこの間違いを検出するとしたら 2 パスにする必要があるが、古い時代の限られたリソースでコンパイルするとしたら厳密な処理はしなかった (エラーとして検出しなかった) 可能性は充分にある。

私は TL/1 については資料を読んだだけで実際に動く環境を持っていなかったのだが、実際に連珠のプログラムを当時のコンパイラでコンパイルしてみたという方から情報をもらった。実引数の数が間違っている連珠のプログラムは当時のコンパイラでコンパイルできたそうだ。しかも、ゲームとして問題なく動作しているように見えるとのことだ。このことから、 TL/1 の 1981 年当時のコンパイラでは引数の後始末を呼出側でやっているものと推測される。スタックがずれてしまえば動作どころではなく暴走してしまうのだから、スタックの整合性は保たれていると考えられるからだ。呼出規約が stdcall や PASCAL のような方式であれば、実引数の個数が間違っていても変数の中身が一時的におかしな値に見えるだけでスタックのずれは起こらない。

Document ID: 6640b10004b68b64362e7c7723299e0b

2016-06-10

強い非保証

前回はプログラミング言語の挙動は何によって保証されるかということを取り上げた。保証していないが現時点で実際そう実装されているということがあてにされてしまう場合が頻出すると追認する形で仕様になってしまう場合も少なくないのだが、保証しないという状態を更に強調した事例を思い出した。

プログラミング言語 Go の map (連想配列) である。 Go の map のイテレーションの順序は最初から保証はされていなかったが、データの数が小さい場合には一定の順序になっていて、それに依存するコードが結構あったらしいのである。そこで Go は乱数を使ってまで毎回順序を出鱈目にするように変更された。

Go 1.3 Release Notes - The Go Programming Language

保証しないという強い意思を感じる。保証していない挙動に依存している場合に問題が顕現しやすいようにするということを私は好ましく感じている。プログラムの汎用的な部品を書くときには「こう動くべきだ」という想定の他に動いてはいけない場合についての配慮が必要だということは常々思っていて、何度かそのことを記事にしてきた。

問題があるなら早めに判明すべきで、早めに判明しやすい設計は良い設計だと思う。

Document ID: 3895e4797a586a74f9ae676af458279b

2016-06-09

言語仕様と処理系仕様と実装と

プログラミング言語では仕様で保証されている挙動とそうでない挙動がある。単に検討されなかった部分について記述が漏れている場合もあるし、実装の裁量で効率的な方法を選択できるようにあえて規定しない場合もある。たとえば Scheme では map 手続きがリストを評価する動的順序は規定していない。これは仕様書に「未規定である」と明記されているので意図的に規定を避けたものだと思う。処理系によって、あるいは同じ処理系でも状況によって適当な順序を選択することが可能なのだ。副作用を生ずる手続きを map に渡した場合には状況によって異なる結果が生じることが有り得る。

とは言うものの、現実的には評価順序はリストの先頭からか末端からかのどちらだろうし、仕様に熟知しているのでなければリストの先頭側から評価するものと期待してしまうというのもそう不自然ではないだろう。初心者がそういうコードを書いているのを見たことは何度かある。また、 Gauche では map はリストの先頭側から処理することがドキュメントに明記されているので Gauche に限ってはそれを期待することが出来る。処理系の仕様として保証しているわけだ。

その他、手元の環境にインストールしている処理系で map がリストのどちら側から処理するか試してみた。以下はリストの先頭側から処理した処理系だ。

Sagittarius 0.7.4
Chicken 4.11.0
Scheme48 1.9.2
Ypsilon 0.9.6-trunk/r506
Mosh 0.2.7
Rhizome/pi 0.57
Larceny 0.99
Guile 2.0.11
Racket 6.5
Foment 0.4

それぞれのドキュメントを確認していないので保証しているかどうかまでは知らないが、これらは実際にリストの先頭側から処理する実装になっている。

以下のように短かいリストで試してみただけなので複雑な状況で挙動が変わる場合も有るかもしれないが。

(map display '(1 2 3 4 5))

つまり、ある挙動を保証しているのは言語仕様か、処理系の仕様か、実装が結果的にそうなっているだけなのかという種類があって、その言語で書いたプログラムが動いているのも実は偶然でしかないという場合は意外にあると思う。個別の処理系の方針について詳細を常に把握するのは難しいが、書いたプログラムをたまには別の処理系で動かしてみたりするくらいはした方が良いと思う次第である。

余談だが、上記の確認において Husk 3.19.2 は map がリストの末端側から処理した。

更に Chez Scheme 9.4.1 は 2 個ごとに入れ替わるような順序になった。 53412 というような順序である。もちろんこれでも言語仕様には違反しないが、どうしてそういう選択をしたのかは興味深いのでいずれソースコードを確認してみようと思う。

Document ID: b939601ec40ec23a868fde033123cfd9

2016-06-07

あるべき姿に

自分が書いたプログラムを見て、汚いなぁと思うことがある。拡張するときに動いている部分にはなるべく手を付けないようにするのはありがちなことだが、そうすると拡張した部分に不格好な部分が出来てしまい、それが詰み重なると不整合だらけになるのだ。それほど長く使うつもりがなかったものがいつまでも残ってしまう。

重い腰を上げてそういう負債の積み重ねをなんとかしようと思っても、それを作ったのは自分自身である。最初に作ったときと同じ発想で設計しなおしてしまい、小手先の綺麗さが少し改善される程度にとどまってしまう。

そういったときにはインターフェイスになる部分から書いていくのが良いと思う。自分が欲しい姿で部品の外側を作ってしまえばそれが構造を決める。それでどうしても中身が汚くなってしまっても、不整合が積み重なるよりは良い。

プログラムを分割統治するにあたって抽象化の壁を作るのは重要なことだが、壁の向こうを知っているときにあえてそれを忘れるということも出来ないと綺麗な構造を保つのは難しい。というよりは、壁の向こうを忘れていられるような壁を作らなければならない。

Document ID: f66b5cacc6c6fe1f9a5aa83b82911aa3