Почему стратегия оценки Call-Value не завершена завершена?

Question

Я читаю статью о разных Стратегии оценки (Я связал статью в вики, но я читаю еще одну, не на английском языке). И он говорит, что в отличие от call-by-name а также call-by-need стратегии, call-by-value Стратегия нет Завершено.

Кто-нибудь может объяснить, пожалуйста, почему это так? Если это возможно, добавьте пример пожалуйста.

Answer 1

Я спорю претензию В статье вы читаете. (Мне не платят за это, поэтому я собираюсь предоставить внукованный аргумент, а не доказательство.)

Хорошо известно, что, по крайней мере, под снижением нормального заказа (AKA Call по имени), чистый лямбда-исчисление - это завершено. Но если мы посмотрим на семанную бумагу Джона Рейнольдса Местрыми определениями для языков программирования более высокого порядка, мы видим, что Рейнольдс продолжал разницу между вызовом по имени и вызовов по значению. Критическая часть аргумента заключается в том, что для того, чтобы сделать правильное различие, мы можем преобразовать программу в Продолжение прохождения. Отказ Преобразование CPS отличается для вызова по необходимости и вызова по значению, но полученные преобразованные термины могут быть оценены в любом стиле.

Итак, вот приходит аргумент: напишите программу лямбда-исчисления, которая имитирует Turging Machine, затем CPS преобразует его с помощью трансформации CBN, и вы можете оценить полученный код, используя стратегию снижения CBV. Хлопнуть! Turing-Complete.

На практике смотрю, вы можете написать программу CBV для эмуляции Turging Machine; Вероятно, достаточно выбрать подходящий комбинатор фиксированного точка, например, например, θ. (Чем более известные Y комбинатор работает только в рамках стратегии снижения вызова, то есть сокращение нормального заказа.)

Отказ от ответственности: Я не изучал исчисление лямбда в возрасте века, и я уверен, что в аргументе выше. Но я уверен в веществе. Это было бы не в первый раз, когда я заметил что-то вростно неправильно в онлайн-ресурсах о теории языка программирования.

Answer 2

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

Существование коммутатора фиксированного точечного вызова (то есть комбинатор Y ») для нетяпированного кабдула лямбда, кажется, опровергает основное требование (см.: Фиксированная точечная комбинатор). Существование такого комбинатора ломает сильную нормализацию, что говорит о том, что существует по меньшей мере один язык, который является завершенным, что использует стратегию оценки стоимости Call-Value.

Гораздо больше шансов повлиять на полноту Turging языка - это существование (или отсутствие) тип системы. Например, просто набранный лямбда-исчисление не может кодировать комбинатор с фиксированной точкой и сильно нормализуется (т.е. все хорошо напечатанные термины уменьшаются до значения), однако это верно независимо от используемой стратегии оценки. Скорее, это следствие системы типа.