У нас на сайте представлено огромное количество информации, которая сможет помочь Вам в написании необходимой учебной работы. 

Но если вдруг:

Вам нужна качественная учебная работа (контрольная, реферат, курсовая, дипломная, отчет по практике, перевод, эссе, РГР, ВКР, диссертация, шпоры...) с проверкой на плагиат (с высоким % оригинальности) выполненная в самые короткие сроки, с гарантией и бесплатными доработками до самой сдачи/защиты - ОБРАЩАЙТЕСЬ!

Оглавление

Введение                                                                                                                                      3

1.     Обзор                                                                                                                                       5

1.1.      Views............................................................................................................................... 5

1.2.      Pattern guards and Transformational Patterns....................................................... 6

1.3.      Scala Objects patterns................................................................................................... 7

1.4.      F# Active Patterns..................................................................................................... 10

1.5.      Haskell Pattern Synonyms........................................................................................ 11

2.     Оператор  возврата к сопоставлению                                                                       13

3.     Выбор  конструкции для реализации                                                                    17

3.1.      Введение объективных критериев для сравнения........................................... 17

3.2.      Сравнение существующих решений................................................................... 18

3.2.1.       Максимальность........................................................................................... 19

3.2.2.       Выразительность........................................................................................... 20

3.2.3.       Образцы первого класса............................................................................. 21

3.2.4.       Проверка на полноту.................................................................................. 21

3.2.5.       Эффективность............................................................................................. 22

3.3.      Заключительный выбор.......................................................................................... 23

4.     Реализация активных образцов в OCaml                                                           24

4.1.      Расширение синтаксиса.......................................................................................... 24

4.2.      Правила типизации.................................................................................................. 25

4.3.      Модификация схемы компиляции...................................................................... 25

5.     Заключение                                                                                                                        28

6.     Благодарности                                                                                                                  29

Список литературы                                                                                                             30

Введение

В контексте языков программирования сопоставление с образцом служит весьма эф- фективным и выразительным средством анализа данных. Появившееся в первых функ- циональных языках вкупе с алгебраическими типами данных эта конструкция доволь- но быстро завоевала популярность и в практически неизменном виде реализовывалась в большинстве последующих функциональных языков. Были разработаны эффектив- ные схемы компиляции [10, 12, 22],проверки на полноту (pattern exhaustiveness) [11] и хрупкость (pattern fragility). Более того, в настоящее время сходные конструкции разрабатываются и добавляются и в некоторые лидирующие императивные языки, такие как C# [13], Kotlin [9] и Java [4].

Однако в своем наиболее распространённом варианте этот приём имеет довольно серьёзные ограничения:

•    конструкторы данных должны быть открытыми (public), что не допускает аб- стракции определения типа данных;

•    для каждого типа данных возможно лишь одно представление для использова- ния в конструкции сопоставления с образцом;

•    охранные выражения (pattern guards) либо не допускаются языком (как в языке Standard ML [14]), либо могут содержать ровно одно булево выражение (как в языке OCaml на текущий момент [24]);

•    семантика сопоставления с образцом жёстко зафиксирована на уровне языка и не допускает определяемых пользователем вычислений1.

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

1.     Со стороны определения образца: лист может быть только открытым конструк- тором типа или константой; заметим также, что при этом, как правило, он не является значением первого порядка (first class value).

2.     Со стороны определения сопоставления: сопоставление с образцом может яв- ляться только списком правил, а его семантика жёстко зафиксирована науровне языка.

В этой работе мы предъявим два независимых расширения языка для устранения каждого типа ограничений. Однако отметим, что в этой работе способы модификации семантики сопоставления с образцом [23, 25] рассматриваться не будут.

1Изменение семантики конструкции сопоставления с образцом путем параметризации образцов ти- пами специального класса типов представлено в секции 6.3 работы [23].

Основным подходом к расширению образцов является возможность проведения некоторых вычислений при сопоставлении, благодаря чему становятся возможными абстракция и задействование нескольких представлений при в сущности столь же выразительном синтаксисе. Многие языки программирования уже содержат подобные конструкции в том или ином виде: active patterns в F# [23], pattern synonyms в Haskell

[19]    и extractors в Scala [5]. В данной же статье мы предложим расширение для языка программирования общего назначения OCaml.

Постановка задачи

Целью работы является разработка расширение языка OCaml, которое бы:

• удовлетворяло требованию консервативности (или обратной совместимости) – синтаксис и семантика любой программы, не использующей средства расшире- ния, должны оставаться неизменными;

• являлось полностью статически типизируемым;

• не требовало модификации системы типов языка;

• допускало абстракцию образцов;

• сохраняло возможность проверки сопоставления на полноту;

• позволяло оперировать образцами как значениями первого порядка;

• не требовало модификации существующих модулей.

Были поставлены следующие задачи:

1. Провести анализ существующих решений и выполнить сравнение по ряду объ- ективных критериев. По результатам обосновать выбор того или иного суще- ствующего решения или представить собственное.

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

• расширение синтаксиса

• правила типизации новых конструкций

• компиляция расширения в промежуточное представление

3. Представить прототип реализации выбранного расширения.

1.      Обзор

1.1.     Views

Ф. Вадлер (Philip Wadler) [26] одним из первых указал на недостатки традицион- ной модели образцов: сопоставление с образцом является мощным выразительным средством и ясно (внекоторых случаях почти досимвольно) выражает индуктивные математические определения, но требует открытого представления типа. Абстракция данных поддерживает эффективность2 и инкапсуляцию, но требует скрыть представ- ление типа – таким образом программист оказывается перед дилеммой выразитель- ного или эффективного кода.

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

2В качестве примера можно рассмотреть представление натуральных чисел в виде эффективного машинного типа целого числа и совершенно неэффективное, но формальное и удобное представление в виде алгебраического типа данных согласно математическому определению Пеано. Подробнее см. в [26].

1.2.     Pattern guards and Transformational Patterns

Примерно в это же время был предложен альтернативный подход к данной задаче: М. Эрвиг (Martin Erwig) и С. П. Джонс (Simon Peyton Jones) представили два рас- ширения сопоставления с образцом: охранные выражения и преобразующие образцы (transformational patterns) [6]. Охранные выражения позволяют в одной ветке разбо- ра проводить несколько последовательныхсопоставлений. Ключевой здесь является возможность вычисления функции от привязанных переменных, результат которой также проходит сопоставление. Такое простое и по синтаксису, и посемантике, и по реализации правило автоматически позволяет абстрагироваться по любому образцу, причем зачастую с возможностью использования уже существующих функций.

К примеру, рассмотрим класс типов для простейшего списка:

class  AbsList c where

nil    :: c a

cons  :: a → c a → c a

head  :: c a → Maybe (a, c a)

Тогда сопоставление с образцом можно записать как

instance  AbsList c  ⇒  Functor c where

fmap f l

| Just (x, xs)  ←  head l = f x `cons` fmap f xs

| Nothing          ←  head l = nil

В последовательно стоящих охранных выражениях можно использовать привязки из предыдущих:

filterMap :: AbsList c  ⇒  c a  →  (a  →  Maybe b)  →  c b filterMap f l

| Just (x, xs) ← head l,

Just v    ←  f x                = v `cons` filterMap f xs

| Just (x, xs) ← head l,

Nothing  ←  f x                = filterMap f xs

| Nothing          ←  head l   = nil

Таким образом любой одиночный образец для выражения типа τ может быть пред- ставлен как функция pat :: τ → Maybe ζ, где ζ являет собой некоторый кортеж, размерность которогоопределяет количество привязываемых при сопоставлении пе-

ременных, а его составляющие – типы этих привязок. Отметим, что в этом смысле Maybe ()эквивалентен Bool, а неопровержимые (irrefutable) образцы могут представ- лены просто как irrPat :: τ → ζ. Используется pat как

f x

| Just (...) ← pat x = ...

