Making a programming language: Part 8 - going faster

Table of contents, Whole project on github

First of all, I wrote some tests for scrat. That was a bit challenging to get started. How do you test a language? I decided to write a bunch of programs that exercise and combine different language features. And then stare into code until I was absolutely sure they are correct. That's the problem with implementing a new language, nobody can tell you if your code is correct but your software, but you don't even know if software is correct.
So I wrote some test programs and parsed and evaluated them in my mind to produce final result. And then I wrote a class using ScalaTest that generates tests by iterating over the array of these tuples. Quite cool, oh and I also included some descriptions into the tuples. So I get nice output. I pondered this idea quite some time ago but finally implemented it a bit after functions and objects.

So now I can do crazy refactorings while still maintaining the language - I trust my tests! But first of all, some benchmarks. I decided to measure execution time of parsing and evaluation on the linked-list consturctor. To my surprise, parsing was quite slow. It started on about 800ms and dropped down to     200ms after a few executions(first time object creation and JIT I suppose). 200ms for 67 lines of code? That would mean about 3 seconds on a 1000 line file IF complexity is linear(which I later leard it isn't!). And that's 3 seconds on fifth run or so, first run(which is the only one when doing real stuff) would be 10 seconds +, unacceptable. (evaluation takes a few ms)

Research

At first I just gave it some thought. Well it's a recursive descent parser, and from what I remember it back traces on failure. So efficiency has a lot to do with grammar structure. And it won't be linear because you have to do (usually) more back tracing when dealing with longer input.

Internets here I come. 

My thoughts were confirmed. I found some guys on forums complaining over speed and then Mr. Odersky himself commented something like this(from memory):

Well the parsers in scala standard library are more like an example how to do recusive descent, functional style. They are perfectly usable for parsing command lines but not for long files. You should use a parser generator for that.  

I was bummed. The reason I didn't use a parser generator was this close integration that parser as a library could provide me. By the way implementation of Parsers is remarkably short, ~800 lines but most of them are comments. But it has quite some problems. A lot of object creation - every time a parsing function is invoked many object are created. Each parser is an object and each combinator is an object too. This in itself is not a big deal, but no memoization is performed, so it becomes a big deal. Now many objects are created on each try, so when backtracing you have to GC all these object and then recreate them. It's clean but it's no wonder it's slow.
Some time passed by and I accidentally found out about Packrat Parsing. This paper provides details but the gist of it is to use lazy evaluation and memoization to reduce object creation and speed things up.

Conversion and results

Conversion is dead easy. It's fully described in scala api documentation. Basically you mix in PackratParsers and change def : Parser[] = ... to lazy val : PackratParser[] = ... and that's it. Mixed in trait provides the necessary implicit conversions, lazy makes sure the creation is only done once and new implementation of parseAll does some clever parsing. Oh and you needn't convert all parsers, the paper says the optimal perfomance is achieved with the right mix of standard recursive descent parsers and packrat(packrat does include some overhead on specific grammars and inputs). But I just converted all and run the benchmark again. And behold...11ms. On the best run. More like 15 on average. But that's still more than a whole order of magnitude faster. And it should scale better. 

next: don't know yet. I caught up with my implementation(finally!). I thinking about making functions stronger by relaxing the rules of invocation and doing some syntax sugar for lambdas. That and java interop. Or possibly compiling to bytecode. 

Related articles

• Parsers! How do they work?
• Beautiful JSON parsing in Scala
• The Benefits of Learning Another Language!
• Why I don't like game rendering performance benchmarks
• No Silver Bullets?
• Dynamic languages are static languages

Making a programming language: Part 7a - objects

Table of contents, Whole project on github

My goal in this post is for this to compile

func create(n){this}

and a call to it to return a reference to an object that contains "n".

Functions are a bit different from the rest of the language. Not by implementation or usage but by thought process behind designing them. I actually thought about objects and functions before implementing any of them. Considering my implementation of scopes(which I like) and shadowing I got this great idea that functions, scopes and objects are just many faces of the same thing. Or "could be" many faces of the same thing. Something a bit more powerful than a function being the "thing".

Let's see how that works. A function in this language needs a new local scope for every execution(not all functions, but this is a simplification because I don't care about performance, see previous post for details). New scope. New something. New. Bells should be ringing right now. I'm creating objects. I could just as well pass the reference to that object. I even have the reference. It's current scope - "this" in scala code. So I just need a language construct to access that. How about "this".

//in SScope body
map.put("this", this)

Not even a language construct, just a magic variable. You can even shadow it.
Anticlimactic? I hope so. The whole point of object is that it's just another view on function.

I could end the post here but I want to show why this is awesome(and therefore why I'm proud of it)

Privates

You don't even need access modifiers, you can use shadowing and nesting

func private(n) {
    that = this
    func (){ 
        func get() { that.n }
        func set(v) { that.n = v }
        this
    }()
}

This is a constructor that returns an object with functions get and set(but no n!). Outer object is available through its alias via nesting. And returned value is the last expression - an immediately invoked lambda(cumbersome syntax..gotta do something about that).
However, this is not bullet-proof

o = private(1)
o.that = func(){
           n=3
           this
         }
o.get()

Returns 3. Though knowledge of implementation is needed to execute such attack.

update:  I kinda sorta forgot to include how I made that dot-access thingy-o.get() to work. Continuation below

next: using objects

Related articles

• Making a programming language: Part 6 - functions
• What is an object?
• The hidden cost of C++
• Understanding The "this" Reference in Javascript

I don't like banks

Image via CrunchBase

This kinda doesn't belong on this blog but I need a way to vent.

I wanted to buy a certain laptop. But no Slovenian company is selling that specific model. Or anything like it. Guenstiger to the rescue - luckily I had German classes in high school and I remembered enough to get by.

So I find this company(computeruniverse) who has it by good price, would ship it to me and even offers a (mostly translated) english page. Awesome. Not to the painful part - payment. I usually do business online through PayPal and on rare occasions directly with my credit card. But no can do. Limit exceeded. I quickly fire up my online banking portal but I can't order a higher limit because I don't have a premium account(I refuse to pay my bank for something that's mandatory today).

The bank

So I make a trip to the bank. Luckily it's just 15 min away using public transportation. First time being there(I moved to Ljubljana for college less than a year ago) I'm kinda impressed. It looks modern and stylish. And best of all, a good-looking well-dressed young lady sits down next to me to service me. I think "This is what a bank should look like". She fills out the application for me and is really nice over all. Props to you lady, sadly I forgot your name.
But here comes the first strike: she told me my limit will be raised starting next week - in 4 days. Reason: I opened my account at another branch. I'm like "wtf? it's the same bank?" but okay...I can hold another four days.
Let me make this clear. I explicitly told her I want this for one-time online payment.

Four days later

I try paying with PayPal. Failure. Oh heck...let's try credit card. Limit exceeded. They didn't raise my limit for single transaction.  Strike two.

I'm tired of credit cards and waiting games. Luckily computeruniverse accepts advance payment by wire transfer. I do a bit of research and choose to trust them. Another trip to the bank. Grrr.

I get there, a bit angry and ask the teller to do the transaction and give her the details on my smartphone.   She gives me a patronizing look and a form to fill out. Now listen to this. I needed to copy the details from my phone to the form - same data in many places(banks had high replication and eventual consistency before NoSQL :P). And she then typed the data into the computer. Putting my form into the drawer. And PRINTS out the same data on another form and asks me to sign it. Now I'm puzzled. WHY IN THE WORLD I HAD TO COPY THE DATA FROM THE PHONE TO THE FORM IF YOU COULD JUST TYPE AND LOOK AT MY PHONE!?!??!?! 

Strike three. 

Aftermath

I paid for my laptop successfully. But I also made an account at another bank. They gave me electronic banking for free and I'm in process of transferring my income to that account. 

disclaimer: the bank at fault is NKBM. And for the record, my father has their online banking and it's quite bad.  

Related articles

• Fake bank websites growing in number and sophistication
• Online Bank Accounts Make Accessing Your Money Easy

Making a programming language: Part 6 - functions

Illustration of Function (mathematics). (Photo credit: Wikipedia)

Table of contents, Whole project on github

Long overdue, I'm finally writing about the most interesting part - user defined functions. Objects should be in the next post as they are a natural extension of what I'm about to do. And because I'm to lazy to write a post that long.

What's a function?

A function is something that takes parameters and returns a result. And I'm opting for side-effects as this is simpler to get something working that doing the whole referential transparency and IO monad(Haskell). Although it would be interesting to have sort of dynamically typed Haskell thingy...maybe in the future. 

So - side-effect-ful functions mean function body is a block of expressions, not just an expression, if I'm to do useful side-effects. This also means I want lexical scope. 

Body scope

Let's think about that. A function body needs a scope. It's parent scope is kinda obvious - it's the scope in which the function was defined. I want closures! It's local scope gets kinda tricky. I implemented read-only cascading and shadowing on write. If expressions can also have side-effects. So in different executions a parent variable may be shadowed or not. This means I cannot reuse the body scope, as the shadows need to be cleaned out(I'm considering an implementation that reuses it currently, but that's another story). As I'm not after performance I can simply create a new scope for each invocation of the function. 

Parameters can be implemented as regular variables pre-put into the local scope before executing the function body. 

Parsing

That was the hardest part. I had quite some problems in my grammar as I tried to introduce blocks. Mostly ambiguity and infinite recursion. I'll just post the interesting bits here - see the full commit if you're interested in details.

The function definition boils down to:

private def exprList: Parser[List[Expression]] = repsep(expr, "\\n+".
private def block: Parser[List[Expression]] = 
  """\{\n*""".r ~> exprList <~ """\n*\}""".
private def functionDef: Parser[FunctionDef] =
  "func" ~> identifier ~ ("(" ~> repsep(identifier, ",") <~ ")") ~ block ^^ {
    case id ~ args ~ body => FunctionDef(id, args, body)
  }

Oh yes, and since I use newlines as separators now, they aren't whitespace and I have to handle them explicitly.

override protected val whiteSpace = """[ \t\x0B\f\r]""".r

And later on I added lambdas which have optional identifier - so the only shcange is opt(identifier) in the parser.

Evaluation

It's just another node in the AST - a case class.

case class FunctionDef(name: Identifier, args: List[Identifier], body: List[Expression]) extends Expression

Now I needed something to execute the definition and create a function value in the enclosing scope. (this is in Evaluator class)

def createFunFromAst(arglist: List[Identifier], 
  body: List[Expression], scope: SScope): FunctionVarArg =
    (args: Any) => args match {
      case lst: List[Any] => {
        if (lst.length != arglist.length) {
          throw new ScratInvalidTypeError(
           "expected " + arglist.length + " arguments, but got " + lst.length)
        } else {
          val closure = new SScope(Some(scope))
          (arglist zip lst) foreach {
            t => closure.put(t._1.id, t._2)
          }
          apply(body)(closure)
        }
      }
      case other => throw new ScratInvalidTypeError(
        "expected list of arguments but got" + other)
    }

So, what am I doing here? I'm taking a part of the function definition(all except name - which is optional in the definition and not needed here) and the parent scope and then returning "FunctionVarArg" which is the same as native functions in standard library. This new function relies heavily on scala's closures(this would not be possible in this way in java!).  First it checks if got a list of arguments(case clauses) or it throws an exception. Then it checks the arity. Scrat is dynamically typed, but not sooo dynamically typed. If everything matches up it creates a new scope("closure"), and inserts key-value pairs for arguments(zip+foreach). And then it evaluates it's body - apply(body)(closure). Mind you, this happens on every execution as createFunFromAst return a function value that, upon execution, does this.
Oh yes, there is also a case clause in Evaluator's apply that invokes createFunFromAst, again trivial.
Such functions are indistinguishable to native functions from scrat's point of view and are invoked by same syntax and by same code in Evaluator.

A sample

First thing I tried to implement(literaly) was fibonaci's sequence

func fib(n) { if n==0 then 1 else if n==1 then 1 else fib(n-1) + fib(n-2) }
println("20th fibbonacci number is", fib(20))

Excuse me for the ugly nested if's, but this was neccessary as I have not implemented < yet. But hey, it works.

Sneak peak

At this point I realised an awesome way to implement objects. With constructors like:

func create(n){this}

next objects and costructors

Related articles

• When are Dynamic and Lexical Scoping equivalent?
• The functor design pattern
• Is Haskell liberal or conservative?
• Thinking Functionally with Haskell
• Making a programming language: Part 1 - how to start
• Making a programming language: Part 3 - adding features

Power sets

It all started out when a friend of mine(check him out) told me a story about someone having an interview at Google. He was live coding and asked to implement a function that computes a power set of a given set. He totaly over-engineered it and after an hour of fiddling came up with 4-liner in python. Ok. Big deal. How hard can it be? I immediately started to brainstorm a solution of my own(and Matevž helped). Paraphrased train of thought below.

So what is a power set? Say a power set of set A. It's a set of all subsets of A. It's all possible combinations of including and excluding single elements. So it's like applying filters to the original set. Wait a sec, a set of size n has 2 to the n-th power subsets. It all matches up. N-bit number are said filters. So you count from 0 to 2^n-1 you enumerate exactly all the filters and therefore all the subsets. You just calculated the power set. This took about 30sec in real time.

Another minute to sketch the implementation.
You implement set as Lists. Let's say Java is the language of choice. An
y reasonable input would be shorter than 64 elements, at least on current machinery. So long can be used as counter. And now a nested for loop to iterate over elements and appending them if counter && (1 << n). Simple.

Won't post the code since I never wrote it.

The original blogpost

This happened in a lab at Faculty for Computer and Information science. On my way home I started thinkking....what is that 4-line implementation? It can't be my algorithm, that won't fit - it just isn't that elegant. Matevž also told me who was the original author and it was someone whose blog I was subscribed to(I still am, it's pretty awesome, check it out). So I searched for the original blogpost. And found it. It wasn't four lines. And it was(as Swizec admits) wrong.

def powerset(set):
      binaries = [bin(a) for a in range(2^len(set))]
      power = []
      for yeses in binaries:
        subset = []
 yeses = str(yeses)
 for i in range(len(yeses)):
                 if yeses[i] == “1”:
          subset.append(set[i])
 power.append(subset)
      return power

But more importantly, it's essentially my algorithm. (And it didn't took him an hour, read the post, it's interesting)

And then I realised. This is ugly. Quite ugly. It may be efficient and allow for doing iteration and evaluating it lazily, but oh boy it's ugly. Can't it be done in a simpler way?

Recursive solution

So by asking how I compute a power set I obtained the imperative algorithm above.

Balanced tree (Photo credit: Wikipedia)

 Time to change the question. What is a power set? 

It's a set of leaves of a balanced binary decision tree. Every inner node represents a decision to either take or leave out the element at respective index(I assume elements are indexed). That is root node responds to first element, it's children to second element, etc. Every leaf can be computed by following the decision path.  It's a recursive structure. So the tree can be decomposed to left and right subtree and recombined. An this is repeated until you get to leaves. So a power set of A is an union of the power set of "A minus the first element" and the same power set again but with every subset added the first element. Subtrees are represented by the two powersets and the recombination by adding head element to one set of sets and then doing the union. And to stop the recursion: power set of an empty set is a set containing just an empty set. 

My attempt to formally express what I just written:

Now let's do that in code, my language of choice now is scala

def power[A](set: List[A]): List[List[A]] = set match {
    case Nil => List(Nil)
    case head::tail => power(tail) flatMap (set => List(set, head::set))
}

Yay just four lines. and the last one barely matters. But I can do even better. The same code in haskell

power [] = [[]]
power (head:tail) = power tail >>= \set ->[set, head:set]

Both code snippets don't comply exactly to the equation. I swapped in flat-map instead of union. It gets rid of repetition(but I don't know the math notation, sadly). So you apply the lambda that creates both sides of the union to your list and then flatten it to produce the same result.

This code may look a bit cryptic at first sight but once you parse the syntax you can grasp the intention much more quickly than the imperative version. At least I can. Recursion is quite nice once you get used to it.

Related articles

• Making a programming language: Part 3 - adding features
• Python and lazy evaluation
• The birth of LISP - a summary of John McCarthy's original paper
• When Is a Set Better Than an Array in Ruby?

Pretty function composition in scala and asynchronous function composition on android

Composition

Surjective composition: the first function need not be surjective. (Photo credit: Wikipedia)

Function composition is a nice way to sequence transformations on data. For example in a compiler you take your source, parse, check, optimize and generate code(in a nutshell). It's a linear series of transformations -> perfect for function composition
In Haskell you can use this beautiful syntax

compile = parse . check . optimize . codegen

leaving out the parameter(as it can be infered) and noting composition as "." which kinda looks like ° used in math(if you squint a bit).
In scala you could do something like

val compile = parse compose check compose optimize compose codegen

Nearly there, I just want it to look a bit prettier. (Compose is a method defined on Function1 trait)
So I define an implicit conversion from function to "composable"

implicit def function2composable[A,B](f: A=>B) = new AnyRef{
  def -->[C](g: B=>C) = v => g(f(c))
}

This creates an object and reimplements "compose" but I really like the syntax:

compile = parse --> check --> optimize --> codegen

Functional programming can be imagined as a waterfall of data, flowing from one function into the next, and the --> operator represents this nicely.

Let's go a step further. If the composition is one-off, and this is a waterfall of DATA it could be nice to represent that.
Something like

result = source --> parse --> check --> optimize --> codegen

So now I'm taking a value and sending it through black boxes. Very nice. Apart from the fact it doesn't work(yet!).

implicit def any2waterfall[A](a: A) = new AnyRef{
  def -->[B](f: A=>B) = f(a)
}

Scala's awesome compiler can handle two implicit conversions with same method names. Nice.
You can even mix and match

result = source --> (parse --> check --> optimize) --> codegen

This does the composition of parse, check and optimize into an anonymous function, applies it to the source and then applies codegen to it's result.

Goin async

Image via CrunchBase

What about asynchronous calls? Can I compose those too? I think it's possible with Lift actors(or with scalaz's?), but I needed to integrate that into Android's activities quite recently. Well I did not *need* to do it, but it was quite a nice solution.

