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