Заметим, однако, небольшую синтаксическую особенность – при таком использо- вании первым зачастую идет неопровержимый образец, именующий само инспекти- руемое выражение(scrutinee) – например, x в выражении f x выше. А уже образец, непосредственно разбирающий выражение, идет после, в охранном выражении. При

этом, как в примере с filterMap, если мы хотим применить функцию к одной из по- лученных привязок, необходимо записать это в следующем охранном выражении, что отличается оттрадиционной вложенной формы записи, при которой подобразцы запи- сываются прямо на месте привязок. К тому же это вызывает дублирование отдельных охранных выражений, как с Just (x, xs) ← head l в примере с filterMap.

Для устранения этой особенности в пользу более привычной формы записи в ра-

боте был предложен синтаксический сахар – преобразующие образцы. Они позволяли записывать сопоставление с результатом функции непосредственно внутри образца. Правда, насколько нам известно, в первоначальном варианте, предложенном в ра- боте, они так и не были реализованы, поскольку вместо них довольно быстро были добавлены так называемыепредставляющие образцы (view patterns), реализующие ту же самую идею. Используя эту нотацию filterMap можно переписать как

екте, именуемом экстрактором.

Однако, по сравнению с представляющими образцами в Haskell при сопоставлении с образцом никаких дополнительных синтаксических элементов вроде → или провер- ки с конструктором Just не требуется, что позволяет писать более краткий и выра-

Решение, предложенное в работе [23] обладает схожей выразительностью и в то же время позволяет объединять отдельные образцы в один многозначный, сопоставление с которым может быть проверено на полноту.

Например, для того же класса типов AbsList (в ML-языках представляемого мо- дулем) можно объединить образцы Cons и Nil в один неопровержимый двузначный образец:

let  (|Cons|Nil|) l =

match  head l with

| Some(hd, tl)  → Cons(hd, tl)

| None              → Nil

В качестве примера использования рассмотрим функцию destutter, удаляющую последовательные дубликаты элементов:

let  rec  destutter = function

