Пратт Т. Языки программирования. Разработка и реализация

Подождите немного. Документ загружается.

657

принятой <=), <, > и >=. Но операция = означает «то же самое», так, X = 1 + 2 означа

ет, что X есть то же самое, что и выражение 1 + 2. Операция is означает вычислить;

результатом выполнения X is 4+1 будет присваивание переменной X значения 5:

|?- X = 1+2.

X = 1+2 ? – X ïðèñâîåíî âûðàæåíèå '1+2'

yes

|?- X is 1+2.

X = 3 ? – X ïðèñâîåíî çíà÷åíèå 3

yes

Изза такого смысла операции = выражение 1 + 3 = 2 + 2 будет ложным. Чтобы

вычислять подобные сравнения, необходимо определить функцию равенства samevalue,

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

samevalue(X,Y) :– A is X, B is Y, A=B.

Тогда samevalue(1 + 4,2 + 3) возвратит значение true.

Операторы

Факты. Факты — это отношения, которые устанавливаются в процессе выполне

ния операции consult, которая добавляет новые факты и правила в базу данных.

Они оформлены в виде nкортежа f(a

, a

,…, a

) и устанавливают отношение

между n аргументами в соответствии с отношением f. В ответ на ввод функции,

consult(user), которая добавляет данные к базе данных, пользователь может ввести

employer(zelkowitz,university).

employer(smith,nasa).

employer(pratt,nasa).

publisher(zelkowitz,prenticehall).

publisher(pratt,prenticehall).

Эти отношения инвариантны. Они не могут быть унифицированы к некоторо

му другому значению.

Правила. Правила — это импликации, которые задаются во время операции

consult. Синтаксис для правил следующий:

employed(X) :–employer(X,_). /*X ðàáîòàþùèé, åñëè ó X èìååòñÿ ðàáîòîäàòåëü*/

employedby(X) :–employer(X,Y), write(Y).

Правило employed только проверяет, что в базе данных имеется отношениепре

дикат employer(X, ÷òî-òî), таким образом, конкретный работодатель игнорируется.

Но правило employedby(X) использует отношение employer(X,Y) для отображения

имени работодателя:

employed(pratt)

yes

employedby(zelkowitz)

university

yes

Запросы. Запросы состоят из последовательности термов, завершающейся

точкой:

, q

,…,q

Мы хотим, чтобы ассоциация для переменных в каждом терме была такой, что

бы все термы были истинными. Запрос выполняется следующим образом: унифи

П.11. Prolog

658 Приложение. Обзоры языков

цируется терм q

(возможно, путем обращения к определению q

в базе данных);

если он истинен, то терм q

унифицируется с помощью своего определения. Если в

какойлибо точке процесс унификации сообщает об отказе, то он возвращается к

предыдущему правильному выбору и пробует альтернативный путь, как описано

в разделе 8.4.3.

Правила могут быть скомбинированы в сложные запросы. Например, вопрос

«Кто работает в NASA и написал книгу, которая издана в „ПрентисХолл“» может

быть выражен с помощью запроса:

employer(X,nasa),publisher(X,prenticehall).

X = pratt?

yes

Хотя и zelkowitz, и pratt унифицируют предикат publisher(X,prenticehall), только

pratt унифицирует предикат employer(X,nasa).

Отсечение. Процесс вычисления запросов часто требует выполнения значи

тельного числа откатов. Для экономии времени было предложено отсечение. От

сечение (обозначается символом «!») предписывает, что если в запросе необходи

мо применить откат, то мы получаем отказ в данном запросе. Действие отсечения

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

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

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

Например, если бы предыдущий запрос был записан в виде

employer(X,nasa),!,publisher(X,prenticehall).

тогда мы получили бы для него отказ. Сначала был бы унифицирован предикат

employer(X,nasa), но получили бы отказ при унификации предиката èçäàòåëü(X,Ïðåíòèñ-

Õîëë)

атомом smith. Обычно в такой ситуации Prolog выполнил бы откат и начал

поиск другой подстановки для унификации предиката employer(X,nasa), но отсече

ние запрещает это делать. Отсечения не имеют никакого действия в прямом на

правлении.

Проблемы с отрицанием. Отрицание определяется следующим образом:

not(X):- X,!,fail.

not(_).

Заметим, это не соответствует тому, что следует возвратить истину, если X лож

но. Если X истинно, то not(X) вычислит X как èñòèíà, откажет на fail, но отсечение

приведет к отказу этого правила. Если X ложно, то при вычислении первого прави

ла получим отказ, но not(_)выполнится успешно. Однако при вычислении перво

го правила можно получить отказ, если X ëîæíî или просто отсутствует в базе дан

ных. Разницу можно увидеть на примере следующих двух запросов:

X is 5, not(X=10).

not(X=10),X is 5

В первом случае X унифицируется целым 5 и not(X=10) выполнится успешно. Во

втором случае X сначала унифицируется целым 10 и возникает отказ при вычисле

нии not(X=10), так что унификация целым 5 никогда не выполняется.

Ввод и вывод

Для большинства простых запросов, чтобы записать ответы, вполне достаточно

вывода по умолчанию унифицированных переменных. Тем не менее в Prolog су

659

ществует также функция write для вывода на печать любой строки. Например,

write('abc') напечатает abc. Функция nl печатает символ новой строки.

Стандартные функции

В большинство реализаций языка Prolog включены следующие встроенные функ

ции, которые помогают генерировать программы:

consult(èìÿ_ôàéëà) Читает файл с заданным именем и добавляет новые факты и правила в базу

данных. èìÿ_ôàéëà может быть записано также в виде 'èìÿ_ôàéëà', если имя

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

ñonsult(èìÿ_ôàéëà) часто может быть заменено просто на [èìÿ_ôàéëà]

reconsult(èìÿ_ôàéëà)

Переписывает отношения в базе данных

fail Всегда означает отказ

see(èìÿ_ôàéëà) Считывает входные данные из указанного файла в виде наборов правил

write(òåðì) Выводит на печать терм

tell(èìÿ_ôàéëà) Направляет вывод функции write в файл с заданным именем

told Закрывает файл, использовавшийся в функции tell, и перенаправляет вывод

функции write на стандартное устройство вывода (терминал)

nl Переходит на новую строку (при вводе и выводе)

atom(X) Предикат, который возвращает èñòèíó, если X является атомом (строковой

константой или именем переменной)

var(X) Предикат, который возвращает истину, если X является переменной

integer(X) Предикат, который возвращает истину, если X является целым числом

trace Включает отладочный режим трассировки программы, показывая

выполнение каждого шага программы

notrace Выключает отладочный режим трассировки программы

П.12. Smalltalk

Пример с пояснениями

Мы возвращаемся к нашему примеру суммирования элементов массива. В этой

версии данные хранятся в файле data. Для входных данных

412345123450

программа, приведенная в листинге П.14, даст следующий результат:

1 2 3 4 SUM =10

1 2 3 4 5 SUM =15

Листинг П.14. Пример суммирования элементов массива на языке Smalltalk

1 Array variableSubclass: #Datastore

2 instanceVariableNames: ''

3 classVariableNames: 'DataFile ArrIndex Storage Size'

4 poolDictionaries: ''

5 category: nil !

6 !Datastore class methodsFor: 'instance creation'!

7 new

8 DataFile _ FileStream open:'data' mode: 'r'.

9 Storage _ Array new: 99.

10 Size _ 99.

продолжение 

П.12. Smalltalk

660 Приложение. Обзоры языков

Листинг П.14 (продолжение)

11 self reset !!

12 !Datastore class methodsFor: 'basic'!

13 asgn: aValue

14 ArrIndex _ ArrIndex + 1.

15 Storage at: ArrIndex put: aValue !

16 getval

17 ArrIndex _ ArrIndex + 1.

18 ^Storage at: ArrIndex !

19 nextval

20 ^((DataFile next) digitValue - $0 digitValue)!

21 reset

22 ArrIndex _ 0 !!

23 |k j sum|

24 Datastore new.

25 "Initialize k"

26 [(k _ Datastore nextval) > 0]

27 whileTrue: [1 to: k do: [(j _ Datastore nextval) print.

28 Character space print.

29 Datastore asgn: j].

30 Datastore reset.

31 sum _ 0.

32 'SUM =' print.

33 1 to: k do: [sum _ sum + Datastore getval].

34 sum printNl.

35 Datastore reset] !

Строка 1. Здесь определяется Datastore как подкласс класса Array.

Строка 2. Пустой список указывает, что в любом объекте класса Datastore от

сутствуют локальные переменные. В данном примере все данные обрабатываются

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

локальных переменных.

Строка 3. Переменные DataFile, ArrIndex, Storage и Size являются глобальными

переменными объектов класса Datastore.

Строки 4–5. Эти строки нужны для корректного определения ключевого мето

да, но их обсуждение выходит за рамки данного примера. Символ (!) означает ко

нец определения подкласса.

Строка 6. Здесь указано начало определения методов для класса Datastore, то

есть вызовов методов вида

Datastore èìÿ_ìåòîäà

Строка 7. Определяется метод new. Этот метод открывает файл входных дан

ных и инициализирует массив, в котором будут храниться данные.

Строка 8. Файл data открывается в режиме 'r' для чтения. Класс FileStream

возвращает объектдескриптор для этого файла, который присваивается пе

ременной DataFile — глобальной переменной в определении подкласса Datastore

в строке 3.

Строка 9. Метод new: посылается классу Array с параметром 99. Возвращается

массив из 99 элементов, который присваивается переменной Storage, объявленной

в строке 3.

Строка 11. Метод reset посылается объекту, представленному переменной self,

который является объектом, куда изначально посылался метод new. Это приводит

661

к вызову метода reset для класса Datastore, определенному в строке 21. Два симво

ла (!) указывают завершение определения вызываемых методов для класса Datastore

из строки 6.

Строка 12. Для класса Datastore определяются основные операционные методы.

Строки 16–18. Унарный метод getval увеличивает значение переменной ArrIndex,

представляющей индекс массива, на единицу и возвращает соответствующий эле

мент массива (^), используя метод at: для экземпляров массивов, в данном случае

для массива Storage.

Строки 19–20. Метод nextval для файлового объекта DataFile возвращает сле

дующий символ из файла. Метод digitValue, переданный этому символу, возвращает

целое значение этого ASCIIсимвола. Вычитая из этого числа значение символа 0,

получаем правильное численное значение для цифры целого числа (например,

Character 0 ($0) возвратит целое число 0, Character 1 ($1) возвратит целое число 1

и т. д.).

Строка 23. k, j и sum определяются как локальные переменные. Все переменные

объявляются без указания их типа, так как типы присваиваются динамически.

Строка 24. Вызывается метод new класса DataStore, объявленный в строке 7,

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

Строка 25. Это комментарий Smalltalk.

Строка 26. Классу Datastore передается метод nextval, который возвращает сле

дующее целочисленное значение из файла. Этот объект присваивается перемен

ной k и сравнивается со значением 0. Результатом выполнения этого блока являет

ся либо булев объект true, либо булев объект false.

Строки 27–29. Метод whileTrue: с параметромблоком передается булеву объек

ту строки 26. Если этот объект является объектом false, то блок игнорируется; если

true, то блок выполняется и условный блок строки 26 вычисляется снова. Таким

образом, реализуется стандартный цикл while.

Фактически блок представляет собой конструкцию цикла do. Метод to:do: полу

чает в качестве параметров счетчик k и блок операторов и передает их целочислен

ному объекту 1. Результатом является циклическое выполнение блока от 1 до k.

Метод Datastore nextval возвращает следующий символ из файла, присваивает

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

операторов.

Строки 30–32. Вызывается метод reset класса Datastore и переменной sum при

сваивается значение 0. Распечатывается строка 'SUM ='.

Строка 34. Распечатывается значение sum. После этого метод printNl вставляет

символ новой строки.

Строка 35. Массив переводится в исходное состояние для нового суммирова

ния. Символ (!) означает выполнение операторов, расположенных в строках 23–34.

П.12.1. Объекты данных

Переменные представляются цепочками строчных букв. В Smalltalk использу

ется соглашение, по которому имена переменных могут состоять из нескольких

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

anInteger, aParameter, theInput, myInputFile и т. д. Имена глобальных объектов дан

П.12. Smalltalk

662 Приложение. Обзоры языков

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

ются объектами (то есть объявленные в определении класса объекта), начинают

ся с прописных букв. Строки заключаются в одинарные кавычки (апострофы),

а символьные данные начинаются с символа $. Так, например, символ "a" задает

ся как $a. Выполнение программ является динамическим. Поэтому типы пере

менных не задаются, а устанавливаются, изменяются и запрашиваются во время

выполнения.

Элементарные типы данных

В Smalltalk классы определяют типы. Множество предопределенных классов пе

речислено в табл. П.2.

Таблица П.2. Иерархия стандартных классов Smalltalk

Class Object (суперкласс — продолжение)

Object Delay

Autoload FileSegment

Behavior Link

ClassDescription Process

Class SymLink

Metaclass Magnitude

BlockContext Character

Boolean Date

False LookupKey

True Association

CfunctionDescriptor Number

Cobject Float

Collection Integer

Bag Time

Mapped Collection Memory

SequenceableCollection ByteMemory

ArrayedCollection WordMemory

Array Message

ByteArray MethodContext

CompiledMethod MethodInfo

String ProcessorSheduler

Symbol SharedQueue

Interval Stream

LinkedList PositionableStream

Semaphore ReadStream

OrderedCollection WriteStream

SortedCollection ReadWriteStream

Set FileStream

Dictionary Random

IdentityDictionary TokenStream

SystemDictionary UndefinedObject

663

Структурированные типы данных

В Smalltalk не имеется встроенных структурированных данных. Объекты данных

создаются методами из определений классов.

Массивы. Массивы создаются при помощи ключевого метода new: класса Array,

причем параметром метода является размер массива. Значения элементов масси

ва задаются ключевым методом at:, как описано в разделе 7.2.5:

arrayVariable at:index put:arrayvalue

Метод at: используется также для получения значений элемента массива:

arrayVariable at:index

Множества. Множества создаются методом new: класса Set. Ключевой метод

add: помещает в множество новый объект, метод remove: удаляет объект из множе

ства, а метод includes: возвращает true или false в зависимости от того, входит ли

параметр метода в данное множество.

Другие структуры. В Smalltalk имеются стандартные определения классов для

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

перечисленных в табл. П.2. В вашей локальной системе могут быть и другие стан

дартные определения классов. Для того чтобы узнать атрибуты каждого такого

класса, можно использовать метод inspect.

Определяемые пользователем типы

В Smalltalk полиморфизм и возможность задания пользовательских функций

обеспечиваются наследованием методов в определениях классов.

Представление объектов в памяти

В Smalltalk используется динамическое управление памятью и указатели. Каждая

переменная имеет указатель на соответствующий контекст для объектов этого

класса.

П.12.2. Управление последовательностью

действий

Выражения выполняются в порядке их задания. Операторы отделяются друг от

друга точками. Определения методов завершаются символом «!», а определения

классов завершаются символом «!!».

Выражения

Выражения в Smalltalk чрезвычайно просты. Существует только три уровня стар

шинства:

 унарный метод;

 бинарный метод;

 ключевой метод.

В пределах каждого уровня выполнение методов осуществляется слева напра

во. Например, выражение 2 + 3 * 4 содержит два бинарных метода с одинаковым

старшинством, поэтому правильной его интерпретацией будет ((2 + 3) * 4) или

П.12. Smalltalk

664 Приложение. Обзоры языков

, а не 14, как можно было ожидать. Возможно, это наиболее необычное свойство

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

Также следует внимательно относиться к таким выражениям, как 1 + 2 print.

Так как print — это унарная операция, то при расстановке приоритетов получим

1 + (2 print), то есть, вероятно, не то, что подразумевалось. Для того чтобы безо

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

использовать скобки.

В Smalltalk определен обычный набор методов сравнения (например, <, <=, =, >,

>=). Метод notequal (не равно) обозначается символами ~=.

Также определены некоторые дополнительные методы вычислений. Наиболее

полезны из них следующие:

 // — частное (целочисленное деление);

 \\ — остаток;

 gcd: — наибольший общий делитель (то есть m gcd:n для целых чисел m и n).

Операторы

Объявления. Синтаксис |variable| определяет локальную переменную, область

видимости которой распространяется до конца определения текущего метода (ко

торое завершается символом «!»).

Присваивание. Основной оператор присваивания имеет вид

ïåðåìåííàÿ _ âûðàæåíèå

В данном случае вычисляется âûðàæåíèå и полученное значение присваивается

ïåðåìåííîé. Выражение может быть как обычными данными, так и выполняемым

блоком — таким образом конструируется оператор if. В GNU Smalltalk можно кро

ме стандартного оператора присваивания «_» использовать и оператор :=.

Блок. Блок имеет следующий синтаксис

[ :ëîêàëüíàÿ_ïåðåìåííàÿ | ñïèñîê îïåðàòîðîâ]

где ëîêàëüíàÿ_ïåðåìåííàÿ — необязательный компонент, представляющий собой спи

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

является данный блок. Метод value, посланный блоку, инициирует его выполне

ние. Обычно блоки присваиваются некоторой переменной x и затем выполняются,

посылая сообщение value соответствующему блоку (например, x value).

Условные операторы. Условные операторы создаются посылкой метода

ifTrue:ifFalse: объектам true или false. Объект true будет выполнять блоковый

параметр ifTrue, тогда как объект false будет выполнять блоковый параметр ifFalse:

Áóëåâî_âûðàæåíèå

ifTrue: [áëîê]

ifFalse: [áëîê]

Áóëåâî_âûðàæåíèå будет вычислено равным true или false. Это значение будет передано

ключевому сообщению ifTrue:ifFalse, после чего выполнится соответствующее действие.

Операторы цикла. Аналогично условным операторам, для создания цикличе

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

Простые итерации. Метод timesRepeat: передает целому числу некоторый блок,

в результате чего этот блок выполняется указанное количество раз. Так,

count timesRepeat:áëîê

665

выполнит блок count раз.

Фиксированное повторение. Код Smalltalk

íà÷àëüíîå_çíà÷åíèå to êîíå÷íîå_çíà÷åíèå by øàã do: [áëîê]

аналогичен циклу в языке FORTRAN:

DO I = íà÷àëüíîå_çíà÷åíèå, êîíå÷íîå_çíà÷åíèå, øàã

ñïèñîê_îïåðàòîðîâ

END DO

Как и в языке FORTRAN, øàã не является обязательным параметром. Можно

получить доступ к текущему значению индекса цикла, задавая локальную пере

менную в цикле:

íà÷àëüíîå_çíà÷åíèå to: êîíå÷íîå_çíà÷åíèå by: øàã do: [:LoopVar | áëîê]

Цикл while. Конструкция, аналогичная оператору while других языков, может

быть задана следующим образом:

[Áóëåâî âûðàæåíèå]

whileTrue: [áëîê]

где áëîê будет выполняться, пока áóëåâî âûðàæåíèå остается истинным.

Ввод и вывод

Функции ввода и вывода обеспечиваются классами ReadStream, WriteStream и их под

классами.

Метод print можно послать любому классу для распечатки его значения. Метод ptintNL

действует так же, как print, но еще и добавляет символ новой строки в конце вывода.

Метод fileIn: класса FileStream считывает и выполняет файл. Например, в ре

зультате действия

FileStream fileIn: èìÿ_ôàéëà

читается файл с заданным именем и обрабатывается Smalltalk. Это позволяет чи

тать и выполнять другие программы во время выполнения основной программы.

Метод open:mode: класса FileStream открывает файл. Так,

FileStream open:èìÿ_ôàéëà mode:ðåæèì

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

ся только для чтения (если параметр ðåæèì задан как 'r') или только для записи

(если параметр ðåæèì задан как 'w').

Метод next, примененный к экземплярам класса FileStream, возвращает следу

ющий символ файла. Если файл с дескриптором f был открыт с помощью приве

денного выше метода open:mode:, то

f next

возвращает следующий символ из f.

Определения классов

Определения классов состоят из четырех компонентов:

1) имени класса;

2) суперкласса данного класса;

3) объявлений переменных, доступных экземплярам класса;

4) методов, используемых экземплярами класса.

П.12. Smalltalk

666 Приложение. Обзоры языков

Подклассы определяются при помощи следующего синтаксиса:

èìÿÑóïåðêëàññà subclass: #èìÿÍîâîãîÊëàññà

instanceVariableNames: ïåðåìåííûåÝêçåìïëÿðà

classVariableNames: ïåðåìåííûåÊëàññà

poolDictionaries: ' '

category: nil !

где èìÿÍîâîãîÊëàññà — это имя нового подкласса; ïåðåìåííûåÝêçåìïëÿðà — список всех

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

объекта и которые, таким образом, формируют структуру нового подкласса; ïåðå-

ìåííûåÊëàññà

— это список переменных, которые совместно используются во всех

экземплярах класса. Компонент category определяется с целью поддержки докумен

тирования класса, чтобы общие методы можно было сгруппировать вместе; на се

мантику языка этот компонент класса не оказывает никакого влияния. Компонент

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

в специфицированных классах системы вне нормальной иерархии наследования.

Определение методов. Методы, которые определяются для экземпляров клас

са, добавляются к определению класса с помощью следующего синтаксиса:

!èìÿÊëàññà methodsFor: 'usage'!

ìåòîä

ñïèñîê_îïåðàòîðîâ

ìåòîä

ñïèñîê_îïåðàòîðîâ

…

ìåòîä

ñïèñîê_îïåðàòîðîâ

где usage задает категорию определяемого метода.

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

ния класса, то его синтаксис имеет вид

!èìÿÊëàññà class methodsFor: 'usage'!

Например, в листинге П.14 показано объявление методов для создания экзем

пляра класса DataStore и задания основных операций для этого класса.

Управление памятью

Локальная среда ссылок. Наследование объектов формирует базу для локальной

среды ссылок. Если метод, переданный объекту, не найден в нем, то вызывается класс

родительского объекта. Аналогично в пределах данного метода доступны только пе

ременные, заданные в определении класса или локально объявленные в нем.

Доступ к экземпляру класса, которому был послан метод, осуществляется с по

мощью объекта self. Чтобы обратиться в методе к родительскому классу, следует

сослаться на объект super, например:

new

^ super new

в результате чего метод new сначала вызывает метод new в родительском классе и за

тем возвратит его экземпляр. Это позволяет модифицировать семантику данного

метода в подклассе, а также вызывать родительский метод.

Общая среда ссылок. Все имена классов являются глобальными, то есть изве

стны во всей программе, поэтому объекты этих классов могут быть вызваны из