Should we have built-in support for conditional productions, stochastic productions? about lindenmayer HOT 16 CLOSED

EDIT: I have edited of my answer quite a bit. So please read again if you have done before 😃

Hi @TMiguelT,
Thanks!

Just for the record, As you have defined only one production, your example above could already be written as:

lsys.setProduction('F', () => { if (Math.random() <= 0.3 && time > 3) return 'F-F++F-F'})

But I see your point about providing better readability for the common use case you mentioned (probability and some condition which is common in ABOP examples).

I have been thinking about this for a while before. Let me explain my hesitation to implement it like you proposed:

In ABOP all productions are set together in beginning, with a fixed order. So you have eg. 3 productions: first one with 25% probability, second also 25% and the third with 50%.

First interpretation of probability:
I have to check again, but afaik that means in ABOPs context that one of the three productions is guaranteed to succeed, like rolling a three sided dice only once, where one side is guaranteed to be rolled.

Second interpretation of probability:
An alternative interpretation would be that the chance for each production is independent of the others; so that its not like a dice that is rolled once, but a different dice rolled for each production. In that case, it is not always guaranteed that one of the three productions has the chance to produce.

The second one would be unproblematic to implement, because it would not be necessary to know the probabilities of the other productions.

Keeping in mind that I am not 100% sure wether the first or the second way of dealing with probability is used in ABOP, the issues that would arise when introducing a chance option in the form of the first implemenation:

• If we would adapt the chance option, what do we do if percentages are not exactly 100% (or less) but more, because of users miscalculations. Do we Just cap the last productions probability, so that all productions don't go over 10? This is probably less serious as we could have a console warning.
• But the more difficult thing in my opinion: What happens when we want to add more productions later on? We'd have to either set all previous productions again and calculate our probability percentages to match eg. 4 or 5 productions. Otherwise, as our 3 example productions already reach 100% total probability the additionally added productions would never have a chance to be executed because of order of execution from top to bottom.

Conclusion: This approach would work when you don't modify productions after setting them in the beginning. Or when all probabilities are equal, so adding more production would automatically change the probabilites of the others. However that would defeat the purpose of the chance option and is already partly implemented via #9.

Sorry for this rather long text, but hopefully I meed my point clear enough :)

The probability notation makes sense in the formal definition of ABOP, but I don't think it is that practical in the library if we are talking about the
However, as I would really like to have more readability and adaptability to ABOP examples I am open to suggestions!

I am also going to re-read again how probability is exactly handled in ABOP.

from lindenmayer.

Ok, I skimmed the stochastic LSystem section of ABOP quickly again. It seems I remembered correctly; the first implementation appears to be the way Lindenmayer/Prusinkiewicz use in ABOP.

I suppose, What we could do is to is introduce the option as part of the classic/ABOP syntax package which I have already added to some degree (context sensitivity with < and >) and simply make it clear that when using chance, you should be careful when using setProduction or setProductions on initiators that have productions modified by chance/probability. And emit a warning/error when probability is over 100%.

This would make it possible to recreate many ABOP examples for those that don't want to mess too much with productions after setting them once :)

I may find some time this WE to actually tackle this one and also improve documentation a bit further.

from lindenmayer.

I think you're correct in the first interpretation. The way I'd implement this is with production 'groups' that have a number of productions with weights. It sounds like you've started doing something like this over in #9, but I think adding weights to each production is a nice simple way of setting a chance for each production without forcing the user to add them to 100%. For example:

let lsystem = new LSystem({
      axiom: 'ABC',
      productions: {
        'A': 'A+',
        'B': [
             {weight: 3, succ: 'AB'}, // 60%
             {weight: 2, succ: 'BA'} // 40%
        ],
        'C': 'ABC'
      }
})

from lindenmayer.

I realise you're trying to make the ABOP notation easy to write literally in JS, but I admit I prefer a more JavaScripty API. For example, I especially like how you've implemented parametric systems (using production objects, rather than trying to parse strings like A(j) as a parametric production), because they're very JavaScripty and intuitive, even if you haven't read papers on L-Systems.

Consequently my ideal API would have production as an object with a succ (successor string or function), condition (function), left_context (string), right_context (string) etc. Rather than using strings for everything.

from lindenmayer.

I like your idea using weights. Will think about how that could be implemented including other often used operations like context checks in a objecty way as you suggest. I still want it to be pretty flexible though.
So for people who want to do basic L-Systems using only strings, it should still work in a clutterless way. Or if users want to only define functions or other objects for every production it should work as it already does.

