Ю.Ю. Громов и др. Информатика (2007)

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

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

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

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

Вопросы для самопроверки

1.Опишите три основных этапа процесса трансляции.

2.Что такое таблица символов?

3.Исходя из синтаксических диаграмм, представленных на рис. 5.14, нарисуйте дерево синтаксического разбора для выражения

х * у + х + z.

4.Напишите несколько строк, формат которых будет соответствовать структуре Ча-Ча-Ча, определенной с помощью следующих синтаксических диаграмм.

Ча-Ча-Ча

5.5.ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ*

Вразделе 5.1 уже говорилось, что объектно-ориентированная парадигма предусматривает разработку активных программных модулей, называемых объектами, каждый из которых содержит процедуры, описывающие реакцию объекта на различные входные сигналы. Эти внутренние процедуры называются методами (или функциями-членами – в терминологии языка C++). Объектно-ориентированный подход к решению задачи состоит в выявлении и описании необходимых объектов,

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

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

Вязыках C++ и Java для объявления, что имя BusinessX будет использоваться для ссылки на объект "типа" Small-

Business, мы могли бы применить следующий оператор:

SmallBusiness BusinessX;

Обратите внимание, что этот оператор ничем не отличается от используемого в языке программирования С для объявления, что Cost является переменной типа integer:

int Cost;

Несмотря на общее сходство, эти операторы имеют несколько существенных отличий. Одно из них состоит в том, что "тип" объекта принято называть классом. Таким образом, класс – это описание структуры объекта. В некотором смысле класс представляет собой шаблон, который используется для создания объекта. Другое отличие заключается в том, что тип integer является встроенным типом языка программирования, тогда как класс SmallBusiness – это "тип", который должен быть описан в каком-то месте программы.

Для описания классов многие объектно-ориентированные языки программирования включают специальные операторы, подобные представленному ниже:

class SmallBusiness

{

.

.

.

};

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

Обобщая сказанное, можно сделать вывод, что в нашей моделирующей программе сначала следует воспользоваться оператором class для описания класса с именем SmallBusiness, а затем поместить операторы объявления приведенного выше типа для указания, что в программе будут использоваться объекты.

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

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

А затем использовать приведенный ниже оператор для описания другого класса, например, с именем MailOrderBusiness:

class MailOrderBusiness extends SmallBusiness

{

.

.

.

}

В языке C++ нужно просто заменить слово extends двоеточием. Этот оператор означает, что данный класс наследует все свойства класса SmallBusiness, а также дополнительно имеет свойства, указанные внутри фигурных скобок. Аналогично можно было бы описать и другой класс под названием ConsultingBusiness, который также наследует свойства класса SmallBusiness и одновременно обладает свойствами, характерными только для предприятий, занимающихся консалтингом. После того как указанные выше классы будут описаны, появится возможность использовать следующие операторы:

MailOrderBusiness BusinessX;

ConsultingBusiness BusinessY;

Эти операторы указывают, что переменная BusinessX является объектом, описывающим малое предприятие, принимающее заказы по почте, а переменная BusinessY – это объект, описывающий малое предприятие, занимающееся консалтингом.

Инкапсуляция и полиморфизм. Существование множества объектов, имеющих сходные, но все же отличающиеся характеристики, приводит к явлению, напоминающему перегрузку, речь о которой шла в разделе 5.2. (Напомним, что понятие перегрузки означает использование одного и того же символа, например знака +, для представления разных операций в зависимости от типа указанных операндов.) Предположим, что объектно-ориентированный графический пакет состоит из разнообразных объектов, каждый из которых описывает некоторую фигуру (окружность, прямоугольник, треугольник и т.п.). Каждое изображение состоит из совокупности таких объектов. Для каждого объекта известны его размер, положение и цвет, а также то, как он реагирует на сообщения, требующие от него определенных действий, например перемещение в новое положение или отображение самого себя на экране. Для того чтобы нарисовать изображение в целом, мы просто посылаем сообщение "нарисуй себя" каждому из объектов, образующих это изображение. Однако программы, рисующие отдельные объек-

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

Другим свойством, связанным с объектно-ориентированным программированием, является инкапсуляция (encapsulation), которая означает ограничение доступа к внутренним свойствам объекта. Если сказать, что некоторое свойство объекта является инкапсулированным, это будет равноценно утверждению, что доступ к этому свойству может иметь только сам объект. Инкапсулированные свойства называются закрытыми (private), а свойства, доступные извне объекта, – открытыми (public). Например, рассмотрим объект нашей программы для моделирования бизнеса, имеющий "тип" HailOrderBusiness. Следует ожидать, что этот объект будет содержать метод, описывающий его реакцию на поступление заказа. Прочим объектам потребуется обращаться к данному методу в целях передачи некоторого заказа. Следовательно, доступ к этому методу должен быть открытым. Однако детальные сведения о том, как именно данное предприятие выполняет заказ, должны быть доступны только внутри объекта. Это означает, что все эти детали должны быть закрытыми. Большинство объектно-ориентированных языков программирования позволяет программисту определять непосредственно в описании класса, какие части объекта являются открытыми, а какие – закрытыми. Например, описание класса MailOrderBusiness на языке Java может выглядеть следующим образом:

class MailOrderBusiness extends SmallBusiness

{

public ...

private ...

private ...

public ...

}

Здесь ключевые слова public и private в начале описания каждого компонента используются для того, чтобы указать виддоступакним.

Вопросы для самопроверки

1.В чем заключается отличие между объектом и классом?

2.Предположим, что классы PartTimeEmployee (Временный работник) и FullTimeEmployee (Постоянный ра-

ботник) наследуют свойства класса Employee (Работник). Укажите, какими свойствами, по Вашему мнению, должен обладать каждый из этих классов.

3.Что такое инкапсуляция?

5.6.ПРОГРАММИРОВАНИЕ ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ*

Предположим, что нам поручили разработать программу для анимации объектов в компьютерной игре, включающей в себя бегущее стадо антилоп, марширующую колонну муравьев или, например, множество атакующих вражеских космических кораблей. Один из подходов к решению этой задачи – создание единой программы, которая управляла бы всей анимацией на экране дисплея. В задачу такой программы входило бы рисование каждой антилопы, которое (если требуется достаточно реалистичная анимация) предполагало бы, что программа должна непрерывно вычислять индивидуальные параметры для каждого из ста животных. Альтернативный подход состоит в разработке программы, управляющей анимацией отдельной антилопы, характеристики которой определяются параметрами, задаваемыми при запуске этой программы. Теперь анимацию на всем экране можно было бы создать посредством выполнения ста запусков этой программы и использования в каждом случае собственного набора параметров. Выполнив эти запуски одновременно, можно получить иллюзию, что сто отдельных антилоп бегут на экране в одно и то же время. (Хотя, строго говоря, одновременное выполнение ста запусков такой программы и превосходит возможности современных компьютеров, тем не менее, пять запусков программы, имитирующей атаку космическогокорабля, недолжнысоставить проблемы; на практике этот прием применяется довольно часто.)

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

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

Анимация в кинофильмах. Конечно, было бы неверным связывать начало современной анимации с однимединственным кинофильмом, однако многие считают фильм Звездные войны (Lucasfilm, 1977) началом современной волны компьютерной анимации в кинематографе. В настоящее время технология, использовавшаяся при создании таких классических мультфильмов Уолта Диснея, как Спящая красавица и Фантазия, и предусматривающая создание многочисленных, сделанных вручную кадров, заменена технологиями компьютерной анимации, требующими применения современных многопроцессорных компьютерных систем. Кинозритель может согласиться, что примеры, описанные в начале этого раздела (бегущие антилопы и марширующие полчища муравьев), вовсе не являются надуманными. Это – примеры из реальных кинофильмов, которые созданы с использованием компьютерных технологий (хотя и не обязательно так, как это описано в тексте, поскольку, в отличие от компьютерных игр, анимация в кино-

фильмах может быть разработана прежде, чем будет выполнена). Существуют ссылки на Web-страницы, посвященные анимации в кинофильмах. В частности, заинтересованный читатель может посетить следующие Web-узлы: http://www.lucasfilm.com, http://www.disney.go.com, http://www.pixar.com и http://www.pdi.com. Особенный интерес представляют Web-узлы http://www.antz.com иhttp://www.dreamworksgames.com.