| Cons(hd, Cons(hd', _) as  tl) when  hd = hd'  → destutter tl

| Cons(hd, tl)  → cons hd (destutter tl)

| Nil                → nil

При этом будет произведена проверка на полноту, которую эта реализация прой- дет благодаря второй и третьей ветвям, определяющим все возможные образцы для

входного значения.

В такой реализации используются “анонимные” типы-суммы, имена конструкторов которых не зависят от предметной области и состоят лишь из имени типа и порядко- вого номера. Такиетипы предопределяются языком F#, к примеру

type  ('a, 'b) choice =

| Choice2_1 of  'a

| Choice2_2 of  'b

Такое решение представляется также крайне удачным для реализации в языке OCaml, благодаря поддержке языком полиморфных вариантов, что любезно заметили авторы работы [23]. Полиморфные варианты позволяют заменить анонимные типы на более информативные и гибкие конструкторы-метки, к примеру

val  (|Cons|Nil|) :

'a AbsList.t  →[`Cons of  ('a ∗ 'a AbsList.t) |  `Nil]

Вместо

val  (|Cons|Nil|) :

'a AbsList.t  →('a ∗ 'a AbsList.t) choice

Пожалуй, единственным недостатком активных образцов, предложенных для F#, по сравнению с обычными образцами конструкторов типа, является тот факт, что первые можно использоватьтолько в сопоставлении с образцом, но не для конструирования данных. Так в примере выше для разбора значения списка используется активный образец Cons, а для конструированияотдельная функция cons. При этом даже самое первое решение в виде представлений [26] позволяет использовать один и тот же терм образца в обоих случаях.

Предложенное в работе [19] решение в виде синонимов образцов позволяло опре- делять неявные (implicit) или явные двунаправленные (explicit bidirectional) образцы, термы которых можно использовать как для конструирования, так и для разбора значений. К примеру, для класса типов AbsList можно определить

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

pattern Q :: Ord a ⇒ a → a → (a, a)

pattern Q x y ← (x, y) where

Q x y | x  �  y      = (x, y)

| otherwise = (y, x)

Здесь для конструирования требуется ограничение Ord, в то время как для сопо- ставления нет. Сигнатура образца выводится только из определения сопоставляющей части. Поэтому вданном случае потребуется явно указать сигнатуру, поскольку вы- веденная окажется слишком общей: Q :: a → b →(a, b).

Инициализация возврата к предыдущим сопоставлениям происходит бросанием статического исключения (оператор exit), перехват которого (оператор catch ... with ...)  означает  переход  к  рассмотрению  следующей  ветви.  Такие  ко- манды бросания исключения генерируются самой схемой компиляции и только внут- ри разбора ветви.

Данное расширение предлагает позволить пользователю инициировать такие воз- враты, причем не только внутри образца, но и в теле ветви, т.е. уже после успешного разбора образцов.Для этого требуется добавить в язык оператор возврата к сопо- ставлению (далее для краткости именуемый как оператор возврата), представляемый ключевым словом backtrack.Идеалогически такая конструкция близка широко ис-

пользуемым в императивных языках операторам возврата из цикла break и continue,

позволяющих ограниченное ручное управление потоком управления.

3.      Выбор конструкции для реализации

3.1.     Введение объективных критериев для сравнения

Для выбора конкретного дизайна необходимо научиться объективно сравнивать суще- ствующие решения, для чего в свою очередь необходимо ввести некоторые критерии. К настоящему моменту таких критериев не было сформулировано: существующие ре- шения сравнивались на некоторых отдельных группах примерах, оперируя такими субъективным понятиями как ”краткость синтаксиса”, ”расширяемость”, ”легковес- ность”, ”более общее” и т.п.

Для введения подходящих критериев стоит обратиться к теоретической части за- дачи. Что такое ”образец”? Что такое ”сопоставление с образцом”? Что такое ”кон- струкция сопоставления собразцом”? Какие теоретические задачи они призваны ре- шать? Опять-таки в существующих работах подобные понятия определяются специ- фично для конкретного языка: вводятся некоторые синтаксические конструкции, на- деляются определенной семантикой, и их называют уже перечисленными выше тер- минами. Поскольку сами определения как правило привязаны к конкретному языку, сравнивать конструкции между языками становится достаточно сложно.

М. Туллсен [25] первым указал на данную проблему и сосредоточился на теорети- ческой части. Введенные им определения не зависят от конкретного языка и приме- нимы к любому статическитипизированному языку с функциями высших порядков и алгебраическими типами данных.

Так       образец       определяется       как       произвольная       функция       типа  τ → Maybe ζ, сопоставление с образцом определяется как применение данной функ- ции к значению идекомпозиции результата (который ограничен типом Maybe ζ).

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

type  ('a, 'b) pat = 'a  → 'b option

(∗ Комбинатор ИЛИ ∗)

val  ($|): ('a, 'b) pat  → ('a, 'b) pat  → ('a, 'b) pat

(∗ Комбинатор И ∗)

val  ($&): ('a, 'b) pat  → ('a, 'b) pat  → ('a, 'b ∗ 'b) pat

(∗ Комбинатор композиции ∗)

val  ($:): ('a, 'b) pat  → ('b, 'c) pat  → ('a, 'c) pat

(∗ Комбинатор функтор-отображения ∗)

val  ($>): ('a, 'b) pat  → ('b  → 'c)     → ('a, 'c) pat

(∗ Комбинатор параллельного разбора ∗)

val  ($∗): ('a, 'c) pat  → ('b, 'd) pat  → ('a ∗ 'c, 'b ∗ 'd) pat

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

практически случаи использования образцов.

Наконец, представляется естественным определить  конструкцию сопоставления  с образцом, как встроенный язык описания предметной области (Embedded DSL), предоставляемыйхост-языком для определения образцов. Заметим, что существую- щие языки используют данную конструкцию одновременно и для применения сопо- ставления с определяемым образцом.

Благодаря такому определению мы естественным образом получаем критерий для сравнения ”мощности” различных дизайнов конструкций сопоставления:

Определение 1 (Максимальность).

Назовем конструкцию сопоставления с образцом максимальной, если она позво- ляет выразить произвольную композицию комбинаторов образцов.

Также интересным представляется формализовать свойство синтаксической крат- кости или выразительности:

Определение 2 (Выразительность).

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

Заметим, что для такого критерия его невыполнимость проверяется простым при- ведением контрпримера, а вот его выполнимость это формально технически сложное доказательство.

Крайне важно отметить, что полнота сопоставления еще формально не опреде- лена. Формально ”полнота” это свойство именно образца, однако по исторически при- чинам прижился термин ”полнота сопоставления”. Кажется естественным определить образец полным, если при сопоставлении с ним могут быть получены только ”непу- стые” значения, т.е. по М. Туллсену, все результирующие значения имеют тег Just. Несложно показать, что такое свойство неразрешимо. Тотальные активные образцы F# предлагают некоторое решение этой проблемы, позволяя в качествеобразцов ис-

          3.2.1.    Максимальность

          3.2.2.    Выразительность

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

Для всех расширений можно привести следующий синтетический пример дубли- рования, возникающий при использования комбинатора композиции и комбинатора ИЛИ.

type  t = C1

| C2

| C3

let _ =

match[@label outer]  a, b with

| _, b →

begin  match  b with

| C1 → 1

| C2 → 2

| C3 → backtrack%outer

end

| C2, C3  → 3

| _          → 4

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

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

Несмотря на некоторую кажущуюся искусственность ситуации такой шаблон в действительности возникал при написании промышленного ПО. В качестве примера, мы можем привести код на языке Scala [8], преобразующий язык из одного пред- ставления в другое. При этом существует некоторое ограниченное множество исклю- чительных ситуаций, которые по тем или иным причинамнеобходимо обработать особым образом. Множество ситуаций представлено одним большим сопоставлением,

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

Оператор возврата же в действительности не имеет этой проблемы и формаль- но даже является выразительным расширением, однако этот дизайн также нельзя назвать таковым спрактической точки зрения ввиду огромного синтаксического шу- ма ключевых слов при попытке использования образцов над абстрактными типами данных, а также вырождения сопоставлений впоследовательность и невозможности использования привычного структурного вложения образцов:

let rec destutter2 l =

match  head l with

| Some(hd, tl)  →

begin  match  head tl with

| Some(hd', _) when  hd = hd'  → destutter tl

| _ → cons hd (destutter tl)

end

| None  → nil

Сравните данную реализацию с предложенной в разделе 1.4 на основе активных образцов.

Таким образом решение данной проблемы состоит в том, чтобы совместить дизай- ны предоставляющие возможность возвратов (такие как pattern guards или оператор возврата) и дизайны предоставляющие абстракции на уровне структурного вложения (такие как view patterns и активные образцы). Можно заключить, что текущая экоси- стема Haskell, обладающая как pattern guards, так иview patterns наиболее близка к оптимальности по выразительности и не достигает ее лишь потому, что, как уже упо- миналось в разделе 2 pattern guards не позволяют разбирать несколько альтернатив внутри ветви.

          3.2.3.    Образцы первого класса

Выполнение или невыполнение данного свойства напрямую следует из определения каждого дизайна. Особенный случай здесь представляют лишь синонимы образцов, для которых кажетсяочевидным возможность использования их в качестве значений первого класса, но конкретной реализации пока не предоставлено — данный вопрос оставлен открытым и в самой работе [19].

          3.2.4.    Проверка на полноту

Как уже было отмечено, проверка на полноту в строгом смысле неразрешима, од- нако для каждого из расширений представлены достаточно точные аппроксимации. Впрочем точность,сложность реализации и производительность этих проверок до- вольно сильно варьируются от дизайна к дизайну. Скажем, для активных образцов и представлений SML такая проверка можетбыть реализована достаточно просто и эффективно [11], но вот для множества расширений языка Haskell проверка весьма

затруднительна и лишь недавно [20] был предложен сложный комплекс алгоритмов, использующих к примеру SMT-решатели для повышения точности выдаваемых пре- дупреждений.

Напомним, что для образцов первого порядка М. Туллсена, как уже упоминалось в 3.1, разумной аппроксимации можно добиться, только расширив их определение.

Для образцов представляемых объектами [5] ситуация с проверкой на полноту, как упоминалось ранее в 1.3, довольно сложна. Более того семантика языка Scala предписывает вызов функции-экстрактора на каждое сопоставление, не используя мемоизацию, и дозволяет использование эффектов, что, как описано в [17], кратно усложняет определения полноты и избыточности ветвей. Вопрос, какой аппроксима- ции можно добиться при таком дизайне остается открытым.

          3.2.5.    Эффективность

Эффективная компиляция сопоставлений над абстрактными типами данных это ма- лоизученная и открытая область для исследований. Для активных образцов (а равно и для представлений SML,выразимых через них) в оригинальной работе [23] представ- лена компиляция в деревья решений [22], и авторы утверждают, что можно добиться лучших результатов, используя дополнительные возможности платформы, такие как кортежи, передаваемые на стеке (unboxed tuples). Также открытым остается вопрос, какие из расширенного ряда оптимизаций, представленных в [12],применимы для активных образцов. Для комплекса расширений языка Haskell неизвестно публика- ций, раскрывающих вопросы оптимальной компиляции. Необходимо также учиты- вать различия стратегий вычисления и виды разрешенных алгебраических эффектов, используемых в языках, что еще более усложняет объективные сравнения.

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

Для решения этих проблем можно предложить два подхода:

4.2.     Правила типизации

К сожалению, для языка OCaml статическая семантика в литературе не представле- на. Поэтому добиться математической строгости в рамках данной работы априори не получится, ввиду того, чтострогость требует введения большого количества инстру- ментов и определений. По этим, а также по другим причинам, описанным в исход- ной работе [23], единственным способом для презентации правил типизации является представление эталонного типизирующего анализатора, производящего типизирован- ное абстрактное синтаксическое дерево для исходного кода.

v/Λ = v c(v1, . . . , vn)/k · o = vk/o

Теперь необходимо дополнить схему C∗ двумя параметрами — вхождением o, кото- рое призвано отслеживать, с какой частью входного выражения сейчас производится сопоставление и кэш-картой amap. Обновленная кэш-карта также будет возвращать- ся схемой в качестве третьего элемента, в дополнение к сгенерированному коду и таблице контекстов.

Вхождение изменяется естественным образом:

•    Для правил схемы компиляцией, выполняющих специализацию (таких как пра- вило конструктора (constructor-rule)), выполняемые рекурсивные вызовыдолж- ны получать специализацию вхождения по конструктору (такая операция фор- мально описана в работе [12]).

•    Для рекурсивного вызова правила переменных (variable-rule), вхождение инкре- ментируется.

•    Для компиляции матрицы P ll → Lll правила или-образцов (orpat-rule) [10] вхож- дение также инкрементируется.

•    В разделяющем правиле вхождение передается рекурсивным вызовам неизмен- ным.

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

let  (|M1|M2|) x = (∗ ... ∗)

let  (|C|_|)     x = (∗ ... ∗)

let  (|D|_|)     x = (∗ ... ∗)

let _ =

match  (1, 2, 3) with

| (M1 _, C  _, 42)  → 1

| (M2 _, D  _,   x)  → 2

| (C   _, _   ,   _)  → 3

5.      Заключение

В данной работе были достигнуты следующие результаты:

1.     Произведён подробный разбор аналогов в большинстве наиболее передовых функ- циональных языков, выделены решения, которые могут служить опорой для дизайна расширений для языка OCaml:

•    Представлено расширение оператора возврата к сопоставлению.

•    расширение синтаксиса

•    правила типизации новых конструкций

•    модификация схемы компиляции [10] для активных образцов

3.     Реализованы следующие элементы прототипа расширения:

•    синтаксический анализ

•    типизация

Список литературы

[2]    Bashkirov Alexander. Active patterns for OCaml. –– 2020. –– Режим доступа: https:

//github.com/ocaml/RFCs/pull/12 (дата обращения: 01.06.2020).

//www.microsoft.com/en-us/research/publication/pattern-synonyms/.