aboutsummaryrefslogtreecommitdiff
path: root/notebooks/guile-recursion.ipynb
blob: ed1678c1149ba1c9752ba0f10276b50e41f4360d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "bd9a0f87",
   "metadata": {},
   "source": [
    "## はじめに\n",
    "\n",
    "関数型プログラミングを学んだ人の多くは、スタックオーバーフローを回避するために再帰関数を末尾再帰の形式に変換する方法について学んでいると思います。Guile では他のプログラミング言語とは事情が異なり再帰をしても[システムのメモリを使い尽すまではスタックオーバーフローが起きません](https://www.gnu.org/software/guile/docs/docs-3.0/guile-ref/Stack-Overflow.html)([Racket も同様](https://docs.racket-lang.org/guide/Lists__Iteration__and_Recursion.html))。なので、一部の例外を除いて Guile でプログラムを書くときは無理に末尾再帰に変形せずに分かりやすくて綺麗な再帰のままにしましょう。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a476ec0",
   "metadata": {},
   "source": [
    "## 自然な再帰と末尾再帰の比較\n",
    "\n",
    "### リストの長さを計算する再帰的な手続き length\n",
    "\n",
    "例としてリスト `x` の長さ(要素の数)を計算する `length` 手続きを Guile で実装することを考えてみましょう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "8a9e45fb",
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (length x)\n",
    "  (if (null? x)\n",
    "      0\n",
    "      (+ 1 (length (cdr x)))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "77c55549",
   "metadata": {},
   "source": [
    "`length` の実行例:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8e3ace64",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 2,
     "metadata": {
      "text/plain": "3"
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(length '(a b c))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6198154b",
   "metadata": {},
   "source": [
    "### 再帰手続きの読み方\n",
    "\n",
    "`length` 手続きは下記のように読み下すことができます。\n",
    "\n",
    "`x` の長さ(`length`)とは:\n",
    "* a. `x` が空リスト(`null?`)のときは `0`\n",
    "* b. さもなくば、先頭以外(`cdr`)の長さ(`length`)に 1 を足したもの\n",
    "\n",
    "a のような自身 `length` を含まない場合のことを基底部、b のような自身を含む場合のことを帰納部と呼びます。\n",
    "再帰手続きの正しさは基底部と帰納部をそれぞれ読んで「ふむ、確かにそうだな」と思えるのであれば正しいので理解するのはとても簡単です。\n",
    "このような自然に読める再帰的な定義のことをここでは「自然な再帰」と呼ぶことにします。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34b5d50b",
   "metadata": {},
   "source": [
    "### 再帰手続きとスタックオーバーフロー\n",
    "\n",
    "Guile 以外の多くのプログラミング言語ではこのような再帰手続きにはスタックオーバーフローのリスクがあります。どういうことかというと、手続き呼び出しをしたときに元に戻る場所を覚えておくためコールスタックを使用するのですが多くのプログラミング言語ではコールスタックに上限が設定されています。コールスタックの上限に到達した段階でそれ以上の計算が不能になり途中で計算が停止してしまうのです。そのため、今回の場合リスト `x` がコールスタックの上限よりも大きい場合には `(length x)` を求めることはできません。\n",
    "この問題を回避するためには末尾呼び出しの形式に変換する必要があります(ただし、末尾呼び出しの最適化が行なわれるプログラミング言語・処理系に限ります。そうでない場合は繰り返しを表現する構文を使って書き換える必要があります。構文上の違いのみでこれから議論する末尾再帰との比較には影響しないので末尾再帰の話を繰り返しに置き換えて読んでいただいても問題ありません)。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "558e0ddb",
   "metadata": {},
   "source": [
    "### 末尾再帰版の length-tail\n",
    "\n",
    "ではスタックオーバーフローの回避のために末尾再帰呼び出しの形式に変換したリストの長さを求める手続き `length-tail` を見てみましょう。`len` という引数を追加していて、これには `0` を渡すことを想定しています(Scheme では手続きの中に手続きの定義がかけるので、`len` 引数を隠蔽することも可能なのですが、分かりやすさのためにあえて `len` 引数を残しています)。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a5e4e1b0",
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (length-tail x len)\n",
    "  (if (null? x)\n",
    "      len\n",
    "      (length-tail (cdr x) (+ len 1))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5c0b8118",
   "metadata": {},
   "source": [
    "`length-tail` の実行例:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "64f000a7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 4,
     "metadata": {
      "text/plain": "3"
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(length-tail '(a b c) 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ed0f4ab0",
   "metadata": {},
   "source": [
    "### 末尾再帰の手続きは理解が難しい\n",
    "\n",
    "`length` では手続きの定義を読み下すだけで理解できましたが、`length-tail` は少し難しいです。なぜなら、`length` の場合は基底部と帰納部をそれぞれ確認して正しいと思うことができましたが、`length-tail` の基底部は `len` であり単独では理解不能です。帰納部も `(length-tail (cdr x) (+ len 1))` とあり正しいかどうかは `len` 変数の値によるということになります。\n",
    "\n",
    "`length-tail` を理解するには計算の流れ全体を見なければいけません。\n",
    "\n",
    "* a. `len` の初期状態は `0`\n",
    "* b. `x` を `(cdr x)` で置き換える度に `len` の値は `1` 増加する\n",
    "* c. `x` が空リスト(`null?`) になったら、 `len` が初期の `x` の長さを表わしているため `len` を返却する\n",
    "    * c1. 初期の `x` が空リストになるには、初期の `x` の長さと同じ回数 b の計算を繰り返したときである\n",
    "    * c2. len の初期状態が 0 のため b を繰り返した回数が len の値となる\n",
    "    * c3. c1, c2 より `x` が空リストのとき len は初期の x の長さを表わしている\n",
    "\n",
    "とても考えることが多く難しいことを分かっていただけたでしょうか。`length-tail` という例が極めて簡単であったために難しいことを納得しにくいということはあるかもしれません。それでも、`length` は基底部と帰納部をそれぞれ読むだけでプログラムの正しさについて納得できたのに対し、`length-tail` を理解するにはプログラム全体の流れを追わないとよく分からないというのは大きな違いです。\n",
    "\n",
    "このような苦労をして `length-tail` を書くよりも `length` を書いた方が良いと思うでしょう。Guile ではスタックオーバーフローは起きないので問題ありません。 `length` の方を書きましょう。ただし、一点だけ注意があります。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99f3d843",
   "metadata": {},
   "source": [
    "###  末尾再帰と効率について\n",
    "\n",
    "実は Guile を使う場合であっても `length` と `length-tail` 手続きの間には違いがあります。\n",
    "\n",
    "`length-tail` では末尾再帰の最適化により呼び出し時の続きの計算を記憶しておく必要がありません。つまり、コールスタックに新しく追加する必要がありません。それに対して `length` では呼び出した後に続く計算を覚えておく必要があるのでコールスタックを消費します。`length` では `length-tail` と違って残りの計算を記憶するために記憶領域を消費してしまうのです。Guile ではコールスタックを消費しきったらヒープ領域を使ってコールスタックを拡張するので、与えるリストが長い場合には `length-tail` よりも `length` の方がメモリを多く使用してしまう可能性があるのです。ただし、メモリを消費するといっても与えるリストと同じくらいしか使わないので大した問題ではないでしょう。よほどメモリの消費に気を使う必要のあるようなケースでしか問題にならないと考えて良いでしょう。\n",
    "\n",
    "また、非末尾再帰の方が末尾再帰のよりも常に効率が悪いということではありません。むしろ末尾再帰にしない方が効率が良い場合もあります。手続き `f` とリスト `x` を取り、それぞれの要素を `f` によって変換したリストを返す `map` 手続きについて考えてみましょう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "5a2fdd3f",
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (map f x)\n",
    "  (if (null? x)\n",
    "      '()\n",
    "      (cons (f (car x))\n",
    "            (map f (cdr x)))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46359f45",
   "metadata": {},
   "source": [
    "`map` の実行例:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "e29afee1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-1 -2 -3)"
      ]
     },
     "execution_count": 6,
     "metadata": {
      "text/plain": "(-1 -2 -3)"
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(map - '(1 2 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb24caf0",
   "metadata": {},
   "source": [
    "末尾再帰版の `map-tail` を実装してみましょう。`result` 引数には空リストを渡す想定です。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "95da1a6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (map-tail f x result)\n",
    "  (if (null? x)\n",
    "      (reverse result)\n",
    "      (map-tail f (cdr x) (cons (f (car x)) result))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "113926d6",
   "metadata": {},
   "source": [
    "map-tail の実行例:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a7b49b21",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-1 -2 -3)"
      ]
     },
     "execution_count": 8,
     "metadata": {
      "text/plain": "(-1 -2 -3)"
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(map-tail - '(1 2 3) '())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3fc8259f",
   "metadata": {},
   "source": [
    "`map` と `map-tail` のメモリ効率の違いについて検討してみましょう。`map` の手続きは `map` の呼び出しをするたびにコールスタックを消費し、不足した場合にはコールスタックを拡張するため `x` が長い場合にはメモリを消費する場合があります。それに対して `map-tail` はどうでしょうか。`map-tail` では `result` 引数を `(cons (f (car x)) result)` によって置き換えています。よって `map-tail` でも再帰するたびにメモリを消費していきます。上記から `map` と `map-tail` で `map` がコールスタックを消費するから `map` の方がメモリを多く使うとは必ずしもいえません。\n",
    "さらに、`map-tail` では基底部で `reverse` を呼び出しています。これは `map-tail` と同じくらいの計算量とメモリを消費するため、`map-tail` の計算の方が時間がかかりそうです。\n",
    "\n",
    "試しに実行にかかる時間を計測して比較してみましょう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "c928cc34",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1000 個のリストの場合\n",
       "map(100回):\n",
       "clock utime stime cutime cstime gctime\n",
       " 0.04  0.03  0.01   0.00   0.00   0.01\n",
       "map-tail(100回):\n",
       "clock utime stime cutime cstime gctime\n",
       " 0.05  0.05  0.00   0.00   0.00   0.01\n",
       "\n",
       "10000 個のリストの場合\n",
       "map(100回):\n",
       "clock utime stime cutime cstime gctime\n",
       " 0.40  0.38  0.01   0.00   0.00   0.10\n",
       "map-tail(100回):\n",
       "clock utime stime cutime cstime gctime\n",
       " 0.52  0.50  0.00   0.00   0.00   0.17\n",
       "\n",
       "100000 個のリストの場合\n",
       "map(100回):\n",
       "clock utime stime cutime cstime gctime\n",
       " 3.76  3.45  0.22   0.00   0.00   0.49\n",
       "map-tail(100回):\n",
       "clock utime stime cutime cstime gctime\n",
       " 4.48  4.36  0.01   0.00   0.00   0.95\n",
       "\n"
      ]
     },
     "execution_count": 9,
     "metadata": {
      "text/plain": "1000 個のリストの場合\nmap(100回):\nclock utime stime cutime cstime gctime\n 0.04  0.03  0.01   0.00   0.00   0.01\nmap-tail(100回):\nclock utime stime cutime cstime gctime\n 0.05  0.05  0.00   0.00   0.00   0.01\n\n10000 個のリストの場合\nmap(100回):\nclock utime stime cutime cstime gctime\n 0.40  0.38  0.01   0.00   0.00   0.10\nmap-tail(100回):\nclock utime stime cutime cstime gctime\n 0.52  0.50  0.00   0.00   0.00   0.17\n\n100000 個のリストの場合\nmap(100回):\nclock utime stime cutime cstime gctime\n 3.76  3.45  0.22   0.00   0.00   0.49\nmap-tail(100回):\nclock utime stime cutime cstime gctime\n 4.48  4.36  0.01   0.00   0.00   0.95\n\n"
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(use-modules (ice-9 time))\n",
    "\n",
    "(define-syntax-rule (dotimes (var n) form ...)\n",
    "  (let ((end n))\n",
    "    (do ((var 0 (+ var 1)))\n",
    "        ((<= end var))\n",
    "      form ...)))\n",
    "\n",
    "(for-each\n",
    " (lambda (n)\n",
    "   (define x (iota (expt 10 n)))\n",
    "   (for-each display (list (expt 10 n) \" 個のリストの場合\\n\"))\n",
    "   \n",
    "   (display \"map(100回):\\n\")\n",
    "   (time (dotimes (i 100) (map - x)))\n",
    "\n",
    "   (display \"map-tail(100回):\\n\")\n",
    "   (time (dotimes (i 100) (map-tail - x '())))   \n",
    "\n",
    "   (newline))\n",
    " (iota 3 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fa6ae93a",
   "metadata": {},
   "source": [
    "予想通り `map-tail` の方が少し遅いという結果になりました(`map-tail` の実装に引数を破壊する版の `reverse!` を使った場合についても調べたところ、その場合は `map` とほぼ同じ計算時間になることを確認しています。計算時間が変わらないのであれば `map` の方が良いでしょう。また、[Guile のマニュアルの Stack Overflow の節](https://www.gnu.org/software/guile/manual/html_node/Stack-Overflow.html#Stack-Overflow)で `reverse!` を使うと継続安全(continuation-safe)が損なわれ、 `map-tail` の計算が終了した後に `f` の計算が再度実行された場合に正常に動作しなくなるという問題が指摘されています)。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23cb50bf",
   "metadata": {},
   "source": [
    "## 自然な再帰だと計算量が爆発してしまうケース\n",
    "\n",
    "ここまでの例では Guile でなら自然な再帰で良いと言える例だったのですが、何でもそうという訳ではありません。たまに自然な再帰だと計算量が爆発的に大きくなってしまう場合がありそういった場合には別のアルゴリズムに変更する必要があります。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92025e95",
   "metadata": {},
   "source": [
    "### リストを反転する手続き\n",
    "\n",
    "リストを反転する手続きを自然な再帰で実装してみましょう。特に効率などを考慮しなければ下記のように実装しようと思うかもしれません。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "6a801cbb",
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (reverse x)\n",
    "  (if (null? x)\n",
    "      '()\n",
    "      (append (reverse (cdr x)) (list (car x)))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef58ca96",
   "metadata": {},
   "source": [
    "`reverse` の実行例:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "22ca7753",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(c b a)"
      ]
     },
     "execution_count": 11,
     "metadata": {
      "text/plain": "(c b a)"
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(reverse '(a b c))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e7cd66e",
   "metadata": {},
   "source": [
    "この手続きは自然でたしかに正しいことはコードを読めば理解できるでしょう。ただし、一つ落とし穴があります。Lisp のリストは先頭に要素を追加する場合は `O(1)` の計算量でできるのに対してリストの最後に要素を追加する場合は `O(n)` かかるのです。\n",
    "この影響でリストが長くなると激的に遅くなります。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "cb5d2be9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "clock utime stime cutime cstime gctime\n",
       " 7.30  7.10  0.01   0.00   0.00   1.46\n",
       "done"
      ]
     },
     "execution_count": 12,
     "metadata": {
      "text/plain": "clock utime stime cutime cstime gctime\n 7.30  7.10  0.01   0.00   0.00   1.46\ndone"
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(time (reverse (iota 20000)))\n",
    "'done"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e0338644",
   "metadata": {},
   "source": [
    "これに対してリストの先頭に追加する操作しか行なわない `reverse-tail` を試してみましょう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "af106f5a",
   "metadata": {},
   "outputs": [],
   "source": [
    "(define (reverse-tail x result)\n",
    "  (if (null? x)\n",
    "      result\n",
    "      (reverse-tail (cdr x)\n",
    "                    (cons (car x) result))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a09232e",
   "metadata": {},
   "source": [
    "`reverse-tail` の実行例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "0ff1881a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(c b a)"
      ]
     },
     "execution_count": 14,
     "metadata": {
      "text/plain": "(c b a)"
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(reverse-tail '(a b c) '())"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc413390",
   "metadata": {},
   "source": [
    "`reverse-tail` の実行時間の計測:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "929e14f1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "clock utime stime cutime cstime gctime\n",
       " 0.02  0.02  0.00   0.00   0.00   0.00\n",
       "done"
      ]
     },
     "execution_count": 15,
     "metadata": {
      "text/plain": "clock utime stime cutime cstime gctime\n 0.02  0.02  0.00   0.00   0.00   0.00\ndone"
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(time (reverse-tail (iota 50000) '()))\n",
    "'done"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9983766e",
   "metadata": {},
   "source": [
    "大きい値では `reverse` と比較すると `reverse-tail` の方が圧倒的に早いのです。\n",
    "\n",
    "このように自然な再帰では計算に時間がかかり過ぎてしまう場合もあります。これは末尾再帰かどうかという話ではなくて、アルゴリズムが異なるために生じている違いであり今回の再帰手続きを末尾再帰の手続きに直す必要性の有無とは少しずれた話ではあります。こういう重い計算をしていてそれが問題となる場合には別のアルゴリズムを検討する必要があります。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c955b77",
   "metadata": {},
   "source": [
    "## おわりに\n",
    "\n",
    "Guile ではシステムのメモリを使い尽すまではスタックオーバーフローは起きないので、一般には自然な再帰をわざわざ末尾再帰の形式に変換してプログラムを読みにくくする必要はありません。末尾再帰に書き換えなくて済むプログラミングライフは大変快適なので、Guile のような再帰でスタックオーバーフローの起こさないプログラミング言語や処理系を探して使ってみてください。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Guile",
   "language": "scheme",
   "name": "guile"
  },
  "language_info": {
   "codemirror_mode": "scheme",
   "file_extension": ".scm",
   "mimetype": "application/x-scheme",
   "name": "guile",
   "pygments_lexer": "scheme",
   "version": "2.0.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}