Posted on Feb 5, 2022

100 Languages Speedrun: Episode 80: Minimalistic Version of Esoteric Language Tuples

In the previous episode I tried to design new esoteric language Tuples. The whole language is just collection of rules like (tuple) -> (tuple).

But one thing I was wondering about is how much of Tuples' power is due to its access to arbitrary mathematical expression.

Would Tuples still be a viable language if we limit it like this:

there's zero or one tuple as dependency (already so in the original version)
every field in dependency is either constant or matches anything
every field in result is one of: constant, field, field+1, or field-1

So in our minimalist version (1, a, b) -> (2, b-1, b, b+1) is a valid tuple, but something like (1, a) -> (1, a+10) or (1, a, b) -> (2, a+b) is not.

I think this is as extreme as we can go while still having something resembling a human-programmable language.

I'm using the same Tuples interpreter as before, I just won't be using any rules not following these restrictions.

All code will be in both idealized Tuples syntax (not implemented yet), and in Ruby DSL that actually runs. These should be both identical.

Hello, World!

Program to print Hello, World! is identical as it's all just constants:

-> (0, 1, 0, 72) -> (0, 1, 1, 101) -> (0, 1, 2, 108) -> (0, 1, 3, 108) -> (0, 1, 4, 111) -> (0, 1, 5, 44) -> (0, 1, 6, 32) -> (0, 1, 7, 87) -> (0, 1, 8, 111) -> (0, 1, 9, 114) -> (0, 1, 10, 108) -> (0, 1, 11, 100) -> (0, 1, 12, 33) -> (0, 1, 13, 10)

#!/usr/bin/env ruby require_relative "tuples" Tuples.run do tuple 0, 1, 0, 72 tuple 0, 1, 1, 101 tuple 0, 1, 2, 108 tuple 0, 1, 3, 108 tuple 0, 1, 4, 111 tuple 0, 1, 5, 44 tuple 0, 1, 6, 32 tuple 0, 1, 7, 87 tuple 0, 1, 8, 111 tuple 0, 1, 9, 114 tuple 0, 1, 10, 108 tuple 0, 1, 11, 100 tuple 0, 1, 12, 33 tuple 0, 1, 13, 10 end

$ ./hello.rb Hello, World!

Hello, name!

The constants part is the same. Previously we could get away with just two rules. Functionality we need is move the name to the right place in the output (+7, to make space for Hello,), and filter all newlines (10) and end-of-input (0), by subtracting 11, as negative numbers aren't saved:

(0, 0, a, b) -> (1, b-11, 7+a, b) (1, a, b, c) -> (0, 1, b, c)

Now we do the same, but we need to do mini loops. Fortunately Tuples language makes it really easy to make a countdown loop from N to 0. We'll be using a lot of loops of such kind:

-> (0, 1, 0, 72) -> (0, 1, 1, 101) -> (0, 1, 2, 108) -> (0, 1, 3, 108) -> (0, 1, 4, 111) -> (0, 1, 5, 44) -> (0, 1, 6, 32) (0, 0, i, c) -> (1, c, 11, i, 7, c) (1, cx, cy, i, ip, c) -> (1, cx-1, cy-1, i, ip, c) (1, cx, 0, i, ip, c) -> (2, i, ip, c) (2, i, ip, c) -> (2, i+1, ip-1, c) (2, i, 0, c) -> (0, 1, i, c) -> (0, 1, 200, 33) -> (0, 1, 201, 10)

#!/usr/bin/env ruby require_relative "tuples" Tuples.run(input: true) do tuple 0, 1, 0, 72 tuple 0, 1, 1, 101 tuple 0, 1, 2, 108 tuple 0, 1, 3, 108 tuple 0, 1, 4, 111 tuple 0, 1, 5, 44 tuple 0, 1, 6, 32 rule(0, 0, :i, :c) { [1, c, 11, i, 7, c] } # 1.* filters out 0s and NLs rule(1, :cx, :cy, :i, :ip, :c) { [1, cx-1, cy-1, i, ip, c] } rule(1, :cx, 0, :i, :ip, :c) { [2, i, ip, c] } # 2.* adds ip to i rule(2, :i, :ip, :c) { [2, i+1, ip-1, c] } rule(2, :i, 0, :c) { [0, 1, i, c] } tuple 0, 1, 200, 33 tuple 0, 1, 201, 10 end

