Comments 49
Сравните решение на С, о котором шла речь выше, с этим кодом из Prolog:

… а теперь сравните время выполнения :-)


Декларативное программирование — замечательная парадигма, но не надо объяснять ее на основе языка Prolog.

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

А если я не знаю решение, но очень хочу найти, то как быть?

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

Можно ли пример кода, как выглядит "задача коммивояжера" на ПроЛоге?

Сам я на прологе не пишу, но беглое гугление по запросу «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,"Колыма").

Судя по постоянным использованиям retract, assert и оператора ! — вы привели императивный код, но никак не простое описание закономерностей, которым должно удовлетворять решение.


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

Приведенный пример перегруженный. Можно проще написать. Нужна пара строчек permutation
permute([], []).
permute([X|Rest], L) :- permute(Rest, L1).
для генерации вариантов, затем описание графа дорого в виде списка
table([way(1,2,10), way(2,3,30),....]).
и далее основное правило для поиска минимума.
К сожалению, под рукой нет Prolog. Попробовал онлайн — не получилось с ходу разобраться.

PS: преимущество пролога как раз в скорости написания кода, а недостаток — в скорости перебора. Но были версии движка со свтроенной оптимизацией перебора.
Программа на прологе содержит три основных секции:
1. Секцию фактов, оно же «дано», по сути константы/база данных. «Коля — мальчик», например.
2. Секцию правил вывода, в форме «если верно А и Б, то верно В». Скажем, «Оля любит мальчиков».
3. Секцию целей. Что, собственно, нужно найти. Условное «Г», которое нужно доказать или опровергнуть, но не вообще, а для конкретно заданных значений А, Б и т.д. из пункта 1. «Любит ли Оля Колю?»
Все вот эти А, Б, В, Г и т.д. по-умному называются предикатами, т.е. переменными или функциями, возвращающими тип bool (т.е. истина или ложь). А сам язык пролог по сути занимается доказыванием математических теорем. Есть такой алгоритм бэктрекинга, вот собственно его рантайм пролога и исполняет.
На практике получается вот что:
— Первая секция («фактов») тривиальна;
— Третья («целей»), в общем, тоже; это или конструкция goal, или просто восклицательный знак после выражения, типа «приехали».
А вот секция правил вывода — это чистейший вынос мозга. Ну вот представьте, что у вас есть «дано» в шахматах (начальная расстановка фигур) и условия «надо» (правила мата). Только вам нужно придумать не алгоритм выигрывания, а правила, по которым должны ходить ваши фигуры — так, чтобы в итоге выиграть. «Если ты ладья, слева-сзади твой ферзь, а справа чужая пешка, то...» И эти правила, в первом приближении, работают одновременно (в прологе есть порядок выполнения, но в первом приближении так).
Причем это не только для программистов вынос мозга, для математиков тоже. В отличие от теорем, здесь есть побочные эффекты, ну там ввод-вывод, запрос даты-времени и вот это всё. В этом ключевое отличие от модной функциональщины.
В итоге имеем красивую идею с отлично проработанным математическим бэкграундом… и полное отсутствие программистов, согласных на этом писать.

Мы писали когда-то лабораторку (нужно было взять пример из методички и дополнить своими правилами). Итог — пришлось всё переписать с нуля. т.к. написанный код "экспертной системы" при добавлении новых правил разваливался и костыли не помогали, а там было всего десяток признаков и пяток ответов. Вот такой он, Пролог.


PS. Автору


Таким образом, создаётся переменная 11

l1?

В отличие от теорем, здесь есть побочные эффекты, ну там ввод-вывод, запрос даты-времени и вот это всё. В этом ключевое отличие от модной функциональщины.
В итоге имеем красивую идею с отлично проработанным математическим бэкграундом… и полное отсутствие программистов, согласных на этом писать.
Как только появляются побочные эффекты, перестаёт работать всенаправленность предиката и «красивая идея» вырождается в «модную функциональщину». А если не видно разницы, зачем мучиться, допиливая напильником N! до log(N).
Давайте начнём с того, что по-настоящему потрясает воображение: существуют такие языки, в которых по умолчанию предполагается конкурентность.

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

