Spreadsheets and programming languages

William Lovas wrote:

>
> You're not full of hot air -- and you're not the first person to notice
> that spreadsheets are a lot like functional programming.

But a lot more like dataflow programming! I have always looked with interest
to asynchronous dataflow languages, but I ask myself why almost nobody in
the world seems to be working at this. Wouldn't it be  to write "x=y+z"
where y and z are variables, and know that this invariant will always hold?

Using haskell and typeclasses it's not difficult to implement this idiom,
why is it so rarely seen?

V.

--
Please notice that my e-mail address has been altered to prevent spam

Vincenzo Ciancia wrote:
> William Lovas wrote:
>
> 
>
>
> But a lot more like dataflow programming! I have always looked with intere
st
> to asynchronous dataflow languages, but I ask myself why almost nobody in
> the world seems to be working at this. Wouldn't it be  to write "x=y+z
"
> where y and z are variables, and know that this invariant will always hold
?
>
> Using haskell and typeclasses it's not difficult to implement this idiom,
> why is it so rarely seen?

Could you post sample about this idea in haskell (using type classes)?

Or a pointer to something like this?

--
Gracjan

Gracjan Polak wrote:

>
> Could you post sample about this idea in haskell (using type classes)?
>
> Or a pointer to something like this?

I can easily point you to FRAN or YAMPA

http://www.haskell.org/yampa/

(in particular look at the example code in the tutorial) where type classes
are used to hide the implementation behind an arrow class instance - I
often think that one could write a module for time-varying values in
haskell, like IORefs in the sense that one can set and get these values
inside the IO monad (or in any other monad), but with operators a-la-FRAN
when creating the variables, however I usually don't get any further than
thinking a little about it :)

V.

--
Please notice that my e-mail address has been altered to prevent spam

Vincenzo Ciancia wrote:
> But a lot more like dataflow programming! I have always looked with intere
st
> to asynchronous dataflow languages, but I ask myself why almost nobody in
> the world seems to be working at this. Wouldn't it be  to write "x=y+z
"
> where y and z are variables, and know that this invariant will always hold?[/color
]

Lack of interesting results, probably - dataflow was one of *the* hypes
in, oh, as far back as the early 90ies, I think.

I can only speculate why the concept "didn't make it". Among the reasons
I can imagine, there are:
* doesn't scale well efficiency-wise
* doesn't modularize well for larger scales
* doesn't cover all important cases, so you need the old idioms anyway
* the old idioms work just as well as the proposed new ones

I'd be interested to hear what the problems really were though.
("Lack of funding" in itself doesn't count - that's just a symptom, not
a cause.)

Regards,
Jo

"Vincenzo Ciancia" <vincenzo_mlRE.MOVE@yahoo.it> escreveu na mensagem
news:woWud.283171$b5.13812266@news3.tin.it...
> William Lovas wrote:
> 
>
> But a lot more like dataflow programming! I have always looked with
interest
> to asynchronous dataflow languages, but I ask myself why almost nobody in
> the world seems to be working at this. Wouldn't it be  to write
"x=y+z"
> where y and z are variables, and know that this invariant will always
hold?

IIUC Mozart/Oz supports this with primitive operations.

> Using haskell and typeclasses it's not difficult to implement this idiom,
> why is it so rarely seen?
>
> V.
>
> --
> Please notice that my e-mail address has been altered to prevent spam
"Vincenzo Ciancia" <vincenzo_mlRE.MOVE@yahoo.it> escreveu na mensagem
news:woWud.283171$b5.13812266@news3.tin.it...
> William Lovas wrote:
> 
>
> But a lot more like dataflow programming! I have always looked with
interest
> to asynchronous dataflow languages, but I ask myself why almost nobody in
> the world seems to be working at this. Wouldn't it be  to write
"x=y+z"
> where y and z are variables, and know that this invariant will always
hold?

IIUC Mozart/Oz supports this with primitive operations.

> Using haskell and typeclasses it's not difficult to implement this idiom,
> why is it so rarely seen?
>
> V.
>
> --
> Please notice that my e-mail address has been altered to prevent spam

Vincenzo Ciancia wrote:
> Wouldn't it be  to write "x=y+z"
> where y and z are variables, and know that this invariant will always hold?[/color
]

Somewhat off topic, but hardware design languages work this way, though
with finite speed.

- ken

Vincenzo Ciancia wrote:
> William Lovas wrote:
> 
notice 
>
> But a lot more like dataflow programming! I have always looked with
interest
> to asynchronous dataflow languages, but I ask myself why almost
nobody in
> the world seems to be working at this. Wouldn't it be  to write
"x=y+z"
> where y and z are variables, and know that this invariant will always
hold?
>
> Using haskell and typeclasses it's not difficult to implement this
idiom,
> why is it so rarely seen?
>
> V.

Adaptive and Incremental computations seem somewhat related to what you
are talking about http://www.cse.ogi.edu/~magnus/Adaptive/

Vincenzo Ciancia wrote:
> Wouldn't it be  to write "x=y+z"
> where y and z are variables, and know that this invariant will always hold?[/color
]

Ken Rose replied:
> Somewhat off topic, but hardware design languages work this way,
> though with finite speed.

I presume you are refering to the "continuous assignment statement" of
Verilog.  That is a dataflow assignment.  As to the finite speed, I'm
not sure what you mean.  However, I don't think any valid program can
detect the point between when the lhs changes and the rhs does.

