search

pjt33 / Alchemist.Py

Python interpreter for the Alchemist esolang
4 stars 0 forks source link

Rule repetition prevents some non-determinism #1

Open GrayJoKing opened 5 years ago

GrayJoKing commented 5 years ago

Take the program

_->10a+c
a+c->c
c->Out_a

This should randomly remove some a atoms before printing the number of a atoms and terminating. However, with your optimisations, it repeats the a+c->c rule either 0 or as many times as it can before any other rule, meaning it only outputs 10 or 0.

pjt33 commented 5 years ago

That's a nice example, although I think I would strengthen it by changing the first rule to

_ -> In_a + c

However, this particular problem is easy to fix: replace the second rule with

a + c -> d
d -> c

I think it's probably the case that most "real" programs (i.e. ones written to accomplish a task other than "Find an edge case which is hard to solve") have similarly simple fixes, so that it's possible to write defensively and avoid the issue. My current thinking is that if I (or someone else) can demonstrate robust ways of generating random numbers following certain basic distributions (uniform, binomial, exponential) then I will consider the effect of this optimisation on non-determinism a non-issue.

GrayJoKing commented 5 years ago

The repetition also doesn't handle the 0-rule correctly.

Take the code

_->In_a+c
a+0f->f+d
d+c->Out_f

This should always output 1, but it outputs the input instead. I assume you're not checking if a 0-rule atom on the LHS is present on the RHS.

My opinion is that the default behaviour of the interpreter should match the specs, regardless of what program is executed. Perhaps you should move the optimisations to an optional flag?

pjt33 commented 5 years ago

That's definitely a bug. Thanks for pointing it out.

The specs aren't very prescriptive on the probability distribution which will be used in the non-deterministic choices, and they're less prescriptive on the string syntax than they used to be following a discussion I had with bforte on the esolangs wiki. My feeling is that the optimisations are necessary for the programming model to be practical, because otherwise manipulating massive numbers with only increments and decrements restricts you to toy examples. But I could consider a flag to toggle on a more conservative mode.