Идея в том, что язык состоит из функций, которые добавляют данные в стек или же выбрасывают данные из стека;

ПОЛИЗ же. И советские программируемые калькуляторы :)

Все-таки большинство процессорных архитектура — регистровые, а не стековые (стек есть, но помимо него — регистры, с которыми в основном и происходит работа).


Примеры чисто стековых — виртуальные машины CLR и JVM, а так же процессор RTX2010, стоявший на зонде Rosetta


RTX2010 — куда более редкий зверь. Это стековый процессор. Он оперирует данными, которые находятся не в регистрах, а в двух встроенных стеках. Роль машинного кода при этом исполняет высокоуровневый язык программирования Forth.

CLR не чисто стековая.


  • Для каждой функции создается свой министек. Поэтому функция не может залезть в стек вызывающей.
  • Для вызова аргументы складываются в стек, но внутри в начале работы стек пуст, а аргументы хранятся в специальном месте
  • Также там доступны локальные переменные
  • Там нельзя просто так вернуть 2 значения. ВМ требует, чтобы по окончании работы в стеке было не больше одного значения.
практического смысла в этом мало
HDL?
Verilog?
Вы даже не представляете, насколько вещи вокруг Вас зависят от этих языков, в которых присутствует мозговыносный паралеллизм.

Verilog

Там же нет параллелизма «по умолчанию», без необходимости. Порядок следования операторов соответствует и последовательности обработки сигнала в сгенерированном девайсе, всё достаточно традиционно.
Да, я теперь смотрю на код и понимаю, как он всё-таки хорош по сравнению со всякими извращениями. Надо было здесь еще Brainfuck или Malbolge для полноты картины упомянуть.

Brainfuck можно хотя бы эффективно (за полиномиальное время с приятной степенью) генерировать, на Malbolge кроме как прямым перебором последовательностей символов вроде как не пишут.

Параллелизм на уровне команд языка высокого уровня смущает.
Сейчас же все процессоры общего назначения — конвейерные, там и так ассемблерные команды исполняются в параллель, если это возможно.
А если у вас многопроцессорная машина?
Вычислительный комплекс с десятками ядер, и это не суперскалярное что-то? Какие-нибудь MIMD.
принципы параллельного исполнения различны. У x86 (и x64) возможность параллельного вычисления вычисляется на лету, т.к. код то последовательный (совместимость с одноядерными).
Следующий уровень — когда в коде задан явный параллелизм, т.е. те же потоки для х86 и х64. Или длинные команды для VLIW.
Так что возможность параллельного исполнения смотрится не только на уровне задачи и кода, но и возможностей процессора. Тем более, что задача может быть решена несколькими способами, причем одни варианты могут быть параллельными, а другие — нет.
То, как сейчас обычно пишется код, как раз-таки сильно ограничивает возможности оптимизирующих компиляторов — обычно они вынуждены действовать максимально пессимистично, чтобы гарантировать такое наблюдаемое поведение, которое бы соответствовало линейному коду. В случае с языками выше, в теории, оптимизация могла бы быть гораздо более агрессивной — ведь компилятору нужно обеспечить только те отношения, которые явно прописаны в коде.
Это, грубо говоря, экономия на спичках за счёт сжигания пачки денег. При таком всегда «параллельном» подходе вы немного облегчаете работу самому дешёвому ресурсу — компилятору (и то, лишь в тех случаях, когда компилятор знает архитектуру исполняющих модулей конкретного процессора, чтобы его максимально загрузить параллельными тасками. Т.е. по сути, применение ограничивается JIT-компиляцией), существенно усложняя работу самому дорогому, программистам. При этом я не слишком ошибусь, если скажу, что узкие места в приложениях сейчас в 99.9999% случаев связаны отнюдь не с недостаточной работой оптимизатора компилятора.
Я с вами согласен. Если такой подход ведет к усложнению (а с такой парадигмой структура кода наверняка будет сложнее), то для подавляющего числа проектов это не актуально.

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

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

Напомнило высказывание Ф.Энгельса о персидском языке:
"Зато персидский язык не язык, а настоящая игрушка. Если бы не этот проклятый арабский алфавит, в котором то и дело целые шестерки букв имеют совершенно одинаковый вид и в котором нет гласных, то я бы взялся изучить всю грамматику в течение 48 часов. "

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

