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

Thu Jun 3 18:13:38 PDT 2004

As a way of experimenting this, I created two similar actors.
actor.lib.hoc.ApplyFunction takes a function closure and applies it to its 
inputs.
actor.lib.hoc.ApplyFunctionOverSequences takes a function closure (possibly 
with array types as input or output) and everywhere where it sees an 
ArrayType it assumes that it will receive the array as a sequence of inputs.

So, the ApplyFunction actor sort of looks like the higher order function:
(a -> b) -> <a> -> <b>

And the ApplyFunctionOverSequences actor looks like the higher order function:
([a] -> [b]) -> <a> -> <b>
or
([a] -> b) -> <a> -> <b>
or
(a -> [b]) -> <a> -> <b>

depending on what kind of function you give it..  Currently OverSequences 
uses SDF rate parameter
to figure out how much data to consume:  it would be nicer if this was 
specified in
the signature of the function, but then we would need arrays to have 
sizes..  (a perfect
case for when this is useful).

You can check out actor/lib/hoc/demo/ApplyFFT for an example of how
it compares to building the actor by hand.

Steve

At 08:12 PM 5/25/2004, Edward A Lee wrote:

>Bertram and Liying:
>
>You have hit upon something that has bothered me for some time,
>and have expressed it better than I ever did...  There are several
>examples of this tension in the Ptolemy II library.  E.g., the
>FFT actor has type <double> --> <double>.  Why isn't it
><[double]> --> <[double]>?  It could just as well be, and I don't
>know of any way to choose between these...
>
>In practice, we've relied on just making a choice, clearly documenting
>it, and then judiciously using SequenceToArray and ArrayToSequence actors.
>These have type <a> --> <[a]> and <[a]> --> <a>.  But this solution has its
>problems.  For SDF, the ArrayToSequence actor needs to set a static
>input array size, but this is not represented in the type system...
>Similarly, SequenceToArray has a parameter arrayLength that has to be
>static for SDF.
>
>Steve Neuendorffer introduced a solution to this in version 4.0 where
>parameters that affect scheduling can change dynamically, and it is
>well-defined when schedules have to be recomputed, but this still
>doesn't help in deciding whether types should be streams or
>streams of arrays...
>
>The short answer is that we don't have to conclude
>that <<a>> == <a>.  We can instead insist that ArrayToSequence
>or SequenceToArray be used to convert types, which is what the
>type system does today (modulo type inference, which can create
>unexpected answers if you don't know whether you are dealing
>with <<a>> or <a>).
>
>But the long answer is harder...  I don't have it...
>Interesting question though...
>
>Edward
>
>
>
>At 01:08 PM 5/25/2004 -0700, Bertram Ludaescher wrote:
>
>>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
>>
>>_______________________________________________
>>kepler-dev mailing list
>>kepler-dev at ecoinformatics.org
>>http://www.ecoinformatics.org/mailman/listinfo/kepler-dev
>
>------------
>Edward A. Lee, Professor
>518 Cory Hall, UC Berkeley, Berkeley, CA 94720
>phone: 510-642-0455, fax: 510-642-2739
>eal at eecs.Berkeley.EDU, http://ptolemy.eecs.berkeley.edu/~eal
>
>
>----------------------------------------------------------------------------
>Posted to the ptolemy-hackers mailing list.  Please send administrative
>mail for this list to: ptolemy-hackers-request at ptolemy.eecs.berkeley.edu