Piszemy własny interpreter w Scali – cz. 1: Wprowadzenie

Na kilku kolejnych kartach kajecika chciałbym pokazać w jaki sposób realizowałem mini projekt, który dostarczał mi relaksu po godzinach.
Projekt polegał na stworzeniu prostego interpretera w Scali, który na wejściu przyjmie wyrażenie reprezentujące operacje na zbiorach liczb całkowitych i zwróci wynikowy zbiór.
Notki będą miały charakter zbliżony do tutoriala, a kod interpretera zostanie w całości udostępniony na githubie pod adresem: https://github.com/mkubala/sets-notation-interpreter


Sam projekt można podzielić na 3 logiczne elementy:

  1. Parser budujący drzewo wyrażeń w oparciu o wejściowy ciąg znaków.
  2. Silnik wyrażeń odpowiedzialny za przetworzenie drzewa i wygenerowanie wyniku w postaci zbioru liczb calkowitych (Int). Silnik będzie obsługiwał tylko podstawowe operacje, ale możliwe będzie jego rozszerzanie o własne operatory.
  3. Przykładowy plug-in – rozszerzenie wprowadzające dodatkowy operator binarny.

schemat-cz1

W pierwszej części chciałbym przedstawić Ci składnię mojego interpretera oraz wprowadzić w temat drzew wyrażeń, na których oparłem swój silnik.

Zakładam, że znasz podstawy scali (jeśli nie to spokojnie – w sieci możesz znaleźć tutoriale (nawet interaktywne) i różnego rodzaju wprowadzenia. Poszukiwania warto zacząć TUTAJ), dlatego nie będę tutaj omawiał podstawowych elementów samego języka, za to pozwolę sobie słowem wstępu pokazać w jaki sposób możemy szybko przygotować podwaliny pod nasz projekt.

