Gomoku

Gomoku is a compiler for programs written in the Go Programming Language, targeting modern-ish C++.

This is an experiment to determine how well Go will perform on embedded devices. Please see the FAQ for more details on the reasoning behind this project.

Help to move this forward is greatly appreciated.

Usage

Pass the path to the program being built. Paths relative to $GOHOME, relative, and absolute paths are accepted. Output will be generated in outdir/ under the current directory (this directory will be cleared every run):

gomoku ./samples/interfaces

This will generate a pair of .cpp and .h files for each imported package (and their dependencies). Generated files are not indented (yet), so piping them through clang-format (or other indenting tool) is recommended.

It is posible that the compiler will abort midway through code generation since not all data types, statements, and expressions are implemented yet.

Sample code

surface (from chapter 3 of "The Go Programming Language" by Kernighan and Donovan)

Full code here, excerpt below:

Go

func corner(i, j int) (float64, float64) {
        // Find point (x,y) at corner of cell (i,j).
        x := xyrange * (float64(i)/cells - 0.5)
        y := xyrange * (float64(j)/cells - 0.5)

        // Compute surface height z.
        z := f(x, y)

        // Project (x,y,z) isometrically onto 2-D SVG canvas (sx,sy).
        sx := width/2 + (x-y)*cos30*xyscale
        sy := height/2 + (x+y)*sin30*xyscale - z*zscale
        return sx, sy
}

C++

std::tuple<double, double> corner(int i, int j) {
  double sx{0};
  double sy{0};
  double x{0};
  double y{0};
  double z{0};
  x = xyrange * (double(i) / cells - 0.5);
  y = xyrange * (double(j) / cells - 0.5);
  z = f(x, y);
  sx = width / 2 + (x - y) * cos30 * xyscale;
  sy = height / 2 + (x + y) * sin30 * xyscale - z * zscale;
  return {sx, sy};
}

samples/interfaces/interfaces.go

Go

type Interfacer interface {
        Interface() int
}

type Foo struct {
        SomeInt int
}

func (f Foo) Interface() int {
        var f2 Foo
        return f2.SomeInt * f.ConcreteMethod()
}

func (f Foo) ConcreteMethod() int { return 42 }

func UsingInterfaceType(i Interfacer) int { return i.Interface() * 1234 }

C++

struct Foo : public Interfacer {
  int SomeInt{0};
  int ConcreteMethod();
  virtual int Interface() override;
};
struct Interfacer { // NB: this is declared in the wrong order
  virtual int Interface() = 0;
};
int UsingInterfaceType(Interfacer i);
int Foo::Interface() {
  Foo f2{};
  return f2.SomeInt * this->ConcreteMethod();
}
int Foo::ConcreteMethod() { return 42; }
int UsingInterfaceType(Interfacer i) { return i.Interface() * 1234; }

defer1 (chapter 5 of the same book)

Go

func f(x int) {
        fmt.Printf("f(%d)\n", x+0/x) // panics if x == 0
        defer fmt.Printf("defer %d\n", x)
        f(x - 1)
}

C++

void f(int x) {
  moku::defer _defer_;

  fmt::Printf("f(%d)\n", x + 0 / x);
  _defer_.Push([=]() mutable { fmt::Printf("defer %d\n", x); });
  f(x - 1);
}

gcd

Go

func gcd(x, y int) int {
	for y != 0 {
		x, y = y, x%y
	}
	return x
}

C++

int gcd(int x, int y) {
  while (y != 0) {
    std::tie(x, y) = std::tuple<int, int>(y, x % y);
  }
  return x;
}

Switch statement (tagged)

Go

switch i {
default:
        println(4)
        fallthrough
case 1:
        println(1)
case 2:
        println(2)
case 3:
        println(3)
}

C++

if ((i == 1)) {
_ident_1_:
  println(1);
} else if ((i == 2)) {
_ident_2_:
  println(2);
} else if ((i == 3)) {
_ident_3_:
  println(3);
} else {
_ident_0_:
  println(4);
  goto _ident_1_;
}

Switch statement (non-tagged)

Go

switch {
default:
        println(0)
case i > 10 && i != 50:
        println(1)
case i < 20, i > 150:
        println(2)
}

C++

if ((i > 10 && i != 50)) {
_ident_1_:
  println(1);
} else if ((i < 20) || (i > 150)) {
_ident_2_:
  println(2);
} else {
_ident_0_:
  println(0);
}

Button and LED sample from Gobot's Getting Started

Go

func main() {
        firmataAdaptor := firmata.NewAdaptor("/dev/ttyACM0")

        button := gpio.NewButtonDriver(firmataAdaptor, "5")
        led := gpio.NewLedDriver(firmataAdaptor, "13")

        work := func() {
                button.On(gpio.ButtonPush, func(data interface{}) {
                        led.On()
                })
                button.On(gpio.ButtonRelease, func(data interface{}) {
                        led.Off()
                })
        }

        robot := gobot.NewRobot("buttonBot",
                []gobot.Connection{firmataAdaptor},
                []gobot.Device{button, led},
                work,
        )

        robot.Start()
}

C++

void _main() {
  ButtonDriver *button{std::nullptr};
  Adaptor *firmataAdaptor{std::nullptr};
  LedDriver *led{std::nullptr};
  Robot *robot{std::nullptr};
  std::function<void()> work{std::nullptr};

  firmataAdaptor = firmata::NewAdaptor("/dev/ttyACM0");
  button = gpio::NewButtonDriver(firmataAdaptor, "5");
  led = gpio::NewLedDriver(firmataAdaptor, "13");
  work = [=]() mutable -> void {
    button->On(gpio::ButtonPush,
               [=](moku::empty_interface data) mutable -> void { led->On(); });
    button->On(gpio::ButtonRelease,
               [=](moku::empty_interface data) mutable -> void { led->Off(); });
  };
  robot = gobot::NewRobot("buttonBot",
                          moku::slice<gobot::Connection>{firmataAdaptor},
                          moku::slice<gobot::Device>{button, led}, work);
  robot->Start();
}

