English version
Accueil     Ŕ propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis ŕ jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml ŕ l'adresse ocaml.org.

Browse thread
Sources, sinks, and unbound parameter types
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2008-03-24 (21:56)
From: Dario Teixeira <darioteixeira@y...>
Subject: Sources, sinks, and unbound parameter types

I'm looking for a way to express the composition of functional components
in a tree-like data structure.  Each node in the tree is either:

  a) a Source, producing values "out of nowhere": unit -> 'a
  b) a Sink, end point of the tree: 'b -> unit
  c) a Processor, transforming values from one type to another: 'c -> 'd

The Ocaml type that represents a node is as follows: (pretty
straightforward, though I wonder if there's a way to explicitly
say that "Source is of 'a -> 'b where 'a must be of type unit")

type ('a, 'b) node_t =
        | Source of (unit -> 'b)
        | Sink of ('a -> unit)
        | Processor of ('a -> 'b)

In addition, there are two types of connectors linking these nodes in the tree:

  a) a Pipe, connecting one node that outputs a value of type 'a into
     another that inputs an 'a.
  b) a Splitter, essentially like a Pipe, but able to feed the same
     value into multiple inputs.

If you'll pardon the ASCII art, here's a diagram of one such simple tree:

|                        ===========
|                        | source1 | 
|                        ===========
|                             |
|                             |
|                             O Pipe
|                             |
|                             |
|                        ============
|                        | process1 |
|                        ============
|                             |
|                             |
|             ----------------O----------------
|             |           Splitter            |
|             |                               |
|        ===========                     ===========
|        |  sink1  |                     |  sink2  |
|        ===========                     ===========

Where each component node can, for example, be defined as follows:

let source1 () = 10
let process1 n = 2.0 *. (float_of_int n)
let sink1 x = Printf.printf "Sink1: %f\n" x
let sink2 x = Printf.printf "Sink2: %f\n" x

To define the tree type, I would like to express something like the code
below.  Note that I am trying to get to the compiler to statically enforce
that outputs and inputs are correctly matched type-wise.

type ('a, 'b) tree_t =
        | Node of ('a, 'b) node_t
        | Pipe of ('a, 'c) tree_t * ('c, 'b) tree_t
        | Splitter of ('a, 'c) tree_t * ('c, 'b) tree_t list

The code above obviously won't work because of the unbound type parameter 'c.
(Also, please ignore for now the fact it allows splitters with an empty
output list -- that can easily be circumvented).

So, my question is if there is any way to express what I want?  I guess there
is a solution involving the creation of a syntax extension, but I'm looking
for a pure Ocaml way.

Thanks in advance for your time!
Best regards,
Dario Teixeira

Rise to the challenge for Sport Relief with Yahoo! For Good