Scala DSL for BASIC

Sweet holidays - two weeks without work (but unfortunately without any connection to the internet). So what did I do? I did some code katas in Java and Ruby and some reading. Masterminds of Programming is a fine book. After reading the chapter about BASIC, which was the first language I used in the 80ties, I spent some time thinking about the old days of Commodore 64 when GOTO was still state of the art ;-)

"How about some fun coding or even performing a kata in BASIC?" Without any connection to the internet gwbasic.exe or any other interpreter was out of reach. But BASIC v2 (aka Commodore BASIC) was quite simple. So I started implementing an interpreter myself. The question was if it is possible to implement BASIC v2 as an internal DSL in Scala. DSLs are quite popular in Scala, even for other languages, e.g. Daniel Spiewak's DSL for calling JRuby from Scala. Let's see how far I got...

Hello World
First I want to compile

10 PRINT "Hello World"
RUN

That shouldn't be difficult using implicit conversions.

class Command(val lineNumber:Int, code: =>Unit) {
   def execute = code
}
class NewStatement(line:Int) {
   def PRINT(msg:String) =
      addToMemory(new Command(line) { println(msg) })
}
implicit def Int2NewStmt(line:Int) = new NewStatement(line)

def RUN ...

Note that there has to be a blank after the line numbers. This is not necessary for BASIC. Method addToMemory adds the Command instance containing the code to run (println(msg)) to a list for later execution by the mixed in RUN method. (In case you are not familiar with Scala, the code that finally gets compiled for line number 10 looks like new NewStatement(10).PRINT("Hello World"). Scala is not strict about dots and braces.) By adding PRINT(num:Int) to NewStatement

10 PRINT 12 + 12
20 PRINT 144/12

work as well. Unfortunately I am not able to implement PRINT's concatenating features, i.e.

40 PRINT "a" ; "b"
50 PRINT "a" , "b"

because ; is the empty statement in Scala and parameter lists containing , need braces.

My old friend where have you gone?
One of the first examples in the Commodore 64 Manual is

10 ? "Commodore 64"
20 GOTO 10

? is just a shortcut for PRINT. So add

class NewStatement(line:Int) {
   ...
   def ?(msg:String) = PRINT(msg)
   def GOTO(target:Int) =
      addToMemory(new Command(line) { lineCounter = target })
}

The implementation of RUN uses lineCounter to keep track of executing line numbers. When the Command with GOTO's code is executed, it changes the number of the next line to be run. Tada! Now I can GOTO Scala ;-)

Assignment and Evaluation
Let's tackle some basic assignments.

10 X% = 15
20 X = 23.5
30 X$ = "SOME STRING"
40 PRINT X
50 PRINT X$

Using the same approach as before (with some refactoring of addToMemory()):

class NewStatement(line:Int) {
   ...
   def X_=(d:Double) = {
      addToMemory(line) { variables.X = d }
   }
   def X:Double = throw new Error()

   def X$_=(s:String) = {
      addToMemory(line) { variables.X$ = s }
   }
   def X$:String = throw new Error()
}

The empty getters are necessary for Scala to recognise the methods as overridden bean properties and are never called. Although % is a valid Scala method name, it's not possible to suffix method names with it. So integer "variables" like def X%_=(i:Int) can't be defined and line 10 will never compile. (One could escape `X%`, but then the BASIC code would have to look like 10 `X%` = 15.)

