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
NewStatement10 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.
(Download the source.)
Trait 