$ ./hello_name.rb Eve Hello, Eve!

Loop

To print numbers 1 to 10, we used the following code:

-> (1, 1, 9) (1, a, b) -> (1, a+1, b-1) (1, a, b) -> (2, (a/10)-1, 10*a+0, 48+(a/10)) (1, a, b) -> (2, 0, 10*a+1, 48+(a%10)) (1, a, b) -> (2, 0, 10*a+2, 10) (2, a, b, c) -> (0, 1, b, c)

It's very readable, but that arbitrary math does a lot of work here. I tried to translate it pretty much directly to our minimalistic language, and the result is not pretty (comments in the Ruby version only):

-> (1, 1, 19) (1, a, b) -> (1, a+1, b-1) (1, a, b) -> (2, a, a, 0, 0) (2, i, a, d, r) -> (2, i, a-1, d, r+1) (2, i, a, d, 10) -> (2, i, a, d+1, 0) (2, i, 0, d, r) -> (3, i, d, r, r, 9) (3, i, d, r, ra, rb) -> (3, i, d, r, ra-1, rb-1) (3, i, d, r, 0, rb) -> (4, i, 0, 0, d, r) (4, i, ia, 0, r, m) -> (4, i-1, ia, 3, r, m) (4, i, ia, ib, r, m) -> (4, i, ia+1, ib-1, r, m) (4, 0, ia, 0, r, m) -> (10, ia, r, r-1) (4, 0, ia, 0, r, m) -> (20, ia+1, m) (4, 0, ia, 0, r, m) -> (30, ia+1) (10, i, d, z) -> (11, i, d, 48) (11, i, a, b) -> (11, i, a+1, b-1) (11, i, a, 0) -> (0, 1, i, a) (20, i, d) -> (21, i, d, 48) (21, i, a, b) -> (21, i, a+1, b-1) (21, i, a, 0) -> (0, 1, i, a) (30, i) -> (0, 1, i+1, 10)

#!/usr/bin/env ruby require_relative "tuples" Tuples.run do # Initial state tuple 1, 1, 19 # Generate data rule(1, :a, :b) { [1, a+1, b-1] } # Send it to digit splitter rule(1, :a, :b) { [2, a, a, 0, 0] } # Split digits, send to r<10 filter rule(2, :i, :a, :d, :r) { [2, i, a-1, d, r+1] } rule(2, :i, :a, :d, 10) { [2, i, a, d+1, 0] } rule(2, :i, 0, :d, :r) { [3, i, d, r, r, 9] } # m<10 filter rule(3, :i, :d, :r, :ra, :rb) { [3, i, d, r, ra-1, rb-1] } rule(3, :i, :d, :r, 0, :rb) { [4, i, 0, 0, d, r] } # OK, we split the number and we're ready to print # Multiply i by 3 to get final position, then send to three printers rule(4, :i, :ia, 0, :r, :m) { [4, i-1, ia, 3, r, m] } rule(4, :i, :ia, :ib, :r, :m) { [4, i, ia+1, ib-1, r, m] } rule(4, 0, :ia, 0, :r, :m) { [10, ia, r, r-1] } rule(4, 0, :ia, 0, :r, :m) { [20, ia+1, m] } rule(4, 0, :ia, 0, :r, :m) { [30, ia+1] } # First digit printer, needs additional check arguments to filter out zeroes rule(10, :i, :d, :z) { [11, i, d, 48] } rule(11, :i, :a, :b) { [11, i, a+1, b-1] } rule(11, :i, :a, 0) { [0, 1, i, a] } # Second digit printer rule(20, :i, :d) { [21, i, d, 48] } rule(21, :i, :a, :b) { [21, i, a+1, b-1] } rule(21, :i, :a, 0) { [0, 1, i, a] } # Newline printer rule(30, :i) { [0, 1, i+1, 10] } end

$ ./loop.rb 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Ruby FizzBuzz with countdown

After doing loop like this, I thought about doing FizzBuzz by directly translating the original version, but that was crazy messy. So instead I got a different approach, with just a lot of countdown counters and minimal logic.

First I implemented it in Ruby:

