Вы пытались оценить их вообще? Это первый или второй случай, который неясен?
Каролис Юоделе
@ KarolisJuodelė: 1-й
URL87
1
Не следует ли писать лямбда-выражения в скобках, чтобы отметить конец первого лямбда-выражения и начало аргумента, например:Let M = (λx.y) ((λx.(x x)) λx.(x x))
mattgately
Ответы:
7
- бесконечный цикл, потому что λ x . ( x x ) λ x . ( x x ) → λ x . ( x x ) λ x . ( x x )
Обратите внимание, что λ x . ( х( λ x . y( λ x . ( x x ) λ x . ( x x ) ) )
λ x . ( x x ) λ x . ( x x ) → λ x . ( x x ) λ x . ( х х )
( КYΩ )КYλ x . YYΩ = ( λ x . ( Xх )λ x . ( хх ) )ΩΩ → Ω, (Удостоверьтесь, чтобы это было на бумаге хотя бы раз в жизни.)
Аппликативное уменьшение порядка должно привести аргумент функции к нормальной форме, прежде чем он сможет оценить переопределение верхнего уровня. Поскольку аргументΩне имеет нормальной формы, аппликативное уменьшение порядка зацикливается бесконечно. В целом, на любой срокM, MΩ → MΩи это сокращение, выбранное стратегией аппликативного заказа.
Снижение нормального порядка начинается с уменьшения переопределения верхнего уровня (потому что функция КYуже в нормальной форме). посколькуКY игнорирует его аргумент, ( КYΩ ) → yв один шаг. В более общем смысле,КYN→ у на любой срок Nи это сокращение, выбранное обычной стратегией заказа.
Этот случай иллюстрирует более общее явление: аппликативное уменьшение порядка только когда-либо находит нормальную форму, если термин сильно нормализует, тогда как нормальное уменьшение порядка всегда находит нормальную форму, если он есть. Это происходит потому, что аппликативный порядок всегда сначала полностью оценивает аргументы, и поэтому упускает возможность для аргумента оказаться неиспользованным; тогда как нормальный порядок оценивает аргументы как можно позже и поэтому всегда побеждает, если аргумент оказывается неиспользованным.
(Обратной стороной является то, что на практике аппликативный порядок имеет тенденцию быть более быстрым, поскольку аргумент редко используется, а аргумент используется несколько раз, а при аппликативном порядке аргумент оценивается только один раз. Порядок оценивает аргумент так часто, как он используется, будь то 0, 1 или много раз.)
Let M = (λx.y) ((λx.(x x)) λx.(x x))
Ответы:
- бесконечный цикл, потому что λ x . ( x x ) λ x . ( x x ) → λ x . ( x x ) λ x . ( x x ) Обратите внимание, что λ x . ( х( λ x . y ( λ x . ( x x ) λ x . ( x x ) ) )
источник
Аппликативное уменьшение порядка должно привести аргумент функции к нормальной форме, прежде чем он сможет оценить переопределение верхнего уровня. Поскольку аргументΩ не имеет нормальной формы, аппликативное уменьшение порядка зацикливается бесконечно. В целом, на любой срокM , MΩ → MΩ и это сокращение, выбранное стратегией аппликативного заказа.
Снижение нормального порядка начинается с уменьшения переопределения верхнего уровня (потому что функцияКY уже в нормальной форме). посколькуКY игнорирует его аргумент, ( КYΩ ) → y в один шаг. В более общем смысле,КYN→ у на любой срок N и это сокращение, выбранное обычной стратегией заказа.
Этот случай иллюстрирует более общее явление: аппликативное уменьшение порядка только когда-либо находит нормальную форму, если термин сильно нормализует, тогда как нормальное уменьшение порядка всегда находит нормальную форму, если он есть. Это происходит потому, что аппликативный порядок всегда сначала полностью оценивает аргументы, и поэтому упускает возможность для аргумента оказаться неиспользованным; тогда как нормальный порядок оценивает аргументы как можно позже и поэтому всегда побеждает, если аргумент оказывается неиспользованным.
(Обратной стороной является то, что на практике аппликативный порядок имеет тенденцию быть более быстрым, поскольку аргумент редко используется, а аргумент используется несколько раз, а при аппликативном порядке аргумент оценивается только один раз. Порядок оценивает аргумент так часто, как он используется, будь то 0, 1 или много раз.)
источник