## 14 January 2010

### Prime Factors Kata BASIC

The Prime Factors Kata is a small coding exercise first shown by Uncle Bob in Java several years ago. It has been done in C#, Ruby and probably some other languages. Recently Uncle Bob performed it as katacast in Ruby. (Go watch it! It's really cool. I will wait here.) He was followed by others in C# and Groovy. Anyway I'm sure it has not been done in BASIC. (Since my last post about Scala and BASIC I've felt so "retro".) So here is my Prime Factors Kata done in BASIC V2 (Commodore 64). I couldn't use my Scala BASIC DSL because it's lacking necessary features like `GOSUB`. So I used the Versatile Commodore Emulator (VICE) instead.

The First Test.
`1000 CLR1010 PRINT "test one ";1020 i=11030 GOSUB 90001040 IF pf(0)<>0 THEN PRINT "expected no factors" : STOP1050 PRINT "green"`
Number `i` is the value to be factored and the array `pf` is expected to contain the number of prime factors in `pf(0)` followed by the factors themselves on return of the "generate" function (line 9000).
`test one?UNDEF'D STATEMENT ERROR IN 1030`
`8990 END9000 REM ----- function generate9010 REM in ... i ... number9020 REM out ... pf() ... factors9030 RETURN`
Run the test.
`test one green`
The Second Test.
`1100 CLR1110 PRINT "test two ";1120 i=21130 GOSUB 90001140 IF pf(0)<>1 THEN PRINT "expected 1 factors:";pf(0) : STOP1150 IF pf(1)<>2 THEN PRINT "expected factor 2:";pf(1) : STOP1160 PRINT "green"`
`test one greentest two expected 1 factors: 0BREAK IN 1140`
`9000 REM ----- function generate9030 IF i=1 THEN RETURN9040 pf(0)=19050 pf(1)=29060 RETURN`
Unfortunately there is no such thing as "BUnit". So I have to create testing infrastructure along the way. Keeping the tests green helps during the extraction of an "assert" method (line 100).
`80 GOTO 100090 REM ***** test infrastructure *****100 REM ----- method assert equals(int)110 REM in ... me\$ ... message120 REM in ... ex ... expected130 REM in ... ac ... actual140 IF ex=ac THEN RETURN150 PRINT "red"160 PRINT me\$;" expected";ex;" but was";ac170 STOP180 RETURN...1100 CLR1110 PRINT "test two ";1120 i=21130 GOSUB 90001140 ex=1 : ac=pf(0) : me\$="num factors" : GOSUB 1001150 ex=2 : ac=pf(1) : me\$="1st factor" : GOSUB 1001160 PRINT "green"`
The Third Test.
`1220 i=31230 GOSUB 90001240 ex=1 : ac=pf(0) : me\$="num factors" : GOSUB 1001250 ex=3 : ac=pf(1) : me\$="1st factor" : GOSUB 100`
Run the test.
`test one greentest two greentest three red1st factor expected 3 but was 2BREAK IN 170`
Modify the function.
`9050 pf(1)=i`
Green again. After the third test it's getting boring. The tests should be refactored to be more DRY:
`200 REM ----- method teardown210 PRINT "green"220 RETURN300 REM ----- method setup310 REM in ... me\$ ... test name320 PRINT "test ";me\$;" ";330 RETURN400 REM ----- method assert prime factors410 READ me\$420 GOSUB 300430 READ i440 GOSUB 9000450 READ af460 ex=af : ac=pf(0) : me\$="num factors" : GOSUB 100470 IF af=0 THEN GOTO 520480 FOR j=1 TO af490 READ ex500 ac=pf(j) : me\$=STR\$(j)+". factor" : GOSUB 100510 NEXT520 GOSUB 200530 RETURN990 REM ***** test cases *****1000 DATA "one", 1, 01010 GOSUB 4001100 DATA "two", 2, 1, 21110 GOSUB 4001200 DATA "three", 3, 1, 31210 GOSUB 400`
The Fourth Test.
`1300 DATA "four", 4, 2, 2, 21310 GOSUB 400`
`9000 REM ----- function generate9010 REM in ... i ... number9020 REM out ... pf() ... factors9025 REM local ... nf ... number factors9030 nf=09040 pf(0)=nf9050 IF i=1 THEN RETURN9060 IF INT(i/2)*2=i THEN nf=nf+1 : pf(nf)=2 : i=i/2 : GOTO 90409070 nf=nf+1 : pf(nf)=i : i=1 : GOTO 90409080 RETURN`
Line 9070 is more than needed to get the fourth test green, but it's the first thing that came to my mind.

The Fifth Test.
`1400 DATA "five", 6, 2, 2, 3`
Works as well, no changes needed.

The Sixth Test.
`1500 DATA "six", 8, 3, 2, 2, 2`
Again this still works, I "cheated" a bit.

The Seventh Test.
`1600 DATA "seven", 9, 2, 3, 3`
Now I really need the nested loops.
`9000 REM ----- function generate9010 REM in ... i ... number9020 REM out ... pf() ... factors9030 REM mod ... ca ... pf candidate9040 pf(0)=0 : REM special case9050 IF i=1 THEN RETURN9060 IF INT(i/2)*2<>i THEN GOTO 91109070 pf(0)=pf(0)+19080 pf(pf(0))=29090 i=i/29100 GOTO 90509110 FOR ca=3 TO INT(SQR(i)) STEP 29120 IF i=1 THEN RETURN9130 IF INT(i/ca)*ca<>i THEN GOTO 91809140 pf(0)=pf(0)+19150 pf(pf(0))=ca9160 i=i/ca9170 GOTO 91209180 NEXT9190 RETURN`
This includes already two performance optimisations: Handling the special case 2 up front to be able to use `STEP 2` and skip every second prime factor candidate. Second using the square root of `i` as upper bound for the loop. But there is a bug not covered by the tests. Can you spot it? Yet another refactoring to remove duplicate code of adding prime factors to `pf`.
`9040 pf(0)=0 : ca=2 : REM special case9050 IF i=1 THEN RETURN9060 IF INT(i/ca)*ca=i THEN GOSUB 9200 : GOTO 90509070 FOR ca=3 TO INT(SQR(i)) STEP 29080 IF i=1 THEN RETURN9090 IF INT(i/ca)*ca=i THEN GOSUB 9200 : GOTO 90809100 NEXT9110 RETURN9200 pf(0)=pf(0)+19210 pf(pf(0))=ca9220 i=i/ca9230 RETURN`
I could still get rid of the duplicate lines 9060 and 9090...

Another Test.
`1700 DATA "eight", 10, 2, 2, 5`
This reveals the bug in line 9070. If the value contains different prime factors then the last factor is lost. We need another check in line 9110.
`9100 NEXT9110 IF i>1 THEN ca=i : GOSUB 92009120 RETURN`
END.
One last refactoring to add colours and time measurements to methods "setup" (line 300) and "teardown" (line 200). Two more tests to see the performance of larger (32719) values of `i`. The function even works for `2^31-1` (huge), but takes quite some time, although the loop is already optimised.(Download the source.)

## 13 January 2010

### T-shirts, T-shirts, T-shirts

My Personal Branding
Here it is - finally - the official Code Cop T-shirt. In fact it's not just a shirt, but a whole series of variations: There is a black on blue version that has proper contrast and one with a navy-coloured logo which is a bit more discreet.

My favourite one is the cosy version of the blue 'Code Cop' shirt. The large logo on the front and the URL on the back are produced using Flock Print. There is a female version - I just don't know when to stop! They all look great and I had each of them produced and sent to me to inspect.

More Freaky
Who needs such T-shirts? Well, geeks need cool shirts and Jeff has one, too. If you like freaky shirts as much as I do, then you will probably love my coding related quotes shirts. I like to use (more or less) ingenious quotes to bother my colleagues with either small advice or mild criticism. One of my favourite quotes for crappy but fast developed code is Uncle Bob's "rushingtogetawholebunchofshitcodedandsortofrunning". Wearing this shirt you don't even have to say it out loud. ;-)

Talking of coding: What's your favourite design pattern? Mine is the Singleton pattern. No, I'm joking, I hate it. Alex Miller hates it too and explained some time ago why it's so hateful. (At my previous working place one third of all classes was dependant on singletons. It was awful.) I can't stand them. I'm getting sick when I see one. Therefore I'm sure that Singletons Are Evil.

## 9 January 2010

### 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 + 1220 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% = 1520 X = 23.530 X\$ = "SOME STRING"40 PRINT X50 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 `Function0`s 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 DoubleExpressionimplicit 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 `StringExpression`s. 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 `Command`s. 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 520 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 `Command`s 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.