version 2009-06-26 - by Guillaume Lathoud (glathoud _at_ yahoo _dot_ fr)
Cite this as:
"Self-closure and mutation: Inheritance for Javascript functions, with a stream application", by Guillaume Lathoud, version 2009-06-26, http://geocities.com/glathoud/publications/mutate_article/mutate_article.2009-06-26.html
Javascript objects have prototype inheritance. But new can only return an object, not a function. Could Javascript functions inherit from each other as well? I am proposing here a solution, called "mutation", and applying it to numerical streams, whose generic, high-level optimization turned out to be interesting enough to devote two sections to it.
In the "mutation" inheritance framework, a function me is at once copied and changed, using mainly self-closure (Section 6):
ret = function() { return ( fun || me ).apply( ret, arguments ); };ret is defined with a closure on itself, so that the original or overriding implementation (respectively me or fun), can access ret's member fields and methods through this.<member> . Members are copied from me and can be changed. As an example, Sections 4 and 5 build "abstract" stream functions S, SM, SMC, through successive mutations. One more mutation is used to build "concrete" numerical streams, e.g. the Fibonacci series. The recursive definition of a series is implemented very naturally through the above-described this.<member> access.
Separating abstraction levels - abstract streams versus concrete streams - permits to implement generic optimization algorithms:
S, SM and SMC.The SICP video lectures from Abelson and Sussman propose wishful thinking as a method to progressively break down complexity while implementing.
One starts to write code for what is ultimately wanted, assuming some functions already implemented - although they do not even exist yet. For example:
function wanted( x ) {
if ( assumed_1( x ) ) {
return assumed_2( x );
} else {
return assumed_3( x );
}
}
wanted is clear, as well as what the not-yet-implemented assume_1, assume_2 and assume_3 should do. This makes it easier for the mind to concentrate on only one layer of abstraction at a time (wanted), then move on to the next layer (assume_1, assume_2 and assume_3).The organisation of present article follows the wishful thinking pattern: The concrete, final stream example - what we want - is first exposed (Section 4), assuming the SMC stream function and the mutate inheritance method to exist. SMC and mutate are described in Sections 5 and 6, respectively.
In addition, Annex A uses SMC to build Pascal and Euler streams of streams, and Annex B contains the full Javascript code.
Notes:
mutate is inspired from Douglas Crockford's writings on Javascript's prototype, but mutate implements inheritance for functions - not just objects, and this in a prototype-free manner (Section 6).var keyword.The present section details what we expect from a convenient stream function, called SMC, and its underlying inheritance method, called mutate. Throughout the present section, SMC and mutate are simply supposed to exist - they will be described in Sections 5 and 6, respectively. (The article is organized following the wishful thinking pattern described in Section 3.)
Take the Fibonacci series:
1 1 2 3 5 8 13 21 34 55 ...
x_0 = 1
x_1 = 1
x_{n+2} = x_{n+1} + x_{n}
SMC that permits to implement such a recursive definition as is, using the SMC.mutate() method [note 1]:fibo = SMC.mutate( function next() {
if ( this.n() < 2 ) { return 1; } // Initialization
var a = this.previousn( 2 ); // Fetch the last two terms
return a[ 0 ] + a[ 1 ]; // Recursive definition of the next term
} );
function next () { ... } defines how to compute the next value of the fibo stream. Section 5 explains how SMC.mutate transforms next into fibo [note 2].Repetitively calling fibo() yields the terms of the series:
fibo = SMC.mutate( function next() {
if ( this.n() < 2 ) { return 1; } // Initialization
var a = this.previousn( 2 ); // Fetch the last two terms
return a[ 0 ] + a[ 1 ]; // Recursive definition of the next term
} );
a = fibo(); // Does: a = 1
a = fibo(); // Does: a = 1
a = fibo(); // Does: a = 2
a = fibo(); // Does: a = 3
a = fibo(); // Does: a = 5
a = fibo(); // Does: a = 8
a = fibo(); // Does: a = 13
a = fibo(); // Does: a = 21
SMC.mutate() builds the fibo Function and adds methods to it, including:
fibo.at( 32 ) // Access the 33th term of the Fibonacci series.
fibo.copy() // Copy fibo, the copy starts again at term 0.
fibo.tee() // Copy fibo, the copy starts at the current term.
at, copy and tee do not affect values returned by fibo(): fibo = SMC.mutate( function next() {
if ( this.n() < 2 ) { return 1; } // Initialization
var a = this.previousn( 2 ); // Fetch the last two terms
return a[ 0 ] + a[ 1 ]; // Recursive definition of the next term
} );
a = fibo(); // Does: a = 1
a = fibo(); // Does: a = 1
a = fibo(); // Does: a = 2
a = fibo(); // Does: a = 3
a = fibo(); // Does: a = 5
a = fibo(); // Does: a = 8
a = fibo.at( 4 ); // Does: a = 5, this does not affect subsequent calls to fibo()
a = fibo(); // Does: a = 13
a = fibo(); // Does: a = 21
a = fibo.at( 17 ); // Does: a = 2584, this does not affect subsequent calls to fibo()
a = fibo(); // Does: a = 34
a = fibo(); // Does: a = 55
fibo2 = fibo.copy(); // fibo2 starts again at term 0,
// this does not affect subsequent calls to fibo()
a = fibo2(); // Does: a = 1
a = fibo2(); // Does: a = 1
a = fibo2(); // Does: a = 2
a = fibo2(); // Does: a = 3
a = fibo(); // Does: a = 89
a = fibo(); // Does: a = 144
a = fibo(); // Does: a = 233
a = fibo(); // Does: a = 377
fibo3 = fibo.tee(); // fibo3 starts at the current term of fibo,
// this does not affect subsequent calls to fibo()
// this does not affect subsequent calls to fibo2()
a = fibo3(); // Does: a = 610
a = fibo3(); // Does: a = 987
a = fibo3(); // Does: a = 1597
a = fibo2(); // Does: a = 5
a = fibo2(); // Does: a = 8
a = fibo2(); // Does: a = 13
a = fibo(); // Does: a = 610
a = fibo(); // Does: a = 987
a = fibo(); // Does: a = 1597
a = fibo(); // Does: a = 2584
a = fibo(); // Does: a = 4181
Observe that streams (like fibo) are unaffected by calls to their "manipulator" methods (at, copy, tee). Therefore, there is no need to introduce "generators" and "iterators" , and copying the stream is much safer (e.g. as compared to Python itertools.tee [note 3] ).Section 5 further discusses the above example, explaining the underlying implementations SM and SMC.
SM and SMCThe present section describes first the SM function object, which permits to create streams (S) with memory (M). Then comes the SMC function object, which also permits to copy (C) streams. Refer to Annex B for full implementations.
SM and SMC both rely on their mutate method. As explained in Section 3, I am following the "wishful thinking" pattern: Throughout the present section, mutate is simply supposed to exist. The implementation of mutate will be described in Section 6.
In the following Fibonacci stream implementation:
fibo = SM.mutate( function next() {
if ( this.n() < 2 ) { return 1; } // Initialization
var a = this.previousn( 2 ); // Fetch the last two terms
return a[ 0 ] + a[ 1 ]; // Recursive definition of the next term
} );
fibo() calls next() with the context object this === fibo, fibo() is roughly equivalent to call next.apply( fibo ) .this.n() returns the current number of terms in the streamfibo() calls done so far. this.previousn( 2 ) returns the last 2 terms of the series. SM.mutate() creates the methods fibo.n and fibo.previousn, as well as a number of other useful methods for recursive definitions (excerpt from Annex B):
SM = ...
...
at: function ( /*Integer*/q ) { return ( _mem.length > q ) ? _mem[ q ] : undefined; },
first: function () { return this.at( 0 ); },
n: function () { return _mem.length; },
nextn: /* copy from F.nextn */
function( /*Integer*/ n ) { var a, ret = []; for ( a = 0; a < n; a++ ) { ret.push( this() ); } return ret; }
previous: function () { var r = this.previousn( 1 ); return r ? r[ 0 ] : undefined; },
previousn: function( /*Integer*/q ) { var a = this.n(); return this.slice( a - q, a ); },
slice: function( /*Integer*/s, /*Integer?*/e ) {
/* Similar to Array.prototype.slice(), // Note that e === undefined is allowed
...
}
...
at and slice methods without affecting the results of the "next term please" calls like fibo(), as in the example of Section 4: ...
a = fibo(); // Does: a = 8
a = fibo.at( 4 ); // Does: a = 5, this does not affect subsequent calls to fibo()
a = fibo(); // Does: a = 13
a = fibo(); // Does: a = 21
a = fibo.at( 17 ); // Does: a = 2584, this does not affect subsequent calls to fibo()
a = fibo(); // Does: a = 34
...
The SMC object builds further, adding methods to copy (C) streams at will (excerpt from Annex B):
SMC = ...
...
copy: function() { return this.copyn( 1 )[ 0 ]; }, // Copy this stream, starting again at the beginning
copyn: function( /*Integer*/nstreams ) { return _copy( n0, nstreams ); }, // n0: start again at the beginning
rest: function( /*Integer?*/q ) {
if ( q === undefined ) { q = 1; } // Default: like cdr in LISP
return _rest( n0 + q );
},
tee: function () { return this.teen( 1 )[ 0 ]; }, // Branch this stream at its current point
teen: function ( /*Integer*/nstreams ) { return _copy( n0 + p, nstreams ); } // n0 + p: current point
...
...
a = fibo(); // Does: a = 55
fibo2 = fibo.copy(); // fibo2 starts again at term 0,
// this does not affect subsequent calls to fibo()
a = fibo2(); // Does: a = 1
...
a = fibo(); // Does: a = 89
...
fibo3 = fibo.tee(); // fibo3 starts at the current term of fibo,
// this does not affect subsequent calls to fibo()
// this does not affect subsequent calls to fibo2()
a = fibo3(); // Does: a = 610
...
a = fibo2(); // Does: a = 5
...
a = fibo(); // Does: a = 610
...
Annex B proposes an copy-safe, optimized implementation of SMC.mutate, which uses SM.mutate to create a single, private object called _stream :
// stream with memory, copiable
SMC = S.mutate( {
mutate: function ( /*...*/ ) {
// Non-copiable stream (will *not* be returned).
var _stream = SM.mutate.apply( SM, arguments );
// Stream copier: _copy() and _rest(): layer of abstraction on
// top of _stream .
var _copy, _rest;
...
// Returned stream (public)
return _rest( 0 ); // Safe copy of the private _stream
}
}, function () { console.error( "Your next() function, to be implemented" ); return; } );
SMC.mutate returns a safe copy of _stream : // Returned stream (public)
return _rest( 0 ); // Safe copy of the private _stream
copy, tee, ..._stream, thus avoiding any unnecessary memory duplication or useless computation repetition. Finally, note that SMC() itself should not be called:
function () { console.error( "Your next() function, to be implemented" ); return; }SMC is akin to abstract classes in other frameworks and languages.Annex A goes one dimension further, using SMC to produce streams of streams, as in Pascal's triangle, and Euler's super-acceleration applied to Pi's approximation.
Section 6 goes one level of abstraction higher (or deeper), explaining the mutate inheritance mechanism used to create SM and SMC themselves.
In Javascript's prototype inheritance framework, new produces Object instances. Objects can have methods, but they are not themselves callable.
On the other hand, Javascript functions are "callable objects" [note 4]. But new cannot return a function, so the prototype framework cannot be used for functions to inherit from other functions.
To achieve inheritance for Javascript functions, I am proposing a some_function.mutate method that produces a mutated copy of some_function:
mutated_copied_function = some_function.mutate(
function ( a, b, c ) { /* modified implementation ... */ },
{
modified_member_1: ...,
new_member_2: ...,
...
} );
some_function is by default copied, and can (optionally) be overriden with another implementation: function ( a, b, c ) { /* modified implementation ... */ },some_function are by default copied, and can (optionally) be overriden: modified_field_1: ..., new_member_2: ...,mutate follows (excerpt of Annex B):...
F.mutate = function F_mutate( /* ... many Objects? and/or only one Function? */ ) {
...
// fun = < the one Function in arguments, if any >
// object = < mixin of all Objects in arguments, if any >
...
// Function implementation: use "me" by default, or "fun" if provided.
// In both cases: "this === ret" at execution time.
var me = this;
ret = function() { return ( fun || me ).apply( ret, arguments ); };
// Copy my member fields and methods ("me"),
// then overwrite or create new members ("object").
return this.mixin( ret, [ me, object ] );
};
ret is by default implemented with a copy of the original me, or (optionally) a new implementation fun: ret = function() { return ( fun || me ).apply( ret, arguments ); };
ret: ret = function () { ... .apply( ret, ... ); }ret()this will always be ret itself:this === retret's methods from within the implementation (fun or me). See for example fibo and next in the stream example of Section 5.In comparison to Javascript's prototype framework:
Functions are callable objects: while the object returned by new is not callable, the proposed mutate method returns a function, which is per definition itself callable - as used in the stream examples.
Encapsulation: mutate at once copies a function and changes the copy. In contrast, when using prototype, changes can only happen before or after calling new - by modifying objects up the prototype chain, or the object returned by new.
Increased safety: modifying a prototype may have unintended consequences on objects down the prototype chain. In contrast, after b = a.mutate( ... ), modifying a affects neither b nor b's descendants, since a.mutate( ... ) copies all members of a.
Increased speed: when calling b.method(), since method is always a direct member of b, the Javascript engine does not track back a prototype chain.
Copy cost: compared to new, the proposed mutate method may need more memory for "duplicate" members, since a.mutate( ... ) copies all members of a.
If you went that far, you might as well have a look at functional languages like Lisp or Haskell - if unknown to you. Functional programming has powerful, concrete applications, including in Javascript: "Functional programming with Dojo - Quick tips"
[note 1] In javascript Functions are "callable Objects", which includes "Object" and can thus have member fields and methods
[note 2] The word next is not mandatory. The function could be anonymously defined: fibo = SMC.mutate( function () { ... } );
[note 3] I have been happily using Python itertools in conjunction with libs like numpy and scipy, since they make possible to quickly build reliable scientific simulations. I do not intend to despise the value of Python itertools, but rather to explore equivalent possibilities in a language with closures like Javascript.
[note 4] Try for example in a Javascript console (Firebug, Rhino, etc.) to evaluate:
Function.prototype
Function.prototype.toSource()
Function.prototype.prototype
(function () {}).prototype
itertools, itertools.tee, The pictures are all copyright of their respective authors. The picture links worked as of June 2009. But the web being what it is, the links will sooner or later die, so here is some additional information:
Panama sloth.
http://www.oas.org/children/animals/PanamaSouthA.html
A close-up of a sunflower, by Steven Shogrunden, Summer 2002, Penticton, British Columbia, Canada.
http://www.suncitydesign.com/portfolio/photos/sunflower.htm
Mechanical sunflower, 3D-Art.
http://wallpapers.free-review.net/wallpapers/12/Mechanical_sunflower.jpg
Michigan from Above, by Alexander Cohn, 2008, Michigan, USA.
http://cohnphoto.com/0207elements/8simpleviewer-from%20above/index.html
First dog clone, by Woo-Suk Hwang, 2005.
http://news.nationalgeographic.com/news/2005/08/photogalleries/dogclone/
Michelangelo di Lodovico Buonarroti Simoni, The creation of Adam (detail), circa 1511, ceiling of the Sistine Chapel, Vatican City.
http://images.worldgallery.co.uk/i/prints/rw/lg/1/6/Michelangelo-The-hands-of-God-and-Man-163501.jpg
Fibonacci Numbers in Nature & the Golden Ratio, by R. Berdan, 2004.
http://www.world-mysteries.com/sci_17.htm
Cover of "Structure and Interpretation of Computer Programs", 1984, MIT Press.
http://mitpress.mit.edu/sicp/full-text/book/book.html
Citroen 2cv v8, by etaku, 2007, Swiss Drag Race Challenge 2007 Turtmann, Switzerland.
http://rides.webshots.com/photo/2345203360101143058leXvBL
IBM Type 80 horizontal sorter, circa 1930.
http://www.officemuseum.com/data_processing_machines.htm
Let C_{n,k} be the number of possibilities to choosekelements amongnwhere0 <= k <= n. One can define C_{n,k} recursively:
For all k > 0 C_{0,k} = 0
For all n >= 0 C_{n,0} = 1
C_{n+1,k+1} = C_{n,k+1} + C_{n+1,k}
C_{n,k} values called "Pascal's triangle":k | 0 1 2 3 4 5 6 ...
-------------------------------------------
C_{0,k} | 1 0 0 0 0 0 0 ...
|
C_{1,k} | 1 1 0 0 0 0 0 ...
|
C_{2,k} | 1 2 1 0 0 0 0 ...
|
C_{3,k} | 1 3 3 1 0 0 0 ...
|
C_{4,k} | 1 4 6 4 1 0 0 ...
...
var SMC_pascal = SMC.mutate( function next_row() {
var g_prev = this.previous(); // Previous row
var row = this.n(); // Index of the next row
var g = SMC.mutate( function next_term() {
var col = this.n(); // Index of the next column
if ( ! g_prev ) { return ( col === 0 ) ? 1 : 0; } // First row
if ( col > row ) { return 0; } // Optimization (not mandatory)
return ( g_prev.at( col - 1 ) || 0 ) + ( g_prev.at( col ) || 0 ); // Recursion
} );
return g;
} );
SMC.mutate generates a stream, one for rows, one for columns. With activated verbosity (verbose = true), you can see that only the needed terms are computed, and only once, because of the generic memory optimization in the SMC.mutate method.And for the curious:
This example is taken from the SICP book. Please refer to its section 3.5.3 for more details.
Consider the following "infinite sum" definition of Pi:
Pi = 4 * ( 1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + ... )
A_n, using the first n+1 terms:A_0 = 4
A_{n+1} = A_n + 4 * (-1)^( n + 1 ) / ( 2n + 3 )
n grows, the error |A_n - Pi| tends towards zero.Below is a stream implementation:// Stream of integers, starting at 0
var SMC_int = SMC.mutate( function next() {
if ( this.n() < 1 ) { return 0; }
return this.previous() + 1;
} );
// Stream of Pi approximations
var SMC_pi = SMC.mutate( function () {
if ( this.n() < 1 ) {
// Initialization: stream of integers
this._a = SMC_int.copy();
// Initialization: stream of (-1)^(n+1) for n = 0, 1, 2 ...
this._b = SMC.mutate( function next() { return -( this.previous() || -1 ); } );
}
this._a(); // Skip even numbers
var x = this._a() * this._b();
if ( this.n() < 1 ) { return 4; } // A_0
return this.previous() + 4 / x; // A_n for n > 0
} );
a = SMC_pi(); // Does: a = 4
a = SMC_pi(); // Does: a = 2.666666666666667
a = SMC_pi(); // Does: a = 3.466666666666667
a = SMC_pi(); // Does: a = 2.8952380952380956
a = SMC_pi(); // Does: a = 3.3396825396825403
a = SMC_pi(); // Does: a = 2.9760461760461765
a = SMC_pi(); // Does: a = 3.2837384837384844
a = SMC_pi(); // Does: a = 3.017071817071818
a = SMC_pi(); // Does: a = 3.2523659347188767
a = SMC_pi(); // Does: a = 3.0418396189294032
a = SMC_pi(); // Does: a = 3.232315809405594
(A_n) we build the accelerated series (B_n) : ( A_{n+2} - A_{n+1} )^2
B_n = A_{n+2} -
A_n - 2 * A_{n+1} + A_{n+2}
function SMC_euler_accel( /*SMC*/ s ) {
var s2 = s.copy();
// Return an accelerated stream
return SMC.mutate( function next() {
while ( s2.n() < 2 ) { s2(); } // Initialization
s2(); // Iter
// Mathematical formula
var x = s2.previousn( 3 );
return x[2] - Math.pow( x[2] - x[1], 2 ) / ( x[0] - 2*x[1] + x[2] );
} );
}
pi_accel = SMC_euler_accel( SMC_pi );
a = pi_accel(); // Does: a = 3.166666666666667
a = pi_accel(); // Does: a = 3.1333333333333337
a = pi_accel(); // Does: a = 3.1452380952380956
a = pi_accel(); // Does: a = 3.13968253968254
a = pi_accel(); // Does: a = 3.1427128427128435
a = pi_accel(); // Does: a = 3.1408813408813416
a = pi_accel(); // Does: a = 3.142071817071818
a = pi_accel(); // Does: a = 3.1412548236077655
a = pi_accel(); // Does: a = 3.1418396189294033
a = pi_accel(); // Does: a = 3.141406718496503
a = pi_accel(); // Does: a = 3.1417360992606667
10^(-10). Let us now repeat the Euler transform again, and again, and so on, indefinitely - that is super-acceleration. The result is a stream of streams:
function SMC_euler_super_accel( /*SMC*/ s ) {
var s2 = s.copy();
// Stream of streams (the many rows of the tableau)
var tableau = SMC.mutate( function next() {
if ( this.n() < 1 ) { return s2; } // Initialization
// Single stream (1 row of the tableau)
return SMC_euler_accel( this.previous() ); // Iter
} );
// Pick the first term of each stream ( = of each row)
return SMC.mutate( function next() {
return tableau().first();
} );
}
SMC_pi stream: pi_super_accel = SMC_euler_super_accel( SMC_pi );
a = pi_super_accel(); // Does: a = 4
// Note: a === SMC_pi.at( 0 )
a = pi_super_accel(); // Does: a = 3.166666666666667
// Note: a === pi_accel.at( 0 )
a = pi_super_accel(); // Does: a = 3.142105263157895
a = pi_super_accel(); // Does: a = 3.141599357319005
a = pi_super_accel(); // Does: a = 3.1415927140337785
a = pi_super_accel(); // Does: a = 3.1415926539752927
a = pi_super_accel(); // Does: a = 3.1415926535911765
a = pi_super_accel(); // Does: a = 3.141592653589778
a = pi_super_accel(); // Does: a = 3.1415926535897953
a = pi_super_accel(); // Does: a = 3.141592653589795
a = pi_super_accel(); // Does: a = NaN
// pi_super_accel.at(9) - Math.PI === 1.7763568394002505e-15
10^(-14).NaN: Eventually the process breaks down, when reaching the limit of the built-inJavascript number representation. To go further we would need a better number representation.Each call to SMC.mutate generates a stream, one for rows, one for columns. With activated verbosity (verbose = true), you can see that only the needed terms are computed, and only once, because of the generic memory optimization in the SMC.mutate method.
The full code follows. It outputs log messages on both:
/*global console F S SM SMC*/
verbose = false;
// Output logs and errors to the main page, and to the console (if any).
log = function log () {
// Firebug console, or equivalent
if ( window.console && console.log ) { console.log.apply( console, arguments ); }
// For all browsers
var s = Array.prototype.join.call( arguments, ' ' );
var n = document.createElement( 'span' );
n.innerHTML = '<code>' + s + '</code>';
document.body.appendChild( document.createElement( 'br' ) );
document.body.appendChild( n );
};
error = function error() {
// Firebug console, or equivalent
if ( window.console && console.error ) { console.error.apply( console, arguments ); }
// For all browsers
var s = Array.prototype.join.apply( arguments );
var n = document.createElement( 'span' );
n.className = 'error';
n.innerHTML = 'Error: <code>' + s + '</code>';
document.body.appendChild( document.createElement( 'br' ) );
document.body.appendChild( n );
};
// F, F.mutate etc. (explained in Section 5)
F = function F( /*String*/ methodname, /*Object*/ object /* , ... arguments*/) {
var a, args = [];
for ( a = 2; a < arguments.length; a++ ) { args.push( arguments[ a ] ); }
object[ methodname ].apply( object, args );
};
F.mixin = function F_mixin( /*Object*/ destination, /* Array of Objects */ source, /* boolean */ do_not_force ) {
var a, arr, b, c;
for ( a = 0; a < source.length; a++ ) {
b = source[ a ];
for ( c in b ) { if ( b.hasOwnProperty( c ) ) {
destination[ c ] = ( do_not_force && destination[ c ] ) || b[ c ];
}}
}
return destination;
};
F.copy = function F_copy() { return this.mutate(); };
F.mutate = function F_mutate( /* ... many Objects? and/or only one Function? */ ) {
// Heavily inspired from Crockford's mutate(), see http://www.crockford.com
var a, b, c, n_object = 0, fun = undefined, n_function = 0, n_other = 0, object = {}, ret, x;
for ( a = 0; a < arguments.length; a++ ) {
b = arguments[ a ];
if ( typeof b === "object" ) {
n_object++;
object = this.mixin( object, [ b ] );
}
else if ( typeof b === "function" ) { n_function++; fun = fun || b; }
else { n_other++; break; }
}
if ( n_function > 1 ) {
error( "F.mutate(): At most one function." );
return;
}
if ( n_other > 0 ) {
error( "F.mutate(): Only objects and/or one function." );
return;
}
// Function implementation: use "me" by default, or "fun" if provided.
// In both cases: "this === ret" at execution time.
var me = this;
ret = function() { return ( fun || me ).apply( ret, arguments ); };
// Copy my member fields and methods ("me"),
// then overwrite or create new members ("object").
return this.mixin( ret, [ me, object ] );
};
// stream without memory, not copiable
/*abstract*/ S = F.mutate( {
nextn: function( /*Integer*/ n ) { var a, ret = []; for ( a = 0; a < n; a++ ) { ret.push( this() ); } return ret; }
}, function() { /*To be implemented*/ } );
// example streams
function S_int_gen() {
var f = S.mutate( function() {
if ( ! f._init ) {
f._next_value = 0;
f._init = true;
}
var ret = f._next_value;
f._next_value++;
return ret;
} );
return f;
}
function S_fibo_gen() {
var f = S.mutate( function() {
var v;
if ( f._v === undefined ) {
f._v = [ 0, 1 ];
return 1;
}
var ret = f._v[ 0 ] + f._v[ 1 ];
f._v.splice( 0, 1 );
f._v.push( ret );
return ret;
} );
return f;
}
// Stream with memory, not copiable. Useful to implement e.g. recursive
// definitions like Fibonacci: this.previous() etc. can be called from
// the "next" function.
SM = S.mutate( {
mutate: function( /*... args ...*/ ) {
// Find the "next" function
var next;
var args = [];
for ( var a = 0; a < arguments.length; a++ ) {
var toa = typeof arguments[ a ];
if ( toa !== 'function' ) {
if ( toa !== 'object' ) {
error( "MS.mutate(): Only objects and/or one function." );
return;
}
args.push( arguments[ a ] );
continue;
}
if ( next && arguments[ a ] ) {
error( "MS.mutate(): At most one function." );
return;
}
next = next || arguments[ a ];
}
next = next || this; // Default: next() returns: undefined
// Private stream: Here are the methods "this.xxx()" that next()
// may use in its implementation
var _mem = [];
return S.mutate(
function () {
var x = next.apply( this );
_mem.push( x );
if ( verbose ) { log('SM next, x:', x, '_mem.length:', _mem.length, ', _mem:', _mem); }
return x;
},
{
at: function ( /*Integer*/q ) { return ( _mem.length > q ) ? _mem[ q ] : undefined; },
mutate: null, // Forbidden in next(), xxx todo: may provide an implementation
first: function () { return this.at( 0 ); },
n: function () { return _mem.length; },
/* nextn: copy from F.nextn */
previous: function () { var r = this.previousn( 1 ); return r ? r[ 0 ] : undefined; },
previousn: function( /*Integer*/q ) { var a = this.n(); return this.slice( a - q, a ); },
slice: function( /*Integer*/s, /*Integer?*/e ) { // Note that e === undefined is allowed
if ( verbose ) { log( 'SM.slice(',s,',',e,')' ); }
if ( s < 0 ) { return undefined; } // Differs here from Array.slice()
if ( e < 0 ) { return undefined; } // Differs here from Array.slice()
if ( e < s ) { return undefined; } // Differs here from Array.slice()
if ( _mem.length < s + 1 ) { return undefined; } // Differs here from Array.slice()
if ( _mem.length < e ) { return undefined; } // Differs here from Array.slice()
return _mem.slice( s, e );
}
} );
}
}, function () { error( "Your next() function, to be implemented" ); return; } );
var SM_int = SM.mutate( function() {
log( 'SM_int, this.n():', this.n() );
if ( this.n() < 1 ) { return 0; }
log( 'SM_int, return this.previous() + 1, this.previous():', this.previous() );
return this.previous() + 1;
} );
var SM_fibo = SM.mutate( function() {
if ( this.n() < 2 ) { return 1; } // Initialization
var a = this.previousn( 2 ); // Fetch the last two terms
return a[ 0 ] + a[ 1 ]; // Recursive definition of the next term
} );
// stream with memory, copiable
SMC = S.mutate( {
mutate: function ( /*...*/ ) {
// Non-copiable stream (will *not* be returned).
var _stream = SM.mutate.apply( SM, arguments );
// Stream copier: _copy() and _rest(): layer of abstraction on
// top of _stream .
var _copy, _rest;
_copy = function(/*Integer*/n0, /*Integer*/nstreams ) { // Generate multiple copies of _stream, starting at element n0
var r = [];
for ( var a = 0; a < nstreams; a++ ) {
r.push( _rest( n0 ) );
}
return r;
};
_rest = function(/*Integer*/n0) { // Generate a copy of _stream, starting at element n0
// The index of the next element is: n0 + p
var p = 0;
// Stream creation and duplication: "public" methods
return S.mutate(
function () { return this.at( p++ ); },
{
at: function( /*Integer*/q ) {
if ( verbose ) { log('SMC.at(' + q + ')'); }
var n0q = n0 + q;
while ( _stream.n() < n0q + 1 ) { _stream(); } // Auto-generation
return _stream.at( n0q );
},
mutate: function() {
error( 'In this particular case, not very interesting. Don\'t you think?' );
return;
},
copy: function() { return this.copyn( 1 )[ 0 ]; }, // Copy this stream, starting again at the beginning
copyn: function( /*Integer*/nstreams ) { return _copy( n0, nstreams ); }, // n0: start again at the beginning
first: function() { return this.at( 0 ); },
n: function() { return p; },
nextn: function( /*Integer*/q ) { return this.slice( p, p + q ); },
previous: function() {
if ( verbose ) { log('SMC.previous: p:', p); }
return ( p > 0 ) ? this.at( p - 1 ) : undefined;
},
previousn: function( /*Integer*/q ) { return ( p >= q ) ? this.slice( p - q, p ) : undefined; },
rest: function( /*Integer?*/q ) {
if ( q === undefined ) { q = 1; } // Default: like cdr in LISP
return _rest( n0 + q );
},
slice: function( /*Integer*/s, /*Integer?*/e ) {
if ( s < 0 ) { return undefined; }
if ( e < 0 ) { return undefined; }
var s2, e2;
s2 = n0 + s;
e2 = n0 + e;
while ( ( _stream.n() < s2 + 1 ) || ( _stream.n() < e2 + 1 ) ) { _stream(); } // Auto-generation
return _stream.slice( s2, e2 );
},
tee: function () { return this.teen( 1 )[ 0 ]; }, // Branch this stream at its current point
teen: function ( /*Integer*/nstreams ) { return _copy( n0 + p, nstreams ); } // n0 + p: current point
} );
};
// Returned stream (public)
return _rest( 0 ); // Safe copy of the private _stream
}
}, function () { error( "Your next() function, to be implemented" ); return; } );
//
var SMC_int = SMC.mutate( function next() {
if ( this.n() < 1 ) { return 0; }
return this.previous() + 1;
} );
var SMC_fibo = SMC.mutate( function next() {
if ( this.n() < 2 ) { return 1; } // Initialization
var a = this.previousn( 2 ); // Fetch the last two terms
return a[ 0 ] + a[ 1 ]; // Recursive definition of the next term
} );
var SMC_pascal = SMC.mutate( function next() {
var g_prev = this.previous();
var row = this.n();
var g = SMC.mutate( function () {
var col = this.n();
if ( ! g_prev ) { return ( col === 0 ) ? 1 : 0; } // First row
if ( col > row ) { return 0; } // Optimization (not mandatory)
return ( g_prev.at( col - 1 ) || 0 ) + ( g_prev.at( col ) || 0 ); // Recursion
} );
return g;
} );
function test_SMC_pascal() {
log( '---------- test_SMC_pascal ----------' );
var b = SMC_pascal(); log( b.nextn( 10 ) );
var c = SMC_pascal(); log( c.nextn( 10 ) );
var d = SMC_pascal(); log( d.nextn( 10 ) );
var e = SMC_pascal(); log( e.nextn( 10 ) );
var s;
s = "SMC_pascal.at( 13 ).at( 3 )"; log( s, ':', eval( s ) ); // Test: "Recursion"
}
test_SMC_pascal();
// Pascal's triangle using factorials
var SMC_fact = SMC.mutate( function next() {
return ( this.n() || 1 ) * ( this.previous() || 1 );
} );
function fact( n ) { return SMC_fact.at( n ); }
function pascal_fact( n, k ) {
return fact( n ) / ( fact( n - k ) * fact( k ) );
}
function test_pascal_fact() {
log( '---------- test_pascal_fact() ----------' );
var s;
s = 'pascal_fact( 3, 1 )'; log( s, ':', eval( s ) );
s = 'pascal_fact( 4, 1 )'; log( s, ':', eval( s ) );
s = 'pascal_fact( 4, 2 )'; log( s, ':', eval( s ) );
s = 'pascal_fact( 13, 3 )'; log( s, ':', eval( s ) );
}
test_pascal_fact();
// Euler's accelerator (for series of terms with alternating signs)
// See the LISP example in the SICP book.
var SMC_pi = SMC.mutate( function () {
if ( this.n() < 1 ) {
this._a = SMC_int.copy();
this._b = SMC.mutate( function next() { return -( this.previous() || -1 ); } );
}
this._a();
var x = this._a() * this._b();
if ( this.n() < 1 ) { return 4; }
return this.previous() + 4 / x;
} );
function SMC_euler_accel( /*SMC*/ s ) {
var s2 = s.copy();
// Return an accelerated stream
return SMC.mutate( function next() {
while ( s2.n() < 2 ) { s2(); } // Initialization
s2(); // Iter
// Mathematical formula
var x = s2.previousn( 3 );
return x[2] - Math.pow( x[2] - x[1], 2 ) / ( x[0] - 2*x[1] + x[2] );
} );
}
function SMC_euler_super_accel( /*SMC*/ s ) {
var s2 = s.copy();
// Stream of streams (the many rows of the tableau)
var tableau = SMC.mutate( function next() {
if ( this.n() < 1 ) { return s2; } // Initialization
// Single stream (1 row of the tableau)
return SMC_euler_accel( this.previous() ); // Iter
} );
// Pick the first term of each stream ( = of each row)
return SMC.mutate( function next() {
return tableau().first();
} );
}
function test_SMC_euler_super_accel() {
log( '---------- test_SMC_euler_super_accel() ----------' );
var pi = SMC_pi.copy(); // copy to make sure we start at the first element
var pi_accel = SMC_euler_accel( pi ); // Note that we do not have to copy "pi", see SMC.mutate()'s implementation above
var pi_super_accel = SMC_euler_super_accel( pi );
var prec = 16;
for ( var a = 0; a < 11; a++ ) {
log( pi().toPrecision( prec ), pi_accel().toPrecision( prec ), pi_super_accel().toPrecision( prec ) );
}
}
test_SMC_euler_super_accel();
test_SMC_euler_super_accel(); // Works exactly the same