From a recursive circuit to a functional/recursive OCaml-code...

From a recursive circuit to a functional/recursive OCaml-code...

[Oliver Bandel]

Hello,


how to implement a simple non-trivial machine (Heinz von Foerster)
in a purely functional manner?

With functional/recursive OCaml code?

I had written a mail with attachement (which contains a
jpeg with the structure of the circuit), but it seems it
was blocked or filtered away by the OCaml mailinglist software?!

So I try to give it as some formulas:


let u = func_B x e
let e = func_C u
let y = func_A x




I want to have y as a function of x (and x is read from stdin as int).
With each next input of x the next y should be calculated and printed
(maybe u and e also printing).

Normally - in the non-functional world - I would use
variables with a start-value and then iterate with
each input. So I had to save some values for some
calculations (call by value), so that I do not change
the values.
The functional way should make it unnecessary to save
the values. The functional programming paradigm should help here.

But it's a recursive process... or should I use iterations,
even if I use a functional language here?

Or, when using recursion, do i have to use mutual recursive functions
or recursive values here?!

Any hint is welcome.


TIA,
   Oliver

Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[skaller]

On Sat, 2006-02-04 at 22:19 +0100, Oliver Bandel wrote:
> Hello,
> 
> 
> how to implement a simple non-trivial machine (Heinz von Foerster)
> in a purely functional manner?

Define a record S containing your state variables.

Write a pure function f: S -> S representing one tick of the  
system clock.

Then write

	let rec run f S = 
		let S' = f S in
		if S' = S then S
		else run f S'
	in 
	run f S0

Note it may never terminate, it isn't hard to build
an oscillator :)

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[Oliver Bandel]

On Sun, Feb 05, 2006 at 01:29:06PM +1100, skaller wrote:
> On Sat, 2006-02-04 at 22:19 +0100, Oliver Bandel wrote:
> > Hello,
> > 
> > 
> > how to implement a simple non-trivial machine (Heinz von Foerster)
> > in a purely functional manner?
> 
> Define a record S containing your state variables.

Is it necessary to have state-variables in a record?
Is it then (with records) functional implementation?!

> 
> Write a pure function f: S -> S representing one tick of the  
> system clock.

Hmhhh.... ok, I see.

But I'm not clear about how to write this function "f",
because it needs mutual recursion...
In a purely impeative way I think i woulf find a solution,
but thinking about it in Ocaml => blackout. ;-(


> 
> Then write
> 
> 	let rec run f S = 
> 		let S' = f S in
> 		if S' = S then S
> 		else run f S'
> 	in 
> 	run f S0
> 
> Note it may never terminate, it isn't hard to build
> an oscillator :)

Well, the run-function is not what I was looking for, because
the loop is intended to work again and again, so, it is not
necessary to have the if-then stuff inside: each clock
cycle reads in a new input-value and calculates a new output value
and then calls itself again...

and inside "f" there also is a feedback.

See the second picture in the jpeg-file:

    http://www.belug.org/~ob/struktur-grafisch.jpg



Ciao,
   Oliver

Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[skaller]

On Sun, 2006-02-05 at 05:16 +0100, Oliver Bandel wrote:

> But I'm not clear about how to write this function "f",
> because it needs mutual recursion...

No it doesn't, not even with feedback, because your
system is CLOCKED.

A simple model is: you have a collection of
chips with inputs and outputs. In phase one,
calculate the ouputs from the inputs.

In phase 2, you have a circuit board, representing
the wiring, this is a function that copies the outputs
of all the chip to their inputs, following the
wiring diagram. That's where the feedback comes in.

If you want to know how to make a subcircuit
do the feedback *internally* on one clock,
there is a simple answer and a hard one.

The simple answer is YOU CANT. Circuits are
monolithic.

The hard answer is .. you can have multiple
clocks, synchronised by a master clock. 
The implementation is simple .. a clock is
just a counter that writes TRUE when it is zero
and FALSE otherwise.

Then you invent a thing called a LATCH, which
is like wire, except it holds the output
stable and ignores the input UNLESS a special
ENABLE input is True. That's connected to your counter.

Basically .. you're asking hard questions about how
to design synchronous circuits. Don't expect a clocked
circuit to just be a simple composition of functions.
The functions get very complicated -- otherwise circuit
designers wouldn't have a job :)

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[Bill Wood]

On Sun, 2006-02-05 at 05:16 +0100, Oliver Bandel wrote:
   . . .
> Is it necessary to have state-variables in a record?
> Is it then (with records) functional implementation?!

If I understand your problem correctly, you're looking for a way to
model a synchronous dataflow network in OCaml.  To do this, I think you
need a global state to capture the simultaneous presence of data tokens
on each input of each function in your network.

The record mentioned above could contain a field for each input line; at
the next tick of the clock the functions are applied to their inputs,
and their outputs then fill in fields of the record corresponding to the
next set of inputs.  The dataflow aspect then manifests as the necessity
to get new values from the "x" input line, for there's no other way to
set that field in the next record.

This approach brings into sharp focus the initialization problem --
initially, there are no inputs on the "e" inputs to either block "A" or
"B".  Thus you have to specify how a block fires with one or more
undefined inputs.  You might model this by defining the type of data
running around the system to be something like "mydata option", and then
define how the various functions act when one or more inputs are "None".
Finally, the initial state record would have "None" in each field
corresponding to "no input available".
   . . .
> But I'm not clear about how to write this function "f",
> because it needs mutual recursion...
> In a purely impeative way I think i woulf find a solution,
> but thinking about it in Ocaml => blackout. ;-(

By using the state record you avoid having to write the block functions
as direct mutual recursions; instead, all the functions take the state
record as input and together (along with the input stream) define the
next state record.
   . . .
> and inside "f" there also is a feedback.

This approach takes care of the feedback at the expense of having to
model each block as operating with one or more inputs latched low, say,
until upstream functions finally supply data.

 -- Bill Wood

Re: [Caml-list] From a recursive circuit to a functional/recursiveOCaml-code...

[Frédéric Gava]

> If I understand your problem correctly, you're looking for a way to
> model a synchronous dataflow network in OCaml.

Peraps, you should read these works:
http://www-spi.lip6.fr/~mandel/rml

http://www.lri.fr/~pouzet/lucid-synchrone

http://www.lri.fr/~pouzet/SystemesSynchrones.html

Bon WE,
Frédéric Gava

Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[Oliver Bandel]

On Sat, Feb 04, 2006 at 10:19:43PM +0100, Oliver Bandel wrote:
> 
> Hello,
> 
> 
> how to implement a simple non-trivial machine (Heinz von Foerster)
> in a purely functional manner?
[...]

Some information about HvF:

    http://www.univie.ac.at/constructivism/HvF.htm



Ciao,
   Oliver

Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[Oliver Bandel]

On Sun, Feb 05, 2006 at 04:42:47PM +1100, skaller wrote:
> On Sun, 2006-02-05 at 05:16 +0100, Oliver Bandel wrote:
> 
> > But I'm not clear about how to write this function "f",
> > because it needs mutual recursion...
> 
> No it doesn't, not even with feedback, because your
> system is CLOCKED.

OK, a clocked circuit.
But in the non-trivial machine example,
not all operators are clocked.

The hint with the clock is good, HvF has not
expplicitly mentioned, which thing is cloecked
in the block diagram.
But I think it is funcion_C (the "C" in the picture),
because it is round and the other operators are in square.
And this is the only part, which can be critical, because of the
feedback.

Maybe this (a cirlce) is american (and maybe old) notation of a clocked thingy?
When looking at circuits I would have seen different symbols than
squares and cirlces.

I programmed a version with a record-type and got different
results than I found in a paper about the non-trivial machine (NTM).

So there may be a problem of wrong timing, so that my program
does not the same as it was meant by the block diagram of the
circuit.


[...]
> Basically .. you're asking hard questions about how
> to design synchronous circuits. Don't expect a clocked
> circuit to just be a simple composition of functions.

Well... IMHO the problem here is, when which function get's
which value. If it is time n -1, n or n+1 ?!


> The functions get very complicated -- otherwise circuit
> designers wouldn't have a job :)

Well, I doubt that for the simple NTM the functions
will get too complicated.

Here follows my implementation of the NTM, but it creates
different results than I saw in examples in papers,
so it seems the initial state is not there at the correct time.
So I have to rewrite the code.
Or I should use explicit timing, using specialized functions
or so...?!


(* ============================================================= *)

type state_t = { st_e: int option; st_u: int option }

let function_A x1 x2 = x1 + x2
let rec function_B x e = x + e
let function_C u = u + 3


let initialize() = 0 (* initial value, could also be a ransom value... :) *)

let initial_state () = { st_e = None; st_u = None }

let get_e state = match state.st_e with Some x -> x | _ -> initialize()
let get_u state = match state.st_u with Some x -> x | _ -> initialize()


let _ =
  let rec calc state =
    let inval = int_of_string (read_line())
    in
      let u = function_B inval (get_e state)
      and e = function_C (get_u state)
      and outval = function_A inval (get_e state)
      in
        Printf.printf "%d => %d \t e: %d u: %d \n" inval outval e u;
        calc { st_u = Some u; st_e = Some e }
  in
    calc (initial_state2()) (* yes, I like this recursive style: I can set starting state here. :) *)
      
(* ============================================================= *)

Ciao,
   Oliver

Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[skaller]

On Sun, 2006-02-05 at 15:17 +0100, Oliver Bandel wrote:

Looking at 

http://www.belug.org/~ob/struktur-grafisch.jpg

the bottom diagram, I would do this:

type state = { e:t; u:t }

for some type t I don't know about, possibly the types
are different, but this will do for exposition.

You also have arrows

	a: t * t -> t
	b: t * t -> t
	c: t -> t

So the clock function is simply

	let step (s:state) x =
	{ s with 
		e = c s.u;
		u = b (x, s.e)
	} 
	in s, a (x, s.e)

This function accepts the state and a new input x,
and returns the state and the output y. 

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[Oliver Bandel]

On Mon, Feb 06, 2006 at 03:05:45AM +1100, skaller wrote:
> On Sun, 2006-02-05 at 15:17 +0100, Oliver Bandel wrote:
> 
> Looking at 
> 
> http://www.belug.org/~ob/struktur-grafisch.jpg
> 
> the bottom diagram, I would do this:
> 
> type state = { e:t; u:t }
> 
> for some type t I don't know about, possibly the types
> are different, but this will do for exposition.
> 
> You also have arrows
> 
> 	a: t * t -> t
> 	b: t * t -> t
> 	c: t -> t
[...]


Ah, OK, that's fine to start with the type! :)

Starting the task with the type clarifies a lot! :)



> 
> So the clock function is simply
> 
> 	let step (s:state) x =
> 	{ s with 
> 		e = c s.u;
> 		u = b (x, s.e)
> 	} 
> 	in s, a (x, s.e)

OK, that's nice... I had forgotten how (but knew that I once knew
that it must be possible) to make a functional record-update-copy.
The "with" keyword is a fine thing. :)
Looks so much smaller the code, much nicer than the let...in stuff :)


> 
> This function accepts the state and a new input x,
> and returns the state and the output y. 

OK, I will explore it.

Thanks.


Ciao,
   Oliver

Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[Oliver Bandel]

On Sat, Feb 04, 2006 at 10:19:43PM +0100, Oliver Bandel wrote:
> 
> Hello,
> 

dito ;-)


> 
> how to implement a simple non-trivial machine (Heinz von Foerster)
> in a purely functional manner?
> 
> With functional/recursive OCaml code?
> 
> I had written a mail with attachement (which contains a
> jpeg with the structure of the circuit), but it seems it
> was blocked or filtered away by the OCaml mailinglist software?!
> 
> So I try to give it as some formulas:
> 
> 
> let u = func_B x e
> let e = func_C u
> let y = func_A x
> 

I started with the wrong things in mind, sorry!

I have picked the original work (the picture I put on the web
was from somwhere else, not the original) from HvF and found
the following description:

  
   A is an operator/function that works like a trivial machine
   B is an operator/function that works like a trivial machine
   c is the internal state!


So it should be possible to have only c as a state variable and all
other stuff will be derived from the input x and the internal
state c via the functions/operators A and B.


Sorry for the wrong start, it was too long ago when I looked
into the original work! :(

So, now the direction is different.


But nevertheless thanks for all your efforts on helping with
implementing it in OCaml. :)

Regards,
   Oliver

Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[Oliver Bandel]

Hello Bill,


On Sun, Feb 05, 2006 at 04:22:16PM -0600, Bill Wood wrote:
> This is a follow-up of my earlier (apologetic) post to you.  After
> reading your post stating that the C block was supposed to be an
> internal memory, I thought about how my model would have to be changed
> to get the right behavior of the C block.


Well, after I saw my fault of forgetting and then have re-read
HvF's papers, I started with the type (I learned that this
 really helps in design... this was (one of) my insight(s) for
 tonight... well, that is the reason why Simon J. Thompson
 in his Haskell book often started with the type-stuff...
 ...hey, this is the overall-structure, which helps in design
 more than simply writing down the idea of the algorithm!)
of the trivial machine and right after it with the
structure of the non-trivial machine.

With a block diagram and the attempt to start with the types
I got the following:
   (to mention: in the original HvF's graphic
    A is called F
    B is called Z
    C is called z
    u is called z'
    x is called x
    y is called y

       ... I can put it on the websrver also if someone is interested.)


   The I have created the following types:

   F (formerly A)  has type:      input_t -> state_t -> output_t
   Z (formerly B)  has type:      input_t -> state_t -> state_t
   z               has type:      state_t -> state_t


  Zjese are the ingreidents of the NTM,
  but looked from the outside (black box !!)
  it has the type:

     input_t -> output_t


I thought about what HvF meant, and then I got it:
When he speaks about the function F (formerly A)
this is the function that makes the calculation
form intput-value to output-value, but it's NOT ONE
trivial machine... the internal state switches between
some trivial machines, and the function that does
the switches is the Z (formerly B).

So, even if you have only simple/stupid machines
that are - in functional programming paradigm's language -
simple mappings between input and output - so this is
what we have as a function (or operator) in a functional language,
even if these stupid machines are underlying, the
NTM creates complexity by internally swiching between
some of these machines.

So, the internal state is used as a selector like in
a cicruit it would be a multiplexor: switch between
already existing functionality/channel/...

If you don't know how it behaves, you will have the problem
that you can't determine what's going on only from the
outside.

It was amazing to see the results of your machine!
It showed the complexity of this simple circuit much better
than only using integer values and do some operations on them.

When generalizing this machines (what I already had in mind,
but only now can think abouzt, since I used the attempt
with the general typing-stuff) it could be a lot of fun
to work with them and research on this, I think. :)


The next fine thing I then saw was: hey, to create the
NTM as a simple (from the outside, looking at the type)
mapping from
    input_t -> output_t
I have to use more input.... e.g. an array of TM's
(trivial machines),  which then internally (by the internal state)
will be selected as the mapping which will be active,
I saw: well, that's why the functional programing is so fine! :)

I can use arrays and functions and such stuff,
give it as arguments/parmeters to a function
and what do I get as a result?
A function. :)

Hey, again and again I see: this functional programming is
soo cool and such a wonderful thing... hey.... wow! :)

No pointer-horror... :)

I don't know if this mazing feeling one day will decay...
... for me it's always again amazing. maybe because
I started with Basic, then used C, then Perl, and now I'm here
in wonderland! :)


OK,
  it's better to stop now, if not... the size of this mail
  may get too big. ;-)


Sorry, not answering to all you wrote then, but well,
to late for today.... and I wan to code something,
before I go to bed. ;-)

Maybe more comments are following. :)

Ciao,
   Oliver

Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[Oliver Bandel]

On Mon, Feb 06, 2006 at 12:23:55AM +0100, Oliver Bandel wrote:
[...]
> Hey, again and again I see: this functional programming is
> soo cool and such a wonderful thing... hey.... wow! :)
> 
> No pointer-horror... :)
> 
> I don't know if this mazing feeling one day will decay...
[...]

"mazing" should be "amazing"

only one of many typos.... sorry... it's late and some beers... ;-)

Ciao,
   Oliver

Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[skaller]

On Mon, 2006-02-06 at 00:23 +0100, Oliver Bandel wrote:
> Hello Bill,

> I thought about what HvF meant, and then I got it:
> When he speaks about the function F (formerly A)
> this is the function that makes the calculation
> form intput-value to output-value, but it's NOT ONE
> trivial machine... the internal state switches between
> some trivial machines, and the function that does
> the switches is the Z (formerly B).

That's right. My original code showed how to wrap a clocked
machine into a pure, unclocked functional unit, and you can
do this in the abstract as follows:

Given a state transformer 

	step: S * I -> S * O

where S is internal state, I is input, and O is output,
and an equality comparison function:

	eq: S -> S -> bool

and a initialisation function S for internal state

	reset: unit -> S

You do this:

let run 
  (step:'state * 'input -> 'state * 'output) 
  (reset:unit->'state)
  (eq:'state->'state->bool)
  (i:'input) 
: 'output =
	let rec clock s =
		let s',o = step (s, i) in
		if eq s s' then o
		else clock s' (* TAIL REC SELF CALL *)
	in clock (reset ())

This algorithm is fully polymorphic. In particular

let f i = run step_f reset_f eq_f i

leaves f as an ordinary old function

	f: 'input -> 'output

by currying .. you can then use it as a functional unit 
in another clocked circuit. 

BTW: you might want to package
up the machine specification into a single record and use
that as an argument:

type ('state,'input,'output) machine = {
  step:'state * 'input -> 'state * 'output;
  reset:unit->'state;
  eq:'state->'state->bool
}

With some modification you can then write the nice
function:

let make_function_from_machine machine i =
	run machine.step machine.reset machine.eq i

and then you can just say

	let f i = make_function_from_machine m i
	(* value restriction? *)

Use 

	let j = f i in ...

to use it (same as an ordinary function). This is just
packaging but it emphasises the transformation

	make_unclocked_function_from_machine:
		('state, 'input, 'output) machine 
		->
		('input -> output)

converts a machine into a function.

OH .. you may think this is not imperative .. 

Felix (and I think GHC) will convert that machine simulation into an 
imperative loop and use mutable variables as an optimisation.

It can (and will, unless there is a bug) do that because of 
the tail rec self call of the function clock.

Ocaml might choose not to since write barrier is more
expensive that spawning variables on the heap (not sure).

So in the end .. the code is equivalent to a loop with
a mutator, and some FPL's may even implement it as such.

The IMPORTANT (IMHO) difference is referential transparency:
in the function

  (step:'state * 'input -> 'state * 'output) 

there is no chance of modifying an input and accidentally
using the modified value instead of the original one,
just because you happened to run that part of the calculation
too early. Referential transparency says that, apart from issues
of termination and dependency, it doesn't matter WHEN you
execute a subcalculation.

So its better! Right! ? Nope!! There is an equivalent bug
in FPLs which is just as disastrous and easy to do:
you can accidentally HIDE a variable with a same named
temporary, and have the right variable name bind to the
wrong variable. So where you place you bindings is just
as important in an FPL as how you sequence your mutations
in a procedural language.

Functional code IS NOT better than procedural code -- IMHO.
A judicious mix is best, and a way to control it.
Ocaml provides very poor** control of the mix. Haskell has
things like State Monads that provide a more structured
way to mix functional and procedural code. But no one
really knows how to do this 'The Right Way (tm)' yet.

[But it is miles better than C or C++ in general because it provides
a fairly balanced set of both functional and procedural
constructions, which C and C++ do not -- apart from other
issues like garbage collectors, type systems, etc :]

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[Oliver Bandel]

On Sun, Feb 05, 2006 at 04:42:47PM +1100, skaller wrote:
> On Sun, 2006-02-05 at 05:16 +0100, Oliver Bandel wrote:
> 
> > But I'm not clear about how to write this function "f",
> > because it needs mutual recursion...
> 
> No it doesn't, not even with feedback, because your
> system is CLOCKED.
[...]

I need for this task one clock.
I can do a clock (in binary values) with true and false
or 1 and 0 or so with a variable.
I can do this with loops or functions that inverts their
last value (true -> false   and false -> true) with simple
toggling.
I then could use this value and do things depending on the value.

But this one clock I also can do with two mutual recursive
functions. Each one represents the work that must be done
in one state (or more precise: when switching from one state to the
other).
So with two functions that call each other recursively I can
do a toggling value (state machine with two states) by
func_x1 calling func_x2 and then func_x2 calling func_x1.

Another reason why I started intuitively with a recursive
definition of my code here.



Ciao,
   Oliver

Re: [Caml-list] From a recursive circuit to a functional/recursive OCaml-code...

[Oliver Bandel]

On Mon, Feb 06, 2006 at 12:52:08PM +0100, Oliver Bandel wrote:
> On Sun, Feb 05, 2006 at 04:42:47PM +1100, skaller wrote:
> > On Sun, 2006-02-05 at 05:16 +0100, Oliver Bandel wrote:
> > 
> > > But I'm not clear about how to write this function "f",
> > > because it needs mutual recursion...
> > 
> > No it doesn't, not even with feedback, because your
> > system is CLOCKED.
> [...]
> 
> I need for this task one clock.
> I can do a clock (in binary values) with true and false
> or 1 and 0 or so with a variable.
> I can do this with loops or functions that inverts their
> last value (true -> false   and false -> true) with simple
> toggling.
> I then could use this value and do things depending on the value.

Following his paper

"Prinzipien der Selbstorganisation im sozialen und
    betriebswirtschaftlichen Bereich"
          (Hvf: Wissen und Gewissen, Ffm 1993)
             
 (title of the english vesrion: "Principles of Self-Organization in Socio-Managerial Context")

I had written this simple inplementation, strictly following
his paper:
  http://me.in-berlin.de/~first/nichttriviale.ml.html

Ciao,
   Oliver