Scala and FORTH - part 3

I upgraded to IntelliJ 10.5 and the new Scala plug-in, and I started getting warnings. I have fixed them, but I won't go into specifics, check the code at the bottom to see the changes.

Ok, numbers, how can they be compiled? In Forth the word "lit" is used behind the scenes to put compiled numbers on the stack, ": 1+ 1 + ;" compiles to "1+ => lit 1 +". In ScalaFORTH we'll use a variation of that concept. We don't explicitly use memory to store word definitions, but Scala List:s, and we can use a "Lit" class to put a number on the stack.

  class Lit(val num :BigDecimal) extends AbstractWord {
    val name:String = "lit " + num
    def eval() {
      stack = num :: stack
    }
  }

Notice that it's a class, not an object, and we use it by instantiating a new instance for every number that we want to compile.

  def main(args: Array[String]) {
    ...
        if (mode == Mode.interpret) {
          ...
        } else {
          if(nameDefinition) {
            ...
          } else {
            dict.get(item) match {
              case Some(s:AbstractWord) => s.compile()
              case None => dict.get("lit " + BigDecimal.apply(item)) match {
                case Some(s:AbstractWord) => s.compile()
                case None =>
                  val num = BigDecimal.apply(item)
                  dict += ("lit " + num -> new Lit(num))
                  compilationStack = compilationStack ::: ("lit " + num) :: Nil
              }
            }
        ...
  }

We use the name "lit " + num, and since it contains a space, there is no way to define a word with that name from within ScalaFORTH. Since we put the created object in the dictionary, we can reuse lit:s every time a specific number is needed.

The vocabulary is somewhat limited, but let's try it out anyway:
Welcome to scalaFORTH

> : 1. 1 . ;
 ok
> 1.
1  ok
>

This was easier done than said so let's clean up the code a bit and build up a basic vocabulary before we call it a day.

If we want to be able to do math without getting ArithmeticException:s all over the place, we need:

  val mc = java.math.MathContext.DECIMAL128

Add a helper class for 2 parameter words that leaves 1 number on the stack:

  abstract class Abstract2to1ParamWord extends AbstractWord {
    var left: BigDecimal = 0
    var right: BigDecimal = 0
    def prepare() {
      right = stack.head
      stack = stack.tail
      left = stack.head
    }
  }

Add some primitive words:

  def initDict() {
    ...
    dict += ("+" -> Plus)
    dict += ("-" -> Minus)
    dict += ("*" -> Times)
    dict += ("/" -> DividedBy)
    dict += ("pick" -> Pick)
    dict += ("nrot" -> Nrot)
    dict += ("minus" -> UnaryMinus)
    dict += ("0=" -> ZeroEquals)
    dict += ("0<" -> ZeroLess)
    dict += ("drop" -> Drop)
  }

You can see their implementations in the complete listing down below. I refactored the main loop and added a simplistic error handling so we don't get shut down every time an error occurs:

  def main(args: Array[String]) {
    initDict()
    interpret(forthVocabulary)
    Console.println("Welcome to scalaFORTH")
    Console.print("> ")
    while (true) {
      try {
        val line = Console.in.readLine
        interpret(line)
        Console.println(" ok")
        Console.print("> ")
      } catch {
        case ex: Exception => ex.printStackTrace()
      }
    }
  }

The line interpreter has been moved to its own method, and now we can initialize ScalaFORTH with regular word definitions at start up:

  val forthVocabulary ="" +
    ": 1+ 1 + ; " +
    ": 1- 1 - ; " +
    ": over 2 pick ; " +
    ": 2over 4 pick 4 pick ; " +
    ": dup 1 pick ; " +
    ": 2dup over over ; " +
    ": 2drop drop drop ; " +
    ": swap 2 nrot ; " +
    ": 2swap 4 nrot 4 nrot ; " +
    ": rot 3 nrot ; " +
    ": 2rot 6 nrot 6 nrot ; " +
    ": = - 0= ; " +
    ": < - 0< ; " +
    ": > swap - 0< ; " +
    ": */ rot rot * swap / ; " +
    ""

Excellent! Now we have an unusable Forth system, but it starts to look like Forth at least:

> : add5 5 + ;
 ok
> 1 3 / add5 dup dup 1+ - .
-1.000000000000000000000000000000000  ok
> .
5.333333333333333333333333333333333  ok

What happened? Define a new word that adds 5 to the top item on the stack, then use the new word together with some built in words: Divide 1 by 3 and leave the result on the stack, add 5 and leave result on stack, duplicate the result twice, add 1 to the top duplicate, subtract the top duplicate from the second item on the stack, print the top of the stack, twice. Maybe it's easier to understand if we track the stack contents (top of stack to the right):
"1" 1
"3" 1 3
"/" .333333333333333333333333333333333
"add5" 5.333333333333333333333333333333333
"dup" 5.3... 5.3...
"dup" 5.3... 5.3... 5.3...
"1+" 5.3... 5.3... 6.3...
"-" 5.3... -1
"." 5.333333333333333333333333333333333
"." empty

Next time we'll implement "if". I think that's going to be a bit tricky, so stay tuned.

object FORTHv5 {
  var stack = List[BigDecimal]()
  var dict = Map[String, AbstractWord]()
  var compilationStack = List[String]()
  var mode = Mode.interpret
  var nameDefinition = true
  val mc = java.math.MathContext.DECIMAL128
  val forthVocabulary ="" +
    ": 1+ 1 + ; " +
    ": 1- 1 - ; " +
    ": over 2 pick ; " +
    ": 2over 4 pick 4 pick ; " +
    ": dup 1 pick ; " +
    ": 2dup over over ; " +
    ": 2drop drop drop ; " +
    ": swap 2 nrot ; " +
    ": 2swap 4 nrot 4 nrot ; " +
    ": rot 3 nrot ; " +
    ": 2rot 6 nrot 6 nrot ; " +
    ": = - 0= ; " +
    ": < - 0< ; " +
    ": > swap - 0< ; " +
    ": */ rot rot * swap / ; " +
    ""

  def main(args: Array[String]) {
    initDict()
    interpret(forthVocabulary)
    Console.println("Welcome to scalaFORTH")
    Console.print("> ")
    while (true) {
      try {
        val line = Console.in.readLine
        interpret(line)
        Console.println(" ok")
        Console.print("> ")
      } catch {
        case ex: Exception => ex.printStackTrace()
      }
    }
  }

  def interpret(input: String) {
    val items = input.split(' ')
    for (item <- items) {
      if (mode == Mode.interpret) {
        dict.get(item) match {
          case Some(s:AbstractWord) => s.eval()
          case None => stack = BigDecimal.apply(item) :: stack
        }
      } else {
        if(nameDefinition) {
          compilationStack = item :: compilationStack
          nameDefinition = false
        } else {
          dict.get(item) match {
            case Some(s:AbstractWord) => s.compile()
            case None => dict.get("lit " + BigDecimal.apply(item)) match {
              case Some(s:AbstractWord) => s.compile()
              case None =>
                val num = BigDecimal.apply(item)
                dict += ("lit " + num -> new Lit(num))
                compilationStack = compilationStack ::: ("lit " + num) :: Nil
            }
          }
        }
      }
    }
  }

  def initDict() {
    dict += ("." -> Dot)
    dict += ("quit" -> Quit)
    dict += (":" -> Colon)
    dict += (";" -> SemiColon)
    dict += ("+" -> Plus)
    dict += ("-" -> Minus)
    dict += ("*" -> Times)
    dict += ("/" -> DividedBy)
    dict += ("pick" -> Pick)
    dict += ("nrot" -> Nrot)
    dict += ("minus" -> UnaryMinus)
    dict += ("0=" -> ZeroEquals)
    dict += ("0<" -> ZeroLess)
    dict += ("drop" -> Drop)
  }

  abstract class AbstractWord {
    val name:String
    def eval()
    def compile() {
      compilationStack = compilationStack ::: name :: Nil
    }
  }

  class Word(var immediate: Boolean = false, val name: String, 
             val words:List[String] = List()) extends AbstractWord {
    def eval() {
      for (word <- words) {
        dict.get(word) match {
          case Some(s:AbstractWord) => s.eval()
          case None => Console.err.println("Word not found: " + word)
        }
      }
    }
  }

  class Lit(val num :BigDecimal) extends AbstractWord {
    val name:String = "lit " + num
    def eval() {
      stack = num :: stack
    }
  }

  object Dot extends AbstractWord {
    val name = "."
    def eval() {
      Console.out.print(stack.head + " ")
      stack = stack.tail
    }
  }

  object Pick extends AbstractWord {
    val name = "pick"
    def eval() {
      stack = stack(stack.head.intValue()) :: stack.tail
    }
  }

  object Drop extends AbstractWord {
    val name = "drop"
    def eval() {
      stack = stack.tail
    }
  }

  object Nrot extends AbstractWord {
    val name = "nrot"
    def eval() {
      val depth = stack.head.intValue()
      val newTop = stack(depth)
      val oldTop = stack.tail.take(depth - 1)
      val oldBottom = stack.drop(depth + 1)
      stack = newTop :: oldTop ::: oldBottom
    }
  }

  object UnaryMinus extends AbstractWord {
    val name = "minus"
    def eval() {
      stack = (- stack.head) :: stack.tail
    }
  }

  object ZeroEquals extends AbstractWord {
    val name = "0="
    def eval() {
      stack = (if (stack.head == 0) -1 else 0) :: stack.tail
    }
  }

  object ZeroLess extends AbstractWord {
    val name = "0<"
    def eval() {
      stack = (if (stack.head < 0) -1 else 0) :: stack.tail
    }
  }

  abstract class Abstract2to1ParamWord extends AbstractWord {
    var left: BigDecimal = 0
    var right: BigDecimal = 0
    def prepare() {
      right = stack.head
      stack = stack.tail
      left = stack.head
    }
  }

  object Plus extends Abstract2to1ParamWord {
    val name = "+"
    def eval() {
      prepare()
      stack = (left + right) :: stack.tail
    }
  }

  object Minus extends Abstract2to1ParamWord {
    val name = "-"
    def eval() {
      prepare()
      stack = (left - right) :: stack.tail
    }
  }

  object Times extends Abstract2to1ParamWord {
    val name = "*"
    def eval() {
      prepare()
      stack = (left(mc) * right) :: stack.tail
    }
  }

  object DividedBy extends Abstract2to1ParamWord {
    val name = "/"
    def eval() {
      prepare()
      stack = (left(mc) / right) :: stack.tail
    }
  }

  object Quit extends AbstractWord {
    val name = "quit"
    def eval() {
      Console.out.print("Live long and prosper! ")
      System.exit(0)
    }
  }

  object Mode extends Enumeration {
    val interpret, compile = Value
  }

  object Colon extends AbstractWord {
    val name = ":"
    def eval() {
      mode = Mode.compile
    }
    override def compile() {

    }
  }

  object SemiColon extends AbstractWord {
    val name = ";"
    def eval() {
    }
    override def compile() {
      mode = Mode.interpret
      val newName = compilationStack.head
      val words = compilationStack.tail
      dict += (newName -> new Word(name = newName, words = words))
      compilationStack = List[String]()
      nameDefinition = true
    }
  }
}

Scala and FORTH - part 2

So far we have only implemented primitive words, and in a typical Forth implementation these words are assembly language constructs. We've use Scala instead, of course. But we need to support creating programs, not just using what's there.

In Forth you program by compiling new words. A word definition starts with a ":" and ends with a ";". E.g. ": ANewWord quit ;" would define a new word called ANewWord, which would execute the existing word "quit" when invoked.

So what do we need to implement compilation? We'll start collecting definitions when ":" is encountered, and compile the gathered data when ";" ends the definition. So we need a place to put stuff until the actual compilation:

  var compilationStack = List[String]()

We also need to know whether to execute or compile a word, ":" will enter compilation mode, and ";" will switch back to interpret mode:

  var mode = Mode.interpret

  object Mode extends Enumeration {
    val interpret, compile = Value
  }

Finally, our implementation will need to be able to differentiate between name and implementation:

  var nameDefinition = true

With that out of the way, we need to add compile time behaviour to the words:

  abstract class AbstractWord {
    val name:String
    def eval
    def compile {
      compilationStack = compilationStack ::: name :: Nil
    }
  }

The default compile implementation is to just add its own name to the compilation stack. ":" just needs to switch mode, while ";" also needs to compile the compilation stack. It does this by using the first stack element as name, and the rest as a list of word names to be executed:

  object Colon extends AbstractWord {
    val name = ":"
    def eval {
      mode = Mode.compile
    }
    override def compile {
    }
  }

   object SemiColon extends AbstractWord {
     val name = ";"
     def eval {
     }
     override def compile {
       mode = Mode.interpret
       val newName = compilationStack.head
       val words = compilationStack.tail
       dict += (newName -> new Word(name = newName, words = words))
       compilationStack = List[String]()
       nameDefinition = true
     }
   }

In the main loop we need to handle compilation:

  def main(args: Array[String]) {
    ...
      for (item <- items) {
        if (mode == Mode.interpret) {
          ...
          }
        } else {
          if(nameDefinition) {
            compilationStack = item :: compilationStack
            nameDefinition = false
          } else {
            dict.get(item) match {
              case Some(s:AbstractWord) => s.compile
              case None => Console.print("Skipping " + item)
            }
          }
        }
      }
      ...
  }

  def initDict {
    ...
    dict += (":" -> Colon)
    dict += (";" -> SemiColon)
  }

And that's it! A minimal Forth compiler ready to go:

Welcome to scalaFORTH
> : .. . . ;
 ok
> 1 2 .. 1 2 . .
2 1 2 1  ok
>

Next time we'll tackle numbers at compile time. As of now scalaFORTH looks like this:

object FORTHv3 {
  var stack = List[BigDecimal]()
  var dict = Map[String, AbstractWord]()
  var compilationStack = List[String]()
  var mode = Mode.interpret
  var nameDefinition = true

  def main(args: Array[String]) {
    initDict
    Console.println("Welcome to scalaFORTH")
    Console.print("> ")
    while (true) {
      val line = Console.in.readLine
      val items = line.split(' ')
      for (item <- items) {
        if (mode == Mode.interpret) {
          dict.get(item) match {
            case Some(s:AbstractWord) => s.eval
            case None => stack = BigDecimal.apply(item) :: stack
          }
        } else {
          if(nameDefinition) {
            compilationStack = item :: compilationStack
            nameDefinition = false
          } else {
            dict.get(item) match {
              case Some(s:AbstractWord) => s.compile
              case None => Console.print("Skipping " + item)
            }
          }
        }
      }
      Console.println(" ok")
      Console.print("> ")
    }
  }

  def initDict {
    dict += ("." -> Dot)
    dict += ("quit" -> Quit)
    dict += (":" -> Colon)
    dict += (";" -> SemiColon)
  }

  abstract class AbstractWord {
    val name:String
    def eval
    def compile {
      compilationStack = compilationStack ::: name :: Nil
    }
  }

  class Word(var immediate: Boolean = false, val name: String, val words:List[String] = List()) extends AbstractWord {
    def eval {
      for (word <- words) {
        dict.get(word) match {
          case Some(s:AbstractWord) => s.eval
          case None => Console.err.println("Word not found: " + word)
        }
      }
    }
  }

  object Dot extends AbstractWord {
    val name = "."
    def eval {
      Console.out.print(stack.head + " ")
      stack=stack.tail
    }
  }

  object Quit extends AbstractWord {
    val name = "quit"
    def eval {
      Console.out.print("Live long and prosper! ")
      System.exit(0)
    }
  }

  object Mode extends Enumeration {
    val interpret, compile = Value
  }

  object Colon extends AbstractWord {
    val name = ":"
    def eval {
      mode = Mode.compile
    }
    override def compile {

    }
  }

  object SemiColon extends AbstractWord {
    val name = ";"
    def eval {
    }
    override def compile {
      mode = Mode.interpret
      val newName = compilationStack.head
      val words = compilationStack.tail
      dict += (newName -> new Word(name = newName, words = words))
      compilationStack = List[String]()
      nameDefinition = true
    }
  }
}

Scala and FORTH - part 1

I was sorting my books the other day, and I came across an old copy of a FORTH manual. Yes we're talking FORTH from the dark ages, before all caps fell out of fashion (the manual was printed in 1981 to be more precise). It must have been more than 20 years since I programmed in FORTH.

Why not see how far I can get writing my own Forth using Scala, I thought to myself. So let's start! But before we start beware that this is a purely iterative process. I have no idea if I'll paint myself into a corner eventually. (It does seems likely though...) Enter scalaFORTH, which will be loosely based on figFORTH.

Forth is interpreted, and is used interactively, so we'll start with a prompt within a loop:

object FORTHv1 {

  def main(args: Array[String]) {
    Console.println("Welcome to scalaFORTH")
    Console.print("> ")
    while (true) {
      val line = Console.in.readLine
      if (line == "quit") System.exit(0)
      Console.println(" ok")
      Console.print("> ")
    }
  }
}

As you can see, quit is the command to exit the interpreter. Traditionally Forth is case insensitive, but the aim of scalaForth is not to be a faithful, to-the-letter, implemetation of figFORTH, just an attempt to get that warm feeling you get when programming Forth.

One fairly unique aspect of Forth is that it's stack based, and functions are typically performed on arguments on the stack, like on HP calculators. So "function(1, 2)" would look like "1 2 function" in Forth. One of the simplest and most used words is "." (dot). "." pops the top element from the stack and prints it on the console. A word is the Forth equivalent of a subroutine, method or what have you. Words are stored in a dictionary in a compiled format so that they can execute directly.

object FORTHv2 {
  var stack = List[BigDecimal]()
  var dict = Map[String, AbstractWord]()

  def main(args: Array[String]) {
    initDict
    Console.println("Welcome to scalaFORTH")
    Console.print("> ")
    while (true) {
      val line = Console.in.readLine
//      if (line == "quit") System.exit(0)
      val items = line.split(' ')
      for (item <- items) {
        dict.get(item) match {
          case Some(s:AbstractWord) => s.eval
          case None => stack = BigDecimal.apply(item) :: stack
        }
      }
      Console.println(" ok")
      Console.print("> ")
    }
  }

  def initDict {
    dict += ("." -> Dot)
    dict += ("quit" -> Quit)
  }

  abstract class AbstractWord {
    def eval
  }

  object Dot extends AbstractWord {
    def eval {
      Console.out.print(stack.head + " ")
      stack=stack.tail
    }
  }

  object Quit extends AbstractWord {
    def eval {
      Console.out.print("Live long and prosper! ")
      System.exit(0)
    }
  }
}

A stack and a dictionary has been added, and also the base class for all words. If the interpreter fails to look up a word, it will try to parse it as a number instead. Note that decimal numbers are used, figForth only supported integers.

Now that we have a dictionary, we can put "quit" there, and we also added ".". Run scalaFORTH and try some numbers!

Welcome to scalaFORTH
> 1 2 3
 ok
> . . .
3 2 1  ok
> quit
Live long and prosper!

In the next part I'll try to get compilation to work.