As to Jo Durchholz's question, the dataflow part of the hardware
description languages is not sufficient.  One still needs imperative
(state) parts.  Now, the distinction in Verilog is particularly, ugly,
counter-intuitive, and error prone.  Still, I think that the point
holds.  Just as one sometimes needs state in a functional language,
one sometimes needs state in a dataflow one.  As a result, some people
program totally in the state mode, arguing that it simplifies their
model.

Hope this helps,
-Chris

 ****************************************
************************************
*
Chris Clark                    Internet   :  compres@world.std.com
Compiler Resources, Inc.       Web Site   :  http://world.std.com/~compres
23 Bailey Rd                   voice      :  (508) 435-5016
Berlin, MA  01503  USA         fax        :  (978) 838-0263  (24 hours)
----------------------------------------------------------------------------
--

Chris F Clark wrote:

> Still,=A0I=A0think=A0that=A0the=A0point
> holds. =A0=A0Just=A0as=A0one=A0sometimes=A0need
s=A0state=A0in=A0a=A0fu=
nctional=A0language,
> one sometimes needs state in a dataflow one.=A0=A0As=A0a=A0result,=A0=
some=A0people
> program totally in the state mode, arguing that it simplifies their
> model.

I think the two could be combined: the stateful part can be modeled usi=
ng
stateful variables with dataflow assignment, where an assignment takes =
a
pure function of other stateful variables as its "right" part, or bette=
r:
there are two distinct kind of effects, those that can happen on state
variable change, and those that need to be performed to set or get the
value of a variable.

V.

--=20
Please notice that my e-mail address has been altered to prevent spam

Vincenzo Ciancia wrote:

> I think the two could be combined: the stateful part can be modeled using
> stateful variables with dataflow assignment. . . .

No doubt that it could be done better.  However, the model in hardware
description languages is (two parts):

1) There are dataflow variables ("wires") and they are the targets of
dataflow assignments.  If one updates the inputs to a dataflow
variable, the dataflow variable changes.  A dataflow variable does not
retain state.  If the inputs change, the variable changes and if the
inputs do not change the variable does not change.*

(* Excepting for some special purpose hacks, which allow one to
forcibly change the value of a dataflow variable so that it not
longer tracks its inputs--those hacks are not for use in
synthesizable code, they're more like a debugger built into the
source language, and that goes back to the intent of the hadrware
design languages, they weren't original created to design hardware
at all, but instead to debug hardware (by simulating it)).

2) There are also state variables ("regs") and they are the targets of
imperative assignments.  State variables only change when there
imprative assignments are executed, they retain state otherwise.
changes to the inputs do not change a state variable automatically
(i.e. there is no dataflow), only executing the assignment statements
changes them.

It is worth mentioning, that this distinction is only a left-hand-side
(assignment target) issue.  Both dataflow and state variables can
appear on the right-hand-sides of any assignment statement,
regardsless of whether the target is dataflow or state preserving.

The problem is one can (and some people do) program by using only the
state variables and using no dataflow assignments at all.  The reverse
is not true (in the general case), one cannot program entirely in the
dataflow language and in that language "create state".  Of course,
programming with state in the hardware description languages is
fraught with the same problems that imperative programming is in any
domain.  One can write imperative programs that "appear to work" only
because some flow path the exhibits a bug was not exercised in the
test cases.  (As someone once said, "some people can write C code in
any language", and some do, even when attempting to design hardware.
The difference being that such designs generally don't actually work.)

Now, in some sense "design styles" recommended by trainers in the
field and practiced by many designers, do effect what you suggest.
The design styles put all the computation in the dataflow variables
and only use the state variables for capturing state at the instances
it needs capturing.  However, those design styles are only guidelines.
More importantly, they don't tell a designer with an algorithm written
in C, how to de-state the algorithm and get it to use a dataflow
style.  If one doesn't "see" the algorithm in hardware terms, the
design styles aren't much help.

Learning how to program without state (at least in the hardware sense)
is in some sense a completely separate art, which some take naturally
to, but others don't.  There are lots of things which make sense if
you think of them happening serially (and one can write a loop for),
that just cannot be realized in hardware (and least not with a naive
translation).  Perhaps, the canonical example is searching an
array. This is a very sane thing to do in an imperative world.  Rarely
does it make sense in a hardware implementation (caches and table
lookups do make sense, but the tradeoffs are different).

One distinction between this and the functional programming world, is
that in hardware design one cannot use recursion either to replace the
loops.  hardware design languages are all dealing with known finite
instances of problems.  At some level one must unroll all the
recursion (or iteration) and deal with the exact fixed size input that
one has.

To my mind the distinction to correct designing hardware is closer to
when one starts using higher-order functions.  Learning recursion and
replacing loops with recursion is not a big step up the model of
programming.  However, when one learns to write higher order functions
and begins to think that way, one is programming at a different level.
One is dealing with the forest and not just a better way to saw down
individual trees.  It is the same with hardware design.  Proper
hardware design is done at the forest level, where one sees everything
happening in parallel, and one knows exactly where one wants to insert
state to control that parallelism.  I know this is vague and far
strayed from the original topic, but still I

Hope this helps,
-Chris

 ****************************************
************************************
*
Chris Clark                    Internet   :  compres@world.std.com
Compiler Resources, Inc.       Web Site   :  http://world.std.com/~compres
23 Bailey Rd                   voice      :  (508) 435-5016
Berlin, MA  01503  USA         fax        :  (978) 838-0263  (24 hours)
----------------------------------------------------------------------------
--