Monthly Archives: March 2018

What I Am Learning About Functional. Some Insights.

For years now I have been working on a replacement for OpenSCAD. The developers of OpenSCAD describe it as

a functional language that lacks both variables and assignment statements.

In various discussions nobody is entirely clear if OpenSCAD is functional or declarative. I’ll leave that argument to the wiki on functional programming.

In computer sciencefunctional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data. It is a declarative programming paradigm, which means programming is done with expressions[1]

Regardless what is true and useful to us is that you can unroll OpenSCAD operations in a way that is declarative and leaves nothing behind but a core subset of basic constructive solids geometry operations. All of which are constant. They take something. They return something. New state is always made. Old state is never altered. This gives us the opportunity to shave OpenSCAD with a sharp razor.

Shave The Nightmare

Following this I am not sure of the  formal proof but I also surmise that it is then true that you can go from a series of unrolled declarative statements to a functional outcome and indeed to any language you desire. The reasoning then follows that a functional representation is by far the best way to move OpenSCAD in to another language.

Why do we want to do this?

Well I will reiterate that we want to translate OpenSCAD in to a language that is formal and sensible. We want to do that for a whole lot of reasons but let us just start with the interesting translation part for now and how it leads us in to the land of functional.

Here is an example …

EXAMPLE : 
difference() {
for( x = [0:10:100] ) {
translate([x,0,0])
cube(size=1);
}
}

BECOMES :
stack.push(difference())
for ( i = 0; i < 100; i++ ) {
stack.push( translate([x,0,0]) .cube(size=1) )
}

UNROLLS :
difference()
this.translate( [ 0 , 0 , 0 ] )
this.cube(size=1)
this.translate( [ 10 , 0 , 0 ] )
this.cube(size=1)  }
this.translate( [ 20 , 0 , 0 ] )
this.cube(size=1)  }
this.translate( [ 30 , 0 , 0 ] )
this.cube(size=1)  }
this.translate( [ 40 , 0 , 0 ] )
this.cube(size=1)  }
this.translate( [ 50 , 0 , 0 ] )
this.cube(size=1)

*we build a push tree which we unwind as we traverse the stack.   

Note here that we applying a greatly simplified grammar set in order to do the bare minimum to the OpenSCAD script to move it over to a new descent tree for a new target. For example to attack the loop above we might have applied the following Ternary 

GRAMMAR:

|for ?  @NEXT : @COPY ?  “(”  ? @PROCESS_FORLOOPS : @COPY

I am referring to this as bare minimum grammar to achieve OpenSCAD shaving.

Now you might be wondering why we don’t use something like Antlr or YACC. Why don’t we take the existing grammar they have created for this purpose?

Having worked this out you are now up to where I am which is you could either implement your own version of the OpenSCAD grammar and parser thus making all the same mistakes again -or- write a translator that moves the quasi functional / declarative OpenSCAD language as it currently is in to a representation accessible in a broader richer more formalised language like Javascript.

Why would we want to do this. Because making up your own grammar and parser is a terrible idea. The heavy lifting has been done for you. Just pick one! They are all good! Just not Prolog. Prolog was that weird kid that sat at the back of the class and smelled funny. See him all alone over thar. Go give him a hug if your feeling sorry for him.

Pick One

Given that we know that at its most basic that the constructive geometry is a series of simple boolean operations it really isn’t a requirement to have written a whole enormous parser. We know that doing these operations well and quickly was the target problem.

What was NEVER the target problem was inventing your own parser. Avoid at all costs.

Whenever you can translate don’t spew out gigantic grammar files and bury us all in your YACC. YOU ARE NOT THAT SMART AND NEITHER ARE WE.

The answer is we could indeed do exactly that. However we have a burden of work which shifts incrementally to the right as the complexity of parsing increases. At a certain point the token consumer is so simple that the majority of our work is actually in the hooks to code. We then weigh up the extra weight and time consuming effort of making something like Antlr or YACC actually work. The OpenSCAD grammar is totally at the opposite end of the scale. I dare you to go read it.

So we reiterate once again we did not come here to write a parser. We came here to reshape as little as possible on the way to getting to a parser that ALREADY WORKS ..

It is particularly useful to understand that this is possible because it makes interpreting OpenSCAD fairly straight forward if you wish to separate the OpenSCAD language from its current parser and grammar and gigantic codebase of C++.

Those playing along may have seen a hole in the above reasoning. Because OpenSCAD is not entirely pure.

For example should a difference statement be cumulative over all children  or should it operate on an invisible but implied a,b argument. It is obvious once you have unrolled it but this is what happens in the existing parser. So this line of thinking is useful in that it makes us really thing about the language itself.

difference() {
this.translate( [ 0 , 0 , 0 ] )
this.cube(size=1)
difference() {
this.translate( [ 10 , 0 , 0 ] )
this.cube(size=1)
difference() {
this.translate( [ 20 , 0 , 0 ] )
this.cube(size=1)
difference() {
this.translate( [ 30 , 0 , 0 ] )
this.cube(size=1)
difference() {
this.translate( [ 40 , 0 , 0 ] )
this.cube(size=1)
difference() {
this.translate( [ 50 , 0 , 0 ] )
this.cube(size=1)
}}}}}}}

And that leads us to functional programming and a conversation about translating and parsing and what the code might look like in JS to get us from thar to over here ….

First some ugly code I put together in my first pass. Imperative. Bad. All bad.

// ------------------------------------------------------------
// Walk a tree
// ------------------------------------------------------------
this.walk = ( tree ) => {
let i = 0
let state = true
while ( state === true && i < tree.length ) {
if ( this.isInList(tree[i][0]) ) {
//tree[i][1]();
this.hooks(tree[i][1])
state = true
} else {
//tree[i][2]();
this.hooks(tree[i][2])
state = false
}
i++
}
}


let s = '|difference |intersection |union |minkowski @NEXT @COPY => |( @NEXT @COPY => |) @NEXT @COPY => |{ @PROCESS_BOOLEANS @COPY' // grammar
let tokens = " difference ( ) { difference ( ) { union ( ) { circle ( size = 5 ) ; } } }" // set of tokens to iterate over
// -------------------------------------------------
// Flow the grammar stream past the tokens stream
// -------------------------------------------------
let flowGrammar = g => t => {
// split each tern delimited by =>
const gram = g.split("=>").map((ternaryGroup)=> {
return ternaryGroup.split(" ").filter((a)=>{ return a.length!==0 ? true : false })
})
// build occurence table of each instruction descent tree in token stream
const set = gram.map((ternaryGroup)=> {
return lodash.flatten(ternaryGroup.map((oPeration) => {
return oPeration[0] === "|" ?
t.split(" ").map( (chnk,index) => {
return oPeration.slice(1,oPeration.length) === chnk ? index : 0
}).filter( (index)=>{ return index > 0 ? true : false })
: []
}))
})
// build call table
const instr = gram.map((ternaryGroup)=> {
return lodash.flatten(ternaryGroup.map((oPeration) => {
return oPeration[0] === "@" ? oPeration : []
}))
})
console.log( set )
console.log( instr )
}
flowGrammar(s)(tokens)