Re: [Caml-list] More problems with memoization

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

On Tue, 2006-10-03 at 01:00 +0200, Andrej Bauer wrote:

> A recursive function _is_ the fixed point of a non-recursive one with an 
> "extra" argument. You may hide this fact if you wish, but I think it's 
> more honest to admit it to yourself. The "untied" version of fib has the 
> advantage that you can do many cool things to it: memoizing is just one 
> possibility.

There is, however, a good reason this is not practical in general:
for a recursion of N entities (either functions or polymorphic
variants in Ocaml can be 'open-recursioned') you need an 
extra N arguments .. and the result is unreadable, as well
as possibly incurring a performance hit.

I wonder if one can add compiler support: for example given

   let rec fib x = match x with
     | 0 -> 0
     | 1 -> 1
     | n -> fib (n - 1) + fib (n - 2)

The compiler silently generates:

   let @fib fib' x = match x with
     | 0 -> 0
     | 1 -> 1
     | n -> fib' (n - 1) + fib' (n - 2)

   let fib = make_rec @fib

and now you have fib as written .. but you ALSO can do:

   let fib = make_mem @fib

to create a memoised version. 

That's for one argument and can clearly be done easily
by the compiler (in fact, camlp4).

However the extension to multiple arguments is not clear. 
Maybe labelled arguments would help, perhaps using
a record.

Andrei said:

"You may hide this fact if you wish, but I think it's 
more honest to admit it to yourself."

but I think this is misleading: there's a good
reason NOT to open the recursions. There's a fundamental
principle of software design: the open/closed principle (OOSC)
which is not obeyed by either the closed or open form.

We need a form that is simultaneously closed and ready to
use but which is also open and amenable to extension.

FYI: the case that most interests me at the moment is neither
type recursion nor functional recursion -- I'm interested
in whether it is possible to design an open-recursive grammar,
this seems to need both recursive data types *and* recursive
functions in open/closed form.

Interestingly in this case I have actually implemented one
already, allowing Felix to extend it's own parser by combining
an Ocamlyacc parser with an executable RD parser .. but
this really isn't the same as systematic static extension
where, for example you write a basic grammar, and then
extensions to it.

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