Оптимизация хвостовой рекурсии в Оз

Question

В главе о функции в руководстве Oz говорится, что:

похоже на ленивые функциональные языки Оз допускает определенные формы оптимизация хвостовой рекурсии, которые не найден в определенном строгом функционале языки, включая Standard ML, Схема и параллельный функционал язык Erlang. Тем не менее, стандарт определения функций в Оз не ленивый.

Затем он показывает следующую функцию, которая является хвостовой рекурсивной в Oz :

fun {Map Xs F}
   case Xs
   of nil then nil
   [] X|Xr then {F X}|{Map Xr F}
   end 
end 

Что он делает, так это сопоставляет пустой список с пустым списком и непустым списком с результатом применения функции F к ее голове, а затем добавляет ее к результату вызова Map в хвост. В других языках это не будет хвостовой рекурсией, потому что последняя операция - это prepend, а не рекурсивный вызов Map.

Итак, мой вопрос: если «стандартные определения функций в Oz не ленивы», что делает Oz, чтобы такие языки, как Scheme или Erlang, не могли (или не будут?) Иметь возможность выполнять оптимизацию хвостовой рекурсии для эта функция? И когда именно функция хвостовой рекурсии в Oz?

Answer 1

Это называется Хвостовая рекурсия по модулю Cons. По существу, с добавлением к списку напрямую после рекурсивный вызов аналогичен добавлению к списку напрямую до рекурсивного вызова (и таким образом, составляя список как «побочный эффект» чисто функционального «цикла»). Это обобщение хвостовой рекурсии, которое работает не только со списками cons, но и с любым конструктором данных с постоянными операциями.

Впервые он был описан (но не назван) как метод компиляции LISP в 1974 году Дэниелом П. Фридманом и Дэвидом С. Вайзом в Технический отчет TR19: Разматывание структурированных рекурсий в итерации он был официально назван и представлен Дэвидом Х. Уорреном в 1980 году в контексте написания первого в мире компилятора Prolog.

Что интересно в Oz, так это то, что TRMC не является ни языковой особенностью, ни явной оптимизацией компилятора, это всего лишь побочный эффект семантики исполнения языка. В частности, тот факт, что Oz является декларативным языком параллельных ограничений, означает, что каждая переменная является переменной потока данных (или «все обещание», включая каждое место хранения). Поскольку все является обещанием, мы можем смоделировать возврат из функции как , сначала , установив возвращаемое значение в качестве обещания, а затем позже , выполнив его.

Питер ван Рой, соавтор книги Концепции, методы и модели компьютерного программирования Питера Ван Роя и Сейфа Хариди , также одного из дизайнеров Oz, и один из его разработчиков объясняет, как именно TRMC работает в потоке комментариев к Lambda the Ultimate: Хвост-рекурсивная карта и декларативные агенты :

Приведенный выше пример неверного кода на Scheme превращается в хороший хвосто-рекурсивный код Oz при переводе непосредственно в синтаксис Oz. Это дает:

fun {Map F Xs}
   if Xs==nil then nil
   else {F Xs.1}|{Map F Xs.2} end
end

Это потому, что у Oz есть переменные с одним присваиванием. Чтобы понять выполнение, мы переводим этот пример на язык ядра Oz (для ясности я приведу лишь частичный перевод):

proc {Map F Xs Ys}
   if Xs==nil then Ys=nil
   else local Y Yr in
      Ys=Y|Yr
      {F Xs.1 Y}
      {Map F Xs.2 Yr}
   end end
end

То есть Map хвостово-рекурсивный, потому что Yr изначально не связан. Это не просто умный трюк; он глубокий, потому что он допускает декларативный параллелизм и декларативные мультиагентные системы.

Answer 2

Я не слишком знаком с ленивыми функциональными языками, но если вы подумаете о функции Map в своем вопросе, ее легко перевести на хвостовую рекурсивную реализацию, если разрешены временно неполные значения в куче (преобразованы в более полные оценивает один вызов за раз).

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

Возвращаясь к вашему вопросу, другие современные языки не делают этого автоматически, вероятно, потому что было бы возможно наблюдать неполное значение во время его построения, и это должно быть то, что Оз нашел решение. Какие еще различия существуют в Oz по сравнению с другими языками, которые могли бы это объяснить?