Costas-Tyros_rus_MS

Глава 9: Типы данных

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

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

9.1.Примитивныетипыданных

Visual Prolog имеет множество примитивных типов данных:

integer: 3, 45, 65, 34, 0x0000FA1B, 845. Между прочим, 0x0000FA1B – шестнадцатеричное число,

то есть, число выраженное в базисе 16, которое имеет следующие цифры: 0, 1, 2,3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

real: 3.45, 3.1416, 2.18E 18, 1.6E 19, и т. д.

string: "pencil", "John McKnight", "Cornell University", и т.д. symbol : "Na", "Natrium", "K", "Kalium", и т.д.

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

/******************************** Project Name: primtype1

UI Strategy: console

*********************************/

% File main.pro implement main open core

constants

className = "main". classVersion = "primtype1".

clauses

classInfo(className, classVersion).

class predicates

energy:(real, real, real) procedure (i, i, o). family:(symbol, string) procedure (i, o).

clauses

energy(N, Z, E) : E= 2.18E 19*Z*Z/(N*N).

1 В данном случае автор имеет в виду типsymbol.

71

family("Na", "alkaline metal") : !. family(_, "unknown").

run(): console::init(), energy(4, 1, E1), energy(2, 1, E2), DeltaE= E1 E2,

stdio::write(DeltaE), stdio::nl, family("Na", F),

stdio::write("Na", " is an ", F), stdio::nl, succeed().

end implement main goal

mainExe::run(main::run).

9.2.Множества

Множества – это коллекции/собрания вещей. Вы определённо знаете, что в коллекциях не быва ет повторяющихся предметов. Я имею в виду, если у кого то есть коллекция наклеек, этот «кто то» не захочет иметь две копии одной и той же наклейки в своей коллекции. Каждый коллекционер стре миться обменять повторяющийся экземпляр на недостающий.

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

9.3.Множества чисел

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

буквой ? Я не знаю, но я могу сделать обосно

ванное предположение. Теория множеств была открыта Георгом Фердинанд Людвиг Филипп Канто ром (Georg Ferdinand Ludwig Philipp Cantor), русским, чьими родителями были датчане, но кто напи сал свою Mengenlehre на немецком! На этом языке целые числа могут иметь такое странное имя как

Zahlen.

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

за то, что они посчитают своей ценой. Однако, вопреки мнению чилийцев, Хорхе Луис Борхес (Jorge Luiz Borges) был величайшим писателем, кто писал на языке, отличающемся от греческого. Вы знаете, какая у него была любимая тема? Это была Теория Множеств, или Der Mengenlehre, как он

любил её называть.

Пожалуйста, мои аргентинские друзья, не злитесь. В конце концов, ваша страна четвёртая в спи

ске моих любимых стран, после Греции, Франции и Парагвая. Положение Парагвая в моём списке высоко, единственно потому, что Хосе Асунсьон Флорес(José Asunción Flores) был парагвайцем; для тех, кто не знает Хосе Асунсьон Флореса, послушайте его песню India, и, я уверен, что вы отметите

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

72

Парагвай на своей карте. Что до Аргентины, то это родина таких людей, как Бернардо Усай1 (Bernardo Houssay), Луис Федерико Лелуар2 (Luis Federico Leloir), Сезар Мильштейн3 (César Milstein), Адольфо Перез Эскивел (Adolfo Pérez Esquivel), Карлос Сааведра Ламас (Carlos Saavedra Lamas), Хорхе Луис Борхес (Jorge Luiz Borges), Альберто Кальдерон (Alberto Calderon), Альберто Гинастера (Alberto Ginaste­ ra), Хосе Кура (José Cura), Дарио Волонте (Dario Volonté), Вероника Дахл (Verónica Dahl), Каролина Мо нард (Carolina Monard), Че Гевара (Che Guevara), Диего Марадонна (Diego Maradona), Хуан Мануэль Фангио (Juan Manuel Fangio), Освальдо Голихов(Osvaldo Golijov), Ева Перон (Eva Peron), Гектор Паниц ца (Hector Panizza) и т. д.. Пока я не забыл, Хосе Асунсьон Флорес жил в Буэнос Айресе. Но давайте вернёмся к множествам.