#!/usr/bin/env ruby i1 = 0 i0 = 0 ic = 9 t = 0 f = 0 pos = 0 cnt = 100 while cnt > 0 cnt -= 1 i0 += 1 if ic == 0 i0 = 0 i1 += 1 ic = 9 else ic -= 1 end f = f == 0 ? 4 : f-1 t = t == 0 ? 2 : t-1 pos += 10 if t == 0 print "Fizz" end if f == 0 print "Buzz" end if t != 0 if f !=0 if i1 != 0 print i1 end print i0 end end print "\n" end

I liked it, so I proceeded to implement a Tuples version as well.

The idea is that we have a bunch of countdowns for things like:

when to end the loop (99 to 0)
when to Fizz (2 to 0)
when to Buzz (4 to 0)
when to overflow the lowest digit (9 to 0)

When the countdown is at 0, it can't go any lower, so in the following step we roll it back to the highest number, and do some logic based on that (or we end the program for the main loop countdown). This fits very well with what our minimalistic Tuples variant can and cannot do.

FizzBuzz

Here's the annotated Ruby version:

#!/usr/bin/env ruby require_relative "tuples" Tuples.run do # Initial state # There's a lot of countdown counters here tuple 1, 0, 0, 9, 0, 0, 0, 100 # cnt -= 1 rule(1, :i1, :i0, :ic, :fcnt, :bcnt, :pos, :cnt) { [2, i1, i0, ic, fcnt, bcnt, pos, 10, cnt-1] } # loop to do pos += 10 rule(2, :i1, :i0, :ic, :fcnt, :bcnt, :pos, :posplus, :cnt) { [2, i1, i0, ic, fcnt, bcnt, pos+1, posplus-1, cnt] } rule(2, :i1, :i0, :ic, :fcnt, :bcnt, :pos, 0, :cnt) { [3, i1, i0, ic, fcnt, bcnt, pos, cnt] } # update i1, i0, and ic # i0 - lowest digit # i1 - highest digit # ic + i0 == 9 always rule(3, :i1, :i0, 0, :fcnt, :bcnt, :pos, :cnt) { [4, i1+1, 0, 9, fcnt, bcnt, pos, cnt] } rule(3, :i1, :i0, :ic, :fcnt, :bcnt, :pos, :cnt) { [4, i1, i0+1, ic-1, fcnt, bcnt, pos, cnt] } # update fizz countdown rule(4, :i1, :i0, :ic, :fcnt, :bcnt, :pos, :cnt) { [5, i1, i0, ic, fcnt-1, bcnt, pos, cnt] } rule(4, :i1, :i0, :ic, 0, :bcnt, :pos, :cnt) { [5, i1, i0, ic, 2, bcnt, pos, cnt] } # update buzz countdown rule(5, :i1, :i0, :ic, :fcnt, :bcnt, :pos, :cnt) { [6, i1, i0, ic, fcnt, bcnt-1, pos, cnt] } rule(5, :i1, :i0, :ic, :fcnt, 0, :pos, :cnt) { [6, i1, i0, ic, fcnt, 4, pos, cnt] } # decide what to print based on counters rule(6, :i1, :i0, :ic, 0, :bcnt, :pos, :cnt) { [10, pos] } rule(6, :i1, :i0, :ic, :fcnt, 0, :pos, :cnt) { [11, pos] } rule(6, :i1, :i0, :ic, :fcnt, :bcnt, :pos, :cnt) { [12, fcnt-1, bcnt-1, i1, i0, pos] } rule(6, :i1, :i0, :ic, :fcnt, :bcnt, :pos, :cnt) { [13, pos] } # continue the loop rule(6, :i1, :i0, :ic, :fcnt, :bcnt, :pos, :cnt) { [1, i1, i0, ic, fcnt, bcnt, pos, cnt] } # print fizz rule(10, :pos) { [20, pos, 0, 70] } rule(10, :pos) { [20, pos, 1, 105] } rule(10, :pos) { [20, pos, 2, 122] } rule(10, :pos) { [20, pos, 3, 122] } # print buzz rule(11, :pos) { [20, pos, 4, 66] } rule(11, :pos) { [20, pos, 5, 117] } rule(11, :pos) { [20, pos, 6, 122] } rule(11, :pos) { [20, pos, 7, 122] } # print number rule(12, :fcheck, :bcheck, :i1, :i0, :pos) { [14, i1-1, pos, i1] } rule(12, :fcheck, :bcheck, :i1, :i0, :pos) { [14, 0, pos+1, i0] } # print newline rule(13, :pos) { [20, pos, 8, 10] } # digit print check rule(14, :dcheck, :pos, :c) { [15, pos, c, 48] } # convert digit to ASCII rule(15, :pos, :c, :cplus) { [15, pos, c+1, cplus-1] } rule(15, :pos, :c, 0) { [0, 1, pos, c] } # print character at specific offset rule(20, :pos, :posplus, :c) { [20, pos+1, posplus-1, c] } rule(20, :pos, 0, :c) { [0, 1, pos, c] } end

