User:Salpynx/Sator Resatus
Sator Resatus is an attempt at creating a 2D string rewriting language by User:Salpynx
It is inspired by graph-rewriting languages and L-systems, but aims to take advantage of the relative ease of following 1D rewriting of strings by extending data field on to a regular 2D grid. Hopefully it results in something computationally equivalent to both string and graph rewriting paradigms.
Sator Resatus = Latin "Sower Resown", a combined reference to Thomas Carlyle's satirical novel Sartor Resartus, and the ancient SATOR/ROTAS word-square.
Terminology
A planting, or sowing, una satio is a collection of seeds. A seed is a planting.
Seed / a sowing (satio): the basic symbolic unit of Sator Resatus. A single character is a seed. A string is a linear sequence of characters (a 1D graph), and is also a seed. Extending this further, a fully connected matrix of seeds, an n*m king's graph, is also a seed. Any connected non-empty result of a sub-seed pattern → seed replacement is likewise also a seed (unless it is the empty string). Unconnected results are multiple distinct seeds. The empty string ε is NOT a seed.
A seed is a labelled graph containing one or more connected nodes. Labels of seeds are themselves seeds. i.e. a seed label can be a single 'character', a 'string', or a more complex labelled graph.
Seeds have a relative position and scale within the bounds of the field they occupy. Replacements of sub-seed groupings retain the basic geometry of the previous field. Scales, positions, and edge connections are adjusted accordingly for each new seed. Based on their initial positions seeds are connected to their neighbours in the form of a tightly connected king's graph. The edge connections need to be tracked as they too are deformed, potentially cut, and replaced with more or less connections every production application. Edge connections are not necessarily to be visualised on output, but are strictly necessary when matching production patterns as graphs. The source format only allows seeds to be specified in regular rectangular grids (connected in a king's graph), but substitutions can deform the seeds out of a regular grid. Since seeds are matched as graphs, the angles of the edges are not important, even though the position of each seed is fixed. Whitespace within the bounds of a grid prevents connections with and across that space. The exact unambiguous operation of this mechanism is still being worked out -- for the moment the operation is mostly intuitive, and there are still some issues to be ironed out.
granum (n) (pl. grana) => a 'grain', a planting or seed that is an atomic unit not further divisible into other seeds. (In practice this is a character label, although characters could be further divided into bit-grana. If so, 'S' would match 'e', as the undirected bit-graphs of each are identical.)
Normally there will only be one start state, but since it is possible for seeds to become completely disconnected using whitespace, and for non-connected nested substitutions to occur inside seed labels, there is no reason a program can't start with unconnected seeds. What this signifies is open to interpretation. It is equivalent to running multiple programs independently. It may be possible to join previously unconnected seeds if whitespace is permitted in production patterns.
Syntax
The starting state is indicated with the Oscan letter ∃, for EZUM (the Oscan verb "to be": ∃𐌌𐌖𐌆). Unfortunately an exact code point for this letter form does not exist in the Unicode Old Italic block, so the mathematical symbol "there exists" ∃ is used instead.
Productions (Opera): <seed1> → <seed2> (seed1 = pattern, seed2 = replacement) Productions are matched as undirected, but labelled graphs. Direction of match is not important, although direction is to be used when determining the order of matches, and relative direction of the replacement is maintained. The Hello World examples below should illustrate this. Fields are oriented with 'up' on the page representing East. Node matching is then evaluated sunwise, starting from the NE corner. This is a general principle in case of ambiguity in match order.
Conditional production: <seed1> → <seed> → <seed> (if first sub-seed found, perform the replacement seed2 → seed3 )
Prompt for user input: ⌘
Halt execution, preserve output: ∎ Halmos / tombstone U+220E
Line separator: ;
1D label grouping: []
2D label grouping: ⌈ ⌉ ⌊ ⌋ RIGHT/LEFT CEILING/FLOOR square brackets.
All whitespace is ignored unless it appears with the significant bounds of a square bracket label grouping. All Sator Resatus code should be unambiguously foldable from 2D layouts with lots of whitespace, to a 1D stream.
Examples
Hello World
∃ABCD DC→!dlroW AB→[Hello, ]
and vertically:
∃⌈A⌉ B C ⌊D⌋ DC→!dlroW AB→[Hello, ]
SATOR square
∃⌈AB⌉ ⌊BA⌋ AB→SATOR RR→RNR RN→RPN TN→TEN SNS→SRNRS∎
Equivalent in one line:
∃⌈AB⌉⌊BA⌋;AB→SATOR;RR→RNR;RN→RPN;TN→TEN;SNS→SRNRS∎
Hopefully this terminates cleanly and does not leave different sized characters scattered between letters. It was designed as a test to identify problems with implementations and/or the spec.
Sierpiński triangle
∃A A→⌈ A ⌉ ⌊A A⌋
In one line: ∃A;A→⌈ A ⌉⌊A A⌋. This code does not terminate.
Higher dimensions
Exploring the possibility that this language does not need to be modified to create higher dimensional objects but can already do so with the repeated application of 2D nxm productions:
3-cube graph
∃⌈ aa ⌉ a Ea H A a a D B a a C F aG a ⌊ aa ⌋ GaaaF→GF GaaaH→GH HaaaE→HE EaaaF→EF
4-cube / tesseract / 4-Hadamard graph Open challenge. It feels like this should be possible. It involves some non-joined crossing edges, but these are possible, and occur in the Sator square example above. The challenge seems to be to form the symmetrical layout in a controlled manner, and halt at the correct point. A 4-cube graph should be easily transformable with simple productions into a 3x3x3 tightly connected mesh, similar to a king's graph but in 3D. If constructing one of these is possible, the other should be too (needs verification!). Whether it is possible, and can be extended to any nxnxn graph and any n-cube is an interesting and open question.
A mechanism to use repeated application of 2D productions to construct graphs which can then be used as more complex patterns for replacements could assist with working with higher dimensional seeds.
Possible solution:
∃⌈ aa ⌉ a Ea H A aa D B aa C F aG a ⌊ aa ⌋ EaaaF→EF;FaaaG→FG;GaaaH→GH;HaaaE→HE // above is the 3-cube skeleton ABCDEFGH // likely bug: following productions are not protected from repeatedly triggering. // They should only trigger once each to form the desired tesseract skeleton. // enclose EFGH in IJKL: ⌈ E ⌉H F⌊ G ⌋ → ⌈ aa ⌉ a Ia L E aa H F aa G J aK a ⌊ aa ⌋ IaaaJ→IJ;JaaaK→JK;KaaaL→KL;LaaaI→LI // enclose IJKL in MNOP: ⌈ I ⌉L J⌊ K ⌋ → ⌈ aa ⌉ a Ma P I aa L J aa K N aO a ⌊ aa ⌋ MaaaN→MN;NaaaO→NO;OaaaP→OP;PaaaM→PM // Join innermost (ABCD) and outermost (MNOP) corners: AEIM→⌈ EI ⌉A M⌊ bb ⌋ BFJN→⌈ FJ ⌉B N⌊ bb ⌋ CGKO→⌈ GK ⌉C O⌊ bb ⌋ DHLP→⌈ HL ⌉D P⌊ bb ⌋ // tighten the loops AbbM→AM;BbbN→BN;CbbO→CO;DbbP→DP∎
Cellular automata
Anything claiming to be a 2D string-rewriting system should be able to relatively directly implement any 2D cellular automaton.
Rule 110, 90 et al. The challenge for this language is restricting growth to the correct edge of the field, and ensuring productions are applied in the correct order, and direction.
Rule 110 for example has two rules that map to the same undirected pattern, but have different replacements.
110→⌈110⌉⌊ 1 ⌋ and 011→⌈011⌉⌊ 0 ⌋, which could trigger from the same state. The order of the production rules and 'sunwise' application of productions with respect to the field direction should be able to deal with this, but needs testing. Restricting growth to the correct edge will require other techniques.
Conway's game of life Ideally this too should be implementable relatively directly with 2D production rules. Creating the initial playing field may be a challenge; Fixed field, or expanding? Does the spec need to provide a shorthand way of creating large but finite tilings?
Computational class
Sator Resatus limited to one dimension should be pretty clearly a trivial clone of Thue or ///, and therefore is Turing complete. Specific programs from those languages may not run as expected without some modification since Sator Resatus can potentially match and apply strings from productions in reverse, although the forwards direction will be matched first.
The Waterfall Model
Rough sketch towards compiling a random The Waterfall Model program into Sator Resatus.
The 0 seed could possibly be the same for each clock, and the whole system could be one connected seed, but that would involve more complex setup, and does not seem necessary.
// Init three clocks: ∃0oooooooooooooo1 ∃0oooooooo2 ∃0ooooooooooooooooooooo3 // Conditional productions for the trigger actions: 01→3o→3oooooo 01→2o→2ooooooooooooo 02→20→2ooooo0 03→1o→1ooooooooo 03→2o→2oo 03→30→3oooo0 // Drain water: 0o→0
Completely false etymology of "Halmos" ∎
"Halmos" (Latinized Halmus or Almus), Greek. A mythological figure, whose name is given to the Boeotian village of Almones, whose inhabitants practised complex agricultural planting rituals that were incomprehensible to anyone from outside that region (source: Pausanias 9.24.3 and 9.34.10). See also: ἅλμη 'Halme' - salt water , to salt the fields and prevent further growth. Also used to preserve (with brine).