Каждый из языков программирования стремится реализовать парадигму параллельной обработки со своей точки зрения, выраженной с помощью собственной терминологии. Например, то, что мы неформально называем запуском, в языке Ada именуется задачей (task), а в языке Java – потоком (thread). Таким образом, в программе на языке Ada одновременные действия осуществляются путем создания нескольких задач, тогда как программа на языке Java создает несколько потоков. В любом случае результатом является порождение нескольких процессов, которые выполняются так же, как и процессы под управлением многозадачной операционной системы. Поэтому далее мы договоримся ссылаться и на запущенную программу, и на задачу, и на поток как на процесс.

Возможно, наиболее важным действием, которое потребуется описывать в программе, выполняющей параллельную обработку данных, является создание новых процессов. Если мы хотим осуществить одновременно сто запусков программы анимации движения антилопы, нам потребуется синтаксическая конструкция, позволяющая выполнить эти действия. Запуск новых процессов обычно выполняется способом, очень напоминающим традиционный вызов процедуры. Разница лишь в том, что в традиционном способе вызывающий процедуру программный модуль приостанавливает свою работу, пока вызываемая процедура не закончит свое выполнение, тогда как при параллельной обработке вызывающий программный модуль продолжает свою работу одновременно с вызванной процедурой. Таким образом, чтобы воспроизвести бег ста антилоп на экране, нам нужно написать основную программу, которая просто генерирует сто запусков программы, имитирующей бег антилопы; причем каждый запуск выполняется со своим набором параметров, описывающим отличия одной антилопы от другой.

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

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

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

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

Один из способов решения этой проблемы заключается в описании подобных процессов в программе таким образом, что возможность их доступа к совместно используемым данным исключается до тех пор, пока работа с ними не станет безопасной. (Этот подход описан в разделе 3.4, где та часть процесса, которая имеет доступ к совместно используемым данным, была названа критической областью.) Опыт показал, что этот подход имеет недостаток, связанный с распределением задачи организации взаимно исключающего доступа между различными частями программы. В этом случае ошибка в описании любого из процессов, имеющих доступ к совместно используемым данным, способна вызвать повреждение всей системы в целом. По этой причине многие считают, что лучше объединять сами данные и средства контроля доступа к ним в единое целое. Такой управляющий механизм часто называют монитором (data monitor). Коротко говоря, в этом случае ответственность за исключение множественного доступа к данным налагается не на процесс, который стремится получить доступ, а на

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

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

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

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

Вопросы для самопроверки

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

2.Опишите два метода организации взаимно исключающего доступа к данным.

3 Эта задача имеет вполне естественное решение в объектно-ориентированных языках программирования, где и данные, и получающие к ним доступ процессы собраны в пределах одного объекта. В частности, для читателя может представлять определенный интерес использование команды synchronize в языке Java.

5.7. ДЕКЛАРАТИВНОЕ ПРОГРАММИРОВАНИЕ*

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

Логический вывод. Предположим, мы знаем, что лягушонок Кермит либо играет в спектакле, либо болен, и нам сказали, что сейчас лягушонок Кермит не играет в спектакле. Тогда мы можем сделать вывод, что лягушонок Кермит, должно быть, болен. Это – пример дедуктивного рассуждения, которое называется резолюцией.

Чтобы лучше понять этот принцип, примем сначала соглашение представлять простые высказывания отдельными буквами, а отрицание высказывания – символом ¬. Например, мы можем представить высказывание "Кермит – принц" буквой А, а высказывание "Мисс Пигги – актриса" – буквой В. Тогда выражение

A OR В

означает "Кермит – принц или мисс Пигги – актриса", а выражение

B AND ¬A

Означает: "Мисс Пигги – актриса, а Кермит – не принц". Для обозначения отношения "следует" мы будем использовать стрелку. Например, выражение

A → B

означает: "Если Кермит – принц, то мисс Пигги – актриса".

Вобщем виде принцип резолюции утверждает, что из двух высказываний

РOR Q и R OR ¬Q

мы можем вывести высказывание

R OR Q.

В этом случае мы говорим, что два исходных высказывания сводятся к третьему, которое называется резольвентой. Важно подчеркнуть, что резольвента – это логическое следствие исходных высказываний. Если исходные высказывания истинны, то резольвента также должна быть истинной. (Если Q – истинно, то R должно быть истинно, но если Q – ложно, то Р должно быть истинным. Следовательно, независимо от того, является Q истинным или ложным, либо Р, либо R должно быть истинным.)

