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

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

627

чается как string list. Аналогично, [[1,2], [3,4]] будет типа int list list или спи

сок списков целых величин.

Функция nil обозначает пустой список.

Для задания записи (record) в языке ML используется синтаксис {label

= çíà-

÷åíèå, label

= çíà÷åíèå, …}, где компоненты записи выбираются операцией #label.

На самом деле кортежи являются специфической разновидностью записи. Кор

теж (10, 23, "a") является экземпляром записи {1=10, 2=23, 3="a"}.

Инициализация. Чисто аппликативные языки не имеют концепции присваи

вания значения области памяти. Однако в языке ML значение может быть связано

с идентификатором с помощью конструкции val. Так,

val èäåíòèôèêàòîð = âûðàæåíèå

связывает значение выражения с именем идентификатора. Например, val X = 7 вы

ведет на печать строку

val Õ = 7 : int

означающую, что X имеет значение 7 типа int. В языке ML также существует ссылоч

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

Заметим, что символ «=» обозначает не присваивание, а операцию унифика

ции, которая предписывает ассоциировать новую копию идентификатора X со зна

чением 7. Это можно продемонстрировать, опустив ключевое слово val. В ответ на

ввод X = 8 ML выведет на печать строку

val it = false : bool

означающую, что унификация текущего значения X (то есть 7) со значением 8 лож

на и поэтому возвращается значение false.

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

Пользовательские типы можно определить с помощью оператора datatype:

datatype èäåíòèôèêàòîð = âûðàæåíèå_òèïà

Например, тип direction (направление) можно определить так:

- datatype direction = north | east | south | west;

con east : direction

con north : direction

con south : direction

con west : direction

что создает четыре константы типа direction. Мы создали тип, похожий на пере

числяемый тип в C и Pascal. Оператор

— val NewDirection = north;

устанавливает тип NewDirection как тип direction со значением north.

Это определение пользовательских типов можно распространить на типы дан

ных с древовидной структурой. Например,

- datatype Mydirection = dir of direction;

datatype Mydirection

con dir : direction → Mydirection

создает тип Mydirection, состоящий из функции выбора dir.

Объекты типа Mydirection задаются как кортежи (то есть dir(north)), например:

- val Heading = dir(north);

val Heading = dir north : Mydirection

П.7. ML

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

Без кортежа получим значение направления:

- val NewHeading = north;

val NewHeading = north : direction

Компоненты типов данных похожи на вызовы функций:

- val NewDirection = dir(NewHeading);

val NewDirection = dir north : Mydirection

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

видные структуры данных. Например, на рис. П.2 изображено дерево, состоящее

из узлов NumEntry и CharEntry. Спецификация будет иметь следующий вид:

- datatype Tree = Empty |

NumEntry of int * Tree * Tree |

Cha Entry of string * Tree;

datatype Tree

con Char Entry : string * Tree → Tree

con Empty : Tree

con NumEntry : int * Tree * Tree → Tree

Рис. П.2. Древовидный тип данных языка ML

Она означает, что тип данных Tree состоит из трех частей: CharEntry, NumEntry и Empty.

Структура рис. П.2 задается следующим образом:

- val NewTree=NumEntry(7,NumEntry(5,Empty,NumEntry(4,Empty,Empty)),

= CharEntry("A", NumEntry(3, Empty, Empty)));

val NewTree =

NumEntry

(7,NumEntry(5,Empty,NumEntry(4,Empty,Empty)),

CharEntry("A",NumEntry(3,Empty,Empty))) : Tree

Доступ к компонентам типов данных можно продемонстрировать с помощью

следующей программы:

datatype object = pair of int * int;

fun CreatePair(a,b) = pair(a,b);

fun CreateTwo(a,b,c,d) = CreatePair(a,b) :: CreatePair(c,d) :: [];

fun PrintFirst(pair(x,y)::z) = print(x)

| PrintFirst(x) = print("Error \n");

fun PrintThird(x::y) = PrintFirst(y)

| PrintThird(x) = print("Error \n");

629

Выполнение операции

val x = CreateTwo(1,2,3,4);

приводит к следующему результату:

val x = [pair (1,2),pair (3,4)] : object list

