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

Хочется потихоньку раздавать эти долги и заодно наполнять блог. Сегодня это будет публикация про языки программирования от 1981 года. Наткнулся на нее, когда читал другой текст про историю языка Haskell: A History of Haskell: Being Lazy With Class. Этот пейпер написан в очень легком стиле и рассказывает нам об эволюции мысли в области языков программирования в районе 70-90-х годов. Именно там я наткнулся на упоминание текста — The Semantic Elegance of Applicative Languages.

Эта работа считается достаточно влиятельной, ее часто цитирует. Она была презентована на конференции FPCA (Functional Programming Languages and Computer Architecture) в 1981 году Дэвидом Тернером.

Тернер известен тем, что он автор языка SASL: первого функционального языка программирования с ленивыми вычислениями.

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

Основная идея

Раз уж я взялся написать пост по этому пейперу, то надо закончить.

Некоторые считают, что в этой работе приятный слог. Не буду спорить, читать ее достаточно просто.

Сама работа рассматривает реализацию алгоритма перечисления всех парафиновых молекул размера n, используя некий аппликативный язык KRC.

Если мы с вами попробуем осознать семантическую элегантность аппликативных языков вместе с Тернером, то получится что-то следующее.

Аппликативные языки позволяют прийти к рабочему решению за более короткое количество шагов

Что ж, в целом, спорить о том, что программы написанные на Haskell короче программ на Java (или на Fortran) не приходится. При этом Тернер говорит, что первое решение может быть очень неэффективным или даже экспоненциальным. Тут тоже вопросов нет, современная практика это подтверждает.

Аппликативные языки поддерживают разделение ответственности

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

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

Законы и абстракции

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

Сам этот пункт скорее интересен тем, что в аппликативных языках паттерны чаще приходят из математики и имеют доказанные свойства. Самый известный пример — монады. В отличие от, например, классического объектно-ориентированного программирования, где паттерны скорее приходят из опыта и наблюдений некоторых отдельных людей.

Интересные факты

Несколько интересных фактов, которые я узнал из работы.

Синтаксис генераторов и гардов

Знакомый нам по разным языкам (haskell, scala и тд) синтаксис для обработки списков (и итераторов) оказывается пришел к нам из теории множеств, а именно из ZF-теории.

Пример приведенный в работе описывает генерацию перестановок списка чисел от 1 до n:

partitions 0 = [[]]
partitions n = {i:p | i <- [1..n]}
                      p <- partitions(n-i)}

Мемоизация

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

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

para 0 = ["H"]
para n = paralist n
paralist = map genpara [1..n]
genpara = ...

В данном примере genpara перечисляет парафиновые молекулы, ее реализация не важна — это именно так функция, которую мы мемоизируем.

Ключ к пониманию этого сниппета кода в том, что у paralist нет аргументов. По сути это ленивый map по бесконечному списку. То есть в коде ниже мы просто достаем n-ый элемент из списка paralist, в результате этот список вычисляется ровно до n-ого элемента.

para n = paralist n

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

Пост-скриптум

Не могу не использовать случай, чтобы не упомянуть эссе: Teaching programming in post-linean age. Оно очень короткое и его главный тезис: парадигмы программирования безвозвратно ушли и большинство языков является комбинацией фич и идей.

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

Если вам хочется послушать больше мыслей про развитие современных языков программирования, то можно посмотреть доклад Виталия Брагилевского про будущее языков программирования: