Apr/100
ChucK: mind-bending programming language of the day
I've recently started teaching myself a new programming language: ChucK. You can read a paper by the authors that gives a quick outline of some of the salient features of the language:
Wang, G., Cook, P. R. (2003). ChucK: a concurrent, on-the-fly audio programming language. In Proceedings of International Computer Music Conference, pages 219–226
Dec/091
Concurrent Hierarchical Reinforcement Learning & Lisp
Allan recently set me onto quite a good paper:
B. Marthi, S. Russell, D. Latham, and C. Guestrin, “Concurrent hierarchical reinforcement learning,” in Proceedings of the National Conference on Artificial Intelligence, vol. 20, 2005, p. 1652.
Marthi et al. describe an extension to Lisp that forms part of their concurrent hierarchical reinforcement learner. Their algorithm is trained to control simulated peasants in the Stratagus real-time strategy game domain. Their approach is similar to Parr and Russell's Hierarchical Abstract Machines (HAMs) in that a program defines a semi-Markov decision process which is then solved with a reinforcement learner and prior knowledge is included in the design of the program.
The paper made me interested in learning Lisp, although I have some hesitation because Lisp is (according to Wikipedia) the second oldest programming language still in use.
Peter
Sep/090
PRETzel
PRETzel is a research group based in the ECE department at the University of Auckland. Their research focuses on the development of Precision Timed (PRET) Machines, which are processor architectures designed to give precise, deterministic execution timing. Predictable timing can be crucial for the reliable operation of embedded systems.
The PRETzel group's approach is based on augmenting an existing general purpose soft-core processor with a "predictable functional unit". Their ARPRET processors are programmed in PRET-C, an extension of C that supports synchronous concurrency, preemption, and a high-level construct for logical time. PRET-C programs are logically concurrent, but compile down to a sequential program for execution.
Berkeley and Columbia are also collaborating on the devlopment of PRET machines, although their approach is slightly different to the PRETzel one.
I'd eventually like to start doing some work with PRET machines here - either on the architecture development front, or on language design for PRET systems. Vorpal's approach to concurrency might map well onto a PRET architecture. It'd be interesting to look at how well the two approaches match, and whether Vorpal could be augmented with timing instructions.
Sep/092
Erlang, Haskell, and some thoughts on robust software design
Via Lambda the Ultimate, an interesting conversation between Simon Peyton-Jones (of Haskell fame), and Joe Armstrong (of Erlang fame). Click "show all" to read the transcript instead of watching the video.
One section I found particularly interesting is the following comment from Joe Armstrong:
JA: If you look at Haskell, Erlang, Scala and F#, what do you see? If you look at Haskell, you see something which, within its context, within the little framework it sets up for its sandbox, it's very consistent, it's very beautiful. You look at Erlang, it kind of fits, the bits fit together nicely. Of course, they don't fit together nicely with the JVM or with .NET or anything like that. If you want to use all the nice things that are there, you can't use them, or you can use them, but it's difficult. So the other approach is, you say "Let's use the JVM and target lots of different languages, so that the different languages can use each other" or you can do that within the .NET framework, you get Scala and you get F#.
The benefit there is you can use all these other things that are available, but in order to do them, you have to break them, massively corrupt and break these abstraction boundaries and I don't like that. I think you are breaking abstraction boundaries in the wrong place. How I would like to see systems built is through communicating black boxes. And I would like to see the type systems applied to the definition of the protocols themselves and I haven't seen that done.
Aug/093
Concurrent Vorpal
Investigating and implementing concurrency in Vorpal has been going well. The idea is to introduce an message based (actor-style) concurrency. Many Vorpal processes can send messages to each other and the VM running those instances of Vorpal are run in a specified number of OS threads. Because each VM is well isolated, there have been remarkably few concurrency bugs so far.
Aug/090
Controlling Hybrid Vehicles with Haskell
Here's one of the more unexpected uses of functional programming that I've come across recently. In a presentation at CUFP 2008 Tom Hawkins from Eaton Corporation (which is focused on power management and power quality, hydraulics, pneumatics, and various automotive and industrial applications) described how they're using the Haskell functional programming language. Haskell apparently gets used for a bunch of fairly typical day-to-day tasks, such as scripting, data conversion, flash programming, hardware-in-the-loop simulation, and data-logging. But they also use Haskell as a host language for an embedded domain-specific language focused on hard real-time control software!
The Atom DSL allows programmers to define control programs as rule-based state-transition systems. The Atom compiler performs static scheduling of rules and automatically thread partitioning. Program timing is partially verified by the compiler (good for hard real-time systems!), and because rules are treated atomically there's no need to mess around with locks or other synchronization mechanisms. Here's a simple example (from the presentation) of Atom rules for handling a bank account:
system “deposit”$ do
when depositRequest
balance <== value balance + amount
system “withdraw”$ do
when withdrawRequest
when $ value balance &gt;=. amount
balance <== value balance -amount
Aug/090
Inferno
Inferno® is a distributed operating system, originally developed at Bell Labs, but now developed and maintained by Vita Nuova® as Free Software. Applications written in Inferno's concurrent programming language, Limbo, are compiled to its portable virtual machine code (Dis), to run anywhere on a network in the portable environment that Inferno provides.
Inferno has a number of neat features. From my perspective, the neatest is that it's programmed using Limbo, a CSP-inspired language that provides cheap processes in a message-passing concurrency model (so similar to languages like occam and Erlang). Others may be more excited by things like Inferno's range of supported OS platforms and processor architectures, relatively small resource requirements, or novel "everything is a file" approach to resource access.
I was reminded of Inferno earlier today, after chatting with a developer who apparently was one of the first employees at Vita Nuova. That chance meeting prompted me to go and take a look at Inferno again (it'd been several years since I last looked at it). I was once again struck by how many cool ideas are packed into such a relatively small package. But one thing in particular caught my attention this time around, and that's the garbage collector in the Dis VM. The Dis VM spec describes the GC as follows: The Dis machine performs both reference counted and real time mark and sweep garbage collection. This hybrid approach allows code to be generated in several styles: pure reference counted, mark and sweep, or a hybrid of the two approaches. Which sounds a lot like some of the ideas being batted around for the Vorpal VM, and suggests that studying the Dis GC design might yield some ideas on how to tackle some of the outstanding issues with the Vorpal design.
Aug/090
Mobile Robot Control – The Subsumption Architecture and occam-pi
I was recently looking at Brooks' Subsumption Architecture for robot control for the first time in a while, and was struck by how well many of the ideas would map onto formalisms like CSP and languages like occam. So I wasn't all that surprised to discover that the good folks on the Transterpreter project have been experimenting with implementing a subsumption architecture in occam. A report of their initial experiments can be found in Simpson et al., Mobile Robot Control - The Subsumption Architecture and occam-pi.
The results look quite promising. Implementing subsumption in occam looks like it's extremely easy, and the expression of basic behaviours in occam ends up being quite clear and easy to follow. For example, here's a simple behaviour to prevent collisions, which is used in tandem with a distance monitoring process:
PROC prevent.collision (CHAN INT distance?, CHAN INT act!)
WHILE TRUE
INITIAL INT min IS 0:
SEQ
distance ? min
IF
min < 20
act ! motor.stop
TRUE
act ! motor.forward
:
It'd be interesting to see if we could build an occam-like interface to the TeRK platform used in ENMT301 (which seems to serve the same purpose as the Player API used in the paper). Alternatively, it seems likely that it'd be quite easy to integrate a JCSP-based Java application into TeRK, or perhaps for slightly cleaner behaviour descriptions it might be possible to use Communicating Scala Objects. --Allan
Aug/091
A Framework for Comparing Models of Computation
Edward A. Lee and Alberto Sangiovanni-Vincentelli, A Framework for Comparing Models of Computation, IEEE Transactions on CAD, Vol. 17, No. 12, December 1998
This is a fascinating paper that presents a unifying mathematical framework for understanding continuous-time systems, discrete-time systems, and discrete-event systems like Petri nets and state machines. In other words, it shows some initial steps towards bringing together the standard theories for control systems, signal processing systems, and computational systems. From the abstract:
We give a denotational framework (a "meta model") within which certain properties of models of computation can be compared. ... The interaction between processes is through signals, which are collections of events. Each event is a value-tag pair, where the tags can come from a partially ordered or totally ordered set. Timed models are where the set of tags is totally ordered. Synchronous events share the same tag, and synchronous signals contain events with the same set of tags. ... The framework is used to compare certain essential features of various models of computation, including Kahn process networks, dataflow, sequential processes, concurrent sequential processes with rendezvous, Petri nets, and discrete-event systems.
The ideas embodied in this paper are the same ones that underlie the Ptolemy II platform for modelling and analysis of heterogeneous systems. I've also found them useful for understanding how different models of computation might or should be interfaced, and for looking at systems I'm familiar with from a different perspective.
Some questions worth thinking about:
- What's the relationship between this tagged-signal model and Fleet (mentioned previously)? Can Fleet be understood in terms of the tagged-signal model? What are the tags, and what properties do they have?
- How could neural networks be understood in terms of the TSM? Do different kinds of networks use different kinds of tag systems, or just different kinds of value sets? Could we define neural networks with heterogeneous tag systems, and would that buy us anything?
--Allan
Aug/093
Fleet
Fleet is a Berkeley project to develop novel processor architecture -- if that's the right word for what Fleet is doing -- based on small interacting components that operate concurrently. The result seems to be sort of halfway between a processor and an FPGA. A Fleet processor consists of a switching fabric, a bunch of functional units (called "ships"), and a collection of connections (called "docks").
Personally, I find the terminology a bit too "cute". It introduces an additional barrier to understanding what they're doing: the analogy between real ships and docks and the Fleet system is sufficiently tenuous that the names don't really help in understanding what they're up to. But the basic idea looks quite interesting. The processor itself is completely asynchronous, and highly concurrent. Programming a Fleet processor is quite different than programming a traditional processor, and largely seems to involve defining movements of data between different "ships" rather than defining operations on data. Seems like there'd be some interesting challenges in programming such a system (although I'd imagine that the occam community might have some applicable ideas), but also some interesting potential applications.
--Allan