а выполнение следующих операторов:

PrintFirst(x);

PrintThird(x);

приводит к выводу

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

Выражения

Арифметические выражения. Арифметические выражения используют следую

щий порядок старшинства для выражений:

~ Унарный минус

*, /, div, mod Мультипликативные операторы

+, – Аддитивные операторы

Можно использовать полный набор арифметических операций сравнения: =,

<>, >=, <=, < и >.

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

ющие предикаты: andalso, orelse и not. Предикат andalso аналогичен предикату and,

но разработан для «ленивого» вычисления: правый операнд вычисляется только

в том случае, если левый принимает значение èñòèíà. Аналогично правый операнд

операции orelse вычисляется, только если левый принимает значение ëîæü.

Строковые выражения. Конкатенация строк определяется знаком ∧:

"abc" ∧ "def" = "abcdef".

Пустая строка задается символами "".

Выражение if. В ML нет концепции условного оператора, так как это апплика

тивный язык. Вместо него используется условное выражение (как в языке C):

if âûðàæåíèå then â_ñëó÷àå_èñòèíû else â_ñëó÷àå_ëæè

Поскольку каждое выражение должно быть правильно определено, часть else

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

Выражение while. Выражение while задается следующим образом:

while âûðàæåíèå

do âûðàæåíèå

и имеет очевидную интерпретацию: âûðàæåíèå

выполняется до тех пор, пока ис

тинно âûðàæåíèå

. Однако как âûðàæåíèå

может изменить свое значение, если учи

тывать аппликативную природу выполнения программ на языке ML? Âûðàæåíèå

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

ке ML имеется понятие ссылочной переменной, значение которой можно изменять.

Списочные выражения. Функции hd(L) для головы списка L и tl(L) для хвоста

списка L осуществляют операции, подобные car и cdr в языке LISP. Операция cons

языка LISP в языке ML задается двойным двоеточием ::. Например, hd(L) :: tl(L) = L.

П.7. ML

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

В языке ML также существует операция объединения, которая соединяет два

списка, [1,2]@[3,4] = [1,2,3,4]. Заметим, что для операции x :: y, если x имеет тип

'a, y должен быть типа 'a list, в то время как для объединения x@y обе переменные

должны быть типа 'a list.

Приведение типов между списками и строками задается встроенными функци

ями explode и implode. Функция explode преобразует строку в список односимволь

ных строк, а функция implode получает в качестве параметра строковый список

и возвращает строку.

Операторы

В языке ML фактически отсутствует понятие оператора, выполнение программы

осуществляется как последовательность выполнения функций. Подобно тому, как

выполняются программы на языке LISP, в ML выполнение программы осуществ

ляется через рекурсивный вызов процедур. Каждое выражение завершается точ

кой с запятой (;).

Последовательное выполнение можно смоделировать выполнением последо

вательности

(âûðàæåíèå

; âûðàæåíèå

; ... ; âûðàæåíèå

)

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

Определение функций

Функции определяются следующим образом:

fun èìÿ_ôóíêöèè (ïàðàìåòðû) = âûðàæåíèå;

где âûðàæåíèå — это то выражение, которое следует вычислить. Параметры функ

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

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

Например, сумму двух чисел можно определить так:

- fun sumit(a:int, b:int):int = a+b;

val sumit = fn : int * int → int

Здесь указывается, что функция sumit получает в качестве параметров два це

лых (int) значения, возвращает также целочисленное значение (int), а имя sumit

имеет тип function с сигнатурой int * int → int.

Любая из приведенных ниже спецификаций int однозначно определяет два дру

гих типа, так что следующие записи эквивалентны:

- fun sumit(a, b):int = a+b;

- fun sumit(a, b:int) = a+b;

- fun sumit(a:int, b) = a+b;

Однако необходимо задать хотя бы одну спецификацию int, поскольку запись

- fun sumit(a, b) = a+b;

неоднозначна, из нее не ясно, какой тип подразумевается — int или real.

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

ции. Рассмотрим функцию, которая перемешивает список путем перемещения го

ловы списка в его конец. Она соединяет хвост списка со списком, состоящим толь

ко из его первого члена:

- fun shuffle(x) = tl(x) @ [hd(x)];

val shuffle = fn : 'a list → 'a list

631

- shuffle([1,2,3]);

val it = [2,3,1] : int list

Функция shuffle оперирует с любым списком типа 'a и возвращает список того

же типа. Однако когда shuffle применяется к конкретному списку [1,2,3], возвра

щается специальный тип int list.

В языке ML предусмотрена некоторая разновидность операции сопоставления

с образцом для определения функций, как описано ранее в разделе 8.4.2. Можно

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

fun append(a,b) = if a=nil then b else hd(a) :: append(tl(a),b);

Данную конструкцию можно рассматривать как две отдельных области, в кото

рых определена функция append. Если a — пустой список nil, то возвращается зна

чение b. Если a не пуст, то осуществляется другая операция. Язык ML позволяет

определить отдельные области для функции:

fun app(nil,b) = b

| app(a,b) = hd(a) :: app(tl(a),b);

Для области, где первый аргумент nil, значением является b, в других случаях

значением будет hd(a) :: app(tl(a),b).

Истинная сила операции сопоставления с образцом заключается в возможности

доступа к компонентам сложных типов данных. Рассмотрим структуру, приведен

ную на рис. П.2. Объект X типа Tree определяется следующими компонентами:

NumEntry * Tree * Tree

CharEntry * Tree

Empty

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

ступ к самому правому компоненту рисунка. Ее можно определить так:

fun last(NumEntry(I,T1,T2))= if T2=Empty then if T1=Empty

then NumEntry(I,T1,T2) else last(T1) else last(T2)

| last(CharEntry(C,T1))= if T1=Empty then CharEntry(C,T1)

else last(T1)

| last(Empty) = Empty;

где каждая подобласть функции last рекурсивно выбирает самое правое поддере

во. Когда мы применяем эту функцию к переменной NewTree, которую мы предва

рительно задали как структуру, изображенную на рисунке, мы получаем NumEntry

с целым компонентом 3:

- last(NewTree);

val it = NumEntry (3,Empty,Empty) : Tree

Выражение as. Иногда бывает полезно в определении образца иметь возмож

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

ражения as. Например,

fun AStart(L as "a"::b) = F1(L)

AList(a) = F2(a)

вызовет:

1) F1 с аргументом L, если это список с первым элементом "a";

2) функцию F2 в противном случае.

Рекурсивные функции. Язык ML допускает рекурсивные функции, но, как

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

П.7. ML

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

Если A вызывает B, а B вызывает A, какую из функций следует объявлять в первую

очередь? В языке Pascal эта проблема разрешается с помощью объявления forward.

Поскольку в ML выполняется статическая проверка типов, то тип функции дол

жен быть известен до того, как функция появится в выражении. Косвенная рекур

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

функции объявляются одновременно:

fun ïåðâàÿ_ðåêóðñèâíàÿ_ôóíêöèÿ = ...

and âòîðàÿ_ðåêóðñèâíàÿ_ôóíêöèÿ = ...

and ïîñëåäíÿÿ_ðåêóðñèâíàÿ_ôóíêöèÿ= ...;

Ввод/вывод

Функция print осуществляет простой вывод. Управляющую последовательность

\n можно использовать для завершения строки вывода. Функция open_in(filename)

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

тип instream. Функция input(file_ptr, n) считывает n символов из файла и воз

вращает строку string. Функция end_of_stream(file_ptr) возвращает значение èñ-

òèíà, если достигнут конец файла.

Исключения

Язык ML позволяет пользователям определять исключения. Исключение опреде

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

exception èìÿ_èñêëþ÷åíèÿ

а генерируется так:

raise èìÿ_èñêëþ÷åíèÿ

Исключения можно обрабатывать с помощью оператора handle:

âûðàæåíèå handle îáðàáîò÷èê

Если операция raise инициируется внутри âûðàæåíèÿ или из любой функции,

вызываемой из âûðàæåíèÿ, то запускается обработчик. Он имеет формат:

îáðàáîò÷èê(îáðàçåö

) => âûðàæåíèå

îáðàáîò÷èê(îáðàçåö

) => âûðàæåíèå

