Self Wright

Tag: language

A simple calculator in Scala

Here1 (credits to Ben Lynn2) is a simple calculator in Haskell.

I decided to try porting it over3 to Scala. The original example also makes this work in Javascript using Haste; I’ve left this out for now (though I might come back and get this to work under Scala.js later).

The underlying basis is the same, using the awesome fastparse library to stand-in for Parsec/Megaparsec from Haskell, and the code feels quite concise and readable to me4.

This is the entirety of the parsing code we need:

  def numParser[_: P] = P( ("-".? ~ CharIn("0-9").rep ~ ".".? ~ CharIn("0-9").rep).!.map(_.toDouble) )
  def parenParser[_: P]: P[Double] = P( "(" ~/ exprParser ~ ")"  )  // needs explicit type because it's recursive.
  def factorParser[_: P] = P( parenParser | numParser )
  def termParser[_: P] = P( factorParser ~ (CharIn("*/").! ~/ factorParser).rep ).map(eval)
  def exprParser[_: P] = P( termParser ~ (CharIn("+\\-").! ~/ termParser).rep ).map(eval)

… along with a tiny bit of evaluation:

  def eval(ast: (Double, Seq[(String, Double)])): Double = {
    val (base, ops) = ast
    ops.foldLeft(base) {
      case (n1, (op, n2)) =>
        op match {
        case "*" => n1 * n2
        case "/" => n1 / n2
        case "+" => n1 + n2
        case "-" => n1 - n2

That’s it.

That’s all you need to take in a String and convert it to a Double.

What Ben says about the evolution of parsing-as-it-used is true: it was completely normal to resort to lex/yacc and then flex/bison for these earlier, but Parser Combinators and PEGs take it to a whole other level, and once you’ve become comfortable with them, there’s no going back to the verbose old days.

Just to break down the parsing code a bit:

This parses a number: def numParser[_: P] = P( ("-".? ~ CharIn("0-9").rep ~ ".".? ~ CharIn("0-9").rep).!.map(_.toDouble) ). Or rather, it returns a function that can parse a number.

It’s possible to play5 with this within a repl; I use sbt console6 when something depends on a class/object within a project, but this is an independent enough chunk that you could use ammonite7 instead too.

agam-agam@ import fastparse._
import fastparse._
agam-agam@ import NoWhitespace._
import NoWhitespace._
agam-agam@ def numParser[_: P] = P( ("-".? ~ CharIn("0-9").rep ~ ".".? ~ CharIn("0-9").rep).!.map(_.toDouble) )
defined function numParser
agam-agam@ parse("45", numParser(_))
res263: Parsed[Double] = Success(45.0, 2)
agam-agam@ parse("4.5", numParser(_))
res264: Parsed[Double] = Success(4.5, 3)

Where it gets interesting is composing these parsing functions.

Given a function to parse a factor (a number, or sub-expression within parentheses), we can define a function to parse combinations of multiplying/dividing these as:

def termParser[_: P] = P( factorParser ~ (CharIn("*/").! ~/ factorParser).rep ).map(eval)

… which reads very “regex-like”, imo!

Anyway, I added a basic I/o driver around this, so it can be “run” as:

➜ sbt run
[info] Loading settings for project simplecalc-build from metals.sbt ...
[info] Loading project definition from /home/agam/code/simplecalc/project
[info] Loading settings for project simplecalc from build.sbt ...
[info] Set current project to hello-world (in build file:/home/agam/code/simplecalc/)
[info] Compiling 1 Scala source to /home/agam/code/simplecalc/target/scala-2.13/classes ...
[warn] there was one deprecation warning (since 2.11.0); re-run with -deprecation for details
[warn] one warning found
[info] running Main
Simple calculator
Enter an expression, or 'END' to quit: 5   6
Result: 11.0
Enter an expression, or 'END' to quit: 2 - 5.2 * 1.5
Result: -5.800000000000001
Enter an expression, or 'END' to quit: 1.8   2.3 / 4.5
Result: 2.311111111111111
Enter an expression, or 'END' to quit: 42   1 - 5
Result: 38.0
Enter an expression, or 'END' to quit: END
[success] Total time: 55 s, completed Aug 6, 2020, 11:36:47 PM

(Yeah, the weird decimal point behavior is just Double being a double; that is beyond the scope of this example 😐)

  1. ”Parser Combinators” ↩︎
  2. Indeed, Ben has a bunch of other awesome stuff like this, and I might just go Scala-ize more of them 🙂 ↩︎
  3. Repo (with this core code, as well as a Main driver and tests) is here ↩︎
  4. My subjective opinion is that Scala is a sweet spot between ↩︎
  5. I’ve taken a “shortcut” with my map(_.toDouble) bit there, so it doesn’t fail properly right now and you get java.lang.NumberFormatException: empty String, but normally you’d get a Parsed.Failure back ↩︎
  6. Console ↩︎
  7. Ammonite ↩︎

Programming is like writing

From a comment on Slashdot:

I swtiched jobs from being a computer programmer to being an ESL teacher in Japan. Japan is somewhat famous for churning out students who know a lot about English, but can’t order a drink at Mac Donald’s. We used to have a name for those kinds of people with regard to programming languages: language laywers. They can answer any question you put to them about a programming language, but couldn’t program to save their life. These people often make it past job interviews easily, but then turn out to be huge disappointments when they actually get down to work. I’ve read a lot about this problem, but the more I look at it, the more I realise that these disabled programmers are just like my students. They have a vocabulary of 5000 words, know every grammar rule in the book but just can’t speak.

My current theory is that programming is quite literally writing. The vast majority of programming is not conceptually difficult (contrary to what a lot of people would have you believe). We only make it difficult because we suck at writing. The vast majority of programmers aren’t fluent, and don’t even have a desire to be fluent. They don’t read other people’s code. They don’t recognise or use idioms. They don’t think in the programming language. Most code sucks because we have the fluency equivalent of 3 year olds trying to write a novel. And so our programs are needlessly complex.

Those programmers with a “spark” are programmers who have an innate talent for the language. Or they are people who have read and read and read code. Or both. We teach programming wrong. We teach it the way Japanese teachers have been teaching English. We teach about programming and expect that students will spontaneously learn to write from this collection of facts.

In language acquisition there is a hypothesis called the “Input Hypothesis”. It states that all language acquisition comes from “comprehensible input”. That is, if you hear or read language that you can understand based on what you already know and from context, you will acquire it. Explanation does not help you acquire language. I believe the same is true of programming. We should be immersing students in good code. We should be burying them in idiom after idiom after idiom, allowing them to acquire the ability to program without explanation.

By studying a number of examples, we have come to the conclusion that programs in less expressive languages exhibit repeated occurrences of programming patterns, and that this pattern-oriented style is detrimental to the programming process.

Felleisen, “On the expressive power of programming languages”

On the evolution of GUIs

From 1998 []

Today’s GUI’s are generally built out of hard-coded event handlers.

A language that could describe the display and the events and associate them with protocol elements such that it would all be data-driven (instead of code-driven) and which required a protocol between the server and the client such that the server only dealt with function calls returning values to the client and the client did all the event handling and dispatching and display, would cause a giant leap forward in GUI design and simplify the tasks involved tremendously.

But thanks to Microsoft, we now mostly have code-driven GUIs that are as portable as the average Egyptian pyramid and which ensure as much “full employment” as the same pyramids, and we now mostly have people who don’t even understand the differences and the layering of language, protocol, and display engine.

Making that happen in a language design should involve some subtle shifts in the way data is conceptualized. That isn’t a digression in a discussion of types, because the way we conceptualize data has deep, not to say insidious, effects on the nature of typing.

As for the types themselves, I suggest we abandon the whole notion of types in favor of a lightweight mathematical notion of sets — and avoid using the word “type” as it naturally drags us back toward the conceptual morass of type theory that we need to escape.

Powered by WordPress & Theme by Anders Norén