Should we create a domain-specific language for CA searches?

For scripts to aid with computation or simulation in cellular automata.
Post Reply
User avatar
blah
Posts: 302
Joined: April 9th, 2016, 7:22 pm

Should we create a domain-specific language for CA searches?

Post by blah » August 6th, 2021, 10:08 pm

I just watched a talk by Brian Kernighan about programming language design. The main takeaway from it for me was that the ideal time to create a new DSL (Domain Specific Language) is when you keep encountering problems that, intuitively, feel like they should be one line, but are not; which, I argue, occurs in this community regularly. For example, here are some problems I've personally solved, that feel like they should be one-liners:

Find x*y planes that are oscillators in rule r.
Find MAP rules where a single cell is a spaceship.
Find constellations of dots that reflect a spaceship 90 degrees without changing.
Simulate an explosive rule like /2/3 and list the spaceships that occur in the chaos. (debatable)

There's also the old problem of "simulate combinations of numerals and run a general census on them". Or "Collide this spaceship with this object in every possible way and do a general census on the results". Or "Test a bunch of soups and check for some property being exceptional, like lifespan being high or final population being 0".

Right now, we have half-solutions (most of which I admit I have no experience with) like Golly scripting, libraries like lifelib, or in some sense lls. But I don't think anyone's gone all the way and created a new language. If it is created, I think it will be followed by a sudden wave of discoveries that were technically possible before, but the scripts to find them were too tedious to implement; the DSL, however, would make them ~10 characters long. It would also cause people to think of problems that are easy to solve with the DSL that they otherwise wouldn't have thought of, further exacerbating the wave (maybe even being its main driver).

I don't know for sure if a CA search DSL would be a good idea in practice or if anyone would use it. But I feel compelled to make this post because I just can't shake the feeling that so many problems like the ones I've mentioned really should be one line. Don't you agree?

Any thoughts?
succ

User avatar
dvgrn
Moderator
Posts: 8288
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Should we create a domain-specific language for CA searches?

Post by dvgrn » August 7th, 2021, 8:56 am

blah wrote:
August 6th, 2021, 10:08 pm
I don't know for sure if a CA search DSL would be a good idea in practice or if anyone would use it. But I feel compelled to make this post because I just can't shake the feeling that so many problems like the ones I've mentioned really should be one line. Don't you agree?

Any thoughts?
My immediate thought is that it may not be as useful as it appears, to be able to state a problem in one line. All of the problems mentioned above were stated in one line (in English). The big problem with many of these kinds of problems is not so much that they can't be turned into runnable code. Often the real problem is getting a good estimate of the amount of CPU time or memory resources needed to complete the work -- and in many cases the estimate turns out to be "sometime after the Sun expands as far as Earth's orbit".

I don't want to discourage the idea of a DSL for CA problems. Paul Chapman spent quite a bit of time trying to develop something along those lines back in the early 2000's -- that was an early and much more ambitious version of the "Glue" project. If it can be done in a way that allows searches to be run and time/resource estimates to be generated in the process, then it will definitely be very useful.

The closest thing available at the moment might be Mathematica (Wolfram Language), which I think can already handle quite a few of the above problems in one line or a few lines. Can anyone who is more familiar with Mathematica chime in on what its abilities and limitations might be in this context? Might it be relatively easy to write functions to extend Mathematica's abilities to include common tasks like censusing?

pzq_alex
Posts: 105
Joined: May 1st, 2021, 9:00 pm
Location: in the life universe

Re: Should we create a domain-specific language for CA searches?

Post by pzq_alex » August 7th, 2021, 11:15 am

dvgrn wrote:
August 7th, 2021, 8:56 am
...
The closest thing available at the moment might be Mathematica (Wolfram Language), which I think can already handle quite a few of the above problems in one line or a few lines. Can anyone who is more familiar with Mathematica chime in on what its abilities and limitations might be in this context? Might it be relatively easy to write functions to extend Mathematica's abilities to include common tasks like censusing?
On one side, there's AlephAlpha's LifeFind package:
https://github.com/AlephAlpha/LifeFind
There does not seem to be any other GoL-(or CA-)related pieces of WL (that I know of).
As for censusing, we should probably dig up the code in apgluxe for censusing. I'm pretty sure that it can be turned into a few* lines of WL.
* for some measurement of "few"

User avatar
blah
Posts: 302
Joined: April 9th, 2016, 7:22 pm

Re: Should we create a domain-specific language for CA searches?

Post by blah » August 9th, 2021, 6:45 pm

dvgrn wrote:
August 7th, 2021, 8:56 am
The big problem with many of these kinds of problems is not so much that they can't be turned into runnable code. Often the real problem is getting a good estimate of the amount of CPU time or memory resources needed to complete the work -- and in many cases the estimate turns out to be "sometime after the Sun expands as far as Earth's orbit". [...] If it can be done in a way that allows searches to be run and time/resource estimates to be generated in the process, then it will definitely be very useful.
I'm not sure why producing time estimates would be that important. I never had automatically generated time estimates when I solved the problems I mentioned above. If you don't know whether a problem is tractable to brute force or not, then the amount of effort it takes to write a Golly script might compel you to not even bother, since you don't know if it'll work anyway. If that burden of effort is reduced, though, and you only need to write a few lines, you're much more likely to try it, and thus more likely to discover something you otherwise wouldn't have.

Also, you mentioned memory, which to me implies something like gfind. But in my opinion, if you want to invoke a gfind-style algorithm, you should just run gfind (or something like it).

Here's a demo of what I'm imagining:

Code: Select all

--[[ grammar:
program = iterator '|' selector
iterator = statement*
statement = number 'x' number
statement = '(' number ',' number ')'
statement = 'o'
selector = criterion*
criterion = 'pop' {'>'|'='} number
]]
local g=golly()
local program = g.getstring("Enter your CADSL program.\n"..
"NOTE THAT THIS IS A PROOF OF CONCEPT; NOTHING IS FINAL.")

----------------------------------------------------------------------- ITERATOR
-- All the code in this section deals with candidate pattern generation.

function resetCursor()
	cursorX, cursorY = 0, 0
end

function newPattern()
	resetCursor()
	g.new("")
end

-- STATEMENTS:
function soup(x, y)
	g.select{cursorX, cursorY, x, y}
	g.randfill(50)
	cursorX = cursorX + math.floor(x)
end
function go(x, y)
	cursorX = x
	cursorY = y
end
function dot()
	g.setcell(cursorX, cursorY, 1)
	cursorX = cursorX + 1
end

function doStatement(s)
	-- figure out which kind of statement it is and run it
	local _, _, num1, num2 = s:find("^(%d+)x(%d+)$")
	if _ then soup(num1, num2) end
	_, _, num1, num2 = s:find("^%((%-?%d+),(%-?%d+)%)$")
	if _ then go(num1, num2) end
	if s == "o" then dot() end
end

function doIterator(s)
	for statement in s:gmatch("[^ \t\n;]+") do
		doStatement(statement)
	end
end

----------------------------------------------------------------------- SELECTOR
-- All the code in this section deals with detecting valid results.

function doCriterion(s)
	s = s:gsub("pop",g.getpop())
	local _, _, arg1, comparison, arg2 = s:find("(%w+)([>=])(%w+)")
	arg1 = tonumber(arg1)
	arg2 = tonumber(arg2)
	if comparison == ">" then
		return arg1 > arg2
	elseif comparison == "=" then
		return arg1 == arg2
	end
end

function doSelector(s)
	local shouldShow = true
	for criterion in s:gmatch("[^ \t\n&]+") do
		shouldShow = shouldShow and doCriterion(criterion)
	end
	return shouldShow
end

--------------------------------------------------------------------------------

pipe = program:find("|")
iterator = program:sub(1, pipe - 1)
selector = program:sub(pipe + 1)
-- main loop
i = 0
while true do
	i = i + 1
	newPattern()
	doIterator(iterator:gsub("i",i))
	g.select(g.getrect()) g.copy()
	g.run(1000)
	if doSelector(selector) then
		g.new("") g.paste(0,0,"copy")
		g.warn("Result found! :D ("..i.." tested)")
	end
