Skip to content

Instantly share code, notes, and snippets.

@evincarofautumn

evincarofautumn/concurrent-esolang.md

Last active May 6, 2019 05:41
Show Gist options
  • Save evincarofautumn/bdcc83dbd8b35e482b440c0d299a6d2f to your computer and use it in GitHub Desktop.
Save evincarofautumn/bdcc83dbd8b35e482b440c0d299a6d2f to your computer and use it in GitHub Desktop.
Download ZIP
Concurrent Esolang Idea
Raw
concurrent-esolang.md

A minimal esoteric language in which execution semantically proceeds in lockstep with a fixed global clock on a “grid” of instructions.

Each grid cell may contain an instruction or an extension of an instruction (for multi-stream instructions), with an optional override slot that overrides the result of the instruction (if any). All streams are zero by default, and an instruction that produces no output semantically produces zero(s).

Each instruction has a consumption, the number of streams it consumes, and a production, the number of streams it produces; its width is the maximum of its consumption and production. It’s an error to schedule an instruction with the wrong width.

A stream is only 8 bits wide; if you want multi-byte data, you must spread it across multiple streams.

Grammar

A source language program consists of a series of ;-delimited rows (corresponding to cycles) of ,-delimited columns (corresponding to streams) of instructions and values. A value is semantically a no-op instruction with a value in the override slot, i.e., 1 is equivalent to ,1. Each row may be labelled. An instruction that spans multiple streams

  • {…} — comment
  • — no-op/identity
  • a; b — execute a at τ=n, b at τ=n+|a|
  • a, b — start executing a and b in parallel
  • a.b — instruction a with b in the override slot
  • 'c' — character c
  • "abc" — character sequence abc
  • 0, 123 — natural
  • +42, -5 — integer
  • 1/3, 3/5 — rational?
  • [a b c] — sequence of a, b, and c, scheduled adjacent and in parallel
  • (…) — load a sequence in series, by attaching it to the result slot of each instruction in sequence rather than in parallel
  • x: — extend multi-stream operation x rightward, aligning inputs & outputs to the left
  • :x — extend multi-stream operation x leftward, aligning inputs & outputs to the right

Notations:

  • |a| — the duration of a
    • |a; b| = |a| + |b|
    • |a, b| = max(|a|, |b|)
  • X@C:S = value X at cycle C on stream S

Examples

Outputting characters sequentially

'h'; putc;
'e'; putc;
'l'; putc;
'l'; putc;
'o'; putc;
' '; putc;
'w'; putc;
'o'; putc;
'r'; putc;
'l'; putc;
'd'; putc;
LF; putc

Each character is scheduled on stream 0 then output in the next cycle.

| 'h'  |
| putc |
| 'e'  |
| putc |
| 'l'  |
| putc |
| 'l'  |
| putc |
| 'o'  |
| putc |
| ' '  |
| putc |
| 'w'  |
| putc |
| 'o'  |
| putc |
| 'r'  |
| putc |
| 'l'  |
| putc |
| 'd'  |
| putc |
| LF   |
| putc |

Spreading characters in parallel, outputting sequentially

"hello world",LF;
putc,,,,,,,,,,,; # h
,putc,,,,,,,,,,; # e
,,putc,,,,,,,,,; # l
,,,putc,,,,,,,,; # l
,,,,putc,,,,,,,; # o
,,,,,putc,,,,,,; # SP
,,,,,,putc,,,,,; # w
,,,,,,,putc,,,,; # o
,,,,,,,,putc,,,; # r
,,,,,,,,,putc,,; # l
,,,,,,,,,,putc,; # d
,,,,,,,,,,,putc; # LF

The characters are all scheduled in parallel on streams 0–10, then each cycle issues a putc on the appropriate stream to output the character for that cycle.

| 'h'  | 'e'  | 'l'  | 'l'  | 'o'  | ' '  | 'w'  | 'o'  | 'r'  | 'l'  | 'd'  | LF   |
| putc | 'e'  | 'l'  | 'l'  | 'o'  | ' '  | 'w'  | 'o'  | 'r'  | 'l'  | 'd'  | LF   |
|      | putc | 'l'  | 'l'  | 'o'  | ' '  | 'w'  | 'o'  | 'r'  | 'l'  | 'd'  | LF   |
|      |      | putc | 'l'  | 'o'  | ' '  | 'w'  | 'o'  | 'r'  | 'l'  | 'd'  | LF   |
|      |      |      | putc | 'o'  | ' '  | 'w'  | 'o'  | 'r'  | 'l'  | 'd'  | LF   |
|      |      |      |      | putc | ' '  | 'w'  | 'o'  | 'r'  | 'l'  | 'd'  | LF   |
|      |      |      |      |      | putc | 'w'  | 'o'  | 'r'  | 'l'  | 'd'  | LF   |
|      |      |      |      |      |      | putc | 'o'  | 'r'  | 'l'  | 'd'  | LF   |
|      |      |      |      |      |      |      | putc | 'r'  | 'l'  | 'd'  | LF   |
|      |      |      |      |      |      |      |      | putc | 'l'  | 'd'  | LF   |
|      |      |      |      |      |      |      |      |      | putc | 'd'  | LF   |
|      |      |      |      |      |      |      |      |      |      | putc | LF   |
|      |      |      |      |      |      |      |      |      |      |      | putc |

This can be optimised using constant propagation for repeated characters.

