Как определить функции, к которым я могу применить оптимизацию хвостового вызова?

Я пытаюсь написать интерпретатор Scheme, но считаю, что TCO сложно реализовать. Я не уверен, какими свойствами должна обладать функция, чтобы сработала совокупная стоимость владения.

1) Функция с саморекурсивным вызовом в конце определения:

(define (sum-list list accum)
  (if (null list) accum
      (sum-list (cdr list) (+ accum 1))))

2) Функция с саморекурсивным вызовом не в конце определения:

(define (sum-list list accum)
  (cond ((not (null list))
         (sum-list (cdr list) (+ accum 1)))
        (else accum)))

3) Функция, которая сохраняет рекурсивный вызов в переменной перед его возвратом:

(define (sum-list list accum)
  (let ((sum
         (if (null list)
             accum
             (sum-list (cdr list (+ accum 1))))))
    sum))

4) Взаимно-рекурсивные функции:

(define (sum-list list accum)
  (if (null list)
      accum
      (other-function (cdr list) (+ accum 1))))

(define (other-function list accum)
  (sum-list list accum))

5) Просто вызов другой несвязанной функции в конце определения функции:

(define (foo)
  (bar))

6) Самый сложный случай, который я могу придумать, это замыкания. Что, если я удержу ссылку на переменную в области видимости?

(define (sum-list list accum ignored)
  (let ((local-var 12345))
    (if (null list)
        accum
        (sum-list
         (cdr list)
         (+ accum 1)
         (lambda () local-var)))))

7) Вызов другой функции в конце определения функции с саморекурсивным вызовом в качестве аргумента:

(define (sum-list list)
  (if (null list)
      0
      (+ 1 (sum-list (cdr list)))))

Насколько я понимаю, реализации TCO (как в Scheme, так и в Common Lisp) переписывают дружественные к TCO функции, поэтому они должны иметь возможность статически обнаруживать дружественные к TCO функции.

Что я хотел бы знать:

  • Какие из этих функций будут переписаны ТШО и почему только эти?
  • Существуют ли обстоятельства (например, 7), когда происходит перезапись совокупной стоимости владения, но функция по-прежнему потребляет память линейно?

lisp scheme tail-call-optimization
person Wilfred Hughes    schedule 15.09.2013    source источник
comment
Любой вызов, значение результата которого непосредственно возвращается функцией, является хвостовым вызовом.   -  person Rainer Joswig    schedule 16.09.2013
comment
Если вы реализуете настоящую схему, то наиболее подходящим является ответ Оскара Лопеса; Стандарт(ы) Схемы определяют, что является вызовом в хвостовой позиции. Вам не нужно пытаться перечислить эти случаи самостоятельно; стандарт(ы) уже сделали это за вас. Sylwester answer может быть полезным подходом к реализации, если вы можете гарантировать, что следование этому подходу охватывает случаи, которые стандарт( с) описать.   -  person Joshua Taylor    schedule 16.09.2013
comment
Ваш случай (3) явно упоминается в стандарте, который процитировал Оскар Лопес: «Примечание. Реализации могут распознавать, что некоторые вызовы без хвоста… могут быть оценены так, как если бы они были хвостовыми вызовами. В приведенном выше примере выражение let может быть скомпилировано как хвостовой вызов … ». (См. код в стандарте для кода, о котором они говорят. Однако это пример того же типа.)   -  person Joshua Taylor    schedule 16.09.2013

Ответы (2)


arrow_upward
7
arrow_downward

Взгляните на спецификацию Scheme, там определены все возможные хвостовые контексты. В частности, в R6RS (текущий ратифицированный стандарт) вы должны проверить раздел §11.20 Вызовы хвоста и контексты хвоста:

Концевой вызов — это вызов процедуры, который происходит в хвостовом контексте. Хвостовые контексты определяются индуктивно. Обратите внимание, что хвостовой контекст всегда определяется относительно конкретного лямбда-выражения.

  • Последнее выражение в теле лямбда-выражения, показанное ниже как ‹концевое выражение›, встречается в хвостовом контексте.

    (lambda <formals>
  <definition>* 
  <expression>* <tail expression>)

  • Если одно из следующих выражений находится в хвостовом контексте, то подвыражения, показанные как ‹концевое выражение›, находятся в хвостовом контексте. Они были получены из спецификаций синтаксиса форм, описанных в этой главе, путем замены некоторых вхождений ‹выражения› на ‹концевое выражение›. Здесь показаны только те правила, которые содержат хвостовые контексты.

    (if <expression> <tail expression> <tail expression>)
(if <expression> <tail expression>)

(cond <cond clause>+)
(cond <cond clause>* (else <tail sequence>))

(case <expression>
  <case clause>+)
(case <expression>
  <case clause>*
  (else <tail sequence>))

(and <expression>* <tail expression>)
(or <expression>* <tail expression>)

(let <bindings> <tail body>)
(let <variable> <bindings> <tail body>)
(let* <bindings> <tail body>)
(letrec* <bindings> <tail body>)
(letrec <bindings> <tail body>)
(let-values <mv-bindings> <tail body>)
(let*-values <mv-bindings> <tail body>)

(let-syntax <bindings> <tail body>)
(letrec-syntax <bindings> <tail body>)

(begin <tail sequence>)

    ‹условное предложение› — (<test> <tail sequence>), ‹случайное предложение› — ((<datum>*) <tail sequence>), ‹конечная часть› — <definition>* <tail sequence>, а ‹концевая последовательность› — <expression>* <tail expression>.

  • Если выражение cond находится в хвостовом контексте и имеет предложение в форме (<expression1> => <expression2>), то (подразумеваемый) вызов процедуры, которая является результатом оценки ‹выражения2›, находится в хвостовом контексте. ‹Выражение2› само по себе не находится в хвостовом контексте.

person Óscar López    schedule 15.09.2013
comment
Я собирался опубликовать что-то похожее на это. Как вы думаете, вы могли бы процитировать соответствующий раздел здесь на случай, если эта ссылка когда-нибудь исчезнет? - person Joshua Taylor; 16.09.2013
comment
@JoshuaTaylor просто найдите хвостовой вызов в оглавлении, в R6RS это раздел 11.20, номер может измениться, но в спецификации схемы всегда будет хотя бы один раздел, посвященный хвостовому вызову - это такая важная часть языка! - person Óscar López; 16.09.2013
comment
О да, раздел легко найти; мое мнение таково, что ответ лучше стоит сам по себе, если соответствующий текст (или, в данном случае, поскольку второй из двух случаев представляет собой большой список, по крайней мере, его часть) цитируется. Я не очень беспокоюсь о том, что R6RS станет полностью недоступным. - person Joshua Taylor; 16.09.2013
comment
@JoshuaTaylor хорошо, понял - person Óscar López; 16.09.2013

arrow_upward
7
arrow_downward

Вы не упомянули, какая среда выполнения или язык будет интерпретировать Scheme, поэтому может случиться так, что этот ответ будет немного неверным.

Надежный способ реализовать оптимизацию хвостового вызова и одновременно получить вызов/копию — выполнить CPS-преобразование. С CPS каждый вызов является хвостовым вызовом, а код без хвостовой рекурсии получает вложенные продолжения.

Совокупная стоимость владения, которую вы получите, когда вы вытащите стек перед применением хвостового вызова. Поскольку каждый вызов является хвостовым вызовом в CPS, вы знаете, что делать.

Каждая из ваших процедур выиграет от этого, кроме 3 и 7. У них есть продолжение, когда рекурсивный вызов возвращается.

ИЗМЕНИТЬ Python:

Python не имеет совокупной стоимости владения, поэтому вы не можете использовать основной язык для прямого вызова. Однако вы можете сделать это с батутами.

person Sylwester    schedule 15.09.2013
comment
Я реализую свой интерпретатор на Python, который дает мне встроенную поддержку закрытия, но не имеет TCO на основном языке. - person Wilfred Hughes; 16.09.2013
comment
@WilfredHughes С батутами вы можете выполнять совокупную стоимость владения на хосте Python. см. мое дополнение к моему ответу. - person Sylwester; 16.09.2013