В последнее время все большую популярность приобретают предметно-ориентированные языки (domain-specific languages - DSL). Вследствие этого одной из наиболее важных характеристик функциональных языков является их применимость для создания DSL. В новой статье серии " Путеводитель по Scala для Java-разработчиков " Тед Ньювард начинает рассказ о создании простого языка-калькулятора, демонстрируя тем самым мощь функциональных языков при разработке "внешних" DSL. Вы откроете для себя такую новую возможность Scala как case-классы , а также вновь увидите в действии метод сопоставления с образцом , который уже описывался ранее.
После опубликования предыдущей статьи я получил несколько критических отзывов от читателей, которые жаловались на слишком сильное упрощение примеров. Несмотря на то, что на ранних этапах описания нового языка имеет смысл использовать тривиальные примеры, читатели имеют законное право требовать более реалистичных задач, на которых можно было бы убедительно продемонстрировать всю глубину и широту возможностей языка. Поэтому в данной статье - первой в мини-серии из двух частей - мы начнем создавать новый предметно-ориентированный язык (DSL) для решения простых вычислительных задач. Назовем его "Калькулятор".
|
Предметно-ориентированные языки
Если по каким-то причинам, например из-за отсутствия времени, вы не можете позволить себе изучать новые технологии, то я просто сформулирую, что такое DSL. Предметно-ориентированные языки - это очередная попытка дать способ контроля над возможностями приложения именно тем, кто и должен им обладать - пользователям.
Создав новый язык, достаточно простой и понятный для пользователей, разработчики могут снять с себя часть непрекращающейся работы по удовлетворению запросов о различных улучшениях интерфейса и других частей приложения. При помощи DSL пользователи могут создавать скрипты и различные утилиты для гибкой настройки приложений под их нужды. Классическим примером DSL, получившим широкую популярность, является язык, использующийся в Microsoft Office Excel, который применяется для описания различных вычислений и операций над данными ячеек таблиц (возможно, этот пример спровоцирует ряд гневных писем от читателей). Некоторые приверженцы DSL даже утверждают, что SQL является примером DSL, так как он служит исключительно для взаимодействия с реляционными базами данных. Попробуйте себе представить, что было бы, если бы программистам пришлось работать с файлами базы данных Oracle напрямую, используя стандартный API на основе функций read()/write().
DSL, который будет создан ниже, представляет собой простой язык описания и вычисления математических выражений. Фактически нашей целью будет разработка элементарного языка, при помощи которого пользователи могли бы создавать простые алгебраические выражения с возможностью их дальнейшего вычисления и получения результатов. Несмотря на то, что перед нами не стоит задача поддерживать все функции, обычно предоставляемые полноценными конструкторами выражений, наш DSL отнюдь не будет элементарным учебным примером. Он должен быть достаточно гибким для того, чтобы вы могли расширять его в дальнейшем, если вам понадобится более мощный язык, при этом не разрабатывая его заново. Таким образом, язык должен быть легко расширяемым и поддерживать максимальную степень инкапсуляции, но при этом оставаться простым в использовании.
|
Другими словами, в конечном итоге язык должен позволять клиентам создавать и вычислять выражения аналогично тому, как показано в листинге 1.
Листинг 1. Каким должен быть DSL арифметических выражений
// использование интерпретатора DSL в Java
String s = "((5 * 10) + 7)";
double result = com.tedneward.calcdsl.Calculator.evaluate(s);
System.out.println("We got " + result); // Should be 57
|
В настоящей статье мы начнем создавать DSL на Scala и завершим эту работу в следующем выпуске серии.
Может показаться, что с точки зрения проектирования и реализации языка следует создать строковый синтаксический анализатор (парсер), работающий по принципу: "перебирать символы и вычислять выражение по мере его анализа". Этот подход может быть применим для простых языков, однако он плохо масштабируется. Поскольку нашей задачей является создание расширяемого языка, то имеет смысл подождать с реализаций и тщательнее продумать дизайн языка.
Те из вас, кто обладает базовым представлением о теории компиляторов, знают, что работа транслятора (компилятора или интерпретатора) состоит как минимум из двух основных шагов:
- парсер обрабатывает текст программы и трансформирует его в абстрактное синтаксическое дерево (AST);
- генератор кода (в случае компилятора) обрабатывает AST и генерирует машинный код, либо блок вычислений (в случае интерпретатора) исполняет команды, содержащиеся в AST.
Разделение этих шагов работы транслятора на отдельные фазы позволяет выполнять оптимизацию промежуточного представления кода в AST. Например, в случае калькулятора можно проанализировать выражения и в ряде случаев отбросить целые его части, в частности операнды, умножаемые на ноль (поскольку результат гарантированно будет равен нулю).
Таким образом, нашей первой задачей будет определение AST для языка выражений. К счастью, в Scala есть case-классы . Они не предоставляют мощных средств инкапсуляции, но в них удобно хранить данные, что в совокупности с другими возможностями делает их подходящим инструментом для создания AST.
Перед тем как углубиться в тему AST, следует ненадолго остановиться на понятии case-класса. Case-классы - это механизм в Scala, облегчающий создание классов, члены которых должны иметь определенные значения по умолчанию.
Листинг 2. Case-класс для представления человека
case class Person(first:String, last:String, age:Int)
{
}
|
Например, при трансляции класса, приведенного в листинге 2, компилятор Scala не просто генерирует стандартный конструктор, но также создает реализацию методов equals(), toString() и hashCode(). Кстати говоря, подобные case-классы, не обладающие никакими дополнительными методами, настолько часто встречаются на практике, что синтаксис позволяет опустить фигурные скобки в объявлении (листинг 3).
Листинг 3. Самое короткое в мире объявление класса
case class Person(first:String, last:String, age:Int) |
В листинге 4 показано, как case-класс преобразуется в Java при компиляции.
Листинг 4. Результат декомпиляции класса при помощи javap
C:\Projects\Exploration\Scala>javap Person
Compiled from "case.scala"
public class Person extends java.lang.Object implements scala.ScalaObject,scala.
Product,java.io.Serializable{
public Person(java.lang.String, java.lang.String, int);
public java.lang.Object productElement(int);
public int productArity();
public java.lang.String productPrefix();
public boolean equals(java.lang.Object);
public java.lang.String toString();
public int hashCode();
public int $tag();
public int age();
public java.lang.String last();
public java.lang.String first();
}
|
Как видите, при компиляции case-классов компилятор выполняет гораздо больше действий, чем обычно, потому что изначально подразумевается, что case-классы будут использоваться в сочетании с механизмом сопоставления с образцом.
Использование case-классов также отличается от обычных классов тем, что, как правило, они инстанциируются не при помощи традиционного оператора "new". В основном для создания экземпляров case-классов применяется фабричный метод, имя которого совпадает с именем класса. Пример приведен в листинге 5.
Листинг 5. Где же оператор "new"?
object App
{
def main(args : Array[String]) : Unit =
{
val ted = Person("Ted", "Neward", 37)
}
}
|
Сами по себе case-классы выглядят не намного интереснее, чем обычные классы (даже различия кажутся несущественными). Однако разница становится ощутимой при их использовании, в частности, при побитовом, а не ссылочном сравнении экземпляров case-классов. Например, результаты выполнения кода в листинге 6 могут показаться удивительными для Java-разработчиков.
Листинг 6. Пример сравнения экземпляров case-классов
object App
{
def main(args : Array[String]) : Unit =
{
val ted = Person("Ted", "Neward", 37)
val ted2 = Person("Ted", "Neward", 37)
val amanda = Person("Amanda", "Laucher", 27)
System.out.println("ted == amanda: " +
(if (ted == amanda) "Yes" else "No"))
System.out.println("ted == ted: " +
(if (ted == ted) "Yes" else "No"))
System.out.println("ted == ted2: " +
(if (ted == ted2) "Yes" else "No"))
}
}
/*
C:\Projects\Exploration\Scala>scala App
ted == amanda: No
ted == ted: Yes
ted == ted2: Yes
*/
|
Главное преимущество case-классов становится очевидным при использовании механизма сопоставления с образцом. Как вы помните из второй части серии, посвященной конструкциям управления в Scala, оператор сопоставления с образцом напоминает "switch/case" в Java, однако обладает гораздо более широкими возможностями. С его помощью можно не только проверять значения объектов, но также тестировать их на соответствие шаблону (в результате получается некий частичный вариант блока "default"), использовать охраняющие выражения (guard) в блоках case, связывать сопоставленные значения с локальными переменными, а также выполнять сопоставление на основе типов.
Case-классы открывают новый пласт возможностей для использования сопоставления с образцом (листинг 7).
Листинг 7. Пример использования сопоставления экземпляров case-классов с образцом
case class Person(first:String, last:String, age:Int);
object App
{
def main(args : Array[String]) : Unit =
{
val ted = Person("Ted", "Neward", 37)
val amanda = Person("Amanda", "Laucher", 27)
System.out.println(process(ted))
System.out.println(process(amanda))
}
def process(p : Person) =
{
"Processing " + p + " reveals that" +
(p match
{
case Person(_, _, a) if a > 30 =>
" they're certainly old."
case Person(_, "Neward", _) =>
" they come from good genes...."
case Person(first, last, ageInYears) if ageInYears > 17 =>
first + " " + last + " is " + ageInYears + " years old."
case _ =>
" I have no idea what to do with this person"
})
}
}
/*
C:\Projects\Exploration\Scala>scala App
Processing Person(Ted,Neward,37) reveals that they're certainly old.
Processing Person(Amanda,Laucher,27) reveals that Amanda Laucher is 27 years old
.
*/
|
В листинге 7 происходит много интересного, поэтому имеет смысл остановиться на нем подробнее, а затем вернуться к калькулятору и постараться применить новые возможности.
Прежде всего обратите внимание, что выражение match полностью заключено в круглые скобки. Это не является частью синтаксиса сопоставления с образцом, а делается только потому, что результат всего выражения (как вы помните, любая конструкция в функциональном языке является выражением) конкатенируется с префиксом, расположенным строчкой выше.
Во-вторых, в первом выражении case используются два шаблонных символа подчеркивания. Это означает, что образцу будут удовлетворять экземпляры Person с любыми значениями этих полей. При этом значение поля p.age, удовлетворяющее образцу, будет присвоено локальной переменной a. Истинность данного блока case определяется истинностью условия охраняющего выражения (блока if, следующего за case). В примере выше охраняющее выражение будет истинным только для первого экземпляра Person. Во втором блоке case используется шаблонный символ для поля firstName, а проверка осуществляется только над полем lastName, которое сравнивается со строкой Neward. Поле age при сопоставлении также игнорируется.
Второй блок case не сработает ни для одного из экземпляров Person, поскольку первый экземпляр будет успешно сопоставлен с образцом в первом case, а фамилия второго экземпляра - не Neward. Блок мог бы сработать, например, для экземпляра Person("Michael", "Neward", 15), так как в этом случае охраняющее выражение в первом блоке было бы ложным.
Третий блок case является типичным примером так называемого извлечения (extraction) при использовании метода сопоставления с образцом. В нем происходит извлечение значений всех полей сопоставленного объекта и их присвоение локальным переменным (в данном случае first, last и ageInYears). Последний case представляет собой стандартный блок default, который выполняется в том случае, если не сработал ни один из блоков case выше.
Теперь, после краткого обзора возможностей case-классов и сопоставления с образцом, можно переходить к задаче построения AST для языка выражений.
Начнем с того, что AST языка выражений должна иметь некоторую общую систему типов, так как математические выражения часто представляют собой иерархию (т. е. состоят из подвыражений). Легче всего это увидеть на примере простого выражения "5 + (2 * 10)". Здесь подвыражение "(2 * 10)" является правым операндом в операции "+".
На самом деле в этом выражении присутствуют следующие типы узлов в AST:
- базовый тип Expression;
- тип Number для представления численных констант;
- тип BinaryOperator для представления операции и двух ее операндов.
Не забывайте, что в математике также используются унарные операции, в частности, отрицания (смена знака), которые меняет знак числа на противоположный. Учитывая этот момент, мы будем работать со следующей системой типов для AST (листинг 8).
Листинг 8. AST языка выражений (src/calc.scala)
package com.tedneward.calcdsl
{
private[calcdsl] abstract class Expr
private[calcdsl] case class Number(value : Double) extends Expr
private[calcdsl] case class UnaryOp(operator : String, arg : Expr) extends Expr
private[calcdsl] case class BinaryOp(operator : String, left : Expr, right : Expr)
extends Expr
}
|
Обратите внимание на объявление пакета, который будет содержать все эти типы (com.tedneward.calcdsl), а также на модификаторы доступа перед каждым из классов. Они говорят о том, что данные классы должны быть доступны для всех членов этого и дочерних пакетов. Возможность доступа к этим классам позволит нам создать набор JUnit-тестов для проверки корректности кода. При этом клиентские приложения, использующие калькулятор, не должны видеть типы AST. Далее создадим юнит-тест и поместим его в пакет, дочерний по отношению к com.tedneward.calcdsl (листинг 9).
Листинг 9. Тестирование калькулятора (testsrc/calctest.scala)
package com.tedneward.calcdsl.test
{
class CalcTest
{
import org.junit._, Assert._
@Test def ASTTest =
{
val n1 = Number(5)
assertEquals(5, n1.value)
}
@Test def equalityTest =
{
val binop = BinaryOp("+", Number(5), Number(10))
assertEquals(Number(5), binop.left)
assertEquals(Number(10), binop.right)
assertEquals("+", binop.operator)
}
}
}
|
Пока все идет хорошо. У нас уже есть AST.
Задумайтесь на секунду: написав четыре строки кода на Scala, мы определили иерархию типов для представления произвольных математических выражений (пусть и простых, но тем не менее). Пока это трудно назвать функциональным кодом, скорее это просто иллюстрация того, как Scala упрощает объектно-ориентированное программирование. Но не волнуйтесь, элементы функционального стиля появятся позже.
Далее нам необходима функция для вычисления выражения. Она должна принимать на вход AST и возвращать результат вычисления. Механизм сопоставления с образцом превращает написание этой функции в тривиальное упражнение (листинг 10).
Листинг 10. Калькулятор (src/calc.scala)
package com.tedneward.calcdsl
{
// ...
object Calc
{
def evaluate(e : Expr) : Double =
{
e match {
case Number(x) => x
case UnaryOp("-", x) => -(evaluate(x))
case BinaryOp("+", x1, x2) => (evaluate(x1) + evaluate(x2))
case BinaryOp("-", x1, x2) => (evaluate(x1) - evaluate(x2))
case BinaryOp("*", x1, x2) => (evaluate(x1) * evaluate(x2))
case BinaryOp("/", x1, x2) => (evaluate(x1) / evaluate(x2))
}
}
}
}
|
Как видите, функция evaluate() возвращает результат типа Double. Это означает, что каждый блок case выражения match должен возвращать Double. В этом нет ничего сложного: в случае типа Number необходимо просто вернуть заключенное внутри значение. Однако в остальных случаях необходимо сначала вычислить значения операндов, а уже затем выполнить над ними нужную операцию (отрицание, сложение, вычитание и т. д.). В соответствии с тем, как это принято в функциональных языках, мы просто рекурсивно вызываем функцию evaluate() для каждого операнда перед выполнением самой операции.
Сама идея, заключающаяся в том, что вычисление выполняется не внутри операторов, наверняка будет выглядеть глубоко ошибочной в глазах большинства закоренелых программистов на объектно-ориентированных языках, так как она грубо нарушает принципы инкапсуляции и полиморфизма. Тут даже обсуждать нечего - она действительно идет вразрез с инкапсуляцией, по крайней мере, если последнюю рассматривать в традиционном смысле.
Если же ставить вопрос шире, то он будет заключаться в том, от чего именно должен быть скрыт (инкапсулирован) код вычисления выражения? Как вы помните, классы AST невидимы за пределами данного пакета, поэтому клиенты будут просто передавать на вход строковое представление выражения. С AST напрямую будут работать исключительно классы юнит-тестов.
Это отнюдь не означает, что принцип инкапсуляции кода потерял свою актуальность. На самом деле все совсем наоборот: данный пример намекает на то, что он может быть реализован способами, отличными от тех, которые принято использовать в объектно-ориентированном программировании. Не забывайте, что Scala позволяет работать как с объектами, так и с функциями, поэтому в тех ситуациях, когда класс Expr должен обладать некоторой функциональностью (например, форматированный вывод через метод toString), она может быть легко реализована путем добавления нужных методов. Объектно-ориентированный и функциональный стили программирования хорошо дополняют друг друга, поэтому сторонники любого из них должны не игнорировать варианты дизайна, базирующиеся на противоположном подходе, а наоборот - искать решения, сочетающие в себе лучшие качества обоих и позволяющие достигать интересных результатов.
С точки зрения дизайна другие выбранные решения менее очевидны. В частности, использование строк для представления операций допускает возможность опечаток, которые могут приводить к ошибочным результатам. В реальном приложении для этого должны использоваться перечисления. Однако строки позволяют в будущем расширить язык, включив поддержку более сложных функций, например, abs, sin, cos, tan и т. д. Более того, можно даже дать пользователям возможность реализовывать собственные функции. Подобные расширения было бы сложнее предусмотреть при использовании перечислений.
Как это обычно бывает при проектировании и реализации приложений, не существует одного, единственно верного пути, есть лишь последствия. Как говорится, да будет осмотрителен покупатель.
Существует один интересный пример, который можно применить при реализации данной функции. Некоторые математические выражения могут быть упрощены, что потенциально может оптимизировать их вычисление (это, кстати говоря, одна из причин использования AST).
- результат сложения с нулем эквивалентен ненулевому операнду;
- результат умножения на единицу эквивалентен второму операнду;
- умножение на ноль всегда равно нулю.
И так далее. Подобными упрощениями будет заниматься функция simplify(), вызываемая до вычисления выражения. Код функции приведен в листинге 11.
Листинг 11. Калькулятор (src/calc.scala)
def simplify(e : Expr) : Expr =
{
e match {
// Двойное отрицание не меняет значение операнда
case UnaryOp("-", UnaryOp("-", x)) => x
// Знак "+" не меняет значение операнда
case UnaryOp("+", x) => x
// Умножение x на 1 равно х
case BinaryOp("*", x, Number(1)) => x
// Умножение 1 на x равно х
case BinaryOp("*", Number(1), x) => x
// Умножение х на 0 равно 0
case BinaryOp("*", x, Number(0)) => Number(0)
// Умножение 0 на x равно 0
case BinaryOp("*", Number(0), x) => Number(0)
// Деление х на 1 равно х
case BinaryOp("/", x, Number(1)) => x
// Добавление х к 1 равно х
case BinaryOp("+", x, Number(0)) => x
// Добавление 1 к х равно х
case BinaryOp("+", Number(0), x) => x
// Других вариантов упрощения нет
case _ => e
}
}
|
Как и в случае вычисления выражений, бросается в глаза то, насколько возможности механизма сопоставления с образцом, а именно сравнение с константами и связывание с переменными, упрощают код подобных функций (листинг 12). При этом единственное изменение функции evaluate() будет заключаться в добавлении вызова simplify().
Листинг 12. Калькулятор (src/calc.scala)
def evaluate(e : Expr) : Double =
{
simplify(e) match {
case Number(x) => x
case UnaryOp("-", x) => -(evaluate(x))
case BinaryOp("+", x1, x2) => (evaluate(x1) + evaluate(x2))
case BinaryOp("-", x1, x2) => (evaluate(x1) - evaluate(x2))
case BinaryOp("*", x1, x2) => (evaluate(x1) * evaluate(x2))
case BinaryOp("/", x1, x2) => (evaluate(x1) / evaluate(x2))
}
}
|
Функцию упрощения выражений можно развивать и далее. Вы могли заметить, что на данный момент она упрощает только выражения, находящиеся на нижнем уровне AST. Однако если, например, узел дерева содержит объект BinaryOp, операндами которого являются BinaryOp("*", Number(0), Number(5)) и Number(5), то вложенный BinaryOp может быть упрощен до Number(0), после чего станет очевидно, что основной BinaryOp также равен 0 (поскольку происходит умножение на ноль).
Пользуясь своим правом автора, я оставлю это в качестве упражнения для читателей. При этом если кто-то из вас пришлет мне свою реализацию, то я включу ее в текст и исходный код к следующей статье (разумеется, с указанием имени автора). На данный момент существует несколько юнит-тестов, которые проверяют упрощение выражений. Пока они сигнализируют об ошибке. Задача того, кто возьмется за эту работу - сделать так, чтобы эти и все любые другие тесты, в которых могут использоваться AST, содержащие BinaryOp и UnaryOp на произвольной глубине, выполнялись без ошибок.
Очевидно, что работа еще не завершена, в частности, необходимо реализовать синтаксический разбор выражений, заданных в текстовом виде. Тем не менее, часть, связанная с AST, практически готова. Мы можем добавлять новые операции без серьезной переработки существующего кода. При этом обход дерева не требует написания большого объема кода, например, в стиле паттера Посетитель (Visitor) из книги Банды Четырех. Наконец, у нас уже есть реализация функции вычислений, которая может вычислять значения выражений по готовому дереву AST.
Главной целью статьи было продемонстрировать, как при помощи case-классов и механизма сопоставления с образцом можно решить задачу создания и обработки AST тривиальным образом. Аналогичный подход очень часто встречается в программах на Scala (как и в большинстве функциональных языков), поэтому если вы планируете серьезно заниматься разработкой на Scala, то вам просто необходимо его освоить.