Upgrade to Pro — share decks privately, control downloads, hide ads and more …

入門: 末尾呼び出し最適化 /tail-call-elimination-intro

入門: 末尾呼び出し最適化 /tail-call-elimination-intro

This slide is distributed under CC-BY 4.0 license.
https://creativecommons.org/licenses/by/4.0/deed.ja

Miyakawa Taku

May 18, 2019
Tweet

More Decks by Miyakawa Taku

Other Decks in Programming

Transcript

  1. #ccc_a4b どの言語がサポートする? ⚫ フルスペックの末尾呼び出し最適化 ◼ Scheme ◼ OCaml ◼ Kink!

    ◼ Haskell...? ⚫ 部分的な末尾呼び出し最適化 ◼ Scala (自己末尾呼び出しのみ) ◼ Clojure (loop+recur) 10/48
  2. まずは普通のCプログラム #ccc_a4b #include <stdio.h> void cat(FILE *in, FILE *out) {

    while (1) { int byte = getc(in); if (byte < 0) { return; } putc(bt, out); } } int main(void) { cat(stdin, stdout); return 0; } 13/48
  3. 再帰呼び出しを行うプログラム #ccc_a4b #include <stdio.h> void cat(FILE *in, FILE *out) {

    int byte = getc(in); if (byte >= 0) { putc(byte, out); cat(in, out); } } int main(void) { cat(stdin, stdout); return 0; } 15/48
  4. 入力サイズが大きいと…… #ccc_a4b $ ./recur <『大菩薩峠』.txt 大菩薩峠 甲源一刀流の巻 中里介山 ... ...

    編笠も取らず、用事をも言わず、小手招《こ てまね》きするので、巡礼の老爺は怖る怖る、 「はい、何ぞ御用でござりまするか」 小腰《こごし》をかがめて進み寄ると、 Segmentation fault (=スタックオーバーフロー) 16/48
  5. スタックフレームの中身の例 #ccc_a4b ... ... ... ローカル変数2 ... ローカル変数1 ... ...

    [fp-24] 引数2 [fp-16] 引数1 [fp-8] 戻り先アドレス fp レジスタ sp レジスタ ※実際のレイアウトは「呼び出し規約」に依存 23/48
  6. 呼び出し・戻り処理の疑似機械語 #ccc_a4b 呼び出し側 呼び出され側 ... [sp-8] ← 戻り先 [sp-16] ←

    byte [sp-24] ← out sp ← sp-24 fp ← sp jump to putc 戻り先: fp ← fp+120 ... ... sp ← fp jump to [sp-8] 24/48
  7. スタックの積まれ方: 時系列 #ccc_a4b main cat#1 cat#2 cat#3 main cat#1 cat#2

    main cat#1 main main cat#1 cat#2 main cat#1 main call call call ret ret ret スタックの消費量は呼び出し階層の深さに比例 → 深くなりすぎるとスタックオーバーフロー 25/48
  8. 入力サイズが大きくても…… #ccc_a4b $ kink cat.kn <『大菩薩峠』.txt ... ... 「ああ、金椎だ」 と言って、二人は遠のいて避けて通るようにし

    ましたけれども、避けなかったところで、相手 は気がつくはずもなかったのです。 「相変らず、イエス・キリストを信じている よ」 と田山白雲が言いますと、柳田平治が、 「ちぇッ、キリシタン!」 と、噛《か》んで吐き出すように言いました。 <終> 28/48
  9. #ccc_a4b なぜスタックがあふれない? ⚫ catの呼び出しは手続きの末尾での 呼び出し = 末尾呼び出し :cat <- {(:In

    :Out) In.read_byte.each{(:Byte) Out.write_byte(Byte) cat(In Out) } } ←末尾 ←非・末尾 30/48
  10. #ccc_a4b スタックフレームの積み方 再 一個ずつ戻るやりかた main cat#1 cat#2 cat#3 main cat#1

    cat#2 main cat#1 main main cat#1 cat#2 main cat#1 main call call call ret ret ret スタックの消費量は呼び出し階層の深さに比例 34/48
  11. #ccc_a4b スタックフレームの積み方 改 一気に戻るやりかた main cat#2 main cat#1 main main

    cat#3 main call call ret ret 呼び出し階層が深くなってもスタック消費は増えない =末尾呼び出し最適化 35/48
  12. #ccc_a4b †1 CPS変換 Martin Gasbichler, Michael Sperber “Final Shift for

    Call/cc: Direct Implementation of Shift and Reset”, 2002 48/48