Спасибо! В статье уже есть классическая реализация вычитания, и даже история про дантиста :)
Беда в том, что на хаскеле придётся писать типизированное лямбда-исчисление, и типы будут основной проблемой.
Интересно видеть символ лямбды на титульной странице! И почему вас не удивляет, что в Лиспе все функции префиксные (в отличие от того же Хаскеля). Так или иначе — в книге нет ни слова о истории создания Лиспа. Да и числа Чёрча там, естественно, не будут использоваться, ибо машинное представление эффективнее на практике.
ячейка «значение + следующий элемент»
Есть так же другая уважаемая книга:
Гарольд Абельсон и Джералд Джей Сассман, "Структура и интерпретация компьютерных программ".
Советую взглянуть на параграф 2.1.3, там как раз про cons, car и cdr.
А Хаскель как раз вокруг математики Чарча и построен
В первую очередь он построен вокруг идеи функционального программирования, появившейся с Лиспом, и вокруг системы типов Хиндли-Милнера (да, она имеет корни в математике, но головной боли ни у кого не вызывает).
Статья ровно о том, что "обычные функции" и лямбды это одно и то же. Мне не пришлось в JS придумывать какие-то особые функции, чем-то отличающиеся от Питона и Явы.
Избыточным потому, что за всю статью отрицательные числа ни разу не пригодились, а если многое можно сделать без них, то есть смысл иметь беззнаковые числа.
Числа изначально вводятся через понятие количества, или длины цепочки вызовов. Это наиболее естественный способ, не подразумевающий под собой наличие константы "-1". Те же числа потом и используются похожим образом — индекс в списке, длина списка, длина подпоследовательности… Наличие знака при этом было бы избыточным и ничего бы не упростило.
Вы верно поняли, описанное представление чисел со знаком всё равно требует трудоёмких операций поиска соседнего числа. Я представляю себе только один способ избавиться от этого — кодировать числа в позиционной системе счисления. Но подобная тема по своему объёму сама заслуживает отдельной статьи.
К вопросу о том, станут ли вычисления проще — если вычисления требуют отрицательных чисел, то мы можем и должны их предоставить. Не знаю, что тут ещё можно добавить.
Lte рассчитана на целые неотрицательные числа, для сравнения знаковых целых понадобится другая функция.
значит в нем должны быть средства реализовать такие простые вещи
Средства есть, числа со знаком реализуются в виде пар. Неплохое объяснение есть в википедии: https://en.wikipedia.org/wiki/Church_encoding#Signed_numbers
Вам стоит понять, что, как и в школьной арифметике, в первую очередь вводятся натуральные числа, а уже потом на их основании целые и рациональные. И это вовсе не говорит о каких-то проблемах в лямбда-исчислении.
Преимущества есть в том, что перед нулём находится ноль, это позволяет легко определить операции сравнения. Реализация Lte, например, именно этим фактом и пользуется.
Касательно 1000000-1 — в теории (в арифметике Пеано) вычисление происходит именно перебором чисел от 0 до 999999. На практике же мы используем более продвинутые инструменты.
Можно немного конкретнее, чем лямбда-исчисление ближе к Хасеклю, чем к Лиспу?
Мне кажется, что система типов в этой ситуации решает далеко не в сторону Хаскеля.
Операция "+1" вводится для натуральных чисел аксиоматически, а вот для реализации "-1" нужно перебирать числа, начиная с нуля, пока не найдём подходящее. Так уж числа устроены. Введение "-1" в аксиоматику избыточно и только бы всё усложнило.
Какие тут преимущества, если банальную параболу нельзя построить?
Не совсем понимаю, причём тут парабола. Кодировались неотрицательные целые числа. Если нужны числа со знаком, можно и для них структуру данных создать, например пара (знак, модуль). Дроби тоже кодируются парой (числитель, знаменатель).
Как было сказано в начале статьи, всегда в распоряжении есть булевы значения и кортежи любой длины, хоть IEEE 754 реализуй, никаких ограничений!
Продемонстрируйте, пожалуйста, операцию вычитания для чисел Чёрча на хаскеле. Вероятно, я просто не смог её написать, поэтому хочу взглянуть, как это делается.
Верно, скобки от JS, а каррирование из лямбда-исчисления. Идея в том, что избавление от этих вещей, ровно как и введение if и let, — это просто синтаксический сахар, который мало меняет суть.
Что касается комбинаторной логики — основные комбинаторы описать не сложно, но я бы с удовольствием глянул на реализацию того же алгоритма Евклида в подобном стиле.
Сама по себе хвостовая рекурсия важна для функциональных языков, где циклов нет как таковых.
Что же касается нефункциональных языков — согласитесь, гораздо приятнее, когда оптимизациями занимается компилятор, а не программист. Плюс рекурсивный код зачастую выглядит красивее и более естественно, чем аналогичный итеративный (как пример — реализация gcd из поста, если из неё выкинуть try/catch, ну или метод add из самого начала).
Спасибо за развёрнутый комментарий! У меня есть к нему несколько замечаний:
Проблема с исключениями остается, но на мой взгляд она несущественна
Пример в статье явно показывает, что игнорирование исключений может всё сломать. Понятие "нормально написанной" программы в вашем комментарии мне не ясно. Программы ведь всякие бывают.
Оптимизация хвостовой рекурсии может делаться не только переходом на начало функции
Странно, среде выполнения ведь всё равно надо будет начать выполнение функции с первой команды независимо от того, был кадр стэка пересоздан или нет.
Проблема с полиморфизмом исчезает
Решение проблемы с полиморфизмом, предложенное вами, уже не имеет к хвостовой рекурсии никакого отношения, но да, такой подход в принципе реализуем. Насколько я понимаю, JIT делает что-то очень похожее с помощью инлайна методов.
такая оптимизация потенциально может позволить зловредному коду вызвать не положенную ему функцию
С этим я не согласен. В стэке вызовов мы заменяем цепочку одинаковых классов на единичный элемент. AccessControlContext это затронуть не должно.
Скажем так, единственность решения обычно подразумевается. Если находится два допустимых решения, то это ошибка издателя, такая раскладка не должна быть допущена до конечного потребителя. Но в теории, конечно, легко составить судоку, которое будет иметь 10 решений, или вообще ни одного. Простейший вариант — неоднозначность типа
1 2
2 1
Это не является правдой. Хотя скорее так — нужно уточнить понятие "доступных".
В этапе 1 я перечислил в сумме 4x9x9 ограничений (в нумерованных пунктах). По факту это есть классические правила судоку. Если "доступностью" считать логическую выполнимость всех этих ограничений по отдельности, то уж точно не каждый ход приведёт к правильному решению.
Пример с судоку приводить не буду, так как для этого нужно сидеть и решать, а вот аналогичный с логическими формулами — легко:
1) (a || b) && (!a || b)
2) (a || b) && (!a || !b)
Обе формулы выполнимы по отдельности при "a == true", но вот их конъюнкция при этом будет ложной.
P.S. естественно именно такой конфигурации, как в моём примере, в реальных судоку не возникнет. Ситуация неоднозначиности на практике бывает тогда, когда неизвестных как минимум несколько десятков.
Способ хороший. Использовать я его, конечно, не буду)
А если серьёзно, я бы с удовольствием, но тут встаёт большой вопрос определения размера входа задачи. 2 раскладки судоку легко могут привести к формулам в КНФ с количествами дизъюнктов, отличающимися на порядки. И эту величину сложно прогнозировать заранее, когда ты просто выбираешь/генерируешь задачу. Это первая проблема.
Вторая проблема — случайный выбор начальных данных для системы ОДУ. Это приводит к непредсказуемому времени выполнения, а значит эксперимент придётся запускать очень много раз, чтобы узнать среднее значение. Будь алгоритм полностью детерминированным (не зависел бы от рандома), всё стало бы куда проще.
В общем, для данного конкретного алгоритма определение сложности станет той ещё головной болью.
Так или иначе, большое спасибо за развёрнутый комментарий!
Действительно интересный вопрос, я бы тоже рад был знать ответ. Мне вообще не понятно, как можно адекватно оценить трудоёмкость описанного алгоритма.
Сразу можно сказать одно — чем больше будет размерность, тем больше будет погрешность вычислений на последнем этапе, поскольку коэффициенты am экспоненциально растут по мере нахождения ответа. Рано или поздно мы выбьемся из точности double, после этого ни о какой эффективности и говорить не стоит.
Спасибо! В статье уже есть классическая реализация вычитания, и даже история про дантиста :)
Беда в том, что на хаскеле придётся писать типизированное лямбда-исчисление, и типы будут основной проблемой.
Интересно видеть символ лямбды на титульной странице! И почему вас не удивляет, что в Лиспе все функции префиксные (в отличие от того же Хаскеля). Так или иначе — в книге нет ни слова о истории создания Лиспа. Да и числа Чёрча там, естественно, не будут использоваться, ибо машинное представление эффективнее на практике.
Есть так же другая уважаемая книга:
Гарольд Абельсон и Джералд Джей Сассман, "Структура и интерпретация компьютерных программ".
Советую взглянуть на параграф 2.1.3, там как раз про
cons,carиcdr.В первую очередь он построен вокруг идеи функционального программирования, появившейся с Лиспом, и вокруг системы типов Хиндли-Милнера (да, она имеет корни в математике, но головной боли ни у кого не вызывает).
Статья ровно о том, что "обычные функции" и лямбды это одно и то же. Мне не пришлось в JS придумывать какие-то особые функции, чем-то отличающиеся от Питона и Явы.
Избыточным потому, что за всю статью отрицательные числа ни разу не пригодились, а если многое можно сделать без них, то есть смысл иметь беззнаковые числа.
Числа изначально вводятся через понятие количества, или длины цепочки вызовов. Это наиболее естественный способ, не подразумевающий под собой наличие константы "-1". Те же числа потом и используются похожим образом — индекс в списке, длина списка, длина подпоследовательности… Наличие знака при этом было бы избыточным и ничего бы не упростило.
Вы верно поняли, описанное представление чисел со знаком всё равно требует трудоёмких операций поиска соседнего числа. Я представляю себе только один способ избавиться от этого — кодировать числа в позиционной системе счисления. Но подобная тема по своему объёму сама заслуживает отдельной статьи.
К вопросу о том, станут ли вычисления проще — если вычисления требуют отрицательных чисел, то мы можем и должны их предоставить. Не знаю, что тут ещё можно добавить.
Lte рассчитана на целые неотрицательные числа, для сравнения знаковых целых понадобится другая функция.
Средства есть, числа со знаком реализуются в виде пар. Неплохое объяснение есть в википедии: https://en.wikipedia.org/wiki/Church_encoding#Signed_numbers
Вам стоит понять, что, как и в школьной арифметике, в первую очередь вводятся натуральные числа, а уже потом на их основании целые и рациональные. И это вовсе не говорит о каких-то проблемах в лямбда-исчислении.
Преимущества есть в том, что перед нулём находится ноль, это позволяет легко определить операции сравнения. Реализация
Lte, например, именно этим фактом и пользуется.Касательно 1000000-1 — в теории (в арифметике Пеано) вычисление происходит именно перебором чисел от 0 до 999999. На практике же мы используем более продвинутые инструменты.
Можно немного конкретнее, чем лямбда-исчисление ближе к Хасеклю, чем к Лиспу?
Мне кажется, что система типов в этой ситуации решает далеко не в сторону Хаскеля.
Операция "+1" вводится для натуральных чисел аксиоматически, а вот для реализации "-1" нужно перебирать числа, начиная с нуля, пока не найдём подходящее. Так уж числа устроены. Введение "-1" в аксиоматику избыточно и только бы всё усложнило.
Не совсем понимаю, причём тут парабола. Кодировались неотрицательные целые числа. Если нужны числа со знаком, можно и для них структуру данных создать, например пара
(знак, модуль). Дроби тоже кодируются парой(числитель, знаменатель).Как было сказано в начале статьи, всегда в распоряжении есть булевы значения и кортежи любой длины, хоть IEEE 754 реализуй, никаких ограничений!
Продемонстрируйте, пожалуйста, операцию вычитания для чисел Чёрча на хаскеле. Вероятно, я просто не смог её написать, поэтому хочу взглянуть, как это делается.
Верно, скобки от JS, а каррирование из лямбда-исчисления. Идея в том, что избавление от этих вещей, ровно как и введение if и let, — это просто синтаксический сахар, который мало меняет суть.
Увы, haskell подходит только для типизированного лямбда-исчисления, я пробовал. Именно поэтому пришлось прибегнуть к языку с динамической типизацией.
Ну согласитесь, практически один в один!
Что касается комбинаторной логики — основные комбинаторы описать не сложно, но я бы с удовольствием глянул на реализацию того же алгоритма Евклида в подобном стиле.
Сама по себе хвостовая рекурсия важна для функциональных языков, где циклов нет как таковых.
Что же касается нефункциональных языков — согласитесь, гораздо приятнее, когда оптимизациями занимается компилятор, а не программист. Плюс рекурсивный код зачастую выглядит красивее и более естественно, чем аналогичный итеративный (как пример — реализация gcd из поста, если из неё выкинуть try/catch, ну или метод add из самого начала).
В теории нарушения семантики не должно быть. На практике же всё немного сложнее — ошибка либо у меня, либо у IDEA, и тут я не знаю точного ответа.
Спасибо за развёрнутый комментарий! У меня есть к нему несколько замечаний:
Пример в статье явно показывает, что игнорирование исключений может всё сломать. Понятие "нормально написанной" программы в вашем комментарии мне не ясно. Программы ведь всякие бывают.
Странно, среде выполнения ведь всё равно надо будет начать выполнение функции с первой команды независимо от того, был кадр стэка пересоздан или нет.
Решение проблемы с полиморфизмом, предложенное вами, уже не имеет к хвостовой рекурсии никакого отношения, но да, такой подход в принципе реализуем. Насколько я понимаю, JIT делает что-то очень похожее с помощью инлайна методов.
С этим я не согласен. В стэке вызовов мы заменяем цепочку одинаковых классов на единичный элемент. AccessControlContext это затронуть не должно.
Скажем так, единственность решения обычно подразумевается. Если находится два допустимых решения, то это ошибка издателя, такая раскладка не должна быть допущена до конечного потребителя. Но в теории, конечно, легко составить судоку, которое будет иметь 10 решений, или вообще ни одного. Простейший вариант — неоднозначность типа
1 2
2 1
Это не является правдой. Хотя скорее так — нужно уточнить понятие "доступных".
В этапе 1 я перечислил в сумме 4x9x9 ограничений (в нумерованных пунктах). По факту это есть классические правила судоку. Если "доступностью" считать логическую выполнимость всех этих ограничений по отдельности, то уж точно не каждый ход приведёт к правильному решению.
Пример с судоку приводить не буду, так как для этого нужно сидеть и решать, а вот аналогичный с логическими формулами — легко:
1) (a || b) && (!a || b)
2) (a || b) && (!a || !b)
Обе формулы выполнимы по отдельности при "a == true", но вот их конъюнкция при этом будет ложной.
P.S. естественно именно такой конфигурации, как в моём примере, в реальных судоку не возникнет. Ситуация неоднозначиности на практике бывает тогда, когда неизвестных как минимум несколько десятков.
Способ хороший. Использовать я его, конечно, не буду)
А если серьёзно, я бы с удовольствием, но тут встаёт большой вопрос определения размера входа задачи. 2 раскладки судоку легко могут привести к формулам в КНФ с количествами дизъюнктов, отличающимися на порядки. И эту величину сложно прогнозировать заранее, когда ты просто выбираешь/генерируешь задачу. Это первая проблема.
Вторая проблема — случайный выбор начальных данных для системы ОДУ. Это приводит к непредсказуемому времени выполнения, а значит эксперимент придётся запускать очень много раз, чтобы узнать среднее значение. Будь алгоритм полностью детерминированным (не зависел бы от рандома), всё стало бы куда проще.
В общем, для данного конкретного алгоритма определение сложности станет той ещё головной болью.
Так или иначе, большое спасибо за развёрнутый комментарий!
Действительно интересный вопрос, я бы тоже рад был знать ответ. Мне вообще не понятно, как можно адекватно оценить трудоёмкость описанного алгоритма.
Сразу можно сказать одно — чем больше будет размерность, тем больше будет погрешность вычислений на последнем этапе, поскольку коэффициенты am экспоненциально растут по мере нахождения ответа. Рано или поздно мы выбьемся из точности double, после этого ни о какой эффективности и говорить не стоит.