end
It's like a reverse awk; the program is broken into two halves: The "iterator", which generates patterns, and the "selector", which filters out everything which isn't wanted. In this limited demo, the iterator can include these commands, separated by spaces, with no spaces within them:
(width)x(height): Generate soup rectangle.
((number),(number)): Move cursor to specified coordinates.
o: Draw dot.
The character "i" is replaced with a number that's incremented each time the program is run. The selector can consist of "=" or ">" tests (but not "<"). The only variable that exists is "pop" (and I guess "i"), which is the population after 1000 steps.
Example programs:
"10x10 | pop=0" finds 10x10 diehards.
"o o (1,1) o o (1,2) o (4,i) o o o |" creates combinations of rpents and blinkers. (See where I'm going with this? I think a fleshed out version of this functionality could solve the 3rd of the 4 problems I mentioned in my last post, about reflecting spaceships.)
"4x4 | pop=55" finds pi predecessors.

Here's a soup found with "4x4 (-16,-16) 4x4 | pop>100 200>pop":

Code: Select all

x = 20, y = 20, rule = B3/S23
3o$o$2b2o$2bo13$16b3o$16b2obo$17b3o$16bo2bo!
A diehard found with "16x16 | pop=0":

Code: Select all

x = 16, y = 16, rule = B3/S23
2b2obo4b2o2bo$o2bo2bo5bob2o$3o2b2ob2ob5o$6b2obobo2bo$2bob4o2bo3bo$4bo
3bobob3o$2bo2bobo2b3obo$bo2b2o3bo2bob2o$2bo3bobo2b2o2bo$ob2o3bob4obo$b
obo2bo2bo2b4o$5o3bo2bo3bo$2b2ob3o2b4obo$5o4bobob3o$4b2o3b2o$o4bob3ob2o
!
My program is a little under a hundred lines long. My fantasy is to have something more like ten thousand lines; the iterator would allow imperative constructs like if/for/while blocks, functions, variables, etc. One example problem I want it to be able to solve is enumerating polyominoes, for example.

I have other things I'd rather work on, so I'll leave the script as it is. If anyone wants to add to the script, especially the selector part, please do so and post it here.
succ

Yoel
Posts: 240
Joined: July 2nd, 2020, 1:02 am
Location: Electronic jungle
Contact:

Re: Should we create a domain-specific language for CA searches?

Post by Yoel » August 11th, 2021, 2:20 am

dvgrn wrote:
August 7th, 2021, 8:56 am
The closest thing available at the moment might be Mathematica (Wolfram Language), which I think can already handle quite a few of the above problems in one line or a few lines. Can anyone who is more familiar with Mathematica chime in on what its abilities and limitations might be in this context? Might it be relatively easy to write functions to extend Mathematica's abilities to include common tasks like censusing?
I would say Common Lisp or, perhaps, any modern Lisp with extensive libraries like Clojure, or even Hy (Python+Lisp hybrid; although it's still beta, it naturally embeds any Python library/toolkit). Traditionally, Lisp is #1 language for DSLs. The Wolfram Language is basically a Lisp with a different syntax. The same things that can be done in Mathematica can usually be done in Maxima, which is an advanced DSL and a set of libraries for symbolic algebra, a free equivalent of Mathematica, build on top of Common Lisp. Also, in my experience, any decent Lisp that compiles into native code, like SBCL, ECL, GCL or CCL, runs way faster than Mathematica and eats much less memory while multiplying 3D matrices, for example. I don't know anything about memory optimization in Mathematica though.

Although, I am aware that many people hate Lisp for its syntax...

EDIT:

There are a couple of utilities that supposedly allow to easily integrate Common Lisp with Python:

https://github.com/marcoheisig/cl4py

https://github.com/bendudson/py4cl

I never tried them yet, but I an planning, whenever I have spare time, to write some code that would run Golly, lifelib, apgsearch and maybe some other programs transparently inside Lisp. C/Lisp integration is not a problem; all major Lisps have built-in support for that.

Regarding Mathematica, I personally stay away from proprietary software and I'm sure some people on this forum do the same. There are several free/open source implementations of WL, but they all seem to be incomplete or not entirely compatible with the original one. IMHO, WL/Mathematica is a very specific environment not suitable for everyone.

EDIT2:

Py4cl seems to work well, albeit slow, with some minor bugs and dependency problems that may require manual code tweaking. It should not be used for switching, say, every millisecond between Lisp and Python, but it should be possible to control and analyze lifelib results etc. by a Lisp-based DSL. I'll post here, If I come up with something generally useful.

pzq_alex
Posts: 105
Joined: May 1st, 2021, 9:00 pm
Location: in the life universe

Re: Should we create a domain-specific language for CA searches?

Post by pzq_alex » September 15th, 2021, 4:01 am

Yoel wrote:
August 11th, 2021, 2:20 am
Regarding Mathematica, I personally stay away from proprietary software and I'm sure some people on this forum do the same. There are several free/open source implementations of WL, but they all seem to be incomplete or not entirely compatible with the original one. IMHO, WL/Mathematica is a very specific environment not suitable for everyone.
Mathematica itself is not free software, but the Wolfram Engine is, and basically it is a command-line GUI-free version equivalent to Mathematica.

tl;dr: Mathematica is free software.

Yoel
Posts: 240
Joined: July 2nd, 2020, 1:02 am
Location: Electronic jungle
Contact:

Re: Should we create a domain-specific language for CA searches?

Post by Yoel » September 15th, 2021, 6:17 am

pzq_alex wrote:
September 15th, 2021, 4:01 am
Yoel wrote:
August 11th, 2021, 2:20 am
Regarding Mathematica, I personally stay away from proprietary software and I'm sure some people on this forum do the same. There are several free/open source implementations of WL, but they all seem to be incomplete or not entirely compatible with the original one. IMHO, WL/Mathematica is a very specific environment not suitable for everyone.
Mathematica itself is not free software, but the Wolfram Engine is, and basically it is a command-line GUI-free version equivalent to Mathematica.

tl;dr: Mathematica is free software.
None of these products are free software in the sense how the free software community uses this term. Proprietary, not open source, restrictively licensed. Even the so-called "free" developer version of the Wolfram Engine has a somewhat restrictive license:

https://www.wolfram.com/engine/faq/

And Mathematica is freely available (not free as GNU products, of course) only on Paspberry Pi. Maybe on other toy computers that I am not aware of, but not on any real-life workstation.

Now, let's try to actually install it.

They don't even offer Linux packages, just one insanely long shell script, which contains the actual code and self-extracts it. 1 gig long .sh file, unheard of! For whatever reason it requires root. Ok, let's play Russian roulette...
WARNING: Wolfram Engine is protected by copyright law and international treaties. Unauthorized reproduction or distribution may result in severe civil and criminal penalties and will be prosecuted to the maximum extent possible under law.
Oh, that sounds very much like free software!
Audit
----------------------------------------

You will maintain accurate records of Your use of the Free Engine sufficient to show compliance with these Terms and Conditions, and WRI will have the right to audit such records to confirm compliance therewith. Upon written notice of an audit from WRI, You shall respond within ten (10) business days.
This Engine was created, and is maintained, in the State of Illinois, United States of America. WRI makes no claims that the materials contained on the Free Engine are appropriate or may be downloaded outside of the United States. Access to the Engine and the materials therein (including software) may not be legal by certain persons or in certain countries. If You access this Free Engine from outside the United States, that access is made at Your own risk. You are responsible for compliance with the laws of Your jurisdiction.
WTF!!!
You will need a valid activation key and password in order
to proceed. Go to http://user.wolfram.com to
register your activation key and obtain the password.
An epitome of non-free software! Deleted this thing and don't want to see it again! :evil:

Post Reply