For evaluation I need a method without parameters called X, in the scope of the current code, like RUN. The method must not return the value of the variable because that would be too early. It should return code that yields the value of the variable when called (yes that's a function ;-).

def X:Function0[Double] = new Function0[Double] {
   override def apply = variables.X
}
def X$:Function0[String] = new Function0[String] {
   override def apply = variables.X$
}

The container variables holds the values of all variables during "BASIC runtime", i.e. when RUN is called. To use the variables in PRINT, it must accept these functions as arguments as well.

class NewStatement(line:Int) {
   ...
   def PRINT(msg:Function0[String]) = {
      addToMemory(line) { println(msg()) }
   }
}

Variables
To allow arbitrary variables all variable names have to be predefined for assignment and for evaluation. That's impossible. But fortunately early basic used only two letters for variables. [A-Z] and [A-Z][A-Z0-9] yield 962 valid names for each Double and String variables. So all these getters and setters could be generated. The generated trait VariableAssignment with all setters is mixed into NewStatement and the generated trait VariableEvaluation with all getters is mixed into the main code. (Unfortunately the Scala compiler crashes with StackOverflowError when mixing in the trait with its nearly 4000 methods.) The container variables is better replaced with two maps, one for Double and one for String variables.

Express Yourself
To add two variables, i.e. to add the values of two variable evaluations, I change all literals and Function0s to expressions (read custom function instances). This is a major refactoring but Scala makes it easy for me. Literals are still covered by implicit conversions.

abstract class DoubleExpression {
   def value:Double

   def +(d:DoubleExpression) =
      new DoubleExpression {
         override def value = DoubleExpression.this.value + d.value
      }
   def *(d:DoubleExpression) =
      new DoubleExpression {
         override def value = DoubleExpression.this.value * d.value
      }
}
class LiteralDoubleExpression(val value:Double) extends DoubleExpression

implicit def Double2DoubleExpression(value:Double) =
   new LiteralDoubleExpression(value)
implicit def Int2DoubleExpression(value:Int) =
   new LiteralDoubleExpression(value.toDouble)

trait VariableAssignment {

   def assign(name:String, d:DoubleExpression) = {
      addToMemory(line) { memory.set(name, d.value) }
   }
   def unused = throw new Error("never used")

   def X_=(d:DoubleExpression) = assign("X", d)
   def X:DoubleExpression = unused
   ...
}
class NewStatement(line:Int) extends VariableAssignment {
   ...
   def PRINT(msg:StringExpression) =
      addToMemory(line) { println(msg.value) }
}
trait VariableEvaluation {

   class VariableDoubleExpression(val fromVariable:String)
      extends DoubleExpression {
      override def value = memory.get(fromVariable)
   }
   def X = new VariableDoubleExpression("X")
   ...
}

The code above shows the changes needed for Double. Similar classes and methods are needed to cover StringExpressions. Now let's examine what happens for 10 X = X + 1: The method call X of trait VariableEvaluation returns a VariableDoubleExpression (which will yield the value of "X" when called) on which + is invoked with the implicitly converted new LiteralDoubleExpression(1.0). The resulting DoubleExpression is the argument for the setter method X_= of trait VariableAssignment in NewStatement.

Let it Flow (Control)
Till now the Scala BASIC lacks any flow control, e.g. a conditional GOTO like

40 IF X < 5 THEN 20

class NewStatement(line:Int) {
   ...
   def IF(expr: => Boolean) = {
      class ConsumeThen(expr: => Boolean) {
         def THEN(target:Int) = addToMemory {
            if (expr) ... // goto target
         }
      }
      new ConsumeThen(expr)
   }
}

Method IF consumes the boolean expression (as a function) and returns some instance of a class that only allows the following THEN. Method THEN in turn adds the code to execute the GOTO to the list of Commands. BASIC comparison operators are different from Scala's and I have to implement them in DoubleExpression:

abstract class DoubleExpression {
   ...
   def <(d:DoubleExpression) = value < d.value
   def <>(d:DoubleExpression) = value != d.value
}

The implementation of FOR is a bit more complex mainly because the BASIC "runtime" has to keep track of the current loop, so NEXT statements are executed proper.

10 FOR X = 1 TO 5
20 PRINT "COMMODORE 64"
30 NEXT X

To allow 1.TO(5) I define a LoopRangeExpression that handles the boundaries of the loop:

class LoopRangeExpression(val lower:DoubleExpression) {
   var upper:DoubleExpression = null
   def TO(u:DoubleExpression) = {
      upper = u
      this
   }
}
implicit def Int2LoopRangeExpression(value:Int) =
   new LoopRangeExpression(new LiteralDoubleExpression(value.toDouble))

Scala compiles the loop statement into new NewStatement(10).FOR().(X()) = new LoopRangeExpression(new LiteralDoubleExpression(1.0)).TO(new LiteralDoubleExpression(5.0)). That's why method TO has to return its instance, to match the update method (used for setting array elements). So FOR has to return an object that defines update(variable: VariableDoubleExpression, range: LoopRangeExpression). Inside method update all necessary code to run the loop is put into the BASIC runtime part. Both FOR and NEXT use DoubleExpression to capture the variable names but never evaluate these expressions.

class NewStatement(line:Int) {
   ...
   def FOR = {
      new Object() {
        def update(variable:VariableDoubleExpression,
                   range:LoopRangeExpression) = {
           val usedVariable = variable.fromVariable
           addToMemory {
              ... // set usedVariable to range.lower.value
           }
           addLoop(usedVariable) {
              ... // increment and check condition
           }
        }
      }
   }
   def NEXT(d:VariableDoubleExpression) = addToMemory {
      ... // perform next for name d.fromVariable
   }
}

Functions
Support for functions like INT() or LEN$() is simple to add. I use another trait BasicFunctions, that defines the functions in terms of expressions, e.g.

def INT(d:DoubleExpression) =
   new DoubleExpression {
      override def value = d.value.floor
   }

Time for Refactoring
Although I factored out the traits of getters, setters and functions there is still too much stuff in the main class. Parsing BASIC should be separated from the logic that stores and executes the lines of code, the "runtime". I call this logic the BasicMemory.
Trait BasicParser is the main parser, which mixes in VariableEvaluation and BasicFunctions. It contains the NewStatement and all implicit conversions. Trait BasicMemory contains the program code as list of Commands and the logic needed to run them. The parser communicates with the runtime by using a small interface LinesOfCode for adding commands, runtime and memory (read variable) operations. BasicApplication is just for convenience, so BASIC programs may be written as

object Demo extends org.codecop.basic.BasicApplication {

   10 PRINT "Hello World"
   RUN
}

The Whole Beast
The shown code was developed with Scala 2.7.7. Download the full source here. There is more implemented than covered in this post, e.g. INPUT, END or STEP. This little DSL has been an experiment. It's far from complete. It lacks important features like DATA/READ or GOSUB/RETURN. I reckon that supporting DIM or DEFFN would be difficult as well. And there are things that can't be done in Scala, e.g. the shown problem with %. Still if this is interesting to people, I may do a proper release into an OSS project somewhere later.