dbj( org ); metacall()()()™ + project Euler

[Note: metacall base article]

I am currently in the stage of searching for simple but valid examples of metacall validity (aka: usefulness) as interfacing concept and programming idiom.

And, I think I have found one. metacall + project Euler. The mathematical nature of some computational problems make them a great fit for the functional paradigm. For those of you who don’t know, “Project Euler is a series of challenging mathematical/computer programming problems…” (ProjectEuler.net). I have concluded I could use the simple and interesting solution for a problem from “Project Euler” to show metacall in action.

Solution no. 1

It seems to me, that the problem no. 1, contains quite enough opportunities to play with it, in the context of an metacall usage example. Without “much ado about nothing”, I shall present my classical solution, without using metacall:

// MIT (c) DBJ.ORG

// Basic particle for the solution

// to projecteuler.net problem 1

// Return is a single number

// that is a sum of natural numbers

// in range [0 .. max]

// Where each number is

// multiplier of a input value div

function sum_n ( max, div ) {

var rez = 0 ;

while ( max-- > div)

if ( max % div== 0 ) rez += max ;

return rez ;

}

I have decided to solve a problem with one “building block” function, and one expression using it. sum_n(), above returns a single number, that is a sum of natural numbers in range [div .. max], where each number is multiplier of a value div. In which case this expression :

// add results for input [0 .. 1000]

// for divisors 3 and 5

// to compute problem [0 .. 1000]

// for divisor 15

var result = sum_n(1000,3) + sum_n(1000,5);

// Why not just [0 .. 1000]

// for divisor 15 ?

Gives the final result of the solution to the problem no. 1? No. The above is not a correct solution and you dear reader are sleeping on the job! Now … wake up and think: 3 x 5 = 15. So? So in the final expression above, 15 is “calculated in” twice, for 3 and for 5. Here is the proper final expression that yields the correct result.

// a correct solution using our

// "building block" function sum_n

var result =

sum_n(1000,3)

+ sum_n(1000,5)

- sum_n(1000,3*5) ;

// gives: 233168

After solution comes optimization

Strep 1 to the “final” solution is basically solved. But. Beside algorithmically, optimizations are achieved on the level of the language and/or runtime environment. For example one could safely predict that running each sum_n() call on a separate thread would speed up things. Or one could extend the solution so that more than two divisors are involved under one limiter :

// extend the functionality to receive 3 divisors

// using the same building block function sum_n

var result = sum_n(1000,3)

+ sum_n(1000,5)

+ sum_n(1000,7)

- sum_n(1000, 3*5*7) ;

// gives: 332679

Of course do not loose the fact that composable programming solutions are reusable and thus applicable to wide range of similar programs. Like this one is. We are composing the finals solution from building block function. This is very different to writing a single function or program for each variant of the same problem.

Here is the JSFiddle source so far.

function print (s) {

return setTimeout(function () {

document.body.innerHTML += "<li style='list-style: none'>"+s+"</li>" ; }, 1

) ;

};

// "building block" function

function sum_n ( max, div ) {

var rez = 0 ;

while ( max-- > div) if ( max % div== 0 ) rez += max ;

return rez ;

}

// https://projecteuler.net/problem=1

// 'standard' solution

var result = sum_n(1000,3)

+ sum_n(1000,5)

- sum_n(1000,3*5) ; // gives: 233168

print(result);

Why not stop here?

Reason 1: performance

Looking at above, it is obvious that parallel processing might be crucial, in improving performance. For that to happen, an correct mechanism (not algorithm) is found, selected and implemented.

Reason 2: change management

Whoever has spent some time developing the code for a customer, knows it is obvious that, requirements do change suddenly and drastically and good programming solution must be also resilient to change, to make improvements possible and feasible.

Change to the program is an improvement only and only if it is both possible and feasible.

Never loose this very simple but often overlooked wisdom. If it is not satisfied your change is not an improvement. This is why architectural patterns like metacall are important. To make the inevitable changes achievable in a feasible manner. Not always, but most of the time.

[nextpage title=”metacall, at last!”]

I shall use a simple form of metacall to create a better solution that will be resilient to change, but in the same time non-intrusive.

Which means: Not getting in the way of the solution of the original problem. This is very important quality for every architectural pattern to be adopted. Let us at last, dive into metacall usage.

// improvement of the previous solution

// sum_n is implemented by following the metacall pattern

// start and keep the result of [0..1000]

euler1solution(1000)

// keep the result for divisor 3

('+',3)

// add to previous result using divisor 5

('+',5)

// final adjustment, remove from what is

// stored, for divisor 3*5

('-',3*5)

// use the result and show it

( function ( rez ) {

alert(rez);

});

This is now more usable. And rather more elegant too. One can ‘stream’ in any number of call’s to compute sum_n(), and then show the accumulated result by using a callback. And of course, implementation might change in any direction without affecting the usage. We could, for example, implement sending input to server, in next version. Above is trivial to implement.

function print (s) {

return setTimeout(function () {

document.body.innerHTML += "<li>"+s+"</li>" ; }, 1

) ;

};

// building block of a solution, we keep it here for simplicity

function sum_n ( max, div ) {

var rez = 0 ;

while ( max-- > div) if ( max % div== 0 ) rez += max ;

return rez ;

}

// CallStream pattern/idiom

function euler1solution ( max_ ) {

var rezult = 0, limit = max_ ;

euler1solution = function (){

var command = arguments[0], divizor = arguments[1],

divmap = [] ;

switch ( typeof command ) {

case 'string' :

divmap[""+divizor] = divizor ;

if ('+' == command ) {

rezult += sum_n ( limit,divizor ) ;

} else if ('-' == command ) {

rezult -= sum_n ( limit, divizor ) ;

} else {

rezult = "Illegal command" ;

}

break;

case 'function':

try {

rezult = command(rezult,limit, divmap );

} catch (x) {

rezult = "Exception: " + x + ", from: " + command ;

}

break;

default :

rezult = 'illegal argument type: ' + typeof(command) ;

break;

}

return euler1solution;

}

return euler1solution;

}

// usage

euler1solution(1000)('+',3)('+',5)('-',3*5)

( function (rez,lim,divs) {

return print(

"For limit:" + lim + ", and divizors: {" + divs + "}, Result is:" + rez

) ;

}) ;

But why stop here?

We are basing our design on a metacall idiom and our solution is thus ultimately changeable. And somehow strangely monadic in nature too.

There is a real possibility, not just a hint, of being able to easily compose new solution form atomic particles of logic. Above initial “sketch”, I could extend to have something like “tool-bench”, for the whole expandable family of similar solutions to “Euler-ian” problems.

// non-trivial call-stream based solution

// compute solution to problem no. 1

euler_bench("id01")

('+',sum_n, 1000, 3)

('+',sum_n, 1000, 5 )

('-',sum_n,1000,3*5)

( show_current, 'sum_n' )

// in the same metacall now compute

// the solution to the problem no. 2

( solution_2, 4*1e6 )

(solution_2, 2*1e6)

(show_current, 'solution_2') ;

// each solution has unique ID

function show_current ( rez_id ) {

compute and show the stored rezults for each

solution before this is called

}

Here we have an euler_bench(), metacall based, mediator pattern, which saves results of solutions to two projecteuler.net problems, and shows the current result when required.

An argument to euler_bench(), is an id of the result data-set for managing the state of the solution so that we can instantiate and use one or more euler_bench( id ), in the same time in the same scope.

Non-trivial Territory

For this last “release” to work, we would have to implement “behind” few non-trivial state management mechanisms. For example each solution function, like .e.g. sum_n(), would have to emit the result to separate “result stack”. One result-stack for one euler-ian solution. otherwise final expressions will not work, since they will use results from disparate solutions.

And, as above, all this named result stacks will have to be clustered under one id, like “id01” in the example above. For this to work I will have the each solution function (aka: fundamental indivisible particle of logic) return an array of values so that calling mechanism can record its results properly associated with the worker who made it and its input parameters.

// Solution to projecteuler.net problem 1

function sum_n ( max, div ) {

var rez = 0, m = max ;

while ( max-- > div) if ( max % div== 0 ) rez += max ;

// Structure returned is used by

// final expression callback

// to compute the results

return [

"sum_n" ,// solution UID

rez , // what is the final result

m,div // variable number of input parameters

] ;

}

