Lambda the Ultimate

LtU doesn't seem to have any mentions of this paper by Minamide from 1998.

Here's a simple problem that benefits from the ideas described in the paper. The usual way of writing functions like "map" or "append" in a strict language like ML involves building the result list in reverse and then reversing it, which uses 2x more memory than needed. Imperative languages like Java can do without intermediate lists, but at the cost of using mutation on the list nodes after allocating them. To get the best of both worlds, we can extend the idea of tail recursion to also allow "tail allocation" aka "destination passing style", which just means that a recursive call nested within a constructor call should be treated as tail-recursive, and compiled to code that uses mutation internally. That way, the naive implementations of functions like "map" and "append" become as efficient as imperative code, allocating only as much memory as needed for the final result.

Some folks on the OCaml mailing lists have pointed out that such an approach would break some assumptions of the garbage collector, namely that the old generation never points into the young generation. I don't know if that problem outweighs the potential benefits of the technique.

How might your language design change in light of this sort of vertical integration?

Abstract: General-purpose processors are often unable to exploit the parallelism inherent to the software code. This is why additional hardware accelerators are needed to enable meeting the performance goals. NISC (No-Instruction-Set Computer) is a new approach to hardware-software co-design based on automatic generation of special-purpose processors. It was designed to be self-sufficient and it eliminates the need for other processors in the system. This work describes a method for expanding the application domain of the NISC processor to general-purpose processor systems with large amounts of processor-specific legacy code. This coprocessor-based approach allows application acceleration by utilizing both instruction-level and task-level parallelism by migrating performance-critical parts of an application to hardware without the need for changing the rest of the program code. For demonstration of this concept, a NISC coprocessor WISHBONE interface was designed. It was implemented and tested in a WISHBONE system based on Altium’s TSK3000A general-purpose RISC soft processor and an analytical model was proposed to provide the means to evaluate its efficiency in arbitrary systems.

(this researcher seems to me (an ignorant neophyte admittedly), to have quite a bit of interesting work on GC, among other interesting things.)

Generational Real-Time Garbage Collection

Abstract. While real-time garbage collection is now available in pro- duction virtual machines, the lack of generational capability means ap- plications with high allocation rates are subject to reduced throughput and high space overheads.

Since frequent allocation is often correlated with a high-level, object- oriented style of programming, this can force builders of real-time sys- tems to compromise on software engineering.

We have developed a fully incremental, real-time generational col- lector based on a tri-partite nursery, which partitions the nursery into regions that are being allocated, collected, and promoted. Nursery col- lections are incremental, and can occur within any phase of a mature collection.

We present the design, mathematical model, and implementation of our collector in IBM’s production Real-time Java virtual machine, and show both analytically and experimentally that the collector achieves real-time bounds comparable to a non-generational Metronome-style col- lector, while cutting memory consumption and total execution times by as much as 44% and 24% respectively.

p.s. i'm less interested in supporting OO everywhere than i am in having kick-ass GCs, i assume that using something more FP with a GC like this would be never less performant anyway.

A real time collector for reconfigurable hardware seems kinda like a nice little 'hardware' implementation.

It is thus quite a tour de force that the authors of the following paper have built a provably correct real-time collec- tor for reconfigurable hardware (field programmable gate arrays). How can this be? It turns out the FPGA setting makes the problem simpler in some ways than is the case with software GC running on stock processors. They can reasonably impose simple uniformity on the memory and its layout; they can exploit single-clock read-modify-write steps; and perhaps most importantly they have, via dual ported memory, com- pletely concurrent memory access. This all leads to one of the cleanest and per- haps most understandable implemen- tations of a concurrent GC that has ever been presented. The other prerequisites for real-time collection also follow eas- ily. It is difficult to find the right word to express the feeling I get seeing such a so- phisticated algorithmic idea reduced to such a straightforward hardware imple- mentation—“Cool!” will have to suffice. (emphasis mine)

Here is the idea: Popular wisdom dictates that functional languages need garbage collection, but is it really true. For example C++ style move semantics seem to solve the problem of returning a closure from a function, you create an object to contain a copy of all the local variables and functions, and then swap the local copy of the handle with the calling functions allocation, so when the function returns it destroys the empty handle from the caller, leaving the caller with the handle to the closure.

On this basis any acyclic datatype can be stored in the heap, but its lifetime managed from the stack handle (this is what RAII is doing in C++ STL).

I guess this is a degenerate case of reference counting, where we limit references to two types, a unique 'owning' reference (lets call it a handle to disambiguate) , that when it goes out of scope releases the memory (its unique and un-copyable so no need to count references), and an 'ephemeral' reference (lets call it a pointer) that is restricted in that it cannot be 'leaked' to a scope more short lived than the scope in which the handle exists. This all sounds a lot like Ada access variables - but note the change from the scope in which the handle was created, to the any scope in which the handle exists, as returning handles by move semantics is possible. This allows a constructor to return a handle into a scope which is also allowed to hold pointers to the object.

It doesn't sound like it really needs anything new, just a combination of Ada's access variable, and the mechanism for converting closures into objects described above.

What potential problems might there be? Could this work, or is there some overlooked flaw?

GPUs as an Opportunity for Offloading Garbage Collection sounds kinda cool to me.