"helo wrd",LF;
putc,,,,,,,,;
,putc,,,,,,,;
,,putc.'l',,,,,,;
,,putc.'l',,,,,,;
,,,putc,,,,,;
,,,,putc,,,,;
,,,,,putc,,,;
,,,,,,putc,,;
,,putc,,,,,,;
,,,,,,,putc,;
,,,,,,,,putc

| 'h'  | 'e'  | 'l'      | 'o'      | ' '  | 'w'  | 'r'  | 'd'  | LF   |
| putc | 'e'  | 'l'      | 'o'      | ' '  | 'w'  | 'r'  | 'd'  | LF   |
|      | putc | 'l'      | 'o'      | ' '  | 'w'  | 'r'  | 'd'  | LF   |
|      |      | putc.'l' | 'o'      | ' '  | 'w'  | 'r'  | 'd'  | LF   |
|      |      | putc.'l' | 'o'      | ' '  | 'w'  | 'r'  | 'd'  | LF   |
|      |      | 'l'      | putc.'o' | ' '  | 'w'  | 'r'  | 'd'  | LF   |
|      |      | 'l'      | 'o'      | putc | 'w'  | 'r'  | 'd'  | LF   |
|      |      | 'l'      | 'o'      |      | putc | 'r'  | 'd'  | LF   |
|      |      | 'l'      | putc     |      |      | 'r'  | 'd'  | LF   |
|      |      | 'l'      |          |      |      | putc | 'd'  | LF   |
|      |      | putc     |          |      |      |      | 'd'  | LF   |
|      |      |          |          |      |      |      | putc | LF   |
|      |      |          |          |      |      |      |      | putc |

And further optimised by reusing streams and delaying scheduling until a value is actually needed.

'h',,,;
putc,'e',,;
putc.'l',,,;
putc.'l',,'o';
,' ',putc.'o',;
,putc,,'w';
,,,putc;
,'r',putc,;
,putc,,;
putc,'d',,;
LF,putc,,;
putc,,,

| 'h'           |      |           |      |
| putc          | 'e'  |           |      |
| 'l'           | putc |           |      |
| putc; 'l'     |      |           |      |
| putc; 'l'     |      | 'o'       |      |
| 'l'           | ' '  | putc; 'o' |      |
| 'l'           | putc | 'o'       | 'w'  |
| 'l'           |      | 'o'       | putc |
| 'l'           | 'r'  | putc      |      |
| 'l'           | putc |           |      |
| putc          | 'd'  |           |      |
| LF            | putc |           |      |
| putc          |      |           |      |

But that doesn’t matter much for this particular program, because…

Sequentialising sequence

("hello world",LF);
putc;putc;putc;putc;putc;putc;putc;putc;putc;putc;putc;putc

Or equivalently:

'h';
putc.'e';
putc.'l';
putc.'l';
putc.'o';
putc.' ';
putc.'w';
putc.'o';
putc.'r';
putc.'l';
putc.'d';
putc

Each character of the sequence overwrites the result of the next instruction (which is null for putc) so it’s available for the following instruction. This cuts the schedule time down from 24 to 13 cycles.

| 'h'      |
| putc.'e' |
| putc.'l' |
| putc.'l' |
| putc.'o' |
| putc.' ' |
| putc.'w' |
| putc.'o' |
| putc.'r' |
| putc.'l' |
| putc.'d' |
| putc.LF  |
| putc     |

Dataflow

+ is an instruction that takes two inputs. +: means scheduling the add so it reads its inputs from streams n and n + 1, writing its result to stream n; :+ means reading from :n and :(n − 1) and writing to stream n. dup takes one input and produces two outputs, so dup: means reading from :n and writing to :n and :(n + 1); :dup means :(n − 1) and :n.

Using rightward streams as scratch:

32;
dup:;
+:;
putc

| 32   | | 32@0:0
| dup  : | 32@1:0, 32@1:1
| +    : | 64@2:0
| putc | | 0@3:0

Moving rightward:

32;
dup:;
:+;
,putc

| 32  |      | 32@0:0
| dup :      | 32@1:0, 32@1:1
|     : +    | 64@2:1
|     | putc | 0@3:1

Using leftward streams as scratch:

,32;
:dup;
:+;
,putc

| | 32   | 32@0:1
| : dup  | 32@1:0, 32@1:1
| : +    | 64@2:1
| | putc | 0@3:1

Moving leftward

,32;
:dup;
:+;
,putc

|      | 32  | 32@0:1
|      : dup | 32@1:0, 32@1:1
| +    :     | 64@2:0
| putc |     | null@3:0

Control Flow

Prints the letters A through Z in a loop.

'A',,;         { initial character on :0 }
[LOOP]
dup:,'Z';      { copy character to :1 }
,<=:(;END);    { compare to Z }
,jz:;          { jump to END if greater }
dup:,;         { copy character to :1 }
inc,putc,LOOP; { output :1 and increment :0 for next iteration }
,,jmp;         { jump to LOOP }
[END]
,,

Schedule with symbolic labels and values for first iteration of loop

      | 'A' |      |          | 65@0:0
LOOP: | dup :      | 'Z'      | 65@1:0, 65@1:1, 90@1:2
      |     | <=   : ; END(7) | 65@2:0, 1@2:1, 7@2:2
      |     | jz   :          | 65@3:0, 0@3:1, 7@3:2
      | dup :      |          | 65@4:0, 65@4:1, 7@4:2
      | inc | putc | LOOP(1)  | 66@5:0, 0@5:1, 1@5:2
      |     |      | jmp      |
END:  |     |      |          |
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment