Декларативное программирование Лекция Введение в предмет Ст преп кафедры поит и. В. Хан



Yüklə 174,45 Kb.
tarix06.06.2020
ölçüsü174,45 Kb.
#31695
1.DP01 Введение

Декларативное программирование Лекция 1. Введение в предмет

Ст.преп.кафедры ПОИТ И.В.Хан

Темы лекции

  • Программирование в повествовательном наклонении
  • Преимущества
  • Недостатки
  • Перспективы
  • Логическое программирование
  • Функциональное программирование

Несколько слов об ИИ

  • В рамках искусственного интеллекта различают два основных направления:
  • 1) символьное (семиотическое, нисходящее) направление, которое основано на моделировании высокоуровневых процессов мышления человека, на представлении и использовании знаний;
  • 2) нейрокибернетическое (нейросетевое, восходящее) направление, которое основано на моделировании отдельных низкоуровневых структур мозга (нейронов) .

Несколько слов об ИИ

  • В настоящее время выделяются следующие подходы:
  • логический подход;
  • структурный подход;
  • эволюционный подход;
  • имитационный подход.

Несколько слов об ИИ

  • Первый подход в разработке систем искусственного интеллекта — логический.
  • Этот подход возник потому, что именно способность к логическому мышлению достаточно сильно отличает человека от неразумных животных.
  • Основой для логического подхода служит булевская алгебра. Каждый программист знаком с этим формализмом с тех пор, как осваивал условную конструкцию if-then-else.

Несколько слов об ИИ

  • Вторым подходом, развившимся в русле искусственного интеллекта, считается структурный подход, под которым подразумеваются попытки построения систем искусственного интеллекта при помощи моделирования структуры человеческого мозга.
  • Одной из первых таких попыток был упоминавшийся ранее перцептрон Ф. Розенблатта.
  • Основной моделируемой структурной единицей в перцептронах (как и в большинстве других вариантов моделирования мозга) является нервная клетка — нейрон.

Несколько слов об ИИ

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

Несколько слов об ИИ

  • Наконец, еще один широко используемый подход к построению систем искусственного интеллекта — имитационный.
  • Данный подход является классическим для кибернетики с одним из ее базовых понятий — «черным ящиком», то есть устройством, программным модулем или набором данных, информация о внутренней структуре и содержании которых отсутствует полностью, но известны спецификации входных и выходных данных.
  • Объект, поведение которого имитируется, как раз и представляет собой такой «черный ящик».
  • Совершенно не важно, что у него и у модели внутри и как он функционирует, главное, чтобы модель в аналогичных ситуациях вела себя точно так же, как и моделируемый объект.

Несколько слов об ИИ

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

Несколько слов об ИИ

  • Разработку систем ИИ в рамках структурного, эволюционного и имитационного подходов без всяких проблем можно осуществить на функциональных языках программирования.
  • Да и логический подход также неплохо проецируется на методики функционального программирования, хотя для него была создана отдельная парадигма — логическое программирование, самым известным представителем которой в мире языков программирования является язык Prolog.

Программирование в повествовательном наклонении

  • В грамматике различает три наклонения предложений:
    • изъявительное (повествовательное),
    • вопросительное и
    • императивное (повелительное).
  • И если в обычной речи преобладают повествовательные предложения, то в известном нам традиционном программировании повелительные.
  • В традиционном представлении программа – последовательность команд, выполняемых компьютером.

Программирование в повествовательном наклонении

  • Но существует и другой стиль программирования, программирование в повествовательном наклонении, при котором программа – просто совокупность утверждений.
  • Этот стиль (или, как сейчас модно говорить, парадигма) получил название декларативное программирование.

Программирование в повествовательном наклонении

  • В противоположность первый стиль называют императивным программированием.
  • Соответственно и языки программирования делят на императивные и декларативные.
  • Наиболее важными разновидностями декларативного программирования, являются функциональное и логическое (или реляционное) программирование.

Программирование в повествовательном наклонении

  • Программа, как правило, создаётся для решения некоторой проблемы.
  • Программируя в императивном стиле, мы должны точно сообщить компьютеру как решить проблему, то есть пошагово описать процесс решения.
  • В декларативном программировании мы скорее сообщаем компьютеру, что собой представляет проблема, описываем спецификацию программы.
  • Можно сказать, что декларативная программа – исполняемая спецификация.

Программирование в повествовательном наклонении

  • В своей статье "Алгоритм = Логика + Управление" Роберт Ковальский подчеркивал тот факт, что во всякой программе можно выделить две составляющих: логику, описывающую собственно решение проблемы и управление процессом вычислений.
  • В этой терминологии декларативное программирование – описание логики алгоритма, но не (обязательно) управления.

Программирование в повествовательном наклонении

  • Пожалуй, лучше всего описывает ключевую идею декларативного программирования следующее определение (принадлежащее Джону Робинсону ): программа является теорией, а вычисления представляют собой вывод в этой теории.

