Lambda the Ultimate

I'm familiar with the "software IC" and "component software" concepts. But those are not what Vahid is talking about. I think you may be misunderstanding what the article is discussing. The argument is not that we should treat software as hardware, but rather that certain elements of hardware (specifically FPGAs) can now be treated as software. However, programming such hardware involves a different computational model than is traditionally supported in programming languages (even those targeted at producing "software ICs" and the like), as opposed to so-called "hardware description" languages.

Sorry if I was a bit too cryptic in my first post. Let me expand just a bit.

I think that we're talking about a boundary (the hardware/software distinction) that is being regarded as increasingly fuzzy from both sides (and Vahid happens to be on the "hard" side of the boundary).

When I look at the concrete examples Vahid offers, every one of them is familiar to me under the "thinking differently about programming" rubric; this is a theme that I've seen and been promoting in my small circles for a few decades.

P. 106: The essence of his A'B'C'+ABC example is that of a function over a finite domain which can be represented in a data structure rather than being re-evaluated every time. (A friend once had an assignment of writing an opcode recognizer for the 6502 CPU; given a byte, determine whether it was an opcode. The teacher had presented the traditional which-bit-means-what discussion. Every other student had written a multi-level decision tree. My friend created a 256-byte table of 0/1 indexed by the input, which he and I thought was the most obvious solution.)

Most of p. 107 is back to advocacy, but at the end of the page he makes the temporal-vs-topological distinction (my choice of terms; "connectedness" is a topological concept, not a spatial/geometric one), and applies it to tasks which "execute concurrently in a parallel or pipelined fashion" (surely a familiar concept in this forum). I totally agree with his assertion that traditional methods of teaching e.g. C leave the student "typically weaker" at creating such models. I simply disagree that this is true of all software developers and computing scientists (such as subscribers to LTU, and others I've observed over the past few decades).

P. 108: Vahid closes the article with a plea for early teaching emphasis on parallel as well as sequential models. Again, I agree totally with the plea; I simply don't regard it as novel. His example is that of parallel sorting, and my example is that Knuth V3 (pp. 219-244, in the second edition) presents and analyzes the concept of sorting with a network of pairwise comparator/swapper elements.

As for the "software IC" metaphor of OO, I recall that one of the earliest metaphors for OO computing was that of a network of independent conceptual computers exchanging messages, but working collaboratively in parallel. There's nothing in the OO model (except for C-oriented teaching and bad habits) that implicitly requires us to think solely in terms of synchronous function calls.

It is certainly true that OO languages don't force us to think differently. Those of us who work in industry have seen mass quantities of "C code run through a C++ or Java compiler". But isn't it true of every significant advance in programming that good programmers already had the metaphors (and were using them) before the next wave of languages/implementations provided more automated support?

We had programmers who understood recursion before hardware supported more than a single "return address".

We had programmers who understood structure before languages directly represented "structured programming" control-flow constructs.

We had programmers who understood information hiding and multiple occurrences of persistent state before OO language concepts automated them.

We've had programmers who understand topological connections, parallelism, systolic processing, and other forms of non-syncronous, non-sequential computing, long before we get programming languages that let us use the embedded FPGAs in our 80-core laptops.

But some of us (including, I suspect, essentially all of the readers of LTU) are already eager for it.

I recall that one of the earliest metaphors for OO computing was that of a network of independent conceptual computers exchanging messages, but working collaboratively in parallel.

We've had programmers who understand topological connections, parallelism, systolic processing, and other forms of non-syncronous, non-sequential computing, long before we get programming languages that let us use the embedded FPGAs in our 80-core laptops.

The "wiring" in Objective C is more about connecting dependencies together. In Java this would be doing with a dependency injection framework such as Guice. This is at least somewhat related because when there's a dependency between two entities, it's because there's dataflow between them, but declaring a dependency doesn't say anything about how the dataflow happens.

Spatial programming has more to do with how things are laid out inside the computer. For traditional programming, these concerns have mostly had to do with memory: which variables are in registers? How are data structures laid out in memory and on disk? But with increased parallelization and NUMA architectures, assigning tasks to processors that are close to the data they operate on becomes important too.

Hopefully this will be done by dividing things up into tasks and shards. Reducing the number of dependencies between tasks will be important because that makes automatic layout easier, but I hope the layout itself is automated by the compiler, similar to how we don't declare register variables anymore.

Indeed. Both VHDL and Verilog (as well as now SystemVerilog) support higher-level constructs that are not synthesizable, but can be used to develop testbenches (a set of automated tests akin to a unit-test suite, for those not familiar with the term) and behavioral models (which can be shown to be refined down to structural models via testing with testbenches). However, these languages don't (as far as I know) support compilation to anything other than a simulator or an FPGA.

Re the link, I've just tested it again, and it works for me. However, I appreciate the alternative link you've provided, since it makes it that much more likely that the paper is available. But note that the link you've given requires an IEEE membership to actually access the paper, which is fine for people who are IEEE members (or are at institutions with an IEEE subscription), but not so useful for others.

This is a big pet peeve of mine. I'm usually at institutions that have membership, but I like to work away from the office and go online on the outside, where anything from ACM/IEEE becomes unreadable. Please, authors, put your papers on your webpages! If its worth reading, it should be easy to Google and download.

Oops. I thought I wasn't logged into IEEE at the time but clearly was. Your original link works for me now too. Thanks.

Lava and Confluence is too low level.

Hawk is too high-level and non-synthezable. And outdated.

I took a look at Atom (Bluespec in Haskell) and wasn't excited either.

In my slightly educated opinion there is no good HDL today. They all about 15-20 years behind state-of-the-art programming languages.

I did that survey because I do transaction level modeling for our hardware group. Modeled hardware ranges from simple logic circuits to complete RISC processor and multicore data flow system designs.

My language of choice for that task is Haskell. It is not perfect for many reasons but we get our job done.

The suggestion that software engineers should learn VHDL or Verilog to be on the "cutting edge" would be somewhat humorous to hardware designers who have been using those languages for years now.

It's interesting that while software engineers are currently looking for ways to better model parallelism, the hardware folks have had the HDLs for years now and they do a very good job at modelling parallelism - in fact one of the things you have to get used to when transitioning to an HDL is that everything can happen at once since you need to model a circuit in which everything can happen in parallel.

It's also interesting to note that some hardware engineers are moving to C/C++ as an HDL - SystemC for example is entirely based on C++; it's not a seperate language, but a set of classes and templates that make it easier to model hardware (and a runtime for simulating models). There's also a movement to just use plain C/C++, the idea being that you can write your algorithms in C/C++ and then use some sort of highlevel synthesis tool that schedules tha algorithm and converts to an HDL. This can be a win for DSP circuits, for example, but it's not so good for control logic. Examples of tools that take this approach: ImpulseC and CatapultC from Mentor Graphics. It is odd that at a time when most software engineers are looking for more parallelism, some hardware types want to go to C/C++ which has no built-in mechanism for explicitly modelling parallelism.

Certainly I can agree that there's no optimal HDL today, though I think Bluespec, Confluence and Atom are attempts to try new directions in the searchspace.

Yes, thank you. I am aware of those other efforts. I wasn't looking for pointers to the literature, but for a discussion of the points that Vahid raises about the need for a greater emphasis on education (and languages) that target what has traditionally been considered the realm of hardware designers rather than programmers. For those interested: reFLect was previously mentioned on LtU here. Previous discussions of Lava were here and here. Esterel seems to have received few mentions on LtU (here and all the way back in the classic LtU).

Of course, the issue isn't so much that HDLs exist, but that:

1. They involve a different computational model than most traditional PLs (although languages like occam, Erlang, and Esterel can be used with a similar style), and thus require a different approach (in much the same way that writing in a functional style differs from writing in an imperative style).
2. They are looked upon as HDLs, and generally considered somehow separate from PLs. Vahid's basic argument is that this separation may not make so much sense any more.

Ed Lee from UC Berkeley makes a few observations regarding the abstraction away from time in a talk titled The Future of Embedded Software. This disconnect can be problematic for embedded systems attempting to deliver predictable behavior against hard deadlines. As Lee puts it:

Electronics technology delivers timeliness... and the overlaying software abstractions discard it.

• Put time into programming languages (e.g. Giotto)
• Rethink the OS/programming language split (e.g. TinyOS/nesC)
• Rethink the hardware/software split (which is largely where this thread started)

The final bullet point in Lee's presentation?

There are opportunities for language design.

...and of computer science.

All the machines we know how to build, have finite resources (memory in particular). Many machines, particularly in embedded systems, are far more constrained than that.

High-level computer science, on the other hand, tries to pretend otherwise--we try to abstract away the limitations of the underlying machine. And in many cases, this is the right thing to do--failure due to lack of resources is often controlled; programs are executed on machines with ample resources; performance is not an issue. If you can ignore the underlying machine, you gain much in terms of portability and composability of your design.

If you are programming for a machine with highly-limited resources, or if you are developing a realtime system, or a mission-critical one--you must understand the machine. The machine must become part of your design. You still may be able to import designs from other places, or designs developed for the desktop/server environment where resources aren't scarce--but demonstrating correct behavior on the machine in question becomes a requirement, rather than an implementation detail or happy circumstance.

On the other hand, if you are programming for code that will run in a possibly hostile environment, or writing software which will host possbily hostile (buggy, malicious) code--then you have a whole different set of problems to worry about. Quite a bit of the current boundary between OS and application, and/or between kernel mode and user mode--is intended to provide process isolation for just this very reason. Many embedded OS's dispense with the kernel/user mode distinction under the theory that most embedded systems need not worry about hostile code (and for many, that's probably true).

I won't get into virtualization--there's a whole 'nother kettle of worms right there. :)

And yes--this does have an impact on PL design, and how we write software. One of the difficulties of concurrent shared-state programming is that concurrency is often implemented by pre-emptive multitasking, which is highly unpredictable in its behavior. Cooperative multitasking (essentially using coroutines to switch between concurrent threads of execution) is far more predictable in hits behavior--but it has long been known to be unreliable in the face of buggy or malicious code--though if we can prove that a program or program fragment will always terminate or yield after some time, this may change. Memory management is another area of contention--most high level languages use garbage collection to abstract management of the freestore (a difficult problem which is hard to do safely manually) away from the programmer. Yet GC is still considered unacceptable in many embedded applications, and is not suitable for managing scarce resources--even those programming languages which successfully manage RAM with a garbage collector, still frequently require the programmer to manually manage system resources, like file handles, database connections, graphics contexts. PLT can help here too, of course.

And I won't get started about distributed systems over unreliable networks--where not only is failure an option, it's a certainty. :)

There are certainly many opportunities for language design.

If you can ignore the underlying machine, you gain much in terms of portability and composability of your design.

Surely there must be some way to parameterize the underlying machine? Are you aware of any efforts in this direction? For instance, parameterizing a BigNum based on the machine's native integer size, so it will automatically scale based on the architecture. I did something very similar in Ada95 a few years ago as a proof of concept, as Ada supports arch-specific Integer'Size property and sufficient compile-time elaboration for this purpose.

Ensuring a program has the resources to run at run/load-time is a problem I have yet to see solved, but one in which I have significant interest. I'm aware of some work with sized types, and first-order analyses which yield resource-use estimates. Anything else?

I won't get into virtualization--there's a whole 'nother kettle of worms right there. :)

I think the virtualization and isolation problems are mostly synonymous; if you have complete isolation, then you can transparently virtualize all interactions crossing that isolation boundary; if you have complete virtualization, then you have full isolation.

Cooperative multitasking (essentially using coroutines to switch between concurrent threads of execution) is far more predictable in hits behavior--but it has long been known to be unreliable in the face of buggy or malicious code--though if we can prove that a program or program fragment will always terminate or yield after some time, this may change.

I've been considering this problem recently as well. What about a VM-supported program transformation parameterized by a schedule; by this I mean, the potentially malicious code is transformed to yield execution after a fixed number of function calls determined by the scheduling slice allocated to it (essentially a work-based schedule). This is pre-emptive, yet also co-operative in a sense, and it's highly predictable. I believe this is similar to how Erlang performs its pre-emptive tasking.

naasking: I've been considering this problem recently as well. What about a VM-supported program transformation parameterized by a schedule; by this I mean, the potentially malicious code is transformed to yield execution after a fixed number of function calls determined by the scheduling slice allocated to it (essentially a work-based schedule). This is pre-emptive, yet also co-operative in a sense, and it's highly predictable. I believe this is similar to how Erlang performs its pre-emptive tasking.

Nicely said: a good description of the same plan I'm following (a bit like a scheme I wrote about a few years ago).

Potentially malicious code run under a VM cannot run indefinitely without yielding if it needs a VM to mediate execution. (But a VM might have few good choices besides whacking badly behaved code. Maybe a VM can send warning events saying "you're disturbing neighbors" first before draconian measures.)

Code can be written in cooperative multi-tasking style if other code mediated by VM cannot pre-empt. If only a VM pre-empts, you get code both cooperative and pre-emptive depending on context. This is another advantage of mixing models.

You can put context switching where a VM is not confused to avoid costly protection against pre-emptive native context switches. As a side effect, you get large safe atomic critical sections in native code between VM context switches.

Unless generated by the VM, you can't let potentially malicious code run as native code.

Code can be written in cooperative multi-tasking style if other code mediated by VM cannot pre-empt. If only a VM pre-empts, you get code both cooperative and pre-emptive depending on context. This is another advantage of mixing models.

I was envisioning a mix of suggestions: unifying OS and language by adding processes, and explicit scheduling control when needed (would this count as "putting time into the language"?); the Manticore project is quite close to what I have in mind.

The above Giotto link looks interesting as well, so I'll have to spend some time on it. Their "time-safety" property might be useful.

Unless generated by the VM, you can't let potentially malicious code run as native code.

Well, you could with a proof-carrying code certificate.

High-level computer science, on the other hand, tries to pretend otherwise--we try to abstract away the limitations of the underlying machine.

This is perhaps a function of where computer science originated, and how it's developed since. Every abstraction involves discarding "unnecessary" detail. The abstractions that "high-level" computer science uses work quite well for the domains to which CS was originally applied. Unfortunately, they tend to discard details that are important to embedded systems. Things like time, and resource consumption. And in some ways, those new abstractions are necessary for more than embedded systems: a huge amount of modern software is interactive, and the need to provide responsiveness to users imposes at least soft real-time constraints. This is not to say that CS has completely ignored these issues (there are, for example, "timed" variants of various process calculi). Rather that such concerns don't seem to have made it into mainstream programming languages. Yet.

Yet GC is still considered unacceptable in many embedded applications...

The former goes back to your point about the finite nature of system resources not being adequately captured by present abstractions. I could swear that I have seen some ideas about how to handle that kind of thing from a PL perspective here on LtU, although the exact nature of the ideas escapes me right now.

There have been a number of links to projects using Haskell to certify low-level abstractions, and generate the corresponding low-level C for device drivers and such. I don't remember all the details at the moment.

many GC implementations seem to require memory equal to a multiple (>2, typically) of the size of the working set to function efficiently. Now, those figures are probably most relevant again to desktop/server applications, where you have oodles of virtual memory, and multiple independent processes vying for system resources--and many not apply to embedded systems (even those that could otherwise tolerate a GC).

In some cases, embedded system developers can add additional memory in order to gain the development efficiency that goes with garbage collection. In other cases, they cannot.

This goes back to my point about other system resources, such as file handles, *not* being suitable for garbage collection. In some cases, this is due to some required action at close, such as flushing a buffer or syncing a disk, that cannot safely depend on the "maybe" semantics of finalization routines. In others, though, this is due to the fact that these resources are scarce--the RDBMS may have a limit to the number of open connections; and applications which keep them open long past their last use until the GC determines that the connection is no longer live, are considered unfriendly. :)