And the Tuples version:

-> (1, 0, 0, 9, 0, 0, 0, 100) (1, i1, i0, ic, fcnt, bcnt, pos, cnt) -> (2, i1, i0, ic, fcnt, bcnt, pos, 10, cnt-1) (2, i1, i0, ic, fcnt, bcnt, pos, posplus, cnt) -> (2, i1, i0, ic, fcnt, bcnt, pos+1, posplus-1, cnt) (2, i1, i0, ic, fcnt, bcnt, pos, 0, cnt) -> (3, i1, i0, ic, fcnt, bcnt, pos, cnt) (3, i1, i0, 0, fcnt, bcnt, pos, cnt) -> (4, i1+1, 0, 9, fcnt, bcnt, pos, cnt) (3, i1, i0, ic, fcnt, bcnt, pos, cnt) -> (4, i1, i0+1, ic-1, fcnt, bcnt, pos, cnt) (4, i1, i0, ic, fcnt, bcnt, pos, cnt) -> (5, i1, i0, ic, fcnt-1, bcnt, pos, cnt) (4, i1, i0, ic, 0, bcnt, pos, cnt) -> (5, i1, i0, ic, 2, bcnt, pos, cnt) (5, i1, i0, ic, fcnt, bcnt, pos, cnt) -> (6, i1, i0, ic, fcnt, bcnt-1, pos, cnt) (5, i1, i0, ic, fcnt, 0, pos, cnt) -> (6, i1, i0, ic, fcnt, 4, pos, cnt) (6, i1, i0, ic, 0, bcnt, pos, cnt) -> (10, pos) (6, i1, i0, ic, fcnt, 0, pos, cnt) -> (11, pos) (6, i1, i0, ic, fcnt, bcnt, pos, cnt) -> (12, fcnt-1, bcnt-1, i1, i0, pos) (6, i1, i0, ic, fcnt, bcnt, pos, cnt) -> (13, pos) (6, i1, i0, ic, fcnt, bcnt, pos, cnt) -> (1, i1, i0, ic, fcnt, bcnt, pos, cnt) (10, pos) -> (20, pos, 0, 70) (10, pos) -> (20, pos, 1, 105) (10, pos) -> (20, pos, 2, 122) (10, pos) -> (20, pos, 3, 122) (11, pos) -> (20, pos, 4, 66) (11, pos) -> (20, pos, 5, 117) (11, pos) -> (20, pos, 6, 122) (11, pos) -> (20, pos, 7, 122) (12, fcheck, bcheck, i1, i0, pos) -> (14, i1-1, pos, i1) (12, fcheck, bcheck, i1, i0, pos) -> (14, 0, pos+1, i0) (13, pos) -> (20, pos, 8, 10) (14, dcheck, pos, c) -> (15, pos, c, 48) (15, pos, c, cplus) -> (15, pos, c+1, cplus-1) (15, pos, c, 0) -> (0, 1, pos, c) (20, pos, posplus, c) -> (20, pos+1, posplus-1, c) (20, pos, 0, c) -> (0, 1, pos, c)

Conclusions and next steps

I think this experiment provides some indication that the power of Tuples language does not come from unlimited arithmetic on the right side, at least in theory. And the language is still human-writeable, at least no less than other esoteric languages, as I did all these without any machine assistance.

However, directly porting programs to the restricted version generates massive amount of state - as to even get a number like 1000 you need to go through 999 previous states, and doing any calculations on anything requires looping it down to zero. So many O(n) programs suddenly turned O(n^3) or worse.

This is also not the direction I want to take Tuples. In the future I'd like to explore not only allowing arbitrary arithmetic expressions, but also expanding the language to allow creation of interactive programs.