Графически мы будем представлять резолюцию двух высказываний так, как показано на рис. 5.19, где мы написали исходные высказывания и изобразили линии, соединяющие их со своей резольвентой. Заметим, что резолюцию можно применять только к парам высказываний, которые выражаются в форме предложения, т.е. к высказываниям, элементарные компоненты которых можно соединять булевой операцией OR (ИЛИ). Таким образом, высказывание

P OR Q

выражено в форме предложения, в то время как для высказывания

P → Q

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

P→ Q

эквивалентно высказыванию в форме предложения

Q OR ¬P.

Совокупность высказываний является противоречивой, если все они не могут быть истинными одновременно. Другими словами, такая совокупность высказываний состоит из противоречащих друг другу высказываний. Простой пример такой совокупности – объединение высказывания Р и его отрицания ¬P. Специалисты-логики доказали, что повторное применение резолюции – это систематический метод проверки непротиворечивости множества предложений. Если повторный метод резолюции приводит к пустому предложению (результату резолюции предложения Р с предложением ¬P), то исходная совокупность высказываний является противоречивой. Например, на рис. 5.20 показано, что совокупность высказываний

является противоречивой.

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

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

(Маша находится в X) → (Машин ягненок находится в X),

гдеX означаетпроизвольноеместоположение иещеодновысказывание

(Маша находится дома).

Рис. 5.20. Резолюция высказываний (Р OR Q), (R OR ¬Q), ¬R и ¬Q

В формепредложения этивысказывания принимаютследующийвид:

(Машин ягненок находится в X) OR ¬(Маша находится в X)

и

(Маша находится дома).

На первый взгляд может показаться, что эти предложения не имеют компонентов, которые можно подвергнуть резолюции. Однако компоненты (Маша находится дома) и ¬ (Маша находится в X) почти противоречат друг другу. Задача заключается в том, чтобы установить истинность высказывания (Маша находится в X), которое является высказыванием о местонахождении вообще и о доме в частности.

Таким образом, частный случай первого высказывания имеет вид

(Машин ягненок находится дома) OR ¬(Маша находится дома)

который может быть сведен путем резолюции с высказыванием

(Маша находится дома)

к высказыванию вида

(Машин ягненок находится дома)

Процесс присваивания значений переменным (например, присвоение значения "дом" переменной X), который делает возможным выполнение резолюции, называется унификацией. Это процесс, который позволяет применять общие высказывания к частным приложениям в дедуктивной системе.

Язык Prolog. Prolog (PROgramming in LOGic – программирование в логике) – это декларативный язык программирования, базовый алгоритм решения задач которого основан на методе повторной резолюции. Программа на языке Prolog состоит из совокупности исходных высказываний, с помощью которых базовый алгоритм выполняет свои дедуктивные рассуждения. Компоненты, из которых состоят эти высказывания, называются предикатами. Предикат состоит из идентификатора предиката, за которым в скобках следуют аргументы предиката. Отдельный предикат представляет собой некоторый факт в отношении его аргументов, а идентификатор предиката обычно выбирается так, чтобы отразить его семантику. Таким образом, если мы хотим выразить тот факт, что Билл – отец Мери, мы можем использовать следующую предикатную форму:

parent(bill, mary).

Обратите внимание, что аргументы в этом предикате начинаются со строчных букв, даже если речь идет об именах собственных. Это происходит потому, что язык Prolog различает константы и переменные и требует, чтобы константы начинались со строчных букв, а переменные – с прописных.

Операторы в языке Prolog являются либо фактами, либо правилами. Каждый из операторов заканчивается точкой. Факт состоит из отдельного предиката. Например, тот факт, что черепаха (turtle) двигается быстрее улитки (snail), выражается оператором языка Prolog следующего вида:

faster(turtle,snail).

А тот факт, что кролик (rabbit) бегает быстрее черепахи, выражается оператором faster(rabbit,turtle).

Правило в языке Prolog – это оператор импликации (следования). Вместо записи оператора в виде X → Y программист на языке Prolog пишет "Y, если X", используя вместо слова "если" символы : –. Таким образом, правило "из того, что X быстрее (faster) Y, a Y быстрее Z, следует, что X быстрее Z" может быть выражено специалистом-логиком в следующем виде:

