(리스펙스)

이 페이지가 쓰는 낱말 셋부터 풀어 두겠습니다.

연속은 지금 계산이 끝난 뒤에 이어서 할 일입니다. (+ 1 (f x))에서 f를 부르는 순간, 돌아오면 1을 더해야 한다는 그 약속이 연속입니다. 약속이 쌓이면 그만큼 자리를 차지합니다.

꼬리 위치는 그 약속이 남지 않는 자리입니다. 어떤 호출의 결과가 곧바로 지금 식의 결과가 되면, 돌아와서 더 할 일이 없으므로 새 연속을 쌓지 않고 지금 것을 그대로 물려줍니다. 그래서 꼬리 위치의 재귀는 몇 번을 돌아도 자리를 더 쓰지 않습니다.

이름 있는 let은 let 뒤에 이름을 하나 붙인 모양입니다. 그 이름이 곧 이 루프를 다시 부르는 이름이 됩니다. 아래에서는 loop이 그 이름입니다.

실행으로 확인하기

LISPEX

(let loop ((xs (list 1 2 3 4)) (sum 0))
  (if (null? xs)
      sum
      (loop (cdr xs) (+ sum (car xs)))))

관측 결과

OUTPUT

null?은 리스트가 비었는지 묻습니다. 빈 리스트면 참입니다.

같은 루프를 do로도 쓸 수 있습니다. do는 변수마다 처음 값과 다음 값을 나란히 적고, 끝낼 조건과 그때 돌려줄 값을 그다음에 적습니다.

LISPEX

(do ((rest (list 1 2 3 4) (cdr rest))
     (sum 0 (+ sum (car rest))))
    ((null? rest) sum))

관측 결과

OUTPUT

do는 이름 있는 let과 같은 루프로 정리되므로 둘 중 읽기 좋은 쪽을 고르시면 됩니다. 끝낼 조건 뒤의 값을 생략하면 돌려줄 값이 없는 루프가 됩니다.

기저 사례를 찾습니다. xs가 비면 답은 이미 sum에 있습니다.
남은 일을 줄입니다. (cdr xs)는 항목을 정확히 하나씩 덜어냅니다. 그래서 길이가 유한한 올바른 리스트는 반드시 기저 사례에 닿습니다.
답을 앞으로 넘깁니다. 다음 누산기를 loop을 부르기 전에 계산합니다. 그러면 재귀 호출 자체가 마지막 동작으로 남습니다.

재귀 호출이 값을 돌려준 뒤에 계산을 덧붙이지 마세요. 대신 누산기를 매개변수로 넘깁니다.
마지막 자리에 오는 if, begin, and·or, cond, case, do, call-with-values, apply 경로에서도 꼬리 위치는 그대로 유지됩니다.
테스트할 때는 입력 크기를 제한하세요. 연속 깊이와 실행 비용은 따로 구분해서 봅니다.

입력 리스트에 5를 하나 더 넣으면 결과는 무엇일까요? 재귀 호출은 여전히 꼬리 위치일까요?

답

결과는 15입니다. 바뀐 것은 입력 데이터뿐이므로 loop는 여전히 선택한 분기의 마지막 동작입니다.

꼬리 안전성은 무한 루프를 끝내 주거나 자원 예산을 없애 주지 않습니다.

꼬리가 아닌 함수를 바꾸는 방법과 어떤 자리가 꼬리 위치로 남는지는 꼬리 호출 매뉴얼에 정리돼 있습니다. 재귀 대신 fold를 고를 때는 고차 프로시저 레퍼런스를 보세요.