Announcing ObjoScript

[GarryPettet]

I’m super happy to announce the open source release of ObjoScript.

What is ObjoScript?

ObjoScript is an object-oriented, dynamic, embeddable and debuggable scripting language for use in Xojo applications. It utilises a stack-based VM and is about 20x faster than my previous open source language Roo.

The syntax is heavily inspired by Wren. It’s a curly brackets language but semicolons are not needed.

Major features

1. Integrated debugger - step through code line-by-line and inspect local and global variable names and values.
2. Familiar syntax. It’s C-like but semicolon free.
3. Implemented via a stack-based virtual machine. This makes it much faster than tree-walk interpreter languages.
4. Object-oriented. All code executes either within a function or the method of a class. Class fields are private by default and are accessed through method calls.
5. Lovingly crafted. Almost every line of code is commented and there is rich documentation within the source code.
6. Comprehensive test suite. Several hundred tests have been implemented testing every facet of the language and the core library.
7. Cross platform. The desktop dev harness compiles and runs on macOS, Windows and Linux. The ObjoScript VM compiles without issue on iOS.
8. 100% native API 2.0 Xojo code. The only plugins required are for the demo app / bundled code editor. The actual VM is entirely Xojo code.

Why create it?

I needed an embeddable scripting language for an app I’m working on that’s written in Xojo. Obviously Xojo provides its own scripting engine (XojoScript) and there are several other scripting languages available via plugins (e.g. Wren and Python) however none of them provide any way to debug code written in the scripting language.

For my app, it’s crucial that the end user is able to step through code written in the scripting language and inspect variables to help them debug. This is simply impossible in the currently available engines so I decided to implement my own.

What’s in the GitHub repo?

1. The ObjoScript compiler and virtual machine.
2. A basic IDE including a syntax-highlighting code editor, interactive debugger, bytecode disassembler and AST viewer.
3. Comprehensive automated test suite.
4. A command line tool (CLI) to run scripts from the Terminal.

About the IDE and debugger

The IDE contains a cut-down version of my XUICodeEditor control. I debated a lot about whether or not to include this in the repo (since I sell the editor as part of a larger suite of controls) but decided in the end that this project is much better with its inclusion. If you like the project, please consider purchasing a license for the full XUI suite.

As you can see from the screenshot, the IDE has most basic functionality.

Code editing

Bytecode disassembly

AST viewer

Debugger

Test suite

Requirements

Development has been done with the latest version of Xojo (currently Xojo 2022 Release 3.2). The code is API 2.0 so you’ll need a modern version of Xojo to run it.

Whilst ObjoScript is 100% Xojo code and itself doesn’t depend on any plugins, the development harness uses Einhugur’s TreeView plugin and the code editor uses Einhugur’s open source TextInputCanvas. Demo versions are included in the repo.

Documentation

There is extensive documentation in the repository’s wiki. I still need to document the core library (string, number functions, etc) but the code is extensively commented.

Where to get it

As usual, it’s hosted on GitHub.

Pull requests and constructive feedback are welcome.

[Kem_Tekinay]

When I get a few minutes, I’m looking forward to looking this over. Thanks for contributing it to the community.

Suggestion: the Advent of Code challenge is starting on Dec. 1. Using this language to solve the puzzles would be a way to show what it can do, and how it’s done, and would also give you a way to tease out bugs or limitations.

[GarryPettet]

Thanks for the kind words Kem.

That’s a great idea about the advent of code. I’ll try to remember to do that.

[Kem_Tekinay]

@GarryPettet about your new sort function, you can replace the bubble sort with a QuickSort algorithm that will run dramatically faster for longer lists and would probably obviate the need for the fastSort.

I can outline the steps if needed, either recursively or inline.

[GarryPettet]

Ooh - that sounds interesting.

I’m currently implementing List.sort() in ObjoScript (you can see it in the core.objo file) since there’s no good way to implement it as a foreign method (since I want to support sorting custom classes which may themselves have overridden equality operators).

This is the current method:

/// Sorts a single dimension list using a bubblesort algorithm.
sort() {
  var n = this.count
  if n < 2 then return
  while true {
    var swapped = false
    foreach i in 1..n-1 {
      if this[i-1] > this[i] {
        var t = this[i-1]
        this[i-1] = this[i]
        this[i] = t
        swapped = true
      }
    }
   if not swapped then return
  }
}

I’d love to see the better algorithm if you have time.

[Kem_Tekinay]

The general idea for QuickSort is to keep creating smaller and smaller piles out of your data until each pile has one element, then join the piles.

A simple example:

5 4 1 9 6 7

Starting with the first element 5, you create three piles:

4 1 and 5 and 9 6 7

Now you never have to look at 5 again, so you do the same thing with the “less than” and “greater than” piles. In this case, with 2 elements in the less than pile, you can do a simple swap:

1 4 and 5 and 9 6 7

Now apply the same logic to the “greater than” pile:

1 4 and 5 and 6 7 and 9

Now there is no “greater than” side and the “less than” pile has only two elements that are already in order.

With nothing left to do, join the piles and you’re done.

This is usually done with recursively, but it’s faster to do it inline by tracking the start and end of each pile and swapping elements within it.

I have Xojo code somewhere that I can share here if it will help.

[GarryPettet]

Is it valid for non-integer arrays? I’ve been looking at Rosetta and there are several examples but they all explicitly function on integer arrays. I presume there is no reason the sorting algorithm can’t work on any item so long it’s elements can compare to another?