Memory management is another area of contention--most high level languages use garbage collection to abstract management of the freestore (a difficult problem which is hard to do safely manually) away from the programmer. Yet GC is still considered unacceptable in many embedded applications, and is not suitable for managing scarce resources--even those programming languages which successfully manage RAM with a garbage collector, still frequently require the programmer to manually manage system resources, like file handles, database connections, graphics contexts. PLT can help here too, of course.

RAII is a simple and powerful idiom that elegantly allows deterministic, safe and efficient management of resources, be them memory or anything else.
However, as far as I know, it's only really used in C++. I wonder why it's not more globally adopted by other programming languages.

From the wikipedia article on RAII, it seems limited to objects with stack lifetime. If that's the case, then region based memory management is more efficient than RAII. Some languages also perform escape analysis to determine whether stack allocation of an object is possible, which has a similar efficiency gain as RAII. RAII seems more error-prone since it relies more on the developer. What is the advantage of RAII over the above techniques? Or am I misunderstanding something?

... the main advantage is the determinism and guarantee of earliest possible deallocation.

It's true that the 'doWithResource' pattern also helps here, but if you're dealing with multiple resources it can lead to huge 'staircase' of anonymous functions. (Though I guess this is largely a syntactic issue.)

Languages with higher-order functions have the withResource pattern instead, where allocation and deallocation're done by a higher order function which allocates, passes in to its parameter and then deallocates the resource - creating a new scope for the resource in question. With a little phantom type trickery you can also prevent the user trying to pass the resource out of that scope.

In C++, when an object goes away (whether by going out of scope, or being deleted, etc, it's destructor is always called, guaranteed. No production GC I can think of makes that sort of guarantee--the time of destruction of an object is unspecified (and many collectors will fail reclaim all possible dead objects), and there's also the problem of finalizers "resurrecting" objects and how to deal with that.

RAII is, as another poster mentions, best used with objects which are constituent parts of other objects (C++ allows object composition with value semantics, whereas Java only allows reference semantics) or on the stack. Reference-counting collectors can be implemented with RAII; more general garbage collection cannot.

As another poster points out, region inference largely subsumes RAII anyway.

hm, does C#'s IDisposable interface not quite count? i realize this isn't like having it always happen. and the IDisposable thing is sorta clunky. seems like there ought to be a way to have an interface which can be used by the VM/GC to kill things at "standard" scope exits w/out having to use the "using" type style. but then you can start to ask questions about long term maintenance of code when things are made sorta invisible.

Computers are much less synchronous than you suggest. There are lots of clocks running at different rates, and even those that supposedly run at the same rate do not. For example, the CPU cycle counters in an SMP system are not synchronized. Even within a CPU, parts of the circuitry may be clocked at different rates, or only when they are used, or they might be asynchronous.

and other representations of a graph, aren't constrained to be planar however. To a large extent, layouts of FPGAs are.

Of course, there are things which have even more constrained topologies than the inside of an FPGA.

So what common methods exist for proving a graph's planar? What classes of graph are known to always be planar? Can we build a logic (and thus a type system) for this?

we can always attempt a four-coloring of the dang thing. If a four-coloring isn't possible, then it isn't planar. :)

While I'm certain that's a useless suggestion, it wouldn't surprise me if there's a paper out there on that very idea. :)

It's probably not totally useless, unfortunately!

Interesting question: when can you safely abstract out a chunk of the graph into a single node? One answer is "when all the edges leaving said chunk are from nodes of the same colour" - we can definitely know that's the case if there's a single node that does all the communicating with the outside for example, or if there're only four nodes. Likewise for a few other small distinguishable patterns, from which we can probably build much larger ones by repeated abstraction. Anyone starting to smell combinators?

Here is a great expository article form Terence Tao blog:
http://terrytao.wordpress.com/2007/09/18/the-crossing-number-inequality/
and of cause wikipedia
http://en.wikipedia.org/wiki/Planar_graphs