Target values and recursion depth

[lagroue]

Re: [was] A new alphabet font

About drawing empty circles :

This is exactly the class of shapes that would benefit from control of recursion depth. This is a much more interesting use than my original thoughts on hue control.

Code: Select all

startshape letter_O
rule arc {
   CIRCLE { }
   arc { r 1 x .1 y .1 }
}
rule letter_O {
   arc {limit =360}
} 

First, three ideas on recursion depth limits :
- they theorically break the context-free paradigm
- they don't break it when they are seen as a rendering engine optimizer (it's useless to draw this empty circle forever, just stop at 360 degrees, this will be enough)
- they totally break it when outside of this optimizing scope, but then they may be seen as a tool for drawing new basic shapes (such as a slice of pie, for example, or a stripped square)

Those make me think too that there is a real interest in implementing such a feature.


Now, assuming target values, aka limit values, described in this topic, will be implemented, maybe we could merge those with this recursion depth requested feature ?

Something like :

Code: Select all

startshape letter_O
rule arc {
   CIRCLE { }
   arc { r 1 x .1 y .1 }
}
rule letter_O {
   # tell arc to break when its rotation will be 360 further
   arc { |r 360 break }
}

As John said, moving towards limits may not be implemented for every parameters. Targetting rotation, and size, for example, raise implementation problems. Code such as "A { r 0.5| }" which would mean "bring rotation 50% towards rotation target" won't be possible any time soon. (If I read well enough)

BUT setting a rotation target "arc { |r 360 }" is still possible.
It wouldn't be useful for "bringing rotation closer to its limit", but it would be to tell "stop iterating when limit is reached".

Now I don't know if previous code should be written as :

Code: Select all

startshape letter_O
rule arc {
   CIRCLE { }
   # break if target is reached
   arc { r 1 break x .1 y .1 }
}
rule letter_O {
   arc { |r 360 }
}

But maybe the matrix internally used don't allow knowing where we are relatively to the limit, and this post is pure utopy.
Or the 360=0 property of angles (hum... in this circle case, 359 would still do the trick)

[grimace]

You could maybe propagate a value 'n' (default 1) which terminates the current shape when it reaches 0. Therefore, for 100 squares in a line, you could do:

Code: Select all

rule SQUARES {
SQUARE{}
SQUARES{x 2 n -0.01}
}

This requires that we perform linear addition/subtraction on n which doesn't quite seem to fit the paradigm...

[grimace]

You could maybe propagate a value 'n' (default 1) which terminates the current shape when it reaches 0. Therefore, for 100 squares in a line, you could do:

Code: Select all

rule SQUARES {
SQUARE{}
SQUARES{x 2 n -0.01}
}

This requires that we perform linear addition/subtraction on n which doesn't quite seem to fit the paradigm...

...or does it? On second thoughts, it only seems to be the size parameter which is updated by multiplication (scaling) rather than addition.

Of course, this proposal is intentionally lightweight. Would it have sufficient scope to be useful at all?

[MtnViewJohn]

We already have a mixture of additive and multiplicative parameters, so making the limit parameter additive isn't a big deal. I feel a little bad that I have taken Context Free/CFDG farther away from its context-free roots. Chris said:

For examples: passing variables to child shapes, limiting the number of times a certain rule can be used, positioning things absolutely, and declaring a specific color -- these are all context "sensitive" rules. By including those things CFDG isn't CF anymore.

The limit parameter directly contradicts the CF nature. The syntax for setting hue, saturation, brightness and alpha is also non-CF. But even if we took it out you would still be able to set saturation, brightness and alpha using two steps, so why not give in and allow it for hue? Maybe we can add a hue limit feature and take out the 'color_component =x' syntax and pretend to be virtuous.

So the limit parameter may be useful and we are already sliding down this slippery slope. I wonder where we will end up?

[lagroue]

