Функции в JavaScirpt

История, терминология,
примеры

Проблема разрешения

Давид Гильберт, 1928

Может ли существовать какой-то способ проверить, является ли данное арифметическое утверждение доказуемым или не доказуемым.

Вики

Может ли существовать такой алгоритм, который примет на вход другой алгоритм и скажет, нормальный этот принятый алгоритм или кривой?

Существует ли способ понять, может ли этот входящий алгоритм выдать в итоге ответ или он зависнет?

Алгоритмическая разрешимость, Проблема остановки

Зачем разбираться?

Например, чтобы понять, что смогут сделать ЭВМ, а чего не могут.

Чёрч и Тьюринг

И еще Пост.

Не существует алгоритма, определяющего является ли данное арифметическое утверждение доказуемым или не доказуемым.

Тезис Черча-Тьюринга

Инструменты

λ-исчисление

Формальный аппарат, придуманный для анализа вычислимости. Основа — анонимная функция от одного аргумента.

x² + 5x + 7 — выражение. Но что здесь x?

f(x) = x² + 5x + 7 — общепринятое обозначение того, что вместо x можно что-то подставлять.
f(4) = 4² + 5×4 + 7

А как представить выражение с переменной, которое сразу же принимает ее значение?

Например, так:
[x² + 5x + 7](4)

А для нескольких переменных так:
[x² + 5x + 7y](4, 5)

Изначальный вариант Чёрча
^x[x² + 5x + 7](4)

^x^y[x² + 5x + 7y](4, 5)

Потом крышки стали лямбдами
(вроде как писать на машинке было проще и символ красивый)
λx[x² + 5x + 7](4)

λxλy[x² + 5x + 7y](4, 5)

Чёрч писал без скобок, но с подсветкой
(любил разноцветные чернила)
λx.x² + 5x + 7 4

λx.λy.x² + 5x + 7y 4 5

На самом деле одного аргумента хватит для всех возможных вычислений.

F(x,y) эквивалентно (f(x))(y)

λx[λy[x² + 5x + 7y]](4)(5)

Было: функция от двух аргументов

(function (x, y) {
    return x**2 + 5*x + 7*y
})(4, 5); // 71

(function (x) {
    return function (y) {
        return x**2 + 5*x + 7*y
    }
})(4)(5); // 71

Современный синтаксис

(x => y => x**2 + 5*x + 7*y)(4)(5); // 71

Свободные и связанные переменные

Лямбда-функция связывает переменную.

Привет, окружение и замыкание.

Функции эквивалентны значениям. Их можно передавать как аргументы и возвращать как результат вычислений.

λx[x² + 5x + 7](λz[z+1])(3)

Привет, колбэки!

    [-1, 0, -3, 2, 3].filter(n => n > 0)

Возможно, у этой системы найдутся приложения не только в роли логического исчисления.
— Алонзо Чёрч, 1932

Машина Тьюринга

Архитектура ЭВМ

Машину Тьюринга можно собрать руками, лямбда-исчисление — абстрактный аппарат.

Императивность для компьютеров естественнее, чем декларативность.

Такое пишется чаще:

    let sum = 0;
    for (let i = 0; i <= 100; i++) {
        sum += i;
    }

    (function sum(n, acc) {
        return (n == 0) ? acc : sum(n - 1, acc + n);
    })(100, 0)

Lisp

λx.λy.x² + 5x + 7y 4 5

    ((λ (x y)
        (+ (expt x 2) (* 5 x) (* 7 y))) 4 5) ; 71

Лисп-машина

Впервые на Лисп-машинах

• Сборка мусора
• Лазерная печать
• Многооконный графический интерфейс пользователя
• Растровая графика высокого разрешения
• Рендеринг
• Множество сетевых инноваций.

JS

Come and put Scheme
into the Browser!

Three Magic Words

JS = Lisp + Self

+ синтаксис а-ля Java

The strength of JavaScript is that you can do anything.
The weakness is that you will.

— Reg Braithwaite

Функции пришли в JS из Лиспа

Имеем λ-исчисление + императивность

Функции — данные

    const checker = n => n > 0
    [-1, 0, -3, 2, 3].filter(checker)

Определения

    // Функциональное выражение (Function Expression)
    const checker = n => n > 0

    // Объявление функции (Function Declaration)
    function checker (n) { return n > 0 }

    // Функция высшего порядка (Higher-Order Function)
    [-1, 0, -3, 2, 3].filter(checker)

Люди второго сорта

• Живут отдельно
• Отдельные места в транспорте
• Нельзя входить в некоторые общественные места

Собакам и китайцам вход запрещен

Сущности второго класса

• Нельзя передать как аргумент.
• Нельзя сохранить в переменную.
• Нельзя вернуть в качестве результата вычисления.

В отличие от сущностей первого класса.

Функции в JS — сущности первого класса

First Class Entities or First Class Objects

• Передаются как аргумент
• Сохраняются в переменную
• Возвращаются из функции [высшего порядка]

Функции высшего порядка

Higher-Order Function

• Принимают функцию как аргумент
• Возвращают функцию как результат вычислений

    [-1, 0, -3, 2, 3].filter(n => n > 0)

Именованное функциональное выражение

Удобно для рекурсии

    const sumOf = function fn (acc) {
      return acc == 0 ? acc : acc + fn(acc - 1)
    }
    sumOf(10) // 55

Функция с вызовом на месте

Immediately Invoked Function Expression, IIFE

    var Module = (function (window, undefined) {
        const private = 'secret'
        const public = 'It is not a ' + private

        // Отдаем наружу только то, что нужно
        return { public: public }
    })(window, undefined);

    console.info(Module.public)
    console.info(Module.private) // undefined

Самовызывающаяся функция

Self-executing function (не путать с IIFE)

    const sum = function fn (acc) {
      return acc == 0 ? acc : acc + fn(acc - 1)
    }
    sum(10) // 55

Самовызывающаяся функция с вызовом на месте

Все сразу

    (function fn (acc) {
      return acc == 0 ? acc : acc + fn(acc - 1)
    })(10)

Итого

λ-исчисление и машина Тьюринга породили два подхода к созданию языков программирования: декларативный (функциональный) и императивный.

λ-исчисление → Lisp → Scheme → JS.

В JS много всего можно делать с функциями.

ООП и функциональное программирование могут быть полностью совместимыми (и должны быть!).

Нам лишь нужно понять, что «компьютеры — это симуляторы» и разобраться, что же симулировать.

— Алан Кей, создатель ООП

Конец

Спасибо за внимание

amiskov@ya.ru, andreymiskov.ru