описание проблемы
В промежуточной викторине CS1101S 2015 года задается вопрос, исчерпывают ли следующие функции время и/или ресурсы пространства.
const C = (x => x(x))(x => x(x)); const D = (x => (x(x))(x))(x => x(x)); const E = (x => x(x(x)))(x => x(x)); const F = (x => x(x))(x => x(x(x)));
Задний план
Я понятия не имел, как это работает, пока не прочитал кое-что о *лямбда-исчислении*, поэтому я кратко расскажу, как это работает:
Немного базового лямбда-исчисления
Рассмотрим одно из простейших лямбда-выражений: `λx. х+1`. Это означает, что в функции черного ящика она получает один параметр с именем `x` и выводит результат `x+1`. Знак `λ` вместе с `.` после имени переменной указывает на объявление лямбда-функции.
Итак, как мы передаем параметры лямбда-функции? Мы пишем его (или их) прямо рядом с лямбда-функцией (, что делает важным добавление круглых скобок в начале и конце лямбда-функции, потому что в противном случае вы не сможете определить, является ли это параметром или частью лямбда-функции. функция). Например, `(λx. x+1) 1` выведет `2`, потому что лямбда-функция заменит все `x` после `λx.` и оценит выражение.
Подключиться к Источнику
Теперь вы обнаружите, что `x =› x + 1` является исходным выражением эквивалентности для лямбда-функции `(λx. x+1)`. Кроме того, `(x, y) =› x + y` эквивалентно `(λx.λy. x+y)`; `a =› b =› a + b` эквивалентно `(λa. (λb. a + b))`. Обратите внимание, что `a` в `(λb. a + b)` — это то, что мы называем нерелевантной переменной, потому что она не объявлена в начале этой функции.
Мой опыт
Итак, почему я запутался с проблемой? Я слишком много думал о такой функции! Поскольку это функция черного ящика, она просто выполняет подстановку, то есть заменяет все `x` справа от `=›` значением, полученным из параметра. А параметр всегда находится рядом с функцией. Что еще более важно, компилятор читает слева направо. Когда он заканчивает чтение функции, он немедленно ищет ее параметры. По этой причине в следующей задаче D первая часть (`((x =› x(x))(x =› x(x)))`) никогда не удлиняется. Так как `(x =› x(x))` — это первая функция, которую компилятор читает, то вторая `(x =› x(x))` естественно считается ее параметром и подстановка происходит сразу.
Решение
// — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — const C = (x => x(x))(x => x(x)); //1. (x => x(x))(x => x(x)) //It is exactly the same as the original one //Yes and No // — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — const D = (x => (x(x))(x))(x => x(x)); //1. ((x => x(x))(x => x(x)))(x => x(x)) //2. ((x => x(x))(x => x(x)))(x => x(x)) //Then the function never gets longer //Yes and No // — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — const E = (x => x(x(x)))(x => x(x)); //1. (x => x(x))((x => x(x))(x => x(x))) //2. ((x => x(x))(x => x(x)))((x => x(x))(x => x(x))) //3. ((x => x(x))(x => x(x)))((x => x(x))(x => x(x))) //Then the function never gets longer //Yes and No // — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — const F = (x => x(x))(x => x(x(x))); //1. (x => x(x(x)))(x => x(x(x))) //2. (x => x(x(x)))((x => x(x(x)))(x => x(x(x)))) //Notice the first part of the function remains the same //This ensures that the tail of the function gets to increase //infinitely, unlike D and E where the function //expansion is limited to a fixed-length expansion //of the first part of the function //Yes and Yes // — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Дополнительные примечания
В задачах D и E есть функция, которую я назвал расширением фиксированной длины. В лямбда-выражении это можно записать как `(λx. x x)(λx. x x)`. (Это немного отличается от `(x =› x(x))(x =› x(x))` из-за круглых скобок, но вы также можете записать его как `((x) =› (x)(x)) ((x) =› (x)(x)))`, чтобы имитировать формат лямбда-выражения, верно?) Это бесконечный цикл, который ничего не делает, и он является строительным блоком для Y-комбинатора `λf. ((λx. f(xx))(λx. f(xx)))` и вы можете выполнить простую, но утомительную работу по подстановке, чтобы увидеть, что Y-combinatior приводит к `f(f(f (ф(…))))`. (Вам нужно только оценить часть `(λx. f(x x))(λx. f(x x))`, потому что мы еще не предоставили значение параметру `f`)
Еще кое-что
В предыдущем сообщении блога мы писали:
((function(f){return f(f);})(
(function(make_factorial){
return function(n){
return (n===0) ? 1 : n * make_factorial(make_factorial)(n-1);
};
})))(5);
После упрощения это выглядит как `(x =› x(x))(f =› (x =› x * f(f)(x-1)))`.
Вспомните Y-combinatior, он должен выглядеть так
— -
Примечание: вместо `x =› f(x(x))` мы пишем `x =› y =› f(x(x))(y))`, потому что мы хотим, чтобы * *используйте** функцию! `x` сам по себе является функцией, мы не пишем так, возвращаемая функция `Y(f)` никогда не ожидает число…
function Y(f){
return (x =>
y => f(x(x))(y))
(x =>
y => f(x(x))(y));
}
что сильно отличается от приведенного выше. В чем ключ? Позвольте мне сделать краткую разбивку:
`(x =› y =› f(x(x))(y))(x =› y =› f(x(x))(y))` в основном применяется `(x =› y =› f( x(x))(y))` в себя. Если мы заменим его более коротким именем `p`, тогда `(x =› y =› f(x(x))(y))(x =› y =› f(x(x))(y)) ` эквивалентно `p(p)`. Тогда все это можно рассматривать как результат `(g => g(g))(p)`. Кроме того, `f =› (p)(p)` можно рассматривать как
`(g =› g(g))(f =› p)`.
Примечание: я переместил `f =›` снаружи внутрь, потому что переменная `f` используется только в `p`. Это изменение не влияет на общность нашего решения.
Далее мы смотрим на `(x =› y =› f(x(x))(y))`. Обратите внимание, что «y» — это число, которое мы получаем, поэтому мы определим наш «базовый случай» и «индуктивный шаг» по отношению к «y».
Базовый случай: `f(x(x))(0) = 1`, что означает, что при `y=0` должно возвращаться `1`
Индуктивный шаг: `f(x(x))(y) = y * f(x(x))(y-1)`, что означает, что в противном случае он должен возвращать `y * f(y -1)`
Что такое "ф"? Нам все равно! В любом случае это черный ящик. Мы предполагаем, что у нас уже есть такая функция `f` в качестве нашего параметра (принятие желаемого за действительное). Затем мы можем начать определять, как должно выглядеть `(x =› y =› f(x(x))(y))`:
function x(f){
return y => y === 0
? 1
: y * f(y-1);
}