[Kem_Tekinay]

I didn’t mention it here, but the scheme as outlined would be slow for already-sorted or mostly sorted arrays. The optimization is to pick your first comparison elements from the middle value of the first, middle, and last element of the pile.

[Kem_Tekinay]

Correct, as long as you can get a valid comparison, you can sort anything.

[GarryPettet]

At first crack this seems to work:

function quickSort(a) {
  if a.count <= 1 then return a

  var pivot = a[0]
  var less = []
  var more = []
  var pivotList = []

  // Partition.
  foreach i in a {
    if i < pivot {
      less.add(i)
    } else if i > pivot {
     more.add(i)
    } else {
     pivotList.add(i)
    }
  }

  // Recursively sort sublists.
  less = quickSort(less)
  more = quickSort(more)

  // Concatenate results.
  less.addAll(pivotList)
  less.addAll(more)
  return less
}

var arr = [1,5,2,7,3,9,4,6,8]
System.print("Before sort: " + arr)
arr = quickSort(arr)
System.print("After sort: " + arr)

// Before sort: [1, 5, 2, 7, 3, 9, 4, 6, 8]
// After sort: [1, 2, 3, 4, 5, 6, 7, 8, 9]

I’ll write some unit tests and see if it’s stable…

[Björn_Eiríksson]

I would do it without the recursion. (Especially in script engine)

Here are examples of implementation without recursion:

https://alienryderflex.com/quicksort/

(Or find better link I guess, the link it self hints there might be errors in this one)

[GarryPettet]

Good point. I’ve found an iterative Quicksort algorithm for Java that I’ll try to port. I can then run some comparisons.

Method calls are optimised a bit in ObjoScript but they still rely on a dictionary lookup so avoiding them should help.

[Kem_Tekinay]

Yes!

For the pivot, take the middle of the first, middle, and last value of your source. Something like this:

middleOfThree(a, b, c) {
  if (a <= b and b <= c) or (a >= b and b >= c) {
    return b
  } else if (a <= c and c <= b) or (a >= c and c >= b) {
    return c
  } else {
    return a
}

var middleElement = a.LastIndex / 2
var pivot = middleOfThree(a[0], a[middleElement], a[a.lastIndex])

It’s faster to inline that, of course.

[GarryPettet]

Here’s the new implementation of List.sort(). It is waaaay faster than the original bubble sort algorithm and I can do away with the tacky List.sortFast() method.

I’m using an iterative QuickSort algorithm.

// Iterative Quicksort routine.
function iterativeQuicksort(a) {
  // Create a stack for storing sublist start and end index.
  var stack = []

  // Get the starting and ending index of a given list.
  var start = 0
  var end = a.count - 1

  // Push the start and end index of the array into the stack.
  stack.add(start : end)

  // Loop until the stack is empty.
  while not stack.isEmpty {
    // Remove top pair from the list and get sublist starting and ending indices.
	var pair = stack.pop()
    start = pair.key
    end = pair.value

    // Rearrange elements across pivot.
    // Pick the rightmost element as a pivot from the list.
    var pivot = a[end]

    // Elements less than the pivot will go to the left of `pIndex`
    // Elements more than the pivot will go to the right of `pIndex`
    // Equal elements can go either way
    var pIndex = start

    // Each time we find an element less than or equal to the pivot,
    // `pIndex` is incremented, and that element would be placed
    // before the pivot.
    foreach i in start...end {
      if a[i] <= pivot {
	    a.swap(i, pIndex)
        pIndex = pIndex + 1
      }
    }

    // Swap `pIndex` with pivot
    a.swap(pIndex, end)

    // We now have index of the pivot element.
    pivot = pIndex

    // Push sublist indices containing elements that are
    // less than the current pivot to stack.
    if pivot - 1 > start {
      stack.add(start : pivot - 1)
    }

    // Push sublist indices containing elements that are
    // more than the current pivot to stack.
    if pivot + 1 < end {
      stack.add(pivot + 1 : end)
    }
  }
}

You’ll notice that I also had to add language support for KeyValue instances (a bit like Xojo Pairs) with the following syntax:

var kv = 1 : 2 // key is 1, value is 2

[Thomas_Tempelmann]

Just seeing this for the first time. Now I get what you’re working on. Impressive!

A little issue on the wiki: The first link is dead - it needs to point to “Contents-of-the-Repository”, not “Contents-of-the-repo”.

[Kem_Tekinay]

Very nice.

One optimization is to check start vs. end at the top of the loop.

if start >= end {
  continue
}

if start = (end - 1) {
  if a[start] > a[end] {
    a.swap(start, end)
  }
  continue
}

Also, look again at the “middle of three” optimization I outlined above. To see the difference, try sorting a long, already-sorted list.

[GarryPettet]

Thanks.

Fixed.

[GarryPettet]

@Kem_Tekinay

if start >= end {
  continue
}

if start = (end - 1) {
  if a[start] > a[end] {
    a.swap(start, end)
  }
  continue
}

Do you mean here?

while not stack.isEmpty {
// Remove top pair from the list and get sublist starting and ending indices.
var pair = stack.pop()
start = pair.key
end = pair.value   // <---------

[Kem_Tekinay]

Right after that, yes. Treat two or fewer elements specially.

[Beatrix_Willius]

What is the use case for ObjoScript? What can I do with it? The code looks impressive. But there is no example beyond the test cases.