Программирование в повествовательном наклонении

  • Ещё одно, негативное определение: декларативные программы не используют понятия состояния и не содержат переменных.
  • Следовательно, они не могут использовать операторы присваивания, так как нечему присваивать.
  • Кроме того, понятие последовательности выполнения команд становится бессмысленным и, значит, бесполезными становятся операторы управления процессом вычислений.

Краткая история

  • Ранние языки высокого уровня, начиная с Фортрана, разделили глобальную память на области кода и данных, и установили ограничение, что только данные могут изменяться.
  • Концепции модульности, структурного программирования, строгой типизации также ограничивают свободу программиста.
  • Последние веяния – более строгие интерфейсы и запреты на непосредственные изменения объектов.

Краткая история

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

Программирование в повествовательном наклонении

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

Краткая история

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

Краткая история

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

Программирование в повествовательном наклонении

  • В основе декларативных языков лежит не какая-то машинная модель, а логика и математика.
  • И появляется возможность формализовывать наши знания о проблеме непосредственно в терминах языка программирования.
  • Это утверждение может показаться сомнительным, но в любом случае декларативные программы гораздо ближе к формальным спецификациям, чем их "обычные" аналоги.

Программирование в повествовательном наклонении

  • Вернёмся к уравнению "Алгоритм = Логика + Управление".
  • При программировании на императивном языке, эти две составляющих переплетены и у программиста нет выбора, кроме как вникать в низкоуровневые подробности выполнения программ.

Программирование в повествовательном наклонении

  • В декларативных языках, логика и управление разделены.
  • Необходимость иметь дело только (или главным образом) с логическим компонентом значительно упрощает программирование.
  • Декларативную программу, вообще говоря, проще написать и, что немаловажно, легче понять, чем соответствующую императивную программу.

Программирование в повествовательном наклонении

  • Кроме того, возникает возможность передачи ответственности за создание управления компьютеру.
  • Часто наличие наиболее эффективного алгоритма не настолько уж важно и можно удовлетвориться разумно эффективным алгоритмом, который находит сама система.
  • Более того, появляются интересные возможности использовать нетривиальные алгоритмы управления, такие как недерминированные, "ленивые" и параллельные вычисления.

Программирование в повествовательном наклонении

  • Многие практически важные задачи требуют огромного количества вычислений и очевидный путь обеспечения требуемой вычислительной мощности – использование параллельных компьютеров.
  • Но автоматическое распараллеливание последовательных программ очень редко обеспечивает достижение приемлемого уровня параллелизма.

Программирование в повествовательном наклонении

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

Программирование в повествовательном наклонении

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

Программирование в повествовательном наклонении

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

Программирование в повествовательном наклонении

  • Декларативные языки хорошо подходят для программирования параллельных компьютеров.
  • Они не требуют специальных методов описания параллелизма.
  • Параллелизм программы определяется неявно её информационными связями.

Программирование в повествовательном наклонении

  • Другими словами, работает ли программа на последовательном или параллельном компьютере, программисту безразлично.
  • Чем более декларативен язык программирования, тем более вероятно наличие неявного параллелизма и тем проще будет параллельное выполнение программы.

Программирование в повествовательном наклонении

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

Программирование в повествовательном наклонении

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

Программирование в повествовательном наклонении

  • Ещё одно достоинство декларативных языков - пригодность для формальных рассуждений.
  • Известно, что тестирование позволяет обнаружить ошибки, но не может гарантировать их отсутствия.
  • Единственный способ убедиться в правильности программы – проанализировать её код.

Программирование в повествовательном наклонении

  • К сожалению, существующие методы формального анализа программ чрезвычайно трудоёмки.
  • Дело в том, что широко используемые языки типа Си имеют очень сложную и запутанную семантику.
  • Это означает, что очень трудно формально (и даже неформально) рассуждать о программах на таких языках.

Программирование в повествовательном наклонении

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

Программирование в повествовательном наклонении

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

Программирование в повествовательном наклонении

  • Более того, возникает возможность создания инструментальных средств, позволяющих автоматизировать процессы анализа, преобразования, синтеза программ.
  • Появление таких средств может в корне изменить программирование.

Программирование в повествовательном наклонении

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

Недостатки

  • После панегириков декларативному программированию, стоит упомянуть и свойственные этому подходу недостатки.

Недостатки

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

Недостатки

  • Часто утверждают, что декларативные языки не подходят для параллельного программирования.
  • При этом под "параллельным программиро-ванием" подразумевается не распараллели-вание вычислений, а задача в некотором смысле противоположная – адекватно выразить в программе естественный параллелизм задачи. То есть речь идёт опять же о временных аспектах.

Недостатки

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

Недостатки

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

Недостатки

  • Другая проблема декларативных языков – эффективность.
  • Как часто бывает, недостатки – продолжение достоинств.
  • Поскольку структура этих языков далека от устройства вычислительных машин, достаточно трудно бывает оценить производительность программы.

Недостатки

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

Недостатки

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

Перспективы

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