Talking with myself how it could be done: What about in setProduction, check if production is an object or list (done already), then also check for objects whether keywords like successor or leftContext are included and for lists if multiple objects with weight are inside; Then: construct functions that perform as expected (as it is already done when transforming classic context sensitive syntax to functions).

from lindenmayer.

With my ideal API you'd allow almost everything to be an object (how I'd probably use it) or a string (the classic ABOP way), or some other things.

With this API, everywhere you have a predecessor (left hand side), it can be:

• An object, which would have {symbol, left_ctx, right_ctx} values
• A string, in which case you interpret in the classical way, meaning it can have a symbol and optionally a left and right context. This will be parsed into the same object structure as above, so you can always treat the predecessor as an object.

Everywhere you have a successor, it can be:

• A string, in which case it's a simple conversion e.g. F->FF
• A function, in which case they can use parameters on the predecessor
• An object, which would have the keys {chance (number), condition (function), successor (function or string), weight}
• An array of objects as above

So you'd check which type the successor is, and then:

• If it's a string, you make that into an object with just the successor key, and then put that in an array by itself (return [{successor: x, weight: 1}]
• If it's a function, you do the same (return [{successor: x, weight: 1}])
• If it's an object you put that in an array with a weight of 1 (return [Object.assign({weight: 1}, x)])
• If it's an array, you just use the value they gave (return x).

This way, you can always treat the successors as an array of objects, which saves you having to switch case everywhere, except on the successor key which can always be a string or a function.

This way, your code should be pretty straight forward since no matter what the user does you can write your code for one data structure. Also, if you provide user documentation showing the options they have like I've done above, it should be pretty clear how to use your module.

from lindenmayer.

I generally like your suggestions so far but I see a few problems we'd have to tackle or take into consideration.

1. simplicity

If it's a function, you do the same (return [{successor: x, weight: 1}])

This is fine if the user wants to use/return objects anyways. But I really love the simplicity of something like the following when using ES6 arrow functions:

// This:
setProduction('F', () => (time > 2) ? 'FF' : 'F-')

// would have to become this, even though the user doesnt want to use objects and only use functions for dynamic conditions. according to your suggestion this would become:
setProduction('F', () => {
    return { successor: (time > 2) ? 'FF' : 'F-', weight: 1 }
})

I don't want to sacrifice the ability to do it the first way. Therefore I propose that Strings should remain to always be allowed as a functions result. To be able to, we'd check wether a result is an object or a string before appending it to the successor axiom/word. If it is indeed a string we could transform it to a normalized object in the form of is result a string then return {sucessor: result, weight: 1} otherwise return result. This would certainly sacrifice processing power, but we could do some benchmarks to see the actual impact.

2. Limits of JSON / defining productions in the constructor
Currently you can set productions like:

let lsystem = new LSystem({
    productions: {
        'F': [{symbol: 'F'}, {symbol: 'F'}],
        'C': {symbol: 'G'}
    }
})

We use an JSON-object to define productions, which gets parsed into a Map for easy and fast production retrieval. However JSON-objects don't allow objects to be used as keys, only strings are allowed on the left side.
What you propose, having objects on the left side, would not work for the above way, because:

let lsystem = new LSystem({
    productions: {
                /* error, invalid JSON object: */
        {predecessor: 'F'}: {successor: [{symbol: 'F'}, {symbol: 'F'}]},
        {predecessor: 'C'}: {sucessor: {symbol: 'G'}}
    }
})

would already throw errors because you'd try to use objects for keys in the object (left side).
Which means that we'd have to use either the existing function (setProduction) or change it to be an array with tuples/two-value-arrays, instead of an object with key:values.

let lsystem = new LSystem({
    productions: [
        [ {predecessor: 'F'}, {successor: [{symbol: 'F'}, {symbol: 'F'}]} ],
        [ {predecessor: 'C'}, {successor: {symbol: 'G'}} ]
    ]
})

The above would work, but is certainly a bit less concise than it used to be.

3. memory
Treating each symbol as an individual object uses certainly more memory than using pure strings. Surely this would already be a problem when not using basic strings and doing parametric stuff. But it would add more overhead for simple situations when you want to only use strings to begin with. A benchmark to see the actual memory and performance impact in string-only-situations may be useful here.

