Cтраница 1
Дерево сопоставления для набора образцов является результатом слияния деревьев сопоставления для отдельных образцов. [1]
Получите дерево сопоставления для этого набора уравнений, слитое из отдельных деревьев сопоставления. [2]
Код, получаемый из дерева сопоставления, выбирает одно из уравнений определения функции исходя из анализа структуры выражения аргумента. Но в выражении правой части могут быть ссылки на переменные, содержащиеся в образце выбранного уравнения. [3]
Поэтому с каждым листом дерева сопоставления нужно связать некоторый дополнительный компонент. При генерации дерева сопоставления для каждого уравнения мы должны строить список связей вида имя / позиция, где имена являются идентификаторами, ссылки на которые имеются в образцах, а позиции указывают положение соответствующих этим идентификаторам частей аргумента и представляются, как и ранее, в виде списка целых чисел. Этот дополнительный список может храниться вместе с номером уравнения в листе дерева сопоставления и используется при генерации связывающего кода для промежуточного кода правой части этого уравнения. Заметим, что символы, обозначающие произвольные переменные ( подчеркивания () в языке Норе), по очевидной причине не следует включать в список связей. [4]
После того как будет сгенерировано дерево сопоставления для каждого уравнения в определении f, необходимо сделать следующий шаг - слить эти деревья в одно. [5]
Заметим, что код для дерева сопоставления используется в качестве первого аргумента функции CASE верхнего уровня по той простой причине, что в определении функции f может быть несколько уравнений с одинаковой правой частью. Тогда, если код для правых частей уравнений генерировать просто из листьев дерева сопоставления, коды одинаковых правых частей будут дублироваться. Однако совсем не трудно установить, имеются ли в определении функции уравнения с одинаковой правой частью, и если это так, тогда, конечно, нет никакой необходимости в упомянутой функции CASE верхнего уровня. [6]
Трансляция сопоставления с образцом включает построение дерева сопоставления, из которого может быть сгенерирован эффективный код, используемый для выбора варианта. [7]
Алгоритм трансляции может работать с литеральными образцами, если ввести в дерево сопоставления новый тип вершин вместе с проверкой значения литерала. [8]
Вместо одного символа для каждой функции мы вводим отдельный символ К для каждого аргумента функции При рассмотрении дерева сопоставления мы по-прежнему можем считать, что аргументы образуют кортеж. Единственное изменение, которое требуется в данном случае, касается окончательной трансляции позиций. Позиция [ п ] теперь указывает n - й аргумент / связанную переменную ( скажем, ai), а не п-й элемент кортежа аргументов. Карринговые конструкторы не представляют проблемы. К моменту вызова функции все аргументы составных данных запомнены в виде кортежей, и описанный нами метод индексации по-прежнему работает. [9]
Код сопоставления может последовательно соотнести каждый образец с аргументом, чтобы определить, соответствуют ли они друг другу, но на практике более эффективно слить все эти тесты в единое дерево сопоставления. Это дерево определяет часть промежуточного кода, который при выполнении возвращает целое число, представляющее собой номер правила, образец которого соответствует аргументу функции. [10]
Поэтому с каждым листом дерева сопоставления нужно связать некоторый дополнительный компонент. При генерации дерева сопоставления для каждого уравнения мы должны строить список связей вида имя / позиция, где имена являются идентификаторами, ссылки на которые имеются в образцах, а позиции указывают положение соответствующих этим идентификаторам частей аргумента и представляются, как и ранее, в виде списка целых чисел. Этот дополнительный список может храниться вместе с номером уравнения в листе дерева сопоставления и используется при генерации связывающего кода для промежуточного кода правой части этого уравнения. Заметим, что символы, обозначающие произвольные переменные ( подчеркивания () в языке Норе), по очевидной причине не следует включать в список связей. [11]
В этом примере порядок проверки конструкторов образца определен в виде в глубине слева направо. Символ X на рисунке обозначает пустое дерево сопоставления, соответствующее несовпадению образца и аргумента, а лист i обозначает успешное совпадение аргумента и образца i - ro уравнения. [12]
Заметим, что код для дерева сопоставления используется в качестве первого аргумента функции CASE верхнего уровня по той простой причине, что в определении функции f может быть несколько уравнений с одинаковой правой частью. Тогда, если код для правых частей уравнений генерировать просто из листьев дерева сопоставления, коды одинаковых правых частей будут дублироваться. Однако совсем не трудно установить, имеются ли в определении функции уравнения с одинаковой правой частью, и если это так, тогда, конечно, нет никакой необходимости в упомянутой функции CASE верхнего уровня. [13]
Хотя наш алгоритм трансляции не допускает выражения, содержащие литеральные образцы, его можно соответствующим образом модифицировать, включив в дерево соответствия новый тип вершин. До сих пор внутренняя вершина дерева сопоставления специфицировала проверку кода конструктора того компонента аргумента, который определяется указанной в данной вершине позицией. Чтобы иметь возможность работать с литеральными образцами, мы должны определить внутреннюю вершину, специфицирующую тест на равенство между литералом и соответствующим компонентом аргумента. [14]
Поэтому с каждым листом дерева сопоставления нужно связать некоторый дополнительный компонент. При генерации дерева сопоставления для каждого уравнения мы должны строить список связей вида имя / позиция, где имена являются идентификаторами, ссылки на которые имеются в образцах, а позиции указывают положение соответствующих этим идентификаторам частей аргумента и представляются, как и ранее, в виде списка целых чисел. Этот дополнительный список может храниться вместе с номером уравнения в листе дерева сопоставления и используется при генерации связывающего кода для промежуточного кода правой части этого уравнения. Заметим, что символы, обозначающие произвольные переменные ( подчеркивания () в языке Норе), по очевидной причине не следует включать в список связей. [15]