Piszemy własny interpreter w Scali – cz. 3: Silnik wyrażeń oraz pierwszy plug-in

W tej notce pokażę w jaki sposób zaimplementowałem silnik wyrażeń interpretera, który przetwarza podane drzewo wyrażenia korzystając z operacji dostarczanych w postaci plug-inów.
Zadanie nie jest takie trudne gdy do dyspozycji mamy:

Interfejs oraz testy jednostkowe

Tak jak w przypadku parsera, na pierwszy ogień pójdzie opracowanie interfejsu oraz stworzenie kilku testów. Najpierw rzućmy okiem na interfejs:

package pl.mkubala.sets.evaluator

import pl.mkubala.sets.SetExpression

class SetNotationEvaluator {

  def eval(expressionTree: SetExpression): Set[Int] = Set()

}

Metoda eval to póki co wydmuszka – niezależnie od wejścia zawsze zwróci nam pusty zbiór.

Założenia zostały ujętn w następujących przypadkach testowych:

package pl.mkubala.sets.evaluator

import org.scalatest.FunSuite

import pl.mkubala.sets.SetBinOp
import pl.mkubala.sets.SetDef

class SetNotationEvaluatorTest extends FunSuite {

  private val evaluator = new SetNotationEvaluator with TestSetOperations

  trait TestSetOperations {
    // TODO
  }

  // some helper constants
  val setDef123 = SetDef(Set(1, 2, 3))
  val setDef234 = SetDef(Set(2, 3, 4))
  val setDef345 = SetDef(Set(3, 4, 5))

  test("should eval empty SetDef to empty set") {
    // given
    val input = SetDef(Set())
    val expectedOutput = Set()

    // when
    val result = evaluator.eval(input);

    // then
    assert(result === expectedOutput)
  }

  test("should throw exception if unput expression tree is null") {
    // given
    val input = null

    // when & then
    intercept[IllegalArgumentException] {
      evaluator.eval(input)
    }
  }

  test("should throw exception if expression contains unsupported binaryOp") {
    // given
    val input = SetBinOp(setDef123, "someUnsupportedOp", setDef234)

    // when & then
    intercept[IllegalArgumentException] {
      evaluator.eval(input)
    }
  }

  test("should eval non-empty SetDef to non-empty set") {
    // given
    val input = setDef123
    val expectedOutput = Set(1, 2, 3)

    // when
    val result = evaluator.eval(input);

    // then
    assert(result === expectedOutput)
  }

  test("should eval 'SetBinOp(setDef123, \"sum\", setDef345)' to 'Set(1, 2, 3, 4, 5)'") {
    // given
    val input = SetBinOp(setDef123, "sum", setDef345)
    val expectedOutput = Set(1, 2, 3, 4, 5)

    // when
    val result = evaluator.eval(input);

    // then
    assert(result === expectedOutput)
  }

  test("should eval 'SetBinOp(setDef123, \"intersect\", setDef345)' to 'Set(3)'") {
    // given
    val input = SetBinOp(setDef123, "intersect", setDef345)
    val expectedOutput = Set(3)

    // when
    val result = evaluator.eval(input);

    // then
    assert(result === expectedOutput)
  }

  test("should eval 'SetBinOp(setDef123, \"intersect\", SetBinOp(setDef345, \"sum\", setDef234))' to 'Set(2, 3)'") {
    // given
    val input = SetBinOp(setDef123, "intersect", SetBinOp(setDef345, "sum", setDef234))
    val expectedOutput = Set(2, 3)

    // when
    val result = evaluator.eval(input);

    // then
    assert(result === expectedOutput)
  }

}

Mogłeś zauważyć, że brakuje implementacji traitu TestSetOperations, czyli plug-inu dodającego operacje wykorzystywane na potrzeby testów: “intersect”, oraz “sum”.
Dodamy ją później, kiedy ustalimy szczegóły interfejsu dla wtyczek.