(faster(X,Y) AND faster (Y,Z)) → faster(X,Z)

На языке Prolog это же правило выражается следующим образом: faster(X,Z) :- faster(X,Y), faster(Y,Z).

Запятая, разделяющая термы faster(X,Y) и faster(Y,Z), представляет оператор конъюнкции AND (И). Такие правила легко могут быть преобразованы программным обеспечением языка Prolog в форму предложения.

Учтите, что система языка Prolog ничего не знает о значении предикатов в программе, она просто манипулирует высказываниями, формально применяя правило резолюции. Таким образом, описание всех относящихся к делу свойств предикатов в терминах фактов и правил входит в обязанности программиста. В этом смысле факты в языке Prolog обычно используются для конкретизации примеров предиката, а правила – для описания общих принципов. Этому подходу соответствуют предыдущие операторы, относящиеся к предикату faster. Два факта описывают конкретные примеры свойства "двигаться

быстрее", а правило – некое общее свойство. Заметим, что факт "кролик двигается быстрее улитки", хотя и не высказан явно, является следствием двух фактов, объединенных в соответствии с существующим правилом.

Большинство реализаций языка Prolog разработано для интерактивного применения. В этом смысле задача программиста – разработать совокупность фактов и правил, которые образуют множество исходных высказываний, используемых затем в дедуктивной системе. Установив такую совокупность высказываний, можно ввести с клавиатуры предложение (называемое в терминологии языка Prolog целью), которое система должна проверить. Как только перед дедуктивной системой языка Prolog будет поставлена некоторая цель, она применит операцию резолюции, пытаясь найти подтверждение того, что указанная цель следует из исходных высказываний. С помощью нашего набора высказываний, описывающих отношение faster, приведенные ниже предложения

faster(turtle, snail). faster(rabbit, turtle). faster(rabbit, snail).

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

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

faster(W, snail).

В результате программа сообщает faster(turtle, snail).

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

faster(rabbit, snail).

И наоборот, мы можем попросить программу найти примеры животных, которые более медлительны, чем кролик, поставив программе цель

faster(rabbit, W).

Поэтому, если мы поставим задачу faster{V, W),

то программа в конце концов найдет все отношения faster, которые могут быть выведены из исходных высказываний. Таким образом, единственная программа на языке Prolog может быть использована для подтверждения, что одно конкретное животное быстрее другого; для поиска всех тех животных, которые быстрее указанного животного; для поиска животных, которые медленнее указанного животного; а также для поиска всех отношений "быстрее/медленнее" между животными. Подобная гибкость просто захватывает воображение специалистов в области компьютерных наук.

Вопросы для самопроверки

1.Какие из высказываний R, S, T, U и V являются логическим следствием совокупности высказываний (¬R OR T OR S), (¬S OR V), (¬V OR R), (U OR S), (T OR ¬U) и (S OR V)?

2.Является ли следующая совокупность высказываний непротиворечивой? Обоснуйте свой ответ.

Р OR Q OR R; ¬R OR Q; R OR ¬P; ¬Q.

3. Предположим, что программа на языке Prolog состоит из операторов, выражающих отношение "экономнее" (thriftier): thriftier(carol, john).

thriftier(bill, sue). thriftier(sue, carol).

thriftier(X,Z) :- thriftier(x, Y), thriftier(Y,Z).

Перечислите результаты, которые можно получить для каждой из следующих целей:

а) thriftier (sue, V); б) thriftier(U, carol); в) thriftier(U, V).

Упражнения

(Упражнения, отмеченные звездочкой, относятся к разделам для дополнительного чтения.)

1.Что означает высказывание "язык программирования является машинно-независимым"?

2.Переведите следующую программу с псевдокода на машинный язык, описанный в приложении В. x ← 0;

while (х ≠ З) do

(x ← x+1)

3. Переведите приведенный ниже оператор на машинный язык, описанный в приложении В, предполагая, что переменные Length, Width и Halfway представлены как числа с плавающей точкой:

Halfway ← Length + Width

4. Переведите следующий оператор языка высокого уровня на машинный язык, описанный в приложении В, предполагая, что числа W, X, Y и Z представлены в двоичном коде и занимают в основной памяти один байт:

if(X equals 0)

then Z ← Y + W else Z ← Y + X

5.Для чего при трансляции операторов необходимо указывать тип данных, связанный с переменными в задаче 4? Почему многие языки высокого уровня требуют от программистов указывать тип каждой переменной в начале программы?

6.Назовите и опишите четыре существующие парадигмы программирования.

7.Предположим, что функция f получает два числа в качестве параметров и возвращает меньшее из них в качестве ре-

зультата. Если переменные w, х, у и z представляют собой числа, то какой результат будет возвращен этой функцией при вычислении выражения f(f(w,х),f(y,z))?

8.Предположим, что f – это функция, возвращающая в качестве результата строку, в которой все символы из входной строки переставлены в обратном порядке, а g – это функция, осуществляющая конкатенацию двух входных строк. Если х – строка "abcd", что вернет функция g(f(х),х)?

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

10.Опишите отличия, существующие между машинным языком и языком ассемблера.

11.Разработайте язык ассемблера для машины, описанной в приложении В.

12.Некий Джон Программер утверждает, что возможность объявления констант в программе является излишней, по-

скольку вместо них можно использовать переменные. Например, в разделе 5.2 можно описать переменную AirportAlt, а потом присвоить ей нужное значение в начале программы. Почему это решение хуже, чем вариант с использованием константы?

13.Опишите отличия, существующие между операторами объявления и выполняемыми операторами.

14.Объяснитеразницумежду литералом, константойипеременной.

15.Что такое приоритет оператора?

16.Что такое структурное программирование?

17.Чем отличается смысл символа равенства в операторе

if(X = 5) then (...)

от смысла этого же символа в следующем операторе присваивания?

X = Z + Y

18. Начертите блок-схему структуры, выраженной следующими операторами языков C++ и Java: for(x = 0; х < 8; ++х)

{…}

19. Начертите блок-схему структуры, выраженной следующими операторами языков С, C++ и Java: switch(suit)

{case "clubs": bid(l): break;

case "diamonds": bid(2): break; case "hearts": bid(3): break; case "spades": bid(4): break;

}

20. Если вы знакомы с нотной записью, проанализируйте принятый принцип записи нот с точки зрения языка программирования. Что здесь является управляющими структурами? Какой предусмотрен синтаксис для вставки комментариев? Какие музыкальные обозначения похожи на операторы for, представленные на рис. 5.8?

21. Перепишите следующий фрагмент программы, используя один оператор case вместо серии вложенных операторов if-then-else.

if (W = 5)

then (Z ← 7) else (if (W = 6)

then (Y ← 7) else (if (W = 7)

then (X ← 7) ) )

22. Выразите приведенную ниже запутанную последовательность операторов с помощью единственного оператора if- then-else.

if X > 5 then goto 80 X = X + 1

goto 90 80 X = X + 2 90 ...

23.Опишите отличия между транслятором и интерпретатором.

24.Предположим, что переменная X в программе описана как переменная типа integer. Какая ошибка будет обнаружена транслятором при выполнении следующего оператора?

X ← 2.5

25.Что означает выражение "язык программирования со строгой типизацией"?

26.Почему большой массив не всегда можно передать в вызываемую процедуру по значению?

27.Предположим, что процедура modify определена следующим образом:

procedure modify(Y) Y ← 7;

напечатать значение переменной Y;

Если параметры передаются по значению, что будет напечатано при выполнении следующего фрагмента программы? Что будет напечатано, если параметры передаются по ссылке?

X ← 5;

apply modify to X;

напечатать значение переменной X;

28. Предположим, что процедура modify определена следующим образом: procedure modify(Y)

Y ← 9;

напечатать значение переменной X;

напечатать значение переменной Y;

Допустим также, что X – это глобальная переменная. Если параметры передаются по значению, что будет напечатано при выполнении следующего фрагмента программы? Что будет напечатано, если параметры передаются по ссылке?

X ← 5;

apply modify to X;

напечатать значение переменной X;

29.Иногда фактический параметр передается в процедуру путем создания его копии, предназначенной для использования в процедуре (как если бы параметр передавался по значению), но после выполнения процедуры значение копии присваивается фактическому параметру перед тем, как будет продолжено выполнение вызывающей процедуры. В таких случаях говорят, что параметр передается по значению-результату. Что будет напечатано фрагментом программы из упражнения 28, если параметры передаются по значению-результату?

