[kepler-dev] question on typing processes and higher-order functions a la map

[Bertram Ludaescher]

Hi:

Liying Sui and I recently came across the following typing problem:

Consider an actor, say "factors" which computes for a given int I, all
the prime factors of I. For example factors(20) = [2,2,5]

Thus, the signature of factors is:

	factors :: int --> [int] 

Now assume factors is to be applied on a stream <x1, x2, x3, ...> of
integers, denoted <int>

It seems tempting to view the *process* Factors that is so created as
applying the higher-order map function to factors, i.e., 
	Factors = map(factors)

There are some interesting typing issues. Let's say map has the
following type on streams:

	map :: (a-->b) --> <a> --> <b> 

That is, map takes a function of type (a-->b) and a stream of a's
(denoted <a>) and returns a stream of b's.
Therefore the type of the Factors process can be determined to be

	Factors :: <int> --> < [int] >	  

Example: Factors( <4, 6, 10, ... > ) = < [2,2], [2,3], [2,5], ... >

So far so good -- no information is lost.

It seems, however, that in practise sometimes  another process is
created: 
	Factors'( <4, 6, 10, ... > ) = < 2,2,2,3,2,5, ... >

Clearly this process Factors' does lose some information (the grouping
of result tuples into list of prime factors). While for this specific
example, Factors' is not desirable, such a "flattening" behavior seems
to be used in practise: 

Let say we change our original function factors to produce not a list
of ints, but a stream of them:
 
	factors' :: int --> <int> 

This correspond to a token consumption/production pattern of " 1:* "
(for each input token, we might get multiple output tokens).

Is it correct that in Ptolemy II using factors' with an SDF director
produces a process Factors' on streams that has the signature:

	Factors' :: <int> --> <int> 

In order to make this behavior type-correct it seems we may have to
say that <<int>> = <int>, because we get 

	map(factors') = Factors'

and the former has the type

	map(factors') ::  <int> --> < <int> >

Note that the type of map(factors') is obtained by using the general
type of map above: 

	map :: (a-->b) --> <a> --> <b> 

and the applying this to factors' :: int --> <int>
(hence a = int and b = <int>)

So if indeed Factors' is of the said type we must accept (whether we
like it or not ;-) that <<int>> = <int> (or in general, nesting
streams in this way yields a "flat" stream).

Comments?? 
Does Ptolemy II with an SDF director and an actor of type
	myactor :: a --> <b> 
produce a process
	MYACTOR :: <a> --> <b> 
which thus can be explained as a "special map" over streams with the
type identity <<b>> = <b> ??

Thanks in advance!

Bertram and Liying