Jak widać w kodzie testu występuje sporo powtórzeń. Można uzwięźlić cały zapis, wprowadzając własny wewnętrzny mini-DSL oparty o niejawne konwersje, ale to temat na zupełnie inną notkę (przykład wykorzystujący niejawne konwersje (implicit conversions, http://scala.net.pl/10-powodow-by-polubic-scale-implicit-conversions/): https://github.com/mkubala/sets-notation-interpreter/blob/master/src/test/scala/pl/mkubala/sets/evaluator/BasicSetOperationsTest.scala).

Implementacja

Nasza metoda eval przyjmuje drzewo, a w zasadzie element drzewa, będący jego korzeniem. Rozróżniamy następujące elementy:

  1. definicja zbioru (SetDef), czyli liść drzewa
  2. operacja wykonywaną na 2 zbiorach (SetBinOp)

Każda inna wartość będzie traktowana jako błąd:

def eval(expressionTree: SetExpression): Set[Int] = expressionTree match {
  case SetDef(elements) => // przypadek 1
  case SetBinOp(left, operator, right) => // przypadek 2
  case _ => throw new IllegalArgumentException("Unvalid expression: " + expressionTree)
}

W pierwszym przypadku wystarczy zwrócić zbiór liczb zdefiniowanych w elemencie SetDef:

  case SetDef(elements) => elements

W drugim przypadku będziemy musieli zaaplikować pewną operację do 2 podanych zbiorów.

Czym własciwie jest operacja?

Operacja w naszym wypadku to zwykła funkcja przyjmująca 2 zbiory liczb całkowitych i zwracająca zbiór wynikowy:

Function2[Set[Int], Set[Int], Set[Int]] // = Function2[typ_arg1, typ_arg2, typ_zwracany]

albo w zapisie skróconym:

(left: Set[Int], right: Set[Int]) => Set[Int]

Możemy wprowadzić pewien poziom abstrakcji i stworzyć nazwany alias dla tego typu:

type SetOperation = (Set[Int], Set[Int]) => Set[Int]

Wprowadzimy sobie dodatkową metodę getOperationForSymbol, która będzie przyjmować symbol operatora i zwracać obiekt typu SetOperation (czyli funkcję dwuargumentową):

private def getOperationForSymbol(opSymbol: String): SetOperation = // TODO

Wróćmy do eval – przypadek w którym element drzewa będzie typu SetBinOp możemy teraz obsłużyć z użyciem nowo dodanej metody:

case SetBinOp(left, operator, right) => getOperationForSymbol(operator)(left, right)

Hmm… coś tu nadal nie gra. SetOperation oczekuje argumentów typu Set[Int], a nie SetExpression, a to oznacza, ze przed wykonaniem (zaaplikowaniem) operacji musimy przetworzyć oba argumenty operacji (left oraz right) na konkretne zbiory (Set[Int]). W tym celu posłużę się rekurencją:

case SetBinOp(left, operator, right) => getOperationForSymbol(operator)(eval(left), eval(right))

Kompletna metoda eval wygląda następująco:

def eval(expressionTree: SetExpression): Set[Int] = expressionTree match {
  case SetDef(elements) => elements
  case SetBinOp(left, operator, right) => getOperationForSymbol(operator)(eval(left), eval(right))
  case _ => throw new IllegalArgumentException("Unvalid expression: " + expressionTree)
}

Analizując kod metody można zauważyć, że przetwarzanie zawsze zaczyna się od ‘wyłuskania’ wartości z liści, następnie z najbardziej zagnieżdżonych gałęzi, na korzeniu kończąc.

Pozostało nam już tylko rozwiązanie problemu wyszukiwania operacji po jej symbolu.
Naturalnym posunięciem będzie użycie mapy, w której kluczem będzie łańcuch znaków reprezentujący symbol operacji, a wartością operacja.
Ponieważ w Scali kolekcje występują w 2 odmianach: mutowalnej (mutalbe) oraz niemutowalnej (immutable), a nam zależy na możliwości rozszerzania mapy o nowe pary klucz-wartość, mamy 2 drogi:

  1. Użyć niemutowalnej mapy i zdefiniować pole jako var (zmienną)
  2. Skorzystać z mutowalnej mapy i zdefiniować pole jako val (wartość, stała)

W pierwszym przypadku dodanie nowej wartości wiąże się z koniecznością stworzenia nowej mapy zawierającej elementy istniejącej oraz dodatkową parę klucz-wartość, a następnie przypisanie jej do zmiennej.

var map = Map()
map = map + (key -> value)

Plusem takiego rozwiązania jest możliwość bezpiecznego udostępniania takiej mapy na zewnątrz obiektu bez obawy przed ‘cichą’ modyfikacją jej zawartości na zewnątrz klasy (co stanowiło by złamanie zasady enkapsulacji).

W drugim przypadku modyfikacja mapy odbywa się poprzez aktualizację jej zawartości (mutowanie). Unikamy konieczności tworzenia nowej instancji i podmiany referencji. Niestety takie podejście powoduje, że tracimy możliwość beztroskiego udostępniania struktury na zewnątrz (bez jej wcześniejszego kopiowania lub opakowywania w jakiegoś rodzaju niemutowalny widok).

Ponieważ nie planuję udostępniać mapy poza samą klasą, postawiłem na drugie rozwiązanie (mutowalna kolekcja, stała referencja):

protected val operations = scala.collection.mutable.Map[String, SetOperation]()

Możemy teraz zaimplementować metodę getOperationForSymbol według następującego schematu:
Jeśli mapa zawiera wartość dla podanego klucza – zwracamy ją, w przeciwnym wypadku rzucamy wyjątkiem informującym o wystąpieniu nieobsługiwanego operatora:

protected def getOperationForSymbol(opSymbol: String): SetOperation = operations get opSymbol match {
  case Some(operation) => operation
  case None => throw new IllegalArgumentException("Unsupported operation: '" + opSymbol + "'")
}

Kompletny kod naszego silnika wygląda następująco:

class SetNotationEvaluator {

  type SetOperation = (Set[Int], Set[Int]) => Set[Int]

  protected val operations = scala.collection.mutable.Map[String, SetOperation]()

  protected def getOperationForSymbol(opSymbol: String): SetOperation = operations get opSymbol match {
    case Some(operation) => operation
    case None => throw new IllegalArgumentException("Unsupported operation: '" + opSymbol + "'")
  }

  def eval(expressionTree: SetExpression): Set[Int] = expressionTree match {
    case SetDef(elements) => elements
    case SetBinOp(left, operator, right) => getOperationForSymbol(operator)(eval(left), eval(right))
    case _ => throw new IllegalArgumentException("Unvalid expression: " + expressionTree)
  }

}

Tak, te niecałe 20 linijek to cały silnik.
Nie bez powodu Scalę chwali się za zwięzłość 🙂

Pierwszy plug-in – testowe operacje

Możemy teraz wrócić do naszego testu i traitu TestSetOperations:

trait TestSetOperations {
  this: SetNotationEvaluator =>

  val unionOperation = (s1: Set[Int], s2: Set[Int]) => s1 union s2
  operations += ("union" -> unionOperation)

  val intersectOperation = (s1: Set[Int], s2: Set[Int]) => s1 intersect s2
  operations += ("intersect" -> intersectOperation)

}

Cała magia odbywa się dzięki jawnemu typowaniu referencji this w 2 linijce.
Wyrażenie

this: SetNotationEvaluator =>

oznacza, że oczekujemy aby referencja this odnosiła się do typu SetNotationEvaluator.
Określamy w ten sposób typ, do którego będziemy mogli domieszać naszą cechą. Dzięki temu (zgodnie z zasadą Liskov) możliwy będzie dostęp do składowych docelowego typu w taki sposób, jakby były one zdefiniowane w samym traicie – tutaj do mapy ‘operations’ znajdującej się w klasie SetNotationEvaluator (linijki 4-5 oraz 7-8).

Weryfikacja

Teraz możemy uruchomić testy jednostkowe aby upewnić się czy niczego nie schrzaniliśmy po drodze 😉

Sukces! Silnik oraz parser działają tak jak się tego spodziewaliśmy!

Ale czy jest coś co moglibyśmy usprawnić?

Rzućmy okiem na sposób w jaki zrealizowaliśmy obsługę wtyczek z operacjami.
W obecnej postaci trait uzyskuje pełny, bezpośredni dostęp do wewnętrznej mapy przechowującej operacje. To oznacza, że możliwe jest usuwanie oraz nadpisywanie operacji pochodzących z innych pluginów (kolizje symboli).
Zdecydowanie lepiej będzie, jeśli w przypadku kolizji rzucimy wyjątek, niż zezwolimy na cichą zmianę implementacji operacji.

Opiszmy pożądane zachowanie w postaci testu jednostkowego:

test("should check for operation's symbols collision") {
  // given
  trait TestCollisionSetOperations {
    this: SetNotationEvaluator =>

    val anotherUnionImpl: SetOperation = (s1, s2) => s1 -- s2
    operations += ("union" -> anotherUnionImpl)
  }

  intercept[IllegalStateException] {
    new SetNotationEvaluator with TestSetOperations with TestCollisionSetOperations
  }
}

Teraz zrefaktorujemy SetNotationEvaluator: ustawimy mapie operacji modyfikator dostępu na prywatny przez co pozwolimy na dodawanie operacji wyłącznie za pośrednictwem dedykowanej metody addOperation, która będzie wykrywała i reagowała na kolizje:

private val operations = scala.collection.mutable.Map[String, SetOperation]()

protected def addOperation(symbol: String, operation: SetOperation) =
  if (operations contains symbol)
    throw new IllegalStateException("Detected collision fo op symbol: '" + symbol + "'")
  else
    operations += (symbol -> operation)

Przy okazji także uzwięźlimy metodę getOperationForSymbol:

protected def getOperationForSymbol(opSymbol: String): SetOperation =
    operations getOrElse (opSymbol, throw new IllegalArgumentException("Unsupported operation: '" + opSymbol + "'"))

Zrefaktorowana klasa wygląda teraz tak:

class SetNotationEvaluator {

  type SetOperation = (Set[Int], Set[Int]) => Set[Int]

  private val operations = scala.collection.mutable.Map[String, SetOperation]()

  def addOperation(symbol: String, operation: SetOperation) =
    if (operations contains symbol)
      throw new IllegalStateException("Detected collision fo op symbol: '" + symbol + "'")
    else
      operations += (symbol -> operation)

  protected def getOperationForSymbol(opSymbol: String): SetOperation =
    operations getOrElse (opSymbol, throw new IllegalArgumentException("Unsupported operation: '" + opSymbol + "'"))

  def eval(expressionTree: SetExpression): Set[Int] = expressionTree match {
    case SetDef(elements) => elements
    case SetBinOp(left, operator, right) => getOperationForSymbol(operator)(eval(left), eval(right))
    case _ => throw new IllegalArgumentException("Unvalid expression: " + expressionTree)
  }

}

Konieczne będzie także zrefaktorowanie traitów z testowymi operacjami aby korzystały z własnie wprowadzonej metody:

trait TestSetOperations {
  this: SetNotationEvaluator =>

  addOperation("union", (s1, s2) => s1 union s2)
  addOperation("intersect", (s1, s2) => s1 intersect s2)
}
test("should check for operation's symbols collision") {
  // given
  trait TestCollisionSetOperations {
    this: SetNotationEvaluator =>

    addOperation("union", (s1, s2) => s1 -- s2)
  }

  intercept[IllegalStateException] {
    new SetNotationEvaluator with TestSetOperations with TestCollisionSetOperations
  }
}

Pomyślne wyniki testów potwierdzają poprawność wprowadzonych zmian.

Dodajemy plug-in z podstawowymi operacjami

Brakuje nam jeszcze zestawu podstawowych operacji:

package pl.mkubala.sets.evaluator

trait BasicSetOperations {
  this: SetNotationEvaluator =>

  val intersect: SetOperation = (s1, s2) => s1 intersect s2
  val union: SetOperation = (s1, s2) => s1 union s2
  val difference: SetOperation = (s1, s2) => s1 -- s2
  val symmetricDifference: SetOperation = (s1, s2) => union(difference(s1, s2), difference(s2, s1))

  addOperation("^", intersect)
  addOperation("v", union)
  addOperation("""\""", difference)
  addOperation("-", symmetricDifference)

}

I gotowe!

Wisienka na torcie – interaktywne środowisko REPL

Interfejsem użytkownika dla naszego interpretera będzie środowisko REPL, czyli Read-Eval-Print-Loop.
Na ekranie pojawiać się będzie tzw. znak zachęty, za którym wpisywać będziemy wyrażenie do zinterpretowania.
Po jego zatwierdzeniu klawiszem Enter wyświetlony zostanie wynik oraz (ponownie) znak zachęty, po którym będzie można wprowadzić kolejne wyrażenia do przetworzenia.
Aby zakończyć pracę z interpreterem będzie trzeba wpisać “bye”, “exit” lub “quit”.

Kompletny kod mini-shella wygląda następująco:

package pl.mkubala.sets

import scala.annotation.tailrec
import scala.tools.jline.console.ConsoleReader

import pl.mkubala.sets.evaluator.BasicSetOperations
import pl.mkubala.sets.evaluator.SetNotationEvaluator
import pl.mkubala.sets.parser.SetNotationParser

object SimpleRepl extends App {

  val evaluator = new SetNotationEvaluator with BasicSetOperations
  val reader = new ConsoleReader()
  reader.setPrompt("> ")

  @tailrec
  def readInput() {
   reader.readLine match {
      case "quit" | "exit" | "bye" => reader.println("bye!")
      case expr => {
        try {
          reader.println("= " + evaluator.eval(SetNotationParser.parse(expr)))
        } catch {
          case ex: Exception => reader.println("Error: " + ex.getMessage)
        }
        readInput
      }
    }
  }

  println("=== Sets Notation Interpreter - interactive shell ===")
  println("Usage: Type expression which you want to parse and press Enter to see results")
  println("If you want to exit, use one of the following expressions:\n 'bye', 'quit' or 'exit'")
  println("Have fun!")
  readInput
}

Dzięki użyciu adnotacji @tailrec kompilator będzie sprawdzał czy metoda readInput może być poddawana optymalizacjom pozwalającym na emulację rekurencji ogonowej.
Zwięzły i przystępny opis czym jest rekurencja ogonowa (a także trampoliny) można znaleźć pod adresem http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html

A tak wygląda nasze środowisko w akcji:repl

Podsumowanie

W tym momencie podstawowa wersja interpretera jest już gotowa do użycia. Jest cała masa usprawnień jakie można by jeszcze wprowadzać, natomiast już w tej chwili stosunek ilości kodu do możliwości jest imponujący.
Całość to zaledwie 124 linie kodu (nie licząc testów jednostkowych, za to wliczając puste linie służące formatowaniu):

marcin@maku-pc:~/scala/sets-notation-interpreter$ find src/main/scala/ -name *.scala -exec wc -l {} +
   5 src/main/scala/pl/mkubala/sets/SetExpression.scala
  28 src/main/scala/pl/mkubala/sets/evaluator/SetNotationEvaluator.scala
  17 src/main/scala/pl/mkubala/sets/evaluator/BasicSetOperations.scala
  36 src/main/scala/pl/mkubala/sets/SimpleRepl.scala
  38 src/main/scala/pl/mkubala/sets/parser/SetNotationParser.scala
 124 razem
marcin@maku-pc:~/scala/sets-notation-interpreter$ 

Robi wrażenie? 😉

Zachęcam do forkowania i przerabiania projektu na githubie (https://github.com/mkubala/sets-notation-interpreter) oraz dzielenia się wnioskami/uwagami/sugestiami.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s