30.Какая неоднозначность кроется в следующем операторе?

X ← 3 + 2 * 5

31. Предположим, что небольшая компания имеет пять сотрудников и планирует увеличить их число до шести. Ниже приведены фрагменты из двух эквивалентных программ (используемых компанией), которые нужно изменить, чтобы отобразить изменение количества сотрудников. Обе программы написаны на языке, напоминающем Pascal. Укажите, какие изменения следует произвести в каждой программе. Какие осложнения возникают в первой программе и не возникают при использовании констант во второй программе?

Программа 1

.

.

.

DailySalary := TotalSal / 5;

AvgSalary := TotalSal / 5; DailySales := TotalSales / 5; AvgSales := TotalSales / 5;

.

.

.

Программа 2

.

.

.

сonst

NumEmpl = 5; DayWk= 5;

.

.

.

DailySalary: = TotalSal / DayWk;

AvgSalary := TotalSal / NumEpml;

DailySales := TotalSales / DayWk;

AvgSales := TotalSales / NumEmpl;

.

.

.

32.Нарисуйте синтаксическую диаграмму, представляющую структуру оператора while из псевдокода, описанного в

главе 4.

33.Разработайте совокупность синтаксических диаграмм для описания синтаксиса телефонных номеров, написанных в формате (044) 555-1234.

34.Разработайте совокупность синтаксических диаграмм для описания простого предложения на английском языке.

35.Напишите предложение, описывающее структуру строки, в соответствии с приведенной ниже синтаксической диа-

граммой. Затем нарисуйте дерево синтаксического анализа строки ххyхх.

36. Добавьте синтаксические диаграммы к диаграммам из вопроса 4 в разделе 5.4, чтобы получить совокупность диаграмм, определяющих структуру Танец, которая может быть структурой Ча-ча-ча или Вальс, где Вальс состоит из одной или более копий типа

вперед по_диагонали каданс

или

назад по_диагонали каданс.

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

х* у + у / х

38.Какую оптимизацию кода может выполнить генератор кода при создании машинного кода для следующего операто-

ра?

*41. Нарисуйте диаграмму (подобную диаграмме, показанной на рис. 5.20), представляющую последовательность операций резолюции, необходимых для того, чтобы показать, что совокупность высказываний (Q OR ¬R), (T OR R), ¬P, (P OR ¬T) и (R OR ¬P) противоречива.

42*. Является ли совокупность высказываний ¬R, (T OR R), (P OR ¬Q), (Q OR ¬T) и (R OR ¬P) противоречивой? Обоснуйте свой ответ.

43*. К каким выводам может прийти программа на языке Prolog, если поставить ей цель bigger(X, Lassie).

Исходными высказываниями являются следующие:

bigger(rex, lessie).bigger(fido, rex).bigger(spot, rex).bigger(X,Z) :- bigger(X,Y), bigger(Y,Z).

44*. К каким выводам придет программа на языке Prolog, если поставить ей цель eq(X, У.) .

Исходными высказываниями являются следующие:

qrteq(a b).qrteq(b, с).qrteq(c, a).qrteq(U, W :- qrteq(U, V), qrteq(V, W).eq(X, У) :- qrteq(X, Y), qrteq(Y, X).

45*. Какие проблемы могут возникнуть при выполнении машиной следующего фрагмента программы (описанной в разделе 1.7), в которой числа хранятся в 8-битовом формате с плавающей точкой?

X ← 0.01;while(X ≠ 1.00) do (вывести значение переменной X; X ← X + 0.01)

Ответы на вопросы для самопроверки Раздел 5.1

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

2.Основное отличие заключается в том, что ассемблер переводит каждую команду исходной программы в единствен-

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

3.Декларативная парадигма программирования основывается на разработке описания задачи, которую требуется решить. Функциональная парадигма требует от программиста описывать решение задачи в виде решений более мелких задач. Объектно-ориентированное программирование делает упор на описании компонентов предметной области задачи.

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

Раздел 5.2

1.Использование описательных констант позволяет улучшить читабельность программы.

2.Оператор объявления описывает терминологию, тогда как исполняемый оператор описывает этапы выполнения алгоритма.

3.Целый, действительный, символьный и логический (булев).

4.Структура if-then-else и структура цикла while являются наиболее распространенными.