We already have a mixture of additive and multiplicative parameters, so making the limit parameter additive isn't a big deal. I feel a little bad that I have taken Context Free/CFDG farther away from its context-free roots. Chris said:

For examples: passing variables to child shapes, limiting the number of times a certain rule can be used, positioning things absolutely, and declaring a specific color -- these are all context "sensitive" rules. By including those things CFDG isn't CF anymore.

The limit parameter directly contradicts the CF nature. The syntax for setting hue, saturation, brightness and alpha is also non-CF. But even if we took it out you would still be able to set saturation, brightness and alpha using two steps, so why not give in and allow it for hue? Maybe we can add a hue limit feature and take out the 'color_component =x' syntax and pretend to be virtuous.

So the limit parameter may be useful and we are already sliding down this slippery slope. I wonder where we will end up?

Hey ! Considering the limit / recursion depth stuff : a python (perl/C++/whatever) script could produce cfdg code which would work today. Instead of producing one rule having a limit of 10, python would spit out ten lines. And the produced cfdg would be exactly as context free as the grammar today. Or wouldn't it for the only reason that it has been produced by another program ?

So there is no true new feature. Just a syntax helper.
Or should we leave such loops available only for developpers who know how to use a language to produce cfdg files ?

It's not "pretending" to be virtuous : we're introducing high-level features on the ground of a contect-free language. Maybe the syntax should clearly split away those two levels.

I agree the "=" syntax is odd. I even wonder why we need that, but I guess John has thought better than I since he says so. But all other extensions look pretty clean to me, for context-freeness' sake. Bricks on the ground.

[MtnViewJohn]

Well I feel better about the limit feature.

I think the "=" syntax was a mistake. It is really not context free and I can't think of any argument that can save it. I thought it would be necessary for color control but it really isn't. It just saves people from having to do some math, or use the color calculator. I would like to take it out. Some cfdg files on the gallery site would have to be redone. We did warn that cfdg files might get broken by changes.

[lagroue]

Complicated post here - next one is much simpler.

Well I feel better about the limit feature.

I think the "=" syntax was a mistake. It is really not context free and I can't think of any argument that can save it. I thought it would be necessary for color control but it really isn't. It just saves people from having to do some math, or use the color calculator. I would like to take it out. Some cfdg files on the gallery site would have to be redone. We did warn that cfdg files might get broken by changes.

OK. Though recursion questions, now.
Recursion depth is not context-free, so, where to store the context ?
And what to put in it ?

I discuss 3 hypothesis in this post.


If context is stored in the rule node of the rule tree, context may have a "depth" attribute, decremented at each step, unless a depth is explicitely set. I'll note a node "RULE(depth)". When depth reaches 1, no expansion is applied.

Simple code :

Code: Select all

startshape 4 A # recursion depth 4
rule A { A { } }

A(4)-A(3)-A(2)-A(1) stop

Simple code 2 :

Code: Select all

startshape 4 A # recursion depth 4
rule A { B { } }
rule B { A { } }

A(4)-B(3)-A(2)-B(1) stop

Less simple code:

Code: Select all

startshape 4 A # recursion depth 4
rule A {
  A { }
  2 A { } # recursion depth 2
}

First node : A(4)
Its children nodes : A(3), and A(2) (2 because of line "2 A { }" overrides current depth)
Let's take this A(2) child node.
Its children would be : A(1) and A(2)
A(1) is bottom, so it won't expand anymore.
A(2) is not yet bottom.
Its children would be : A(1) and A(2)
A(1) is bottom, so it won't expand anymore.
A(2) is not yet bottom.
Its children would be : A(1) and A(2)
etc.

So we still have infinity.


If this is not intended, then a new method has to be invented, assuming that either :
- context should not be stored in the rule node
- context should not have a single "depth" attribute


Let's try to let several "depth" attributes in the node. Each time a depth limit is requested, a new "depth" attribute is created. A node doesn't expand if any depth has gone to 1.

This would give the tree below (grey nodes are not expanded) :

Code: Select all

startshape 5 A # recursion depth 5
rule A {
  A { }
  3 A { } # recursion depth 3
}

We'll stop at 5, whatever happens, and we'll never have more than 3 nodes linked by successive blue lines.

But a new curse raises : the "3 A {}" line would not be honored, as designer expects, several times (where there isn't two blue lines one after the other, at the bottom of 5-staired tree)


Last try : the context is stored I don't know where, but the depth is related to the line of code
"A { }" and "3 A { }" are the two lines in the code below.

Code: Select all

startshape 4 A # recursion depth 4
rule A {
  A { }
  3 A { } # recursion depth 3
}

Each time we see a blue line, for "3 A {}", we see two of them one after the other, linking 3 nodes.
The line "startshape 4 A" is triggered at the beginning, so we'll never have more than 3 red lines in the tree, from seed to leaves (3 lines for 4 nodes).

Maybe this last case is closer to what's expected.
But implementation is still beyond my analysis.


And I wonder if this code should be infinite :

Code: Select all

startshape A
rule A {
  2 A { }
}

Time for a new nap...

[lagroue]

I don't like all the code above because the context-free elements are merged with context-dirty ones. I wonder if there is any way to split them apart.

We could create context-free "universes". In a universe, no recursion depth can be set for rules. But a universe can be given its own recursion depth which applies globally.

Something like :

Code: Select all

startshape A
rule A {
    B { }
}

universe B {
   depth 100
   startshape C
   rule C { ... }
   ...
}

This would be cleaner, and raise less paradoxes, I hope.

[grimace]

We already have a mixture of additive and multiplicative parameters, so making the limit parameter additive isn't a big deal. I feel a little bad that I have taken Context Free/CFDG farther away from its context-free roots. Chris said:

For examples: passing variables to child shapes, limiting the number of times a certain rule can be used, positioning things absolutely, and declaring a specific color -- these are all context "sensitive" rules. By including those things CFDG isn't CF anymore.

The limit parameter directly contradicts the CF nature.

Which criteria does the limit parameter break?

It doesn't "limit the number of times a certain rule can be used"; to do that, one would require a global limit assigned to a specific rule, which would certainly not be CF. The limit parameter I suggest is not global and is not associated with any particular rule.

Or am I just being dense?

[lagroue]

Which criteria does the limit parameter break?

It doesn't "limit the number of times a certain rule can be used"; to do that, one would require a global limit assigned to a specific rule, which would certainly not be CF. The limit parameter I suggest is not global and is not associated with any particular rule.

I wish we were immortal - but something has broken the context free paradigm of "rule life { life { year 1 }" : something did "limit the number of years a certain life can be used".

[aaronstj]

I wish we were immortal - but something has broken the context free paradigm of "rule life { life { year 1 }" : something did "limit the number of years a certain life can be used".

Yeah, but I don't think it's a recursion limit. I think it's more of a random stop rule

Code: Select all

startshape liveAnotherYear

rule liveAnotherYear {
     //yay!
     liveAnotherYear {}
}

rule liveAnotherYear 0.015 {
    //sucks to be you!
    die{}
}

rule die {
    //recursion bottomed out
}

[MtnViewJohn]

Here is an attempt at a purely local recursion limit that doesn't add new syntax. Let us associate a limit parameter 'n' with each shape. The default 'n' of the startshape is 0. The limit is changed using the following rules:

Code: Select all

rule ParentShape {
	Shape { n -1 }    // Subtract 1 from n and execute Shape if result is not negative
	Shape { n 100 } // Add 100 to n and execute Shape
	Shape { n 0 }     // Execute Shape only if ParentShape limit 'n' is 0
	Shape { }          // Always execute Shape
}

I didn't list an 'n =100' syntax because I want to get rid of this in the color adjustments, so it hardly seems appropriate to propagate it here. Please respond if you think an '=' syntax is important for recursion limits.

I think that Chris labels recursion limits as non-CF because a recursive CF grammar should recurse infinitely unless there is an explicit stopping rule. The size based stopping rule is not intrinsic to the context free grammar. It is an optimization that is needed because we don't have infinitely powerful computers. The size based stopping rule stops recursion at the point at which further recursion cannot change the resulting image.

Any finite recursion limit breaks this paradigm because the recursion stop is noticably different from infinite recursion. But as Lagroue has pointed out, any finite recursion can be replaced by a set of shapes generated by a Python script. There is little point in restricting this capability to Context Free users who are also programmers.

[Guest]

Code: Select all

rule ParentShape {
	Shape { n -1 }    // Subtract 1 from n and execute Shape if result is not negative
	Shape { n 100 } // Add 100 to n and execute Shape
	Shape { n 0 }     // Execute Shape only if ParentShape limit 'n' is 0
	Shape { }          // Always execute Shape
}

Gee, I love that ! Even recursion depth has been context-freed !
And there's an awsesome feature : we could even "rebounce" : "Shape { n 0 }" could allow to start a absolutely new kind of rules, something like :

Code: Select all

startshape A
rule A { B { n 100 } } # set B's n to 100 (yes ?)
rule B {
    # some drawing
    ...
    B { n -1 } # one step towards 0, B will be called 100 times (yes ?)
    C { n 0 } # on the 100th B, C will be triggered (yes ?)
}
rule C {
    ...
}

Or did I miss something ?

[lagroue]

OK, I'm logged now

I wish we were immortal - but something has broken the context free paradigm of "rule life { life { year 1 }" : something did "limit the number of years a certain life can be used".

Yeah, but I don't think it's a recursion limit. I think it's more of a random stop rule

Code: Select all

startshape liveAnotherYear

rule liveAnotherYear {
     //yay!
     liveAnotherYear {}
}

rule liveAnotherYear 0.015 {
    //sucks to be you!
    die{}
}

rule die {
    //recursion bottomed out
}

If only it was exactly that, we could sometimes leave a thousand years, or even more !
Maybe some kind of god invented recursion limits years after characters like Abraham and others have lived several centuries... We live in Earth 1.3, nowadays !

Code: Select all

# politically correct die rules
rule die { }
rule die { paradise { } }
rule die { hell { } }
rule die { human { } }
rule die { sheep { } }
rule die { bee { } }
rule die { grass { } }
rule die { princess { } }

[MtnViewJohn]

And there's an awsesome feature : we could even "rebounce" : "Shape { n 0 }" could allow to start a absolutely new kind of rules, something like :

Code: Select all

startshape A 
rule A { B { n 100 } } # set B's n to 100 (yes ?) 
rule B { 
    # some drawing 
    ... 
    B { n -1 } # one step towards 0, B will be called 100 times (yes ?) 
    C { n 0 } # on the 100th B, C will be triggered (yes ?) 
} 
rule C { 
    ... 
} 

Or did I miss something ?

This is exactly what I meant. I probably should have said:

Code: Select all

rule ParentShape { 
   Shape { n -1 }    // Subtract 1 from n and execute Shape if result is not negative 
   Shape { n 100 } // Add 100 to n and execute Shape 
   OtherShape { n 0 }     // Execute Shape only if ParentShape limit 'n' is 0 
   Shape { }          // Always execute Shape 
}

It occurs to me that there is a problem if you write something like 'Shape {n -2}'. You could go straight from n=1 to n<0 without ever hitting n=0 and triggering the 'rebounce'. Maybe there should be a '<' syntax instead:

Code: Select all

rule ParentShape { 
   Shape { n -1 }    // Subtract 1 from n and execute Shape if result is not negative 
   Shape { n 100 } // Add 100 to n and execute Shape 
   OtherShape { n <1 }     // Execute Shape only if ParentShape limit 'n' is < 1 
   Shape { }          // Always execute Shape 
   Shape { n 0 }     // Exactly the same as Shape {}
}

It certainly makes the intent more clear.