Когда я прочитал теорему Церкви Россера II здесь
Теорема (Church Rosser II)
Если есть одна завершающая редукция, то и внешняя редукция тоже закончится.
Мне интересно: есть ли какая-то теорема, которая укрепляет теорему Церковного Россера II, чтобы она рассказывала об асимптотической временной сложности вместо завершения?
Или, можно ли доказать, что стратегия по требованию имеет минимальную асимптотическую временную сложность среди всех стратегий сокращения?
Я думаю, что ваш вопрос немного смущен. Прошу пояснить несколько моментов.
Прежде всего указанная вами теорема традиционно известна как теорема стандартизации и принадлежит Карри и Фейсу (Комбинирующая логика I, 1958), обобщенная на eta-редукция Хиндли (Стандартное и нормальное сокращение), а затем пересмотрено многими другими авторами (см., например, question).
Во-вторых, внешнее сокращение отличается от вызова потребностью (вызов по необходимости - это даже не стратегия сокращения в традиционном смысле слова).
Приходя к проблеме сложности, в этом и заключается суть вопроса, вызов по требованию является оптимальным только в отношении слабой редукции. Однако слабая редукция не всегда является наилучшим способом сокращения лямбда-терминов. Хорошо известным примером является следующий термин
n 2 I I
где n и 2 - целые числа в церкви, а я - тождество. Я добавляю два я в конце, иначе слабые языки сократят вычисления слишком рано.
Заметим, что член сводится к
2 (2 (... (2 I))..) I
и (2 I) сводится к I. Итак, с самой внутренней редукцией вы могли бы уменьшить член в линейном времени w.r.t n.
С другой стороны, я приглашаю вас выполнить предыдущие вычисления в Haskell, и вы обнаружите, что время сокращения растет экспоненциально по n. Я оставляю вам понять причины этого явления.
Аналогичное обсуждение было сделано в этой нити.
Конечно нет. Рассмотрим
f x y = sum [1..x] + y
g x = sum (map (f x) [1..x])
Сокращение по требованию g x будет выполнять дополнения O (x ^ 2), но на самом деле нужно только O (x). Например, ленивый HNF доставит нам эту сложность.
-- The definition f3 will get lazily refined.
let f3 y = f 3 y = sum [1,2,3] + y
g 3 = sum (map f3 [1,2,3])
= sum [f3 1, f3 2, f3 3]
-- Now let refine f3 to HNF *before* applying it
f3 y = sum [1,2,3] + y
= 6 + y
-- And continue g 3
g 3 = sum [f3 1, f3 2, f3 3]
-- no need to compute sum [1..x] three times
= sum [6 + 1, 6 + 2, 6 + 3]
= ...
Я немного поместил оценочный заказ, но, надеюсь, вы поняли эту идею. Мы сводим тело функции к HNF перед его применением, таким образом разделяя любые вычисления, которые не зависят от аргумента.
Подробнее об этом см. Michael Jonathan Thyer Lazy Specialization.