Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
how to implement generic operators
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-10-24 (05:20)
From: skaller <skaller@u...>
Subject: how to implement generic operators
I am looking for some ideas on how to implement generic

To explain what I mean by that: consider some operations
such as: fold, map, iter. In Ocaml these are polymorphic.

A generic iter would be something like:

	iter f [1; 2.0; "hello"] 


	f 1; f 2.0; f "hello"

Now, within Ocaml itself this doesn't make sense. However
my question relates to how to *implement* such an operation
in a compiler. In that case, the list above is a list
of *terms* not values -- so there is no typing problem,
provided the reduction rules ground at compile time.

Now for the problem: there are a LOT of such operators.
Here is another example:

	compose [f; g; h; k]

and another 

	ravel [f; g; h; k]

which converts a product of functions to a function of products.

I want the USER to be able to define these operations,
and provide only a minimal set of combinators in the compiler.

Obviously, one of the key combinators is fold, since all of
the above operations suffer from the problem that whilst
the user can .. as in Ocaml .. easily define a binary version
of the operator .. there is no way in the target language
to handle *lists* of arguments: the compiler itself can do
so easily by using Ocaml lists of terms, but the user
cannot modify the compiler to add new combinators.

To make the problem concrete: suppose I would like
to avoid:

	Compose of term list
	Ravel of term list

each of which uses much the same reduction rules: it expands
to some tree or using more basic binary primitives .. 
I would clearly need some representation like:

	Assoc of op * term list

and then some kind of fold which works for all different binary op,
where now 'op' is defined by the user.

So crudely the question is: what is the representation of 'op'
required so the generic fold can create a wide class of
generic n-ary operations from binary ones?

Note the data for op will be obtained by parsing in the input
program, so cannot consist of just a fixed list of variants.

Crudely .. I am looking for a way to declare a function
which instead of having 'two' arguments, can have n.
All the arguments must be the same KIND so their terms
have the same type, but the arguments obviously will not
have the same type.

Hope this makes sense .. I have a feeling MetaOcaml can do this already.

John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: