Возможности DSL на основе AST в представлении рекурсивных структур
Уже около года пишу Go, и столько же времени занимаюсь реализацией синтаксических деревьев. Сейчас все идет хорошо, но когда я начинал, это была настоящая борьба из-за того, что я не нашел никакого контента для начинающих, посвященного этой теме. Итак, это я делаю одолжение себе и, надеюсь, некоторым из вас.
Одной из полезных особенностей предметно-ориентированных языков на основе синтаксического дерева является их рекурсивный характер, что делает их превосходными для представления математических областей, таких как логика и алгебра. Таким образом, в качестве рабочего примера мы напишем программу, которая может символически представлять основные алгебраические выражения, а также манипулировать ими и вычислять их. Если вы не помешаны на математике, как я; Не волнуйтесь! В основном я сосредоточусь на деталях реализации нашей программы, а не на математике.
Предпосылки
Доменный язык (DSL)
Вам не нужно быть экспертом по предметно-ориентированным языкам (DSL), чтобы следовать этому курсу. На самом деле вам не нужно ничего знать о нем, кроме того, что это язык с меньшей областью применения, чем язык общего назначения (GPR), такой как Go. Это означает, что DSL оптимизирован для очень эффективного решения проблем в одной конкретной области (как с точки зрения вычислений, так и с точки зрения реализации) и может даже не поддерживать выполнение каких-либо действий за пределами этой области.
Поскольку DSL имеют очень ограниченную функциональность, они часто реализуются на других языках. Следовательно, пакет для построения SQL-запросов можно рассматривать как DSL, где предметной областью являются SQL-запросы. В случае нашего рабочего примера предметной областью будут алгебраические выражения, реализованные в виде пакета Go.
Абстрактное синтаксическое дерево (AST)
Абстрактное синтаксическое дерево (AST) — это структура данных, используемая для представления абстрактной синтаксической структуры некоторых данных. Для нас это означает, что, как следует из названия, AST представляет структуру и значение некоторых данных в виде дерева. Тип данных, который легко моделируется с помощью AST, обычно является рекурсивным, например. алгебраические выражения или исходный код. AST обычно используются в компиляторах, поскольку они позволяют представить значение.
Для наших намерений и целей достаточно понять, что алгебраическое выражение, т.е. 4 + 6x, представленный на рисунке 1, хорошо вписывается в древовидную структуру. Точнее, каждый оператор (+, -, *, /, Const, x) представлен узлом, а его аргументы, если они есть, представлены дочерними узлами.
Сочетание DSL и AST
Имея представление о том, что такое DSL и AST, мы можем собрать их воедино, чтобы сформировать идею, лежащую в основе нашего рабочего примера предметно-ориентированных языков на основе синтаксического дерева для простых алгебраических выражений.
Мы хотим иметь возможность представлять любое алгебраическое выражение одной переменной, содержащее любой или все основные арифметические операторы (+, -, *, /), и нам нужен какой-то способ вычисления данного выражения по некоторому заданному значению. Все это проиллюстрировано на рис. 2, где выражение 4 + 6x представлено в виде AST, а процесс его вычисления в x = 10, приводящий к 4 + 6*10 = 64, визуализируется.
Выполнение
Моделирование дерева с использованием структур
Наиболее важным инструментом при создании DSL на основе синтаксиса является система типов Go. Однако прежде чем приступить к построению древовидной структуры нашего AST, мы рассмотрим каждый узел на рисунке 1 и поймем, что существует два основных класса различных узлов; с детьми и без. Первый состоит из основных арифметических операций (+, -, *, /). Все они принимают два аргумента, которые в нашей древовидной структуре соответствуют своим дочерним элементам. Узлы без дочерних элементов — это листья нашей древовидной структуры, и можно увидеть, что они состоят из констант и переменных.
Затем мы понимаем, что каждый из различных типов узлов, по отдельности или связанных для формирования дерева, может рассматриваться как алгебраическое выражение. Поэтому мы определяем интерфейс как:
| type Expr interface { | |
| String() string | |
| } |
Чтобы алгебраические выражения печатались красиво, мы разрешили этому интерфейсу реализовать String-метод.
Теперь, с идентифицированными различными типами узлов и с интерфейсом, который улавливает их сходство, мы можем с помощью встраивания типов определить все различные типы узлов как структуры:
| /* Operand definitions */ | |
| type Const struct { | |
| Expr | |
| Value float64 | |
| } | |
| type X struct { | |
| Expr | |
| } | |
| type Add struct { | |
| Expr | |
| LHS Expr | |
| RHS Expr | |
| } | |
| type Sub struct { | |
| Expr | |
| LHS Expr | |
| RHS Expr | |
| } | |
| type Mul struct { | |
| Expr | |
| LHS Expr | |
| RHS Expr | |
| } | |
| type Div struct { | |
| Expr | |
| LHS Expr | |
| RHS Expr | |
| } |
Здесь внедрение типа относится к безымянному полю структуры типа Expr в верхней части каждой структуры. По сути, это аналог наследования в Go и говорится, что каждый тип узла также является Expr. Это позволяет определить дочерние элементы или аргументы для узлов любого типа, включающего интерфейс Expr.
Вот подробности реализации метода String:
| /* String formating rules for Expr */ | |
| func (e Const) String() string { | |
| return fmt.Sprint(e.Value) | |
| } | |
| func (e X) String() string { | |
| return "X" | |
| } | |
| func (e Add) String() string { | |
| return fmt.Sprintf("( %v ) + ( %v )", e.LHS, e.RHS) | |
| } | |
| func (e Sub) String() string { | |
| return fmt.Sprintf("( %v ) - ( %v )", e.LHS, e.RHS) | |
| } | |
| func (e Mul) String() string { | |
| return fmt.Sprintf("( %v ) * ( %v )", e.LHS, e.RHS) | |
| } | |
| func (e Div) String() string { | |
| return fmt.Sprintf("( %v ) / ( %v )", e.LHS, e.RHS) | |
| } |
Со всем этим реализованным мы можем построить выражение, показанное на рисунке 1, и распечатать его с помощью программы ниже.
| func main() { | |
| e := Add{ | |
| LHS: Const{Value:4}, | |
| RHS: Mul{ | |
| LHS: Const{Value:6}, | |
| RHS: X{}, | |
| }, | |
| } | |
| fmt.Println(e) | |
| } |
> go run main.go ( 4 ) + ( ( 6 ) * ( X ))
Eval-функция
Возможность представить алгебраическое выражение в Go с помощью структур и встраивания типов — это круто, но мы также хотели бы оценить его для заданного значения x. Для этого мы расширим интерфейс Expr, включив в него функцию Eval:
| type Expr interface { | |
| String() string | |
| Eval(float64) float64 | |
| } |
Поведение этой функции показано на рисунке 2; он принимает синтаксическое дерево и значение для x и возвращает выражение, оцененное по этому значению. Чтобы реализовать это, мы используем рекурсию, давая каждому типу узла свою собственную реализацию Eval с двумя типами листовых узлов (Const и x), которые являются базовыми для рекурсии, поскольку у них нет дочерних узлов. В случае нелистовых узлов функция Eval заменяет синтаксическую операцию той, которая фактически используется в Go, например. Add становится +, а затем рекурсивно делает то же самое с дочерними узлами. На практике это выглядит следующим образом:
| /* Evaluation patterns */ | |
| func (e Const) Eval(arg float64) float64 { | |
| return e.Value | |
| } | |
| func (e X) Eval(arg float64) float64 { | |
| return arg | |
| } | |
| func (e Add) Eval(arg float64) float64 { | |
| return e.LHS.Eval(arg) + e.RHS.Eval(arg) | |
| } | |
| func (e Sub) Eval(arg float64) float64 { | |
| return e.LHS.Eval(arg) - e.RHS.Eval(arg) | |
| } | |
| func (e Mul) Eval(arg float64) float64 { | |
| return e.LHS.Eval(arg) * e.RHS.Eval(arg) | |
| } | |
| func (e Div) Eval(arg float64) float64 { | |
| return e.LHS.Eval(arg) / e.RHS.Eval(arg) | |
| } |
Помимо представления алгебраического выражения и его вывода на терминал, теперь мы также можем оценить его по определенному значению. Пример того, как это сделать, показан в программе ниже:
| func main() { | |
| e := Add{ | |
| LHS: Const{Value:4}, | |
| RHS: Mul{ | |
| LHS: Const{Value:6}, | |
| RHS: X{}, | |
| }, | |
| } | |
| x := 10 | |
| val := e.Eval(x) | |
| fmt.Printf("%v = %v" e, val) | |
| } |
> go run main.go ( 4 ) + ( ( 6 ) * ( X )) = 64
Преобразование синтаксического дерева
Хорошо, мы можем представить алгебраическое выражение в виде древовидной структуры данных в нашей программе и оценить его для заданного значения, и что? Почему бы нам просто не написать выражение как лямбда-функцию напрямую, избавившись от проблем с деревьями и рекурсией? Я надеялся, что вы спросите, потому что мы еще не видели самого удивительного в синтаксических представлениях.
Допустим, по какой-то причине вам нужно вычислить производную нашего примерного выражения 4 + 6x. Если бы мы представили это выражение в виде лямбда-функции, мы могли бы только аппроксимировать производную для заданного значения x, но с нашей DSL на основе AST мы действительно можем выполнить дифференцирование в соответствии со всеми правилами, которые мы изучили на уроке математики, и таким образом, получить точную производную, которую мы затем можем вычислить в любой точке.
Чтобы сделать это возможным, нам снова нужно расширить наш интерфейс Expr функцией дифференцирования D:
| type Expr interface { | |
| String() string | |
| Eval(float64) float64 | |
| D() Expr | |
| } |
Затем, как и в случае с Eval-функцией, мы можем рекурсивно реализовать правила дифференцирования для каждого из различных операторов:
| /* Differentiation rules */ | |
| func (e Const) D() Expr { | |
| return Const{ Value: 0 } | |
| } | |
| func (e X) D() Expr { | |
| return Const{ Value: 1 } | |
| } | |
| func (e Add) D() Expr { | |
| return Add{ LHS: e.LHS.D(), RHS: e.RHS.D() } | |
| } | |
| func (e Sub) D() Expr { | |
| return Sub{ LHS: e.LHS.D(), RHS: e.RHS.D() } | |
| } | |
| // Product rule: (fg)' = f'g + fg' | |
| func (e Mul) D() Expr { | |
| return Add{ | |
| LHS: Mul{ LHS: e.LHS.D(), RHS: e.RHS }, | |
| RHS: Mul{ LHS: e.LHS, RHS: e.RHS.D() }, | |
| } | |
| } | |
| // Fraction rule: (f/g)' = (f'g - fg')/(g^2) | |
| func (e Div) D() Expr { | |
| return Div{ | |
| LHS: Sub{ | |
| LHS: Mul{ LHS: e.LHS.D(), RHS: e.RHS }, | |
| RHS: Mul{ LHS: e.LHS, RHS: e.RHS.D() }, | |
| }, | |
| RHS: Mul{ LHS: e.RHS, RHS: e.RHS }, | |
| } | |
| } |
Затем мы можем дифференцировать наше выражение, запустив следующую простую программу:
| func main() { | |
| e := Add{ | |
| LHS: Const{Value:4}, | |
| RHS: Mul{ | |
| LHS: Const{Value:6}, | |
| RHS: X{}, | |
| }, | |
| } | |
| deriv := e.D() | |
| fmt.Printf("D(%v) = %v" e, deriv) | |
| } |
> go run main.go D(( 4 ) + ( ( 6 ) * ( X ) )) = ( 0 ) + ( ( ( 0 ) * ( X ) ) + ( ( 6 ) * ( 1 ) ) )
В выводе много избыточных терминов, что связано с тем, что мы никогда не упрощаем наше выражение, а получаем то, что ожидаем; D(4 + 6x) = 0 + 0*x + 6*1 = 6.
Заключение
Теперь мы увидели, насколько полезными могут быть DSL на основе AST для представления рекурсивных структур, особенно алгебраических выражений, и как их реализовать в Go. Мы также видели, насколько полезными могут быть синтаксические представления при выполнении символических преобразований, таких как дифференцирование.
Если вы нашли это интересным, вам повезло, потому что с AST и DSL можно делать гораздо больше. Я впервые столкнулся с этой темой в курсе предметно-ориентированных языков математики в Технологическом университете Чалмерса, который является курсом с открытым исходным кодом, и его содержание можно найти в этом репозитории G ithub. Тем не менее, содержание курса довольно насыщено математикой, но ссылки в файле README репозитория содержат некоторую литературу, которая охватывает эту тему без особой математики.
