Lambda the Ultimate

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?

The latest video in Dyalog's library - Depth-First Tree-Search in APL - is now available (https://www.youtube.com/watch?v=DsZdfnlh_d0)

The classic depth-first search algorithm is explored using APL, a simple and concise array notation with high-order functions. The presentation highlights APL's incremental development style, using simple steps and culminating in a purely functional solution for the N-Queens problem. The informative style of this presentation brings clarity to this advanced topic, making it accessible even to those who are still near the start of their APL journey.

Once you've seen the video, why not examine the code used in greater detail and try the expressions for yourself in the online tutorial at http://tryapl.org/ (Learn tab > Depth-first search)

By the way, no this is not a "homework question". Yes, I did research it. I think some people on here can probably point me to some interesting links that weren't obvious on Google.

Has anyone used Datalog or RDF as a basis for something beyond basic model-driven development, like projectional editing or unikernel generation?

Seems like Google is hitting on some model-driven development stuff that uses RDF, but what I really am interested in is generating the whole program or even system entirely based on some kind of semantic model, not just representing some domain model with it.

Unikernels: Rise of the Virtual Library Operating System -- this is what is making me wonder about this type of thing again. I think having a high-level description of all layers of the whole system makes sense, but not everyone is going to want to use OCaml, and practically speaking you will probably want to be able to generate program code or at least configuration files for specific languages or existing machines/VMs or interpreters.

The idea is to have kind of RDF schema or semantic model or common datalog database of facts and rules and then use that as a basis for modeling a program or entire system and then generating the program code from that.

Or better have different programming languages defined using this common set of rules and facts, so the programming language code can be automatically translated back into the common representation and then processed using another tool or edited using a particular interactive projection.

The basic idea is that assuming the whole system is open source, all of the different programming languages or database formats or programs or data representations are defined based on some common semantics in a logic format like datalog. This should make it much easier for different systems (like programming languages or databases or applications) to work together.

I am wondering especially if someone has applied an approach like that to projectional editing or unikernel generation or maybe both together.

Thanks.

In brief
------

I'm porting an existing compiler/interpreter framework to Swift, from a more imperative code base. It currently exists in JavaScript (feh), Dart, and Objective-C. It has more-or-less the same (recursive descent) structure in all three languages; in particular, I use exceptions to immediately bail when I encounter a syntax error.

My proximal question is: how can I structure an exception-free parser to conveniently handle syntax errors? My more global question is: how do people do that in an idiomatically functional way?

Remarks
-------

Just about every line of parser code can (transitively) result in a syntax error. For example, to parse the language construct "split x into y" I write (roughly):

acceptToken(split)      // Could fail if split is misspelled
source = expression()   // Could fail if expression is faulty or missing
acceptToken(into)       // Could fail
dest = expression()     // Could fail
acceptToken(newline)    // Could fail
return new JoinNode(source, dest)

It is convenient to expect that any of these calls will throw an exception, in particular that lines subsequent to the failure will not execute. Repeated wrapping and testing each line is just the sort of thing exceptions are supposed to save us from. (Although I agree the details of handling exceptions — rolling back the program state — are almost impossible to get right.)

What I am looking for is a design architecture that will let me continue exploit the isomorphism between the grammar and the code structure: one term in the grammar maps to one line of parser code. Not one line of parser code, wrapped in conditional tests, with each line testing the success/failure of its predecessor.

There have been some suggestions in this thread:

https://devforums.apple.com/thread/227375?start=0&tstart=0

that involve optional types and comparisons to languages like Rust and Scala, but I did not see usable ideas from actual compiler writers. Suggestions or pointers/references welcome.

I've sketched some ideas about slot-based interfaces as a way to turn method names into first-class citizens of the language, with an example of the resulting framework as applied to C++:

"Objects, slots, functors, duality "

The key idea is to treat objects as polymorphic functors and regard a method call like

x.foo(arg1,...,argn)

as an invocation of x where the first parameter (the slot) is an entity indicating the particular method called upon:

x(foo,arg1,...,argn)

If we now define a slot as a generalized functor accepting objects as their first parameter and with the following semantics:

foo(x,arg1,...,argn) --> x(foo,arg1,...,argn)

then objects and slots become dual notions, and many interesting patterns arise around method decoration, smart references, etc.

I wonder if these ideas have been already explored in a more general setting than the toy framework described here.

Blog post by Olin Shivers.

Excerpts with my editorial:

Newell and Simon's Turing award cited them for their work on “symbol systems.” Newell once told me that this was just names, and then he explained his understanding of names: “They provide distal access.” That is, a name is a local piece of data that stands for some other piece of data, which is presumably large and remote. You can now use that small, convenient, local datum instead of the large, remote thing for which it stands.

The treatment bothers me, because it doesn't distinguish very well between names for computers and names for people, which contrasts in the idealism I picked up from Edwards ("names are too valuable to be wasted on compilers"):

As far as Newell was concerned, this is the purpose served by names, or symbols, in all computational systems. Including the one in your head.

And afterwards, dives into the computational:

The BitTorrent example above is particularly interesting, since it comes with an unusual, distributed dereferencing mechanism. A BitTorrent name also has the additional exotic property of being a “true name,” in that it names one and only one piece of data.

He then visits the humanistic viewpoint:

Good name choices make it easy and natural to do the right thing—like expressive, well-chosen types, they lead you effortlessly to the terms you wanted to write. This is because names used by humans come with baggage. They fit into a larger framework. When you can get that framework right, and stick to it, then the names come easy—not just when they are minted, but when someone is trying to recall the name for some existing thing.

Queue a bunch of suspiciously OO names that take the form verb-noun or noun-verb. And then finally back to the computational viewpoint, where FP reigns supreme:

One final remark about names. We use names all our lives, every day, all day. So they seem obvious and not so mysterious. But names are subtle. There is a sense in which the λ calculus is nothing more, really, than a theory of: names. Go look at the fundamental, definitional rules of the λ calculus.

I'm of the opinion that the humanistic and computational nature of names are completely different, and find it weird that they are presented in such close quarters as to imply a strong connection between them.

Also, the way FP and OOP deal with names illuminates a lot about the paradigms. In OOP, objects have identities (intrinsic globally unique names that allow for easy aliasing) with interfaces that are named according to natural metaphors; FP is rather more oriented to symbolic reasoning where values (in pure FP at least) are anonymous and defined strictly by their structure, functions are named according to transformations on this data (map, reduce, select, etc...).