The usual way of doing things async in Android is with the conveniently named AsyncTask. The problem is - you can't subclass it in scala because of some compiler bug regarding varargs parameters. Silly. 

So let's do a lightweight(in terms of code) substitution. We can "spawn a thread" using scala's actors. And activity can receive messages through a Handler. 

import android.os.{Message, Handler}

trait MessageHandler {
  private val handler = new Handler {
   override def handleMessage(msg: Message) {
     react(msg.obj)
   }
  }

  def react(msg: AnyRef)

  def !(message: AnyRef) {
   val msg = new Message
   msg.obj = message
   handler.sendMessage(msg)
  }
}

So in an activity that mixes in MessageHandler I can post messages to my self. An I can do it async since Handler is thread safe

def react(msg: AnyRef) = msg match {
  case s: String = Toast(this, s, Toast.LENGTH_LONG).makeText()
  case _ => ()
}

...
//somewhere inside UI thread
import actors.Actor.actor
val that = this
actor{
  val msg = doExpensiveWork()
  that ! msg
}
...

Not the most concise way to write it, but I believe the most clear one. Method doExpensiveWork is done in the background so it doesn't block UI and it posts the result back as a message.

Async composition - finally

What I want to do now is use function composition to do something like

(input --> expensiveOne --> expensiveTwo) -!> displayResults

