Pattern format supporting recursive definitions

[wirehead]

Lua scripts can already support defining sub-patterns in terms of several sub-sub-patterns (and so on for more "sub"s) -- but the scripts haven't been written yet to analyze patterns and produce compact recursive definitions, and they wouldn't translate readily into LifeViewer format (though that might change, if someone wrote such a script!)

If you or someone else would be interested in doing that, I'd love to help. I know Python and Javascript.

This might be off topic so this post can be moved to the appropriate thread or a new one if it is,

[dvgrn]

If you or someone else would be interested in doing that, I'd love to help. I know Python and Javascript.

Okay, here's a possible starting point: have a look at recognizer.py, and maybe try using it to produce a level-one structured description of some recent piece of circuitry, like the glider-to-[weekender|doo-dah] converter. If the README isn't clear enough to help you get it working, let me know and I'll post some kind of walkthrough for it.

If the code is unreadable, feel free to rewrite it. What it does isn't all that complicated, and so it works pretty fast to "recognize" even a fairly large pattern and write out a compact script to re-create it -- once the library of component pieces has been defined.

Things that would be nice to be able to add:

1) XOR "patch" patterns -- when a subpattern is _almost_ the same as something in the library, it would be great to be able to generate a small patch showing the cells that are different between the standard library pattern and the (usually custom-welded) variant in the actual full pattern. The "standard object plus XOR patch" could then be recursively defined as a new named object, "syringe_plus_welded_eater" or whatever.

2) multi-level defined patterns in general. For example, in the existing glider-to-weekender defined pattern, the smallest defined units in the library are Herschel-based glider reflectors -- a syringe plus a Herschel conduit plus a H-to-G converter, let's say. But a recursive definition would allow the syringe, the Herschel conduit, and the H-to-G to be defined separately, and then the combination of the three could be called "180_degree_glider_reflector_1" or whatever -- with XOR patches holding the parts together whenever a weld is necessary. And then "syringe" itself could be defined as eater plus block plus beehive-with-tail plus syringe_catalyst.

(I suppose beehive-with-tail could then be defined as "beehive" plus "tail", but that might be taking things a little bit too far. We definitely don't want to get down as far as "block" = "cell" plus "cell" plus "cell" plus "cell".)

The Secret Ambition Behind All of This
As described way back in this post, there's a type of Life editor that would naturally use this kind of recursive definition as its input and output format, once the syntax is all figured out and in working order. The idea is to be able to select several smaller objects and click "group" to group them together and give them a name -- or select one larger-scale object and click "ungroup" to convert it into its next lower-level named objects.

Then we'd be able to do things like build different periods of guns just by click-and-dragging "trombone_slide_adjuster", and the adjuster component (made out of two attached Snarks, maybe) would never get out of alignment, because it would always snap to the nearest valid location.

Years ago Andrew Trevorrow added a mechanism that would allow this kind of editor to be added to Golly with no changes to Golly's code base -- in the form of a Lua "overlay" script. The learning curve for using the Lua overlay is apparently steep enough that few people have made the effort to figure it out and do wonderful things with it -- but wonderful things can obviously be done, as evidenced by Chris Rowett's breakout.lua and overlay-demo.lua.

[wirehead]

1) XOR "patch" patterns -- when a subpattern is _almost_ the same as something in the library, it would be great to be able to generate a small patch showing the cells that are different between the standard library pattern and the (usually custom-welded) variant in the actual full pattern. The "standard object plus XOR patch" could then be recursively defined as a new named object, "syringe_plus_welded_eater" or whatever.

It would take a while to write this, but I don't think that patch patterns would be necessary if an automatic welder script could be written. It could just be a simple "tweak and see what happens" algorithm until it gets something that fits, is still a (still life|oscillator|whatever), and serves its intended purpose (i.e. would not generate an eater that explodes when a glider hits it).

Years ago Andrew Trevorrow added a mechanism that would allow this kind of editor to be added to Golly with no changes to Golly's code base -- in the form of a Lua "overlay" script. The learning curve for using the Lua overlay is apparently steep enough that few people have made the effort to figure it out and do wonderful things with it -- but wonderful things can obviously be done, as evidenced by Chris Rowett's breakout.lua and overlay-demo.lua.

1) Why is there no Python overlay?

2) For me to really be able to help with this, I need to get a version of Golly that has Python3. See this post. The most of what I can help with right now is code style and formatting (PEP 20 compliance).

Also, MC files are already sort of this recursive pattern tree definition -- that is, if your patterns are meticulously aligned to power-of-two bounding boxes and coordinates. And also horrible to read if you're not a computer.

Now that I look at the generated script from this recognizer experiment, it seems to be exactly what I was thinking of over here -- just in a Python format.

[offtopic]In terms of having a comprehensive database of conduits and converters, LifeWiki would be a really great resource... except it's a mess to read if you're a computer. As with a lot of what I have been saying lately, it would be a HUGE undertaking, but if anything like this is going to exist, LifeWiki needs to be cleaned up so that there is a standard format in the infobox (i.e. a LifeSuper pattern which could convey what and where the inputs and outputs are by using marked off states.) The rest (repeat time, envelope, etc) the script could determine programatically by inserting an input and running it until the output shows up. This could also be combined with a classifier script to produce sensible names in the output file, such as "Fx77" instead of "A1".[/offtopic]

It wasn't my intention to get myself into this mess -- I am more of a Wireworld person -- but now that you've asked, I guess I can help. I digress.

[dvgrn]

1) Why is there no Python overlay?

Per Andrew Trevorrow, Lua is ultimately a better choice for a default scripting language for Golly than Python is -- because it's built-in. There aren't any additional download or installation requirements, no version issues like Python 2.x vs. 3.x or 32-bit vs. 64-bit, no "pip install X" dependency headaches.

That said, I can do a lot more with Python, a lot more quickly than I can in Lua -- so I almost always use Python, unless I'm really trying to build something to share that's maximally compatible with everyone's copy of Golly.

It wasn't my intention to get myself into this mess -- I am more of a Wireworld person -- but now that you've asked, I guess I can help. I digress.

Well, definitely don't let this little project ruin your life or anything, but it's definitely one of those things that everybody wishes that somebody would work on, but nobody ever actually does -- except sometimes Andrew Trevorrow and/or Chris Rowett do sneak another amazing feature into Golly and/or LifeViewer.

[erictom333]

I would like to propose two types of file.
The Life Pattern Dictionary or lpd file stores objects in apgcode format, along with names and other data. The syntax would be as follows:

Code: Select all

#categoryname
pattern;N=name;S=symmetery;P=period, velocity, etc;O=discoverer;D=date;C=comment

Example:

Code: Select all

#1
33;N=Block;S=*c*c;P=1;D=JHC;C=The most common still life
252;N=Tub
253;N=Boat
696;N=Beehive
#2
7;N=Blinker
7e;N=Toad
218c;N=Beacon
2a54;N=Clock

The purpose of lpd is to provide a better way to organise large dictionaries, which can be compiled into mcps or rle.

The Multiple Cluster Pattern Storage or mcps file stores recursive lists of objects. The stntax is as follows:

Code: Select all

Name=pattern
pattern or name,x(x offset),y(y offset),r(rotation),t(time offset)
"Text",x(x position),y(y position)

An example is as follows:

Code: Select all

Glider=247         #define "glider", facing N/NE by default
696,x-5,y-5,r2     #beehive at -5,-5 rotated 90° clockwise
Glider,x0,y0,r6,t2 #glider at origin, rotated 270° clockwise and advanced 2 generations
"Synthesis",x0,y-3 #label

The purpose of mcps is to provide a better way to store large or sparse patterns.

[hotdogPi]

Unfortunately, MCPS as an initialism is already in use: minimum covering polyplet size.

[wirehead]

The Multiple Cluster Pattern Storage or mcps file stores recursive lists of objects. The stntax is as follows:

Code: Select all

Name=pattern
pattern or name,x(x offset),y(y offset),r(rotation),t(time offset)
"Text",x(x position),y(y position)

I don't see where this is recursive. Also, how do you determine where one pattern starts and another stops? Is it simply "name=pattern" starts a new pattern and then it goes until the next "name=pattern"? And what does "pattern" stand-in for on the first line anyway?

EDIT: erictom333, I think you already proposed something similar to this here, but it's a little different. As-is, either of these two formats don't look really optimized for recursive large patterns, (i.e. APGcode vs. RLE). I think something that has brackets in it that can be nested (and would necessarily then be recursive) would probably be the way to go.

[pcallahan]

The Secret Ambition Behind All of This
As described way back in this post, there's a type of Life editor that would naturally use this kind of recursive definition as its input and output format, once the syntax is all figured out and in working order. The idea is to be able to select several smaller objects and click "group" to group them together and give them a name -- or select one larger-scale object and click "ungroup" to convert it into its next lower-level named objects.

Then we'd be able to do things like build different periods of guns just by click-and-dragging "trombone_slide_adjuster", and the adjuster component (made out of two attached Snarks, maybe) would never get out of alignment, because it would always snap to the nearest valid location.

I had a similar ambition when I started tweaking XLife (that was around 1994 and probably the first major thing I worked on connected to CGoL). XLife 3.0 even supported an include format #I, and I reverse engineered some patterns like the original giant breeder into structured patterns based on components. Note: it was not literally recursive in the sense of having cyclic definitions. I'm not sure if that's what you mean. To do that, I would have needed a way to express a base case. E.g., what is p30 stream of n gliders at (x, y)? If n=0, it's empty space. Otherwise it's a p30 stream of n-1 gliders generated 30 steps with a new glider at (x, y). I can see the utility but I had not intended to write a universal programming language, just a description format.

Dave Greene brought up #I format recently in this thread: viewtopic.php?f=7&t=3831&p=136816&hilit=xlife#p136813

Added: Here is what the breeder looked like in this format (unearthed from an old xlife distribution). It is a little hard to read, but #I specifies not only position and orientation but also a number of steps to generate the base pattern before doing the include. It is clunky but effective.

Code: Select all

## FOUND IN (breeder.life):
#I :breeder.startup -300 0 0 1 0



## FOUND IN (breeder.life):
#B breeder.startup
#I :breeder.flotilla -287 -280 0 1 0
#C gliders to fix up initial configuration
#I :ss.glider 256 76 2 -1 947
#I :ss.glider 252 -198 1 -1 946
#I :ss.glider 177 -120 2 1 947
#I :ss.glider 167 -4 2 -1 947
#E

## FOUND IN (breeder.life):
#B breeder.flotilla
#I :./breederrake.00 473 371 0 1 946
#I :./breederrake.10 428 336 0 1 714
#I :./breederrake.01 349 273 0 1 573
#I :./breederrake.00 368 286 0 1 105
#I :./breederrake.11 314 242 0 1 0
#I :./breederrake.11 312 201 0 -1 4
#I :./breederrake.10 359 158 0 -1 138
#I :./breederrake.10 406 137 0 -1 444
#I :./breederrake.10 426 107 0 -1 714
#I :./breederrake.00 472 71 0 -1 947
#E

## FOUND IN (./breederrake.life):
#B ./breederrake.11
#I :breederpuffer 71 37 0 1 0
#I :ss.s 75 14 0 1 18
#I :ss.m 60 6 0 1 18
#I :ss.m 60 -8 0 -1 18
#E

## FOUND IN (./breederpuffer.life):
#B breederpuffer
#I :gen.breeder 15 -45 0 1 0
#I :ss.l 16 -30 0 1 0
#I :ss.l 16 -46 0 -1 0
#I :ss.l 5 -54 0 1 0
#I :ss.l 5 -22 0 -1 0
#E

## FOUND IN (./gen.life):
#B gen.breeder
#P
..*.....
.*......
**...**.
*.*...**
.*...**.
.....*..
........
.....*..
.*...**.
*.*...**
**...**.
.*......
..*.....
#E

## FOUND IN (./ss.life):
#B ss.l
#P 0 -1
..**...
*....*.
......*
*.....*
.******
#E

## FOUND IN (./ss.life):
#B ss.s
#P
*..*.
....*
*...*
.****
#E

## FOUND IN (./ss.life):
#B ss.m
#P 0 -1
..*...
*...*.
.....*
*....*
.*****
#E

## FOUND IN (./breederrake.life):
#B ./breederrake.01
#I :./breederrake.11 0 0 0 1 0
#I :ss.m 0 -6 0 -1 18
#E

## FOUND IN (./breederrake.life):
#B ./breederrake.11
#I :breederpuffer 71 37 0 1 0
#I :ss.s 75 14 0 1 18
#I :ss.m 60 6 0 1 18
#I :ss.m 60 -8 0 -1 18
#E

## FOUND IN (./breederrake.life):
#B ./breederrake.10
#I :./breederrake.11 0 0 0 1 0
#I :ss.m 0 4 0 1 18
#E

## FOUND IN (./breederrake.life):
#B ./breederrake.00
#I :./breederrake.11 0 0 0 1 0
#I :ss.m 0 4 0 1 18
#I :ss.m 0 -6 0 -1 18
#E

## FOUND IN (ss.life):
#B ss.glider
#P 
.**
*.*
..*
#E