Piszemy (trochę ?) mniej złożony kalkulator

O czym będzie ten wpis

• Piszemy trochę bardziej złożony kalkulator w C#.NET
• Piszemy trochę bardziej złożony kalkulator w C#.NET - #2
• Piszemy trochę bardziej złożony kalkulator w C#.NET - #3 - Refactoring

Linki te zawierają kolejno:

• stworzenie bazowej klasy wyrażeń
• obliczanie wyrażenia w postaci postfiksowej z wykorzystaniem stosu
• oraz w końcu zamiana wyrażenia infiksowego na postfiksowe przy wykorzystaniu algorytmu wymyślonego przez prof. Dijkstrę, czyli Shunting-yard algorithm

Pomysł całkiem niezły. Kalkulator "funkcjonalniejszy" od pierwowzoru, ale zawsze musi być jakieś "ale"... inaczej nie powstałby ten wpis. Gdyby przez złożoność rozumieć nie funkcjonalność, a złożoność projektową to jest tragedia. Nie liczyłem linii, ale na oko z 300 do tak prostego zadania. Dodatkowo ilość warunków i pętli mnie przeraża.

[item]Udzieliłem odpowiedź jednemu użytkownikowi forum, odnośnie jego postu[/item] I tu można dostrzec paradoks sam zaleciłem powyższy algorytm (podły ze mnie człowiek, wiem). Do tego pisanie tego w PHP to musi skończyć się apopleksją piszącego, bez dwóch zdań. Mówiąc poważnie, ten algorytm nie jest zły. Jego zaletą jest prostota zależności, o których musimy wiedzieć (o kolejce i stosie chyba każdy słyszał). Nie mniej dostajemy coś mało funkcjonalnego. Głównie dla tego, że algorytm ma pewne ograniczenia. Zastosować go można tylko i wyłącznie do podzbioru języków z gramatyką LR, gdzie dwa symbole nieterminalne nie pojawiają się po prawej stronie żadnej z reguł gramatyki. Oczywiście do prostego kalkulatora to wystarczy, ale warto zdawać sobie sprawę z ograniczeń.

Ja w tym wpisie chcę zaproponować alternatywne podejście do tworzenia kalkulatora, tylko zastanawiam się, czy nie będzie ono trudniejsze w zrozumieniu. Mimo wszystko spróbuję, gdyż uważam, że nie ma rzeczy trudnych, tylko źle wytłumaczone. W trakcie wpisu omówię bądź, co bądź, pobieżnie informacje na temat gramatyk bezkontekstowych oraz przejdziemy proces tworzenia najprostszego kalkulatora. Napiszemy go w Scali.

Dlaczego Scala?

Można powiedzieć, że jestem częściowym Java Refugee (z ang. uchodźca). Czemu częściowym? W biznesie jak to w biznesie JEE trzyma się całkiem dobrze, a jak coś działa to się tego nie zmienia. Jak widać komitet wydający kolejne JSR utworzył z tego hasła motyw przewodni, no i mamy, to co mamy.

A Scala? Scala jest przyjemna, jest tym, czym Java nigdy nie chciała zostać, jest stabilna i najważniejsze jest skalowalna. Nie zamierzam się teraz nad tym rozwodzić (może kiedyś w osobnym wpisie), dlaczego z języków dostępnych na JVM najlepiej wybrać Scalę, ale zapewne będzie to tylko opinia, i tak znajdzie się ktoś, kto powie że banany są lepsze od jabłek. Oczywiście na tym prościutkim przykładzie nic ze skalowalności nie zobaczymy, ale cukier syntaktyczny będzie się lał.

A więc do dzieła...

Zacznijmy od podstaw. Chciałbym mieć czas na omówienie wszystkiego dogłębnie, ale niestety go nie znajdę w tym momencie. Dużo może ułatwić poznanie na własną rękę jakiejś serii wykładów na temat automatów i gramatyk. Wprowadźmy szybko cztery pojęcia. Pierwsze z nich to Abstrakcyjne Drzewo Syntaktyczne (AST). Jest to struktura przechowująca budowę pewnego dokumentu w oparciu o zdefiniowaną gramatykę, pozwala stwierdzić jak należy interpretować dany dokument, czy nie ma w nim błędów, etc.. Gramatyka (my rozważamy tylko te bezkontekstowe) czyli formalny zbiór definicji, dzięki którym można tworzyć wyrażenia w danym języku. Terminal, czyli węzeł AST, który jest liściem (kończy rekursywne wywołanie budowy AST), oraz węzeł nie terminalny, czyli dopełnienie zbioru (wszystko poza liśćmi).