Перспективы

  • Но прямолинейное добавление императивных операторов часто перечёркивает многие достоинства декларативных языков.
  • Объединение различных парадигм в рамках одного языка, требует тщательной проработки.

Перспективы

  • К сожалению, долгое время создатели функциональных и логических языков недостаточно серьёзно относились к идее декларативности и в результате практические программы на Прологе или Лиспе ненамного легче анализировать, чем даже программы на Си.

Перспективы

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

Логическое программирование

  • Логическое программирование – это один из подходов к информатике, при котором в качестве языка высокого уровня используется логика предикатов первого порядка в форме фраз Хорна.
  • Начало исследованиям в области формальной логики было положено работами Аристотеля в IV в. до н.э.

Логическое программирование

  • Логика предикатов первого порядка — это ветвь формальной логики, получившая развитие в основном в XX в.
  • Это — универсальный абстрактный язык предназначенный для представления знаний и для решения задач. Его можно рассматривать как общую теорию отношений.
  • Логическое программирование базируется на подмножестве логики предикатов первого порядка, при этом оно одинаково широко с ней по сфере охвата.

Логическое программирование

  • Рассуждая логически, логическое программирование - программирование, основанное на логике.
  • Часто его определяют как использование языка логики в качестве языка программирования, вместе с использованием логического вывода в качестве вычислительного механизма.

Логическое программирование

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

Логическое программирование

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

Логическое программирование

  • Другие понятия информатики из таких областей, как теория реляционных баз данных, программная инженерия и представление знаний, также можно описать (и, следовательно, реализовать) с помощью логических программ.
  • С этой позиции логическое программирование оказывает потенциально революционизирующее влияние на многие аспекты информатики.

Логическое программирование

  • Исторически сложилось так, что термином "логическое программирование" обозначают использование в качестве языка программирования некоторго подмножества чистой логики первого порядка.
  • Это означает, что для выражения концепции действия применяется математическое понятие отношения или предиката.

Логическое программирование

  • Часто встречается еще более узкое толкование понятия логического программирования, когда язык ограничивается применением хорновских предложений (хорновских дизъюнктов), а механизм вывода - определенным вариантом метода резолюций.
  • На этих принципах создан Пролог и сходные с ним языки программирования.

Логическое программирование

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

A, если B1 и B2 и ... Bn

и как определение процедуры

  • чтобы выполнить A
  • выполнить B1;
  • выполнить B2;
  • ...
  • выполнить Bn.

Логическое программирование

  • Но такое узкое понятие следует признать слишком ограничительным. Многие языки программирования заслуживающие названия "логических" не вписываются в эту схему.
  • С другой стороны, тот же Пролог содержит элементы логики второго порядка.
  • А некоторые свойства Пролога при казуистическом подходе вообще не позволяют отнести его к декларативным языкам.

Функциональное программирование

  • Функциональное программирование использует математическое понятие функции для выражения концепции действия.
  • Подобно обычным математическим функциям, процедуры («функции») функциональных языков отображают одни объекты (аргументы) в другие (значения).

Функциональное программирование

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

Функциональное программирование

  • Например, в математике мы можем определить квадратный корень из числа a как такое число, которое, будучи возведённым в квадрат, даёт a.
  • Это совершенно законное определение, тем не менее, абсолютно неконструктивно, оно не даёт метода находить этот самый корень.
  • (Однако нельзя сказать, что такое определение совершенно бесполезно, поскольку оно важно в качестве средства спецификации.)

Функциональное программирование

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

Функциональное программирование

  • Это же понятие функции как мы увидим в дальнейшем, используется и для выражения концепции данных.
  • Вообще, изучение функционального программирования – хороший повод убедиться, что разница между «данными» и «операциями» не столь уж принципиальна.
  • Функции в функциональных языках являются объектами «первого класса».

Функциональное программирование

  • Понятие «первоклассных» элементов языка программирования было введено Кристофером Стрейчи.
  • Он отметил, что языки программирования налагают различные ограничения на методы использования элементов языка.
  • Элементы первого класса – это элементы с наименьшим количеством ограничений.

Функциональное программирование

Важные свойства таких первоклассных элементов:

  • На них можно ссылаться посредством переменных.
  • Их можно включать в структуры данных.
  • Их можно передавать как параметры.
  • Они могут быть возвращены в качестве результата.

Функциональное программирование

  • За небольшими исключениями (например, Алгол-68) императивные языки ограничивают «права и свободы» функций и процедур.
  • В отличие от них, функциональные языки предоставляет функциям статус первого класса.
  • Это создаёт трудности для их эффективной реализации, но приводит к значительному увеличению выразительной силы этих языков.

Функциональное программирование

  • Для дальнейшего изложения нам потребуется язык программирования и в качестве такового был выбран Haskell.
  • Выбор обусловлен чрезвычайно простой семантикой языка и в некоторой степени его однородным синтаксисом.
  • Эти свойства позволяют прозрачно выразить основные идеи функционального программирования.

Yüklə 174,45 Kb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin