how to implement generic operators

how to implement generic operators

[skaller]

I am looking for some ideas on how to implement generic
operators.

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++: http://felix.sf.net

Ant: [Caml-list] how to implement generic operators

[Martin Chabr]

I am not an expert and I am not a compiler or language
designer. I only use languages and I can only tell you
how I feel when I use one language or move to another
one.

I did some Prolog and some Python programming before I
moved to OCaml. In both Prolog and Python you can use
lists with mixed types as you suggest. I thing the
problem is not mixing types in a list, but what you
want to do with the data afterwards. Operators do
restrict data types.

I was surprised at first when I found out how OCaml
restricts lists. I was even more surprised when I
learned about the distinction between the integer and
floating operators (+ and * vs +. and *. etc.): Then I
learned about some problems with type inference in
Standard ML which uses overloaded operators. You have
to declare the types more in Standard ML than in
OCaml.

Now I got used to it and appreciate the clarity: types
in mixed expressions must always be converted to be
compatible with each other. No automatic conversion
where you wonder what will happen.

C# had collections of mixed types as well in the 1.x
version. Now, in the version 2.0 they have generics
and strong type checking and everybody seems to like
it, not having to do any type detection and casting.

Martin

--- skaller <skaller@users.sourceforge.net> wrote:

> I am looking for some ideas on how to implement
> generic
> operators.
> 
> 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++: http://felix.sf.net
> 
> _______________________________________________
> Caml-list mailing list. Subscription management:
>
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list:
> http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> 



	

	
		
___________________________________________________________ 
Gesendet von Yahoo! Mail - Jetzt mit 1GB Speicher kostenlos - Hier anmelden: http://mail.yahoo.de

Re: [Caml-list] how to implement generic operators

[Jacques Carette]

skaller wrote:

>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?
>  
>
You really need your operations to be left-associative for that to make 
sense... But in my toy interpreter for a subset of Maple (written in 
Ocaml), I have
type op = term -> term -> term * term
and then in the eval() function for a term, a case
   | Assoc ((f,init), l) -> List.fold_left f init l

f can be created from a term by applying a term-level lambda, so that 
when you ask for

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

>I have a feeling MetaOcaml can do this already.
>  
>
Yes and no.  Yes, it can be done by staging a very finely crafted 
evaluator.  But doing that is very, very difficult given the current 
state-of-the-art [typed PE for typed languages is hard].  Or merely 
difficult if you write everything CPS style.  But it is most definitely 
not something you get right out of the box.

Jacques C.

Re: Ant: [Caml-list] how to implement generic operators

[skaller]

On Mon, 2005-10-24 at 20:26 +0200, Martin Chabr wrote:

> I was surprised at first when I found out how OCaml
> restricts lists.

> Now I got used to it and appreciate the clarity: types
> in mixed expressions must always be converted to be
> compatible with each other. No automatic conversion
> where you wonder what will happen.

> C# had collections of mixed types as well in the 1.x
> version. Now, in the version 2.0 they have generics
> and strong type checking and everybody seems to like
> it, not having to do any type detection and casting.

The idea is to provide 'manifest' heterogeneity
like this:

iter print (1,2.0,"Hello");

which of course is just sugar for

print 1; print 2.0; print "Hello";

This will work in Felix because it supports overloading.
There is no loss of type safety, since each of the 
3 generated terms is independently type checked.

Internally, the Ocaml representation would be something like

Iter (print, [1;2.0;"Hello"])

and the reduction rule would be something like:

function 
| Iter (op, elts) -> fold_left 
  (fun (result, elt) -> seq (result, op elt)) nop elts

So basically this operation is just sugar which takes
advantage of 'ad hoc polymorphism' aka overloading to
allow the user to get 'free' nary operators.

Note that the second argument to 'iter', 
namely (1,2.0, "hello"), is a *tuple*. It is therefore
heterogenous automatically, but of fixed length.

In Ocaml the *representation* is a list of terms, all of
the same type, namely 'expression'.

What I wrote above using Iter variant will work just fine.
The problem is, I also need Compose, Ravel, ... and many MANY
others. There are far too many to encode all of them in the
compiler: a reasonable fixed subset will remain both incomplete
and a lot of work to encode.