...

îáðàáîò÷èê(îáðàçåö

) => âûðàæåíèå

Например, исключение myerror, порожденной оператором raise myerror(2), можно

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

myerror(1) => âûðàæåíèå

myerror(2) => âûðàæåíèå

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

Функции вводавывода:

 use èìÿ_ôàéëà считывает указанный файл как программу.

 print(x) печатает элементарный объект x.

 open in("èìÿ_ôàéëà") открывает указанный файл и возвращает указатель типа

instream на открытый файл.

 input(file_ptr, size) возвращает строку длиной size, состоящую из после

дующих size символов открытого файла file_ptr.

633

 end_of_stream(file_ptr) возвращает значение èñòèíà, если достигнут конец

файла.

Другие функции:

 #i возвращает iй компонент кортежа.

 hd(list) возвращает первый элемент списка.

 tl(list) возвращает список, состоящий из элементов списка list, начи

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

 explode(string_val) преобразует строку string_val в список односимволь

ных строк.

 implode(list) получает список строк list и возвращает строку. Например,

функция implode(["a", "bc"]) возвращает abc.

 size(str) возвращает количество символов в строке str.

 ord(x) возвращает целое значение символа x.

 chr(i) возвращает символ, представленный целым числом i.

 inc(i) эквивалентно i :=!i+1 для ref int i, а dec(i) эквивалентно i :=!i–1

для ref int i.

Абстракции и инкапсуляция

Структуры. ML включает концепцию пакетов, которые называются структурами

(structure) и имеют следующий синтаксис:

structure èäåíòèôèêàòîð = struct

ýëåìåíò

...

ýëåìåíò

end

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

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

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

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

- structure ListItem = struct

= val NewList = nil;

= fun add([ ],y)= y :: nil |

= add(x,y) = x @ [y];

= fun size(x) = if x=[ ] then 0 else 1+size(tl(x));

= fun delete(x) = tl(x)

= end;

Результирующая сигнатура будет иметь вид

structure ListItem :

sig

val NewList : 'a list

val add : 'a list * 'a → 'a list

val delete : 'a list → 'a list

val size : 'a list → int

end

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

