Incremental Averaging

On Thu, 10 May 2012 02:07:59 -0700, Hugh Aguilar wrote:

> On May 9, 10:56Â*pm, Arnold Doray <inva...@invalid.com> wrote:
>> I needed a number tower (this Forth handles big integers, reals,
>> rationals & complex numbers),
>
> If you want all of these data types, Forth would seem to be an unlikely
> choice, what with Forth being an untyped language. :-)
>
> Have you considered making your system a super-set of PostScript? It has
> limited dynamic-OOP, which could be extended to include all of your
> "number tower" types. Doing PostScript in Java would certainly put a
> smile on Don Lancaster's face! PostScript is written in C. I don't know
> much about the implementation, but I think that it is fairly simple ---
> a lot simpler than Factor, anyway --- you might be able to port this
> into Java and also upgrade it to do that other stuff that you want.
> Apparently you have already done a huge amount of work in implementing
> Forth though, so maybe you are pot committed now.
>
> BTW, I do have rationals in my novice package.
>
> Jython has all of those data types --- have you thought about it? --- or
> do you consider it to be ugly like Clojure?

I have been on a long trek down a long road trying to find the simplest
language for impatient domain experts. I have inflicted on them Lisp,
OCaml and Ruby. These are all much too hard, since all they want is to
get on with their work, not program! Most know Fortran, but the nature of
the work is such that it isn't suited to Fortran. I can't see them using
Clojure -- too much hinges on recursion. I can't see them using P/Jyton
-- it's harder than Ruby.

I needed a language that I could use conveniently, change conveniently,
leverage on legacy code and which they could use too. Having found Forth,
I can safely say that it meets all these needs.

I needed to soften the edges a little, by using HOFs, etc, I also needed
multitasking, RPCs and Java connectivity. So I couldn't use ANS Forth.

The big revelation for me is how easy it is to write this kind of Forth
in Java. It gives you the facilities out of the box (like the GC).

Cheers,
Arnold

On Fri, 11 May 2012 22:27:39 -0700, Hugh Aguilar wrote:

> On May 11, 3:58Â*am, Arnold Doray <inva...@invalid.com> wrote:
>> The other problem is that you can't "save" MAP's result to a variable
>> where it could be reused and composed with other HOFs.
>
> You really should take a look at my novice package. My EACH and other
> similar HOFs (not a term I knew about, but whatever) allow the "toucher"
> (my term for the function that gets called for each node) to access
> parameters on the stack. This is EACH:
>
> : each ( i*x head 'toucher -- j*x ) \ toucher: i*x node -- j*x
>
> Notice how the toucher has access to the i*x stuff, which it can change
> into j*x stuff. EACH hides its own working data on the return stack
> during the execution of the toucher so that that data doesn't get in the
> way of the toucher accessing the i*x stuff underneath. Also, the toucher
> can REMOVE the node from the list, as EACH has already acquired the next
> node and stashed its address on the return stack out of the way.
>
> These functions demonstrate how all of this works:
> count-C purge-C collect-C first-C

Hugh, I understand what you are doing, but this is only going it half
way.

For HOFs to be really effective, your system needs 2 more ingredients --
lazy evaluation (or "delayed" evaluation as it also called), and for
*that* to really be practical, you need boxed quantities (ie, you need to
keep the sequence in memory somehow, not directly on the stack). The
stack is used to keep track of these boxed entities. Of course, having
such boxed entities presumes a GC.

I wrote in another post on this in much more detail (also in this
thread).

Cheers,
Arnold

On Sun, 13 May 2012 23:32:35 +0200, Marcel Hendrix wrote:

> Arnold Doray <invalid@invalid.com> writes Re: Incremental Averaging
>
>> On Sat, 12 May 2012 21:20:37 +0200, Marcel Hendrix wrote:
> [..]
>> That's another neat solution.
>
>> The HOF solution is comparable in speed to your imperative one above. I
>> used a version of your solution on my slow Forth (it runs on Java, uses
>> boxed integers, is not compiled to bytecode and has no optimization
>> whatsoever) at 3ms - 8ms (once JIT kicks in) for both solutions.
>
> The code doesn't run long enough to time it properly. With a special ns
> timer utility:
>
> FORTH> SumSQ*CUBE 24,616,520,368,496,750,925 248 microseconds elapsed.
> ok
>
> This is about 32 times faster than your timing, the speed ratio of a
> jetplane to a scooter :-)
>
> -marcel

Aren't you are comparing apples to oranges?

You have a very fast Forth. I am using a forth cobbled together in a few
days. A direct comparison is silly and it proves nothing of consequence.

The correct comparison is to compare timings of your imperative algorithm
against the HOF method *both* on MY forth (since your forth does not have
HOFs).

I have done exactly this, and on that basis, your imperative algorithm
and HOF algoritm performed similarly.

I re-ran it for larger N = 10^30:

6073475610503260942236987344898741

The HOF is faster (4400ms) vs the imperative solution (5500ms). I made
sure to run both 10 times to get the JIT to kick in. I think this is
because of my unoptimized DO...LOOP which is in Forth.

The listings are attached below. Remember, this is my Forth where * is
overloaded.

Cheers,
Arnold

\ ------------ IMPERATIVE SOLUTION

: => create , ;

: ^ 1 swap 0 do over * loop swap drop ;
10 30 ^ => n
0 => ix41
0 => ix63

: clear ( xt -- )
0 swap ! ;

: startup ( -- )
ix41 CLEAR ix63 CLEAR TIMER ;

: finish ( n -- )
ELAPSED . . ;

: square_41mod? ( -- next_n )
BEGIN ix41 @ 1 + DUP ix41 !
DUP * DUP 41 MOD WHILE DROP REPEAT ;

: cube_63mod? ( -- next_n )
BEGIN ix63 @ 1 + DUP ix63 !
DUP DUP * * DUP 63 MOD WHILE DROP REPEAT ;

: ?use ( dsum1 n1 n2 -- dsum2 bool )
* 2DUP n @ < IF + FALSE ELSE 2DROP TRUE THEN ;

: SumSQ+CUBE ( -- d )
startup 0 BEGIN cube_63mod? square_41mod? ?use UNTIL finish ;


\ --- HOF Solution

: square dup * ;
: cube dup square * ;
: squares ['] square map ;
: cubes ['] cube map ;
: /41? 41 mod 0= ;
: /63? 63 mod 0= ;
: ** ['] * zipwith ;
: sum 0 ['] + 1 reduce ;
: N< n @ < ;

: SumSQ+CUBE-HOF
timer
1 2 ...
dup squares ['] /41? filter
swap cubes ['] /63? filter
**
['] N< take-while
sum
elapsed . . ;

On Thu, 10 May 2012 01:40:21 -0700, Hugh Aguilar wrote:

> On May 10, 2:17Â*am, Arnold Doray <inva...@invalid.com> wrote:
>> I'm simply saying -- and I hope, proving with real code -- that Forth
>> is capable of flourishing outside its original design context, and can
>> be very relevant to solving modern programming problems.
>
> Is this Forth of yours proprietary? Or can we play with it? I'm
> definitely interested in looking at it.

I think it will be ok to release it under the GPL. Give me a week to get
this sorted. If anyone else is interested, mail me at arnold at terra
hyphen weather dot com.

On Sun, 13 May 2012 19:31:20 +0200, A. K. wrote:
>
> In the end with operator overloading one has to make a choice between
> early binding and late binding. Late binding makes for pretty code but
> has a runtime penalty. With early binding you have to give the compiler
> some type information. And overloading has a tendency to exponential
> growing complexity, the more types the operators have to digest.
>
> Eg. say one wants to use + for string concatenation and also for scalar
> numeric vector addition. One has to tell the compiler that character
> vectors are strings and no numeric vectors...

Very well put.

I use late binding internally.

But with Forth, you can have your cake and eat it.

If speed is your concern, then go "traditional" and define separate
operators for each "type".

If flexibility is your concern, then go with late binding-type operator
overloading.

Either way, that same Forth would allow you to do what you want. It need
not be an either/or decision.

I don't like early binding for obvious reasons. I've heard it said that
static type checking saves you trouble, but in truth, I feel (having used
"duck" typed languages like Lisp or Ruby and strongly typed ones like
Java and Haskell) they are more bother than a help.

The best reason for Types, (IMHO) is the ability to create new types
complete with their operators. I don't think early binding is needed for
this.

Cheers,
Arnold

On Wed, 09 May 2012 16:49:35 -0700, Hugh Aguilar wrote:

>
> I don't really understand why you want lazy evaluation. Isn't that for
> situations in which the data is calculated (usually some mathematical
> series, such as the Fibonacci or some such), and the lazy evaluation
> allows the calculation to be postponed until the data is needed? This
> isn't your situation at all! You just have a lot of data. It is not
> calculated though, but it came from measurements taken by some guy
> somewhere. I think that what you really need is virtual memory --- this
> way your data doesn't have to all be in memory at one time (as it does
> in Factor's sequences, or in my lists in my novice package). For this, I
> recommend that you use ye olde Forth 1K blocks --- that is what they
> were invented for!

Do read that other post to Albert where I explain this at some length.

In summary, no, you *don't* want lazy evaluation in general.

But you DO want lazy evaluation specifically when dealing with infinite
sequences. In other words, you want your HOFs to be lazy. There are two
reasons: It allows you to duplicate & pass the transformed sequence, and
that allows you to compose things to make complicated sequences.

The example below should answer your question. The data is from a CSV
file on disk.

Cheers,
Arnold

: => create , ;

"scs.csv" open-text => input

\ NB: :> is :NONAME

:> input @ readline ; seq => data

\ Extracts a given column of data from a row of CSV text.
: column ( <string> n -- <string> )
>R "," split R> @@ ;

data :> 2 column ; map => E
data :> 3 column ; map => Ei
data :> 4 column ; map => Ew-deficit

\ Pairwise subtraction of two sequences
: -- ( seq1 seq2 -- seq3 )
' - zipwith ;

Ei Ew-deficit -- => Ew
E Ei -- => Ei-error
E Ew -- => Ew-error

: square ( x -- x*x )
dup * ;

: ^2 ( seq -- seq' )
['] square map ;

: sum ( seq -- n )
0 ['] + 1 reduce ;

: length ( seq -- n )
0 ['] 1+ 1 reduce ;

: average ( seq -- n )
dup sum swap length / ;

Ei-error ^2 average sqrt => RMS-Ei
Ew-error ^2 average sqrt => RMS-Ew

\ Print the two Root Mean Squares.
RMS-Ei ? RMS-Ew ?

>
> I'm sorry, but in most cases you need different code to operate on
> different kinds of data.

Yes, but.... !

IF you had a way to specify type, you could imbue either your operators
with intelligence to know what to do at runtime (late-binding) or at
compile time by your compiler (early-binding, which I am not advocating).

Let's say you have +. for addition of floats and + for addition of
integers.

In our *hypothetical* Forth supporting types, to get + to do double duty
(to act on floats and ints), you might do this:


\ Definition for Floats
: + (( d d )) +. ;

\ Definition for Float + Int
: + (( d i )) real +. ;

\ Definition for Int + Anything else
: + (( i _ )) swap + ;

And presto, + would work for both integers and floats. The compiler takes
the special (( ... )) stack comments and converts them to late binding
decisions. Because I am using late binding, I am not interested in the
output type.

This is similar to what StrongForth does but (I am not sure of this),
StrongForth uses early binding. This is obviously faster, but requires
"discipline" on behalf of the programmer, since every word needs to be
typed -- both input and output. Which IMHO is rather tedious.

Let's say we now want to extend + to complex numbers.

\ Tells the compiler about a complex number. The type is called CPX.
type cpx

\ makes a boxed complex number
: complex ( n1 n2 -- n1+in2 )
... / Code to box the complex number somehow
cpx set-type ; / Set the type to CPX.

\ This word deconsructs the complex number
: ~complex ( c -- re img ) .... ;

\ Extend + to CPX domain
: + (( cpx cpx ))
~complex >R >R
~complex
swap R> +
swap R> +
complex ;

: + (( cpx _ ))
swap ~complex >R + R> complex ;

And now your + would work on complex numbers , floats, integers, etc.
If this isn't "simple" for professional programmers, I don't know what
is.

The drawback is that late binding is slow, and so is boxing/unboxing. A
GC is likely needed. But if speed is a serious concern, then nothing
stops you from "going traditional" and using separate + operators for
each type.

Cheers,
Arnold

On Sat, 12 May 2012 07:21:21 +0000, Arnold Doray wrote:

> How about this: Find all the pairwise products of squares divisible by
> 41 and cubes divisible by 63. Sum all such products which are less than
> 100,000,000,000.
>
> Not a fair challenge at all since this is where HOFs+Seqs shine. But
> here is the solution anyway:
>
> : square dup * ;
> : cube dup square * ;
> : squares ['] square map ;
> : cubes ['] cube map ;
> : /41? mod 41 0= ;
> : /63? mod 63 0= ;
> : ** ['] * zipwith ;
> : sum 0 ['] + 1 reduce ;
>
> 1 2 ...
> dup squares ' /41? filter
> swap cubes ' /63? filter
> **
> :noname 100000000000 < ; take-while
> sum
> .
>
> 68887253925 ok
>
> The Forth HOF/seq solution is simple because it is constructive; You
> only need to build the parts and put them together like "Lego blocks".
> There is no need to explicitly manage state.
>
> Cheers,
> Arnold

Hi!

Just for maintaining diversity of solutions:
8<---
\ Generator&filters solution; `|' - pipe prefix means filter-word

\ --- Helper Words
\ Borowed from M.L.Gasanenko backtracking papers:
: enter >r ;
: FORWARD postpone r@ postpone enter ; immediate
: BACKWARD postpone rdrop postpone exit ; immediate
\ ---
: :=0e 0e0 f! ;
: f+! dup f@ f+ f! ;
: fdiv? f/ fdup floor f= ;
: sqr fdup f* ;
: cub fdup sqr f* ;
: f2dup fover fover ;
: f2drop fdrop fdrop ;
\ --- Consumable Variables ---
: consumable -1 , here 0e0 f, constant ;
: consumed ( aconsumable -- aflag ) [ -1 cells ] literal + ;
: consumed? ( aconsumable -- flag.consumed ) consumed @ ;
: store ( aconsumable -- ; F: value -- )
dup consumed? IF dup f! consumed off ELSE fdrop drop THEN ;
: consume ( aconsumable -- ; F: -- value )
dup consumed? IF drop 0e0 ELSE dup f@ consumed on THEN ;

\ Problem specific words \
41e0 fconstant M 63e0 fconstant N
1e11 fconstant MAXPRODUCT
\ ======================= \
fvariable sump sump :=0e
consumable Sqrs consumable Cubs

: cub/N ( -- ; F: CB -- )
cub fdup N fdiv? IF Cubs store ELSE fdrop THEN ;

: sqr/M ( -- fincrSQ ; F: SQ -- )
sqr fdup M fdiv? IF Sqrs store ELSE fdrop THEN ;

: |updflags FORWARD nip nip Sqrs consumed? swap Cubs consumed? swap
BACKWARD ;

: |** ( forwd: F: -- product ) ( backw: F: -- )
Sqrs consumed? Cubs consumed? OR 0=
IF Sqrs consume Cubs consume f* FORWARD THEN
BACKWARD ;

: |product<MAX ( forwd: -1 -- -1; F: x -- x ) ( backw: -1 -- 0; F: x
-- )
fdup MAXPRODUCT f< IF FORWARD ELSE fdrop 0= THEN BACKWARD ;

: roots ( -- ; control flows like water in a plant - from roots to stem
and backwards )
1e0 1e0 -1 -1 -1 ( fincrSQ fincrCB fgen ; F: SQcnt CBcnt )
BEGIN dup
WHILE FORWARD
rot dup IF fswap 1e0 f+ fswap THEN
rot dup IF 1e0 f+ THEN
rot
REPEAT f2drop 2drop drop BACKWARD ;

: grows sump :=0e
roots |updflags fdup cub/N fover sqr/M |** |product<MAX sump f+! ;

: 1000harvest
utime 1000 0 do grows loop utime
2swap d- 1000 um/mod nip . ." miliseconds elapsed for 1000 grows." cr
sump f@ f>d d. cr ;
--->8

Test for spforth and gforth:
bo@ou:~/Software/src/forth$ spf4 adclf.f 1000harvest bye ; gforth adclf.fs
-e "1000harvest bye"
60 miliseconds elapsed for 1000 grows.
68887253925
252 miliseconds elapsed for 1000 grows.
68887253925

Have a nice day,
humptydumpty