Ок, проверить, что строковая константа является палиндромом на этапе компиляции можно и на C++. Но как это поддерживается для динамических данных? Каждый раз при изменении значения запускается процедура валидации или код пишется так, что можно доказать, что строка всегда будет оставаться палиндромом? Если первое, то как себя ведёт программа, если контракт нарушен?

или код пишется так, что можно доказать, что строка всегда будет оставаться палиндромом

Вот так, да.

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

Было бы хорошо расширить и углубить статью :-)

Конкурентность по умолчанию

А чем это отличается от G/LabVIEW? Там конкурентность и параллелизм на уровне синтаксиса. И кстати Alice еще есть. По идее можно было бы наверное и Verilog с VHDL вспомнить, там правда конкурентность ИМХО под вопросом, т.к. определяется таймингами, но зато там чистый параллелизм. Еще наверное можно и Erlang с Go сюда же добавить (ну или хотя бы объяснить разницу, если нет).

Язык Aurora — образчик символического программирования.

Опять таки не упомянули LabVIEW — куда более известная и устоявшаяся штука (в отличии от Авроры, которую походу вообще ради фана делали), а также VisSim, SystemView, и JMCAD, а также все языки стандарта IEC 61131-3 и их потомки(символическое/графическое программирование, наверное наверное самое распространенное для промышленного программирования управления охрененно больших и дорогих штук). Ну Наверное еще и HiAsm и Simulink — правда я хз, можно ли вот эти два считать уже полноценными ЯП или нет.

Требуем больше хлеба и зрелищь больше примеров и сравнений!
UFO landed and left these words here

В конкатенативных языках не упомянут Factor Славы Пестова, который более-менее готов для продакшена и про который во второй книге Семь языков за семь недель глава есть.

UFO landed and left these words here
UFO landed and left these words here
К палиндрому это тоже относится.

Это немножко читерство. Вы переносите описание свойств структуры данных с её типа на её интерпретацию (toList в вашем случае).

UFO landed and left these words here
wolfram когда-то несколько раз пытался пользовать, не очень там гибкий синтаксис, шаг в сторону от описанного в доке и уже не работает, но так или иначе статистические данные можно извлекать, иногда только там их и находишь.
Название статьи претенциозное и неудачное.
А на фоне признания автора, что он не является экспертом ни в одном из перечисленных языков (а может, и парадигм) вызыват стокие ассоциации с назойливой рекламой религиозных сект. Причем, шести сразу.
Готовность автора пересматривать свои взгляды на программирования неоднократно вызывает по крайней мере сильные сомнения в полезности статьи: получается, что он уже поменял свои вгляды на программирование ШЕСТЬ раз. И предлагает читателям последовать его интеллектуальным метаниям, так как вполне вероятно это далеко не предел и его взгляды еще поменяются не раз.
Описание парадигм, по крайне мере символического, конкатенативного и «основанного на знаниях» — крайне поверхностное.
Короче, статья — рекламный мусор.
поменял свои вгляды на программирование ШЕСТЬ раз. И предлагает читателям последовать его интеллектуальным метаниям, так как вполне вероятно это далеко не предел и его взгляды еще поменяются не раз.

Как будто что-то плохое. Конечно же, догматизм и синдром утёнка лучше.


Короче, статья — рекламный мусор.

Надо было ещё добавить проплаченный рекламный мусор, ну так для полноты картины. (:

(Пожимая плечами) Если я, как автор коментария, посчитаю необходимым уточнить свое мнение, я это сделаю.
Стоит добавить HDL языки (VHDL или Verilog). Кстати, вполне практичное применение конкурентности.

При упоминании слов "символы" и "программирование" вспоминается APL.
А Aurora, по крайней мере, на видео, выглядит как не очень удобный MathLAB

Интересующимся парадигмами зело рекомендую следующую книжку: https://mitpress.mit.edu/books/concepts-techniques-and-models-computer-programming Ну и другие книжки этого автора также неплохи.
Only those users with full accounts are able to leave comments. Log in, please.
Information
Founded

10 May 2009

Location

Россия

Employees

101–200 employees

Registered

24 October 2016

Habr blog