4. Conclusion
After thinking about the above points I suggest the following modifications to your proposal:

I see that you want to keep leftCtx and rightCtx on the left side similiar to ABOPs definition (A<B>C -> A+A).
What do you think about keeping a single String on the left side as it is now and defining all contexts, conditions, weights on the right side. This would the parsing a bit more straight forward, would keep the conciser construction (see 2) and also get rid of your proposed unnecessary predecessor key.
It would be a bit less ABOPy but in my opinion overall better. Would you agree, or prefer your initial proposal?

So a new workflow to set production may look like:

setProduction('F', {
    /* set a basic condition*/
    condition: () => time > 1.0,

    stochasticSuccessors: [
        {
            weight: 0.2,
            successor: [{symbol: 'F', customParameter: 2}, {symbol: '+'}, {symbol: 'F', customParameter: 5}]},
        {
            weight: 0.3,
            successor: {symbol: 'F', customParameter: 0}},
        {
            weight: 0.5,
            /* additional condition in a case when this sucessor is choosen with a chance of 50%*/
            condition: () => time > 9000.0,
            successor: [{symbol: 'G', customParameter: 2}, {symbol: 'F', customParameter: 2}, {symbol: '-'}]}
    ]
});


setProduction('B', {
    /* set a basic condition*/
    condition: () => time > 1.0,
    leftCtx: 'FFB',
    rightCtx: '+B',
    sucessor: 'BB' /* which would internally get transformed to the equivalent object: {symbol: 'BB', weight: 1}*/
});

// Or with explicit classicSyntax option this may be allowed:

setClassicProduction('FFB<B>+B', {
    /* set a basic condition*/
    condition: () => time > 1.0,
    sucessor: 'BB' /* which would internally get transformed to the equivalent object: {symbol: 'BB', weight: 1}*/
});

//or something like: 

setProduction('FFB<B>+B', {
    allowClassicSyntax: true,
    /* set a basic condition*/
    condition: () => time > 1.0,
    sucessor: 'BB' /* which would internally get transformed to the equivalent object: {symbol: 'BB', weight: 1}*/
});

// Or when defining it together via the constructor:

let lsystem = new LSystem({
    axiom: [{symbol: 'F'}, {symbol: '+'}, {symbol: 'F'}],
    productions: {

        'F': {
            /* set a basic condition*/
            condition: () => time > 1.0,
            leftCtx: 'FFB',
            rightCtx: '+B',
            sucessor: 'BB' /* which would internally get transformed to the equivalent object when this production is being applied: {symbol: 'BB', weight: 1}*/
        },

        'B': {
            leftCtx: 'F+',
            /* To not cause confusion, I suggest using something like `stochasticSuccessor`             to define a stochastic list, because each of these would need the weight,
            which of course shouldnt be part of the final successor object. If the user should define both,
            a successor and stochasticSuccessors,
            we could trigger a warning and ignore the singly successor in favor of the list*/
            stochasticSucessors: [
                { weight: 0.2, successor: [{symbol: 'F', customParameter: 2}, {symbol: '+'}, {symbol: 'F', customParameter: 5}]},
                { weight: 0.3, successor: {symbol: 'F', customParameter: 0}},
                {
                    weight: 0.5,
                    condition: () => time > 9000.0,
                    successor: [{symbol: 'G', customParameter: 2}, {symbol: 'F', customParameter: 2}, {symbol: '-'}]}
            ]
        }

    }
});

from lindenmayer.

I kinda also like your initial idea setProduction(from, to, conditions) or perhaps evensetProduction(from, conditions, to) which is really good in this form because it nicely separates everything in a logical way. It would also get rid of using "predecessor" or "sucessor" everywhere, because its clearly defined where they go. But this would mess again with setting the prods in the constructor; But I got an idea for that..

hmm, I might actually give the triple a try.

from lindenmayer.

Oh sorry I'm not sure I made myself clear. What I meant was that the user can specify the production as a:

• string
• object
• array
• function

But lindenmayer.js, internally would convert all of these to arrays of objects. But looking at what you've suggested, I much prefer using objects for all the successors, with an optional stochasticSuccessors array. That looks really nice. And I entirely agree with your proposal to put the left and right context on the RHS object, your reasoning is good (makes it useable with dictionaries etc.)

So, having taken that into account, here's my revised proposal:

Everywhere you can set a production (in the LSystem constructor, in setProduction and setProductions), there will be a LHS (the dictionary key or first argument), and the RHS (the dictionary value or second argument)