We investigate the challenges for offloading garbage collection to a GPU, by examining the performance trade-offs for the mark phase of a mark & sweep garbage collector. We present a theo- retical analysis and an algorithm that demonstrates the feasibility of this approach. We also discuss a number of algorithmic design trade-offs required to leverage the strengths and capabilities of the GPU hardware. Our algorithm has been integrated into the Jikes RVM and we present promising performance results.

Mainly I've been trying to learn from anybody who might know: can moving a GC (especially in things like Ocaml or whatever) off to another core have good results like making pauses less obvious in interactive apps?

BCS FACS - Annual Peter Landin Semantics Seminar 2014
On correspondences between programming languages and semantic notations

Date/Time: Monday 8 December 2014, 6.00pm - 8.30pm

Venue: BCS, First Floor, The Davidson Building, 5 Southampton Street, London, WC2E 7HA

Cost to attend: Free of charge, but, please book your place via the BCS online booking system.

Book Online: https://events.bcs.org/book/1170/

Speaker: Prof. Peter Mosses, Swansea University

Synopsis:

Peter Landin (1930 - 2009) was a pioneer whose ideas underpin modern computing. In the the 1950s and 1960s, Landin showed that programs could be defined in terms of mathematical functions, translated into functional expressions in the lambda calculus, and their meaning calculated with an abstract mathematical machine. Compiler writers and designers of modern-day programming languages alike owe much to Landin's pioneering work.

Each year, a leading figure in computer science will pay tribute to Landin's contribution to computing through a public seminar. This year's seminar is entitled "On correspondences between programming languages and semantic notations" and will be given by Prof. Peter Mosses (Swansea University).

Programme:

5.15pm Coffee
6.00pm Welcome & Introduction - Prof Tony Clark (Middlesex University)
6.05pm Peter Landin Semantics Seminar -
On correspondences between programming languages & semanic notations - Prof. Peter Mosses (Swansea University)
7.20pm Drinks Reception

Seminar details:

50 years ago, at the IFIP Working Conference on Formal Language Description Languages, Peter Landin presented a paper on “A formal description of ALGOL 60”. In it, he explained “a correspondence between certain features of current programming languages and a modified form of Church’s λ-notation”, and suggested using that as the basis for formal semantics. He regarded his formal description of ALGOL 60 as a “compiler” from ALGOL abstract syntax to λ-notation.

10 years later, denotational semantics was well established, and two denotational descriptions of ALGOL 60 had been produced as case studies: one in the VDM style developed at IBM-Vienna, the other in the continuations-based style adopted in Christopher Strachey’s Programming Research Group at Oxford.

After recalling Landin’s approach, I’ll illustrate how it differs from denotational semantics, based on the ALGOL 60 descriptions. I’ll also present a recently developed component-based semantics for ALGOL 60, involving its translation to an open-ended collection of so-called fundamental constructs. I’ll assume familiarity with the main concepts of denotational semantics.

Closing date for bookings is 8 December @ 5pm. No more bookings will be taken after this date.

Grammar of Graphics (Vega) for declarative static semantics + FRP (Flapjax) for declarative temporal!

We investigate the design of declarative, domain-specific languages for constructing interactive visualizations. By separating specification from execution, declarative languages can simplify development, enable unobtrusive optimization, and support retargeting across platforms. We describe the design of the Protovis specification language and its implementation within an object-oriented, statically-typed programming language (Java). We demonstrate how to support rich visualizations without requiring a toolkit-specific data model and extend Protovis to enable declarative specification of animated transitions. To support cross-platform deployment, we introduce rendering and event-handling infrastructures decoupled from the runtime platform, letting designers retarget visualization specifications (e.g., from desktop to mobile phone) with reduced effort. We also explore optimizations such as runtime compilation of visualization specifications, parallelized execution, and hardware-accelerated rendering. We present benchmark studies measuring the performance gains provided by these optimizations and compare performance to existing Java-based visualization tools, demonstrating scalability improvements exceeding an order of magnitude.

See video and UIST 2014 paper.

For our own production code, we've been combining RxJS ~E-FRP with D3 charts.

An interesting paper by Oney, Myers, and Brandt in this year's UIST. Abstract:

InterState is a new programming language and environment that addresses the challenges of writing and reusing user interface code. InterState represents interactive behaviors clearly and concisely using a combination of novel forms of state machines and constraints. It also introduces new language features that allow programmers to easily modularize and reuse behaviors. InterState uses a new visual notation that allows programmers to better understand and navigate their code. InterState also includes a live editor that immediately updates the running application in response to changes in the editor and vice versa to help programmers understand the state of their program. Finally, InterState can interface with code and widgets written in other languages, for example to create a user interface in InterState that communicates with a database. We evaluated the understandability of InterState’s programming primitives in a comparative laboratory study. We found that participants were twice as fast at understanding and modifying GUI components when they were implemented with InterState than when they were implemented in a conventional textual event-callback style. We evaluated InterState’s scalability with a series of benchmarks and example applications and found that it can scale to implement complex behaviors involving thousands of objects and constraints.

I sometimes get a bee in my bonnet to look for tools to do model driven design and the like. So, I found a list of verification and synthesis tools. The mind boggles. For little people such as myself, I wish there were a table somewhere that listed the range of features and then showed what each system did/not support. I want stuff that would help with application development: user interface and state machine (e.g. audio playback engine + ui controlling it) type modeling and code generation (and round tripping). Anybody know of such guidance for the laymen?