Когда математик хочет сказать, что элемент является членом множества, он пишет что то напо добие

Дизъюнкция. Выражение

чисел так:

0

На неформальном языке это выражение означает, что рациональное число представляет собой дробь вида

Visual Prolog не имеет специального обозначения для множеств, но вы можете использовать спи ски для их представления. Например, выберите пункт Project/New из панели задач и заполните диа логовое окно Project Settings так:

General

Project Name: zermelo

UI Strategy: console

1Бернардо Альберто Усай – аргентинский физиолог, лауреат Нобелевской премии по физиологии и медицине 1947 года.

2Луис Федерико Лелуар – аргентинский биохимик французского происхождения, лауреат Нобелевской премии 1970 года.

3Русской транскрипции не нашёл, биохимик, поделил Нобелевскую премию по физиологии или медицине

(пишется вместе) в 1984 году с Niels K. Jerne и Georges Köhler.

4В русской математической школе используется одиночная вертикальная черта, уж не знаю, как, скажем, в Европе.

5В оригинале автор указывает как числитель, так и знаменатель рациональной дроби как элементы

множества (оба). Но это несущественно, так как если числитель , то эта дробь уже может изображать как положительные, так и отрицательные рациональные числа, а из множества уже исключён ноль.

73

Обратите внимание, что мы собираемся использовать консольную стратегию, не GUI. Выберите пункт Build/Build из панели задач чтобы вложить прототип класса zermelo в дерево проекта. Отре

дактируйте zermelo.pro как показано ниже. Снова постройте проект и запустите его, используя

Build/Run In Window.

implement main open core

clauses

classInfo("main", "zermelo"). run():

console::init(),

Q= [tuple(X, Y) || X= std::fromTo(1, 4), Y= std::fromTo(1, 5)],

stdio::nl,

stdio::write(Q), stdio::nl, stdio::nl,

foreach tuple(Num, Den)= list::getMember_nd(Q) do stdio::write(Num, "/", Den,", ")

end foreach, stdio::nl.

end implement main goal

mainExe::run(main::run).

Вы можете спросить, почему я назвал программу именем немецкого математика Эрнста Фрид рих Фердинанд Цермело (Ernst Friedrich Ferdinand Zermelo). Одной из причин может быть то, что он был назначен на почётную должность во Фрайбурге́ в Брайсгау́ (Freiburg im Breisgau) в 1926, который

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

Q= [tuple(X, Y) || X= std::fromTo(1, 4),

foreach tuple(Num, Den)= list::getMember_nd(Q) do stdio::write(Num, "/", Den,", ")

end foreach,

говорит компьютеру делать write(Num, "/", Den,", ") для каждого кортежа (Num, Den), ко торый является членом списка Q.

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

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

74

9.4.Иррациональные числа

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

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

ждает, что , т. е.,

9.1

Вы также можете выбрать меру так, что p и q не будут иметь общих множителей. Например, если и p и q делимы на 2, вы можете удвоить длину меры, получая значения

более не делимые на 2. Например, если p=20 и q=18, и вы удваиваете длину меры, вы получаете p=10 и q=9. Таким образом, допустим, что вы брана мера такая, что p и q одновременно не чётные. Но из уравнения 9.1 получается, что q2 чётное. Но если q2 чётное, то q тоже чётное. Вы можете проверить, что квадрат нечётного числа всегда нечётное число. Так как q чётное, вы можете подставить 2×n вместо него в уравнение 9.1.

Уравнение 9.1 показывает, что q чётное; уравнение 9.2 доказывает,

что p тоже чётное. Но это противоречит нашему допущению, что p и q не

одновременно чётные. Следовательно, p и q не могут быть целыми чис Рисунок 9.1 Думающий грек лами в уравнении 9.1, которое вы можете переписать так:

√2

Число √2, которое даёт отношение между стороной и диагональю любого квадрата, не элемент

, или другими словами, √2 tapontum), греческий философ.

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

9.5.Действительныечисла

Множество всех чисел, целых, иррациональных и рациональных называется , или множеством действительных чисел. В Visual Prolog, называется integer – целым, хотя множество integer по крывает не все целые числа, но все равно их количество достаточно чтобы удовлетворить вашим ну ждам. Действительные числа Visual Prolog принадлежат множеству real, подмножеству .

1 Доказательство несоизмеримости стороны квадрата и его диагонали, приведенное ниже автором, было известно еще Пифагору

75

integer – Целые числа между 2147483648 и 2147483647.

real – Действительные числа должны быть записаны с десятичной точкой: 3.4, 3.1416, etc. string – Заключённая в кавычки строка символов: "3.12", "Hippasus", "pen", etc.

char – Символы в одинарных кавычках: 'A', 'b', '3', ' ', '.', etc.

9.6.Математика

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

что такое тип и как типы связаны с теорией чисел. В качестве бонуса я надеюсь, что читающие лите ратуру студенты найдут книги Боргеса (Borges’) более лёгкими для усвоения после прочтения моего

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

9.7.Форматирование

Метод format создаёт неплохие представления примитивных типов данных для вывода. К при меру, хорошо бы отображать цвета, используя шестнадцатеричные числа. В этом представлении, ос новные цвета выглядят так: 0x00FF0000 (красный), 0x0000FF00 (зелёный), и 0x000000FF (синий). Тем не менее, если вы попытаетесь вывести эти значения, используя stdio::write/n, вы получите их в десятеричном базисе. Используя string::format/n, как показано ниже, вы получите распечатку примитивных цветов в шестнадцатеричном виде.

/******************************* Project Name: primtype2

UI Strategy: console

********************************/

% File main.pro implement main open core

constants

className = "main". classVersion = "primtype2".

clauses

classInfo(className, classVersion).

class predicates

color:(symbol, integer) procedure (i, o).

clauses

color("red", 0x00FF0000) : !. color("blue", 0x000000FF) : !. color("green", 0x0000FF00) : !. color(_, 0x0).

run(): console::init(), color("red", C),

S= string::format("%x\n", C), stdio::write(S), stdio::nl, succeed().

end implement main

76

goal mainExe::run(main::run).

Первый аргумент функции format определяет, какой вы хотите видеть распечатку. В примере ар гумент “%x\n”: вы хотите шестнадцатеричное отображение числа, завершающееся возвратом карет ки (\n). Аргументы, следующие за первым, показывают данные, которые вы хотите напечатать. Вот несколько примеров форматирования:

Спецификацией поля форматирования является %[ ][0][width][.precision][type], где дефис ( ) означает, что поле будет выравнено по левому краю, выравнивание по правому краю принято по

умолчанию; ноль перед width заполняет форматированную строку нулями до тех пор, пока не будет достигнута минимальная ширина; width определяет минимальный размер поля; precision определяет

точность числа с плавающей точкой; наконец, type может быть f (число с фиксированной точкой), e (научная запись действительных чисел), d (десятичное целое), x (шестнадцатеричное целое), o (вось меричное). Строки отображаются как “%s”. Вы можете добавить любое сообщение в спецификацию формата; вы также можете добавить возврат каретки (“\n”).

9.8.Домены

Вам могут потребоваться иные типы данных кроме примитивов, предложенных Visual Prolog. В этом случае, вам нужно определить новые типы данных, которые вы будете помещать в ваш код. В предыдущих главах вы уже изучили, как объявлять домены; вы также изучили, как создавать состав ные структуры данных, такие, как списки. Следовательно, всё, что нам следует сделать в этом разде ле, это вспомнить уже усвоенные идеи и подвести итог тому, что мы изучили.

9.8.1. Списки

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

Когда у вас есть объявление домена, вы можете использовать его как любой другой примитив ный тип. В случае списков объявление домена не обязательно, так как можно использовать типы вроде real*, string* или integer* прямо в объявлении предиката, как в программе на рис. 9.2.

9.8.2. Функторы

Ветвь логики под названием исчисление предикатов имеет тип данных, называемый функцио нальный символ (functional symbol). Функциональный символ имеет название, или функтор, за кото

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

77

•author("Wellesley", "Barros", 1970)

•book( author("Peter", "Novig", 1960),"Artificial Intelligence")

•date("July", 15, 1875)

•entry("Prolog", "A functional language")

•index("Functors", 165)

•sunday

/******************************* Project Name: newdomains

UI Strategy: console

********************************/

% Файл main.pro implement main open core

class predicates

sum:(real*, real) procedure (i, o).

clauses

classInfo("main", "newdomains").

sum([], 0) : !.

sum([X|Xs], X+S) : sum(Xs, S).

run(): console::init(), sum([1, 2, 3, 4, 5, 6], A),

stdio::writef("The sum is % 4.0f", A). end implement main

goal mainExe::run(main::run).

Рисунок 9.2 Объявления списков

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

Следующий пример вычисляет день недели для любой даты между годами 2000 и 2099. Он име ет следующие объявления доменов:

78

/******************************* Project Name: dayOfWeek

UI Strategy: console

********************************/

%Файл main.pro

%This program calculates the day of the week

%for the years between 2000 and 2099. implement main

open core

constants

className = "main". classVersion = "dayOfWeek".

domains

year= integer.

day= sun; mon;tue; wed; thu; fri; sat; err.

month= jan;feb;mar;apr;may;jun;jul;aug;sep;oct;nov;dec. month_code= m(month, integer).

numberOfDays= nd(integer); february.

class predicates

dayOfWeek:(integer, day) procedure (i, o).

calculateDay:( string Month, integer Day_of_the_month, year Y, day D) procedure (i, i, i, o).

class facts

monthCode:(string, month_code, numberOfDays).

clauses

classInfo(className, classVersion).

monthCode("January", m(jan, 6), nd(31)). monthCode("February", m(feb, 2), february ). monthCode("March", m(mar, 2), nd(31)). monthCode("April", m(apr, 5), nd(30)). monthCode("May", m(may, 0), nd(31)). monthCode("June", m(jun, 3), nd(30)). monthCode("July", m(jul, 5), nd(31)). monthCode("August", m(aug, 1), nd(31)). monthCode("September", m(sep, 4), nd(30)). monthCode("October", m(oct, 6), nd(31)). monthCode("November", m(nov, 2), nd(30)). monthCode("December", m(dec, 4), nd(31)).

dayOfWeek(0, sun) : !. dayOfWeek(1, mon) : !.

79

dayOfWeek(2, tue) : !. dayOfWeek(3, wed) : !. dayOfWeek(4, thu) : !. dayOfWeek(5, fri) : !. dayOfWeek(6, sat) : !. dayOfWeek(_, err).

calculateDay(Month, MD, Year, D) :

Y= Year 2000, % Last digits of Year

monthCode(Month, m(_M, C), _), % Get month code !,

S= Y+Y div 4+C+MD,

R= S mod 7, /* Day of the week as an integer between 0 (sunday) and 6 (saturday) */

dayOfWeek(R, D). % Get functional symbol of the day calculateDay(_, _, _, err).

run(): console::init(),

calculateDay("May", 3, 2005, R), stdio::write("Day of the week: ", R), stdio::nl, succeed(). % place your own code here

end implement main goal

mainExe::run(main::run).

9.9. Представления о логике: Предложения Хорна

Предложение Хорна имеет самое большее один положительный литерал. Для математиков хор новы предложения обладают интересными свойствами. Однако, для компьютерных учёных они ещё

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

…,

…,

…,

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

Пойдёт дождь, если ласточки летают низко над землёй.

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

80