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.

Code

All code examples for the series will be in this repository.

Code for the Minimalistic Version of Esoteric Language Tuples episode is available here.

Blog