[kepler-dev] question on typing processes and higher-order fu

[kepler-dev] question on typing processes and higher-order fu

Post by Ed.Willin » Thu, 27 May 2004 19:55:47


Hi Edward, Bertram, Liying


Surely <double> --> <double> is just wrong. It uses the COSSAP
fudge to support Arrays in a non-Array tool via accidental sequences.
Any type system that requires exaplanatory text, (use N successive
samples) is not a type system.

For the proposed WDL, Waveform Description Language,
( http://www.yqcomputer.com/ )
I identified three distinct forms of array.

A conventional array (distributed over adjacent memory addresses)
A spatial array (distributed in space over a multi-port/multiple ports)
A sequential array (distributed in time over sequential samples)

(There is no limitation to 1D, provided the rasterising policy is
well defined.)

An FFT specification therefore is always T1[N} --> T2[N].
Particular specialisations may choose different forms of array distribution.

Once these three forms are treated uniformly, it is also very easy
to do automated conversions between them. For instance in Caltrop,
each conversion would be just an 'assignment', with the distribution
being an externally inferable property. In Ptolemy the multi-axis
type lattice needed for fixed point must be extended with a further
axis for the array-form lattice.

Regards

Ed Willink

------------------------------------------------------------------------
E.D.Willink, Email: mailto: XXXX@XXXXX.COM
Thales Research and Technology (UK) Ltd, Tel: +44 118 923 8278 (direct)
Worton Drive, or +44 118 986 8601 (ext 8278)
Worton Grange Business Park, Fax: +44 118 923 8399
Reading, RG2 0SB
ENGLAND http://www.yqcomputer.com/
------------------------------------------------------------------------

----------------------------------------------------------------------------
Posted to the ptolemy-hackers mailing list. Please send administrative
mail for this list to: XXXX@XXXXX.COM
 
 
 

[kepler-dev] question on typing processes and higher-order fu

Post by Ed.Willin » Thu, 27 May 2004 23:19:15

i Edward

Unfortunately, I'm not well-versed in 'dependent type system's
so I cannot comment on that.

I don't doubt that a set of contradictory type constriants can be
set up, but that's a detectable error, that can be made in a
simpler system too.

I see type inference as a multi-axis lattice problem, rather than
the single axis approach of Ptolemy. Typical axes are:

minimum value
maximum value
fixed-point epsilon
floating-point epsilon
overflow behaviour (a small enumeration)
rounding behaviour (a small enumeration)
overflow bit-truth (2-valued)
rounding bit-truth (2-valued)
is-complex
each array dimension
array form (a small enumeration)

Each axis is orthogonal and therefore amenable to independent lattice
or number line maximisation/minimisation as appropriate. Whereas in
a single axis system valid solutions satisfy e.g a GE operator
consistently, in a multi-axis system valid solutions must satisfy
a GE operator on all axes. Perhaps the GT case on one axis, LT on
another is what you mean by undecideable. With orthogonal axes
it's just insoluble.

I think that it may be the failure to move from single-axis in
Ptolemy that may be creating a variety of problems. It was certainly
the case that the Ptrolemy lattice had to double-up for Complex
variants of all scalar types.

My ptolemy.math.Quantization contribution makes some progress in this
direction and allowed for independent treatment of some of the above
axes. Ultimately the work stalled through lack of response to a number
of emails.

C++ (and I think Fortran) are examples of conventional
languages where array dimensions can participate in the type
checking. If this is not part of the type system then I'm
not sure what you mean.

Ultimately if 'dependent type system' does mean that
dimensioned arrays are difficult, it just means that
practical designs are difficult. We cannot run away
from it. FFT frame sizes must be type-checked.

Regards

Ed Willink

wdl.html)
distribution.

------------
Edward A. Lee, Professor
518 Cory Hall, UC Berkeley, Berkeley, CA 94720
phone: 510-642-0455, fax: 510-642-2739
XXXX@XXXXX.COM , http://ptolemy.eecs.berkeley.edu/~eal

----------------------------------------------------------------------------
Posted to the ptolemy-hackers mailing list. Please send administrative
mail for this list to: XXXX@XXXXX.COM

 
 
 

[kepler-dev] question on typing processes and higher-order fu

Post by Ed.Willin » Thu, 03 Jun 2004 17:47:06

Hi Edward

Edwasrd Willink wrote

Edward Lee wrote

I don't think we got to the bottom of this, getting side tracked into
axes of type lattices.

If <double> --> <double> is the signature of an FFT, what is the output?

Does the FFT fire after the first token to do an FFT1, then second to do
FFT2,
then 4 to do FFT4 etc, or after every 64 to do FFT64? Whichever; the output
can only really be a stream of double (complex surely) for FFT1.

I think there is a confusion between the computation firing signature

double[64] -> double[64]

and the communication context which might indeed be

<double> --> <double>

The two are only compatible after a helpful type-inference system has
inserted the conversions

<double> --> <double[64]>
and
<double[64]> --> <double>

(The implementation option of address/space/time distribution of the
64 elements remains open.)

A helpful system may do this automatically, however a type-safe system
must require user intervention to avoid accidental and undiagnosed
interconnection of skewed frame boundaries. You agreed to my suggestion
a couple of yeasrs ago that the Prolemy type system should have
two modes: helpful/safe.

If Ptolemy is to approach a consistent specification of behaviour rather
than yet another set of intuitions, this conversion should not be automatic.

When seen as a conversion, it ceases to be part of the FFT, just another
part
of the type system.

It might even be that a smart code generator could exploit a stream
optimised FFT implementation to weave the conversions into the computation,
but that is a code generation/implementation issue that should only
appear on the mapping of a Ptolemy diagram to a target platform.

Regards

Ed Willink

------------------------------------------------------------------------
E.D.Willink, Email: mailto: XXXX@XXXXX.COM
Thales Research and Technology (UK) Ltd, Tel: +44 118 923 8278 (direct)
Worton Drive, or +44 118 986 8601 (ext 8278)
Worton Grange Business Park, Fax: +44 118 923 8399
Reading, RG2 0SB
ENGLAND http://www.yqcomputer.com/
------------------------------------------------------------------------

----------------------------------------------------------------------------
Posted to the ptolemy-hackers mailing list. Please send administrative
mail for this list to: XXXX@XXXXX.COM