FAQ

What's with the name?

Go is one of the oldest board games that are still played today. Gomoku is a newer game, but is played with the same board and pieces. The rules are different, but for the untrained eye, they look exactly the same.

The parallels with the Go programming language and this compiler were too good to not make the pun.

Why not just modify the Go compiler?

There are a few reasons:

• There are many architectures out there that we'd like to support, and writing a backend for every single one of them would be impractical. Mainly, we'd like to support x86, ARC, ARM Thumb, Xtensa, and RISC-V. x86 is already (well) supported by the reference Go compiler, but microcontroller class x86 will often sport an older ISA (usually i586 class CPU or older), which most likely would involve some maintenance work.
• Go was never designed for embedded applications, specially when executing on environments with severe memory restrictions such as many microcontrollers. The reference runtime and compiler assumes this at every opportunity.
• While C++ is a language that people love to hate, the modern variants are powerful, reasonably expressive, and compilers such as GCC and Clang leverage years of engineering effort in order to produce correct, efficient code. All the while supporting all the architectures that we'd want to support.
• The Go compiler was recently changed to use an SSA backend; this made it easier to write backends, and it's possible to write one that generates C code. This would mostly take care of the instruction set, though, still leaving on the table many of the assumptions for the kind of operating systems the reference compiler has been designed to generate code for.
• This is a good challenge and a great way to learn all the nook and crannies of a language.

How does transpiling to C++ make Go more "embeddable"? Especially when considering that Go has a non-trivial runtime, including a garbage collector and support for multithreading.

Gomoku isn't targetting 8-bit microcontrollers; it's targetting the 32-bit ones, with reasonably fast CPUs (over 40MHz, sometimes with dual cores running at over 100MHz), a few hundred kilobytes of RAM, and a megabyte or so of ROM.

For instance, it's possible to run JavaScript with zephyr.js, which also has a non-trivial runtime and garbage collector.

Zephyr also has threads and all the basic building blocks necessary to build Go's primitives on top of, and it's the embedded operating system Gomoku is targeting first. (Linux will be supported as well mostly for debugging reasons, of course. Maybe it will be possible to use some Go libraries from C++ as a "stretch goal".)

The C++ standard template library (stl) will most likely be used at first to support the Gomoku runtime, but it'll eventually be ditched for something that works better on more limited platforms. Also, the Go standard library won't be used as is on embedded devices; a new one will most likely have to be written. This means that much of what makes Go the environment that it is won't be available for Gomoku; see the FAQ on the project name.

What's the license?

It's a 2-clause BSD.

I'd like to contribute. Is there a code of conduct?

Yes. We're using the same code that the Go commmunity uses.

When it will actually be able to generate compilable code?

It's hard to tell; there are still a lot of things to do. Some of them are easier than others, but there are a lot of subtle details that are hard to get right.

But we're very open to contributions, so if you'd like to see this happen faster, you know what to do.

Will it be self-hosting?

The original Go compiler was written in C, mechanically translated to Go (with manual work to fix up the translation). If this compiler could compile itself, it would be almost a full circle. While awesome, we're quite far away from this possibility.

What platforms will this support?

At first, Linux with STL is going to be the only supported platform. The reason is that tools such as AddressSanitizer and Valgrind are invaluable when debugging.

Afterwards, it's very possible that an RTOS such as Zephyr will be supported. There's a good possibility that STL will be ditched at this point, favoring either something existing but lightweight, or something custom made.

In any case, compilation for different operating systems and/or architectures should be as simple as setting the GOOS and GOARCH environment variables, or different but related variables that will be specific to Gomoku.

Are there unit tests?

No, not yet. This is a must and will happen soon.

What about memory management, what's going to be the strategy?

At first, a stop-the-world-mark-and-sweep garbage collector, with collection happening at allocation phase, when there's no more heap space available.

This will most likely be custom made, but experimnents with existing collectors might be performed -- if they're adequate, there will be no need to write (or modify) one.

Will it use the Go standard library?

At first, yes, as that's what we already have. However, it's very likely that a lightweight library will be written for embedded devices. Not everything should be written from scratch, though; some parts from the standard library might be cherry-picked.

What's necessary to have this actually work?

There are many things that can (and need) to be performed before calling this even remotely usable. Here's a short list of tasks and things that need to be implemented; it's by no means complete, and some of these tasks are way more challenging than others:

• Generating code for imports, not only type information
• Review generation and call of package-level initialization (init func, global calls, etc)
• Ensuring that all types implementing interfaces are assignable to the interface type
• Fix the order of generated types
• Reorganize the package in smaller files
• Implement unit tests
• Get pointer vs. value semantics as correct as possible
• Implement type conversion
• Implement type assertion (incl. type switches)
• Implement basic Go data types (arrays, slices, and maps)
• Nil values
• Comparison with nil values
• Built-in functions (e.g. make(), new(), append(), cap(), etc.)
• Closures / anonymous functions
• Deferred statements
• Range-based loops
• Switch statement
• If statement
• Write a basic standard library for embedded devices
• Memory management with garbage collection
• Perform escape analysis to determine where to allocate things
• Channels (including select statement)
• Goroutines
• Implement _
• Implement built-in functions (println, len, cap, etc.)
• Implement interface expressions for non-empty interfaces