Периодически я натыкаюсь на языки программирования, которые настолько самобытны, что меняют моё представление о коде в целом. В этой статье я хотел бы поделиться некоторыми из самых любимых моих находок.
Здесь вы не найдёте устаревшего посыла «функциональное программирование спасёт мир!»; мой список состоит из куда менее популярных наименований. Готов поспорить, многие из читателей вообще не слышали о большинстве языков и парадигм, о которых пойдёт речь, так что надеюсь, вам будет так же интересно с ними разбираться, как и мне.
Примечание: прошу заметить, что у меня очень ограниченный опыт работы с большей частью этих языков: идеи, на которых они строятся, кажутся мне заслуживающими внимания, но экспертом я назвать себя не могу. Поэтому, пожалуйста, указывайте на ошибки и предлагайте исправления. А если найдёте какие-то ещё идеи и парадигмы, которые я пропустил, делитесь!
Примеры языков: ANI, Plaid
Давайте начнём с того, что по-настоящему потрясает воображение: существуют такие языки, в которых по умолчанию предполагается конкурентность. То есть все строки кода выполняются параллельно друг другу!
Например, представьте, что вы написали три строки кода — А, В и С.
В большинстве языков сначала будет выполняться А, затем В, а потом уже С. Но в ANI и ему подобных A, B и C будут выполнены одновременно!
В ANI контроль потока и выстраивание строк кода в определённом порядке — это только побочный эффект зависимостей, прописанных между разными строками. Скажем, если в В содержится отсылка к переменной, которая определяется в А, то А и С будут выполняться в одно и то же время, а В — позже, когда завершится А.
Давайте разберём пример из ANI. Как говорится в туториале, программы, написанные на ANI, состоят из каналов (pipes) и задвижек (latches), с помощью которых происходит управление потоками данных. В этом необычном синтаксисе не так просто разобраться, а сам язык кажется мёртвым, но концепты он предлагает весьма интересные.
Вот пример реализации «Hello, world!» на ANI:
Используя принятые в ANI термины, мы отправляем объект «Hello, world!» (текст) в поток std.out. А что если отправить еще какой-нибудь текст в std.out?
Обе эти строки будут выполняться параллельно, поэтому текст выведется на консоль в произвольной последовательности. Теперь посмотрим, что будет, если включить переменную в одну строку и отсылку к ней — в другую.
Первая строка объявляет задвижка (что-то вроде переменной) под названием s, в которой содержится текст; вторая строка отправляет в s текст «Hello, world!»; третья — «открывает» задвижку на s и отправляет содержимое в std.out. Здесь вы можете наблюдать, как подспудно происходит упорядочивание в ANI: так как каждая строка зависит от предыдущей, строки кода будут выполняться в той последовательности, в которой они написаны.
Язык Plaid также, согласно заверениям создателей, поддерживает конкурентность по умолчанию, однако использует при этом модель разрешений (подробнее в этой статье) для настройки контроля потока. Plaid также экспериментирует и с другими интересными концепциями, например, программирование, ориентированное на состояние типа, где на первый план выходят изменения состояния: объекты определяются не как классы, а как серии состояний и переходов, которые может отслеживать компилятор. Этот подход представляется мне занятным — время в нём определяется как языковой конструкт первого класса. Rich Hickey писал об этом в своей статье Are we there yet.
Многоядерность сейчас на подъёме, и добиться конкурентности до сих пор сложнее, чем хотелось бы. ANI и Plaid предлагают нетривиальный подход к проблеме, который мог бы улучшить производительность в разы. Вопрос только в том, сделает ли принцип «параллелизм по умолчанию» управление конкурентностью проще.
Примеры языков: Idris, Agda, Coq
Вы, наверное, привыкли к системам, представленным в таких языках, как C и Java, где компилятор может определять разновидность переменной — целое число, список или текст. Но что если он мог бы определять переменную как «положительное целое число», «список из двух пунктов» или «текст, который является палиндромом»?
На этой идее строятся языки, которые поддерживают зависимые типы: вы можете задавать типы, которые будут проверять значение ваших переменных на стадии компиляции. Библиотека shapeless для Scala в качестве эксперимента добавила частичную (иными словами, не совсем ещё доработанную) поддержку зависимых типов в Scala и предлагает простой способ ознакомиться с примерами.
Вот как объявить Vector, который содержит значения 1, 2, 3 в библиотеке shapeless:
Таким образом, создаётся переменная 11, в сигнатуре которой указано не только то, что это Vector, который содержит Ints, но и то, что длина вектора — 3. Компилятор может использовать эту информацию, что отлавливать ошибки. Давайте применим метод vAdd к вектору, чтобы произвести попарное сложение двух векторов:
В приведённом примере всё работает нормально, так как система знает: у обоих векторов длина 3. Однако если бы мы попытались применить vAdd к векторам разной длины, то получили бы ошибку уже на стадии компиляции, ещё до выполнения!
Shapeless — отличная библиотека, но, насколько мне известно, ещё немного сыроватая: поддерживает только небольшой набор зависимых типов, даёт тяжеловесный код и сигнатуры. Idris же делает типы объектом первого класса в языке программирования, вследствие чего система зависимых типов получается аккуратнее и мощнее. Для детального сравнения почитайте Scala vs Idris: Dependent Types, Now and in the Future.
Формальные методы верификации существуют уже давно, но зачастую оказываются слишком громоздкими, чтобы программисты общего профиля находили их полезными. Зависимые типы в языках вроде Idris, а в будущем, возможно, и Scala, могут предоставить более компактные и практичные альтернативы, которые существенно расширят возможности системы в том, что касается выявления ошибок. Конечно, никакая система зависимых типов не способна отловить все ошибки, которые возникают из-за ограничений, накладываемых проблемой остановки. Однако при разумном применении зависимые типы могут стать значительным скачком для статических систем типов.
Примеры языков: Forth, cat, joy
Никогда не задумывались, как это было бы — писать код без переменных и применения функций? Я тоже нет. Но, очевидно, какие-то ребята задумались и в результате изобрели конкатенативное программирование. Идея в том, что язык состоит из функций, которые добавляют данные в стек или же выбрасывают данные из стека; программы строятся практически исключительно с помощью функциональной композиции (конкатенация — это и есть композиция).
Звучит как-то туманно, поэтому давайте возьмём простой пример из cat:
Здесь мы добавляем в стек два числа, а затем вызываем функцию +, которая выбрасывает оба из стека и добавляет туда их сумму. The output этого кода — 5. Теперь рассмотрим пример чуть поинтереснее:
Разберём каждую строку:
За более подробным введением вы можете обратиться к The Joy of Concatenative Languages.
Этот стиль программирования отличается некоторыми интересными свойствами: программы можно расщеплять и объединять бесчисленными способами, чтобы создавать новые программы. Стоит также отметить сжатый синтаксис (еще более сжатый, чем у LISP), который делает программы крайне лаконичными и мощную поддержку метапрограммирования. На мой взгляд, конкатенативное программирование даёт много пищи для размышлений, но вот практичность его вызывает сомнения. Представляется, что при таком подходе нужно постоянно помнить или представлять себе текущее состояние стека, вместо того чтобы восстанавливать его по названиям переменных в коде, вследствие чего становится сложнее принимать решения
Примеры языков: Prolog, SQL
Декларативное программирование появилось много лет назад, но большинству программистов эта концепция до сих пор не знакома. Суть в следующем: в большей части распространённых языков вы описываете, как решить проблему; в декларативных же языках вы просто указываете, к какому результату хотите прийти, а язык уже сам определяет, что для этого нужно сделать.
Например, если вы с нуля создаете алгоритм сортировки на С, то вам нужно прописать инструкции для сортировки слиянием, в которых будет пошагово расписано, как рекурсивно разделить все данные на две части, а потом объединить в соответствующем сортировке порядке; вот пример. Если вы сортируете числа в декларативном языке вроде Prolog, вместо всего этого вы прописываете желаемый результат: «Я хочу получить список из тех же составляющих, но число на позиции i должно быть меньше или равно числу на позиции i+1». Сравните решение на С, о котором шла речь выше, с этим кодом из Prolog:
Если вы когда-нибудь пользовались SQL, то у вас есть опыт декларативного программирования, пусть даже вы, возможно, об этом и не догадывались. Когда вы отправляете запрос типа select X from Y where Z, вы описываете типа данных, которые хотите получить; как выполнять этот запрос решает сам движок базы данных. В большинстве баз данных вы можете применить команду explain, чтобы посмотреть на схему выполнения и получить представление, как все происходило за кулисами.
Красота декларативных языков в том, что они позволяют вам работать на более высоком уровне абстракции. Ваше дело — прописать спецификации для искомого вывода. Например, код для простой игры судоку в Prolog просто указывает, как должны выглядеть горизонтальный, вертикальный и диагональный ряды решённой головоломки:
Вот как запустить игру, описанную выше:
К сожалению, у этого метода есть и недостатки: декларативные языки часто сталкиваются с проблемами производительности. Незамысловатый алгоритм сортировки, который мы приводили выше, скорее всего даст O(n!); в игре судоку поиск производится силовыми методами, большинству разработчиков приходится включать в подсистему дополнительные намёки и индексы, чтобы избежать затратных и неэффективных планов при выполнении SQL запросов.
Пример языка: Aurora
Язык Aurora — образчик символического программирования. Код, который вы пишете на нём и ему подобных, помимо простого текста может включать в себя изображения, математические уравнения, графики и так далее. Это позволяет вам описывать и работать с самыми разнообразными данными в их оригинальном формате, вместо того, чтобы переводить всё в текст. Кроме того, Aurora — в высшей степени интерактивный язык, который сразу же показывает вам результат после каждой строки кода, прямо как REPL на стероидах.
Язык Aurora был создан Chris Granger, авторству которого принадлежит также Light Table IDE. Он говорит о мотивации, которая побудила его изобрести Aurora, в своём посте Toward a better programming. Он преследовал такие цели, как сделать программирование более наглядным, прямым и свести случайное усложнение к минимуму. Если хотите узнать больше, обязательно ознакомьтесь с материалами от Bret Victor — Inventing on Principle, Media for Thinking the Unthinkable и Learnable Programming.
Пример языка: Wolfram
Как и описанный выше Aurora, язык Wolfram также основывается на принципах символического программирования. Но символический слой — это всего лишь способ обеспечить стабильный интерфейс для того, что составляет ядро — то есть программирование, основанное на знаниях, широкий круг встроенных в язык библиотек, алгоритмов и данных. Благодаря такому подходу, можно легко и просто делать что угодно: строить графики на базе статистики по вашем аккаунту на Facebook, редактировать картинки, смотреть погоду, обрабатывать запросы на естественном языке, прокладывать маршруты на карте, решать уравнения и так далее.
Я полагаю, что из всех существующих языков у Wolfram самая обширная «стандартная библиотека» и набор данных. Также меня очень вдохновляет мысль, что связь с Интернет-сообществом становится неотъемлемой частью процесса написания кода: это напоминает IDE, где функция автозаполнения осуществляет поиск в Google. Интересно будет проверить, правда ли символическая модель программирования настолько гибкий, как утверждает Wolfram, и может ли она должным образом воспользоваться всеми этими данными.
Здесь вы не найдёте устаревшего посыла «функциональное программирование спасёт мир!»; мой список состоит из куда менее популярных наименований. Готов поспорить, многие из читателей вообще не слышали о большинстве языков и парадигм, о которых пойдёт речь, так что надеюсь, вам будет так же интересно с ними разбираться, как и мне.
Примечание: прошу заметить, что у меня очень ограниченный опыт работы с большей частью этих языков: идеи, на которых они строятся, кажутся мне заслуживающими внимания, но экспертом я назвать себя не могу. Поэтому, пожалуйста, указывайте на ошибки и предлагайте исправления. А если найдёте какие-то ещё идеи и парадигмы, которые я пропустил, делитесь!
Конкурентность по умолчанию
Примеры языков: ANI, Plaid
Давайте начнём с того, что по-настоящему потрясает воображение: существуют такие языки, в которых по умолчанию предполагается конкурентность. То есть все строки кода выполняются параллельно друг другу!
Например, представьте, что вы написали три строки кода — А, В и С.
A;
B;
C;В большинстве языков сначала будет выполняться А, затем В, а потом уже С. Но в ANI и ему подобных A, B и C будут выполнены одновременно!
В ANI контроль потока и выстраивание строк кода в определённом порядке — это только побочный эффект зависимостей, прописанных между разными строками. Скажем, если в В содержится отсылка к переменной, которая определяется в А, то А и С будут выполняться в одно и то же время, а В — позже, когда завершится А.
Давайте разберём пример из ANI. Как говорится в туториале, программы, написанные на ANI, состоят из каналов (pipes) и задвижек (latches), с помощью которых происходит управление потоками данных. В этом необычном синтаксисе не так просто разобраться, а сам язык кажется мёртвым, но концепты он предлагает весьма интересные.
Вот пример реализации «Hello, world!» на ANI:
"Hello, World!" ->std.outИспользуя принятые в ANI термины, мы отправляем объект «Hello, world!» (текст) в поток std.out. А что если отправить еще какой-нибудь текст в std.out?
"Hello, World!" ->std.out
"Goodbye, World!" ->std.outОбе эти строки будут выполняться параллельно, поэтому текст выведется на консоль в произвольной последовательности. Теперь посмотрим, что будет, если включить переменную в одну строку и отсылку к ней — в другую.
s = [string\];
"Hello, World!" ->s;
\s ->std.out;Первая строка объявляет задвижка (что-то вроде переменной) под названием s, в которой содержится текст; вторая строка отправляет в s текст «Hello, world!»; третья — «открывает» задвижку на s и отправляет содержимое в std.out. Здесь вы можете наблюдать, как подспудно происходит упорядочивание в ANI: так как каждая строка зависит от предыдущей, строки кода будут выполняться в той последовательности, в которой они написаны.
Язык Plaid также, согласно заверениям создателей, поддерживает конкурентность по умолчанию, однако использует при этом модель разрешений (подробнее в этой статье) для настройки контроля потока. Plaid также экспериментирует и с другими интересными концепциями, например, программирование, ориентированное на состояние типа, где на первый план выходят изменения состояния: объекты определяются не как классы, а как серии состояний и переходов, которые может отслеживать компилятор. Этот подход представляется мне занятным — время в нём определяется как языковой конструкт первого класса. Rich Hickey писал об этом в своей статье Are we there yet.
Многоядерность сейчас на подъёме, и добиться конкурентности до сих пор сложнее, чем хотелось бы. ANI и Plaid предлагают нетривиальный подход к проблеме, который мог бы улучшить производительность в разы. Вопрос только в том, сделает ли принцип «параллелизм по умолчанию» управление конкурентностью проще.
Зависимые типы
Примеры языков: Idris, Agda, Coq
Вы, наверное, привыкли к системам, представленным в таких языках, как C и Java, где компилятор может определять разновидность переменной — целое число, список или текст. Но что если он мог бы определять переменную как «положительное целое число», «список из двух пунктов» или «текст, который является палиндромом»?
На этой идее строятся языки, которые поддерживают зависимые типы: вы можете задавать типы, которые будут проверять значение ваших переменных на стадии компиляции. Библиотека shapeless для Scala в качестве эксперимента добавила частичную (иными словами, не совсем ещё доработанную) поддержку зависимых типов в Scala и предлагает простой способ ознакомиться с примерами.
Вот как объявить Vector, который содержит значения 1, 2, 3 в библиотеке shapeless:
val l1 = 1 :#: 2 :#: 3 :#: VNilТаким образом, создаётся переменная 11, в сигнатуре которой указано не только то, что это Vector, который содержит Ints, но и то, что длина вектора — 3. Компилятор может использовать эту информацию, что отлавливать ошибки. Давайте применим метод vAdd к вектору, чтобы произвести попарное сложение двух векторов:
val l1 = 1 :#: 2 :#: 3 :#: VNil
val l2 = 1 :#: 2 :#: 3 :#: VNil
val l3 = l1 vAdd l2
// Result: l3 = 2 :#: 4 :#: 6 :#: VNilВ приведённом примере всё работает нормально, так как система знает: у обоих векторов длина 3. Однако если бы мы попытались применить vAdd к векторам разной длины, то получили бы ошибку уже на стадии компиляции, ещё до выполнения!
val l1 = 1 :#: 2 :#: 3 :#: VNil
val l2 = 1 :#: 2 :#: VNil
val l3 = l1 vAdd l2
// Result: a *compile* error because you can't pairwise add vectors
// of different lengths!Shapeless — отличная библиотека, но, насколько мне известно, ещё немного сыроватая: поддерживает только небольшой набор зависимых типов, даёт тяжеловесный код и сигнатуры. Idris же делает типы объектом первого класса в языке программирования, вследствие чего система зависимых типов получается аккуратнее и мощнее. Для детального сравнения почитайте Scala vs Idris: Dependent Types, Now and in the Future.
Формальные методы верификации существуют уже давно, но зачастую оказываются слишком громоздкими, чтобы программисты общего профиля находили их полезными. Зависимые типы в языках вроде Idris, а в будущем, возможно, и Scala, могут предоставить более компактные и практичные альтернативы, которые существенно расширят возможности системы в том, что касается выявления ошибок. Конечно, никакая система зависимых типов не способна отловить все ошибки, которые возникают из-за ограничений, накладываемых проблемой остановки. Однако при разумном применении зависимые типы могут стать значительным скачком для статических систем типов.
Конкатенативное программирование
Примеры языков: Forth, cat, joy
Никогда не задумывались, как это было бы — писать код без переменных и применения функций? Я тоже нет. Но, очевидно, какие-то ребята задумались и в результате изобрели конкатенативное программирование. Идея в том, что язык состоит из функций, которые добавляют данные в стек или же выбрасывают данные из стека; программы строятся практически исключительно с помощью функциональной композиции (конкатенация — это и есть композиция).
Звучит как-то туманно, поэтому давайте возьмём простой пример из cat:
2 3 +Здесь мы добавляем в стек два числа, а затем вызываем функцию +, которая выбрасывает оба из стека и добавляет туда их сумму. The output этого кода — 5. Теперь рассмотрим пример чуть поинтереснее:
def foo {
10 <
[ 0 ]
[ 42 ]
if
}
20
fooРазберём каждую строку:
- Сначала объявим функцию foo. Обратите внимание на то, что в cat параметры ввода функций не указываются: все параметры считываются со стека.
- foo вызывает функцию <, которая добавляет в стек первое число, сравнивает его с 10 и добавляет значение True или False.
- Далее мы добавляем в стек значения 0 и 42, причём заключаем их в скобки, чтобы они добавились без прохождения проверки. Причина в том, что они будут использоваться как ветви then и else соответственно при вызове функции «если» в следующей строке.
- Функция if выбрасывает из стека три вещи: логическое условие, ветвь then и ветвь else.
- Наконец, мы добавляем число 20 в стек и вызываем функцию foo.
- В конечном итоге мы получаем число 42.
За более подробным введением вы можете обратиться к The Joy of Concatenative Languages.
Этот стиль программирования отличается некоторыми интересными свойствами: программы можно расщеплять и объединять бесчисленными способами, чтобы создавать новые программы. Стоит также отметить сжатый синтаксис (еще более сжатый, чем у LISP), который делает программы крайне лаконичными и мощную поддержку метапрограммирования. На мой взгляд, конкатенативное программирование даёт много пищи для размышлений, но вот практичность его вызывает сомнения. Представляется, что при таком подходе нужно постоянно помнить или представлять себе текущее состояние стека, вместо того чтобы восстанавливать его по названиям переменных в коде, вследствие чего становится сложнее принимать решения
Декларативное программирование
Примеры языков: Prolog, SQL
Декларативное программирование появилось много лет назад, но большинству программистов эта концепция до сих пор не знакома. Суть в следующем: в большей части распространённых языков вы описываете, как решить проблему; в декларативных же языках вы просто указываете, к какому результату хотите прийти, а язык уже сам определяет, что для этого нужно сделать.
Например, если вы с нуля создаете алгоритм сортировки на С, то вам нужно прописать инструкции для сортировки слиянием, в которых будет пошагово расписано, как рекурсивно разделить все данные на две части, а потом объединить в соответствующем сортировке порядке; вот пример. Если вы сортируете числа в декларативном языке вроде Prolog, вместо всего этого вы прописываете желаемый результат: «Я хочу получить список из тех же составляющих, но число на позиции i должно быть меньше или равно числу на позиции i+1». Сравните решение на С, о котором шла речь выше, с этим кодом из Prolog:
sort_list(Input, Output) :-
permutation(Input, Output),
check_order(Output).
check_order([]).
check_order([Head]).
check_order([First, Second | Tail]) :-
First =< Second,
check_order([Second | Tail]).Если вы когда-нибудь пользовались SQL, то у вас есть опыт декларативного программирования, пусть даже вы, возможно, об этом и не догадывались. Когда вы отправляете запрос типа select X from Y where Z, вы описываете типа данных, которые хотите получить; как выполнять этот запрос решает сам движок базы данных. В большинстве баз данных вы можете применить команду explain, чтобы посмотреть на схему выполнения и получить представление, как все происходило за кулисами.
Красота декларативных языков в том, что они позволяют вам работать на более высоком уровне абстракции. Ваше дело — прописать спецификации для искомого вывода. Например, код для простой игры судоку в Prolog просто указывает, как должны выглядеть горизонтальный, вертикальный и диагональный ряды решённой головоломки:
sudoku(Puzzle, Solution) :-
Solution = Puzzle,
Puzzle = [S11, S12, S13, S14,
S21, S22, S23, S24,
S31, S32, S33, S34,
S41, S42, S43, S44],
fd_domain(Solution, 1, 4),
Row1 = [S11, S12, S13, S14],
Row2 = [S21, S22, S23, S24],
Row3 = [S31, S32, S33, S34],
Row4 = [S41, S42, S43, S44],
Col1 = [S11, S21, S31, S41],
Col2 = [S12, S22, S32, S42],
Col3 = [S13, S23, S33, S43],
Col4 = [S14, S24, S34, S44],
Square1 = [S11, S12, S21, S22],
Square2 = [S13, S14, S23, S24],
Square3 = [S31, S32, S41, S42],
Square4 = [S33, S34, S43, S44],
valid([Row1, Row2, Row3, Row4,
Col1, Col2, Col3, Col4,
Square1, Square2, Square3, Square4]).
valid([]).
valid([Head | Tail]) :- fd_all_different(Head), valid(Tail).Вот как запустить игру, описанную выше:
| ?- sudoku([_, _, 2, 3,
_, _, _, _,
_, _, _, _,
3, 4, _, _],
Solution).
S = [4,1,2,3,2,3,4,1,1,2,3,4,3,4,1,2]К сожалению, у этого метода есть и недостатки: декларативные языки часто сталкиваются с проблемами производительности. Незамысловатый алгоритм сортировки, который мы приводили выше, скорее всего даст O(n!); в игре судоку поиск производится силовыми методами, большинству разработчиков приходится включать в подсистему дополнительные намёки и индексы, чтобы избежать затратных и неэффективных планов при выполнении SQL запросов.
Символическое программирование
Пример языка: Aurora
Язык Aurora — образчик символического программирования. Код, который вы пишете на нём и ему подобных, помимо простого текста может включать в себя изображения, математические уравнения, графики и так далее. Это позволяет вам описывать и работать с самыми разнообразными данными в их оригинальном формате, вместо того, чтобы переводить всё в текст. Кроме того, Aurora — в высшей степени интерактивный язык, который сразу же показывает вам результат после каждой строки кода, прямо как REPL на стероидах.
Язык Aurora был создан Chris Granger, авторству которого принадлежит также Light Table IDE. Он говорит о мотивации, которая побудила его изобрести Aurora, в своём посте Toward a better programming. Он преследовал такие цели, как сделать программирование более наглядным, прямым и свести случайное усложнение к минимуму. Если хотите узнать больше, обязательно ознакомьтесь с материалами от Bret Victor — Inventing on Principle, Media for Thinking the Unthinkable и Learnable Programming.
Программирование, основанное на знаниях
Пример языка: Wolfram
Как и описанный выше Aurora, язык Wolfram также основывается на принципах символического программирования. Но символический слой — это всего лишь способ обеспечить стабильный интерфейс для того, что составляет ядро — то есть программирование, основанное на знаниях, широкий круг встроенных в язык библиотек, алгоритмов и данных. Благодаря такому подходу, можно легко и просто делать что угодно: строить графики на базе статистики по вашем аккаунту на Facebook, редактировать картинки, смотреть погоду, обрабатывать запросы на естественном языке, прокладывать маршруты на карте, решать уравнения и так далее.
Я полагаю, что из всех существующих языков у Wolfram самая обширная «стандартная библиотека» и набор данных. Также меня очень вдохновляет мысль, что связь с Интернет-сообществом становится неотъемлемой частью процесса написания кода: это напоминает IDE, где функция автозаполнения осуществляет поиск в Google. Интересно будет проверить, правда ли символическая модель программирования настолько гибкий, как утверждает Wolfram, и может ли она должным образом воспользоваться всеми этими данными.
Поделиться с друзьями
mayorovp
… а теперь сравните время выполнения :-)
Декларативное программирование — замечательная парадигма, но не надо объяснять ее на основе языка Prolog.
MacIn
Я попрошу! Пролог замечательно подходит для описания такой парадигмы. Мозг необычностью подхода так сносит напрочь точно.
Idot
А если я не знаю решение, но очень хочу найти, то как быть?
fireSparrow
Решение и не надо знать, в этом и весь смысл, чтобы компьютер его сам нашёл.
В коде программы достаточно описать те закономерности, которым должно удовлетворять решение, чтобы считаться правильным. А уж конкретные цифры под эти закономерности компьютер подбирает сам.
Idot
Можно ли пример кода, как выглядит "задача коммивояжера" на ПроЛоге?
fireSparrow
Сам я на прологе не пишу, но беглое гугление по запросу «prolog задача коммивояжера» выдаёт множество ссылок.
Вот один из найденных примеров:
/**************************************************************
Коммивояжёр. Поиск в глубину.
**************************************************************/
domains ss = string*
database - путь
путь(string,integer,string)
оценка(ss,integer)
predicates
оптим_маршрут(ss,integer)
nondeterm маршруты(string,integer,ss,integer)
nondeterm вариант(string,integer,string,ss,integer)
nondeterm участок(string,integer,string)
уник(ss,ss,integer)
удалить(string,ss,ss)
принадлеж(string,ss)
goal
оптим_маршрут(Маршрут,Длина).
clauses
оптим_маршрут(Маршрут,Длина):-
путь(Начало,_,_),!,
findall(Город,путь(Город,_,_),Города),
уник(Города,_,Количество),
маршруты(Начало,Количество,Маршрут,Длина),!.
маршруты(Начало,Количество,_,_):-
вариант(Начало,Количество,Начало,[Начало],0),fail.
маршруты(_,_,Маршрут,Длина):-
оценка(Маршрут,Длина).
вариант(Начало,0,От,Маршрут,Длина):-
участок(От,Участок,Начало),
Длина1=Длина+Участок,
not(оценка(_,_)),
assert(оценка([Начало|Маршрут],Длина1)).
вариант(Начало,0,От,Маршрут,Длина):-
участок(От,Участок,Начало),
Длина1=Длина+Участок,
оценка(_,Длина0),Длина1<Длина0,
retract(оценка(_,Длина0)),
assert(оценка([Начало|Маршрут],Длина1)).
вариант(Начало,К,От,Маршрут,Длина):-К>0,
участок(От,Участок,До),
not(принадлеж(До,Маршрут)),
Длина1=Участок+Длина, К1=К-1,
вариант(Начало,К1,До,[До|Маршрут],Длина1).
уник([Э|Х],[Э|Х2],Число):-удалить(Э,Х,Х1),!,
уник(Х1,Х2,Число1),Число = Число1+1.
уник([],[],0).
удалить(Э,[Э|Х],Х1):-!,удалить(Э,Х,Х1).
удалить(Э,[А|Х],[А|Х1]):-!,удалить(Э,Х,Х1).
удалить(_,[],[]).
участок(От,Длин,До):-путь(От,Длин,До).
участок(От,Длин,До):-путь(До,Длин,От).
принадлеж(Город,[Город|_]):-!.
принадлеж(Город,[_|Города]):-принадлеж(Город,Города).
путь("Курск",12,"Орёл").
путь("Курск",120,"Магадан").
путь("Курск",40,"Азов").
путь("Магадан",110,"Орёл").
путь("Магадан",52,"Колыма").
путь("Орёл",32,"Азов").
путь("Орёл",105,"Колыма").
путь("Азов",112,"Колыма").
mayorovp
Судя по постоянным использованиям retract, assert и оператора
!— вы привели императивный код, но никак не простое описание закономерностей, которым должно удовлетворять решение.Собственно, именно это и является проблемой Пролога — при изначальной красивой идее декларативности любая попытка оптимизации вырождается в императивный код с кривым синтаксисом.
Danov
Приведенный пример перегруженный. Можно проще написать. Нужна пара строчек permutation
permute([], []).
permute([X|Rest], L) :- permute(Rest, L1).
для генерации вариантов, затем описание графа дорого в виде списка
table([way(1,2,10), way(2,3,30),....]).
и далее основное правило для поиска минимума.
К сожалению, под рукой нет Prolog. Попробовал онлайн — не получилось с ходу разобраться.
PS: преимущество пролога как раз в скорости написания кода, а недостаток — в скорости перебора. Но были версии движка со свтроенной оптимизацией перебора.
vanxant
Программа на прологе содержит три основных секции:
1. Секцию фактов, оно же «дано», по сути константы/база данных. «Коля — мальчик», например.
2. Секцию правил вывода, в форме «если верно А и Б, то верно В». Скажем, «Оля любит мальчиков».
3. Секцию целей. Что, собственно, нужно найти. Условное «Г», которое нужно доказать или опровергнуть, но не вообще, а для конкретно заданных значений А, Б и т.д. из пункта 1. «Любит ли Оля Колю?»
Все вот эти А, Б, В, Г и т.д. по-умному называются предикатами, т.е. переменными или функциями, возвращающими тип bool (т.е. истина или ложь). А сам язык пролог по сути занимается доказыванием математических теорем. Есть такой алгоритм бэктрекинга, вот собственно его рантайм пролога и исполняет.
vanxant
На практике получается вот что:
— Первая секция («фактов») тривиальна;
— Третья («целей»), в общем, тоже; это или конструкция goal, или просто восклицательный знак после выражения, типа «приехали».
А вот секция правил вывода — это чистейший вынос мозга. Ну вот представьте, что у вас есть «дано» в шахматах (начальная расстановка фигур) и условия «надо» (правила мата). Только вам нужно придумать не алгоритм выигрывания, а правила, по которым должны ходить ваши фигуры — так, чтобы в итоге выиграть. «Если ты ладья, слева-сзади твой ферзь, а справа чужая пешка, то...» И эти правила, в первом приближении, работают одновременно (в прологе есть порядок выполнения, но в первом приближении так).
Причем это не только для программистов вынос мозга, для математиков тоже. В отличие от теорем, здесь есть побочные эффекты, ну там ввод-вывод, запрос даты-времени и вот это всё. В этом ключевое отличие от модной функциональщины.
В итоге имеем красивую идею с отлично проработанным математическим бэкграундом… и полное отсутствие программистов, согласных на этом писать.
Pakos
Мы писали когда-то лабораторку (нужно было взять пример из методички и дополнить своими правилами). Итог — пришлось всё переписать с нуля. т.к. написанный код "экспертной системы" при добавлении новых правил разваливался и костыли не помогали, а там было всего десяток признаков и пяток ответов. Вот такой он, Пролог.
PS. Автору
l1?
Femistoklov
DrPass
Это не потрясает воображение. Это скорее удивляет. Т.к. практического смысла в этом мало, параллелизм в программировании нужен не на уровне команд, а на уровне последовательностей команд. А авторы этих экзотических зверушек заставляют программиста тратить массу времени на то, чтобы вручную задавать эти самые последовательности команд, то, что у более привычных языков даётся автоматически.
ПОЛИЗ же. И советские программируемые калькуляторы :)
kozzztik
Так ассемблер же вроде, чего далеко ходить?
Alex_ME
Все-таки большинство процессорных архитектура — регистровые, а не стековые (стек есть, но помимо него — регистры, с которыми в основном и происходит работа).
Примеры чисто стековых — виртуальные машины CLR и JVM, а так же процессор RTX2010, стоявший на зонде Rosetta
0xd34df00d
PostScript ещё можно вспомнить.
Deosis
CLR не чисто стековая.
Alex_ME
В CLR есть регистры?
slovak
DrPass
Там же нет параллелизма «по умолчанию», без необходимости. Порядок следования операторов соответствует и последовательности обработки сигнала в сгенерированном девайсе, всё достаточно традиционно.
daiver19
Да, я теперь смотрю на код и понимаю, как он всё-таки хорош по сравнению со всякими извращениями. Надо было здесь еще Brainfuck или Malbolge для полноты картины упомянуть.
0xd34df00d
Brainfuck можно хотя бы эффективно (за полиномиальное время с приятной степенью) генерировать, на Malbolge кроме как прямым перебором последовательностей символов вроде как не пишут.
neomedved
Так ведь это обычные императивные языки.
nightwolf_du
Параллелизм на уровне команд языка высокого уровня смущает.
Сейчас же все процессоры общего назначения — конвейерные, там и так ассемблерные команды исполняются в параллель, если это возможно.
MacIn
А если у вас многопроцессорная машина?
Вычислительный комплекс с десятками ядер, и это не суперскалярное что-то? Какие-нибудь MIMD.
IvanTamerlan
принципы параллельного исполнения различны. У x86 (и x64) возможность параллельного вычисления вычисляется на лету, т.к. код то последовательный (совместимость с одноядерными).
Следующий уровень — когда в коде задан явный параллелизм, т.е. те же потоки для х86 и х64. Или длинные команды для VLIW.
Так что возможность параллельного исполнения смотрится не только на уровне задачи и кода, но и возможностей процессора. Тем более, что задача может быть решена несколькими способами, причем одни варианты могут быть параллельными, а другие — нет.
Regis
То, как сейчас обычно пишется код, как раз-таки сильно ограничивает возможности оптимизирующих компиляторов — обычно они вынуждены действовать максимально пессимистично, чтобы гарантировать такое наблюдаемое поведение, которое бы соответствовало линейному коду. В случае с языками выше, в теории, оптимизация могла бы быть гораздо более агрессивной — ведь компилятору нужно обеспечить только те отношения, которые явно прописаны в коде.
DrPass
Это, грубо говоря, экономия на спичках за счёт сжигания пачки денег. При таком всегда «параллельном» подходе вы немного облегчаете работу самому дешёвому ресурсу — компилятору (и то, лишь в тех случаях, когда компилятор знает архитектуру исполняющих модулей конкретного процессора, чтобы его максимально загрузить параллельными тасками. Т.е. по сути, применение ограничивается JIT-компиляцией), существенно усложняя работу самому дорогому, программистам. При этом я не слишком ошибусь, если скажу, что узкие места в приложениях сейчас в 99.9999% случаев связаны отнюдь не с недостаточной работой оптимизатора компилятора.
Regis
Я с вами согласен. Если такой подход ведет к усложнению (а с такой парадигмой структура кода наверняка будет сложнее), то для подавляющего числа проектов это не актуально.
Но есть ниши, где принципиально важно писать максимально производительный код. И вот там как раз вполне можно жертвовать простотой языка в пользу скорости и параллелизации.
vintage
Параллелизм на уровне команд к сожалению мало что даёт из-за разных кэшей у разных ядер. Самым эффективным получается исполнение каждым ядром разных задач, не связанных друг с другом по памяти.
sbnur
Напомнило высказывание Ф.Энгельса о персидском языке:
"Зато персидский язык не язык, а настоящая игрушка. Если бы не этот проклятый арабский алфавит, в котором то и дело целые шестерки букв имеют совершенно одинаковый вид и в котором нет гласных, то я бы взялся изучить всю грамматику в течение 48 часов. "
mbait
Ок, проверить, что строковая константа является палиндромом на этапе компиляции можно и на C++. Но как это поддерживается для динамических данных? Каждый раз при изменении значения запускается процедура валидации или код пишется так, что можно доказать, что строка всегда будет оставаться палиндромом? Если первое, то как себя ведёт программа, если контракт нарушен?
0xd34df00d
Вот так, да.
michael_vostrikov
Думаю, для императивных языков допустимо неконсистентное состояние между какими-нибудь точками контроля. Например, проверка может происходить при передаче в функцию, которая принимает "список из двух пунктов", или при ручном приведении типа. Для методов класса можно ввести какой-нибудь атрибут, при наличии которого компилятор будет подставлять проверку типа в конец метода.
CrazyFizik
Было бы хорошо расширить и углубить статью :-)
А чем это отличается от G/LabVIEW? Там конкурентность и параллелизм на уровне синтаксиса. И кстати Alice еще есть. По идее можно было бы наверное и Verilog с VHDL вспомнить, там правда конкурентность ИМХО под вопросом, т.к. определяется таймингами, но зато там чистый параллелизм. Еще наверное можно и Erlang с Go сюда же добавить (ну или хотя бы объяснить разницу, если нет).
Опять таки не упомянули LabVIEW — куда более известная и устоявшаяся штука (в отличии от Авроры, которую походу вообще ради фана делали), а также VisSim, SystemView, и JMCAD, а также все языки стандарта IEC 61131-3 и их потомки(символическое/графическое программирование, наверное наверное самое распространенное для промышленного программирования управления охрененно больших и дорогих штук). Ну Наверное еще и HiAsm и Simulink — правда я хз, можно ли вот эти два считать уже полноценными ЯП или нет.
Требуем
больше хлеба и зрелищьбольше примеров и сравнений!d_olex
Разработка подразумевающая конкурентность по умолчанию, кстати, используется в полный рост, только в немного других областях.
Не так давно я в порядке хобби начал изучать FPGA после over 10 лет программирования на обычных ЯП, и это прям доставляет. Конфигурация для FPGA (программой это назвать наверное нельзя в виду отсутствия концепции потока исполнения) пишется на HDL языках вроде VHDL, Verilog, итд. которые сильно напоминают ANI/Plaid по вашему описанию: «инструкции» в пределах одного блока синхронной логики «исполняются» все и сразу за каждый тик тактового сигнала.
Эти же концепции очень широко используются в системе команд и архитектуре современных процессоров. Почти наверняка у вас есть мобильное устройство с baseband модемом от Qualcomm внутри которого стоит несколько суперскалярных ядер с архитектурой Hexagon (разжиревший DSP который в ходе своего развития вытеснил проц общего назначения), там весь машинный код разбит на блоки по 4 (ЕМНИП) инструкции которые исполняются конкурентно. Процессоры со стековой архитектурой (конкатенативное программирование на низком уровне в сущности) тоже кстати бывают :)
bentall
В конкатенативных языках не упомянут Factor Славы Пестова, который более-менее готов для продакшена и про который во второй книге Семь языков за семь недель глава есть.
Sirikid
Есть ещё один любопытный вариант — Оккам, потенциально подход ANI может быть более эффективным, но Оккам более удобным для программиста.
Положительное целое число не обязательно представлять зависимым типом, по крайней мере в языках с поддержкой АТД. К палиндрому это тоже относится.
То, что перечислил автор, скорее refinement types, чем dependent types.
Лямбда-исчисление больше не катит, переходим на комбинаторную логику %)
Эквивалент кода из поста на Haskell (ленивость then- и else- веток достигается встроенными средствами языка): https://ideone.com/mCRLdF
Sirikid
Блин, опять четную с нечетной перепутал >_<
0xd34df00d
Это немножко читерство. Вы переносите описание свойств структуры данных с её типа на её интерпретацию (
toListв вашем случае).Sirikid
Согласен.
А как написать список, который не сможет не быть палиндромом? Предикат легко: http://lpaste.net/8126944908561874944
worldmind
wolfram когда-то несколько раз пытался пользовать, не очень там гибкий синтаксис, шаг в сторону от описанного в доке и уже не работает, но так или иначе статистические данные можно извлекать, иногда только там их и находишь.
aristarh1970
Название статьи претенциозное и неудачное.
А на фоне признания автора, что он не является экспертом ни в одном из перечисленных языков (а может, и парадигм) вызыват стокие ассоциации с назойливой рекламой религиозных сект. Причем, шести сразу.
Готовность автора пересматривать свои взгляды на программирования неоднократно вызывает по крайней мере сильные сомнения в полезности статьи: получается, что он уже поменял свои вгляды на программирование ШЕСТЬ раз. И предлагает читателям последовать его интеллектуальным метаниям, так как вполне вероятно это далеко не предел и его взгляды еще поменяются не раз.
Описание парадигм, по крайне мере символического, конкатенативного и «основанного на знаниях» — крайне поверхностное.
Короче, статья — рекламный мусор.
DarkEld3r
Как будто что-то плохое. Конечно же, догматизм и синдром утёнка лучше.
Надо было ещё добавить проплаченный рекламный мусор, ну так для полноты картины. (:
yuklimov
Стоит добавить HDL языки (VHDL или Verilog). Кстати, вполне практичное применение конкурентности.
Mishkun
При упоминании слов "символы" и "программирование" вспоминается APL.
А Aurora, по крайней мере, на видео, выглядит как не очень удобный MathLAB
artur93gev
Статья хорошая, мне понравилась.спасибо
rkosolapov
Интересующимся парадигмами зело рекомендую следующую книжку: https://mitpress.mit.edu/books/concepts-techniques-and-models-computer-programming Ну и другие книжки этого автора также неплохи.