В рамках искусственного интеллекта различают два основных направления:
1) символьное (семиотическое, нисходящее) направление, которое основано на моделировании высокоуровневых процессов мышления человека, на представлении и использовании знаний;
2) нейрокибернетическое (нейросетевое, восходящее) направление, которое основано на моделировании отдельных низкоуровневых структур мозга (нейронов) .
Несколько слов об ИИ
В настоящее время выделяются следующие подходы:
логический подход;
структурный подход;
эволюционный подход;
имитационный подход.
Несколько слов об ИИ
Первый подход в разработке систем искусственного интеллекта — логический.
Этот подход возник потому, что именно способность к логическому мышлению достаточно сильно отличает человека от неразумных животных.
Основой для логического подхода служит булевская алгебра. Каждый программист знаком с этим формализмом с тех пор, как осваивал условную конструкцию if-then-else.
Несколько слов об ИИ
Вторым подходом, развившимся в русле искусственного интеллекта, считается структурный подход, под которым подразумеваются попытки построения систем искусственного интеллекта при помощи моделирования структуры человеческого мозга.
Одной из первых таких попыток был упоминавшийся ранее перцептрон Ф. Розенблатта.
Основной моделируемой структурной единицей в перцептронах (как и в большинстве других вариантов моделирования мозга) является нервная клетка — нейрон.
Несколько слов об ИИ
Довольно большое распространение получил и эволюционный подход.
При построении систем искусственного интеллекта основное внимание уделяется построению начальной модели и правилам, по которым она может изменяться (эволюционировать). Причем модель может быть составлена по самым различным методам, это может быть и нейросеть, и набор логических правил, и любая другая модель.
После этого производится запуск эволюционного алгоритма, который на основании проверки моделей отбирает самые лучшие из них, посредством которых по определенным правилам генерируются новые модели, из которых опять выбираются самые лучшие и т. д.
Несколько слов об ИИ
Наконец, еще один широко используемый подход к построению систем искусственного интеллекта — имитационный.
Данный подход является классическим для кибернетики с одним из ее базовых понятий — «черным ящиком», то есть устройством, программным модулем или набором данных, информация о внутренней структуре и содержании которых отсутствует полностью, но известны спецификации входных и выходных данных.
Объект, поведение которого имитируется, как раз и представляет собой такой «черный ящик».
Совершенно не важно, что у него и у модели внутри и как он функционирует, главное, чтобы модель в аналогичных ситуациях вела себя точно так же, как и моделируемый объект.
Несколько слов об ИИ
На практике четкой границы между описанными подходами к построению систем искусственного интеллекта нет.
Очень часто встречаются смешанные системы, где часть работы выполняется по одному типу, а часть — по другому.
Несколько слов об ИИ
Разработку систем ИИ в рамках структурного, эволюционного и имитационного подходов без всяких проблем можно осуществить на функциональных языках программирования.
Да и логический подход также неплохо проецируется на методики функционального программирования, хотя для него была создана отдельная парадигма — логическое программирование, самым известным представителем которой в мире языков программирования является язык Prolog.
Программирование в повествовательном наклонении
В грамматике различает три наклонения предложений:
изъявительное (повествовательное),
вопросительное и
императивное (повелительное).
И если в обычной речи преобладают повествовательные предложения, то в известном нам традиционном программировании повелительные.
В традиционном представлении программа – последовательность команд, выполняемых компьютером.
Программирование в повествовательном наклонении
Но существует и другой стиль программирования, программирование в повествовательном наклонении, при котором программа – просто совокупность утверждений.
Этот стиль (или, как сейчас модно говорить, парадигма) получил название декларативное программирование.
Соответственно и языки программирования делят на императивные и декларативные.
Наиболее важными разновидностями декларативного программирования, являются функциональное и логическое (или реляционное) программирование.
Программирование в повествовательном наклонении
Программа, как правило, создаётся для решения некоторой проблемы.
Программируя в императивном стиле, мы должны точно сообщить компьютеру какрешить проблему, то есть пошагово описать процесс решения.
В декларативном программировании мы скорее сообщаем компьютеру, что собой представляет проблема, описываем спецификацию программы.
Можно сказать, что декларативная программа – исполняемая спецификация.
Программирование в повествовательном наклонении
В своей статье "Алгоритм = Логика + Управление" Роберт Ковальский подчеркивал тот факт, что во всякой программе можно выделить две составляющих: логику, описывающую собственно решение проблемы и управление процессом вычислений.
В этой терминологии декларативное программирование – описание логики алгоритма, но не (обязательно) управления.
Программирование в повествовательном наклонении
Пожалуй, лучше всего описывает ключевую идею декларативного программирования следующее определение (принадлежащее Джону Робинсону ): программа является теорией, а вычисления представляют собой вывод в этой теории.
Программирование в повествовательном наклонении
Ещё одно, негативное определение: декларативные программы не используют понятия состояния и не содержат переменных.
Следовательно, они не могут использовать операторы присваивания, так как нечему присваивать.
Кроме того, понятие последовательности выполнения команд становится бессмысленным и, значит, бесполезными становятся операторы управления процессом вычислений.
Ранние языки высокого уровня, начиная с Фортрана, разделили глобальную память на области кода и данных, и установили ограничение, что только данные могут изменяться.
Концепции модульности, структурного программирования, строгой типизации также ограничивают свободу программиста.
Последние веяния – более строгие интерфейсы и запреты на непосредственные изменения объектов.
Краткая история
Декларативное программирование может рассматриваться как еще один, более радикальный, шаг в этом направлении.
Джон Хьюз сравнивал функциональных программистов со средневековыми монахами, отвергающими удовольствия жизни.
Программирование в повествовательном наклонении
Понятно что, принимая схиму и отказываясь от средств, которые менее набожные программисты считают стандартными, мы надеемся получить некоторые преимущества.
Императивные языки развивались путем абстракции от модели вычислений типичного компьютера, известной как модель фон Неймана.
Поэтому они позволяют эффективно использовать ресурсы компьютера.
Краткая история
Но человек не компьютер. И рассуждать в терминах и понятиях вычислительной машины для него трудно и неестественно.
Решая достаточно сложную задачу, мы обычно сначала создаем модель в некоторой формальной системе, а затем переписываем найденное решение в виде программы, то есть, переводим с одного формального языка на другой.
Краткая история
Этот второй этап не имеет отношения собственно к процессу решения, и в то же время требует большого количества усилий и специальных навыков.
Возникло даже разделение труда среди программистов: одни (аналитики) думают, как решить задачу, а другие (кодировщики) записывают найденное первыми решение на языке программирования.
Программирование в повествовательном наклонении
В основе декларативных языков лежит не какая-то машинная модель, а логика и математика.
И появляется возможность формализовывать наши знания о проблеме непосредственно в терминах языка программирования.
Это утверждение может показаться сомнительным, но в любом случае декларативные программы гораздо ближе к формальным спецификациям, чем их "обычные" аналоги.
Программирование в повествовательном наклонении
Вернёмся к уравнению "Алгоритм = Логика + Управление".
При программировании на императивном языке, эти две составляющих переплетены и у программиста нет выбора, кроме как вникать в низкоуровневые подробности выполнения программ.
Программирование в повествовательном наклонении
В декларативных языках, логика и управление разделены.
Необходимость иметь дело только (или главным образом) с логическим компонентом значительно упрощает программирование.
Декларативную программу, вообще говоря, проще написать и, что немаловажно, легче понять, чем соответствующую императивную программу.
Программирование в повествовательном наклонении
Кроме того, возникает возможность передачи ответственности за создание управления компьютеру.
Часто наличие наиболее эффективного алгоритма не настолько уж важно и можно удовлетвориться разумно эффективным алгоритмом, который находит сама система.
Более того, появляются интересные возможности использовать нетривиальные алгоритмы управления, такие как недерминированные, "ленивые" и параллельные вычисления.
Программирование в повествовательном наклонении
Многие практически важные задачи требуют огромного количества вычислений и очевидный путь обеспечения требуемой вычислительной мощности – использование параллельных компьютеров.
Но автоматическое распараллеливание последовательных программ очень редко обеспечивает достижение приемлемого уровня параллелизма.
Программирование в повествовательном наклонении
Программа на императивном языке "переопределена".
Она устанавливает определенный порядок вычислений, часто не связанный с решением задачи.
Векторизующий компилятор пытается ретроспективно обнаружить параллелизм первоначально присущий задаче, но сделать это очень сложно, а часто и невозможно.
Программирование в повествовательном наклонении
В конечном счете, компилятор, который находит возможности для параллелизма, только избавляется от переопределенности присущей последовательным языкам.
В связи с этим возник класс параллельных языков программирования, которые имеют явные средства для выражения параллелизма.
Программирование в повествовательном наклонении
Но программировать на таких языках гораздо труднее, чем на последовательных – человеку гораздо легче понять статические соответствия, чем осознать протекающий во времени процесс и совсем уж трудно наглядно представить совокупность одновременно протекающих процессов.
Программирование в повествовательном наклонении
Декларативные языки хорошо подходят для программирования параллельных компьютеров.
Они не требуют специальных методов описания параллелизма.
Параллелизм программы определяется неявно её информационными связями.
Программирование в повествовательном наклонении
Другими словами, работает ли программа на последовательном или параллельном компьютере, программисту безразлично.
Чем более декларативен язык программирования, тем более вероятно наличие неявного параллелизма и тем проще будет параллельное выполнение программы.
Программирование в повествовательном наклонении
Такое неявное использование параллелизма очень удобно для программиста, поскольку для него не возникает дополнительных трудностей сверх тех, которые присутствуют в программе для последовательного компьютера.
Но сама система должна быть достаточно "разумна", чтобы найти наиболее эффективный способ выполнения программы.
Программирование в повествовательном наклонении
Это очень трудная задача, но некоторые положительные результаты уже достигнуты и можно надеяться, что в ближайшем будущем станет возможно эффективно выполнить декларативные программы на параллельных компьютерах "прозрачно" для программиста.
Программирование в повествовательном наклонении
Ещё одно достоинство декларативных языков - пригодность для формальных рассуждений.
Известно, что тестирование позволяет обнаружить ошибки, но не может гарантировать их отсутствия.
Единственный способ убедиться в правильности программы – проанализировать её код.
Программирование в повествовательном наклонении
К сожалению, существующие методы формального анализа программ чрезвычайно трудоёмки.
Дело в том, что широко используемые языки типа Си имеют очень сложную и запутанную семантику.
Это означает, что очень трудно формально (и даже неформально) рассуждать о программах на таких языках.
Программирование в повествовательном наклонении
Много усилий было направлено на создание более простых и строгих языков, а также на совершенствование методов анализа, но результаты не обнадёживают.
Применение формальных методов остаётся очень дорогостоящим и ограничивается теми областями, где надёжность программного обеспечения критична.
Программирование в повествовательном наклонении
Декларативная программа представляет собой формальную теорию, и, следовательно, относительно легко может быть подвергнута логическому анализу.
Причём анализ этот может производиться в терминах самой программы, не требуя привлечения дополнительных формализмов, таких как предикаты на состояниях.
Программирование в повествовательном наклонении
Более того, возникает возможность создания инструментальных средств, позволяющих автоматизировать процессы анализа, преобразования, синтеза программ.
Появление таких средств может в корне изменить программирование.
Программирование в повествовательном наклонении
Нельзя утверждать, что создание такого рода инструментов для декларативных языков - легкая задача, но многие несущественные трудности исчезают и, по крайней мере, не придётся впустую тратить время, пытаясь решить проблемы, которых попросту не должно быть.
Недостатки
После панегириков декларативному программированию, стоит упомянуть и свойственные этому подходу недостатки.
Недостатки
Существующие формы декларативного программирования плохо справляются с временными аспектами многих задач.
Для приложений, которые активно взаимодействуют с пользователями или внешними процессами декларативных средств часто оказываются недостаточно и программистам приходится применять довольно специфические методы, нарушающие декларативность программ.
Недостатки
Часто утверждают, что декларативные языки не подходят для параллельного программирования.
При этом под "параллельным программиро-ванием" подразумевается не распараллели-вание вычислений, а задача в некотором смысле противоположная – адекватно выразить в программе естественный параллелизм задачи. То есть речь идёт опять же о временных аспектах.
Недостатки
Причина этих трудностей в том, что декларативные языки основаны на теориях по существу "статических".
Нужны новые "динамические" формализмы, которые позволили бы включить в декларативные языки временные средства.
Недостатки
Возможные пути их создания можно увидеть во "временных логиках", в алгебраических теориях процессов и даже в теории автоматов.
В настоящее время эти теории недостаточно развиты для широкого практического применения, либо имеют довольно узкую область применения.
Но стоит вспомнить, какой переворот в науке произвело открытие дифференциального исчисления, позволившего статически описывать непрерывные процессы.
Недостатки
Другая проблема декларативных языков – эффективность.
Как часто бывает, недостатки – продолжение достоинств.
Поскольку структура этих языков далека от устройства вычислительных машин, достаточно трудно бывает оценить производительность программы.
Недостатки
Правда техника реализации за последние десятилетия значительно возросла, но очень легко написать краткую, понятную и изящную программу, которая, тем не менее, будет совершенно неприемлема из-за низкой производительности.
Создание же эффективных программ в некоторых случаях требует немалого искусства.
Недостатки
Предлагаемые пути решения этой проблемы – использование специальных аннотаций и автоматические преобразования программ.
Первые уже нашли некоторое применение, вторые – всё ещё предмет исследований.
Перспективы
Пока же на практике предпочитают включать в декларативные языки программирования императивные свойства.
Такой подход не лишён смысла.
В конце концов, не зря же существуют повелительные предложения и, если мы хотим, чтобы что-то произошло, проще всего сказать "сделай это".
Перспективы
Но прямолинейное добавление императивных операторов часто перечёркивает многие достоинства декларативных языков.
Объединение различных парадигм в рамках одного языка, требует тщательной проработки.
Перспективы
К сожалению, долгое время создатели функциональных и логических языков недостаточно серьёзно относились к идее декларативности и в результате практические программы на Прологе или Лиспе ненамного легче анализировать, чем даже программы на Си.
Перспективы
Но, несмотря на свои недостатки, декларативный подход стоит того, чтобы его изучить.
Во-первых, область применения декларативных языков достаточно широка и продолжает расширяться.
Во-вторых, в арсенале функционального и логического программирования накоплено немало средств, которые могут применяться и в традиционном императивном программировании.
Логическое программирование
Логическое программирование – это один из подходов к информатике, при котором в качестве языка высокого уровня используется логика предикатов первого порядка в форме фраз Хорна.
Начало исследованиям в области формальной логики было положено работами Аристотеля в IV в. до н.э.
Логическое программирование
Логика предикатов первого порядка — это ветвь формальной логики, получившая развитие в основном в XX в.
Это — универсальный абстрактный язык предназначенный для представления знаний и для решения задач. Его можно рассматривать как общую теорию отношений.
Логическое программирование базируется на подмножестве логики предикатов первого порядка, при этом оно одинаково широко с ней по сфере охвата.
Логическое программирование
Рассуждая логически, логическое программирование - программирование, основанное на логике.
Часто его определяют как использование языка логики в качестве языка программирования, вместе с использованием логического вывода в качестве вычислительного механизма.
Логическое программирование
Это очень хорошее определение, но оно очень широкое.
Логическое программирование, определеннное таким образом, включает в себя то же функциональное программирование как и многие другие стили программирования.
Логическое программирование
Логическое программирование дает возможность программисту описывать ситуацию при помощи формул логики предикатов, а затем, для выполнения выводов из этих формул, применить автоматический решатель задач (т.е. некоторую процедуру).
При использовании языка логического программирования основное внимание уделяется описанию структуры прикладной задачи, а не выработке предписаний компьютеру о том, что ему следует делать.
Логическое программирование
Другие понятия информатики из таких областей, как теория реляционных баз данных, программная инженерия и представление знаний, также можно описать (и, следовательно, реализовать) с помощью логических программ.
С этой позиции логическое программирование оказывает потенциально революционизирующее влияние на многие аспекты информатики.
Логическое программирование
Исторически сложилось так, что термином "логическое программирование" обозначают использование в качестве языка программирования некоторго подмножества чистой логики первого порядка.
Это означает, что для выражения концепции действия применяется математическое понятие отношения или предиката.
Логическое программирование
Часто встречается еще более узкое толкование понятия логического программирования, когда язык ограничивается применением хорновских предложений (хорновских дизъюнктов), а механизм вывода - определенным вариантом метода резолюций.
На этих принципах создан Пролог и сходные с ним языки программирования.
Логическое программирование
В основе этих языков лежит возможность интерпретировать одно и то же выражение, как логическое утверждение
A, если B1 и B2 и ... Bn
и как определение процедуры
чтобы выполнить A
выполнить B1;
выполнить B2;
...
выполнить Bn.
Логическое программирование
Но такое узкое понятие следует признать слишком ограничительным. Многие языки программирования заслуживающие названия "логических" не вписываются в эту схему.
С другой стороны, тот же Пролог содержит элементы логики второго порядка.
А некоторые свойства Пролога при казуистическом подходе вообще не позволяют отнести его к декларативным языкам.
Функциональное программирование
Функциональное программирование использует математическое понятие функции для выражения концепции действия.
Подобно обычным математическим функциям, процедуры («функции») функциональных языков отображают одни объекты (аргументы) в другие (значения).
Функциональное программирование
Причём, в отличие от процедур (функций) императивных языков, значения функций однозначно определяются их аргументами и не зависят от истории вычислительного процесса.
Но имеется важное различие между математическими функциями и процедурами.
Процедуры должны быть эффективно определены.
Функциональное программирование
Например, в математике мы можем определить квадратный корень из числа a как такое число, которое, будучи возведённым в квадрат, даёт a.
Это совершенно законное определение, тем не менее, абсолютно неконструктивно, оно не даёт метода находить этот самый корень.
(Однако нельзя сказать, что такое определение совершенно бесполезно, поскольку оно важно в качестве средства спецификации.)
Функциональное программирование
В дальнейшем мы будем использовать термины «процедура» и «функция» как синонимы за исключением тех случаев, когда необходимо подчеркнуть эту разницу между математическим понятием функции и её определением на языке программирования.
Функциональное программирование
Это же понятие функции как мы увидим в дальнейшем, используется и для выражения концепции данных.
Вообще, изучение функционального программирования – хороший повод убедиться, что разница между «данными» и «операциями» не столь уж принципиальна.
Функции в функциональных языках являются объектами «первого класса».
Функциональное программирование
Понятие «первоклассных» элементов языка программирования было введено Кристофером Стрейчи.
Он отметил, что языки программирования налагают различные ограничения на методы использования элементов языка.
Элементы первого класса – это элементы с наименьшим количеством ограничений.
Функциональное программирование
Важные свойства таких первоклассных элементов:
На них можно ссылаться посредством переменных.
Их можно включать в структуры данных.
Их можно передавать как параметры.
Они могут быть возвращены в качестве результата.
Функциональное программирование
За небольшими исключениями (например, Алгол-68) императивные языки ограничивают «права и свободы» функций и процедур.
В отличие от них, функциональные языки предоставляет функциям статус первого класса.
Это создаёт трудности для их эффективной реализации, но приводит к значительному увеличению выразительной силы этих языков.
Функциональное программирование
Для дальнейшего изложения нам потребуется язык программирования и в качестве такового был выбран Haskell.
Выбор обусловлен чрезвычайно простой семантикой языка и в некоторой степени его однородным синтаксисом.
Эти свойства позволяют прозрачно выразить основные идеи функционального программирования.