From Esolang
Jump to: navigation, search

Bubblegum is an esoteric programming language created by Programming Puzzles & Code Golf user Dennis.

It was designed for a single purpose: to chew bubblegum in Kolmogorov complexity code golf competitions.

While Bubblegum is Turing complete, programs with non-constant output are hard to write.

Language overview

Bubblegum does its best to guess the programmer's intentions. It attempts to interpret the source code in the following ways:

  1. If the SHA-256 hash of the source code is 5e247c455fde7711206ebaa3ad0793114b77a6d16ed0497eff8e3bf98c6dba23, do the following:
    1. Read a line from standard input and save it in the variable i.
    2. Interpret the source code as Python 3.4 would.
    3. Print the contents of the variable o (initially undefined).
    4. Exit.
  2. If the source code is a valid DEFLATE stream, decompress it, print the result and exit.
  3. If the source code is a valid, raw LZMA 2 stream that could have been generated with the extreme preset level 9 and no custom filters, decompress it, print the result and exit.
  4. In all other cases, replace each byte in the source code with its code point, convert the resulting big-endian byte array from base 256 to bijective base 96 and replace the resulting digits with characters as follows:
    1. If the digit d is between 1 and 95 (both inclusive), replace it with the dth printable ASCII character (0x20 to 0x7e).
    2. If the digit d is 96, replace it with a linefeed (0x0a).

In all cases but the first, I/O is raw, i.e., Bubblegum reads and writes bytes, not characters. In the first case, the output is encoded as Python 3.4 would.


There are only two known Bubblegum programs with non-constant output.

The following program reads two or more integers from standard input and prints their sum. It will fail if the input consists of a single integer.

from math import factorial as F#

The following program reads a single integer p from standard input and prints p - 1 if p is prime and 0 otherwise. It will fail if the input consists of anything but a single integer.

from math import factorial as F#

Coincidentally, these two programs implement exactly the functionality that PPCG consensus has decided qualifies a language as being a real programming language. Therefore, it is definitely a real programming language.

Computational class

It is overwhelmingly likely that Bubblegum is Turing complete due to the fact that you can add a comment with arbitrary content to a Python program; it is not known if any string can be made to have any SHA-256 hash (that is the hash of some string) by appending to it, but if it isn't it would be quite an unexpected property. However, writing any non-constant-output program other than the known one is somewhat harder than a second preimage attack against SHA-256 (because you need to find a second preimage with certain properties), and therefore would require major advances in cryptography before it becomes possible.

Reference implementation


import hashlib, lzma, sys, zlib

def bb96encode(code, a = 0, s = []):
  code = list(code)
  for byte in code:
    a = 256 * a + byte
  while a:
    a -= 1
    r = a % 96
    s = [[10, r + 32][r < 95]] + s
    a //= 96
  return bytes(s)

with open(sys.argv[1], 'rb') as file:
  code = file.read()

if bb96encode(hashlib.sha256(code).digest()) == b"3'A~2dM'O6xiv9fzcp_ZoaI@eikCL*)%mR])NoB":
  i = input()
    o = zlib.decompress(code, -zlib.MAX_WBITS)
      o = lzma.decompress(code, format=lzma.FORMAT_RAW, filters=[{'id': lzma.FILTER_LZMA2, 'preset': 9 | lzma.PRESET_EXTREME}])
      o = bb96encode(code)

  print(o, end="")