In other words, do "waterfall composition" in background using some input I have now and post the result back into the UI thread to method displayResults. That should be the magic of the -!> operator. Do the left side in bg and post it to the right side async.
I need a new trait for that

trait MessageHandlerExec extends MessageHandler{ outer =>
  override protected val handler = new Handler {
    override def handleMessage(msg: Message) = msg.obj match {
      case r: Runnable => r.run()
      case other: AnyRef => react(other)
    }
  }

  implicit def any2asyncComposable[A](a: => A) = new AnyRef{
    def -!>[B](f: A=>B) = outer ! new Runnable{
      def run() = f(a)
    }
  }
}

The trick here is using by-name parameters in the implicit conversion. This delays the execution of a(which in example above would be a waterfall and moves it into a worker thread.

Related articles

• 3 Tips for Writing Performant Scala
• Making a programming language: Part 1 - how to start
• Does Category Theory Make You a Better Programmer ?
• Why Java developers should check out Scala
• Ten Things You Should Know About Haskell Syntax

Making a programming language: Part 5 - variables and decisions

A typical text terminal produces input and displays output and errors (Photo credit: Wikipedia)

Table of contents, Whole project on github

In Part 4 I managed to create a Hello World. What's the next program after this in every programming tutorial? A program that asks your name and greets you. Greeter perhaps?

Reading from standard input in pretty trivial, just wrapping up readLine function from scala, see previous post on how this is done. And I called this function readln.

Variables

I could cheat a bit and write something like this

println("who are you?")
println("hello", readln())

since I don't really have to store the name. This works but I also want to make a program that responds differently to different input, e.g. simplified authentication. So I want to store the input. Something like

print("enter passcode")
input = readln()

So I first create a case class to represent this

case class Assignment(to: Identifier, from: Expression) extends Expression

parsing isn't that hard either

private def assignment: Parser[Assignment] = identifier ~ "=" ~ expr ^^ {
  case id ~ "=" ~ exp => Assignment(id, exp)
}

private def expr: Parser[Expression] = sum ||| assignment

Notice again my abuse of ||| where reverse order would have sufficed, don't do that.

Evaluation...here I had to make a choice. Where to put the assigned variables. In the same bucket as constants. Global variables ARE evil but I don't care since I'm having fun and I do it anyway. Don't worry this changes when I introduce function definitions and objects.

So StdLib became ScratRuntime and has a mutable map for storing values of identifiers. Full source here if you're interested. Of course some changes had to be made because of this refactoring. Full commit diff here.

Evaluation of assignment is now simple map put

case Assignment(name, exp) => {
  val e = apply(exp)
  runtime.identifiers.put(name.id, e)
  e
}

The expression returns the assigned value so you can do a=b=1(in fact I didn't try that yet)

What if

If expressions. I wasn't in the mood for parentheses or brackets so I went ruby style. Except my expressions are single line only(for now) so I had to put everything in one line. I needed a separator between the predicate and positive value and as an added bonus I didn't need the "end". So not much like ruby anymore but it was good inspiration. 

I considered booleans but ultimately I can implement everything still in doubles(too much work to make  whole type system of primitives when you can have just one type). Zero is False and everything else is True. So AND becomes * and OR becomes -. I'll add some equality so I can compare strings too.

I didn't need inequalities until now(didn't even think about before writing this post) so they aren't in the language yet.

Sample if expression

if input1*input2 then "okay" else "nooooooo"

See, no parens. And I was inspired by scala to make the else part mandatory.

So how do I implement this? Case class is quite trivial, it has tree expressions: predicate, true value and false value. Evaluation just evaluates the predicate(recursion!!) and then evaluates and returns the appropriate expression

case IfThenElse(pred, then, els) => apply(pred) match {
  case d: Double => if (d != 0) apply(then) else apply(els)
  case other => throw new ScratInvalidTypeError("expected a number, got "
                                                   + other)
}

That error is just a class that extends exception.
I added some more case classes and evaluation cases for Equals and NotEquals. They're very simple so I won't include them here(diff on github)
Parsing on the other hand is more interesting, here's the changed part.

private def ifThenElse: Parser[IfThenElse] =
  "if" ~ expr ~ "then" ~ expr ~ "else" ~ expr ^^ {
  case "if" ~ predicate ~ "then" ~ then ~ "else" ~ els => IfThenElse(predicate, then, els)
}

private def equality: Parser[Expression] = 
  noEqExpr ~ rep(("==" | "!=") ~ noEqExpr) ^^ {
  case head ~ tail => {
    var tree: Expression = head
    tail.foreach {
      case "==" ~ e => tree = Equals(tree, e)
      case "!=" ~ e => tree = NotEquals(tree, e)
    }
    tree
  }
}

private def noEqExpr: Parser[Expression] = sum ||| assignment ||| ifThenElse

private def expr = noEqExpr ||| equality

layers (Photo credit: theilr)

I finally got around to understand grammars a bit more. In order to make the grammar not ambiguous an not left recursive you stack layers upon layers. Like onion.  And you use these layers to separate layers of precedence - most lightly binding operations being the upper layer(expr). This gets rid of ambiguity. And you can also use these layers to deal with recursion. Something in a deeper layer can contain an item from a higher layer - thus recursion - but it must first match something to avoid infinite recursion.  And that's it. This is very well explained on compilers course on Coursera and I thought I understood the (very abstract) explanation but the evidence says I did not until I had some hands on experience.

A quick sample in scrat to finish it of

print("enter passcode")
pass = "password"
state = if readln()==pass then "granted" else "denied"
println("access", state)

next implementing user defined functions

Related articles

• 20 controversial programming opinions
• Is it a must for every programmer to learn regular expressions?

Making a programming language: Part 4 - Hello World

printf("hello, world\n"); (Photo credit: isipeoria)

Table of contents, Whole project on github

What good is a language if you cannot do a Hello World program. Every tutorial on every language I ever read has a Hello World in it somewhere, even if it's a convoluted and sarcastic one.

So what do I need?

• a way to print stuff to console 
• strings

In that order. Since this is more of a math lang for now my first hello world can just print 1 - arguably the simplest number.

Println

This one is super easy. Just wrap scala's println. Here's the whole code

lazy val sprint: FunctionVarArg = {
  case lst: List[_] => lst --> mkString --> println
  case other => throw ScratInvalidTypeError("expected a commaList but got "                                                   + other)
}

And then I put this as "println" into StdLib's map = global namespace. Since I already have support for functions I just allowed them to do side effects(semantics-no code).
The --> operator might have confuse you. It's in an implicit conversion I defined:

implicit def any2applyFunc[A](a: A) = new AnyRef {
  def -->[B](f: A => B): B = f(a)
}

This is the so called pimp my library pattern in scala. It adds the --> operator to all objects. This operator takes another single argument function, applies it and returns the result.
So I can have

lst --> mkString --> println

instead of

println(mkString(lst))

Think of it like Haskell's $ operator even if it works in a different way. Oh yes, mkString is another function that I put into StdLib that takes a List(takes Any but does pattern matching) and returns List.mkString

And now I have my Hello Math World

println(1)

Strings

First I have to parse strings

private def string: Parser[SString] = "\".*?\"".r ^^ {
  s => SString(s.substring(1, s.length - 1))
}

private def value: Parser[Expression] = number | string | identifier

SString is just a case class wrapper for string that extends Expression so I can use it in other expressions.
When I was first writing this I forgot to add the action combinator to strip of the quotes and was greatly mistified by all strings being wrapped in "". I even spend half an hour debugging my evaluator before it dawned on me.
I believe the evaluation of this is trivial.

Now I have a REAL hello world:

println("Hello world")

Well...no. Hello world is a program you run. I need an interpreter to run files.

Interpreter

Not quite that different from REPL. In fact it's just REL: read, evaluate, loop. Printing is now only with explicit println calls. And I don't need to catch exceptions and return into the loop.  Whole code for the interpreter

object Interpreter {
  def main(args: Array[String]) = {
    if (args.length != 1) {
      println("parameters: filename to interpret")
    } else {
      interpretFile(new File(args(0)))
    }
  }

  val runtime = new ScratRuntime

  def interpretFile(file: File) {
    if (file.canRead) {
      val source = io.Source.fromFile(file)
      source.getLines().foreach(runtime.eval)
      source.close()
    } else {
      println("cannot open file " + file.getPath)
    }
  }
}

And now I can put my hello world in a file and run it.
But I needed to decide on the extension. I know it's silly but I didn't want to save the file until I had the extension in mind. And this mean naming the language. Being in "logic mode" I asked my awsome girlfriend who's more artsy type of a person and she immediately responded "scrat"(she's huge fan of Scrat the squirrel from Ice Age). And them some more funny names, but scrat stuck with me. So I named the file hello.scrat.


next: variables and decisions

Related articles

• 10 Programming Languages You Probably Never Heard Of
• Functional Programming in 2012 ... time to learn something more?
• Conways Game of Life in Scala REPL
• Java 8 lambdas