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

Question

Когда я прочитал теорему Церкви Rosser II here

теоремы (Church Россер II)

Если есть один снижение терминатора, то внешнее снижение прекращается, тоже.

Мне интересно: существует ли какая-то теорема, которая укрепляет теорему Церк. Россер II, чтобы она рассказывала об асимптотической временной сложности вместо термина?

Или, может быть доказано, что стратегия по требованию имеет минимальную асимптотическую временную сложность среди всех стратегий сокращения?

Answer 1

Я думаю, что ваш вопрос немного смущен. Пожалуйста, позвольте мне уточнить несколько моментов.

Прежде всего, упомянутая теорема традиционно известна как теорема стандартизации и принадлежит Карри и Фейсу (Комбинационная логика I, 1958), обобщенная на eta-редукция Хиндли (Standard and normal reductions), а затем пересмотренная многими другими авторами (см., например, это question).

Во-вторых, внешнее сокращение отличается от вызова по необходимости (вызов по необходимости не является даже стратегией сокращения в традиционном смысле слова).

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

       n 2 I I 

где n и 2 являются целыми целыми числами, а I является личностью. Я добавляю два я в конце, иначе слабые языки сократят вычисления слишком рано.

Заметим, что термин сводится к

      2 (2 (... (2 I))..) I 

и (2 I) сводится к I. Так, с сокровенной сокращения вы могли бы сократить срок в линейном времени w.r.t п.

С другой стороны, я предлагаю вам выполнить предыдущие вычисления в Haskell, и вы обнаружите, что время сокращения растет экспоненциально по n.Я оставляю вам понять причины этого явления.

Аналогичное обсуждение было сделано в этом thread.

Answer 2

Наверняка нет. Рассмотрим

f x y = sum [1..x] + y 
g x = sum (map (f x) [1..x]) 

вызов по необходимости сокращения g x будет выполнять O (х^2) дополнения, но на самом деле только O (х) необходимы. Например, ленивый 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's 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 перед его применением, таким образом разделяя любые вычисления, которые не зависят от аргумента.

Подробнее об этом см. В статье Майкла Джонатана Тиера Lazy Specialization.