Tak więc zdefiniujmy naszą klasę bazową dla Terminali oraz obiekty pochodne (czyli również będące Terminalami), dziedziczące z niej, mające podstawową implementację z wykorzystaniem mechanizmu property.

[code=Scala] abstract class Terminal case class Number(value: Double) extends Terminal case class BinaryOp(operator: String, left: Terminal, right: Terminal) extends Terminal [/code]

Mamy zatem definicję dwóch terminali, są to kolejno liczby oraz operatory dwuargumentowe. Dla liczb przechowujemy double (warto zwrócić na to uwagę, ponieważ wyniki są tylko pewnym przybliżeniem, nie mniej ta kwestia nas nie obchodzi, nie o tym jest wpis).

Dalej zdefiniujmy klasę Kalkulatora, która będzie właściwie robić całą magię:

[code=Scala] class Calculator { ... } [/code]

Zacznij implementację powyższej klasy od funkcji, która dla otrzymanego terminalu obliczy go. Taki mechanizm z angielskiego nazywamy resolve:

[code=Scala] def resolve(terminal: Terminal): Double = { terminal match { case Number(x) => x case BinaryOp("^", x1, x2) => (math.pow(resolve(x1), resolve(x2))) case BinaryOp("+", x1, x2) => (resolve(x1) + resolve(x2)) case BinaryOp("-", x1, x2) => (resolve(x1) - resolve(x2)) case BinaryOp("*", x1, x2) => (resolve(x1) * resolve(x2)) case BinaryOp("/", x1, x2) => (resolve(x1) / resolve(x2)) } } [/code]

Jak widzimy, jest to dość proste. Funkcja otrzyma obiekt będący terminalem, a następnie tworząc prototyp dopasuje (match) odpowiedni prototyp do obiektu i wykona kod zdefiniowany w domknięciu.

Teraz przejdźmy do parsowania wyrażenia. Użyję tu małego cheatu. Jako, że Scala ma podstawowy parser (a właściwie parser połączony z domyślnym lekserem), to postaramy się go wykorzystać. Profesjonalnie byłoby użyć jakiejś uznanej biblioteki do tworzenia lekserów/parserów (np. dla C będą to odpowiednio Flex/Bison, dla Javy JFlex/JCup, etc.) dla danego języka. Jednak projekt jest na tyle prosty i "naklepany" w ciągu 7 minut, że nie ma to większego sensu.

Zdefiniujmy obiekt o nazwie ExpressionParser w następujący sposób:

[code=Scala] object ExpressionParser extends JavaTokenParsers with PackratParsers { ... } [/code]

Dzięki temu uzyskamy dostęp do leksera z klasy JavaTokenParsers, a przyjęcie cech PackratParser umożliwi nam definiowanie gramatyki LR.

Teraz przejdziemy do w sumie najciekawszej części, czyli definiowania context-free grammar, w celu utworzenia AST. Przejrzystość Scali pod tym względem jest niesamowita i łatwo przyswajalna:

[code=Scala] lazy val expression: PackratParser[Terminal] = (expression <~ "+") ~ expr1 ^^ { case lhs~rhs => BinaryOp("+", lhs, rhs) } | (expression <~ "-") ~ expr1 ^^ { case lhs~rhs => BinaryOp("-", lhs, rhs) } | expr1

lazy val expr1: PackratParser[Terminal] = (expr1 <~ "*") ~ expr2 ^^ { case lhs~rhs => BinaryOp("*", lhs, rhs) } | (expr1 <~ "/") ~ expr2 ^^ { case lhs~rhs => BinaryOp("/", lhs, rhs) } | expr2

lazy val expr2 : PackratParser[Terminal] = (expr3 <~ "^") ~ expr2 ^^ { case lhs~rhs => BinaryOp("^", lhs, rhs) } | expr3

lazy val expr3 : PackratParser[Terminal] = "(" ~> expression <~ ")" | floatingPointNumber ^^ { x => Number(x.toDouble) }

def parse(text : String) = parseAll(expression, text) [/code]

Teoretycznie, gdyby użyć porządnej biblioteki generowania parserów, to można by to jeszcze uprościć. Głównie za sprawą tego, że expr1, expr2 i expr3 są redundantne. Tak naprawdę użyłem ich do "poziomowania" ze względu na brak możliwości zdefiniowania priorytetu operatorów (co jest możliwe w np. Bisonie).