// solution to the euler problem no: 2

// Find sum of even valued terms

// in the fibonacci_sequence up to X

function solution_2 ( X )

{

var rez ;

// solution here

// Structure returned is used by

// final expression callback

// to compute the results

return

[ "solution_2" , // solution UID

rez , // what is the final result

X // variable number of input parameters

] ;

}

// here we can have any number of

// solution functions implemented as the two above

// results of each solution used

// in a call-stream are stored in

// a separate named data-set

// by using solution UID

Also. Callbacks we send, can be used to control the behavior of the solution “behind”. For example, we can have a callback that will erase the current result data-set, callback that will send the current result data-set to server, another one that can record the time passed, etc. But, all of these will not change the callers experience at all. If properly micro-designed metacall based interfacing mechanism stays intact.

Onto the next page more usage and hopefully some helpful thinking.[nextpage title=”Learn to think De-Coupling”]

Flexibility of metacall based API’s is almost endless. Each metacall based solution delivers bigger freedom to experiment, than a “normal” object+methods solution. And also it forces the programmer to think of decoupling idioms from the start. Which I consider as a very good thing indeed.

One more thing. Each and every metacall based solution does not have to be completely flexible, and ultimately clever. For example, one could pose much more strict rules for the above, and start like so:

// option:

// change back to strict rules for the callers

// euler bench must be constructed with id

// of the solution and initial constant input

// one instance is made for one solution usage

// solution UID is stored until not explicitly erased

// limiter is considered a constant in this variant

euler_bench("sum_n", 1000 )

(3)(5)(7) // divisors are variables

( compute _and_show_current ) ;

// result found by id "sum_n"

Above is not all singing and all dancing “workbench”, but still functional and flexible call-stream based solution. We can use our original solution unchanged to “stream in” any number of divisors we want, and then we collect the result.

Now please carefully re-read everything once more up to this point, and try to record how the original simple requirement has changed gradually to be almost dramatically different to what it wa on the beginning.

Change management is the key

This example is just an abstract problem, but imagine if it is to be solved and delivered to a paying customer? Who is also a “typical-real-life” customer, who likes to add and more importantly remove “details” from requirements?

A typical interaction with a typical customer goes like this. The original requirement might have been:

// start date

R1 :: make a program to compute the sum of all numbers,

which are less than X, and are multiples of Y.

Then (like us here) customer adds a “detail”, after let’s say two weeks.

// start date + two weeks

// R1 becomes R2

R2 :: make a program to compute the sum

of all numbers which are less than X,

and are multiples of Y1 or Y2 .

This is perhaps the original problem no 1. But. Mr Customer is unstoppable by now. After 3 days requirements are changed again.

// stat date + two weeks + 3 days

// R1 become R2, R2 becomes R3

R3 :: make a program to compute the sum of

all numbers which are less than X,

and are multiples of

one or more numbers less than X.

I am sure this is enough to illustrate the point. Add to the above all the requirements customer will make to “improve” the usability of each solution.

I am sure you understand, and I do not have to paint more of this “reality” picture. And now imagine you do not use a concept and mechanism like metacall is. To implement these changes as improvements would be much more difficult.

And as in real life with real requirements, down the development line, more and more changes are simply impossible to implement. And in the same time call them ‘improvements’.

Now imagine doing this without metacall based solution composed of particles of logic. That, i am sure you know by now, will be a struggle.

–DBJ

(first published 13 Apr 2010)

ps: We can talk about javascript code to implement the above if anyone cares to ask.

pps: We can also talk about c++ code to implement the above if anyone cares to ask :)

metacall()()()™ + project Euler

Solution no. 1

After solution comes optimization

Why not stop here?

[nextpage title=”metacall, at last!”]

But why stop here?

Non-trivial Territory

Change management is the key

Like this:

Related

Solution no. 1

After solution comes optimization

Why not stop here?

[nextpage title=”metacall, at last!”]

But why stop here?

Non-trivial Territory

Change management is the key

Share this:

Like this:

Related