So instead of encoding them all in the compiler, I want
to encode them in the standard library, parse them,
and write an interpreter in Ocaml to 'execute' the 
parsed encodings.

See Jacques Carette post and my response for more.

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

Re: [Caml-list] how to implement generic operators

[skaller]

On Mon, 2005-10-24 at 15:27 -0400, Jacques Carette wrote:
> skaller wrote:

> You really need your operations to be left-associative for that to make 
> sense... But in my toy interpreter for a subset of Maple (written in 
> Ocaml), I have
> type op = term -> term -> term * term
> and then in the eval() function for a term, a case
>    | Assoc ((f,init), l) -> List.fold_left f init l
> 
> f can be created from a term by applying a term-level lambda, 

I am already doing this for types. There is also a separate
programmable term evaluator however it works only on the syntax tree
(unbound terms).

My type term calculus has lambdas and products .. but no lists.
There is no real 'term' calculus (just ad hoc reduction
rules**).

Do you provide lists directly in the term calculus?
Or are they just constructed from products and sums?

It looks like I would have to

(1) provide a term calculator
(1a) extend the type calculator to support either lists
or
(1b) add sums and make sure recursion works

1a looks easier, clearly 1b is more general.

** the 'ad hoc' reduction rules are 'weak' things
like constant folding, plus some sophisticated
but very specialised rules for inlining and
substitution: there is no way I could really claim
this 'term calculator' I already have is a general
'calculus', in the same way that the type calculator is.


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

Re: Ant: [Caml-list] how to implement generic operators

[skaller]

On Mon, 2005-10-24 at 20:26 +0200, Martin Chabr wrote:

> I was surprised at first when I found out how OCaml
> restricts lists. I was even more surprised when I
> learned about the distinction between the integer and
> floating operators (+ and * vs +. and *. etc.): 

> Now I got used to it and appreciate the clarity: 

Felix is designed for people who, like you, are
a bit surprised at the lack of generics .. but 
unlike you are not so patient.. :)

It therefore provides something more C++ like in both
syntax and features, whilst still providing many
of the features of ML style FPLs like Ocaml.

Type inference is one of the things lost, since I'm
not smart enough to encode a type system supporting
both overloading and inference, nor figure out what
the consequences would be for the end user -- systems
with type inference typically produce lousy error messages,
so I'd guess developers of these systems don't themselves
know enough about how to properly track and report
inference conflicts (i.e. type errors) -- so there
is little hope of a good resolution at this time
for a system with both. G'Caml generics may solve this
problem by encapsulating the overloads in a way the compiler
can report type sane type errors.


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

Re: [Caml-list] how to implement generic operators

[Jacques Carette]

skaller wrote:

>Do you provide lists directly in the term calculus?
>Or are they just constructed from products and sums?
>  
>
Short answer: yes, lists are provided in the term calculus.

Long answer: Maple has no linked lists (ie lists based on nil and 
cons).  It has "automatically flattened n-tuples" - they are called 
"expression sequences".  When you see
(a list)               [a,b,c]
(a set)               {a,b,c}
(a function call) f(a,b,c)

all 3 contain the expression sequence a,b,c.  Two additional points:
1) expression sequences (and their contents) are uniquified [ie stored 
only once]
2) they are stored in contiguous memory, so that they are more 
array-like than list-like

While you may want your term language to support lists, supporting 
'flattened' n-tuples can be much simpler from a polymorphism point of 
view. The idea here is that a tagged datatype is just a pair tag + 
expression sequence, and you can defined all your polymorphic operators 
to "map into" the datatype by mapping onto the expression sequence.  
Experience shows that this is mightily convenient.  And most likely 
difficult as all #$%#$% to ``type''.

On the other hand, I was able to reflect this high degree of 
polymorphism in parts of my toy interpreter, where I could 'factor' a 
lot of my code quite nicely.  If only that 'tags' of an algebraic 
datatype were also first-class functions in Ocaml [as they are in 
Haskell], I would make my code considerably more elegant.

Jacques C.