1.1.4. Объектно-ориентированная вычислительная модель (ооп)
Основным элементом программы в этом стиле является объект, объединяющий в себе данные и операции над ними, называемые методами. Это отличает ООП от процедурного программирования, где операции отделены от данных.
Внутренняя структура данных и реализация методов объекта скрыта от остальной программы (инкапсуляция). Программе доступен только интерфейс объекта.
Основной механизм повторного использования программного обеспечения – это класс (по сути шаблон, описывающий все объекты, для которых характерны одинаковые операции и элементы данных).Разработка шаблонов позволяет создавать проекты сложных систем прямо “на лету”. Платить за это, правда, приходится выразительностью.
Для существующего класса можно создать подклассы путем использования наследования. Способность подклассов одного класса отвечать на одно и то же входящее сообщение по-разному называется полиморфизмом.
Такова краткая характеристика различных парадигм программирования.
Следовать какой-либо парадигме можно практически на любом языке программирования, но каждый язык программирования предназначен в первую очередь для работы внутри своей парадигмы.( Можно например, следовать функциональной парадигме программирования на языках С или С++, когда в теле каждой функции будет только одна инструкция – return.)
Необходимо решить, какой математический формализм должен быть положен в основу вычислительного процесса, который будет выполнять компьютер для решения задачи, то есть выбрать парадигму программирования.
1.2.Метод оценки (способ получения результатов)
Для каждой вычислительной модели существует свой метод оценки. Эти методы разделяются на 3 основных типа:
управление потоками команд; (процедурный)
управление потоками данных; (логический)
редукционные. (функциональный)
1.3. Обмен информацией в процессе оценки
В процессе оценки необходимо осуществить обмен информацией. Для этого используют различные способы:
вызов по значению;
вызов по ссылке;
вызов по имени;
вызов по запросу и т. д.
При программировании применяются различные вычислительные модели (стили), соответственно различные методы оценки и различные способы передачи информации.
Алгоритмы, используемые в этих стилях (моделях), реализуются с помощью языков программирования 4 типов – процедурного, функционального, логического и объектно-ориентированного.
Каждый язык программирования приспособлен к определенному типу вычислений, и использование того или иного языка вынуждает применять именно те типы вычислений, к которым данный язык программирования приспособлен. Это значит, что язык программирования навязывает определенный взгляд на мир и вынуждает мыслить в терминах того языка, на котором предполагается работать. Выбор стиля должен проходить оценку на соответствие стиля и цели программирования. Когда выбор языка сделан, то используются конструкции выбранного языка, а, следовательно, приходится мыслить в терминах семантики этих конструкций. Именно смысловая (семантическая) часть конструкций языка и определяет процесс мышления программиста. Конечно, факторы, которые влияют на выбор стиля, часто противоречивы. Например, эффективность программы с точки зрения архитектуры машины и ясность программы с точки зрения человека могут требовать различных способов изображения. Часто можно написать короткую программу, но понять ее будет очень трудно. Именно в таких ситуациях удачный выбор способа представления данных и метода решения позволяет найти приемлемый компромисс.
Способы мышления и программирования определяют модели (парадигмы) программирования, которые являются основой для создания конкретных языков программирования. Есть традиционные стили программирования, такие как процедурное и функциональное программирование. Есть сравнительно новые стили, такие как логическое и объектно-ориентированное программирование.
Вычислительные машины позволяют автоматизировать не только вычислительные задачи, но и задачи, которые принято относить к сфере искусственного интеллекта (ИИ).
Методы организации рекурсии в ЛП.
Понятия рекурсии и рекурсивности.
Рекурсия – способ описания функций или процессов через самих себя. Рекурсия используется как основа для записи рекурсивных конструкций.
Рекурсивность – это свойство языка программирования, состоящее в том, что конструкции языка допускают включение в себя в явном виде конструкции того же типа.
Именно это обстоятельство позволяет записывать любую программу с использованием небольшого количества типов логических структур. В логическом программировании такое поведение обычно достигается за счет использования рекурсивных процедур, то есть процедур, имя которых встречается по крайней мере в одном вызове из ее тела. Итерационные процедуры, таким образом, являются частным случаем рекурсивных процедур.
Введем в рассмотрение еще одно отношение –ancestor (предок). Определим его в терминах уже известного отношения parent. Отношение ancestor может быть представлено с помощью двух правил:
Правило для определения прямых предков (1);
Правило для определения отдаленных предков, то есть таких, между которыми существует цепочка родительских связей типа parent. (2)
Рис.2.4.Отношение ancestor для прямого(правило 1) и отдаленного предков(правило2)
Для всех X и Z,
1) X - предок Z, если
X – родитель Z.
Второе правило (б) формулируется так:
Для всех X и Z,
2) если имеется такой Y, что
а) X -родитель Y(прямые предки) и
б) Y –предок Z. (отдаленные предки)
Эти утверждения можно перевести на Пролог таким образом:
1) ancestor(X,Z):-
parent(X,Z).
2) ancestor(X,Z):-
parent(X,Y),
ancestor(Y,Z).
Отсюда видно (2), что было использовано утверждение ancestor, которое само еще не было полностью определено. Такие определения называются рекурсивными. Отношение, представленное в заголовке правила (2) зависит от более простой версии самого себя- от подцели ancestor(Y,Z).
Предложенная задача содержит в себе подзадачу такого же типа. При работе с такими задачами должно существовать обязательное условие выхода из рекурсии, иначе рекурсия может оказаться бесконечной, а правила бесполезными. Окончательное решение задачи откладывается до тех пор, пока не сработает утверждение, которое и определяет условие выхода из рекурсии. Ответственность за выход из рекурсии лежит на программисте.
Состав рекурсивной процедуры :
Нерекурсивное предложение (1), определяющее вид процедуры в момент ее прекращения (терминальный случай –базис рекурсии).
Рекурсивное правило (2). Первая подцель в теле правила вырабатывает новые значения аргументов, далее идет рекурсивная подцель, в которой используются эти новые значения аргументов. При каждом вызове это правило поднимается на одно поколение вверх.
Символьные языки программирования.
Сопоставление декларативного и процедурного стилей.
Сравнение пропозициональной логики и логики первого порядка.
Логика – это использование ИП1П (фразы Хорна) для представления наших общих знаний, для описания проблемной области. Этим занимаются программисты. Логика первого порядка, основанная на понятиях объектов и их отношений, позволяет нам выражать факты обо всех объектах Вселенной.
Декларативная модель -определение статического отношения между термами. Эта модель близка к семантике логики предикатов, что делает Пролог эффективным для представления знаний. Но она не учитывает порядок следования подцелей.
Процедурная модель –определяет смысл правила, как последовательности вызовов подцелей( подпрограмм). И здесь важен порядок следования целей, потому что компилятор будет обрабатывать их в том порядке, как они записаны. Но эта модель не способна разъяснить смысл фраз, вызывающих побочные эффекты. (остановка выполнения запросов, удаление фразы из программы)
Декларативный подход в отличии от процедурного не смешивает знания и методы логического вывода, и логический вывод осуществляется полностью независимо от проблемной области.
Декларативное значение определяет то, каким должен быть результат работы программы. Процедурное значение определяет способ получения этого результата, то есть показывает, как на самом деле Пролог-система проводит обработку представленных в программе отношений. Процедура выводит сведения об истинности или ложности целей и в случае истинности целей показывает при каких значениях переменных это достигается.
Так как результаты в принципе определяются их декларативным значением, то для написания программы этого должно быть достаточно. Процедурные аспекты надо оставлять для самой системы.
Однако декларативный подход не всегда позволяет решить все задачи. Поэтому процедурные аспекты полностью игнорироваться программистом не могут,в частности, из-за необходимости обеспечения вычислительной эффективности.
Прогресс в технологии программирования достигается за счет все более глубокого ухода к декларативным аспектам (они легче понимаются и легче поддаются формальному описанию). Желательно все процедурные детали переложить на саму систему.
Но система Пролог не всегда, к сожалению, способна проработать все процедурные детали. Часто это бывает связано с тем, что стратегия решения задачи в компиляторе – другая и не совпадает с порядком написания предложений в программе (например, рекурсивный вызов стоит раньше других подцелей предложения, из-за этого не происходит надежной обработки). В этой ситуации необходимо сначала сосредоточиться на декларативных аспектах программы, затем оттестировать программу, и в случае ее отказа, попытаться переупорядочить предложения и цели.
Проблемная область модели для логики первого порядка – их связь с синтаксисом естественных языков. Объекты. Отношения. Функции.
Формализм, используемый для описания предметной области. Логическая модель вычисления и способ исполнения логических программ.
Выполнение программ осуществляется по принципу обратного логического вывода с поиском в глубину, то есть мы идем от цели, проходим по цепочке от одного правила к другому, чтобы найти известные факты, которые поддерживают доказательство. Для логического программирования это и есть форма автоматизированных рассуждений.
Замечание: логические программы не содержат алгоритма, для решения логической задачи достаточно точного логического описания. Так как в логической программе последовательность и способ выполнения программы не фиксируется, как при описании алгоритма, программы в принципе могут работать в обоих направлениях. Прологовская программа может на основе исходных данных вычислить результат, но с тем же успехом без дополнительного программирования на основе результата –вычислить исходные данные.
(В традиционных языках программирования данные обрабатываются в порядке, задаваемом описанием алгоритма. Это определяет несимметричность функции, то есть вычислить значения аргументов, исходя из значения функции нельзя!)
Понятие отношения и предиката в ЛП.
Центральное понятие- отношение между объектами, представленное в терминах ограничения условий и целей. Программист мыслит в терминах структуры отношений, не заботясь о точности их реализации.
Отношение – это обобщение функции, которое определяется как подмножество прямого произведения множеств.
Итак, сама программа – это множество фактов и правил, задающих отношения между объектами в конкретной прикладной области. Отношение в Прологе называется предикатом. Объекты, связанные этим отношением, называются аргументами. Аргументы могут быть константами (атомами) или переменными.
Предикат определяет, является ли данное отношение истинным или ложным, поэтому предикат можно рассматривать как “индикатор отношения”.
Для записи отношений между объектами можно использовать различные формализмы. В ЛП используется исчисление предикатов первого порядка (ИП1П).Вернее, ограниченная форма ИП1П в виде логики так называемых хорновских предложений(факты, правила и цели).
Общая схема построения формальной системы. Поясните понятия языка системы, аксиом, правил вывода. Сопоставьте понятия дедуктивной системы, исчисления и формальной системы.
Дедуктивной системой(ДС) называется способ задания множества путем указания исходных элементов (аксиом исчисления) и правил вывода, каждое из которых описывает, как строить новые элементы из исходных.
ДС называют также исчислением (то есть правилами вычисления и оперирования объектами) или формальной системой.
Когда говорят о языках программирования, предложения которых построены на основе строгих правил таким образом, чтобы для любой последовательности символов можно было сказать, является она правильно построенной конструкцией этого языка или нет, то о языке говорят тоже как о формальной системе.
Множество фактов, правил и целей задают логическую программу.
Факты задают отношения между объектами.
Правила определяют одни отношения через другие.
Цель требует доказательства, исходя из множества фактов и правил программы. Процесс доказательства – само выполнение программы.
Логика возложена на программиста, управление – на компьютер. Компьютер строит необходимый для решения логический вывод в соответствии с процессом упрощения (внутренние подпрограммы унификации и поиск с возвратом) и механизмом вывода (принцип резолюции – раздел логики – автоматическое доказательство теорем)
Программист должен быть квалифицирован и в представлении знаний, и в понимании того, как они обрабатываются на компьютере.
Метод отката после неудачи.
Есть несколько способов реализации повторов в Прологе. Наиболее удобными считаются два способа - откат после неудачи и отсечение и откат.