списков любого типа (обозначенного как 'a) в сигнатуре.

П.7. ML

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

Объявление open

open èìÿ_ñòðóêòóðû

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

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

туры, как в приведенном списке целых переменных:

- open ListItem;

open ListItem

val add = fn : 'a list * 'a → 'a list

val size = fn : 'a list → int

val delete = fn : 'a list → 'a list

val NewList = [ ] : 'a list

- val a = NewList;

val a = [ ] : 'a list

- val b = add(a,3);

val b = [3] : int list

- val c = size(b);

val c = 1 : int

Сигнатура структуры определяет интерфейс подобно пакетам языка Ada или

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

ограничением на более общую структуру. Например, можно определить списки

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

функцию delete, определяя эту новую сигнатуру при помощи объявления signature:

signature IntListSig = sig

val NewList : int list;

val add : int list * int → int list;

val size : int list → int

end;

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

исходная структура ListItem, только ограниченная до сигнатуры IntListSig, исполь

зуя альтернативную форму структуры:

structure IntList : IntListSig = ListItem;

В этом месте можно вызвать NewList и add для создания новых целых списков,

но delete не является частью нашей новой ограниченной среды:

- val i = IntList.NewList;

val i = [ ] : int list

- IntList.add(i,7);

val it = [7] : int list

- IntList.delete(i);

Error : unbound variable or constructor : in path

(Îøèáêà: íåñâÿçàííàÿ ïåðåìåííàÿ èëè êîíñòðóêòîð: delete â IntList.delete)

Абстракция. Использование объявления signature для создания ограничений

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

щем примере было скрыто имя функции delete в структуре IntList. Реализации

Standard ML (НьюДжерси) также включает конструкцию abstraction:

abstraction òèï_àáñòðàêöèè : ñèãíàòóðà_àáñòðàêöèè = îïðåäåëåíèå_ñòðóêòóðû

которая выполняет такую же функцию. Аналогично для создания новых типов дан

ных можно использовать

abstype èìÿ_òèïà_äàííûõ with îáúÿâëåíèÿ end

635

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

что обеспечивает истинную абстракцию.

Массивы. ML реализует массивы как структуры:

 open Array добавляет функции массивов в текущую среду.

 array(m, n) возвращает массив с диапазоном изменения индексов от 0 до (m–1),

все элементы которого инициализированы как n.

 sub (a, i) возвращает значение a[i].

 update(a, i, val) присваивает элементу a[i] значение val.

П.8. Pascal

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

В листинге П.10 приведена версия на Pascal программы, которую мы уже рассмат

ривали при изучении языков C и FORTRAN. В этой программе считывается мас

сив целых чисел, распечатываются значения его элементов, а затем вычисляется

и распечатывается сумма всех значений элементов массива. Если входной файл

sample.data содержит

12 14 16

4 1.2 1.4 1.6 1.0

то в результате работы программы будет напечатано:

12.00 14.00 16.00

sum = 42.0000

1.20 1.40 1.60 1.00

sum = 5.2000

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

1 program main(input, output, infile);

2 const size = 99;

3 type Vector = array [1..size] of real;

4 var infile: text;

5 a: Vector;

6 j,k: integer;

7 function sum(v: Vector; n: integer): real;

8 var temp: real;

9 i: integer;

10 {Òåëî ôóíêöèè sum}

11 begin

12 temp := 0;

13 for i := 1 to n do temp := temp + v [i];

14 sum := temp

15 end ;{sum}

16 begin {of main}

17 reset(infile, 'sample.data');

18 while not (eof(infile)) do

19 begin

20 read(infile, k);

21 for j := 1 to k do

22 begin

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

П.8. Pascal

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

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

23 read(infile, a[j]);

24 write(a[j]:10:2)

25 end;

26 writeln;

27 writeln('sum = ', sum(a,k):6:4);

28 readln(infile)

29 end

30 end.

Строка 1. main — это имя программы. Файл input ссылается на стандартный

файл ввода (обычно это клавиатура), output — на стандартный файл вывода (обычно

это экран монитора), а infile — на файл данных, который используется внутри

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

Строка 3. Определяется новый тип данных Vector, который представляет со

бой массив вещественных чисел с диапазоном изменения индекса от 1 до 99. И верх

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

Строки 4–6. Оператор var определяет глобальные переменные, используемые

в программе. В данном случае infile — это текстовый файл, содержащий входные

данные. Файлы input и output объявлять не требуется.

Строка 7. Объявляется функция sum. У нее имеются параметры v типа Vector

и n типа integer, передаваемые по значению. Если бы требовалось передавать па

раметры по ссылке, то в объявлении функции надо было бы написать, например:

var v: Vector. Функция sum возвращает значение типа real (вещественное число).

Строка 10. Комментарии в Pascal задаются в фигурных скобках.

Строка 13. Оператор for, в котором переменная цикла i изменяется от 1 до n.

Если тело оператора for состоит более чем из одного оператора, то всю последова

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

раторами begin и end (см. строки 22–25).

Строка 14. Функция возвращает вычисленное значение простым его присваи

ванием имени функции.

Строка 17. Оператор reset открывает файл для ввода. В данном случае он свя

зывает файл sample.data с внутренним объектом данных infile. Если данные вво

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

rewrite открывает файл для записи.

Строка 20. Здесь считывается первое значение из файла infile и сохраняется

в переменной k. Если бы ввод осуществлялся с клавиатуры, то имя файла можно

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

той или пробела и пытается перевести прочитанные данные в целочисленный фор

мат. Если бы переменная k была символьного типа (char), то был бы прочитан только

один символ из файла ввода.

Строка 24. Значение элемента вектора записывается в стандартный файл вы

вода (то есть отображается на экране монитора), так как в операторе write первым

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

тельные члены 10:2 предписывают печатать 10 десятичных цифр числа, причем

две цифры отводятся под дробную часть. Если эти параметры не указаны, то Pascal

использует умалчиваемый формат представления десятичных чисел. Следующие

операторы write записывают числа в ту же строку вывода до тех пор, пока не будет

выполнен оператор writeln (строка 26).