Научное программирование: часть 1

Очень странное обсуждение! Целая статья о "научном программировании", 200 комментариев, жаркие споры и ни разу не прозвучали волшебные слова: "денотационная семантика", "аксиоматическая семантика", "изоморфизм Карри-Говарда", "формальная верификация". Зато есть "ООП", "ФП", "хочешь странного: Хаскель и всякие F#"… Неужели никому в этой дискуссии не интересно именно научное программирование, а не ваяние формочек?

Олимпиадные задачи в промышленном программировании. Часть 1

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

Олимпиадные задачи в промышленном программировании. Часть 1

Хорошая задачка, приходилось её решать. Приведённое решение неплохо справляется с задачей, но всё становится хитрее, если элементы повторяются, как например, буквы в реальном тексте. В таком, более общем виде, эта задача хорошо разобрана на Rosetta code. Там приводится и моё решение для Haskell, решающее задачу с фиксированным объёмом используемой памяти и за линейное время (в on-line режиме).

SALI — это Вам ~ язык программирования

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

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

SALI — это Вам ~ язык программирования

Судя по описанию, нет. Haskell — это, прежде всего, система типов, затем ленивость и, наконец, лямбда-исчисление, которое в том или ином виде присутствует во всех ФЯП.

SALI — это Вам ~ язык программирования

А если серьёзно, то желаю вам удачи и не сильно обидеться на нас "академиков". Это непросто изобрести что-то новое, но я убеждён, что нужно пытаться и стараться изобретать. Одно непременное условие: не переставать учиться, сочтя, что весь мир остался далеко позади.

SALI — это Вам ~ язык программирования

Продолжу игру в угадайку, пока не вышла вторая статья. Значит так… Декларативность, функциональность и чистота, произвольная вложенность объектов и явные зависимости между ними, предельно простой синтаксис, нацеленность на конфигурирование систем, неполнота по Тьюрингу (судя по утверждению о конечных автоматах)… Это Nix! А если гарантируется тотальность, то Dhal. Правда, они статически типизированные.

Самые симметричные объекты в мире

Абстрактность математики не означает, что в ней можно придумать всё что угодно человеческой фантазии или творческому порыву. Математика — это оплот объективного идеализма в современном мире.
Фантаст может придумать мир, который будет жить по придуманным им законам (любым), но только в книге, в идее, наблюдать такой мир нельзя, открыть его не получится. Реальный мир, если мы, всё же, предполагаем его существование, накладывает определённые ограничения на нашу фантазию.
Если бы группу Е8 придумали, наделив её искусственными свойствами, не удалось бы предсказать и обнаружить её представление в реальном мире — состоянии твёрдого тела.

Как я "<" моноидом делал

Если мы хотим моноид, то нейтральный элемент должен быть нейтральным как справа, так и слева. Некоммутативность операции тут не может быть оправданием. В противном случае, мы не сможем получить нормальную ассоциативность:

 если   x * e ≠ e * x   то    (a * e) * b ≠ a * (e * b)

а без ассоциативности моноид не получится никак.

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

λ> getMin <$> foldMap (Just . Min) ([2,4,1,8,5] :: [Integer])
Just 1
λ> getMin <$> foldMap (Just . Min) ([] :: [Integer])
Nothing

где Min импортирован из Data.Semigroup.

Однако, когда мне нужно было на практике использовать моноид Min для неограниченного множества я ввёл для этого множества искусственные границы, то есть определил его экземпляром класса Bounded. Так существенно удобнее, чем таскать Maybe.

Ну и, наконец, Maybe (Min a) равен, с точностью до изоморфизма, типу Min a + Maximal. Так что преступления никакого автор не совершает. К тому же, спорное Maximal можно заменить на Undefined, это дело вкуса и стилистики.

Чем отличается императивное программирование от декларативного

За это мы, махровые декларативщики, и боремся! Практически идеальны в этом отношении конкатенативные языки, такие как Joy или J.

Чем отличается императивное программирование от декларативного

Добавьте в ваше описание типы, а к типам свойства, или лучше, аксиоматическую семантику, и абсурдные комбинации отпадут.

Чем отличается императивное программирование от декларативного

Декларативный подход, как таковой, существует. Это аксиоматика, денотационная семантика, лежащая в основе языка, даже императивного, наконец, просто способ декомпозиции и композиции задачи. Чаще всего, он используется в комплексе с императивными конструкциями, но иногда и сам по себе: HTML, CSS и SVG тому примеры.

Чем отличается императивное программирование от декларативного

Не удержусь, приведу пример функционального декларативного описания на Haskell.

Начнём с описания омлета:

omelette :: Food f => Int -> f
omelette n = fried . scrambled . map broken $ eggs
  where
    eggs = take n $ repeat Egg
    broken Egg = Scrambled Yolk <> Scrambled EggWhite
    scrambled = getScrambled . fold

В этом описании используются стандартные функции для создания и обработки коллекций: repeat, take и foldMap, универсальная функция: fried, полугруппа Scrambled ну, и, собственно, яйца.

Пусть для яйца и его частей будут определены атомарные типы:

data Yolk = Yolk
data EggWhite = EggWhite
data EggShell = EggShell
data Egg = Egg

Взбалтывать и жарить можно не только яйца. Для взболтанных продуктов определим тип-обёртку Scrambled. Взболтанные продукты образуют полугруппу: смесь двух взболтанных продуктов тоже является взболтанным продуктом, причём их смешивание ассоциативно.

Наконец, опишем универсальный процесс жарки:

fried :: Food f => f -> f
fried x = heated 180 x `for` Minutes 8

Здесь используются универсальные функции из гипотетической библиотеки Reactive.Bananas.Cooking с такими сигнатурами:

heated :: Temperature -> a -> Process a
for :: Process a -> Time -> a

Для абстракции времени тут используется реактивное программирование.

Чем отличается императивное программирование от декларативного

Пока единственный пример декларативного описания яичницы дал @Unrull. В нём хорошо разделены описание и интерпретация.

Декларативное описание состоит из неупорядоченной последовательности определений, позволяющей однозначно редуцировать выражение, определяющее конкретную яичницу к нормальной форме. Саму яичницу будет делать исполнитель, он получит императивный объектный код, в который транслируется нормальная форма, определяющая яичницу. В решении @Unrull дана нормальная форма в виде свободной монады. Её соответствующей F-алгеброй можно интерпретировать в последовательность действий, в том числе, побочных.

Гораздо, впрочем, лучше разницу между декларативным и императивным подходами показывает пример с описанием изображения, скажем, домика:

Декларативное:

house = (roof `above` (window `over` walls)) `at` (0,0) 
roof = triangle 100 50 `color` "blue"
walls = square 100 `color` "brown"
window = w' `above` w'
  where w = square 10
         w' = w `beside` w

Эту программу пишет и отлаживает человек. Всю вычислительную работу выполняют конструкторы примитивов square и triangle, а также универсальные комбинаторы: above, below, over и at.

Императивное:

function DrawHouse () {
  // roof
  newPath()
  moveTo(0,100)
  lineTo(100,100)
  lineTo(50,150)
  lineTo(0,100)
  setColor("blue")
  stroke()

  // walls
  newPath()
  moveTo(0,0)
  lineTo(100,0)
  lineTo(100,100)
  lineTo(0,100)
  lineTo(0,0)
  setColor("brown")
  stroke()
  ...
}

Чем отличается императивное программирование от декларативного

Это у вас свободная монада получилась. Поздравляю!

Тёмный путь

Настоящие и стОящие теории требуют вдумчивой проверки временем и длительного осмысления, после чего они превращаются в непотопляемый и неподвластный моде фундамент. Развитие современных ЯП состоит в создании эффективных механизмов для воплощения фундаментальных идей и в поиске современных задач, решаемых "старыми" методами. Изоморфизм Карри-Ховарда, в конце концов, сводит большинство "новых" подходов в программировании к "старым" подходам в алгебре, логике или топологии. Но это не значит, что всё уже "украдено до нас" и "всё в географии открыто".
Кстати, находка по-настоящему удачного синтаксического сахара к полезной, но неудобоваримой теоретической конструкции — это очень важная составляющая прогресса. Изобретение бра и кет векторов для исчисления состояний, оператора Гамильтона для представления дифференциальных операторов в теории поля, диаграмм Фейнмана для описания механики частиц, регулярных выражений для представления конечных автоматов, введение do-нотации для монад и адаптация коалгебры для комонады косостояния в виде изящных линз в Haskell, "толстые" стрелки для представления громоздких делегатов… все эти синтаксические нововведения не являются чем-то фундаментальным, но они позволяют просто и последовательно рассуждать о сложных концепциях, не теряя внутренней структуры концепции. Это сродни открытию нового представления для группы или построения изоморфизма между абстрактной "невидимой" структурой и житейским "обозримым" понятием. Это классная, красивая, хоть и непростая и небыстрая часть прогресса!

