星にゃーんのブログ

ほとんど無害。

Scheme 継続

もうひとつのScheme入門 16. 継続を写経した。

「継続」は、計算において必ず存在する。 しかし、明示的に扱われることが少ない。

例えば、

(* 3 (+ 1 2))

のような計算があるとき、(+ 1 2)を評価した後の残りの計算は、(* 3 _)である。 この部分を継続と呼ぶ。

継続渡しスタイル

継続は、第一級関数をもつ言語であれば、CPS(継続渡しスタイル)によってあつかうことができる。

これは、関数が値を返す部分に、計算結果をどんな関数に渡すのかを引数で指定する方法。

(define (id x)
  x)

(define (k+ a b k)
  (k (+ a b)))

(define (k* a b k)
  (k (* a b)))

この関数群を使って、先ほど示したコードを書くとこうなる。

(k+ 1 2 (lambda (x) (k* 3 x id)))

関数適用の順番が入れ替わっている。

再帰関数のCPS

(define (fact n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))

(define (kfact n k)
  (if (= n 1)
      (k 1)
      (kfact (- n 1) (lambda (x) (k (* n x))))))

一つ目が通常の階乗。二つ目がCPS階乗。 CPS版は末尾再帰になっている。 このように、再帰関数をCPS化することで、末尾再帰に変換できる。 Schemeは末尾再帰をループに最適化するので、とても嬉しい。

call/cc

call/ccを使うと、継続によるジャンプができる。

> (* 3 (call/cc (lambda (k) (+ 1 2))))
9 ;継続が呼ばれていないので、普通の式と同じ
> (* 3 (call/cc (lambda (k) (+ 1 (k 2)))))
6 ;継続kが呼ばれ、(* 3 2)を計算し、トップレベルに6が返る
(define cc)
(* 3 (call/cc (lambda (k)
                 (set! cc k)
                 (+ 1 2))))

> (+ 100 (cc 3))
9
> (+ 100 (cc 100))
300

継続を呼ぶと、その後の式を無視してトップレベルに戻る。

具体的な使用方法は後でまとめる。

SBCLで(progn (princ hoge) (read))の実行順序が入れ替わるときの対処法

問題のコードがこれ

(defun read-with-prompt ()
  (princ "> ")
  (read))

CLISPではきちんと動く。

[1]> (read-with-prompt)
> hoge
hoge

SBCLではこうなる。

* (read-with-prompt)
hoge
> 
hoge

princよりも先にreadが実行されてしまう。 この問題は、SBCLの最適化が原因らしい。 (finish-output)で出力の終了を明記するとうまく動く。

修正後のコード

(defun read-with-prompt ()
  (princ "> ")
  (finish-output)
  (read))

下記のコードを書いている時にこの問題を発見した。

じゃんけん

Land of Lisp 読んでみた。

Land of Lisp

Land of Lisp

これを買った。 表紙にいる緑色の怪物はLispエイリアンというらしい。 キモカワ。

ざっと見た感じ、すごいH本とかリーダブルコードみたいな雰囲気。

"はじめに"のイラストに爆笑した。 「お宅の床下にはストラウストラップの大きな巣があるようです 。」 Amazonのプレビューでも見れる。

軽快なノリと愉快な漫画でさくさく読み進めると、いつの間にかLispエイリアンが脳内に住み着く、そんな感じの本。 他のプログラミング言語の経験があって、Common Lispで遊んでみたいという人におすすめしたい。

また時間があいたら、Lispのマクロについてまとめたい。

Go言語でもプリプロセッサしたかった

cppというコマンドがある。 引数にCのソースを取り、標準出力にプリプロセッサを展開したCのソースを返す。

で、Go言語のソースでも、Cのプリプロセッサを書いてcppに通せばプリプロセッサできる。

Cのプリプロセッサ on Go言語

実行はこうする。

$ cpp hello_cpp.go > hello_cpp.out.go
$ go run hello_cpp.out.go
[1 4 9 16 25]
[1 2 Fizz 4 Buzz]

YEY!Go言語でプリプロセッサ書き放題だぜー

C言語でmapしたかった

※注意: この記事に実用性はありません。

C言語で遊んでたら、突然写像の方のmapを書きたくなったので、ggってみた。

するとありがたいことにこんな記事が。 ワンダープラネット株式会社(WonderPlanet Inc.)

でも、配列の長さをいちいち指定しないといけないのがめんどくさい。

というわけで、マクロにしてみた。

#include <stdio.h>

int square(int n) {
  return n * n;
}

int* raw_int_map(const int *source, int *result, size_t n, int (*func)(int)) {
  for (int i = 0; i < n; i++) {
    result[i] = func(source[i]);
  }
  return result;
}

// マクロでラップ
#define map(SOURCE, RESULT, FUNC)\
  int RESULT[sizeof(SOURCE) / sizeof(SOURCE[0])] = {0};\
  raw_int_map(SOURCE, RESULT, sizeof(SOURCE) / sizeof(SOURCE[0]), FUNC);

int main(void) {
  int numbers[] = {1, 2, 3, 4, 5};
  map(numbers, squares, (int (*)(int))square);
  for (int i = 0; i < 5; i++) {
    printf("%d ", squares[i]);
  }
  return 0;
}

マクロの可能性を感じた。 要素の型をマクロの引数にしたら多相型関数っぽいこともできそう。

結論: Cのマクロ怖い

C言語で多相のmap

おまけ カッとなってやった

C言語で多相もどきとmap · GitHub

多分この記事はn番煎じです。

2021-01-29追記:

アクセス解析を見るとちょくちょく閲覧されてるようなので、この記事の内容について補足する。

もちろん、このマクロは実用的ではない。 具体的には、以下のように配列を関数の引数に渡すケースでは、たとえ仮引数をint int_nums[5]のように書いていたとしてもバグる。

int print_int(int n) {
  return printf("%d", n);
}

void print_array(int int_nums[5]) {
  map(int, int_nums, result, print_int);
}

これは、関数の引数に配列が渡される際、ポインタ型に型変換されるためだ。その結果、sizeof(SOURCE) / sizeof(SOURCE[0])の結果が期待通り(配列の要素数)にならない。暗黙の型変換はかなり挙動がややこしいので、これ以上具体的な動作については言及しないが、例えばclang -Wallコンパイルすると以下のようなかなりゴツい警告が出る。

main.c:22:3: warning: sizeof on array function parameter will return size of 'int *' instead of 'int [5]' [-Wsizeof-array-argument]
  map(int, int_nums, result, print_int);
  ^
main.c:4:21: note: expanded from macro 'map'
  TYPE RESULT[sizeof(SOURCE) / sizeof(SOURCE[0])] = {0};\
                    ^
main.c:21:22: note: declared here
void print_array(int int_nums[5]) {
                     ^
main.c:22:3: warning: 'sizeof (int_nums)' will return the size of the pointer, not the array itself [-Wsizeof-pointer-div]
  map(int, int_nums, result, print_int);
  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.c:4:30: note: expanded from macro 'map'
  TYPE RESULT[sizeof(SOURCE) / sizeof(SOURCE[0])] = {0};\
              ~~~~~~~~~~~~~~ ^
main.c:21:22: note: pointer 'int_nums' declared here
void print_array(int int_nums[5]) {
                     ^
main.c:22:3: warning: sizeof on array function parameter will return size of 'int *' instead of 'int [5]' [-Wsizeof-array-argument]
  map(int, int_nums, result, print_int);
  ^
main.c:5:30: note: expanded from macro 'map'
  for (int i = 0; i < (sizeof(SOURCE) / sizeof(SOURCE[0])); i++) {\
                             ^
main.c:21:22: note: declared here
void print_array(int int_nums[5]) {
                     ^
main.c:22:3: warning: 'sizeof (int_nums)' will return the size of the pointer, not the array itself [-Wsizeof-pointer-div]
  map(int, int_nums, result, print_int);
  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.c:5:39: note: expanded from macro 'map'
  for (int i = 0; i < (sizeof(SOURCE) / sizeof(SOURCE[0])); i++) {\
                       ~~~~~~~~~~~~~~ ^
main.c:21:22: note: pointer 'int_nums' declared here
void print_array(int int_nums[5]) {
                     ^
4 warnings generated.

sizeof演算子を使って配列の要素数を求めるときには、その配列変数がどう宣言されているかに気を配る必要がある。また、個人的な意見としては、このような気が狂ったマクロを冗談以外で使うべきではない。冗談としてはかなりイカしてると思う。