11.4 Программируем с умом — Классный калькулятор

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

Node

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

// new(Number(), value)

% NodeClass Number: Node {

    double value;

%}

Наше дерево может расти, если есть узлы с поддеревьями. Monad имеет только одно поддерево, Dyad имеет два:

% NodeClass Monad: Node {

    void * down;

%}

%prot

#define down(x)    (((struct Monad *)(x)) -> down)

% NodeClass Dyad: Node {

    void * left;

    void * right;

%}

%prot

#define left(x) (((struct Dyad *)(x)) -> left)

#define right(x) (((struct Dyad *)(x)) -> right)

Технически .down, .left и .right должны заполняться только конструкторами этих узлов, но если мы планируем копировать дерево, подкласс может потребовать изменения указателей.

Мы используем одиночные поддеревья для построения двух совершенно разных вещей. Val используется для получения значение символа из таблицы символов, а Unary представляет собой оператор, например, знак минус:

% NodeClass Val: Monad {

%}

// new(Minus(), subtree)

% NodeClass Unary: Monad {

%}

% NodeClass Minus: Unary {

%}

Один вид Val это Global, который указывает на символ Var или Const, и получает своё значение оттуда. Если мы реализуем определяемые пользователем функции, то используем Parm, чтобы получить значение единственного параметра.

// new(Global(), константа-или-переменная)

// new(Parm(), функция)

% NodeClass Global: Val {

%}

% NodeClass Parm: Val {

%}

Мы будем наследовать записи таблицы символов от базового класса Symbol, который независим от Node. Таким образом нам нужен Val и его подклассы, потому что больше нельзя позволять дереву выражений указывать непосредственно на Symbol, который не понял бы метод exec().

Есть много узлов с двумя поддеревьями. Add, Sub, Mult и Div комбинирует значения своих поддеревьев; мы можем всё упростить, добавив Binary в качестве их базового класса:

// new(Add(), левое-поддерево, правое-поддерево)

...

% NodeClass Binary: Dyad {

%}

% NodeClass Add: Binary {

%}

...

Так же как Val используется для доступа к значениям символов, Ref используется, чтобы объединить символ и дерево выражения: Assign указывает на Val и хранит там значение другого своего поддерева; Builtin указывает на символ Math, который вычисляет значение библиотечной функции для значения правого поддерева Builtin в качестве аргумента; наконец, User указывает на символ Fun, который вычисляет значение определяемой пользователем функции для значения другого поддерева User в качестве параметра.

// new(Assign(), var, правое-поддерево)

// new(Builtin(), math, поддерево-аргументов)

// new(User(), fun, поддерево-аргументов)

% NodeClass Ref: Dyad {

%}

% NodeClass Assign: Ref {

%}

% NodeClass Builtin: Ref {

%}

% NodeClass User: Ref {

%}

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

Хотя мы и нарушаем принцип, что конструкторы и деструкторы должны быть сбалансированы, мы делаем так по следующей причине: деструкторы отсылают delete() к своим поддеревьям. Это приемлемо до тех пор, пока удаляется поддерево выражения, но совершенно ясно, что нельзя отсылать delete() в таблицу символов. Val и Ref были введены специально для управления процессом разрушения.

На данный момент это выглядит так, как будто мы не должны различать Global и Parm. Однако, в зависимости от представления их символов, нам, вероятно, придётся реализовать разные методы exec() для каждого. Введение подклассов позволяет не торопиться с решением.

Symbol

Рассматривая возможные деревья выражений мы обнаружили необходимые узлы. В свою очередь, после разработки узлов мы найдём большинство символов, в которых нуждаемся. Symbol — абстрактный базовый класс для всех символов, которые могут быть введены в таблицу символов и находимых по имени. Reserved является зарезервированным словом:

// new(Reserved(), "name", lex)

% Class Reserved: Symbol {

%}

Var представляет собой символ со значением с плавающей точкой. Global будет указывать на символ Var и использовать value(), чтобы получить текущее значение; Assign так же использует setvalue(), чтобы установить новое значение:

// new(Var(), "name", VAR)

% Class Var: Symbol {

    double value;

%

    double value (const _self);

    double setvalue (_self, double value);

%}

Const это Var с другим конструктором:

// new(Const(), "name", CONST, value)

% Class Const: Var {

%}

Если мы сделаем Const подклассом Var, то избежим проблем, из-за которых setvalue() должен был бы иметь доступ к .value в базовом классе и мы должны были бы проинициализировать Var во время конструирования. Мы синтаксически защитим Const от того, чтобы быть целью присвоения для Assign.

Math символизирует библиотечную функцию. Builtin использует mathvalue() для передачи аргумента в и получения значения функции как результат:

// new(Math(), "name", MATH, название-функции)

typedef double (* function) (double);

% Class Math: Symbol {

    function fun;

%

    double mathvalue (const _self, double value);

%}

Наконец, Fun символизирует определяемую пользователем функцию с единственным параметром. Этот символ указывает на дерево выражения, которое может быть первоначально установлено или позже заменено с помощью setfun() и рассчитано узлом User с помощью funvalue():

// new(Fun(), "name", FUN)

% Class Fun: Var {

    void * fun;

%

    void setfun (_self, Node @ fun);

    double funvalue (_self, double value);

%}

Игнорируя проблемы рекурсии мы определяем Fun как подкласс Var, чтобы можно было сохранить значение аргумента с помощью setvalue() и встроить узел Parm в выражение везде, где требуется значение параметра. Вот иерархия классов для Symbol:

И снова почти весь код может быть скопирован из главы 5 и требует небольшой адаптации к данной иерархии классов. Const и Math никогда не должны удаляться; поэтому, мы можем добавить пустые методы для их защиты:

% : Const delete { // не позволяем удаление

}

Единственная новая идея — определяемые пользователем функции, которые реализованы в классе Fun:

% Fun setfun {

%casts

    if (self -> fun)

        delete(self -> fun);

    self -> fun = fun;

}

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

% Fun funvalue {

%casts

    if (! self -> fun)

        error("undefined function");

    setvalue(self, value);  // аргумент для параметра

    return exec(self -> fun);

}

Для вычисления значения функции мы импортируем значение аргумента, чтобы Parm мог использовать value() для получения его в виде значения параметра. Затем exec() сможет вычислить значение функции из дерева выражения.

Symtab

Мы могли бы попытаться расширить List как таблицу символов, но функция двоичного поиска, используемая в главе 5, должна применяться к массивам, и нам нужны только методы screen() и install():

// new(Symtab(), минимальный-размер)

#include <stddef.h>

% Class Symtab: Object {

    const void ** buf;      // const void * buf [dim]

    size_t dim;             // текущий размер буфера

    size_t count;           // количество элементов в буфере

%

    void install (_self, const Symbol @ entry);

    Symbol @ screen (_self, const char * name, int lex);

%}

Память для массива выделяется так же, как для List:

% Symtab ctor {

    struct Symtab * self = super_ctor(Symtab(), _self, app);

    if (! (self -> dim = va_arg(* app, size_t)))

        self -> dim = 1;

    self -> buf = malloc(self -> dim * sizeof(void *));

    assert(self -> buf);

    return self;

}

search() является внутренней функцией, которая использует binary() для поиска символа с определённым именем или ввода самого имени в таблицу:

static void ** search (struct Symtab * self, const char ** np)

{

    if (self -> count >= self -> dim) {

        self -> buf = realloc(self -> buf,

                        (self -> dim *= 2) * sizeof(void *));

        assert(self -> buf);

    }

    return binary(np, self -> buf, & self -> count,

                                        sizeof(void *), cmp);

}

Это внутренняя функция; поэтому мы используем небольшой трюк: binary() будет искать символ, но если он не будет найден, binary() впишет в *np строку, а не символ. cmp() сравнивает строку с символом — если бы использовался строковый класс, подобный Atom, можно было бы реализовать cmp() с помощью differ():

static int cmp (const void * _key, const void * _elt) {

    const char * const * key = _key;

    const void * const * elt = _elt;

    return strcmp(* key, name(* elt));

}

name() является методом Symbol, возвращающим имя символа. Мы сравниваем его со строковым аргументом search() и не создаём символ, прежде чем не узнаем, что поиск действительно не дал результата.

С табличным поиском и записью в этом же месте фактические методы Symtab довольно просто реализовать. install() вызывается со вторым аргументом, созданным new(). Мы можем добавлять в таблицу символов произвольные объекты Symbol таким образом:

% Symtab install {

    const char * nm;

    void ** pp;

%casts

    nm = name(entry);

    pp = search(self, & nm);

    if (* pp != nm)         // запись найдена

        delete(* pp);

    * pp = (void *) entry;

}

install() готов к замене символов в таблице.

% Symtab screen {

    void ** pp;

%casts

    pp = search(self, & name);

    if (* pp == name) {                // введённое имя

        char * copy = malloc(strlen(name) + 1);

        assert(copy);

        * pp = new(Symbol(), strcpy(copy, name), lex);

    }

    return * pp;

}

screen() или находит запись по имени, или создаёт новый Symbol с помощью динамически сохранённого имени. Если мы позже решим, что будет лучше, если запись таблицы принадлежит подклассу Symbol, то сможем вызвать install(), чтобы заменить запись в таблице. Хотя это немного неэффективно, это не требует никаких новых функций для интерфейса таблицы символов.

Абстрактные базовые классы

Symbol — базовый класс для записей таблицы символов. Symbol состоит из имени и значения маркера для синтаксического анализатора, значения обоих передаются во время конструирования:

Symbol.d

// new(Symbol(), "name", lex)       "name" не должно изменяться

% Class Symbol: Object {

    const char * name;

    int lex;

%

    const char * name (const _self);

    int lex (const _self);

%}

Symbol.dc

% Symbol ctor {

    struct Symbol * self = super_ctor(Symbol(), _self, app);

    self -> name = va_arg(* app, const char *);

    self -> lex = va_arg(* app, int);

    return self;

}

Мы позволяем Symbol предположить, что были сделаны внешние приготовления для имени символа сделать его разумно постоянными: имя это или статическая строка, или имя должно быть сохранено динамически до того, как с помощью него будет сконструирован символ. Symbol не сохраняет имя и не удаляет его. Если screen() сохраняет имя динамически, и если мы решаем заменить символ, используя install(), то можем просто скопировать имя из предыдущего символа, который удаляется install(), и избежать большего количества трафика в динамической памяти. Однако, намного лучшей стратегией было бы использование класса, подобного Atom.

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

Node.d

% NodeClass: Class Node: Object {

    void * next;

%

    void sunder (_self);

%-

    double exec (const _self);

%+

    void reclaim (const _self, Method how);

%}

Node.dc

static void * nodes;         // сцепляем все узлы

% Node new {

    struct Node * result =

                cast(Node(), super_new(Node(), _self, app));

    result -> next = nodes, nodes = result;

    return (void *) result;

}

Согласно словарю Вебстера, sunder означает "разъединение полностью и окончательно или с помощью силы", и это именно то, что мы делаем:

% Node sunder {

%casts

    if (nodes == self)           // первый узел

        nodes = self -> next;

    else if (nodes) {            // другой узел

        struct Node * np = nodes;

        while (np -> next && np -> next != self)

            np = np -> next;

        if (np -> next)

            np -> next = self -> next;

    }

    self -> next = 0;

}

Прежде чем удалить узел, удаляем его из цепочки:

% Node delete {

%casts

    sunder(self);

    super_delete(Node(), self);

}

Устранение утечек памяти

Как правило синтаксический анализатор в parse.c после завершения работы с выражением будет вызывать delete():

if (setjmp(onError)) {

    ++ errors;

    reclaim(Node(), delete);

}

while (gets(buf))

    if (scan(buf)) {

        void * e = stmt();

        if (e) {

            printf("\t%g\n", exec(e));

            delete(e);

        }

    }

Если что-то пошло не так и был сделан вызов error(), для применения delete() ко всем узлам цепочки используется reclaim():

% Node reclaim {

%casts

    while (nodes)

        how(nodes);

}

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

reclaim(Node, sunder);

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

Элегантность схемы заключается в том, что весь механизм находится в базовом классе Node и наследуется всем деревом выражений. С данными функциями класса мы можем заменить new() для поддерева иерархии классов. Замена new() только для всех узлов, но не для символов или таблицы символов, обеспечивает утилизацию повреждённых выражений без повреждения переменных, функций, и тому подобного.

Технически reclaim() задекларирована как метод класса. Нам не нужна возможность перезаписывать эту функцию для подкласса Node, но это действительно оставляет место для расширения. reclaim() разрешает выбор относительно того, что должно быть применено к цепочке. В случае ошибки это будет delete(); однако, если мы сохраняем выражение для определяемой пользователем функции в символе Fun, то должны применить к цепочке sunder(), чтобы помешать следующей ошибке стереть выражение, сохранённое в таблице символов. Когда функция заменена, setfun() удалит старое выражение, а delete() по-прежнему использует sunder() — вот почему sunder() не требует находить свой аргумент в цепочке.