Creating Your Own Programming Language

Computerphile is one of my favorite YouTube channels. It’s full of “videos about computers & computer stuff”, usually pretty nerdy things. One of their recent videos is called Creating Your Own Programming Language and it is an interesting watch. In just about 20 minutes, Dr Laurie Tratt (of King’s College London) creates a very simple programming language in just a few lines of code.

Dr. Tratt creates this unnamed language using Python and I thought it might be fun to quickly port it over to Xojo. Before we look at the Xojo version, here’s a brief summary of the language, which is about as stripped down as can be.

First, to simplify things it uses RPN (Reverse Polish Notation, aka postfix) for the expressions. If you’re not familiar with this, it is a different way of writing an expression where the operator comes after the operands. For example you would normally (using infix notation) write an expression to add two numbers like this:

2 + 4

In RPN you would write it like this:

2 4 +

It looks a little odd, but it is much easier to write the code for this, primarily because it removes the need for parentheses and order of operations.

The syntax for this simple language only supports a few things:

Integer literal values
+, *, – math operators
variable assignment
>= comparison operator
while…end loop

Lastly, this little language also has no error checking and its only output is the contents of any variables.

With all that said, it does run the program demonstrated in the video, which calculates the factorial of a number:

n = 5
r = 1
while n 1 >=
  r = r n *
  n = n 1 -
end

I call the Xojo version PLX and here it is showing the result of running the above program to calculate the factorial of 5:

The RPN certainly makes that code look odd! Few languages today use RPN for this reason, although it was used by some older HP calculators and the Forth programming language.

The Xojo port primarily matches the Python version since the two languages are not that dissimilar. However the code makes heavy use of the split command to do rudimentary parsing and Python does have a version of split that returns a maximum number of splits or a split that discards empty items. In the Util module is are Xojo versions of these as extension methods of String.

I also took the liberty of using longer variable names in the Xojo code. I’ve found academics like to use too-short names for things, perhaps because of their math background or maybe they don’t type well. Either way, it can make sample code harder to read in my opinion.

The Evaluator class contains the “language” and it has two methods: Evaluate and EvaluateExpression. There is also one property, Variables, that contains the list of variables and their values.

The Evaluate method parses things and calls EvaluateExpression when needed:

Public Function Evaluate(source As String) As JSONItem
  Variables = New JSONItem
  source = source.ReplaceLineEndings(EndOfLine)
  Var lines() As String = source.Split(EndOfLine, True)
  Var programCounter As Integer = 0
  
  While programCounter < lines.Count
    Var line As String = lines(programCounter).Trim
    Var parts() As String = line.Split(" ", 1)
    Select Case parts(0)
    Case "while"
      parts = line.Split(" ", 1)
      If EvaluateExpression(parts(1)) = 1 Then
        // The conditon was true, so process the code in the loop.
        programCounter = programCounter + 1
      Else
        // The condition was false, so search ahead for the "end", skipping the loop.
        parts = lines(programCounter).Split(" ", 1)
        While parts(0) <> "end"
          programCounter = programCounter + 1
          parts = lines(programCounter).Split(" ", 1)
        Wend
        programCounter = programCounter + 1
      End If
    Case "end"
      // Search back for the while to evaluate its expression again.
      parts = lines(programCounter).Split(" ", 1)
      While parts(0) <> "while"
        programCounter = programCounter - 1
        parts = lines(programCounter).Split(" ", 1)
      Wend
    Else
      // Variable assignment and expression.
      parts = line.Split(" ", 2)
      
      Var name As String = parts(0)
      Var expr As String = parts(2)
      
      Variables.Value(name) = EvaluateExpression(expr)
      
      programCounter = programCounter + 1
    End Select
  Wend
  
  Return Variables
End Function

EvaluateExpression handles the operators and operands in expressions:

Public Function EvaluateExpression(expr As String) As Integer
  Var tokens() As String = expr.Split
  Var stack() As Integer
  
  For Each token As String In tokens
    If IsNumeric(token) Then
      // Push the literal value on the stack.
      stack.Add(Integer.FromString(token))
    ElseIf Variables.HasKey(token) Then
      // This is a variable so push its value on the stack.
      stack.Add(Variables.Value(token).IntegerValue)
    Else
      // Process various operators using what is on the stack.
      Var rhs As Integer = stack.Pop
      Var lhs As Integer = stack.Pop
      
      If token = "+" Then
        stack.Add(lhs + rhs)
      ElseIf token = "*" Then
        stack.Add(lhs * rhs)
      ElseIf token = "-" Then
        stack.Add(lhs - rhs)
      ElseIf token = ">=" Then
        If lhs >= rhs Then
          stack.Add(1)
        Else
          stack.Add(0)
        End If
      End If
    End If
  Next
  
  Return stack(0)
End Function

I do encourage you to watch the video so you get Dr. Tratt’s full explanations. He walks through building this up in pieces, whereas I am only showing the final version here.

Download PLX.

Play around with the source, perhaps extending it with your own commands.

Paul learned to program in BASIC at age 13 and has programmed in more languages than he remembers, with Xojo being an obvious favorite. When not working on Xojo, you can find him talking about retrocomputing at Goto 10 and on Mastodon @lefebvre@hachyderm.io.