Еще одна остановка на долгом пути к пониманию JavaScript с точки зрения разработчиков C #.
На этот раз мы действительно посмотрим, что значит сказать, что функции — это не только объекты, но и первоклассные объекты в JavaScript.
В этой серии я постоянно объявлял функции, используя выражения функций вместо операторов функций. Например, я использовал:
var isFiniteNumber = function(value) {
return ((typeof value === "number") && isFinite(value));
};
вместо этого:
function isFiniteNumber(value) {
return ((typeof value === "number") && isFinite(value));
};
Между ними нет никакой реальной разницы (если хотите, второе объявление компилируется как первое), но причина этого в том, что я хотел подчеркнуть, что функция — это просто объект другого типа. Второе объявление, как объявление функции , выглядит как метод C #, и, читая его, вы можете попасть в ловушку и просто рассматривать его как метод, каким-то образом фиксированный, неизменный и привязанный к классу. Функции в JavaScript не такие.
Давайте исследуем «функции как объекты», используя рекурсивную функцию. Вот факториальная функция, написанная рекурсивно, а не, скажем, итеративно.
var factorial = function(value) {
if (value <= 1) {
return 1;
}
return value * factorial(value - 1);
};
console.log(factorial(5));
Выглядит достаточно просто (и обратите внимание, что для простоты я удалил немного проверки ошибок параметров): если значение равно 0 или 1, верните 1, в противном случае верните значение, умноженное на факториал значения минус 1.
Но обратите внимание на одну особенность: функция ссылается на себя. Ну, конечно, да, вот что значит рекурсия. Но помните, что функции являются объектами, поэтому я могу сделать это:
var factorial = function(value) {
if (value <= 1) {
return 1;
}
return value * factorial(value - 1);
};
var anotherFactorial = factorial;
console.log(anotherFactorial(5));
Подумайте о том, что сейчас делает этот код. Выполнение anotherFactorial будет называться факториалом; однако это не является рекурсивным само по себе. Это все еще будет работать, так что давайте действительно склеим работы:
var factorial = function(value) {
if (value <= 1) {
return 1;
}
return value * factorial(value - 1);
};
var anotherFactorial = factorial;
factorial = undefined;
console.log(anotherFactorial(5));
Сбой: факториал не является функцией. Обратите внимание, что anotherFactorial все еще является функцией: это оригинальный код для факториала. Просто факториал больше не существует.
Это, мягко говоря, раздражает: поскольку любой именованный объект функции может рассматриваться как временный, мы не можем ссылаться на имя функции в теле функции. Если хотите, код функции — это анонимный объект, который мы можем присвоить любой переменной, которая нам нравится. Как мы можем написать рекурсивную анонимную функцию? В конце концов, он должен ссылаться на себя, и поскольку он анонимный, это немного сложно. Посмотрим, как мы можем.
Лучшая идея — передать рекурсивную анонимную функцию в качестве параметра, так как тогда мы можем назвать ее. Идея, которую мы собираемся исследовать, заключается в создании функции, которая может выполнять функцию факториала.
var makeFactorial = function(recurse) {
return function(value) {
if (value <= 1) {
return 1;
}
return value * recurse(value - 1);
};
};
ОК, возьми это медленно. Мы определяем функцию под названием makeFactorial. Он принимает рекурсивную функцию с именем recurse в качестве параметра и возвращает другую функцию. Эта другая функция принимает единственный параметр с именем value, который возвращает факториал значения при условии правильной работы recurse. Вы бы назвали это так
var factorial = makeFactorial(someFunction);
var result = factorial(5);
Или в одну строку:
var result = makeFactorial(someFunction)(5);
Другими словами, выполните makeFactorial для someFunction, чтобы вернуть другую функцию, которая немедленно выполняется с параметром 5. Но что такое someFunction? Ну, это, в некотором смысле, функция факториала, и единственный способ узнать, как это сделать с помощью этого кода, — это использовать makeFactorial.
Каким-то образом.
Проблема в том, что makeFactorial — это функция, принимающая другую функцию, а не функция, принимающая одно числовое значение. Таким образом, единственный способ написать это так:
var makeFactorial = function(recurse) {
return function(value) {
if (value <= 1) {
return 1;
}
var factorial = recurse(recurse);
return value * factorial(value - 1);
};
};
var factorial = makeFactorial(makeFactorial);
var result = factorial(5); // result === 120
Вау, это становится тавтологическим и определенно рекурсивным. Что делает makeFactorial сейчас? Он по-прежнему принимает функцию и возвращает другую, это ясно. Возвращенная функция, при выполнении, будет вызывать оригинал, переданный в функцию, передавая сам по себе. Это возвращает функцию, которую мы затем выполняем, и, бинго, производит факторный результат через рекурсивный вызов.
Здесь полезно остановиться в нашем обсуждении и выяснить, что происходит при выполнении этого кода. Прежде всего, внешняя факториальная переменная устанавливается на результат вызова makeFactorial для себя. Так что, если хотите, внешний факториал будет установлен на:
var outerFactorial = function(value) {
if (value <= 1) {
return 1;
}
var factorial = makeFactorial(makeFactorial);
return value * factorial(value - 1);
};
Затем мы называем это передачей в 5. Первое, что происходит, это то, что мы проверяем значение, которое меньше или равно 1 (это не так), а затем мы устанавливаем внутреннюю факториальную переменную равной:
var factorial2 = function(value) {
if (value <= 1) {
return 1;
}
var factorial = makeFactorial(makeFactorial);
return value * factorial(value - 1);
};
Это вторая факторная функция, которую мы создали, поэтому для ясности я пометил ее как 2. Еще во внешней факториальной функции мы теперь называем эту внутреннюю факториальную функцию factorial2, передавая значение 4. Первое, что делает factorial2, это проверить, передано ли значение 1 или меньше, а затем вызвать makeFactorial для себя (в третий раз):
var factorial3 = function(value) {
if (value <= 1) {
return 1;
}
var factorial = makeFactorial(makeFactorial);
return value * factorial(value - 1);
};
а затем он вызывает эту третью факториальную функцию.
Эта рекурсия продолжается, пока мы не доберемся до пятого уровня. На этот раз факториальная функция не создается, так как мы можем вернуть 1. Затем мы разматываем стек, передавая возвращаемые значения и выполняя все умножения, пока не достигнем внешней функции, чтобы получить результат 120. (Обратите внимание на все это Насколько мы обязаны закрытиям функций.)
Кажется, довольно хорошо, за исключением одного факта: мы делаем ссылку на makeFactorial в качестве параметра при первом вызове. Так что мы все еще ссылаемся на себя. Хорошо, давайте удалим это.
var factorial = function(maker) {
return function(value) {
if (value <= 1) {
return 1;
}
var factorial = maker(maker);
return value * factorial(value - 1);
};
}(function(maker) {
return function(value) {
if (value <= 1) {
return 1;
}
var factorial = maker(maker);
return value * factorial(value - 1);
};
});
var result = factorial(5); // result === 120
Хорошо, прежде чем вы начнете волноваться, все, что я сделал, это заменил makeFactorial (makeFactorial) реальным кодом для makeFactorial, и если вы присмотритесь, вы увидите круглые скобки вызова, окружающие второе объявление функции. Хотя это румяный беспорядок, он все еще работает. (Я также воспользовался возможностью переименовать создатель рекурсивных функций, так как эта функция создает другую.)
Но, заметьте, больше нет ни одного makeFactorial. Мы создали анонимную функцию, которая является рекурсивной; хотя за счет некоторого довольно ужасного дублированного кода. Давайте очистим это.
Сначала нужно очистить бит, который выполняет факториальный расчет (будет проще понять, что происходит, если тело возвращенной факториальной функции состоит из одной строки):
var factorial = function(maker) {
return function(value) {
return (value <= 1) ? 1 : value * maker(maker)(value - 1);
};
}(function(maker) {
return function(value) {
return (value <= 1) ? 1 : value * maker(maker)(value - 1);
};
});
var result = factorial(5); // result === 120
Теперь мы должны как-то извлечь этот дублирующий код, не называя его снова.
Сначала лемма, как мы говорим в математике. Используя анонимную функцию, мы можем написать
f(value);
(то есть вызывая f со значением параметра) следующим образом:
(function(x) {
return f(x);
})(value);
Мы объявляем анонимную функцию, которая принимает один параметр. Функция возвращает значение f, примененное к этому параметру. В общем, это эквивалентно, хотя я не рекомендую делать это в обычном программировании на JavaScript.
Вернуться к проблеме. Мы хотели бы извлечь эту функцию как-нибудь:
var F = function(value) {
return (value <= 1) ? 1 : value * maker(maker)(value - 1);
};
Но мы остались с этой ужасной вещью. Мы можем использовать нашу лемму, чтобы преобразовать это:
var F = function(value) {
return (value <= 1) ? 1 : value * (function(x){return maker(maker)(x);})(value - 1);
};
Еще раз применив лемму, на этот раз сделав внутреннюю анонимную функцию (( function (x) { return maker (maker) (x);})) параметром, мы получим:
var F = function(mm) {
return function(value) {
return (value <= 1) ? 1 : value * mm(value - 1);
};
}(function(x){return maker(maker)(x);});
То есть F устанавливается на результат вызова анонимной функции, принимающей один параметр, и результат этой функции выглядит как функция факториала.
Почти там! Мой следующий шаг — удалить параметр этого выражения и создать функцию, которую я собираюсь вызвать genFactorial, потому что она будет генерировать рекурсивную факториальную функцию через мгновение:
var genFactorial = function(mm) {
return function(value) {
return (value <= 1) ? 1 : value * mm(value - 1);
};
};
Теперь я могу сделать некоторые подстановки в моем «очищенном» объявлении функции выше:
var factorial = function(maker) {
return genFactorial(function(x){return maker(maker)(x);});
}(function(maker) {
return genFactorial(function(x){return maker(maker)(x);});
});
var result = factorial(5); // result === 120
Хорошо, это все еще работает. Следующим шагом будет немного обобщить это. Я собираюсь объявить новую функцию, которая может принимать функцию genFactorial в качестве параметра и производить функцию факториала, как мы ее только что написали:
var Y = function(generator) {
return function(maker) {
return generator(function(x){return maker(maker)(x);});
}(function(maker) {
return generator(function(x){return maker(maker)(x);});
});
};
И тогда мы можем легко создать функцию факториала следующим образом:
var factorial = Y(genFactorial);
var result = factorial(5); // result === 120
Вот и все. Мы можем безнаказанно удалить genFactorial после создания факториала, если мы того пожелаем, и факториал продолжит работать, потому что текущее значение genFactorial будет сохранено из-за замыкания внутри функции Y. Мы создали рекурсивную функцию для вычисления факториалов без self ссылка на имя функции.
По пути мы создали эту довольно причудливую функцию под названием Y, которая может преобразовать любую специально написанную функцию генератора для создания рекурсивной функции. Эта Y-функция, которую мы получили из первых принципов, более известна как Y-комбинатор и хорошо известна в кругах функционального программирования (а также является инвестором венчурного капитала и владельцем Hacker News ). Я называю это странным, потому что, просто взглянув на конечный результат, трудно понять, как он на самом деле работает; Вы должны пройти через вывод, как мы сделали, чтобы получить лучшее понимание. Y-комбинатор был первоначально получен американским математиком Хаскеллом Карри (после которого у нас есть функциональный язык, называемый Хаскелл и процесс, известный как каррирование ) с использованием лямбда-исчисления.
В качестве еще одного примера полезности Y-комбинатора, вот генераторная функция для числа Фибоначчи (мы предполагаем, что fib (0) === 1, fib (1) === 1 и fib (n) = fib ( n-2) + fib (n-1)):
var genFibonacci = function(mm) {
return function(value) {
if (value === 0) return 1;
if (value === 1) return 1;
return mm(value - 2) + mm(value - 1);
};
};
var fib = Y(genFibonacci);
var result = fib(7); // result === 21
Обратите внимание, что ни одно из этих исследований лямбда-исчисления не сработало бы, если бы JavaScript не поддерживал функции как первоклассные объекты (то есть функции можно передавать в качестве параметров другим функциям, а функции можно возвращать из функций).
В следующий раз в нашем путешествии мы рассмотрим кое-что попроще.