val eq = op = fun f(x) = x

>structure S =

type t = int

val eq = fn : int*int -> bool val f = fn : a -> a

- structure S = I(S);

>structure S =

type t = int

val eq = fn : int*int -> bool end

Обратите внимание на то, что компонента f структуры S отсутствует в

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

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

3.5 Модульная система в реальной практике

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

signature SYMBOL = sig

type symbol

val mksymbol : string -> symbol

val eqsymbol : symbol*symbol -> bool end;

signature ABSTSYNTAX = sig

structure Symbol : SYMBOL type term

val idname : term -> Symbol.symbol end;

signature SYMBOLTABLE = sig

structure Symbol : SYMBOL type entry type table val mktable : unit -> table val lookup : Symbol.symbol * table -> entry end;

signature PARSER = sig

structure AbstSyntax : ABSTSYNTAX structure SimbolTable : SYMBOLTABLE val symtable : Symboltable.table val parse : string -> AbstSyntax.term end;

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

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

structure Symbol: SYMBOL = struct

datatype symbol = symbol of string * ... fun mksymbol(s) = symbol(s, ...) fun eqsymbol(syml,sym2) = ... end;

structure AbstSyntax : ABSTSYNTAX = struct

structure Symbol : SYMBOL = Symbol

datatype term = ... fun idname(term) = ... end;

structure SymbolTable : SYMBOLTABLE = struct

structure Symbol: SYMBOL = Symbol type entry = ... type table = ... fun mktable() = ... fun lookup(sym, table) = ... end;

structure Parser: PARSER = struct

structure AbstSyntax : ABSTSYNTAX = AbstSyntax structure SymbolTable : SYMBOLTABLE = SymbolTable val symtable = SymbolTable.mktable(); fun parse(str) =

... SymbolTable.lookup(AbstSyntax.idname(t).symtable)...

Обратите внимание на то, что в последней строке структуры Parser мы записали применение функции SymbolTable. lookup к результату функции AbstSyntax.idname. Это применение корректно с точки зрения согласования типов только благодаря тому, что структуры AbstSyntax и SymbolTable включают одну и ту же структуру Symbol. Если бы было две структуры, сопоставимые с сигнатурой SYMBOL, и одна из них была использована в структуре SymbolTable, а другая - в структуре AbstSyntax, в упомянутой строке возникла бы ошибка несоответствия типов. Имейте это в виду при чтении дальнейшего.

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