Making a programming language: Part 7b - using objects

Table of contents, Whole project on github

Something like EPIC FAIL occured to me and I published a post containing only half the content I intended to write. So I'm doing a part b.

My intended usage of objects is something along the lines of

objectName.someProperty
objectName.someFunction()
someFunction().someProperty
someObject.someProperty.someFunction().someProperty.someFunction

Explanation

1. getting a value from an object
2. invoking a function contained in an object
3. getting a value from returned object of the invoked function
4. a bit contrived example. Invoking a function contained inside a property(object) of an object and then getting a function value from a property of the returned value from the first function. That's a mouthful, just read the damn code instead

Dot access

So everything bases on those little dots. First my thoughts were something like "you just do expr <- expr | expr.expr". This is just wrong. At least I should have reversed the order as this leads to infineite left recursion. Then I might have got away. Then I realized I only need dots after function calls and simple identifiers. Design choice(if you think it's a bad one leave a comment). Notice the "simple identifier". That's what I did: Renamed identifier to simple identifier and put something that handles dots under name identifier. And then fixed everything. 

case class DotAccess(lst: List[Expression]) extends Expression

private def identifier: Parser[DotAccess] = 
  rep1sep((functionCall | simpleIdentifier), ".") ^^ DotAccess.apply

That's about it. At least for parsing. Now the fun begins.

Nesting scopes

Scopes were designed with nesting in mind. This is a double edged sword. See, the "privates" can be  done if you rely on not being able to access the parent scope. If dot access exposes full addressing functionality a powerful feature ceases to exist. So some protection should me in place. Something like strict get

class SScope ...
 def getStrict(key: String): Option[Any] = map.get(key)
...

And I also added an unlinked view to it just to ease usage. This is just a method that returns new SScope with no parent overriding getters and put to use map available in closure.
So now I can walk down the list in DotAccess recursively and explicitly override the implicit scope parameter. And everything automagically works. Well, not quite. If you have a function call, the arguments need to be evaluated in top scope. Not in the nested one like the function identifier. At first I didn't even think about this and only failing attempts at more complex recursion brought up this quite obvious bug.
So how to solve this? I could pre-evaluate all arguments, but I use recursion to do this and it's two levels(at least) deeper from where dots happen. So no go. I need to carry on the outer scope. I overloaded the apply method from Evaluator so other code can still function(tests ftw!) and all in all it looks like this:

def apply(e: List[Expression])(implicit scope: SScope): 
    Any = {
    (e map apply).lastOption match {
      case Some(a) => a
      case None => ()
    }
  }

  def apply(e: Expression)(implicit scope: SScope): Any = apply(e, None)(scope)

  def apply(e: Expression, auxScope: Option[SScope])(implicit scope: SScope):     Any = e match {
    ...
    case DotAccess(list) => {
      val outerScope = scope
      def step(list: List[Expression])(implicit scope: SScope): Any =
        list match {
        case Nil =>        
          throw new ScratInvalidTokenError("got empty list in DotAccess")
        case elem :: Nil => apply(elem, Some(scope))(outerScope)
        case head :: tail => apply(head) match {
          case s: SScope => step(tail)(s.unlinked)
          case other => 
            throw new ScratInvalidTypeError("expected scope, got " + other)
        }
      }
      step(list)
  }
}

So an optional aux scope is the answer. It doesn't seem pretty to me, but it does the job. 

next: trying to go faster

Related articles

• Making a programming language: Part 7 - objects
• A Quick Intro to TypeScript
• What is an object?

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

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?