schemeの末尾再帰での終了条件が上手く書けません。

Question

前提・実現したいこと

Racketでリストと整数を与えるとリストのリストとして返す関数を書こうとしています。
動作イメージは以下の通りです。

(list->Tmatrix '(1 2 3 4 5) 3)
((1 2 3) (2 3 4) (3 4 5) (4 5 0) (5 0 0))

発生している問題・エラーメッセージ

リストの長さと同じ数のリストを得るところまで書いてみたところ、末尾再帰が止まらずにエラーが出てしまいました。デバッグツールで動作を確認したところ、list->Tmatrix-subでnが0になってもcons以下を評価しに行って、takeでのエラーメッセージが出ています。
末尾再帰の書き方が間違っているのだと思いますが、どこがおかしいのでしょうか？

take: arity mismatch;
 the expected number of arguments does not match the given number
  expected: 2
  given: 1
  arguments...:

該当のソースコード

#lang racket
(require srfi/1)

(define (list->Tmatrix lst width)
  (list->Tmatrix-sub (add-0xWidth lst width) width (length lst)))

(define (add-0xWidth lst1 width1)
  (append lst1 (make-list (- width1 1) 0)))

(define (list->Tmatrix-sub lst2 width2 n)
    (if (= n 0)
        '()
        (cons (take (list->Tmatrix-sub (cdr lst2) width2 (- n 1))) (take lst2 width2))))

(define x (iota 5))
(list->Tmatrix x 3)

試したこと

手直ししてgaucheでも動かしてみましたが同様の問題が発生しています。
...
*** ERROR: wrong number of arguments for #<closure (take list k)> (required 2, got 1)
While loading "././mytest01.scm" at line 10
Stack Trace:

---

0 (take (list->Tmatrix-sub (cdr x) y (- z 1)))
at "././mytest01.scm":8
1 (take (list->Tmatrix-sub (cdr x) y (- z 1)))
at "././mytest01.scm":8
2 (list->Tmatrix-sub (cdr x) y (- z 1))
at "././mytest01.scm":8
3 (take (list->Tmatrix-sub (cdr x) y (- z 1)))
at "././mytest01.scm":8
4 (list->Tmatrix-sub (cdr x) y (- z 1))
at "././mytest01.scm":8
5 (take (list->Tmatrix-sub (cdr x) y (- z 1)))
at "././mytest01.scm":8
6 (list->Tmatrix-sub (cdr x) y (- z 1))
at "././mytest01.scm":8
7 (take (list->Tmatrix-sub (cdr x) y (- z 1)))
at "././mytest01.scm":8
...

補足情報（FW/ツールのバージョンなど）

使用しているのは
racket c7.5.
DrRacket, version 7.5, Japanese
gauche 0.9.9
です。

Answer 1

エラーの直接的な原因は引数の数が違うからです。 (take (list->Tmatrix-sub (cdr lst2) width2 (- n 1))) をよく見ると take に引数を一個しか渡していません。

list->Tmatrix-sub を次々に再帰で呼び出していって戻ってくるときになって初めて take が呼び出されるので終了条件を満たした後にエラーになるのです。 終了条件の記述は間違っていません。

エラーの原因とは別に、末尾再帰になっていません。 自分を呼び出すのは末尾文脈である必要があります。 末尾文脈 (tail context) の定義は仕様書にありますのでよく読み返してください。

Comments

[onbangdo]

ご回答ありがとうございます！
引数の件は完全に見落としていました。エラーメッセージをよく読んでおらずお手数をお掛けしました。また末尾再帰に関するご指摘もありがとうございました。

早速、件の箇所を修正して実行してみたところ、本来自分の質問で想定していた（以前も出ていました）エラーが出ました。

修正内容
...
(define (list->Tmatrix-sub lst2 width2 n)
(if (= n 0)
'()
(cons (take (list->Tmatrix-sub (cdr lst2) width2 (- n 1))　width2) (take lst2 width2))))
...

エラーメッセージ
...
take: contract violation
expected: a list with at least 3 elements
given: '()
...

(take lst2 width2)のlst2が(0 0)になってから評価されているのかと思って、
(take lst2 width2)を空きリストにしても同じエラーが出ているので、
やはりがnが０になっても下記の
...
(cons (take (list->Tmatrix-sub (cdr lst2) width2 (- n 1))　width2)
...
評価されていると思うのですがどこが間違っているんでしょうか。

[onbangdo]

追記です。
エラーメッセージにgiven: '()とあるということはtakeが(0 ０)ではなくif文前半の'()を評価してしまっているのでしょうか？

[SaitoAtsushi]

はい、 if の条件が真のときの '() は評価されます。 終了条件がそれなので当然に評価されます。

(list->Tmatrix-sub (cdr lst2) width2 (- n 1)) を呼び出した結果が '() になるとき、 width2 の値は 3 なのですから (take '() 3) という呼び出しをしている状態に相当し、リストの長さが 3 もないのに 3 個を取れと言っているからエラーメッセージが「最低でも三要素のリストを期待する (expected: a list with at least 3 elements)」なのです。

[onbangdo]

>(list->Tmatrix-sub (cdr lst2) width2 (- n 1)) を呼び出した結果が '() になるとき、
>width2 の値は 3 なのですから (take '() 3) という呼び出しをしている状態に相当し、

ここが分かっていなくて、ただ空リストが買えるものと勘違いしていました。

[SaitoAtsushi]

手続きが自分自身をどんどん呼び出していったら、その逆順に呼び出し元に戻っていくという構造がよくわかっていなかったということですね？ 再帰であってもそうでなくても手続きは呼び出し元に戻ります。 (第一級継続を使うと戻ってこない手続きというのも作れるのですが、それは今回の場合には関係ないのでとりあえず脇に置きます。)

だだし、手続きを呼び出して返された値をそのまま更に上の呼び出し元に返す場合には、段階的に戻らずに一気に戻っても同じこと (なのでそのように Scheme 処理系は最適化しなければならない) というのが末尾呼び出しの最適化です。 そしてそれに当てはまるような形の再帰が末尾再帰です。

今回の list->Tmatrix-sub 場合は定義の中で list->Tmatrix-sub を呼び出した結果を take や cons で加工する処理が入っているので「そのまま更に上の呼び出し元に返す」という条件に当てはまりません。 なので末尾再帰ではありません。

一般のプログラミング言語において、関数呼び出しはジャンプとスタック操作として実現されているのが普通です。 つまり再帰というのは (ループになっている) ジャンプとスタック操作で説明がつけられます。 Scheme の場合は逆に、再帰からスタック操作を省略 (それが一気に戻るということ) できる場合はループと同じじゃないかと言っています。 どちらを軸にして説明するかが違うだけで、 Scheme が普通と違うことをしているわけではありません。

ところで、私なりに list->Tmatrix を書いてみました。 R5RS の語彙に加えて SRFI-1 の make-list と take だけは使うという制約内で書いたので素朴な書き方になっているはずです。 補助的な手続きを作るのが面倒なので名前付き let を使っています。 (名前付き let が分かり難いという初心者は結構いるみたいなんですが、本質的に一体の処理を分割して書くのは見通しが悪いので慣れたらこっちの方がたぶんやりやすいです。)

(define (list->Tmatrix lst width)
(let loop ((len (length lst))
(lst (append lst (make-list (- width 1) 0))))
(if (zero? len)
'()
(cons (take lst width)
(loop (- len 1) (cdr lst))))))

末尾再帰に変形するとこうなります。

(define (list->Tmatrix lst width)
(let loop ((len (length lst))
(lst (append lst (make-list (- width 1) 0)))
(result '()))
(if (zero? len)
(reverse result)
(loop (- len 1) (cdr lst) (cons (take lst width) result)))))

実質的にループしているだけの場合は do を使う方が私の好みです。 (が、 do は名前付き let よりもっと苦手な人が多いみたいです。)

(define (list->Tmatrix lst width)
(do ((len (length lst) (- len 1))
(lst (append lst (make-list (- width 1) 0)) (cdr lst))
(result '() (cons (take lst width) result)))
((zero? len) (reverse result))))

[onbangdo]

解答例まで頂いてしまい大変ありがとうございました！！
丁寧な解説で自分レベルでも分かり易かったです。
また今回の件でconsやlistの理解も中途半端だった事が判りました。
超初心者の疑問にお付き合い頂きまして感謝です！！