Лямбда-исчисление на JavaScript

    Привет! В этой статье я хочу в очередной раз взглянуть на лямбда-исчисление. Теоретическую сторону вопроса на хабре обсуждали уже множество раз, поэтому взглянем на то, как лямбда-исчисление может выглядеть на практике, например, на языке JavaScript (чтобы примеры можно было выполнять прямо в браузере).

    Итак, основная идея: всё есть функция. Поэтому мы ограничим себя очень узким кругом возможностей языка: любое выражение будет либо анонимной функцией с одним аргументом (x => expr), либо вызовом функции (f (x)). То есть весь код будет выглядеть похожим образом:

    id = x => x
    double = f => x => f (f (x))
    

    Поскольку результатом работы функций будут другие функции, нам понадобится способ интерпретировать результат. Это единственное место, в котором пригодятся нетривиальные возможности JavaScript.

    Базовые вещи


    Начнём, как это принято, с условного ветвления. Введём две константы:

    True  = t => f => t
    False = t => f => f
    

    Это функции «двух аргументов», True возвращает первый аргумент, False возвращает второй аргумент. То есть, справедливы следующие утверждения:

    console.assert(1 == True  (1) (2))
    console.assert(2 == False (1) (2))
    

    Данные константы представляют логические истину и ложь, и позволяют написать функцию If:

    If = b => t => f => b (t) (f)
    console.assert(1 == If (True)  (1) (2))
    console.assert(2 == If (False) (1) (2))
    

    Это уже похоже на традиционный оператор if, просто синтаксически выглядит немного иначе. Имея условное ветвление, можно легко реализовать стандартные булевы операторы:

    Not = x => If (x) (False) (True)
    And = x => y => If (x) (y) (False)
    Or  = x => y => If (x) (True) (y)
    

    Следующим делом введём первую «структуру данных» — пару. Определение выглядит следующим образом:

    Pair = x => y => (f => f (x) (y))
    Fst  = p => p (True)
    Snd  = p => p (False)
    
    p = Pair (1) (2)
    console.assert(1 == Fst (p))
    console.assert(2 == Snd (p))
    

    Оно выглядит немного страннее, но в нём есть смысл. Пара в данном случае есть функция, инкапсулирующая внутри себя 2 значения и способная передать их своему параметру при вызове. Подобным образом можно описать кортеж любой длины:

    Triplet = x => y => z => (f => f (x) (y) (z))
    Pentuplet = x => y => z => u => v => (f => f (x) (y) (z) (u) (v))
    

    Вообще говоря, с подобным арсеналом мы уже могли бы определить Byte как кортеж из 8 логических значений, Int как кортеж из 4 Byte и реализовать на них машинную арифметику, но дело это рутинное и удовольствия никакого не принесёт. Есть более красивый способ описать натуральные числа — арифметика Чёрча.

    Арифметика


    Арифметика Чёрча описывает множество натуральных чисел с нулём как функции от двух аргументов:

    Zero  = s => z => z
    One   = s => z => s (z)
    Two   = s => z => s (s (z))
    Three = s => z => s (s (s (z)))
    

    Первый аргумент — это функция, второй аргумент — это что-то, к чему функция применяется n раз. Для их построения, по сути, нужны только ноль и функция +1:

    Succ = n => (s => z => s (n (s) (z)))
    

    Succ накидывает слева ещё один вызов s на уже имеющуюся цепочку вызовов, тем самым возвращая нам следующее по порядку натуральное число. Если данная функция кажется сложной, есть альтернативный вариант. Результат его работы будет абсолютно таким же, но накидывание s здесь происходит справа:

    Succ = n => (s => z => n (s) (s (z)))
    

    Тут стоит ещё описать способ преобразования чисел Чёрча во всем нам знакомый int — это в точности применение функции x => x + 1 к нулю n раз:

    toInt = n => n (x => x + 1) (0)
    
    console.assert(0 == toInt (Zero))
    console.assert(1 == toInt (One))
    console.assert(2 == toInt (Two))
    

    Аналогично определяются операции сложения, умножения и т.д.:

    Add = n => m => m (Succ) (n)
    Mul = n => m => m (Add (n)) (Zero)
    Pow = n => p => p (Mul (n)) (One)
    //⇈ = n => m => m (Pow (n)) (One)
    

    Таки образом можно продолжать реализовывать стрелочную нотацию, но смысла в этом нет: к этому моменту принцип работы с числами должен быть понятен.

    Следующий шаг — вычитание. Следуя только что появившейся традиции, его реализация будет вот такой:

    Sub = n => m => m (Pred) (n)
    

    но остаётся проблемой реализация функции Pred. К счастью, Клини придумал её за нас.

    Pred = n => Fst
        (n (p => Pair (Snd (p))
                      (Succ (Snd (p))))
           (Pair (Zero) (Zero)))
    

    История гласит, что эта идея возникла у него во время приёма у дантиста, а анестезия тогда была посильнее, чем сейчас. Не буду с этим спорить, а объясню, что тут творится. Для получения предыдущего числа мы строим пару (n-1, n) следующим образом: применяем n раз функцию (x, y) -> (y, y+1) к паре (0, 0) и у результата извлекаем левый компонент. Как следствие, легко заметить, что число, предыдущее для нуля, тоже будет нулём. Это спасает от неопределённости и даёт множество других преимуществ.

    Для полноты картины приведу реализации операций сравнения:

    IsZero = n => n (_ => False) (True)
    Lte    = n => m => IsZero (Sub (n) (m))
    Lt     = n => m => Lte (Succ (n)) (m)
    Eq     = n => m => And (Lte (n) (m)) (Lte (m) (n))
    
    Max = n => m => If (Lte (n) (m)) (m) (n)
    Min = n => m => If (Lte (n) (m)) (n) (m)
    

    Списки


    Списки кодируются практически так же, как и натуральные числа — это тоже функции двух аргументов.

    Nil = f => x => x
    L1  = f => x => f (a0) (x)
    L2  = f => x => f (a0) (f (a1) (x))
    L3  = f => x => f (a0) (f (a1) (f (a2) (x)))
    //...
    

    Интересно отметить, что False, Zero и Nil являются одинаковыми функциями.

    Если вы знакомы с функциональными операциями на списках, то, вероятно, уже заметили, что эта структура описывает правую свёртку. Поэтому и реализуется она тривиально:

    Foldr  = f => z => l => l (f) (z)
    

    Теперь реализуем стандартные операции для персистентных списков — добавление в начало, получение «головы» и «хвоста» списка.

    Append = a => l => (f => x => f (a) (l (f) (x)))
    Head   = l => l (a => _ => a) ()
    
    list = Append (1) (Append (2) (Nil))
    console.assert(1 == Head (list))
    

    Пустые скобки в конце описания Head — это голова пустого списка. В корректной программе данное значение никогда не должно быть использовано, поэтому я и выбрал синтаксически наименьшую величину. Вообще говоря, внутри этих скобок можно писать всё, что угодно. Позднее в статье будет ещё одно место, где я буду использовать пустые скобки по абсолютно той же причине.

    Функция получения хвоста списка практически полностью повторяет функцию получения предыдущего натурального числа. По той же причине хвост пустого списка будет пустым списком.

    Tail = l => Fst (
        l (a => p => Pair (Snd (p))
                          (Append (a) (Snd (p))))
          (Pair (Nil) (Nil))
    )
    
    console.assert(2 == Head (Tail (list)))
    

    Как пример использования, приведу реализацию функции map и ещё некоторых других:

    Map     = m => l => (f => x => l (a => f (m (a))) (x))
    Length  = l => Foldr (_ => Succ) (Zero) (l)
    IsEmpty = l => IsZero (Length (l))
    
    // конвертация в стандартный список языка JavaScript
    toList    = l => Foldr (x => y => [x].concat(y)) ([]) (l)
    toIntList = l => toList (Map (toInt) (l))
    function arraysEqual(a,b) { return !(a < b) && !(b < a); } // надо для ассертов
    

    Map заменяет каждый элемент списка результатом вызова функции f на нём.
    Length и IsEmpty говорят сами за себя. toList и toIntList будут полезны для тестирования и для вывода списков в консоль.

    Рекурсия


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

    Например, я хочу написать функцию OnNonEmpty : fun => list => result, которая будет вызывать функцию fun на списке list только если он не пуст. Попробуем:

    OnNonEmpty = f => l => If (IsEmpty (l)) (Nil) (f (l))
    

    Видите ошибку? Если f не останавливается на пустом списке, то и OnNonEmpty не остановится, хотя должна. Дело в том, что JavaScript предоставляет нам аппликативный порядок вычислений, то есть все аргументы функции вычисляются до её вызова, никакой ленивости. А оператор If должен вычислять лишь одну ветку в зависимости от условия. Поэтому функцию нужно переписать, и красивее она от этого не станет.

    OnNonEmpty = f => l => (If (IsEmpty (l)) (_ => Nil) (_ => f (l))) ()
    

    Теперь If, в зависимости от условия, возвращает функцию, которую нужно вычислить. И только после этого производится вычисление, только так мы можем гарантировать ленивость.

    Вторая проблема — рекурсия. Внутри функции мы можем обращаться только к её формальным аргументам. Это значит, что функция не может ссылаться сама на себя по имени.

    Но решение есть, это пресловутый «Комбинатор Неподвижной Точки». Обычно после этих слов приводится описание комбинатора Y, но для аппликативного порядка он не годится. Вместо него мы будем использовать комбинатор Z, бессовестно подсмотренный в этой замечательной статье.

    Z = f => (x => f (y => x (x) (y)))
             (x => f (y => x (x) (y)))
    

    Комбинатор — это функция, выбираемая исходя из ровно одного свойства: Z (f) == f (Z (f)), то есть Z(f) — это такое значение x, что x == f (x). Отсюда и термин «неподвижная точка». Но не нужно думать, что каким-то чудом комбинатор способен решать уравнения, вместо этого он представляет собой бесконечный рекурсивный вызов Z(f) = f (f (f (f ( ... )))).

    «Главное свойство» комбинатора даёт прекрасный «побочный эффект»: возможность реализации рекурсии. Например, запись:

    MyFun = Z (myFun => ...)
    

    эквивалентна записи:

    MyFun = (myFun => ...) MyFun // если бы мы разрешили так делать
    

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

    Rem = Z (rem => n => m => (
        If (Lt (n) (m)) (_ => n)
                        (_ => rem (Sub (n) (m)) (m))
    ) ())
    console.assert(1 == toInt (Rem (Three) (Two)))
    console.assert(0 == toInt (Rem (Three) (One)))
    

    После этого можно реализовать наш первый полезный алгоритм — алгоритм Евклида. Забавно, но он вышел ничуть не сложнее поиска остатка от деления.

    Gcd = Z (gcd => n => m => (
        If (IsZero (m)) (_ => n)
                        (_ => gcd (m) (Rem (n) (m)))
    ) ())
    

    Последовательности


    Последняя структура данных, которой я коснусь, это «бесконечные списки», или последовательности. Функциональное программирование славится возможностью работать с подобными объектами, и я просто не могу обойти их стороной.

    Объявляются последовательности следующим образом:

    Seq = head => tail => Pair (head) (tail)
    
    SeqHead = seq => Fst (seq)
    SeqTail = seq => (Snd (seq)) ()
    

    Хвост последовательности в конструкторе — это функция вычисления новой последовательности, а не готовый результат. Такой подход обеспечивает возможность генерировать хвост бесконечной длины.

    Для возможности тестирования напишем функцию получения первых n элементов:

    SeqTake = Z (take => n => seq => (
        If (IsZero (n)) (_ => Nil)
                        (_ => Append (SeqHead (seq))
                                     (take (Pred (n)) (SeqTail (seq))))
    ) ())
    

    Если хотите поупражняться — реализуйте SeqTake без рекурсии. Это возможно, я гарантирую.

    Теперь стоит привести пример какой-нибудь последовательности. Пусть это будут натуральные числа — всё-таки приходится работать только с тем, что уже реализовано:

    Nat = (Z (natFrom => n => Seq (n) (_ => natFrom (Succ (n))))) (Zero)
    console.assert(arraysEqual([0, 1, 2], toIntList (SeqTake (Three) (Nat))))
    

    Тут используется вспомогательная функция natFrom (n), возвращающая последовательность натуральных чисел, начинающуюся с n. Nat — это просто результат natFrom (Zero).

    Осталось совсем немного, последние 2 функции, и они самые громоздкие из тех, что есть в данном тексте. Первая — функция фильтрации последовательности. Она находит в передаваемой последовательности все элементы, удовлетворяющие переданному предикату:

    SeqFilter = Z (filter => cond => seq => (
        If (cond (SeqHead (seq))) (_ => Seq (SeqHead (seq))
                                            (_ => filter (cond) (SeqTail (seq))))
                                  (_ => filter (cond) (SeqTail (seq)))
    ) ())
    

    В случае, если головной элемент не выполняет предикат, SeqFilter возвращает отфильтрованный хвост. В противном случае это будет последовательность из текущей головы и всё того же отфильтрованного хвоста.

    Вторая — последовательность простых чисел. Очередной вариант Решета Эратосфена в моём исполнении:

    Primes = (Z (sieve => nums =>
        Seq (SeqHead (nums))
            (_ => sieve (SeqFilter (p => Not (IsZero (Rem (p) (SeqHead (nums)))))
                                   (SeqTail (nums)))
    ))) (SeqTail (SeqTail (Nat)))
    

    Эту функцию можно назвать кульминацией статьи. Принцип её работы проще будет понять на псевдокоде:

    sieve (nums) {
        p = head (nums)
        rest = tail (nums)
        return append (p, sieve (filter (n -> n % p != 0, rest)))
    }
    primes = sieve [2, 3, 4, ...]
    

    Вот тест:

    Ten = Mul (Two) (Add (Two) (Three)) // s => z => s (s (s (s (s (s (s (s (s (s (z))))))))))
    console.assert(arraysEqual([2, 3, 5, 7, 11, 13, 17, 19, 23, 29],
                               toIntList (SeqTake (Ten) (Primes))))
    

    Не знаю, как вас, а меня всё ещё удивляет, что подобные вещи возможно написать с помощью лишь чистых функций!

    Заключение


    В итоге у меня получилось такое вот странное введение в LISP на примере языка JavaScript. Надеюсь я смог показать, что абстрактные математические идеи на самом деле очень близки к реальности программирования. И после подобного взгляда лямбда-исчисление перестанет выглядеть чем-то чересчур академичным.

    Ну и, конечно, вот ссылка на Github со всем кодом из статьи.

    Спасибо!
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 52
    • –2
      ++[[]][+[]]+[+[]] === "10" 

      Ответ

      true


      ['10', '10', '10'] .map(parseInt)

      Ответ

      [ 10, NaN, 2 ]

      • +8
        ['10', '10', '10'].map(parseInt)
        Ответ
        [10, NaN, 2]

        Ожидаемое поведение. Всё согласно спецификации.

        Синтаксис функции Array.prototype.map():

        arr.map(callback, thisArg);

        Параметры:
        • callback — функция, создающая элемент в новом массиве, принимает три аргумента:
          • currentValue — текущий обрабатываемый элемент массива
          • index — индекс текущего обрабатываемого элемента в массиве
          • array — массив, по которому осуществляется проход
        • thisArg — значение, используемое в качестве this при вызове функции callback, необязательный параметр


        Синтаксис функции parseInt():

        parseInt(string, radix);

        Параметры:
        • string — значение, которое необходимо проинтерпретировать
        • radix — целое число в диапазоне между 2 и 36, представляющее собой основание системы счисления числовой строки string


        В вашем примере функция parseInt() будет вызвана три раза со следующими аргументами:
        parseInt('10', 0, [10, 10, 10]); // 10
        parseInt('10', 1, [10, 10, 10]); // NaN
        parseInt('10', 2, [10, 10, 10]); // 2
        
      • +19
        Статья о том, как написать js-код после которого тебя не смогут уволить.
        • +3

          Да после такого кода и ультиматум о повышении зп можно ставить (шутка).

          • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Дошел до конца, не нашел тега brainfuck.
          • 0
            Не поверите, но я как раз собирался писать статью о лямбда исчислении на JS и даже написал под нее библиотеку.
            Статья очень хорошо переварена для неподготовленного читателя(статья на викиконспектах зашла далеко не с первого раза)
            На самом деле неплохо было бы раскрыть понятия: каррирования/декаррирования и частичного применения функций, которые тут показаны, но не указано, что это они и есть, а прочитавшие статью могут так и не понять, что страшные термины, которых они ранее избегали весьма безобидные и понятные.
            • 0

              Идея в том, что имея бедное ЛИ можно закодировать почти любую конструкцию

            • 0
              Вот вычисление лямбда-термов в браузере (не моё)
              https://www.npmjs.com/package/inet-lib
              • +2
                Не знаю, как вас, а меня всё ещё удивляет, что подобные вещи возможно написать с помощью лишь чистых функций!

                Меня больше удивляет что люди используют язык в котором практически полностью отсутствуют типы:


                omega = x => x (x)
                Omega = omega (omega) // stack overflow, аппликативный порядок "спасает"

                В итоге у меня получилось такое вот странное введение в LISP на примере языка JavaScript.

                Почему в лисп?


                Ну и ещё немного LC:


                • 0
                  Почему в лисп?

                  Ну согласитесь, практически один в один!


                  Что касается комбинаторной логики — основные комбинаторы описать не сложно, но я бы с удовольствием глянул на реализацию того же алгоритма Евклида в подобном стиле.

                  • 0

                    Ну комбинаторы были предшественниками лямбда исчислению. Их идея в том что у них есть только одна метаоперация в отличии от лямбда исчисления где их две (абстракция и аппликация) Вот вам задание напишите дерево на js потом на Черче и попробуйте написать изоморфны функции чтобы через обычное дерево считать для Черча (у меня все это написано на хаскель через ана и катаморфизмы используя F-algebra) На js я вроде тоже подобное видел называется excursion (от DrBoolean) Но как было замечено что лучше использовать языки типа хаскель для таких забав которыми вы тут занимались =)

                    • 0

                      Увы, haskell подходит только для типизированного лямбда-исчисления, я пробовал. Именно поэтому пришлось прибегнуть к языку с динамической типизацией.

                      • 0

                        Если я говорю, что можно использовать Черча в хаскель то это так и есть. И выглядит даже лучше

                        • 0

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

                          • 0

                            Позже, нет доступа к компьютеру сейчас

                            • 0
                              Вычитание единицы для чисел Чёрча довольно трудно сделать (сам Чёрч не справился, придумал Клини, сидя под наркозом у зубного врача). Вот в этой книге поищите
                              gen.lib.rus.ec/search.php?req=методы+рекурсивного+программирования&lg_topic=libgen&open=0&view=simple&res=25&phrase=1&column=def
                              • 0

                                Спасибо! В статье уже есть классическая реализация вычитания, и даже история про дантиста :)
                                Беда в том, что на хаскеле придётся писать типизированное лямбда-исчисление, и типы будут основной проблемой.

                                • 0

                                  В принципе всегда можно написать


                                  data Term = Variable Nat | Abstraction Term | Application Term Term
                                  
                                  eval :: Term -> Term
                                  -- implementation omitted

                                  (или это будет считаться читерством?)

                                  • 0

                                    Это уже написание интерпретатора внутри хаскеля. Можно, конечно, но это не тот результат, который хотелось бы иметь)

                                    • 0
                                      Описываешь нат числа через ADT с RankNTypes и дальше пойдет)
                        • 0

                          Не соглашусь, большая часть скобок появились из-за JS, а не из-за самого лямбда-исчисления.
                          Вообще в распространенных лиспах неудобно использовать каррирование и частичное применение, а Haskell и компания, опять же, не требуют столько скобок.

                          • 0

                            Верно, скобки от JS, а каррирование из лямбда-исчисления. Идея в том, что избавление от этих вещей, ровно как и введение if и let, — это просто синтаксический сахар, который мало меняет суть.

                        • 0

                          Это M комбинатор, в энергичных языках его определить можно, а в ленивых типа хаскеля нет (это если все что у ас есть то примитивы как функции)

                          • 0
                            Соглашусь, никаким лиспом тут и не пахнет. К Хаскелю гораздо ближе. Лисп проще раз в тыщу.

                            В лиспе только простейшие операции над списками типа «первый элемент», «добавить элемент к началу», «следующие за первым элементы» и т.п. Рекурсивный вызов и лямбды есть, но они имеет явно не математическое обоснование.
                            • 0

                              Можно немного конкретнее, чем лямбда-исчисление ближе к Хасеклю, чем к Лиспу?
                              Мне кажется, что система типов в этой ситуации решает далеко не в сторону Хаскеля.

                              • +1
                                Тем что на Хаскеле любая операция выражается через реальные функциональные трансформации, а в лиспе слово «лямбда» присутствует из уважения к Чарчу, и сама работа идет при помощи обычных функций как мы их понимаем в Питоне, Яве и других более близких к народу языках.
                                • 0

                                  Статья ровно о том, что "обычные функции" и лямбды это одно и то же. Мне не пришлось в JS придумывать какие-то особые функции, чем-то отличающиеся от Питона и Явы.

                              • 0

                                В википедии написано что в основе лиспа лежит ЛИ, какое именно правда не указано, может быть и нетипизированное. В любом случае термов зависящих от типов тут нет, выходит что лисп ближе.

                                • 0
                                  Пол Грехм, «On Lisp» вот тут: http://www.paulgraham.com/onlisptext.html

                                  Ни арифметики Черча, ни «все есть функция», ничего подобного.

                                  Просто есть ячейка «значение + следующий элемент», и на основании таких ячеек строится язык.

                                  Википедия конечно может тоже правду пишет, на все можно посмотреть с разных сторон. И на Луне можно сыр найти.

                                  Вот еще интересная ссылка: http://norvig.com/lispy.html реализация Лиспа на Питоне, около 40-а строк. Математикой и не пахнет, чистая работа с данными.

                                  А Хаскель как раз вокруг математики Чарча и построен, именно из-за этой математики у всех при изучении Хаскеля такая головная боль.
                                  • 0
                                    Пол Грехм, «On Lisp»

                                    Интересно видеть символ лямбды на титульной странице! И почему вас не удивляет, что в Лиспе все функции префиксные (в отличие от того же Хаскеля). Так или иначе — в книге нет ни слова о истории создания Лиспа. Да и числа Чёрча там, естественно, не будут использоваться, ибо машинное представление эффективнее на практике.


                                    ячейка «значение + следующий элемент»

                                    Есть так же другая уважаемая книга:
                                    Гарольд Абельсон и Джералд Джей Сассман, "Структура и интерпретация компьютерных программ".
                                    Советую взглянуть на параграф 2.1.3, там как раз про cons, car и cdr.


                                    А Хаскель как раз вокруг математики Чарча и построен

                                    В первую очередь он построен вокруг идеи функционального программирования, появившейся с Лиспом, и вокруг системы типов Хиндли-Милнера (да, она имеет корни в математике, но головной боли ни у кого не вызывает).

                                    • 0
                                      Какое отношение лямбды имеют к нашему диалогу?

                                      Лисп: все есть список

                                      Хаскель: все есть функция

                                      Мне как-бы все очевидно.

                                      Вы ссылку мне дали и там черным по белому написано: «Демонстрировать процедурную реализацию имеет смысл не для того, чтобы показать, как работает наш язык (Scheme, и вообще Лисп-системы, реализуют пары напрямую из соображений эффективности), а в том, чтобы показать, что он мог бы работать и так. »

                                      То есть лисп работает на реальных списках, а не на функциях. Списки можно выразить при помощи функций, равно как и функции можно представить в виде списков. Но то что car и cdr являются одними из (шести кажется) форм, которые принципиально нельзя выразить другими операциями, как-бы намекает.
                                      • 0
                                        То что Хиндли-Милнеры что-то там выразили в математике, вовсе не означает что без математики такой штуки нет. Лично для меня было очевидно как выводить типы еще до того как я узнал об этих ребятах, думаю для многих других тоже. Но мне потребовалось пол дня потратить чтобы разобраться с ихними формулами, и понять что там ничего эзотерического, просто ребята повеселились используя математику для описания простых вещей.

                                        Это как если ты используешь счеты, и тут приходит перец и говорит: смотри, я выразил твои исчисления при помощи матанализа, вот книга которую ты должен изучить чтобы научиться считать на счетах, и ты должен меня уважать, так как я придумал счеты, я математик. Че??

                                        Хиндли-Милнер как раз очевиден и не вызывает головной боли, если не пытаться его читать в оригинале.

                                        Я о математике выражения всего через функции говорил. Про вот эту запись: «L3 = f => x => f (a0) (f (a1) (f (a2) (x)))» для вас может это и очевидно, а для обычных людей это белиберда. Когда математики начинают разжевывать, оказывается что они просто все запутали излишним использованием символизации в месте где можно было использовать обычную человеческую речь, а сама идея и выеденного яйца не стоит.
                                        • +1

                                          Меня возмущает то, как легко вы плюёте на математику, лежащую в основе программирования.
                                          Цель статьи — показать, насколько лямбда-исчисление, которому без малого 100 лет, по факту близко к современному программированию. Что это не просто бесполезная заумная теория, какой её себе представляют люди подобные вам.


                                          Если вы не хотите задумываться над тем, что читаете, то данная статья не для вас. У меня отбито всё желание продолжать данный диалог, извините.

                                          • 0
                                            В основе современного программирования лежит обработка данных. Математика *используется* в программировании а вовсе не является его основой. Раньше программирование применялось исключительно ради математики. Теперь это две очень разные области.

                                            Ну если не хотите продолжать диалог, то жалко. Статья на самом деле мне понравилась, и выражение примитивных операций при помощи функций — довольно интересная для меня тема.
                              • +1
                                Для получения предыдущего числа мы строим пару

                                Который раз читаю про это и всегда удивляюсь. Почему для сложения есть простое решение, а для вычитания сложное и на сложение непохожее? Неужели никто не обращает внимание, что это выглядит как костыль?


                                Для их построения, по сути, нужны только ноль и функция +1

                                Если мы вводим функцию +1, почему нельзя ввести функцию -1?


                                Как следствие, легко заметить, что число, предыдущее для нуля, тоже будет нулём. Это спасает от неопределённости и даёт множество других преимуществ.

                                Какие тут преимущества, если банальную параболу нельзя построить? Кстати, а что насчет дробных чисел?

                                • 0

                                  Операция "+1" вводится для натуральных чисел аксиоматически, а вот для реализации "-1" нужно перебирать числа, начиная с нуля, пока не найдём подходящее. Так уж числа устроены. Введение "-1" в аксиоматику избыточно и только бы всё усложнило.


                                  Какие тут преимущества, если банальную параболу нельзя построить?

                                  Не совсем понимаю, причём тут парабола. Кодировались неотрицательные целые числа. Если нужны числа со знаком, можно и для них структуру данных создать, например пара (знак, модуль). Дроби тоже кодируются парой (числитель, знаменатель).
                                  Как было сказано в начале статьи, всегда в распоряжении есть булевы значения и кортежи любой длины, хоть IEEE 754 реализуй, никаких ограничений!

                                  • 0

                                    Мы же не перебираем все числа до миллиона при вычислении выражения 1000000 — 1. Мы пользуемся правилами вычисления.


                                    В примере с натуральными числами они не были реализованы через кортеж битов. Потому и возник вопрос про аналогичное построение отрицательных а заодно и дробных чисел. Потому что никаких преимуществ в отсутствии отрицательных чисел нет.

                                    • 0

                                      Преимущества есть в том, что перед нулём находится ноль, это позволяет легко определить операции сравнения. Реализация Lte, например, именно этим фактом и пользуется.
                                      Касательно 1000000-1 — в теории (в арифметике Пеано) вычисление происходит именно перебором чисел от 0 до 999999. На практике же мы используем более продвинутые инструменты.

                                      • 0

                                        А, то есть если мне понадобятся отрицательные числа, то у меня еще и функция Lte сломается)


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

                                        • 0

                                          Lte рассчитана на целые неотрицательные числа, для сравнения знаковых целых понадобится другая функция.


                                          значит в нем должны быть средства реализовать такие простые вещи

                                          Средства есть, числа со знаком реализуются в виде пар. Неплохое объяснение есть в википедии: https://en.wikipedia.org/wiki/Church_encoding#Signed_numbers
                                          Вам стоит понять, что, как и в школьной арифметике, в первую очередь вводятся натуральные числа, а уже потом на их основании целые и рациональные. И это вовсе не говорит о каких-то проблемах в лямбда-исчислении.

                                          • 0

                                            Ок. То есть, я правильно понял, там есть отрицательные числа, но в операциях с ними все равно поиск предыдущего используется?


                                            Но ведь, если ввести -1, то все вычисления станут проще, разве нет?

                                            • 0

                                              Числа изначально вводятся через понятие количества, или длины цепочки вызовов. Это наиболее естественный способ, не подразумевающий под собой наличие константы "-1". Те же числа потом и используются похожим образом — индекс в списке, длина списка, длина подпоследовательности… Наличие знака при этом было бы избыточным и ничего бы не упростило.
                                              Вы верно поняли, описанное представление чисел со знаком всё равно требует трудоёмких операций поиска соседнего числа. Я представляю себе только один способ избавиться от этого — кодировать числа в позиционной системе счисления. Но подобная тема по своему объёму сама заслуживает отдельной статьи.
                                              К вопросу о том, станут ли вычисления проще — если вычисления требуют отрицательных чисел, то мы можем и должны их предоставить. Не знаю, что тут ещё можно добавить.

                                              • 0

                                                Почему избыточным, если они нам нужны и мы все равно вводим их через пары? Я бы даже сказал, имитируем. Причем вводим при этом две дополнительные константы для знаков вместо одной операции.

                                                • 0

                                                  Избыточным потому, что за всю статью отрицательные числа ни разу не пригодились, а если многое можно сделать без них, то есть смысл иметь беззнаковые числа.

                                      • +1

                                        В данном случае важнее то, что о таких числах удобно рассуждать с точки зрения логики, а не алгоритмическая сложность вычитания.

                                        • 0

                                          Я не столько про алгоритмическую сложность, сколько про сам подход. Сложение сделано так, а обратная операция абсолютно по-другому. Нелогично.

                                          • 0

                                            Все потому что числа у нас натуральные, а вычитание для них не замкнуто.

                                            • 0

                                              Вот я и говорю, зачем нам только натуральные. Можно же и дополнительные множества определить, и вычитание нормально сделать. Неужели в функциональном программировании нет такого способа?

                                              • 0

                                                Покажите как.

                                                • 0

                                                  Не знаю, потому и спросил) Если б знал, сразу бы написал. Просто то, что есть сейчас, не выглядит логичным, значит теоретически есть возможность сделать лучше.

                                                  • 0
                                                    Просто то, что есть сейчас, не выглядит логичным, значит теоретически есть возможность сделать лучше.

                                                    Доказать это утверждение вы можете только одним способом — предложить своё решение.

                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.