Содержание


Путеводитель по Scala для Java-разработчиков

Часть 3. Создание калькулятора

Совместное использование case-классов и комбинаторов парсеров

Comments

Серия контента:

Этот контент является частью # из серии # статей: Путеводитель по Scala для Java-разработчиков

Следите за выходом новых статей этой серии.

Этот контент является частью серии:Путеводитель по Scala для Java-разработчиков

Следите за выходом новых статей этой серии.

Приветствую вас, отважные читатели! Путешествие в мир Scala и его стандартных библиотек продолжается. В этой статье мы, наконец, завершим работу над DSL арифметических выражений. Сам по себе данный язык достаточно тривиален, он поддерживает только четыре математических операции, однако нашей целью является создание гибкого интерпретатора, который можно было бы легко расширять в дальнейшем.

Оглянемся назад

Как вы помните, на данный момент наш DSL представляет собой несколько несвязанных между собой компонентов. Во-первых, готова реализация абстрактного синтаксического дерева (AST) на основе case-классов (листинг 1).

Листинг 1. AST
package com.tedneward.calcdsl
{
  // ...

  private[calcdsl] abstract class Expr
  private[calcdsl]  case class Variable(name : String) extends 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

}

Выражение, представленное в виде AST, можно упрощать и вычислять путем обхода дерева (листинг 2).

Листинг 2. Интерпретатор AST
package com.tedneward.calcdsl
{
  // ...

  object Calc
  {
        def simplify(e: Expr): Expr = {
      // сначала упрощаем подвыражения
      val simpSubs = e match {
        // упрощаем обе части выражения
        case BinaryOp(op, left, right) => BinaryOp(op, simplify(left), simplify(right))
        // упрощаем операнд
        case UnaryOp(op, operand) => UnaryOp(op, simplify(operand))
        // здесь нечего упрощать
        case _ => e
      }

      // теперь упрощаем само выражение, считая,
      // что все вложенные выражения уже упрощены
      def simplifyTop(x: Expr) = x 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
      }
      simplifyTop(simpSubs)
    }
  
    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))
      }
    }
  }
}

Во-вторых, у нас готов текстовый парсер, созданный при помощи библиотеки комбинаторов в Scala. Он способен осуществлять синтаксический разбор простых арифметических выражений (листинг 3).

Листинг 3. Парсер арифметических выражений
package com.tedneward.calcdsl
{
  // ...

  object Calc
  {
    object ArithParser extends JavaTokenParsers
    {
      def expr: Parser[Any] = term ~ rep("+"~term | "-"~term)
      def term : Parser[Any] = factor ~ rep("*"~factor | "/"~factor)
      def factor : Parser[Any] = floatingPointNumber | "("~expr~")" 
      
      def parse(text : String) =
      {
        parseAll(expr, text)
      }
    }
    
    // ...
  }
}

На данный момент парсер в качестве результата возвращает наборы строк и списков. Комбинаторы парсеров по умолчанию возвращают экземпляры типа Parser[Any], предоставляя парсерам самим выбирать типы возвращаемых значений (в нашем случае - это наборы экземпляров List и String).

Однако, чтобы быть полезным, парсер должен возвращать объекты тех типов, которые присутствуют в AST, чтобы по окончании разбора интерпретатор мог вычислить выражение, представленное в виде дерева (для этого служит метод evaluate()). Таким образом, необходимо изменить реализацию комбинаторов парсеров для того, чтобы возвращать экземпляры нужных типов на этапе синтаксического разбора.

Коррекция грамматики

Для начала следует слегка модифицировать грамматику нашего языка. На данный момент выражения типа "5 + 5 + 5" являются грамматически корректными благодаря комбинатору rep(), использующемуся при описании выражений (expr) и операндов (term). Однако это может в будущем привести к проблемам, связанным с ассоциативностью операций, так как некоторые операции могут потребовать явного указания приоритетов при помощи скобок. Поэтому первым делом мы внесем изменения в грамматику, указав, что все выражения должны быть заключены в круглые скобки.

