The Good Soldier LMeyerov

Scaling the Data Wall: Exporting Your List of Kindle Books from Amazon

2013-12-02T21:24:00.003-08:00

I'm waiting to make a couple of cool announcements about our big data visualization startup. Meanwhile, I wanted to relate a stupid hack I needed to do before I could analyze my reading preferences: a way to download my list of Kindle books from Amazon. Amazon lets you export the list of physical purchases, but they try to only show a few digital purchases at a time. I have hundreds of books, so that's a no go. Searching on Google showed others got stuck on Amazon and Goodreads as well. After some dead ends (examining receipt pages, digging around files in their native app, ...), I found a winner.

Long story short, here's how to extract your reading list from Amazon (~2 min) and, optionally, transform it into a CSV file (~2 min):

Extract the List of Books

Log in to your Amazon account
Click on "Your Account" up top
Click on "Your Collection" as part of the "Digital Content" box

You'll get to a page that's close but no cigar: books show up as you scroll, but at the same time, old ones get swapped out.
Hit the print button and wait. And wait. And wait...
At some point, everything will load. If a printer dialog pops up, cancel it.
Voila!

You can copy/paste the page into a text editor like Notepad and you'll get a list of records like:

Your Collection

Title: Diffusion of Innovations, 5th Edition

Author: Everett M. Rogers

Date Acquired: January 26, 2010

Rating:

Title: Guns, Germs, and Steel: The Fates of Human Societies

Author: Jared Diamond

Date Acquired: January 24, 2010

Rating:

Don't use something like Word because it'll probably copy the HTML structure behind the page.

Transform Into CSV

Most text editors support regular expressions for fixing up content. For whatever search/replace menu item you have, do the following three steps to turn it into a CSV:

Clean your data by removing commas
Find: ,
Replace:
Order your data by making each entry a comma delimited line
Find: \r(Title|Author|Date Acquired|Rating):
Replace: ,
Clean your data by removing all those "Your Collection" lines
Find: \rYour Collection
Replace:

The rewrites will turn the above entries into just two lines

, Diffusion of Innovations, 5th Edition, Everett M. Rogers,January 26, 2010,

, Guns, Germs, and Steel: The Fates of Human Societies, Jared Diamond,January 24, 2010,

Success! You have scaled the data wall and can plug in your personal preferences to Excel, Goodreads, or your own homebrew algorithm. Let's see how long it takes before Amazon plugs this hole!

Sneak Peek for My Strange Loop Talk on Parallel Program Synthesis

2013-09-14T00:14:00.000-07:00

I'm excited for Strange Loop (programmable bio!) and Emerging Languages Camp next week. My talk will geek out on the language design idea in Superconductor that makes parallel programming in it such a breeze: program synthesis!

To give a taste, this post takes a synthesis approach to programming regular expressions. The trigger for it was one of the most important issues for programming languages in the 21st century: increasing literacy. My geneticist friend was struggling to transform values in a huge spreadsheet, and telling her to learn regular expressions is a non-starter.

Uphill Both Ways.

Imagine a "quick" sed script to rewrite "Alonzo Church" into "C., A.":

sed 's#^\([a-zA-Z]\).* \([a-zA-Z]\).*#\2., \1.#g'

... if you were sitting over here, you'd be watching my eyes bleed right now. Also, I'm pretty sure that the code is buggy and might even erase my hard drive.

A New Hope.

Emina Torlak and I spent the last couple of days tweaking a synthesizer that can generate the above Sed scripts from just two examples:

(syn-sed
'(("Leo Meyerovich" ("L" "M") "M., L.")
("Emina Torlak" ("E" "T") "T., E."))
`(? "., " ? "."))

Each example specifies a name, what text to pull out of it, and the rewritten result. The last line defines a result template where the "?" symbols should get replaced by some of the input text.**

The "syn-sed" function will generate code that works like the Sed script above but without harming any animals. The relationship is strong: in theory, if you let your computer spin long enough, it will recreate any sed formula. As the tool outputs the desired formula, it also serves as a gentler onboarding to learning and using regular expressions. Going back to my biologist friend, that's a big deal.

Automating Test-Driven Development.

Regular expressions are tricky; we constantly have to test them on examples and tweak them until they work. The synthesis approach asks you to write down the input/output tests (specifications are good, right?), and in return, automates the crazy tweaking for you. If you ever find an example that doesn't work, instead of reverse engineering the regular expression and tweaking it, just add the new input/output test specification to the list of examples.

The regular expressions are just the beginning of what I'll show program synthesis can do, so see you at the talk!

Note: L* and other algorithms provide inference techniques specific to characterizing a regular language; the Sed example's use of a rewrite rule shows that we want synthesis for all the other DSLs too. For an amazing version of the regular expression scenario, check out Excel's new FlashFill!

**: I bet we can eliminate the result template with some more hacking.

Startup Name Picker: Stage II

2013-08-03T13:31:00.004-07:00

We're on to the second stage of picking our startup name. I'd love to learn what you think!

In a couple more weeks, I'll describe the data analysis we're using to break down the results.

OOPSLA Preprint: Empirical Analysis of Programming Language Adoption

2013-07-31T12:19:00.001-07:00

We put up a preprint of our analysis of how languages spread and developers adopt them. The camera ready is coming, so any feedback would be welcome. If anyone is extra ambitious, I'd love help in using our data to estimate the total number of languages out there :) The basic idea is to use a species estimator given our power law findings.

At the same time, I'm doing a lot of traveling in the next couple of months, and would love to meet up with folks:

Hawaii, mid August
Denmark, late August (IFIP WGLD)
Germany, early September
Missouri, mid September (Emerging Languages / Strange Loop)
NY/NJ, mid September (IBM PL Day)
Tentative: RI, mid September

Name Our Startup!

2013-07-20T18:23:00.001-07:00

Exciting news: we're launching a data visualization startup!

It is going to push the Superconductor project forward: we're building a service for prebuilt big data visualizations that help data analysts explore their data and analytics providers to report their results. Launching the company will enable us to keep hacking on the open source core while pushing forward with new ideas. Keep an eye on this blog as I write about what happens as part of founding a tech startup in the Bay Area.

In the meanwhile, if you've ever thought about naming a company, I've love for you to help pick ours by filling out a quick survey. Inspired by our colleagues at Mozilla, I'm going to be transparent where possible. An option in the survey lets you sign up to get involved with fun decisions like this one in the future.

Happy hacking!

Programming Language Popularity Revisited: Power Law vs. Exponential

2013-06-26T19:45:00.005-07:00

Understanding the 'tail' behavior of programming language popularity can help tell practicing language designers whether to sink effort into a domain specific language for a niche audience (long tail) vs. focusing on winner-takes-all with general purpose languages (short tail). I previously showed an analysis of languages in 200,000+ SourceForge projects from 2000-2010, which found popularity to follow an exponential curve. That means a short tail and most language use on SourceForge is centered in the big languages... or does it?

I cross-validated the result today with two other data sources: Ohloh stats of 500,000+ projects across different open source repositories, and our survey of 1,600+ Wired, Slashdot, etc. readers that asked about the primary language for their most recent project. Ohloh also shows exponential short tail behavior, but not our Survey. What the heck happened, right?

Conflicting cross-validation. The red and green exponential curves drop off in popularity starting around the bottom half of the languages. In contrast, just like there being a page for everything on the web, the blue power law line keeps going.

My first thought was that the data sets were measuring different things. Maybe commercial behavior is different from open source, but lines have blurred nowadays. It could have been that the SourceForge data was from 2-4 years before the others -- but both the survey and Ohloh were recent and in conflict. Or, perhaps, it's the double-dipping in Ohloh from counting any project a language is used in, rather than measuring just for when its the primary language. These differences are real, but I realized a simple but deadly methodological issue is at play.

SourceForge and Ohloh curate their list of languages! They only have about 100 languages -- if a language is not in their list, its use in a project will not be counted. The languages that would make up the long tail are not being counted! To get a taste, our survey was of magnitudes less people, yet it elicited 20% more languages. The survey measures what actual developers do, while my SourceForge and Ohloh data crunching was a meta-analysis restricted to what SourceForge/Ohloh chose to annotate. Other techniques, such as trawling Google search results as in langpop.com, are therefore similarly suspect for this style of curve fitting.

Going forward, I'd like to predict, for example, what an estimated tail of SourceForge and Ohloh language popularity would look if we assume its similar to the survey data. Furthermore, I'd like to test whether SourceForge and Ohloh are actually power laws once the truncated data set is considered (e.g., is the completion using survey data a power law?). My stats skills bottom out at what's posted here, unfortunately -- if this sounds like your type of thing, I'd love to talk :)

Just for fun: the cumulative distributions with matching trendlines

Superconductor-as-a-service

2013-06-24T19:45:00.003-07:00

We just got Superconductor running as a web service on EC2. You no longer need to install the compiler to get started! There's still a ways to go to make this fully usable, but the hardest part is done.

Currently, the compiler service outputs unoptimized JavaScript. Send a POST request of a JSON object to our service and you'll get the synthesized layout engine:

 var src = "interface I {} class C : I { children {} attributes { var x : int; } actions { x := 1; }}";
 var myRequest = new Request({
        url: 'http://ec2-54-218-69-113.us-west-2.compute.amazonaws.com/compile/',
        method: 'POST',
        data: JSON.stringify({
            'ftl': src,
            'target': 'js'
        }),
        onSuccess: function(text, xml) {
            console.log("received from server: " + text.length + " characters");
            if (text.substring(0,6) == "error:")
                console.error("Synthesis error: " + text.substring(6));
            else
                console.log('result', JSON.parse(text));
        }
    }).send();

Switching to this compiler service model is exciting in a few ways, but the first two important ones will be:

Legacy: as the FTL language upgrades, we'll just keep legacy compilers running. You won't need to see the bitrot for running legacy files. Once the API and site mature, we'll lock it in.
Multiple backends: as hinted by the 'target' field, we're going to start exposing our multiple backends. Right now the naive JavaScript one is up, and next on bat is WebCL.

To play around, I posted an interactive fiddle.

How We Fixed Temporal Locality of Work Stealing for the Parallel Browser

2013-05-22T13:59:00.001-07:00

Broken Temporal Locality in Work Stealing:

Red shading indicates a temporally-induced miss.

The end of my last post mentioned a big problem with work stealing: it has no temporal locality. For example, if a layout engine traverses Wikipedia's HTML nodes twice, 2/3rds of the nodes would move to different threads for the second traversal. To understand such a harsh critique and how we tackled it, you can try running the next version of the visualization:

var s = document.createElement("script");
s.type = 'text/javascript';
s.src = 'https://raw.github.com/lmeyerov/devnull/master/one-offs/workstealMulti.js';
document.getElementsByTagName('head')[0].appendChild(s);

Run visualization by putting into your browser's JavaScript console

Open a website, go to the JavaScript console, and put in that script. Hit the run button on the top-left once to do a normal work stealing traversal, and once the traversal finishes, hit the button again to run another pass. The first pass uses colors to show which thread got which node. As described in the previous post, spatial and intra-traversal temporal locality are great. The second pass switches to blue/red coloring to show, on the second pass, if a thread got the same node (blue) or a different one (red).

What we see is that, near the beginning of the second pass, work stealing is great: lots of blue near the top of the page. As the traversal continues, however, slight deviations occur. These compound, so the longer the schedule, the more random the assignment. By the end of the traversal, only 33% of the nodes were temporal hits. Not good! Our parallel layout engines do 3-9 passes, and often the data used in one pass is computed in the previous one, so that hurts.

For the parallel browser, we had a simple and effective solution: just record the old schedule and reuse it. This worked because it does several passes in succession of a big tree. Temporal locality isn't an issue for the first traversal, so we use work stealing to find a load balanced schedule. For subsequent traversals, we play the schedule forwards (top-down traversal) or backwards (bottom-up). We lose a bit of load balancing, but not much in practice (hurray big trees!), and gain a bit by lowering overheads (no dynamic queues etc., just p2p locking). Simple to implement and we've seen near-ideal scaling: 80-95% of ideal on 4-8 cores.

We did this work years ago, and since then, others have published nice generalizations. Common elements of locality-aware work stealing schedulers are allowing programmers to annotate locality groups (e.g., mark a node as part of a subtree/tile) or using static/dynamic analysis to infer it, and then using that information to pick the steal. I'm not aware of any that are smart enough to 'wait' as in our case, but it's a sensible next step in profile-guided systems. See Trishul Chilimbi's late 90's thesis work to get in the right mindset.

Visualize Parallel Work Stealing in the Browser

2013-05-05T16:24:00.003-07:00

I try to write at least one interesting program every week. This weekend, to spice up my dissertation talk, I built an animated visualization of how my parallel CSS engine partitions a webpage via work stealing.

Work stealing is a great parallel task scheduling algorithm that provides dynamic load balancing and spatial locality. The idea is that each thread has a local queue of ready-to-fire tasks that it loops through, and if it ever runs out of local tasks, it will steal tasks from another thread's queue. The visualization shows how this works for a parallel top-down tree traversal over a webpage's HTML tree. In this case, a task is a node, and executing a task is denoted by changing the background color of that node to match the thread's color. The node's children are then added to the local queue for firing, and the process repeats. Whenever one thread steals a task from another, the webpage node corresponding to the stolen task has its border highlighted by the color of the thieving thread.

To try it it out, open your favorite website, paste the following code into the JavaScript console, and hit the start button:

var s = document.createElement("script");
s.type = 'text/javascript';
s.src = 'https://raw.github.com/lmeyerov/devnull/master/one-offs/worksteal.js';
document.getElementsByTagName('head')[0].appendChild(s);

Alternatively, copy the following into your URL bar and hit start after it loads:

javascript:(function(){var s = document.createElement("script"); s.type = 'text/javascript'; s.src = 'https://raw.github.com/lmeyerov/devnull/master/one-offs/worksteal.js'; document.getElementsByTagName('head')[0].appendChild(s); }())

For this version, make sure you browser doesn't strip the "javascript:" at the front.

The animation shows several important things for parallelization. First, the same thread will run many tasks that are near each other, which indicates good spatial locality. The evidence of this occurring is that many regions of the webpage will share the same color. Second, steals are infrequent, which keeps overheads low and again highlights locality benefits. This shows up in the page as very few stolen nodes (colored borders). To measure it, the per-thread percentage counters at top show the ratio of stolen nodes to non-stolen ones, and on most webpages, I get a pleasingly low 5% miss rate. Finally, you can see a problem with the algorithm: the steal rate spikes at the beginning and end of a tree traversal. I made a simple optimization to the initial traversal -- I do a short sequential BFS traversal rather than immediately start with parallel DFS -- but did nothing here for the end.

My layout engine actually uses a novel semi-static work stealer rather Cilk-style dynamic work stealing. The reason is that Cilk does not account for temporal locality, which is important in situations such as multiple traversals over a tree because they revisit the same nodes over time. With Cilk-style scheduling, which thread a node lands on can easily change across different traversals, which is a huge hit. Instead, my approach is to use work stealing once to partition the tree, and then reuse the precomputed schedule across different traversals: load balancing suffers a bit, but temporal locality goes up.

Enjoy!

Monday, Monday, Monday! Dissertation Talk

2013-05-03T21:11:00.000-07:00

About time.

---

Your message for list eecs-announce has been forwarded to editor(s):

[Dissertation Talk] Parallelizing the Browser: Synthesis and Optimization of Parallel Tree Traversals

Speaker: Leo Meyerovich
Advisor: Rastislav Bodik
Date: Monday, May 13th, 2013
Time: 3:30pm
Room: 373 Soda Hall

ABSTRACT:
From low-power phones to speed-hungry data visualizations, web browsers need a performance boost. Parallelization is an attractive opportunity because commodity client devices already feature multicore, subword-SIMD, and GPU hardware. However, a typical webpage will not strongly benefit from modern hardware because browsers were only designed for sequential execution. We therefore need to redesign browsers to be parallel. This thesis focuses on a browser component that we found to be particularly challenging: the layout engine.

We address layout engine implementation by identifying its surprising connection with attribute grammars and then solving key ensuing challenges:

1. We show how layout engines, both for documents and data visualization, can often be functionally specified in our extended form of attribute grammars.

2. We introduce a synthesizer that automatically schedules an attribute grammar as a composition of parallel tree traversals. Notably, our synthesizer is fast, simple to extend, and finds schedules that assist aggressive code generation.

3. We make editing parallel code safe by introducing a simple programming construct for partial behavioral specification: schedule sketching.

4. We optimize tree traversals for SIMD, MIMD, and GPU architectures at tree load time through novel data representation and scheduling optimizations.

Put together, we generated a parallel CSS document layout engine that can mostly render complex sites such as Wikipedia. Furthermore, we ran data visualizations in the browser that support interacting with over 100,000 data points in real time.

Parallel Parsing isn't Hard (Or, Parallel JSON via Web Workers!)

2013-04-07T15:54:00.000-07:00

Generalized parallel parsing is hard. Many a Ph.D. has been burned by attempting parallel parsing. Guy Steele wrote papers about it, and you'll find custom ones for favorite modern technology X for X = JavaScript, HTML, XML, etc. However, in practice, practical parallel parsing does not have to be so hard because parallel parsing research generally focuses on extreme cases. For example, our group examined automatically generating parallel parsers and handling arbitrary HTML.

Actual parallel parsing is easy. Real applications provide significantly simplifying assumptions. Case in point: for our browser-based big data visualization framework, we needed to somehow load in big JSON arrays. Modern browsers provide a fast native function "JSON.parse :: String -> JSObj" that is fine for normal sized data sets, but parsing 9MB of sparse data takes over 1s, which requires a loading screen and eats your battery. The solution took ~2 days: on the server, split the data into multiple arrays, and on the client, use web workers to parse each array in parallel. Even though I'm controlling the parsing in JavaScript, the actual parsing is still being done natively by calling into JSON.parse for handling each fragment.

Anyways, the proof is in the pudding. The relevant benchmarks are impact on file size and load time.

Benchmark 1: file size

Splitting one of our sparse JSON data files into multiple chunks has no real hit to the file size, and due to some uninteresting phenomena, actually helps when gzip is used. I'm also showing the benefit of compressing repeating zeros ("sparse json") for our particular data set.

Benchmark 2: speedup

For the second benchmark, I'm testing loading the data set from a local hard drive when using different formats. The first two columns are sequential data formats, and with the second column primarily demonstrating the benefit of doing preprocessing for my particular application. The blue part of each column shows, in ms, how much time is spent reading the file from disk and parsing it.

The important part is comparing the blue of the third column against the blue part of the second: using workers to parse JSON chunks is 2x faster than parsing the file in one sequential go.

For further parallel speedups, it is important to realize that this application hit Amdahl's Law. In particular, the sequential stuff, like the black subcolumns, must be parallelized. The blue columns also have sequential code due to APIs I'm using. First, Safari does not have zero-copy message passing (transferable objects), so a sequential copy is made in communicating a parsed fragment back to the master. Second, I'm actually creating a big typed array, so even current web worker APIs do not help: I want to the Buffer into the worker, not get a new buffer out of one, which means I have to do a sequential copy even in Firefox and Chrome. Basically, we're seeing the web's poor support of message passing forcing a lot of slow, sequential copies.

Finally, I only benchmarked the case of local file loads. Our application, ultimately, will be used online with a server providing the data on-the-fly. The optimizations I showed should still help even if the application is network bound: they also enable pipeline parallelism. By splitting the JSON, parsing one chunk is now done in parallel with downloading the next. Modern webpages alternate between waiting on the network and the CPU, which this solution elegantly addresses.

Conclusion

So there you have it -- parallel parsing, in practice, should be easy. I did a constrained case of handling big JSON arrays. Even for more general JSON, it should only take a day more of work: partition the JSON via work stealing -- I successfully did a similar thing in my thesis for HTML in a few hundred lines of C++.

If you'd like the code, it'll be part of our Superconductor (automatically GPU-accelerated web programming framework for big data visualization) release next month. Ping me if you'd be interested in working on parallel parsing of arbitrary JSON -- it should be awesome!

UPDATE

I more carefully measured the overheads and also did a couple more optimizations. The chart below shows the new results. It also now includes the message passing overheads in gray, where ~90% of it would go away in Chrome with transferable objects and the other 10% might be eliminated with ownership transfer of buffer views (sub-buffers), not just buffers.

Two big things are going on:

The workers now perform decompression rather than the master. However, decompressing in the worker has a cost: each worker now returns an inflated result message. Safari does not have ownership transfer so almost 100ms is spent copying the message back to the main thread rather than passing a pointer.

The overhead is still worth it -- the blue region shrunk a lot, even if there is now a big gray region. (The gray region is in both because the sequential job runs in a worker in order to avoid pressuring the UI thread.) If/when Safari gets transferrable objects, 90% of the gray bars will disappear.
Faster reduction of worker results into the final GPU buffer. Typed arrays support method set that can also help such reductions. It acts like a memcpy, so result.set(chunk, len) copies array buffer "chunk" into array buffer "result" starting at byte offset "len" into "result." It only takes about 13ms. If the typed array spec was extended so that disjoint sub-buffers could be transferred across workers, the other 10% of the gray bars would disappear.

Adoption-Oriented Languages

2013-01-26T20:34:00.004-08:00

Language design decisions should not just increase adoption but also exploit adoption. For example, I just measured how popular languages can rely upon Stackoverflow as a code assistant. The chart below shows that increased language popularity on SourceForge (x axis) leads to faster answer times for questions asked on Stackoverflow (colored bins on the y axis):

Stackoverflow Time-to-Answer vs. Sourceforge.net Language Popularity. Raw data grabbed a stackoverflow query that modifies G. Winker's, and language rankings from our previous analysis.

Top 10 languages have questions answered within 5 hours over 80% of the time, but for languages worse than Top 50, that shrinks to only 50% of the time. In terms of a simple blocker at work, that's a big deal: you can reliably ask a question, go work on something else, and come back to the answer!

Of course, measuring response time vs. popularity is up to interpretation: it could be that as adoption increaess, people ask easier questions. However, I suspect the chart is actually undercounting the adoption benefit: the more questions are answered, the more people don't need to wait for answers because they can just search for old ones! As one measure, we see that a language's popularity relates to its answer corpus size:

Stackoverflow Answer Corpus Size vs. Sourceforge.net Language Popularity. Same dataset as above.

I had to switch to a log-scale axis for answers! For popular languages, search becomes a valuable tool because Stackoverflow alone provides a FAQ of 100,000 solutions. An enterprising individual might want to further examine the duplicate rate, which I suspect would provide an insightful indicator for the likelihood of a query already being answered by a previous response.

Open source library repos are another case of a feature that improves with adoption: the library of builtins is ever expanding. Likewise, one of my favorite research projects is cooperative bug isolation, which exploits the adoption of a program to help narrow down causes of bugs. (AFAICT, most software companies do some form of tracking error and performance dumps.) A/B testing for feature design is also increasingly common. As another example, in academia, code completion tools are also increasingly incorporating corpus-based solutions. A corpus can provide more value than type and namespace based solutions because, for example, synthesized code completions will resemble what people would actually write.

I started sketching out the notion of adoption-oriented language design in a position paper last week. I struggled to think of features that couldn't be designed to strengthen with adoption. For example, verification, testing, security, program synthesis, and optimization could all be designed to automatically exploit adoption of either the language, the library, or a program. What strikes me is how little adoption is exploited today. Outside of the cases, am I missing any that are commonly practiced, or should be?

Superconductor Language in Action: Easy Big Data Viz in Your Browser

2013-01-20T19:43:00.000-08:00

Exciting news: we'll be talking about Superconductor at the O'Reilly Fluent conference! This will be the first time we show it outside of small seminars, and will hopefully coincide with our open source release. This video proposing our session gives a feel for what Superconductor can do. The link skips right into the demo:

The basic idea is that you write a normalish webpage (HTML5, JS, JSON, CSS) for including and manipulating your big data viz, except:

Instead of relying up on the browser to run it (parse, layout, render, & animate), you load in our GPU-accelerated JavaScript libraries for the heavy lifting. Behind the scenes, we automatically exploit workers, WebCL, WebGL, etc.
Instead of using JavaScript for fancy layouts, you load in a widget made with our declarative layout DSL (or use it to define your own). Our parallel program synthesizer automatically finds the parallelism in the widget specs and our code generators output GPU code based on it.

We're finally ramping up on a paper with the end-to-end system details; this will be the first time we discuss running inside of a commercial browser and using GPUs. Papers have a ridiculous delay period, so of you'll be at SIGGRAPH (LA), PPOPP (Shenzen, China), or Intel's TechFest (Portland), you'll be able to catch a demo before then.

Reactive Objects and Arrays via Direct Proxies

2012-12-26T19:10:00.006-08:00

Arrays are a crucial building block for programming. Consequently, an essential question for functional reactive programming is how to react to imperative array updates. Designing a clean interface gets bogged down in issues like identity, API consistency, and efficient incrementalization. I used a recent extension to JavaScript, Direct Proxies (Firefox-only), to sketch a transparent dual-mode model (JSFiddle) for Flapjax. I made a reactive array interface that covers the entire Array interface and supports both instant and batched updates. A fun holiday break from Superconductor :)

Update: I generalized the code in two ways: it works with object instances and also allows choosing whether the prototype is Array or Behavior.

Transparency

The idea is to create a reactive array that is tied to an existing normal array:

var arr = ['init'],
var arrB = bindB(arr);

From then on, interactions with one array are automatically reflected from one to the other. (In particular, arrB uses arr as its backing store and proxies interactions to it):

// assert(arr[0] == arrB[0]);
arr.push('a'); // assert(arr.length == fxArr.length);
arrB.push('b'); // assert(arr.length == fxArr.length);

By defining traps for JavaScript's meta-object proxy protocol, I guarantee that all of JavaScript's array methods are supported by the reactive array arrB. All in all, for normal JavaScript, it should not matter if you pass around arr or arrB: they act on the same underlying data.

(Full transparency might be wrong. I'll raise a semantic issue at the end about what if you *do* want to distinguish reactive arrays vs. flat ones using operators such as instanceof.In my implementation, I let you pick as an optional parameter to bindB.)

Functional Reactivity and Instant Reactions

Now the cool thing is that array mutations can be automatically reacted to using normal functional reactive programming constructs.

For example, we can declare a live counter of the array size:

insertDomB(arrB.liftB(function (av) { return av.length; }));

The above snippet is the usual functional reactive code that is a joy to read. It displays the length of the array. Whenever arrB updates, the GUI will automatically update to show the correct length.

The new ability here is that wrapped array mutations automatically trigger reactions:

arrB[30] = 20; //updates length counter on screen

arrB.push('hello'); //updates length counter on screen

I'm calling these instant reactions because each mutation registers an update event. In the above statements, two update events will be fired, one for each statement.

The original array and reactive array refer to the same data, but differ on how they interact with the event system. Updates to the original array do not trigger reactions:

arr.push('world'); //no screen update

Maintaining non-triggering behavior of the original array is important so that non-reactive code not ready for the extended behavior does not trigger massive DOM updates. In places where it is safe to do the switch, arrB can be swapped in.

Batched Reactions

A nice pattern falls out of the wrapped and unwrapped view of the array. When many updates to an array should happen, we can batch them for a single subsequent response:

function addSome(n, arrB) {

//batched update

for (var i = 0; i < n; i++) {

arrB.last.push(i);

}

//notification

if (n < 0)
arrB[0] = arrB.last[0]; //updates length counter on screen

}

addSome(10, arrB);

The "arrB.last.push(i)" calls trigger no reactions, while the assignment to arrB[0] triggers an instant reaction. This pattern of silent array updates followed by an instant reaction on the reactive view is a batched reaction. It is largely an optimization, but if you create local invariants inside the body of addSome, you can also use the pattern for (non-nested) transactional reactions.

Object Instances and Meta Protocols

In response to Shriram's comment, the technique here is a late-bound dual to his work in making legacy classes reactive. For Racket's class system, he showed how to make a reactive subclass: the case of arrays would act like "var myArrB = new ArrayB(1, 2, 3); assert(myArrB instanceof Array)". The dual problem examined in my post is where an instance of a class must be made reactive ("var myArr = [1,2,3]; ...; var myArrB = bindB(myArr)"). It is an important practical distinction because the developer writing "var myArrB = bindB(myArr)" might not have control over "var myArr = [1,2,3]" nor "...".

His connection is important for two reasons: it provides a principle for how bound arrays should act (as subclass instances) and, more generally, shows that the same approach can be used for making object instances reactive.

1. Design principle of subclassing. Given an array, his connection tells us that reactive version should act as a subclass of Array. As seen above, this works for methods like push and [] (get). However, the desired object protocol behavior is not obvious. For example, should "assert(myArrB instanceof Array)" succeed? By the subclass reasoning, yes!

Unfortunately, setting myArrB to be an instance of Array breaks introspection within the Flapjax library. To add dependencies to an object, Flapjax checks whether it can register event listeners. For example, "liftB(function (v) { return v.length; }, myArrB)" triggers a check "arg2 instanceof Behavior": if myArrB is an Array and not a Behavior, Flapjax will not register listeners on it! Some examples still work, such as "myArrB.liftB(function (v) { return v.length; })", because the check is elided. For now, I support two constructor options:

var xB = bindB(arr);
assert(xB instanceof Array); //indistinguishable from Array
xB.liftB(function (v) { return v.length; }); //only supports chained reaction

var yB = bindB(arr, true);
assert(xB instanceof Behavior); //distinguishable from Array
yB.liftB(function (v) { return v.length; }); //chained reactions

liftB(function (v) { return v.length; }, yB); //and as arguments

The non-default constructor is more readily distinguished from an Array, and Flapjax uses this ability to out-of-the-box to to react to it. If code consuming "myArrB" does not need "myArrB instanceof Array", I suggest the second, non-default form.

2. Generalization to Objects. The motivation of this post was to handle array instances, but as Shriram implies, those are a special form of object instances. We get the simpler case of objects for free!

var o = {};
var p = bindB(o);

insertDomB(DIV("o has x: ", p.liftB(function (v) { return v.x ? true : false; })));
//display shows false

p.x = 1; // o.x == 1 and display updates to show true
delete p.x; //o.x == undefined and display updates to show false

The code snippet above shows creating a reactive view of an object. The original object is the backing store for the view, and edits to the reactive view automatically trigger DOM updates. As with arrays, when reactions occur can be controlled by choosing to edit the raw object or the view.

Conclusion

Via proxies, I was able to make imperative arrays play nicely along their entire API with our FRP library and support both instant and batched/transactional updates. You can play with this in Firefox via my JSFiddle. There is more to do (for example, the direct proxy API precludes behavioral indices like fxArr[secondsB]), but the flexibility of this approach is handy.

APPENDIX

var arr = ['init'];
var fxArr = bindB(arr);

Google Tech Talk Video on Socio-PLT: Quantitative and Social Theories of Programming Language Adoption

2012-11-29T12:40:00.002-08:00

My Google Tech Talk on the Socio-PLT work was recorded and posted. It starts with the quantitative stuff + questions on it, and then switches to the social theories: pick your poison. Enjoy!

Temp URLs for Flapjax documentation

2012-11-28T11:42:00.005-08:00

The Flapjax server is a bit wonky right now, so if you are looking for online documentation, check out the following:

Of course, you can always check the git repo for the latest.

Hope that helps!

What Women Want

2012-11-22T13:34:00.004-08:00

Trending on Quora is the question, "Which programming language is the most female friendly?"I do not know (I can provide primary sources who will verify this), but based on our survey of 802 men and 154 women, I can answer which languages females prefer over males. To learn how to think about these questions, see my recent Google Tech Talk or the links below.

Gayle presciently suggests that "Python is also a no-no because, I mean, you just named a language after a snake. Ick! And, I mean, do I need to call out the Freudian imagery there?" Go Gayle -- there is indeed a 3% drop! However, despite Gayle's insight that "All women love shiny objects," that does not help Ruby. Our numbers show a 7% drop for Ruby, so Ruby's bad press might be representative.

Overall, we saw little difference among the top 10 languages known by males and females. The ordering is fairly stable, and overall knowledge is similar (see the pink trendline). A few language jumps stand out: C, PHP, C#, and Ruby drop for female knowledge, while Excel rises.

If you're curious, check out our methodology, more of our statistics and raw data, and what a language designed for women might look like. Long story short, for the above statistics, we had good respondents: mostly educated, mostly employed, and biases because we polled students taking a free UC Berkeley online Ruby course on software as a service.

Asymptotic Productivity of a Language Feature

2012-11-03T21:00:00.000-07:00

Good news: our big data visualization DSL has a new name (Superconductor!), runs in a browser, and even more unusual, a per-feature asymptotic analysis.

We built a synthesizer for Superconductor that automatically maps widget code down into parallel algorithms, but synthesis isn't magic: the more you want it to do, the longer it has to run. Synthesis is essentially a search that automates manual thinking a programmer would have performed. This introduces a new way of thinking about the benefit of language features. Features have a cost, and instead of being in runtime complexity, it is now in compilation speed, which is arguably a formal proxy for developer time. The new language design question is how to tame these costs by isolating them, and when pricey features are still desirable, how to provide levers.

Consider two of the following features in our language:

Automatic full tree traversals. For a particular top-down parallel traversal over a document, what parts of the (declarative) computation can be safely mapped into it? Not forcing the programmer to figure this out ends up being O(A^2) in the number of static object fields being computed. It took a bit of work (iterative refinement and topological sorting), but well worth it!
Automatic subtree traversals. Sometimes, different parts of a tree have different types of data dependencies. For example, text in CSS is represented as a subtree of the document, and several computations over it are inherently sequential such as line wrapping. The tree traversal that encounters text does not need to be sequential, however: for each traversal, we can run different types of subtrees with different types of traversals, and thereby exploit parallelism within some subtrees and even by running disjoint subtrees concurrently. The feature to automatically infer subtree traversals blows up in the number of types of nodes (classes). Basically, each partitioning of the classes is a different way of statically characterizing a different subtree (and matched with a traversal type, a prospective parallelization scheme).

Synthesis is fast enough that automatic parallelization of full tree traversals are effectively free. However, specializing for per-subtree traversal schedules is only fast for programs with few types of nodes. Subtree traversals are useful in practice (such as if you enjoy stylized text on a webpage!), so we still need to support it. What is a language designer to do?

Deprioritization. Of parallelization can occur without using a slow feature, it will. In this case, the search will look for a full tree traversal before trying subtree ones. O(A^2) asymptotics are actually preserved, even if the full tree traversal is impossible: if there is no full tree traversal, we guarantee there is no subtree traversal, and therefore can stop compilation and terminate with an error. Enumerating all parallelizations will reveal a subtree traversal if it exists, this will not be exercised during most development.
Sketching. We use sketching for targeted opt-in prioritization of slow features. If you know the third tree traversal of the algorithm should use subtree traversals, say so, and even better, give a hint as to how to group the classes. If you do that, synthesis will still handle mapping individual computations into the traversals, including the subtree ones, and compilation is still O(A^2)!

Asymptotics of synthesis is an intriguing way to characterize language features, and perhaps a step towards representing developer effort. It defines how much is 'unsaid' in a precise way, how hard is the 'exercise for the reader'. There is still more to be desired -- the asymptotics is subject to the synthesis algorithm and translation of the features into it -- but I found it to be a neat, and an insightful indicator for productivity.

Quantifying Social Influences on Language Adoption

2012-08-31T09:17:00.005-07:00

Average influences for picking a language at work

As alluded to in the previous post, Ari and I have been hard at work at quantitatively analyzing how programming languages get adopted -- or fail to. For example, the above chart shows that for commercial projects, social factors (open source libraries, legacy code, and familiarity) matter much more than language support (correctness, simplicity, development speed, tools, language features, ...). This chart is also fascinating because we see that developers act differently depending on the company size.

Check out our draft "Social Influences on Language Adoption" for more fun charts where we performed and analyzed large surveys and also looked at 10 years of the SourceForge repository with over 200,000 projects. As another example, we validated some of our suspicions in the sociology survey that DSLs can be understood in terms of competing niches (e.g., popularity comes from spreading to other niches, not being the best in the niche). We'd love comments! More is in the pipeline -- we'll be releasing the raw data and also a small writeup about the methodological hazards we had to circumvent for this type of research.

Socio-PLT camera-ready and a glimpse at the next step

2012-07-27T16:22:00.002-07:00

Our Onward! 2012 draft about matching problems in programming languages to social theories about adoption made a stir -- and solicited some great comments. We're cleaning up the camera ready, so if there are any final comments, we'd love to incorporate them for the 'final' print version. It's a controversial topic!

As a follow-up, we've been doing some heavy quantitative analysis of extrinsic (social) and intrinsic factors in language adoption. These charts should give you a taste:

Fig 1: Factors in Picking a Language for A Recent Project

Fig 2: Language Popularity on SourceForge.

The first figure is cool in that it shows that social factors are more important than intrinsic features when picking a language. Language designers are community builders.

The second figure starts questioning the social structure. Popularity, city populations, etc. often follow power laws, and therefore growth gets modeled by some intuitive generative processes. However, SourceForge for ~200,000 projects followed an exponential curve. What type of processes can make more sense there?

Anyways, hope the camera ready looks good and the quantitatve analysis sparks thought :)

Synthesis over Parallel Patterns: A Leap Beyond Parallel Frameworks, Types, and Annotations

2012-07-06T11:54:00.002-07:00

We've been struggling with explaining the theoretical PL parts of our language research, but I think we're finally circling in. Basically, we found attribute grammars OK for defining the functional behavior of CSS and simple enough for running basic compiler analyses, but the formalism is poor for programming over the parallel patterns used for efficient runtime evaluation. That's where our language extensions for synthesizing over parallel patterns comes in.

Synthesizing over / into parallel patterns breaks down to three high-level issues:

The low-level language of patterns. The low-level language has to thoroughly express how our crazy-optimized tree traversals can be used. Think of it as the assembly language for parallel algorithms.
The usable high-level language. Writing in assembly sucks. Unlike traditional higher-level languages, which suffer from leaky abstractions, ours is a superset of the low-level one: you can always pick the right level. We do this by adding the simple notion of a hole. Assemble the patterns where and how you want, but whatever patterns are inferable or unimportant, just leave a hole and let the compiler figure it out.
The compilation technique for going from the high-level pattern language to the low-level one. I'll try to give a more detailed explanation in a future post. In a sense, our algorithm is a form of CEGIS (counter-example guided inductive synthesis) that searches over ways to complete a partial program. Every time there is a potential candidate, it checks if any input would trigger a bug in the candidate, and if so, prunes out this and any other completion with the same sort of breakage. Ours is a bit cooler than usual because we have a domain-specific constraint solver, use symbolic counter examples ones that give asymptotic progress on the search, and we get a queryable debugger for free. All for another day :)

First, however, a recap of our use of attribute grammars for the functional specification language, all of which sits besides the pattern specification language.

Background: Attribute Grammars

The functional behavior in our language is specified with attribute grammars. For example, to define CSS, you'll say the width of an HBox is the sum of its children. That says nothing about when it is evaluated. Later, via our pattern specification layer, you can control that as well. In theory, other logical specification languages other than attribute grammars can be used, all the way up to your traditional favorite imperative language (see Sketch). However, the road from attribute grammars is clear, with most other alternative surface layers adding a painful indirection.

A traditional attribute grammar would let you declaratively define the horizontal box layout widget as follows:

HBox -> Node Node { HBox.width := max(HBox0.minWidth, Node1.width + Node2.width); ... }

Under our extensions (object-orientation, loops, etc.), we would instead write:

class HBox (paintRect) : Node attributes: input minWidth var intrinsWidth children: childs : [ Node ] constraints width = max(minWidth, intrinsWidth) loop childs: intrinsWidth = fold 0 .. childs[i - 1].width

Hopefully the mapping is intuitive. Our extensions are nice, for example, because we support lists of children. Instead of making an awkward NodeList tree schema with a traditional grammar, you can just have a list of Nodes ("childs : [Node]") in our modernized form (think EBNF). In the end, after some compiler translation, it's the same thing. After reductions, traditional AG compiler checks ensure that every variable is assigned exactly once (well-defined and non-ambiguous spec) and can generate a schedule that orders the assignments. Code generation (e.g., of a layout engine) is a direct step after getting the schedule.

In the example, our compiler realizes the width of an HBox should be computed after the loop. More subtle, when and how to perform the loops is determined as well. For example, this grammar defines a tree where some nodes have interface Node, such as HBox ones. The width of these nodes will be computed in a bottom-up or inorder traversal over the entire tree: for an inorder traversal, the compiler would insert a "recur" right before the computation of "intrinsWidth." Writing loopy code in our language is cathartic for this reason. You just say a statement occurs in some loop, and the compiler will figure out in which loop and when, and reason about both local loops over the children of a node and global loops over the tree.

To learn more about attribute grammars and our use of them for layout language specifications, I previously wrote about our declarative looping construct and an early experience in mechanizing CSS's automatic table layout specification.

The Low-Level Pattern Language

Our conceptually deep extension really starts with being able to express this new fragment:

schedule: (bottomUp ((HBox (intrinsWidth width))) ) ; ??

I'll get into the "??" bit later, but some of the low-level language shows through here: a bottomUp (parallel postorder) tree traversal. Both bottom up and inorder tree traversals are valid passes for laying out any tree in this widget language, so our declarative pattern scheduling construct lets you pick which one. Most layout languages have many passes: if there was another class in this language, whatever pass comes after the semicolon would presumably handle whatever it needs to solve.

Our schedules are expressive and fine-grained. The one above says exactly what attributes will be solved in the first bottomUp pass. Furthermore, the compiler will check that these attributes really will be solved in such a traversal. This is great if someone changes code elsewhere that has a non-local impact on the dependency structure, which is quite common in practice. The patterns can be complicated as well, such as using a (sequential) inorder traversal for some subtrees while doing an overall parallel bottom up, so help with reasoning about dependency validity is huge.

The amazing expressive bit about parallel pattern languages comes next, however.

High-Level Pattern Language: Declarative Scheduling with Holes

Imagine our HBox widget is being added to a parallel library. There might be some other traversals that happen after, but we want to guarantee that it will solve in the first one. The sequencing operator ";" runs one pattern after another. Powerfully, instead of saying what pattern to use next, we leave a hole, "??". It might be instantiated as another pattern, say "topDown", or even another composition of patterns, say "topDown ; bottomUp". The synthesizer will figure out what is valid. These can quite non-obvious. For example, we repeatedly found inorder tree traversals that sequentialize a computation can often be eliminated. Instead, a global parallel (topdown or bottomup) traversal is run, and only certain subtrees will be run as sequential subtraversals.

Holes can be anywhere (see the last line of the grammar above). If we don't care at all, we might replace the entire schedule with "??". More commonly, we'll specify something like that a bottomUp should be first and then trust the synthesizer to compute the right attributes in it: "(bottomUp ??) ; ??".

Not shown in the grammar above, and generally only rarely exploited, arbitrary Prolog expressions can actually be used to constrain the holes. For example, the schedule may be one where the last traversal is an inorder one that makes sequential rendering calls. Writing "?? ; (Inorder ??)" is incorrect because it presupposes there is a preceding traversal. Prolog, for all its oddities, ended up being a great for such constraints.

Synthesizing over Parallel Patterns

The above declarative pattern language let's us automatically use efficient parallel patterns with details where you care and holes where you don't. Synthesis over parallel patterns is powerful and expressive leap over say "@parallel" loop annotations in C++, map/reduce/etc. skeletons in cloud computing, and type-directed data parallelism in Haskell:

Our synthesizer finds complicated parallel pattern usages. Not discussed, it doubles as a parallelism inspecter/debugger. (Topic for another day: the algorithms under the patterns, such as my cool semi-static extension to work stealing that gives temporal locality and drops overheads).
Our synthesizer automatically generates code to exploit the parallelism based on an orthogonal specification. No need to group code in the spec based on the parallelization scheme!
Our low-level pattern language lets programmers communicate to each other and the compiler the precise parallelization scheme.
Our high-level pattern language (holes via synthesis) lets programmers communicate at an arbitrarily high level. Combined with the above, we get some very different styles of parallel programming: sometimes we roll in the mud, sometimes we don't.
Our synthesizer checks and rejects invalid schedules. This is good both when designing the initial code and especially essential when maintaining it. Editing someone else's parallel code is normally terrible: now we can both precisely learn about and check against the previous versions!

It'll be fascinating to see if the community can get such declarative schedule synthesis for applying patterns beyond the tree traversal scenario. For example, I bet most graph computations (e.g., stencils) can have their level of abstraction similarly raised through our basic model.

Socio-PLT: Quantifying Language Perception

2012-06-06T15:36:00.005-07:00

We finally released our interactive visualizations for exploring programmer beliefs about programming languages. We've been scouring several large data sets -- 10 years of SourceForge repo data, mass surveys of thousands of programmers each, etc. -- so visualizations like these help us get a grip on what's going on. Beyond revealing many surprises, such as static typing anti-correlating with code reuse, they are fun to play with.

Check it out! (Animations are fastest in Chrome/Safari)

Socio-PLT: Principles for Programming Language Adoption

2012-04-08T18:47:00.007-07:00

Ari and I are getting ready to send out our first paper on socio-PLT, the sociology of programming languages. We've been performing qualitative and quantitative analysis of language adoption, and I've been thinking about how to apply sociological principles to the design of my own languages. This paper 1) overviews some of my favorite cases that I gleaned from reviewing relevant sociology research over the past few years and 2) connects it to programming language design, both in the scientific design of existing features and the principled and creative design of new ones. Basically, it shows how understanding results from sociology can influence your approach to language design :)

I just put up a draft and would love comments. I suspect the paper may be controversial, but I would like it to be so for the right reasons :) Did we misrepresent anyone or leave out any awesome case studies? Was anything belabored and boring, or terse and tantalizingly vague? This is still in the draft state, so we have a lot to do and would appreciate feedback :)

Socio-PLT: Principles for Programming Language Adoption

Why does one programming language fail and another succeed? What does this tell us about programming language design, implementation, and principles? To help answer these and other questions, we argue for examining the sociological basis of programming language theory: socio-PLT.

This paper presents a survey for programming language adoption principles drawn from various sociological fields. For example, many programming language features provide benefits that programmers cannot directly and immediately observe and therefore may not find compelling. From clean water to safe sex, the health community has long examined how to surmount similar observability barriers. We discuss how principles and techniques drawn from social sciences such as economics, public health, and historical linguistics relate to programming languages. Finally, we examine implications of our approach, such as for the design space of language features and even the expectations of scientific research into programming languages.

Looking forward to your thoughts! (draft pdf)

Languages for Bad Programmers

2012-03-10T00:18:00.007-08:00

Bad programmers are linguistic victims and good programmers are masochists.

Brett Victor is going viral with an inspiring video on language and tool design (and philosophy). The language community has actually already made some strong strides in the directions he wants. Some of my favorite research is in tangible programming, live coding, and omniscient debuggers.

Patrick Lam picked up on something else. As part of Brett Victor's philosophy that every code artifact should be directly (physically) manipulatable and understood, Brett believes requiring indirect manipulation and indirect understanding to be language design flaws. In particular, programming should not require mentally simulating an abstract Von Neumann machine that steps through your program. Not everyone agrees: Pat observed that, on the list of signs of being a bad programmer, the very first warning that you are a bad programmer if you cannot "run the program in your head".

Here's the thought. What would a language for bad programmers look like? Looking at the list of hacky "bad" programming practices, can you imagine a future where language and tool support will advance enough that they're the acceptable norm? The "bad" habits actually form an admirable set of goals for the language research community:

Warning sign: Cannot simulate the program in their head.
Goal: Get the computer to do the simulation.
Warning sign: Have a poor understanding of the language's programming model.
Goal: If I make basic grammatical mistakes when I speak, people correct me -- why doesn't the compiler?
Warning sign: Chronically poor knowledge of the platform's features. Symptoms: reinvent language and framework code, "Email me teh code, plz" messages on forums, etc.
Goal: Instead of viewing code copying as a bug, it's a design goal: I suspect *most* code today is duplicated, so I look forward to the future where the emphasis is on searching and synthesizing code rather than learning and writing it.
Warning sign: Struggle to comprehend pointers. Symptoms: failure to implement a linked list, allocates arbitrarily big arrays, inability to find pointer arithmetic bugs, etc.
Goal: raise the level of abstraction so programmers don't have to think about these issues.
Warning sign: Have difficulty seeing through recursion.
Goal: Thinking concretely should be fine, and the tools should walk you through the base cases and generalization.

You can apply similar reasoning to the category of "mediocre programmers" and, my favorite, "pinball programmers". Pinball programmers struggle with edge cases, or simply do not care. They can be a security disaster. Again, however.... so what? These types of problems are exactly what we built computers to solve: rote grunt work.

The shocking conclusion of the bad programmer essay is the signs that you shouldn't be a programmer. If you cannot determine the order of program execution, cannot think abstractly, poorly organize your code as an ever-expanding ball of mud, believe the code and runtime are unreliable, or simply don't care about much of the code quality, you shouldn't be a programmer. Hogwash! If these traits are required for programming, our ability to write code that keeps growing in ambition by magnitudes seems doomed. I can fairly neatly bucket these warning signs as inevitable programming realities (massive and concurrent code on unreliable hardware) and goals ("search, don't sort"; declare what instead of how).

Maybe the programmers aren't really all that bad. It sounds like today's languages are the stupid ones.

(Updated 1/26/2013 with minor editing.)

Loop synthesis: more declarative than functional programming?

2012-03-07T20:57:00.004-08:00

As part of the FTL language, I've been playing with the idea of declarative loops. For example, I'd like to write:

for i in range(0, n):
b[i + 1] = g(a[i]);
a[i - 1] = f(b[i - 4]);

First, the synthesizer should figure out that the problem is under-constrained. It should report that the following values are undefined:

a[0..2] = ??
b[0] = ??
a[n] = ??

If, as suggested by the synthesizer, I refined the program to be consistent:

a[0..2] = 0
b[0] = 0
a[n] = 0
for i in range(0, n):
b[i + 1] = g(a[i]);
a[i - 1] = f(b[i - 4]);

I'd like to get:

a[0] = 0
a[1] = 0
a[2] = 0
b[0] = 0
b[1] = g(a[0])
b[2] = g(a[1])
b[3] = g(a[2])
for (int i = 3; i < n - 1; i++) {
a[i] = f(b[i - 3]);
b[i + 1] = g(a[i])
a[n] = 0

Note that the synthesizer performed loop peeling -- it figured out to do loop peeling to emit assignments for b[1], b[2], and b[3]. Furthermore, it reordered the assignments in the loop and performed loop skewing -- it changed the indices of the assignments, such as from a[i - 1] to a[i], to ensure an array value is written before it is read.

Milind and I just worked out most of the theory for this today. You can think of it as a generalization of attribute grammar synthesis to loop code. Basically, if we assume the input code is singly assigned -- array values should have one unique value -- this is a matter of unrolling the intermediate steps of the loop, scheduling their dependency graph, and reconstructing the Von Neumann-friendly loop. The weekend may be busy :)

A fun question is whether a functional program could declaratively handle the above. For example, it could expand the for loop into a dependency graph and then use demand-driven evaluation. However, there are two problems. First, the interpretation of indices would have to change: my code correctly skewed the loop indices to make sure "a[i - 1]" and "b[i - 4]" are never negative. Second, the loop would be unsafe: in my approach, the synthesizer can statically check that the array is fully defined. Either way, traditional functional languages force programmers to explicitly handle these (arguably) low-level loop details. Go synthesis!