Do zarządzania cyklem budowy oraz zależnościami używam SBT (http://www.scala-sbt.org/) – możemy powiedzieć, że to taki Maven dla Scali. Moim ulubionym środowiskiem IDE jest eclipse, więc będę się wspierał pluginem Scala IDE (http://scala-ide.org/).
Projekt SBT, podobnie jak projety Maven’a znane z Javy można utworzyć na dwa sposoby: ręcznie tworząc niezbędne pliki (maven: pom.xml / sbt: build.sbt) i katalogi lub posługując się szablonem. Ja wybrałem drugą opcję i wygeneruję go z pomocą gitera (https://github.com/n8han/giter8) oraz szablonu scala-sbt:

marcinkubala:~/blog$ g8 typesafehub/scala-sbt

Scala Project Using sbt 

organization [org.example]: pl.mkubala.sets
name [Scala Project]: SetsNotationInterpreter
scala_version [2.9.2]: 2.10.0
version [0.1-SNAPSHOT]: 

Template applied in ./setsnotationinterpreter

Projekt nazwałem ‘SetsNotationInterpreter’ i będę używał Scali w wersji 2.10.0

Można dostrzec tutaj podobieństwo do procesu tworzenie projektu Mavena na podstawie artefaktów.

Sbt, giter8 oraz samą scalę możesz ściągnąć i zainstalować osobno lub sięgnąć po Typesafe Stack (http://typesafe.com/stack), który je zawiera w formie jednej paczki i który jest dostępny w repozytoriach większości dystrybucji GNU/Linuksa, a także poprzez Homebrew na Macu.

Dodałem plugin sbt-eclipse-plugin, pozwalający szybko wygenerować projekt eclipse, poprzez utworzenie pliku project/plugins.sbt o następującej zawartości:

addSbtPlugin("com.typesafe.sbteclipse" % "sbteclipse-plugin" % "2.1.1")

Dodatkowo dodałem do zależności framework ScalaTest, którego będę używał przy tworzeniu testów jednostkowych. Wyedytowałem plik project/SetsnotationinterpreterBuild.scala, dodajac pod linią scalaVersion := "2.10.0" (po przecinku!) linię libraryDependencies += "org.scalatest" % "scalatest_2.10" % "1.9.1" % "test"Ostatecznie plik ma postać:

import sbt._
import sbt.Keys._

object SetsnotationinterpreterBuild extends Build {

  lazy val setsnotationinterpreter = Project(
    id = "setsnotationinterpreter",
    base = file("."),
    settings = Project.defaultSettings ++ Seq(
      name := "SetsNotationInterpreter",
      organization := "pl.mkubala.sets",
      version := "0.1-SNAPSHOT",
      scalaVersion := "2.10.0",
      libraryDependencies += "org.scalatest" % "scalatest_2.10" % "1.9.1" % "test"
    )
  )
}

Kolejnym krokiem było wygenerowanie projektu eclipse:

marcinkubala:~/blog/setsnotationinterpreter$ sbt eclipse
[info] Loading project definition from /Users/marcinkubala/blog/setsnotationinterpreter/project
[info] Set current project to SetsNotationInterpreter (in build file:/Users/marcinkubala/blog/setsnotationinterpreter/)
[info] About to create Eclipse project files for your project(s).
[info] Updating {file:/Users/marcinkubala/blog/setsnotationinterpreter/}setsnotationinterpreter...
[info] Resolving org.scala-lang#scala-library;2.10.0 ...
[info] Done updating.
[info] Successfully created Eclipse project files for project(s):
[info] SetsNotationInterpreter

OK, przygotowaliśmy fundamenty, teraz pora przejść do właściwego projektu.
Założenia, na których będzie opierała się składnia mojego interpretera są następujące:

  • Definicja zbioru – zbiory będziemy wyrażać w następującej notacji:
    { 1, 2, 3, .., n }

    Dodatkowo przyjąłem założenie, że zbiór jednoelementowy możemy wyrazić po prostu jako liczbę (bez nawiasów klamrowych) dlatego:

    { n }

    będzie oznaczać dokładnie to samo co

    n
  • Operatory – do dyspozycji będziemy mieli operatory, które będą składać się z jednego lub więcej następujących znaków:
    ! " # $ % & ' * + , . / : ; < = > ? @ ^ _ ` | ~ - \ A-Z a-z

    Notacja najprostszego wyrażenia:

    zbiór_lub_wyrażenie operator zbiór_lub_wyrażenie

    Przykład (wyznaczenie części wspólnej):

    {1, 2, 3} ^ {2, 3, 4, 5, 6}
  • Grupowanie wyrażeń – możliwe będzie grupowanie wyrażeń z użyciem nawiasów. Przykład (operator “v” oznacza sumę zbiorów, “^” część wspólną):
    ({2,3} ^ {3}) v ({10, 100} ^ 100)

    Powyższe wyrażenie powinno nam zwrócić zbiór składający się z 2 elementów: 3 oraz 100

Jak już wcześniej pisałem całość można rozbić na takie składowe jak parser, silnik wyrażeń i moduły.
Wynikiem działania parsera będzie drzewo wyrażenia, struktura reprezentująca zbiory jako liście drzewa (elementy skrajne, nie posiadające żadnych dzieci (odnóg)) oraz operatory jako gałęzie (a ponieważ mamy do czynienia z operatorami o 2 argumentach mogą one posiadać tylko 2 elementy potomne: wyrażenie po lewej oraz prawej stronie).

Przykładowo dla wyrażenia (op* oznacza operator, S* zbiór)

S1 op1 S2

nasze drzewo wygląda następująco:

Z kolei drzewo dla wyrażenia

S1 op1 S2 op2 S3

Teraz zacznie się robić ciekawie, w kolejnym przykładzie zgrupujemy wyrażenia, wymuszając tym samym zmianę kolejności przetwarzania:

S1 op1 S2 op2 (S3 op3 S4)

Idąc dalej możemy dojść do takiego przykładu:

S1 op1 S2 op2 (S3 op3 (S4 op4 S5))


Co może być równoznaczne z:

{1, 3} ^ {3} v ({10} ^ ({10, 5} ^ {10}))

Jeśli moje przykłady nie są klarowne, to pod adresem http://informatyka.wroc.pl/node/391 znajdziesz całkiem udany opis drzewa wyrażenia w ramach cyklu “Własny język programowania”.

Nasze drzewo zbudowane będzie z 2 rodzajów obiektów, reprezentujących kolejno: zbiory oraz operatory.

package pl.mkubala.sets

sealed trait SetExpression
case class SetDef(elements: Set[Int]) extends SetExpression
case class SetBinOp(leftBranch: SetExpression, opSymbol: String, rightBranch: SetExpression) extends SetExpression

SetDef reprezentuje zbiór, natomiast SetBinOp reprezentuje operację i przechowuje symbol operatora (np. “^”, “v”, “-” itd.) oraz referencje do lewej i prawej gałęzi. Dodatkowo wprowadziłem cechę SetExpression, będącą rodzicem obu klas. Dzięki temu będę mógł zamiennie używać zbiorów lub podwyrażeń jako gałęzi SetBinOp.

I to byłoby na tyle w tej części. W kolejnej będzie bardziej praktycznie, gdyż na tapetę weźmiemy parser 🙂

Projekt dostępny jest na githubie pod adresem: https://github.com/mkubala/sets-notation-interpreter

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