На самом деле, это необходимо было сделать в самом начале создания DSL. Как правило, бывает гораздо легче ослаблять требования к любой разрабатываемой системе (если они оказываются несущественными), чем добавлять их по ходу работы, однако существует несколько неприятных проблем, связанных с ассоциативностью и приоритетом операций, которые трудно предусмотреть. Если вы не до конца представляете себе, что такое ассоциативность или приоритет операций, то постарайтесь прочитать материалы, посвященные этой теме. В частности, в спецификации языка Java можно найти общее описание сложностей, обусловленных операциями, поддерживаемыми в Java. Проблемы, связанные с ассоциативностью, также рассматриваются в книге "Загадки Java" (авторы Блох, Bloch и Гафтер, Gafter). Поверьте, картина вырисовывается весьма неприглядная.

Мы же начнем с малого, а именно – вновь протестируем грамматику языка (листинг 4).

Листинг 4. Тестирование грамматики со скобками
package com.tedneward.calcdsl
{
  // ...

  object Calc
  {
    // ...
    
    object OldAnyParser extends JavaTokenParsers
    {
      def expr: Parser[Any] = term ~ rep("+"~term | "-"~term)
      def term : Parser[Any] = factor ~ rep("*"~factor | "/"~factor)
      def factor : Parser[Any] = floatingPointNumber | "("~expr~")" 
      
      def parse(text : String) =
      {
        parseAll(expr, text)
      }
    }
    object AnyParser extends JavaTokenParsers
    {
      def expr: Parser[Any] = (term~"+"~term) | (term~"-"~term) | term
      def term : Parser[Any] = (factor~"*"~factor) | (factor~"/"~factor) | factor
      def factor : Parser[Any] = "(" ~> expr <~ ")" | floatingPointNumber
      
      def parse(text : String) =
      {
        parseAll(expr, text)
      }
    }
    
    // ...
  }
}

Как видите, мы переименовали старую версию парсера в OldAnyParser и оставили ее для сравнения. Новая грамматика реализуется парсером под именем AnyParser. Обратите внимание, что в соответствии с ней выражения (expr) могут принимать вид term + term, term - term, просто term и т. д. Другое существенное изменение коснулось определения элемента factor, в котором теперь используются другие комбинаторы, а именно - ~> и <~. Они будут отбрасывать встречающиеся символы круглых скобок.

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

Листинг 5. Фальшивый, но тем не менее полезный тест
package com.tedneward.calcdsl.test
{
  class CalcTest
  {
    import org.junit._, Assert._
    
    // ...
    
    @Test def parse =
    {
      import Calc._
      
      val expressions = List(
        "5",
        "(5)",
        "5 + 5",
        "(5 + 5)",
        "5 + 5 + 5",
        "(5 + 5) + 5",
        "(5 + 5) + (5 + 5)",
        "(5 * 5) / (5 * 5)",
        "5 - 5",
        "5 - 5 - 5",
        "(5 - 5) - 5",
        "5 * 5 * 5",
        "5 / 5 / 5",
        "(5 / 5) / 5"
      )
      
      for (x <- expressions)
        System.out.println(x + " = " + AnyParser.parse(x))
    }
  }
}

Помните, что этот тест служит исключительно педагогическим целям (другими словами, это означает следующее: "Такое непозволительно писать в реальном приложении, однако поскольку я не пишу реальное приложение, то могу позволить себе схалтурить. Вы – нет. Точка"). Тем не менее, при запуске этот "тест" выведет результаты в стандартную секцию выходного файла юнит-тестов, и вы увидите, что разбор выражений без скобок (например, 5 + 5 + 5) завершается с ошибкой, в то время как выражения со скобками разбираются нормально. Великолепно.

Не забудьте потом закомментировать этот тест. А еще лучше – удалите его бесследно. Это чистейшей воды мошенничество, а как мы все знаем, настоящие джедаи используют Силу только в благих целях и никогда – в мошеннических.

Продолжаем корректировать грамматику

Теперь необходимо вновь изменить определения некоторых комбинаторов. Как вы помните из предыдущей статьи, каждая функция (expr, term и factor) представляет собой грамматическое правило в БНФ, при этом типом ее возвращаемого значения является параметризованный класс Parser, где в качестве аргумента шаблона выступает Any. Any является вершиной иерархии типов в Scala, его имя недвусмысленно говорит о том, что любой объект в Scala неявно принадлежит типу Any. Таким образом, пока комбинаторы могут возвращать все, что им заблагорассудится, в частности – экземпляры классов String и List. В этом несложно убедиться, вновь запустив наш псевдотест из листинга 5.

Для того чтобы заставить комбинаторов возвращать экземпляры типов, присутствующих в AST, необходимо изменить тип в определении комбинаторов на Parser[Expr]. Однако если этим ограничиться, то компиляция завершится с ошибками, потому что данные три комбинатора умеют представлять результаты разбора только в виде объектов String, но не Expr. Поэтому мы создадим еще один комбинатор под именем ^^, который будет принимать на вход анонимную функцию и передавать ей результат синтаксического разбора.

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

Листинг 6. Комбинатор ^^
package com.tedneward.calcdsl
{
  // ...

  object Calc
  {
    object ExprParser extends JavaTokenParsers
    {
      def expr: Parser[Expr] =
        (term ~ "+" ~ term) ^^ { case lhs~plus~rhs => BinaryOp("+", lhs, rhs) } |
        (term ~ "-" ~ term) ^^ { case lhs~minus~rhs => BinaryOp("-", lhs, rhs) } |
        term 

      def term: Parser[Expr] =
        (factor ~ "*" ~ factor) ^^ { case lhs~times~rhs => BinaryOp("*", lhs, rhs) } |
        (factor ~ "/" ~ factor) ^^ { case lhs~div~rhs => BinaryOp("/", lhs, rhs) } |
        factor

      def factor : Parser[Expr] =
        "(" ~> expr <~ ")" |
        floatingPointNumber ^^ {x => Number(x.toFloat) }
      
      def parse(text : String) = parseAll(expr, text)
    }
  
    def parse(text : String) =
      ExprParser.parse(text).get

    // ...
  }
  
  // ...
}

Комбинатор ^^ принимает на вход анонимную функцию и передает ей результат синтаксического разбора, который она трансформирует в объект типа, присутствующего в AST. Например, результатом разбора выражения 5 + 5 будет строка ((5~+)~5)), которая затем будет преобразована в объект типа BinaryObject. Вновь обратите внимание на мощь сопоставления с образцом: левая часть выражения присваивается переменной lhs, символ + - переменной plus, а правая часть – переменной rhs. После этого переменные lhs и rhs передаются в конструктор класса BinaryOp.

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

Листинг 7. Тестирование парсера (в этот раз по-настоящему)
package com.tedneward.calcdsl.test
{
  class CalcTest
  {
    import org.junit._, Assert._
    
    // ...
    
    @Test def parseAnExpr1 =
      assertEquals(
        Number(5),
        Calc.parse("5")
      )
    @Test def parseAnExpr2 =
      assertEquals(
        Number(5),
        Calc.parse("(5)")
      )
    @Test def parseAnExpr3 =
      assertEquals(
        BinaryOp("+", Number(5), Number(5)),
        Calc.parse("5 + 5")
      )
    @Test def parseAnExpr4 =
      assertEquals(
        BinaryOp("+", Number(5), Number(5)),
        Calc.parse("(5 + 5)")
      )
    @Test def parseAnExpr5 =
      assertEquals(
        BinaryOp("+", BinaryOp("+", Number(5), Number(5)), Number(5)),
        Calc.parse("(5 + 5) + 5")
      )
    @Test def parseAnExpr6 =
      assertEquals(
        BinaryOp("+", BinaryOp("+", Number(5), Number(5)), BinaryOp("+", Number(5),
                 Number(5))),
        Calc.parse("(5 + 5) + (5 + 5)")
      )
    
    // другие тесты не показаны в целях экономии места
  }
}

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

Собираем все части воедино