The LHS must be a string containing the predecessor symbol, optionally with a left and right context in the classical syntax. These left and right contexts will be converted to leftContext and rightContext on the successor object.

The RHS can be:

• A string, which is internally converted to {successor: x}, where x is the string. Note, if this causes memory issues, we could keep this as a string, and then switch case every time we need to run a production. This would improve the performance but messy the internal code somewhat
• A function, which is internally converted to {successor: x}, where x is the function
• An object, which can have the keys:
  • leftCtx: the left context
  • rightCtx: the right context
  • condition: a function with the signature object -> boolean that returns true if we should use this production, otherwise false
  • successor, a string or function returning a string that determines the successor symbols
  • weight, only relevant if part of a stochasticSuccessors array. Determines the chance that this production is used
  • stochasticSucessors: an array of more RHS objects in any of the three types described here (string, function, object), from which one production will be chosen, based on weight.

Thoughts?

from lindenmayer.

Actually why can't we use the same key for stochastic successors and normal successors? Then we just say that successor can be either:

• A string
• A function
• An array of objects

Then, they can set the RHS as any of these options, which would all be internally converted to an object, or they can pass a full object containing any of the keys above

from lindenmayer.

Actually why can't we use the same key for stochastic successors and normal successors? Then we just say that successor can be either

It would work of course. It's just a matter of style.
I kind of like to have objects x in successor: x to be of the same format in all places. To me it feels irritating to have key:values likes weight and other successors inside an object that is called successor which indicates that this would be the final form in which it is going to be stored in memory. Having the separate identifier makes the distinction better pronounced in my opinion. But maybe thats just me.

Also you could have an array of functions btw. (that return either false in which case the next function or value in the array is used or they return a valid successor). See this line: https://github.com/nylki/lindenmayer/blob/master/test/tests.js#L155

from lindenmayer.

Thoughts?

I like it! 👍
But what do you think of the alternative setProduction, similiar to your initial idea:

// Scaffold all conditions, stochastic stuff and options into a third argument
// so instead of:
setProduction('F', {leftCtx: '+G', condition: someFc, successor: 'FFF'});
// We could do:
setProduction('F', {leftCtx: '+G', condition: someFc }, 'FFF');
// This would still be internally transformed to {leftCtx: '+G', condition: someFc, successor: 'FFF'} or similiar

setProduction('F', {leftCtx: '+G', condition: someFc }, [{symbol: 'F'}, {symbol: 'G'}]);

setProduction('F', {leftCtx: '+G', condition: someFc }, {
    stochasticSuccessor: [
        {weight: 0.2, successor: [{symbol: 'F'}, {symbol: 'G'}, {symbol: 'G'}] },
        {weight: 0.8, successor: [{symbol: 'G'}, {symbol: 'G'}] }
    ]
});


// And when defining them in the constructor, it could be the same as we discussed.
let lsys = new LSystem({
    axiom: 'F',
    productions: {  
        'F': { leftCtx: '+G',  condition: someFc, successor: {symbol: 'G'} }
        'G': { leftCtx: '-FF', condition: someFc, successor: {symbol: 'G'} },
        'H': 'FF'
    }
})

The successor is the field that is mandatory, why not making it into a separate argument of the function? The only problem I see is that the constructor would look different again. Maybe its best to go with only two arguments (predecessor string, string/object/func/array) and offer the slightly more concise way with three arguments as an option (by checking wether the user used three or two arguments)?

from lindenmayer.

I think I prefer only two sections to the arguments (LHS and RHS). Ideally I'd only want 1 section, but that stops us using the nice dictionary syntax so 2 is a good compromise

from lindenmayer.

I'm working on something based on our ideas right now. I'll let you know (in ~1-3 weeks) when you can test and play around with it!

Oh and btw. there won't be any serious memory problem as long as you don't have an extremely large amount of productions. When I wrote that, I actually had a different scenario in my head: (transforming all strings of axiom and productions RHS to Arrays of Objects, like FFF --> [{symbol: 'F'}, {symbol: 'F'}, {symbol: 'F'}]. This one would indeed have a performance impact on string only L-Systems, but would simplify things at some places as well.

from lindenmayer.

Quick heads up, I am still on it. Got sick and couldn't do anything productive the past two weeks :/

from lindenmayer.

Resolved via #16

from lindenmayer.