Выражение Y в терминах SKI-комбинаторов в JavaScript
-
28-10-2019 - |
Вопрос
Я возился с коминаторами в JavaScript и гордился (надеюсь) тем, что S заработал, когда наткнулся на слова Википедии: «Комбинатор Y можно выразить в SKI-исчислении как: Y= S (K (SII)) (S (S (KS) K) (K (SII))) ", поэтому мне пришлось попробовать это:
родовое словоЧто я делаю не так?Я неправильно перевожу это выражение?Что-то не так с моим подходом?Это вообще имеет смысл?Большая часть того, что нужно прочитать о подобных вещах, просто заставляет мой мозг взорваться, поэтому целью этого упражнения для меня было в основном посмотреть, понял ли я обозначения (и смогу ли я таким образом перевести их на JavaScript).p>
Да, кстати, меня снова заставило читать и возиться с тем, что prototype.js реализует как Prototype.K, на самом деле комбинатор I.Кто-нибудь заметил?
Решение
Проблема в том, что вы используете строго проверенный язык программирования. Y-комбинатор, как и любой другой комбинатор с фиксированной точкой, будет работать правильно только тогда, когда ваши функции вызываются по необходимости или «лениво вычисляются».
Я знаю способ обойти эту проблему ( один из моих профессоров изучил это было некоторое время назад ), но это сделает ваш код совершенно нечитаемым.
Ниже я показал, что именно происходит, в надежде, что вы поймете, почему JavaScript не может справиться с простой реализацией SKI-исчисления.
Вот как выглядит код Y
после того, как JavaScript оценил ваше SKI-выражение:
Теперь давайте посмотрим, что произойдет, если вы загрузите его своей функцией function (fac) { ... }
. Назовем эту функцию f
:
Поскольку первая анонимная функция применяется к аргументу, она будет оценена следующим образом:
родовое слово В языке с отложенным вычислением аргумент f
теперь будет оставлен в покое, и будет оцениваться сам f
. Однако, поскольку JavaScript является языком со строгой оценкой (или «вызовом по значению»), он хочет знать, какой аргумент ему нужно передать функции f
, прежде чем запускать эту функцию. Итак, давайте оценим этот аргумент, ладно?
Думаю, теперь вы начинаете понимать, где что-то идет не так и как на самом деле работает Y-комбинатор. В любом случае на вашем компьютере JavaScript не хватит места в стеке, потому что он пытается создать бесконечный стек вызовов f
.