Итак, теперь наш парсер ведет себя именно так, как нам надо, а именно – создает AST. Все что нам остается – это связать парсер с интерпретатором AST и проверить, что все работает как надо. На самом деле, это уже практически рутинная работа, необходимо просто добавить код из листинга 8 в класс Calc.

Листинг 8. Окончательный вариант
package com.tedneward.calcdsl
{
  // ...

  object Calc
  {
    // ...
    
    def evaluate(text : String) : Double = evaluate(parse(text))
  }
}

Далее добавим простой тест, проверяющий что результатом вызова evaluate("1+1") будет 2.0 (листинг 9).

Листинг 9. И все это только для того, чтобы убедиться, что 1 + 1 = 2?
package com.tedneward.calcdsl.test
{
  class CalcTest
  {
    import org.junit._, Assert._
    
    // ...
    
    @Test def add1 =
      assertEquals(Calc.evaluae("1 + 1"), 2.0)
  }
}

Теперь просто запустите тест. Выглядит неплохо, не так ли?

Расширение языка

Тот же самый язык вполне мог быть реализован на Java без тех сложностей, через которые нам пришлось пройти (в частности, необязательно было строить AST, можно было просто рекурсивно вычислять каждое вложенное выражение), поэтому может показаться, что Scala – это очередной пример языка или программы, решающей надуманные проблемы. Однако основная мощь Scala проявляется при расширении данного DSL, т. е. добавлении в него новых синтаксических конструкций.

В частности, можно добавить новый оператор ^, который будет возводить число в степень. Например, 2 ^ 2 означает квадрат числа 2 (т. е. 4). Добавление этого оператора в наш язык делается за несколько простых шагов

Вначале необходимо решить, требуется ли расширение AST. В данном случае оператор возведения в степень представляет собой лишь разновидность бинарной операции, поэтому достаточно класса case-класса BinaryOp. Таким образом, AST можно оставить без изменений.

Далее необходимо внести изменения в функцию evaluate, чтобы она правильно интерпретировала экземпляр BinaryOp("^", x, y). Для этого достаточно добавить вложенную (т. е. невидимую извне) функцию, которая будет заниматься возведением чисел в степень. Наконец, следует добавить следующую строчку в оператор сопоставления с образцом (листинг 10).

Листинг 10. Расширенный вариант интерпретатора
package com.tedneward.calcdsl
{
  // ...

  object Calc
  {
    // ...
    
    def evaluate(e : Expr) : Double =
    {
      def exponentiate(base : Double, exponent : Double) : Double =
        if (exponent == 0) 
          1.0
        else
          base * exponentiate(base, exponent - 1)

      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))
        case BinaryOp("^", x1, x2) => exponentiate(evaluate(x1), evaluate(x2))
      }
    }
  }
}

Обратите внимание: для добавления оператора возведения в степень потребовалось всего шесть строк кода, причем большая часть класса Calc осталась нетронутой. Это и есть инкапсуляция.

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

Перед тем как добавить оператор в парсер, давайте дополнительно испытаем нашу реализацию, добавив несколько тестов. Они должны гарантировать, что возведение в степень работает корректно (листинг 11).

Листинг 11. Проверка возведения в квадрат
package com.tedneward.calcdsl.test
{
  class CalcTest
  {
    // ...
    
    @Test def evaluateSimpleExp =
    {
      val expr =
        BinaryOp("^", Number(4), Number(2))
      val results = Calc.evaluate(expr)
      // (4 ^ 2) => 16
      assertEquals(16.0, results)
    }
    @Test def evaluateComplexExp =
    {
      val expr =
        BinaryOp("^",
          BinaryOp("*", Number(2), Number(2)),
          BinaryOp("/", Number(4), Number(2)))
      val results = Calc.evaluate(expr)
      // ((2 * 2) ^ (4 / 2)) => (4 ^ 2) => 16
      assertEquals(16.0, results)
    }
  }
}

Данный тест проверяет правильность возведения в степень (за исключением ранее отмеченной ошибки). Таким образом, полдела сделано.

Последнее, что осталось сделать – это изменить грамматику, добавив операцию возведения в степень. Данная операция имеет тот же приоритет, что и умножение с делением, поэтому его логично поместить в комбинатор term, как показано в листинге 12.