No więc, co tu się dzieje, dla tych co Scalę widzą pierwszy raz na oczy: Początek (tak dla zmyły) umieściłem na końcu. Obiekt klasy Kalkulator wywoła (dzięki oddelegowaniu metody) metodę parseAll z klasy parsera. Rozpocznie się parsowanie zmiennej text (w której znajdzie się wyrażenie arytmetyczne) przyjmując za korzeń tego drzewa definicję wyrażenia. Następnie rozwinięte zostaną węzły mające dodawanie i odejmowanie, potem mnożenie i dzielenie, kolejna będzie potęga, a na samym końcu to co znajduje się w nawiasie. No własnie a co tam się znajduje? Znowu wyrażenie, zatem nawias wymusi kolejność działań, ale wewnątrz nawiasu odnowa kolejność zostanie zachowana (aż do napotkania kolejnego nawiasu - prosta rekursja). Takie rozwijanie będzie miało miejsce aż do rozwinięcia wszystkiego do poziomu symboli terminalnych. Wtedy to, od dołu, zaczniemy obliczać wyrażenia. Najpierw najbardziej zagnieżdżony nawias, a wewnątrz każdego nawiasu kolejno potęga, mnożenie i dzielenie, dodawanie i odejmowanie (kolejność działań została zachowana).

Warto jeszcze zwrócić uwagę na jedną rzecz. Podczas definiowania gramatyki, expression i expr1 są rozwijane lewostronnie (rekursja po lhs). Natomiast dla expr2 jest po prawej. Pytanie dlaczego tak to umieściłem? Odpowiedź jest dość prosta: cztery podstawowe działania liczymy od lewej do prawej zatem musimy rozwijać je w takiej kolejności inaczej moglibyśmy otrzymać coś takiego:

  BinOp
 /  |  \
1   - BinOp
      /  |  \
      2  -  3

licząc więc od dołu zostanie wykonane 2 - 3 czyli -1, a potem 1-(-1) czyli 2. To byłoby skrajnie głupie w obliczu algebry, której używa większość ludzi. Tak samo sprawa wygląda z potęgowaniem, które jest łączne prawostronnie. Więcej w przykładach testowych w ostatnim kodzie.

Za obliczanie będą odpowiedzialne następujące metody klasy Kalkulator

[code=Scala] def parse(text: String) = ExpressionParser.parse(text).get def evaluate(text: String): Double = resolve(parse(text)) [/code]

Tak więc, parse oddelegowuje wykonanie do metody parse z klasy ExpressionParser czyli tak naprawdę do parseAll (o czym już mówiłem), natomiast evaluate wykorzystuje parse i resolve do podstawienia pod węzły wartości, które można obliczyć. I to właściwie już wszystko. Dołączyłem jeszcze obiekt testujący, ale to już wraz z całym kodem (56 linii):

[code=Scala] abstract class Terminal case class Number(value: Double) extends Terminal case class BinaryOp(operator: String, left: Terminal, right: Terminal) extends Terminal

class Calculator { def resolve(terminal: Terminal): Double = { terminal match { case Number(x) => x case BinaryOp("^", x1, x2) => (math.pow(resolve(x1), resolve(x2))) case BinaryOp("+", x1, x2) => (resolve(x1) + resolve(x2)) case BinaryOp("-", x1, x2) => (resolve(x1) - resolve(x2)) case BinaryOp("*", x1, x2) => (resolve(x1) * resolve(x2)) case BinaryOp("/", x1, x2) => (resolve(x1) / resolve(x2)) } } import scala.util.parsing.combinator._ object ExpressionParser extends JavaTokenParsers with PackratParsers { lazy val expression: PackratParser[Terminal] = (expression <~ "+") ~ expr1 ^^ { case lhs~rhs => BinaryOp("+", lhs, rhs) } | (expression <~ "-") ~ expr1 ^^ { case lhs~rhs => BinaryOp("-", lhs, rhs) } | expr1 lazy val expr1: PackratParser[Terminal] = (expr1 <~ "*") ~ expr2 ^^ { case lhs~rhs => BinaryOp("*", lhs, rhs) } | (expr1 <~ "/") ~ expr2 ^^ { case lhs~rhs => BinaryOp("/", lhs, rhs) } | expr2 lazy val expr2 : PackratParser[Terminal] = (expr3 <~ "^") ~ expr2 ^^ { case lhs~rhs => BinaryOp("^", lhs, rhs) } | expr3 lazy val expr3 : PackratParser[Terminal] = "(" ~> expression <~ ")" | floatingPointNumber ^^ { x => Number(x.toDouble) } def parse(text : String) = parseAll(expression, text) } def parse(text: String) = ExpressionParser.parse(text).get def evaluate(text: String): Double = resolve(parse(text)) }

