4 ms·
Ahhh! I love this one. FP was such an interesting language and point-free programming is still one of my favourite styles. I like this topic too (breaking away
by dkersten 17y ago
Ahhh! I love this one. FP was such an interesting language and point-free programming is still one of my favourite styles.
I like this topic too (breaking away from von Neumann style programming) because I believe that it is useful for some, but NOT all, problems. There are problems which are better solved with other paradigms. For example, mathematical algorithms and inherently sequential calculations (issuing commands to hardware often has to be strictly sequential, for example) - I'm sure I missed a load - are very well suited to von Neumann style programming. There are other tasks, however, which are not so well suited, as we have recently discovered: concurrent programming, for example, is pretty difficult in this style of programming.
I'm sure theres plenty of alternatives, but the one I'm currently interested in is dataflow, which appears to solve concurrency inherently and without programmer input, though obviously, being implemented on von Neumann hardware means the implementations may not make the best use of this.
Dataflow is interesting, to me, because it seems to be a minor step from imperative programming - a step which could have been taken arbitrarily back when computing was in its infancy. I don't believe that it was, I believe that imperative was chosen because it was, indeed, most suited to what early programmers were trying to achieve and the flaws (mainly concurrency) only became apparent a long time later. Its interesting to think about what programming would have been like if dataflow were the programming paradigm of choice, though. Ultimately, a nice balance between both would be best, IMHO.
I see it like this: in imperative programming, you have a stream of instructions, which is routed through the data it processes (that is, the next instruction is chosen by the previous instruction and the operate on a static (non moving) block of data) whereas in dataflow, you have static instructions with streams of data (that is, the data is routed by the instructions, much like logic gates route electrical signals in digital circuits). Conceptually, the difference is very small - but it makes a big difference.
I think theres values in both ways and would love a programming model which allowed both of these seamlessly. Oz provides some dataflow constructs, but IMHO they're too limited (and also the implementation should make use of these for implicit and transparent concurrency).
Thoughts?
- jerf 17y ago"(issuing commands to hardware often has to be strictly sequential, for example)" Do they, though? I mean, yes, sure, with current hardware this is true, but is this a true necessity, or an artifact of the fact that modern hardware is designed to be used by von Neumann machines? Honest question, I don't know enough about hardware to have an answer. Can there be "functional hardware", or perhaps more practical, "dataflow hardware"?
- notaddicted 17y agoIf the commands don't have to be executed sequentially, then you don't have to issue them sequentially. A modern processor will look at the incoming instructions and execute whatever it can without creating a hazard, this is called out of order execution. http://en.wikipedia.org/wiki/Out-of-order_execution http://en.wikipedia.org/wiki/Out-of-order_execution
- wmf 17y agoOOO still preserves sequential semantics, so it's not that interesting from the programmer's perspective.
- wwalker3 17y agoIt would be hard to create truly "functional" hardware. A piece of hardware is a real physical object with an internal state which is shared by all accessors and which can change over time. Shared, modifiable state is the exact opposite paradigm from the one that pure functional languages use. I think this is also why pure functional languages are so hard for "normal" people to understand -- their basic premise is the opposite of the real world around us that's filled with stateful physical objects.
- dkersten 17y agoI think one other reason why von Neumann-type imperative programming was chosen over dataflow IS because sequential instructions and shared memory makes a lot of sense to us. Having said that, a lot of non-programmers use graphical dataflow languages all the time, so maybe dataflow is ACTUALLY easier (at least for non-programmers - maybe the mathematical feel of imperative code attracts us programmers to it?) - eg, graphics tools often have dataflow languages for defining animations, materials, lighting and so on. I once used a dataflow tool for generating 3D visualizations and it was very intuitive.
- michaelneale 17y agoThe way I have had it explained to me (which I still don't quite get) is that an object is immutable if there was no time. When you mutate an object, it only happens due to time passing (ie if you were to "go back in time" the object would be as it was) - so changing something creates something else (in time). Confused.
- stefano 17y agoDataflow programming is exceptional for GUI programming, although I've never tried using it in a large application. This style of programming does its best if it has support from the underlying language to enforce consistency. Without it, it's just too easy to get the program into an unconsistent state. I'm aware of only two implementations providing dataflow programming: Cells for Common Lisp and FrTime for PLT Scheme (but I've actually used only the former).
- pcarmichael 17y agoYou're right that dataflow is well suited for concurrent programming. For a certain class of problems, it's ability to express your intentions in simplistic form is outstanding. I currently work on the compiler team for a dataflow programming language. Our compiler generates machine code for various processors, as well as VHDL for FPGAs. As you would probably expect, the generated code is very different depending on the target. Most CPUs are more suited to imperative programming rather than dataflow, so we often have to compromise on the granularity of parallelism to get good performance. On FPGAs, the compromise is typically reducing either parallelism or performance to save resources and making the code fit on the device. Programming for a dataflow environment is definitely a very different experience. Our customers typically do not have a computer science background, and in some ways this is a blessing. Most people with a computer science background initially try to program imperatively when exposed to an inherently parallel dataflow language. It takes some time to adjust to it, but when it finally clicks you can begin to look at problems from the both perspectives simultaneously. I feel like having a mastery of the different styles (imperative, dataflow, functional, etc.) has improved my overall ability to solve problems regardless of which model of computation I decide to use.
- dkersten 17y agoAre you able to talk about your dataflow language and/or compilation techniques? I'd love to hear about them, if possible, as its something I'm very interested in and am looking into myself. I've found it dificult to find information on compilation techniques for compiling a dataflow language to a traditional processor so have been making most of it up as I need, but my own work is far from optimal. Any insights you can provide here would be appreaciated. Are you simply converting dataflow code to blocks of imperative code and have these blocks running concurrently (eg, in threads) and communicating with each other? Or is there a more elaborate instruction scheduling mechanism at work?
- pcarmichael 17y agoWithout going into too much detail for obvious reasons, we are doing as you mention - converting dataflow into blocks of imperative code and scheduling them on threads. Although the scheduling we do both at the thread level and also at the block level is non-trivial and reasonably optimized. I'm sure most of what I'll mention below you've already discovered if you're implementing a dataflow language, but just in case: When implementing/generating code for a dataflow language it really depends on the level of granularity you want for your parallelism. On one extreme, you have super-fine-grained parallelism and can schedule each operation independently. On the other extreme, you have little or no parallelism and pre-schedule all of your operations in one big chunk. In the middle somewhere is typically a sweet spot where you have chunks of operations pre-scheduled, and then dynamically schedule those chunks. A key to optimal dataflow code generation (while retaining parallelism) is figuring out where to draw that line regarding parallelism granularity. Too granular and you spend all your time scheduling. Too coarse and you lose all of your parallelism. The ideal point somewhere in the middle likely depends on the operations themselves (i.e. the composition of your language). In some cases it is a decision you have to make by trial and error. In other cases you can make more informed decisions based on the nature of the operations and the context of their use within the program. Communication is really important as well. CPU caches encourage you to minimize data copies and operate on the data in place when possible (to minimize cache line fetches). Thus if your communication is based on a scheme where you need separate copies for each operation then your performance will really suffer. Message passing can work, so long as you are passing things by pointer and aren't having to make copies.