Использование map и reduce в функциональном JavaScript

Свёртка не тьюринг-полна, она как раз и гарантирует тотальность при обработке конечных данных тотальной функцией. В этом её преимущество и ограничение: за пределы КС-языков со свёрткой уже не выйти, нужна машина Тьюринга, цикл while или генерация данных для свёртки.

А вот что вы понимаете под множеством
(method(A), predicate(method(A))) и замкнутыми путями я не очень понял.

Если рассматриваемый язык строго типизирован и все функции чистые, то

data : A
method : A -> A
predicate : A -> Bool

а значит, область значения функции method и область определения предиката совпадают.

Описанный вами паттерн это полноценный вычислитель, в котором анаморфизмом является итератор, а катаморфизмом — функция dropWhile, определяемая через свёртку:

head . dropWhile predicate . iterate method $ initial

Тотальность тут, увы, ничем не гарантирована, зато есть тьюринг-полнота. Если в качестве типа A взять некоторое окружение, то получим модель императивной программы в чистом функциональном исполнении.

Ну, и для полноты картины, стоит сказать, что эту модель можно свести к поиску наименьшей неподвижной точки слегка модифицированной функции method. А именно оператор фиксированной точки (Y-комбинатор) делает нетипизированное лямбда-исчисление тьюринг-полным. С этих рассуждений, когда-то и начали Алонзо Чёрч и его ученик Алан Тьюринг.

Использование map и reduce в функциональном JavaScript

Используя свёртку можно построить детерминированный автомат с магазинной памятью, а значит, с его помощью можно распознать и транслировать любую контекстно-свободную грамматику. Вот, например, анализатор языка Дика (правильных скобочных выражений) с использованием левой свёртки:

brackets :: String -> Bool
brackets expr = foldl pda [0] expr == [0]
  where
    pda []     _ = []
    pda (x:xs) c = delta c x ++ xs

    delta '(' 0 = [1,0]
    delta '(' 1 = [1,1]
    delta ')' _ = []

Это Haskell, на JS можно написать как-то так:

function brackets(s) {
  return s.reduce(f,[0])

  function f(stack,x) {
    return stack == [] ? [] : stack.concat(delta(stack.pop(),x))
  }

  function delta(s,x) {
    if (x == ')') return []
    if (s == 0) return [0,1]
    if (s == 1) return [1, 1]
  }
}

Использование map и reduce в функциональном JavaScript

В рамках чистого ФП функции map и filter реализуются через reduce, так что ваш вопрос сводится к такому: какой класс задач можно решить с помощью свёртки (катаморфизма)? Не претендуя на исчерпывающий и математически точный ответ можно сказать, что одна только свёртка позволяет обрабатывать конечные индуктивные данные. С её помощью можно построить конечный автомат, или автомат с магазинной памятью. Они не эквивалентны машине Тьюринга, но способны вычислять примитивно рекурсивные функции. На вскидку, с помощью reduce и без изменяемых состояний можно построить программу, эквивалентную программе, использующей только цикл for (точнее, foreach, C-шный for это переодетый while). Это хороший и полезный класс программ, гарантирующий тотальность. Для реализации цикла while потребуется ленивый генератор данных для свёртки: анаморфизм. Их композиция — хиломорфизм, уже Тьюринг полна. Повторюсь, все эти рассуждения имеют смысл при отсутствии изменяемого состояния, так как если сворачивающая функция может получить доступ к ссылке на сворачиваемые данные и изменять их на ходу, то это уже не катаморфизм, а бардак. В таком случае ответ на ваш вопрос будет таким: да, свёртка тьюринг-полна, но она тут ни при чём, это просто цикл. Кстати, в С# изменять итератор цикла foreach запрещено на уровне языка.

Использование map и reduce в функциональном JavaScript

Увы, о композиции в С-подобном синтаксисе говорить очень неудобно. А рассуждать о её изяществе даже опасно, засмеют и композицию заругают. Недаром у Lisp, Haskell, F# и J такой "странный" синтакис :)