Scala i notacja polska

Notacja PolskaW to takie cóś co miało uprościć zapis formuł logicznych i algebraicznych. Generalnie bardzo wygodna rzecz, która pozwala na uniknięcie nawiasów i można dzięki niej zapomnieć o kolejności działań. Ma ona niestety tą wadę, że stosunkowo trudno „tłumaczy się” na język komputerów tak by było to wydajne. W tym celu wymyślono Odwrotną Notację PolskąW, która pozwala na operowanie na ciągu znaków w znacznie bardziej przyjazny sposób.

Scala ma takie ustrojstwo jak pattern machting. Jest to taka cholera, która siedzi sobie radośnie gdzieś pomiędzy drabinką ifów i programowaniem przez ifowanie, a wzorcem strategii. Mówiąc w uproszczeniu język sam buduje za nas odpowiednią strukturę instrukcji if lub bloków catch. To ostatnie wynika ze sposobu obsługi przez scalę wyjątków. Generalnie jest to bardzo fajna i przydatna rzecz jeżeli chcemy np. przetwarzać listę obiektów co do których wiemy, że mogą być różnego typu względnie w zależności od ich wartości należy wybrać inny sposób obróbki.

Wiadomo już o co chodzi. Będzie przykład na to jak połączyć notację polską i scalę.

Notacja Polska

Na początek zwykła notacja polska. Algorytm jest prosty i sprowadza się do prawidłowego odczytania intencji autoraW. Popatrzmy chwilę na abstrakcję wyrażenia zapisanego w notacji polskiej:

OPERATOR OPERAND OPERAND

Czytamy to mniej więcej tak „Za pomocą operatora wykonaj działanie na operandach”. Masło maślane? Niekoniecznie ponieważ jeżeli zaczyna liczyć się kolejność działań to taki zapis naturalnie dzieli nam zapis na części.

2+2*2 =?

Problem znika dzięki odpowiedniemu zapisowi

* 2 + 2 2 = 8
+ * 2 2  2 = 6

Pierwszy czytamy „pomnóż 2 przez sumę 2 i 2”, a drugi „dodaj iloczyn 2 i 2 do 2”. To mała uwaga dla chujmanistów – jeżeli macie problem z rachunkami warto zainteresować się NP i ONP. Szczególnie ta druga może być przydatna ponieważ wymyślono ją dla debilniejszych z matmy od was dla komputerów. Wracamy do scali.

Listing 1. Notacja polska w Scali

object Main {

  def main(args: Array[String]): Unit = {

    println(List("*", 2, "+", 2, 2) + "=" + np(List("*", 2, "+", 2, 2)));
    println(List("+", "*", 2, 2, 2) + "=" + np(List("+", "*", 2, 2, 2)));

    println(List("+", "+", 3, 4, "+", 1, 2) + "=" + np(List("+", "+", 3, 4, "+", 1, 2)))
    println(List("-", 7, "+", 1, 2) + "=" + np(List("-", 7, "+", 1, 2)))
    println(List("*", 3, "+", 1, 2) + "=" + np(List("*", 3, "+", 1, 2)))
    println(List("/", 6, "+", 1, 2) + "=" + np(List("/", 6, "+", 1, 2)))
  }

  def np(args: List[Any]): Double = args match {
    case Nil => 0;
    case "+" :: x :: rest => {
      doubleValue(x) match {
        case None => (np(List(x) ::: rest)) + np(rest)
        case Some(a) => (a + np(rest))
      }
    }
    case "-" :: x :: rest => {
      doubleValue(x) match {
        case None => (np(List(x) ::: rest)) - np(rest)
        case Some(a) => (a - np(rest))
      }
    }

    case "*" :: x :: rest => {
      doubleValue(x) match {
        case None => (np(List(x) ::: rest)) * np(rest)
        case Some(a) => (a * np(rest))
      }
    }

    case "/" :: x :: rest => {
      doubleValue(x) match {
        case None => (np(List(x) ::: rest)) / np(rest)
        case Some(a) => (a / np(rest))
      }
    }

    case x :: rest => {
      return doubleValue(x) match {
        case None => np(List(x))
        case Some(n) => n
      }
    }
  }

  def doubleValue(arg: Any): Option[Double] = arg match {
    case Nil => None;
    case a: Number => Option(a.doubleValue);
    case _ => None;
  }
}

Jak widać intensywnie wykorzystuję tu pattern maching. W metodzie doubleValue służy ona do określenia czy mamy do czynienia z wartością liczbową czy też z czymś innym (w domyśle z wyrażeniem). W zależności od wyniku zwracany jest Option, który następnie jest poddawany kolejnemu testowi od którego zależy czy jak będzie przeprowadzane dalsze przetwarzanie wyrażenia. Metoda np też testuje argument pod kątem tego z czym ma do czynienia czy jest to operator czy prosty operand, czyli liczba (tu też przypadek bazowy rekurencji). Całość można radośnie rozszerzać o kolejne operacje, ale też można pokusić się o napisanie dodatkowego case w metodzie doubleValue, który będzie testował zmienną typu String pod kątem jej zamianę na liczbę. Wtedy można będzie przekazywać do metody listę stringów – parametrów programu i już mamy kalkulator 🙂

ONP zajmę się przy innej okazji. Ponieważ jest trochę lepszym przykładem na możliwości scali w innym kontekście.

2 myśli na temat “Scala i notacja polska

  1. Hater gonna hate!

    1.
    List(x) ::: xs x :: xs

    2. Po co pierdyliard matchy?
    scala> val op = Map[Char, (Int, Int) => Int](‚+’ -> (_ + _))
    op: scala.collection.immutable.Map[Char,(Int, Int) => Int] = Map(+ -> )

    scala> op(‚+’)(1,2)
    res2: Int = 3

    3. Match jest fajny ale bez przesady:
    doubleValue(x) match {
    case None => (np(List(x) ::: rest)) / np(rest)
    case Some(a) => (a / np(rest))
    }

    to samo co:

    doubleValue(x).getOrElse(np(x :: rest)) / np(rest)

    Pozdrownienia ze #scala.pl @ irc.freenode.net 😉

  2. O widzisz. Człowiek uczy się przez całe życie. Nie mam tylko pewności co do 2 ponieważ w NP można napisać + + 2 2 2 i wtedy nie dopasuje char, Int, Int do pierwszego +.

Napisz odpowiedź

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax