Выражение Y в терминах SKI-комбинаторов в JavaScript

Question

Я возился с коминаторами в JavaScript и гордился (надеюсь) тем, что S заработал, когда наткнулся на слова Википедии: «Комбинатор Y можно выразить в SKI-исчислении как: Y= S (K (SII)) (S (S (KS) K) (K (SII))) ", поэтому мне пришлось попробовать это:

родовое слово

Что я делаю не так?Я неправильно перевожу это выражение?Что-то не так с моим подходом?Это вообще имеет смысл?Большая часть того, что нужно прочитать о подобных вещах, просто заставляет мой мозг взорваться, поэтому целью этого упражнения для меня было в основном посмотреть, понял ли я обозначения (и смогу ли я таким образом перевести их на JavaScript).p>

Да, кстати, меня снова заставило читать и возиться с тем, что prototype.js реализует как Prototype.K, на самом деле комбинатор I.Кто-нибудь заметил?

Answer 1

Проблема в том, что вы используете строго проверенный язык программирования. Y-комбинатор, как и любой другой комбинатор с фиксированной точкой, будет работать правильно только тогда, когда ваши функции вызываются по необходимости или «лениво вычисляются».

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

Ниже я показал, что именно происходит, в надежде, что вы поймете, почему JavaScript не может справиться с простой реализацией SKI-исчисления.

---

Вот как выглядит код Y после того, как JavaScript оценил ваше SKI-выражение:

родовое слово

Теперь давайте посмотрим, что произойдет, если вы загрузите его своей функцией function (fac) { ... }. Назовем эту функцию f:

родовое слово

Поскольку первая анонимная функция применяется к аргументу, она будет оценена следующим образом:

родовое слово

В языке с отложенным вычислением аргумент f теперь будет оставлен в покое, и будет оцениваться сам f. Однако, поскольку JavaScript является языком со строгой оценкой (или «вызовом по значению»), он хочет знать, какой аргумент ему нужно передать функции f, прежде чем запускать эту функцию. Итак, давайте оценим этот аргумент, ладно?

родовое слово

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