Lambda the Ultimate

Hi all,

Not sure if this is a good forum to post this question on, but it's the best I could come up with, so hopefully someone will have some insights or pointers as to where to look for research :)

I've been thinking about 'graph processing' systems (for want of a better name) - for example, say an image editing system where an output image is described by a process on various input images, and those input images are again described by more processes on further inputs, and so on. A DAG basically, where each node is a process that produces an item of data, and the edges represent dependencies on input data.

Now say I wrote an image editing application based on such a system. I'd like to allow users to edit any process, thereby meaning all downstream nodes need recalculating, but to achieve best performance, ideally upstream nodes of the thing being edited would be cached somewhere - so you don't need to continually re-evalute any inputs whilst editing. However, clearly you've only got a limited amount of memory to cache stuff in, and therefore can't cache everything, so how do you decide which nodes should be cached and which shouldn't?

Kind of feels like if you could assign each process a cost (i.e. how expensive it is to recalculate the output of a node from its inputs), and a probability that it will be edited (i.e. there's no point in caching something if nothing downstream of it changes, but if a process is continually edited you'll probably want to cache it's inputs), then there ought to be some way of determining roughly which processes should be cached and which shouldn't. Seems like it ought to be possible to do better than just a simple LRU cache of node outputs for example.

Feels like it's probably a problem that's been researched somewhere in some form or other, or it's some computer science 101 problem I happened to miss out on phrased in somewhat odd terms, but I'm at a loss as to where to start looking...

Any pointers appreciated...!

apparently first being aimed at the Android Dalvik system.

This kernel defines a kernel language, call it Kl, that is the kernel necessary to run Qi. Now the interesting bit is that Qi is mapped to Python etc. through a mapping from the Qi-generated Lisp source to the Python language. So by mapping Kl to Blub, you get a version of Qi that runs under Blub.

I have done some work recently on the theory of aliasing, which I believe provides the key to the frame problem and more generally to proving O-O programs (although these applications remain to be better explained and explored further).

I was struck by the simplicity and generality of the laws uncovered in the process.

A blog entry at bertrandmeyer.com presents the basics. It includes a link to the draft paper, and also to a downloadable version of the implementation (currently a Windows executable, the source will be released later), which makes it possible to test all the examples of the paper.

-- Bertrand Meyer

(some muddling thoughts fermented with "adt vs. object" and "triz" and such.)

What problems in PLT are best solved via better tools? And what are those tools? And what does it take to get there? And which ones already exist? For example:

• Based on my experience, the vision for Subtext rings very true: the traditional ASCII representations just don't offer enough concise information vs. a tool with layout and UI that is targeted at the narrow problem.
• There was something useful about the Visual Age IDE's habit of breaking up files into snippets of code. I think part of the problem with the expression problem is that people are worried about what files need to be modified for a change. If our tools let us weave according to current reader need, wouldn't that free us a lot? Mightn't it help unify ADTs and Objects as well?

In Heron I'm adding literal tables which like literal dictionaries/maps/hashes/tables in many languages (e.g. Python, Ruby, etc.) are intended to provide a convenient syntax for associative collection literals.

The syntax looks like this:

var animals = table(animal:String, sound:String, legs:Int)
  {
    "Dog", "woof", 4;
    "Cat", "meow", 4;
    "Human", "hello", 2;
  };

The first column is used as a key, and the "value" is an anonymous record containing the other columns.

So you you can say: animals["Dog"].legs.

Question one: what other languages that have built-in support associative collections with more than two columns?

Now obviously this looks a lot like a simple array of objects: but the identity is chosen as the first field. So an interesting application is to construct an object-oriented programming system built from tables alone. It would then be helpful if the first field could be an auto-generated immutable integer id (e.g. the object address, or the database auto-generated key field).

So then the question becomes what syntax should I use? I'm thinking of something like:

var animals = table(self:Id, animal:String, sound:String, legs:Int)
  {
    $, "Dog", "woof", 4;
    $, "Cat", "meow", 4;
    $, "Human", "hello", 2;
  };

Question two: I don't want to invent brand new syntax, what syntax do other languages use for similar features (auto-generated ids)?

After working for several years in the information security business as a software developer and researcher, I'm planning to go back to school and complete, at least, a bachelors degree but would like to go on to graduate work. I will be talking to an general academic advisor in a few months but I can't get this out of my head: What I really want to do is graduate work in theoretical computer science. That is, my specific interests include the lambda calculus and combinatorial logic, formal logic, type theory, category theory, automata theory, formal languages and so on. All of these have in common that they are almost completely rooted in mathematics. However, when I look at the mathematics program at the university that I'm planning to attend it has a very strong emphasis on calculus, which I have little interest in (however, that's not to say that I wouldn't enjoy more calculus and learn a lot from it in the process.) When I look at the computer science programs, all of the undergraduate work seems overly-practical for someone who wants to do graduate work in theoretical c.s.. For example, I have no interest in studying programming languages such as Java or working with database systems more than I already have.

My first instinct is to go through the mathematics program and transition to a c.s. program at some point at the graduate level, but it seems to me that I'd still end up having to go through a lot of courses rooted overly-practical computer engineering in the end anyway. I think that I would prefer the mathematics because it includes may non-c.s. and non-calculus topics that I'm interested in such as number theory, abstract algebra and so on. But will I be left out of c.s. completely if I do this?

I was hoping with all the educated folk on this forum, someone may have a had a similar experience or advice that might help me make the right decision.

In summary, is it better for someone with my interests and ambitions to bare the calculus or bare the Java, and if I do opt for the math., will I be putting myself at a disadvantage for oppertunities in c.s.?

[Edit: I've just been made aware of two important facts. PSU is on a quarter system, not a semester system. Knowing this, the amount of calculus does not seem as heavy as I had thought. Although calculus still stands at slightly over 1/3 of the coursework. The second interesting fact is that PSU has just received a significant amount of money to be invested in improving their computational mathematics curriculum and facilities. In light of these new facts, the commentary in this thread and likely too much thought on the subject, I think that I will probably stick to my, previously less educated, instinct and enter this mathematics program. That's not to say that I'll discontinue my research into other options. I'd like to apologize for not having realized the quarter/semester issue earlier and I'd like to thank all the people who have so far.]

Recently, I've been trying to come to grips with pure functional programming (e.g., Haskell) and other potential kinds of declarative languages that work at the level of declarative binding rather than functions (e.g., constraint languages). As an example of the difference, consider how to make a button blue. Using functions, we define a function that creates a new button that is blue; e.g.,

make_blue(button) -> button
let my_blue_button = make_blue(my_original_button) in ...

The point of the pure functional approach is that we create new values to reflect new desired realities. Now for the declarative binding (constraint) approach:

is_blue_button(a_button) => a_button.background = blue
...
assert is_blue_button(my_button)

The point of the declarative binding approach is that we refine existing values declaratively to reflect desired realities. Different approach, same result I guess. For reactive programming, I've always been interested in the declarative binding approach with SuperGlue vs. the compositional approach of FRP. However, both approaches seem to have their benefits and drawbacks. Explicit function application gives you more immediate control over the values you produce, but without universal quantification we have to explicitly encode conditions around each application site. Implicit bindings allows things to "just happen" when the right conditions are met, but sometimes we have to struggle to control what goes on.

Any thoughts about the different styles?

I read this recently and found it very interesting. Paper here. Abstract:

The development of high-level programming environments is essential if wireless sensor networks are to be accessible to nonexperts. In this paper, we present the Regiment system, which consists of a high-level language for spatiotemporal macroprogramming, along with a compiler that translates global programs into node-level code. In Regiment, the programmer views the network as a set of spatially-distributed data streams. The programmer can manipulate sets of these streams that may be defined by topological or geographic relationships between nodes. Regiment provides a rich set of primitives for processing data on individual streams, manipulating regions, performing aggregation over a region, and triggering new computation within the network.

In this paper, we describe the design and implementation of the Regiment language and compiler. We describe the deglobalization process that compiles a network-wide representation of the program into a node-level, event-driven program. Deglobalization maps region operations onto associated spanning trees that establish region membership and permit efficient in-network aggregation. We evaluate Regiment in the context of a complex distributed application involving rapid detection of spatially-distributed events, such as wildfires or chemical plumes. Our results show that Regiment makes it possible to develop complex sensor network applications at a global level.

Also, earlier work covered here.

What I really like this paper is the way they combine continuous-time FRP signals with spatial regions of nodes. A signal S has a time component, and can be mapped (smap) or combined as a signal, but also has a spatial component and so can support filtering (rfilter) and folding (rfold). rfilter is useful for reducing communication of unimportant changes to save power, while rfold allows for result aggregation at intermediate points in the sensor network. They provide special operators for defining regions based on node topology, so you can program your whole sensor network as simply one FRP program (aka macro programming).

The alternative would be to program each node individually and let global behavior merge from how node's interact. This approach is also appealing. Diffusion is mentioned as one possible micro programming model, and so maybe the Anti-objects approach would contrast with the macro-programming approach for time-dependent spatial programming.

i've seen various approaches to making games with functional (even sometimes pure) tools, and of course there is more than one way to skin the problem. anybody have favourite references? here are some of mine, off the top of my head:

• PLT worlds
• Monadic approaches
• James Hague
• Forms of FRP

We cannot compose our own code with pre-written code (terms, types, classes, mixins/traits, modules, signatures, metalinguistic abstractions, etc.) - or compose two or more already constructed code constructs - if we cannot discover that such appropriate code exists.

What language features might help or hinder "code discovery". My own thoughts are thoroughly scattered. I think about completely diverse things such as 1) the standard "omnibus" Smalltalk package/class browser; 2) Stepanov and Lee's early emphasis re: STL on the more or less precise performance characteristics of different but otherwise functionally equivalent "pluggable" algorithms; 3) the extreme encapsulation, and thus essential invisibility, permitted by languages such as Pascal and Scheme with nested functions, other terms and even nested types (Pascal?); 4) the desirability or lack thereof of ADT's (existential types) as afforded by ML signatures and the very real trade offs between such encapsulation and the pragmatics of reuse; 5) the extremely widely varying "scope" of term composition and thus the size of the unit of computation and hence composition - from the typically terse Forth "word" all the way to giant multipage C functions common in industry, or even the domain specific, typically monolithic commercial libraries or "frameworks" often comprising 100,000's of lines of code or more.

As I said, my thoughts have a few "anchors," but otherwise seem completely scattered. I seek some set of uniform, organizing principles.

Our languages (common production languages plus at least the most popular "academic" languages) seem to be all over the map regard "discover-ability" - an attribute that seems both antecedent to and essential to the "holy grail" (among others) of relatively painless code discovery and consequent code composition.

Any papers, thoughts or general enlightenment greatly appreciated, particularly related to the relationship between individual or types of language features that enhance or hinder discover-ability. Thanks much in advance.

Scott