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

[skaller <skaller@users.sourceforge.net>]

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