object Main extends App { val calc = new Calculator println(calc.evaluate("10+10")) // prosty example println(calc.evaluate("2+2*2")) // haczyk z podstawówki mnożenie jest najpierw println(calc.evaluate("(2+2)*2")) // wymuśmy działanie println(calc.evaluate("2^3^4")) // raczej oczywisty wynik println(calc.evaluate("2^-3^4")) // też chyba spodziewany, potęga jest łączna prawostronnie println(calc.evaluate("(2^-3)^4")) // a tu wymuszenie 2^-3 == (1/2)^3 stąd ułamek println(calc.evaluate("-7+6*2/3+9^2-1")) // -7+6*2/3+81-1 <=> -7+12/3+81-1 <=> -7+4+81-1 <=> 77 // coś "skomplikowanego" println(calc.parse("-7+5*3/3+9^2-1")) // obejrzyjmy sobie drzewko (niestety bez wcięć) } [/code]

oraz wyniki:

20.0
6.0
8.0
2.4178516392292583E24
2.4178516392292583E24
2.44140625E-4
77.0
BinaryOp(-,BinaryOp(+,BinaryOp(+,Number(-7.0),BinaryOp(/,BinaryOp(*,Number(5.0),Number(3.0)),Number(3.0))),BinaryOp(^,Number(9.0),Number(2.0))),Number(1.0))

Kod został napisany tak, aby działał na ideonie, dzięki czemu można go testować, bez instalowania Scali.

O czym jeszcze chciałem powiedzieć

Ostatni przykład pokazuje "drzewo". Należy je czytać, tak jakby to były funkcje. Najbardziej zagnieżdżone wykonanie to korzeń, każdy kolejny zredukowany poziom zagnieżdżenia to dzieci, aż w końcu wszystkie terminale to liście.

Dodatkowo jeszcze raz przypominam, użyty został typ double, który nie przechowuje wartości dokładnie, tylko z pewnym przybliżeniem.

Mała dygresja (ale w temacie) o demagogii programistycznej

Od czasu do czasu, tu i tam spotykam się z mała wiedzą programistyczną. Dziś opowiem o:

Zapewne przy takim kodzie:

    int time = 1 * 60 * 60;

spotkaliście się z:

a co to się nie dzieje, gdy zrobisz taki hopsztos:

while (...) {
    int time = 1 * 60 * 60;
}

Wiesz co się dzieje? Aż by się chciało rzucić mięsem, no ... nic. Praktycznie każdy wysoko poziomowy kompilator działa właśnie w oparcie o budowę takiego drzewa AST, z tym, że poza arytmetyką są tam inne konstrukcje, if, while, for, etc. I jak widziałeś mój program zwinął to wyrażenie do jednej liczby. Taki zapis wpływa tylko i wyłącznie na czas budowy AST (więcej węzłów) czyli w czasie kompilacji. To samo dzieje się w drugim przypadku, z tym, że dodatkowo zmienne nieulegające modyfikacji kompilatory wynoszą poza pętle.

Aby uściślić temat, są języki (skryptowe/interpretowane : np. PHP), gdzie ma to znaczenie. Taki plik nie jest kompilowany, ale interpreter i tak musi zbudować dla niego AST, po prostu robi to za każdym razem. O ile w przypadku aplikacji desktopowych uruchamianych raz na godzinę, to bez znaczenia o tyle np. w technologiach webowych ma to duży wpływ (budowane co request).

Króciutkie podsumowanie

Zacząłem temat w sumie o kompilatorach, bo jakby nie patrzeć to co napisałem to prosty arithmetic resolver. Jednak nie jestem pewny czy będę go kontynuował (czas, czas, czas). Początkowo, czyli jakiś rok temu chciałem napisać serię dotyczącą automatów i gramatyk (głównie bezkontekstowych), ale znowu czas, czas, czas, więc zobaczymy jak to będzie. Zdaję sobie sprawę, że dla osoby zupełnie zielonej, może być to ciężko przetrawić, bez tego "wprowadzenia" z czym co się je. Ale chyba nie muszę powtarzać co mnie ogranicza.

Z takich ciekawostek warto zobaczyć np. formalny opis gramatyki Javy. Dostępny jest pod tym linkiem.

Jeśli macie jakieś pytania, to śmiało, postaram się odpowiedzieć, tylko możecie się spodziewać jakiegoś odnośnika do materiałów, jeśli w wytłumaczeniu będzie potrzebna teoria, odnośnie automatów skończonych, gramatyk, etc. W przeciwnym razie postaram się po prostu odpowiedzieć (jeśli nie zajmie to dużo czasu).