Листинг 12. Вот теперь точно окончательный вариант!
package com.tedneward.calcdsl
{
  // ...

  object Calc
  {
    // ...
    
    object ExprParser extends JavaTokenParsers
    {
      def expr: Parser[Expr] =
        (term ~ "+" ~ term) ^^ { case lhs~plus~rhs => BinaryOp("+", lhs, rhs) } |
        (term ~ "-" ~ term) ^^ { case lhs~minus~rhs => BinaryOp("-", lhs, rhs) } |
        term 

      def term: Parser[Expr] =
        (factor ~ "*" ~ factor) ^^ { case lhs~times~rhs => BinaryOp("*", lhs, rhs) } |
        (factor ~ "/" ~ factor) ^^ { case lhs~div~rhs => BinaryOp("/", lhs, rhs) } |
        (factor ~ "^" ~ factor) ^^ { case lhs~exp~rhs => BinaryOp("^", lhs, rhs) } |
        factor

      def factor : Parser[Expr] =
        "(" ~> expr <~ ")" |
        floatingPointNumber ^^ {x => Number(x.toFloat) }
      
      def parse(text : String) = parseAll(expr, text)
    }
    
  // ...
  }
}

Разумеется, нам опять надо добавить несколько тестов (листинг 13).

Листинг 13. Еще одно возведение в степень
package com.tedneward.calcdsl.test
{
  class CalcTest
  {
    // ...
    
    @Test def parseAnExpr17 =
      assertEquals(
        BinaryOp("^", Number(2), Number(2)),
        Calc.parse("2 ^ 2")
      )
    @Test def parseAnExpr18 =
      assertEquals(
        BinaryOp("^", Number(2), Number(2)),
        Calc.parse("(2 ^ 2)")
      )
    @Test def parseAnExpr19 =
      assertEquals(
        BinaryOp("^", Number(2),
          BinaryOp("+", Number(1), Number(1))),
        Calc.parse("2 ^ (1 + 1)")
      )
    @Test def parseAnExpr20 =
      assertEquals(
        BinaryOp("^", Number(2), Number(2)),
        Calc.parse("2 ^ (2)")
      )
  }
}

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

Листинг 14. Проверка разбора и вычисления выражения возведения в квадрат
package com.tedneward.calcdsl.test
{
  class CalcTest
  {
    // ...
    
    @Test def square1 =
      assertEquals(Calc.evaluate("2 ^ 2"), 4.0)
  }
}

Все работает!

Заключение

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

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

  • можно перейти от типа Doubles к типамBigDecimal или BigInteger из пакета java.math. Это позволит осуществлять операции над большими числами с большей точностью;
  • можно добавить поддержку десятичных чисел (пока они не поддерживаются парсером);
  • можно добавить ряд новых операторов, в частности,"sin," "cos," "tan" и т. д.;
  • наконец, можно добавить поддержку выражений с переменными, например "x = y + 12", и передавать в функцию evaluate() объект типа Map, содержащий начальные значения переменных.

Самое главное, что вся реализация DSL полностью скрыта за фасадом Calc, который можно легко вызывать из Java точно так же, как из Scala. Поэтому даже в тех проектах, которые вы пока не можете полностью перевести на Scala, на нем можно писать отдельные компоненты – те, в которых преимущества объектно-функционального подхода будут особенно заметны. Эти компоненты по-прежнему будут доступны для использования в Java.

На этом мы завершаем нашу серию. В следующей серии мы вернемся к Scala и рассмотрим другие возможности языка, в частности, шаблоны, используемые комбинаторами. Scala может предложить гораздо больше, чем было описано в этой серии, однако теперь вы, по крайней мере, должны лучше представлять себе, как можно применять Scala для решения задач, с которыми было бы гораздо сложнее справиться на Java. До новых встреч!


Ресурсы для скачивания


Похожие темы


Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Технология Java
ArticleID=394738
ArticleTitle=Путеводитель по Scala для Java-разработчиков: Часть 3. Создание калькулятора
publish-date=06052009