Comments 49
Сравните решение на С, о котором шла речь выше, с этим кодом из 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 и оператора !
— вы привели императивный код, но никак не простое описание закономерностей, которым должно удовлетворять решение.
Собственно, именно это и является проблемой Пролога — при изначальной красивой идее декларативности любая попытка оптимизации вырождается в императивный код с кривым синтаксисом.
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?
Вы даже не представляете, насколько вещи вокруг Вас зависят от этих языков, в которых присутствует мозговыносный паралеллизм.
Сейчас же все процессоры общего назначения — конвейерные, там и так ассемблерные команды исполняются в параллель, если это возможно.
Вычислительный комплекс с десятками ядер, и это не суперскалярное что-то? Какие-нибудь MIMD.
Следующий уровень — когда в коде задан явный параллелизм, т.е. те же потоки для х86 и х64. Или длинные команды для VLIW.
Так что возможность параллельного исполнения смотрится не только на уровне задачи и кода, но и возможностей процессора. Тем более, что задача может быть решена несколькими способами, причем одни варианты могут быть параллельными, а другие — нет.
Но есть ниши, где принципиально важно писать максимально производительный код. И вот там как раз вполне можно жертвовать простотой языка в пользу скорости и параллелизации.
Напомнило высказывание Ф.Энгельса о персидском языке:
"Зато персидский язык не язык, а настоящая игрушка. Если бы не этот проклятый арабский алфавит, в котором то и дело целые шестерки букв имеют совершенно одинаковый вид и в котором нет гласных, то я бы взялся изучить всю грамматику в течение 48 часов. "
Но что если он мог бы определять переменную как «положительное целое число», «список из двух пунктов» или «текст, который является палиндромом»?
Ок, проверить, что строковая константа является палиндромом на этапе компиляции можно и на C++. Но как это поддерживается для динамических данных? Каждый раз при изменении значения запускается процедура валидации или код пишется так, что можно доказать, что строка всегда будет оставаться палиндромом? Если первое, то как себя ведёт программа, если контракт нарушен?
Думаю, для императивных языков допустимо неконсистентное состояние между какими-нибудь точками контроля. Например, проверка может происходить при передаче в функцию, которая принимает "список из двух пунктов", или при ручном приведении типа. Для методов класса можно ввести какой-нибудь атрибут, при наличии которого компилятор будет подставлять проверку типа в конец метода.
Конкурентность по умолчанию
А чем это отличается от G/LabVIEW? Там конкурентность и параллелизм на уровне синтаксиса. И кстати Alice еще есть. По идее можно было бы наверное и Verilog с VHDL вспомнить, там правда конкурентность ИМХО под вопросом, т.к. определяется таймингами, но зато там чистый параллелизм. Еще наверное можно и Erlang с Go сюда же добавить (ну или хотя бы объяснить разницу, если нет).
Язык Aurora — образчик символического программирования.
Опять таки не упомянули LabVIEW — куда более известная и устоявшаяся штука (в отличии от Авроры, которую походу вообще ради фана делали), а также VisSim, SystemView, и JMCAD, а также все языки стандарта IEC 61131-3 и их потомки(символическое/графическое программирование, наверное наверное самое распространенное для промышленного программирования управления охрененно больших и дорогих штук). Ну Наверное еще и HiAsm и Simulink — правда я хз, можно ли вот эти два считать уже полноценными ЯП или нет.
Требуем
В конкатенативных языках не упомянут Factor Славы Пестова, который более-менее готов для продакшена и про который во второй книге Семь языков за семь недель глава есть.
А на фоне признания автора, что он не является экспертом ни в одном из перечисленных языков (а может, и парадигм) вызыват стокие ассоциации с назойливой рекламой религиозных сект. Причем, шести сразу.
Готовность автора пересматривать свои взгляды на программирования неоднократно вызывает по крайней мере сильные сомнения в полезности статьи: получается, что он уже поменял свои вгляды на программирование ШЕСТЬ раз. И предлагает читателям последовать его интеллектуальным метаниям, так как вполне вероятно это далеко не предел и его взгляды еще поменяются не раз.
Описание парадигм, по крайне мере символического, конкатенативного и «основанного на знаниях» — крайне поверхностное.
Короче, статья — рекламный мусор.
поменял свои вгляды на программирование ШЕСТЬ раз. И предлагает читателям последовать его интеллектуальным метаниям, так как вполне вероятно это далеко не предел и его взгляды еще поменяются не раз.
Как будто что-то плохое. Конечно же, догматизм и синдром утёнка лучше.
Короче, статья — рекламный мусор.
Надо было ещё добавить проплаченный рекламный мусор, ну так для полноты картины. (:
При упоминании слов "символы" и "программирование" вспоминается APL.
А Aurora, по крайней мере, на видео, выглядит как не очень удобный MathLAB
Шесть парадигм программирования, которые изменят ваш взгляд на код