Cтраница 4
ДЗ) должен быть узлом первого типа, а узел первого типа может не быть корневой вершиной. Узлы различных типов, наследуя признаки и атрибуты базовой сущности BASE, также имеют только им присущие атрибуты. Корневой узел ROOT, являясь по сути узлом FIRST и наследуя его свойства, должен добавить свой атрибут - время исполнения подалгоритма ДЗ. [46]
На этом этапе стохастически генерируется популяция Р, состоящая из Np древовидных программ, причем корневой вершиной дерева всегда является функция, аргументы которой выбираются случайно из множеств function set или terminal set. Концевыми вершинами дерева должны быть переменные или константы, в противном случае процесс генерации необходимо рекурсивно продолжить. Если структура дерева становится сложной, то заранее устанавливается максимальная высота дерева, равная числу ребер дерева, которое содержит самый длинный путь от корневой вершины до некоторой концевой вершины. Коза предлагает применить способ, согласно которому деревья разной высоты генерируются с одинаковой частотой. [47]
Проблема, возникающая в описанной нами реализации, состоит в том, что вершина редекса заменяется корневой вершиной ( неизменного) результирующего подграфа, так что после этого существуют две копии этого подграфа, в которых все вершины, кроме корневых, являются разделяемыми. Поскольку каждая корневая вершина может впоследствии стать редексом, имеет место двойная редукция этого параграфа. [48]
После подстановки аргумента при выполнении р-редукции редекс физически заменяется результатом этой редукции - либо атомом, либо корневой вершиной упрощенного ( редуцированного) выражения. Если вершина редекса сама является разделяемой, тогда после замены каждая ссылка на нее соответствует уже вершине в редуцированной форме, и именно поэтому операция замены обеспечивает реализацию семантики вызова по необходимости. Как и в случае преобразования задержки в дампе с присваиванием ленивой SECD-машины, замена вершины редекса является сохраняющей значение в том смысле, что значения заменяемого и заменяющего графов совпадают. Другие вершины редекса не будут затронуты операцией замены, но будут отрезаны от корневой вершины и от графа в целом. Различные типы сборщиков мусора и методы их работы описаны в гл. В примерах на рис. 11.2 и 11.3 эти потенциально мусорные вершины не показаны. На рис. 11.4, а снова показана редукция рис. 11.3, но при этом показаны все отрезанные подграфы, которые могут оказаться мусором. [49]
Чтобы получить эффект разделения графов аргументов, заменяем каждый указатель связанной переменной в листах графа функции на указатель корневой вершины графа аргумента, что в результате дает модифицированную копию графа функции. [50]
С-схема компилирует код, создающий граф, представляющий выражение, и помещает указатель на его вершину редекса ( корневую вершину) в вершину стека. Во время прогона программы каждая переменная в г является формальным параметром функции, определенной пользователем, и должна иметь в стеке соответствующий указатель на подграф аргумента. Доступ к указателям аргумента происходит с помощью макроса PUSH, причем PUSHi помещает копию указателя в i - й, считая от УВС, элемент стека. Поскольку доступ к указателям аргумента происходит относительно вершины стека, то глубина стека п также должна быть параметром С-схемы. [51]
Отсутствие циклов приводит к тому, что в графе ( и в любом его подграфе) найдется хоть одна корневая вершина. [52]
В состав элементарных циклов включаются ключи, лежащие на одном пути из корневой древовидной структуры в висячие вершины, помеченные меткой исходной корневой вершины. [53]