日本語文法では音便や省略が重要

http://d.hatena.ne.jp/kanimaster/20091022/1256217225に書いたブックマークへの追記。

「おいしいです」はやや崩した表現。「おいしゅうございます」の方がより丁寧。選択肢としては「おいしいのです/おいしいんです」も。

「おいしいのです」は書き言葉、「おいしいです」や「おいしいんです」は話し言葉。

「おいしいです」という表現は「おいしいのです」が元々の形だと私は思っている。「おいしいのです」が撥音便化*1して「おいしいんです」、さらに撥音が省略*2されて「おいしいです」となったのではないだろうか。
さらに、発声が表記通りとは限らない、という点も考慮するべきだろう。私が思いつく限りでも

• オイシイノデス
• オイシインデス
• オイシインデス(「ン」が弱く短い)
• オイシイデス

という四つの発声がある。「オイシインデス(「ン」が弱く短い)」と「オイシイデス」とを聞き分けるのもなかなか難しい。

〆。

やや極端な思考実験としては、「おいしゅうございます」を近畿地方の方言とみなす、という立場も考えられる。「おいしゅうございます」がとても丁寧な表現だということは変わりないが、どのような場面であっても相応しいとは言いがたいだろう。

*1:「〜なのです」→「〜なんです」など。

*2:「ひんがし」→「ひがし」など。

free_LIST()

• http://www.tees.ne.jp/~sin-x/200910a.html#0901
• http://shinh.skr.jp/m/?date=20091011#p01
• http://www.tees.ne.jp/~sin-x/200910b.html#1201
• http://homepage1.nifty.com/herumi/diary/0910.html#12

の話。

作るべきもの。

仕様の話としては

リストの先頭を与えると、再帰的にリスト末尾から free() してくれるようなラッパー

は必要だと思う。それがスタックを食い潰す実装になっていたらまた問題があるわけだけれども、そこまで規定してある仕様は滅多にない。「NNN要素まで処理できること」と規定されていれば上出来か*1。
一応、ベタに再起をループへ変換するとこんな感じか。C言語で末尾呼び出しの最適化を規定するのはけっこう難しいな。

static LIST* free_LIST_first(LIST *list) {
  LIST* next;
  assert(list != NULL);
  next = list->next;
  free(list->name);
  free(list);
  return next;
}
void free_LIST(LIST *list) {
  while (list != NULL) {
    list = free_LIST_first(list);
  }
}

教育としては。

C言語は計算科学と関係のない要素が多すぎるし、最初に習うプログラミング言語としてはあまりお勧めできないのかなと思うようになった。計算*機*科学の中のハードウェア教育の一環で教えるのなら最良の選択だと思うのは変わりないけれども。

*1:本当は「〜という条件で」が付いていないとダメなのだけども。

Ｃ言語でCurrying 5

ちょっと休んだけどまだ続くよ。

これまでのまとめ。

呼び出し規約

cdecl

呼び出し側でスタック掃除

stdcall

呼び出され側でスタック掃除

部分適用とは

関数を呼び出す際の引き数を、呼び出し時と事前との二つに分けて与える。問題になるのは

• 呼び出し側から見た引き数の個数と呼び出され側から見た引き数の個数が違う⇒どうやってスタックを掃除するか。
• 事前に与えた引き数をどう管理するか。

というところ。

不定長引き数への対応。

残念ながらstdcallで不定長引き数に対応するのは難しい。なので、cdeclでの部分適用を目指してみよう。

ダミー引き数を与える。

今手元にコンパイラがないので疑似コードで書くと

int add(int a, int b);
int binded_add(int a, int b) {
  a = 123;
  jmp add;
}

という感じ。スタック調整用のダミー変数を咬ませることにより、極めて自然に部分適用を達成できた。ダミー変数の不自然さを我慢できるならお勧め。

呼び出し規約を作る。

cdeclで呼び出された場合、cdeclとしてretしさえすれば問題はないはずだ。つまり、

ダミー呼び出し開始時のスタック	…	$1	$2	$R
本体の呼び出し開始時のスタック	…	$1	$2	$3	$R
本体の呼び出し終了時のスタック	…	$1	$2	$3
ダミー呼び出し終了時のスタック	…	$1	$2

というように本体呼び出し終了からダミー呼び出し終了までの間でスタック位置を調整できれば良い。通常の呼び出し規約の範疇ではそのような機能はない。それなら作ろう。
とは言うものの、実際に部分適用する引き数の個数は限られている。一つしか部分適用しないと判っているのなら

ret $1

というようにret imm16で調整すれば良い。これくらいなら事前に生成することも十分に考慮できるだろう。

C言語でCurrying 4

Boehm GCと組み合わせた場合の注意点について述べる。

悪い例。

下のような記述ではGC_malloc()で取得したポインタを部分適用したものの、肝心のメモリ領域が回収されてしまう。何故かと言えば、GC_malloc()で取得したポインタがポインタサイズ境界に位置しておらず、Boehm GCがポインタだと認識できないからだ*1。

 58                      pop    %eax
 68 78 56 34 12          push   ptr
 50                      push   %eax
 b8 f0 de bc 9a          mov    func,%eax
 ff e0                   jmp    *%eax

良い(?)例。

クイックハック以外の何者でもない解決策だが、適宜ポインタの位置をサイズ境界に調整すれば想定どおり動くようになる。

 58                      pop    %eax
 90                      nop
 90                      nop
 68 78 56 34 12          push   ptr
 50                      push   %eax
 90                      nop
 90                      nop
 b8 f0 de bc 9a          mov    func,%eax
 ff e0                   jmp    *%eax

〆。

問題の適用範囲が狭すぎてXbyakも使えなさそう。パディングも嵩張るし、独自(簡易)アセンブラを使うくらいでちょうど良いかも。

*1:一応、独自のマーク付け関数を用意すれば可能。

C言語でCurrying 3

もっとも簡単な手段がもっとも優れた手段ということがしばしばある。

calleeがスタックを解放する場合

x86=IA32でのstdcall関数の場合、calleeがスタックを解放する。つまり

call cを呼んだ直後のスタック	……	100	ret(c)
jmp addを呼んだ直後のスタック	……	100	10	ret(c)

で良い。

#include <stdlib.h>
#include <stdio.h>

extern int __attribute__((stdcall)) add(int i, int j);
int __attribute__((stdcall)) add(int i, int j) {
  return i + j;
}

extern int __attribute__((stdcall)) add4(int j);
__asm__(".global add4\n\t"
	"add4:\n\t"
	"popl	%eax\n\t"
	"pushl	$4\n\t"
	"pushl	%eax\n\t"
	"jmp	add");

int main() {
	printf("%d\n", add4(3));
	return 0;
}

このadd4()はたったの9bytesに収まる。Xbyakを使えば実用に足るような気もしてきた。

C言語でCurrying

と思ったら既にあった。http://d.hatena.ne.jp/shinichiro_h/20060119

厳密には。

#include <stdio.h>

int test(int i, int j) {
  return i+j;
}

static int _i;

int test1(int j) {
  return _i+j;
}

int (*test2(int i))(int) {
  _i = i;
  return test1;
}

厳密には「int (*)(int,int)」な関数test()を「int (*(int))(int)」な関数test2()に変換するところまでがCurry化で、test1()を生成する部分自体は部分適用という別のものらしい。Curry化と部分適用とをまとめて扱うことが多いので、Curry化という言葉が部分適用まで含むように使われるということだろうか。

C言語でCurrying2

http://d.hatena.ne.jp/shinichiro_h/20060119の手法は引数を積みなおして関数ポインタを呼ぶというもの(だと思う)。

call cを呼んだ直後のスタック	……	100	ret(c)
call addを呼んだ直後のスタック	……	100	ret(c)	100	10	ret(add)

という感じで。これをtail callに出来たら面白いかも。

calleeがスタックを解放する場合

簡単すぎて省略。

callerがスタックを解放する場合

call cを呼んだ直後のスタック	……	100	ret(c)
call addを呼んだ直後のスタック	……	100	10	ret(add)
call cから帰った直後のスタック	……	x

となるように手を加えればよい。

細工付きトランポリン

call cを呼んだ直後のスタック	……	100	ret(c)
call addを呼んだ直後のスタック	……	100	10	ret(add)
call addから帰った直後のスタック	……	100	10
call cから帰る直前のスタック	……	100	ret(c)
call cから帰った直後のスタック	……	100

トランポリン関数部分で細工を頑張る。でも、スタック消費がわずかに減っただけで処理自体は元のものよりも重くなっている。

bp, spに細工

call cを呼んだ直後のスタック	……	100	ret(c)
call addを呼んだ直後のスタック	……	100	ret(c)	100	10	ret(c)
call addから帰った直後のスタック	……	100

call addを呼ぶ直前のebp, espをcall cを呼ぶ直前の値にし、一回のretで二つの関数呼び出しの分を返してしまうという。処理の流れはtail call、スタック消費は非tail callになっている。

〆。

C言語の呼び出し規約は良くも悪くも難しい。