Subscribe: Lambda the Ultimate - Programming Languages Weblog
http://lambda-the-ultimate.org/rss.xml
Preview: Lambda the Ultimate - Programming Languages Weblog

Lambda the Ultimate - Programming Languages Weblog



Programming languages news, articles and discussion



 



How efficient is partial sharing?

Tue, 07 Nov 2017 16:39:42 +0000

Partial sharing graphs offer a reduction model for the lambda calculus that is optimal in a sense put forward by Jean Jacques Levy. This model has seen interest wax and wane: initially it was thought to offer the most efficient possible technology for implementing the lambda calculus, but then an important result showed that bookkeeping overheads of any such model could be very high (Asperti & Mairson 1998). This result had a chilling effect on the initial wave of excitement over the technology.

Now Stefano Guerrini, one of the early investigators of partial sharing graphs, has an article with Marco Solieri (Guerrini & Solieri 2017) arguing that the gains from optimality can be very high and that partial sharing graphs can be relatively close to the best possible efficiency, within a quadratic factor on a conservative analysis (this is relatively close in terms of elementary recursion). Will the argument and result lead to renewed interest in partial sharing graphs from implementors of functional programming? We'll see...

(Asperti & Mairson 1998) Parallel beta reduction is not elementary recursive.

(Guerrini & Solieri 2017) Is the Optimal Implementation inefficient? Elementarily not.




Is Haskell the right language for teaching functional programming principles?

Mon, 16 Oct 2017 19:18:08 +0000

No! (As Simon Thompson explains.)
You cannot not love the "exploration of the length function" at the bottom. Made me smile in the middle of running errands.




"8th" - a gentle introduction to a modern Forth

Mon, 02 Oct 2017 00:26:36 +0000

Found on the ARM community's embedded blog. It seems that Forth may be making a comeback.
"8th" - a gentle introduction to a modern Forth

8th is a secure, cross-platform programming language based on Forth which lets you concentrate on your application’s logic instead of worrying about differences between platforms. It lets you write your code once, and simultaneously produce applications running on multiple platforms. Its built-in encryption helps protect your application from hackers. Its interactive nature makes debugging and testing your code much easier.

As of this writing it supports 32-bit and 64-bit variants of:

  • Windows, macOS and Linux for desktop or server systems
  • Android (32-bit Arm only) and iOS for mobile systems
  • Raspberry Pi (Raspbian etc) for embedded Linux Arm-based systems.

...
8th differs from more traditional Forths in a number of ways. First of all, it is strongly typed and has a plethora of useful types (dynamic strings, arrays, maps, queues and more).

Other differences from traditional Forth appear to include automatic memory management and some kind of signed and encrypted application deployment.

[Edit: per gasche's comment, please note that 8th appears to be closed source. From their FAQ:

"Is 8th a GPL-Licensed product? No, it is a commercial product. None of the libraries it uses are under the GPL or LGPL. Due to the desire for security, 8th includes its required libraries in the binary, and the GPL family of licenses is therefore not appropriate."
Let the arguments about the effectiveness of security-by-obscurity begin. Source is apparently available if you buy an Enterprise license and sign an NDA.]




Project Loom: adding fibers and continuations to Java

Wed, 27 Sep 2017 01:52:24 +0000

Just saw this on Hacker News -- Project Loom: Fibers and Continuations for the Java Virtual Machine with the following overview:

Project Loom's mission is to make it easier to write, debug, profile and maintain concurrent applications meeting today's requirements. Threads, provided by Java from its first day, are a natural and convenient concurrency construct (putting aside the separate question of communication among threads) which is being supplanted by less convenient abstractions because their current implementation as OS kernel threads is insufficient for meeting modern demands, and wasteful in computing resources that are particularly valuable in the cloud. Project Loom will introduce fibers as lightweight, efficient threads managed by the Java Virtual Machine, that let developers use the same simple abstraction but with better performance and lower footprint. We want to make concurrency simple(r) again! A fiber is made of two components — a continuation and a scheduler. As Java already has an excellent scheduler in the form of ForkJoinPool, fibers will be implemented by adding continuations to the JVM.

I'm a fan of fibers, and this has quite a bit of interesting material in it for like-minded folks.




Copattern matching and first-class observations in OCaml, with a macro

Tue, 26 Sep 2017 15:13:32 +0000

Copattern matching and first-class observations in OCaml, with a macro, by Paul Laforgue and Yann Regis-Gianas:

Infinite data structures are elegantly defined by means of copattern matching, a dual construction to pattern matching that expresses the outcomes of the observations of an infinite structure. We extend the OCaml programming language with copatterns, exploiting the duality between pattern matching and copattern matching. Provided that a functional programming language has GADTs, every copattern matching can be transformed into a pattern matching via a purely local syntactic transformation, a macro. The development of this extension leads us to a generalization of previous calculus of copatterns: the introduction of first-class observation queries. We study this extension both from a formal and practical point of view.

Codata isn't well supported enough in languages IMO, and supporting it via a simple macro translation will hopefully make it easier to adopt, at least for any language with GADTs.




Non-determinism: a sublanguage rather than a monad

Wed, 20 Sep 2017 21:52:27 +0000

Non-determinism: a sublanguage rather than a monad

A puzzlingly named, exceedingly technical device introduced to structure the denotational semantics has by now achieved cult status. It has been married to effects -- more than once. It is compulsively looked for in all manner of things, including burritos. At least two ICFP papers brought it up without a rhyme or reason (or understanding), as the authors later admitted. I am talking about monads.

In truth, effects are not married to monads and approachable directly. The profound insight behind monads is the structuring, the separation of `pure' (context-independent) and effectful computations. The structuring can be done without explicating mathematical monads, and especially without resorting to vernacular monads such as State, etc. This article gives an example: a simple, effectful, domain-specific sublanguage embedded into an expressive `macro' metalanguage. Abstraction facilities of the metalanguage such higher-order functions and modules help keep the DSL to the bare minimum, often to the first order, easier to reason about and implement.

The key insight predates monads and goes all the way back to the origins of ML, as a scripting language for the Edinburgh LCF theorem prover. What has not been clear is how simple an effectful DSL may be while remaining useful. How convenient it is, especially compared to the monadic encodings. How viable it is to forsake the generality of first-class functions and monads and what benefits it may bring. We report on an experiment set out to explore these questions.

We pick a rather complex effect -- non-determinism -- and use it in OCaml, which at first blush seems unsuitable since it is call-by-value and has no monadic sugar. And yet, we can write non-deterministic programs just as naturally and elegantly as in Haskell or Curry.

The running tutorial example is computing all permutations of a given list of integers. The reader may want to try doing that in their favorite language or plain OCaml. Albeit a simple exercise, the code is often rather messy and not obviously correct. In the functional-logic language Curry, it is strikingly elegant: mere foldr insert []. It is the re-statement of the specification: a permutation is moving the elements of the source list one-by-one into some position in the initially empty list. The code immediately tells that the number of possible permutations of n elements is n!. From its very conception in the 1959 Rabin and Scott's paper, non-determinism was called for to write clear specifications -- and then to make them executable. That is what will shall do.




A unified approach to solving seven programming problems

Mon, 04 Sep 2017 18:44:29 +0000

A fun pearl by William E. Byrd, Michael Ballantyne, Gregory Rosenblatt, and Matthew Might from ICFP: seven programming challenges solved (easily!) using a relational interpreter. One challenge, for example, is to find quines. Another is to find programs that produce different results with lexical vs. dynamic scope.

The interpreter is implemented in miniKanren (of course), inside Racket (of course).




ICFP 2017 live streaming

Sun, 03 Sep 2017 18:35:27 +0000

If you are one of the few LtU-ers not presenting (just kidding...), you can get your functional programming fix by following the live stream from ICFP, starting tomorrow at 11:00 (UK). Want to know when to tune in? Check out the incredible program!




Proceedings of the ACM on Programming Languages

Wed, 30 Aug 2017 21:05:36 +0000

Proceedings of the ACM on Programming Languages (PACMPL) is a Gold Open Access journal publishing research on all aspects of programming languages, from design to implementation and from mathematical formalisms to empirical studies. Each issue of the journal is devoted to a particular subject area within programming languages and will be announced through publicized Calls for Papers.

See the ToC of the September 2017, ICFP issue, here. Some very cool stuff.

Congrats!




Graydon Hoare: What next for compiled languages?

Sun, 20 Aug 2017 03:52:33 +0000

Since everybody is talking about this post,we might as well.

Key topics discussed: modules(you know, real ones); errors ("there are serious abstraction leakages and design trade-offs in nearly every known approach"); Coroutines, async/await, "user-visible" asynchronicity; effect systems, more generally (you could see that coming, couldn't you?); Extended static checking (ESC), refinement types, general dependent-typed languages; and formalization ("we have to get to the point where we ship languages -- and implementations -- with strong, proven foundations").

He goes on to discuss a whole grab bag of "potential extras" for mainstream languages, including the all time favorite: units of measure.

Feel free to link to the relevant discussions from the LtU archive...




Review of Graham Hutton's Programming in Haskell, 2e

Thu, 17 Aug 2017 18:19:26 +0000

A concise review by Simon Thompson of the second edition of Graham Hutton's Programming in Haskell. The first edition was published in 2007, but chapters were written earlier, and the review focuses on how the language has changed since then, embracing the "categorical / algebraic approach more fully".




Happy Birthday, dear Lambda: 17 is good edition

Fri, 28 Jul 2017 05:48:39 +0000

Seventeen years ago to the day, LtU was born. I guess it's about time I stop opening these birthday messages by saying how remarkable this longevity is (this being the fate of Hollywood actresses over 25). Still, I cannot resist mentioning that 17 is "good" (טוב) in gematria, which after all is one of the oldest codes there are. It's is very cool that the last couple of weeks had a flurry of activity. This old site still got game. I will not try to summarize or pontificate. The community has grown too big and too unruly for that and I have been more an absent landlord recently than a true participant (transitioning from CS to being a professional philosopher of science and having kids took a bit more of my free time than I expected). One thing I always cherished about LtU was that we welcomed both professional, academic work, and everything and anything that was cool and fun in programming languages. It was never a theory only site. So here's a little birthday party game instead of a long summary. Which new (or old) languages inspire you to think that a good language can smoothly allow people to reach heretofore hard to reach semantic or abstraction levels? I mean things that affect how the little guy thinks, not formal semantics, category theory, or what have you. I'll start with two unconventional languages that I have had the pleasure (and exasperation) of using recently. Both are in some respects descendants of Logo, the language through which I was introduced to programming when I was a ten year old child in Brookline. They are NetLogo and ScratchJr. NetLogo is a language for building agent based models (here's a classic ABM for you to enjoy; if you install NetLogo there's an implementation in the model library). While some aspects of the language semantics (and syntax) are irritating, NetLogo is very good at what it does. I may say more in the comments, but the key is that a simulation consists of multiple agents, who can move and interact, and the language makes building such simulations straightforward. There is a central clock; you can address multiple agents using conditions ("ask guys with [color = red] [die]"); implicitly have code run by each agent etc. In fact, you hardly think about these issues. If you have no previous background in programming, it feels natural that keeping track of these and other details is not part of the task programming. ScratchJr is for young kids. It allows them to create little animated scenes, which may be responsive to touch and so on. You can record sounds and take pictures and use them as first class elements in your animations. But the nice thing for me was to notice how natural it is for kids to use the event-driven model (you can "write" several bits of code, and each will execute when the triggering event happens; no need to think about orchestrating this) as well as intuitively understand how this may involves things happening concurrently. These things just emerge from the way the animations are built, they are not concepts the programmer has to explicitly be aware of (which is a good thing, considering she is typically a five year old). When I see philosophy students writing netlogo and reasoning about the behavior of the agents and when I see kids playing with ScratchJr, I am reminded why I found this business of "engineering abstractions" so enticing when I first used structured programming to design vocabulary for the program I was writing and when I heard some language described as a language for stratified design. So which are your nominations for cool language based abstractions, for the little guy? Just to give us all some motivation and maybe get me worked up enough to finally delve into algebraic effects? Happy birthday, LtU-ers. Keep fighting the good figh[...]



Implementing Algebraic Effects in C

Thu, 27 Jul 2017 13:50:17 +0000

Implementing Algebraic Effects in C by Daan Leijen:

We describe a full implementation of algebraic effects and handlers as a library in standard and portable C99, where effect operations can be used just like regular C functions. We use a formal operational semantics to guide the C implementation at every step where an evaluation context corresponds directly to a particular C execution context. Finally we show a novel extension to the formal semantics to describe optimized tail resumptions and prove that the extension is sound. This gives two orders of magnitude improvement to the performance of tail resumptive operations (up to about 150 million operations per second on a Core i7@2.6GHz)

Another great paper by Daan Leijen, this time on a C library with immediate practical applications at Microsoft. The applicability is much wider though, since it's an ordinary C library for defining and using arbitrary algebraic effects. It looks pretty usable and is faster and more general than most of the C coroutine libraries that already exist.

It's a nice addition to your toolbox for creating language runtimes in C, particularly since it provides a unified, structured way of creating and handling a variety of sophisticated language behaviours, like async/await, in ordinary C with good performance. There has been considerable discussion here of C and low-level languages with green threads, coroutines and so on, so hopefully others will find this useful!




Project Snowflake: Non-blocking safe manual memory management in .NET

Thu, 27 Jul 2017 13:11:03 +0000

Project Snowflake: Non-blocking safe manual memory management in .NET by Matthew Parkinson, Kapil Vaswani, Manuel Costa, Pantazis Deligiannis, Aaron Blankstein, Dylan McDermott, Jonathan Balkind, Dimitrios Vytiniotis:

Garbage collection greatly improves programmer productivity and ensures memory safety. Manual memory management on the other hand often delivers better performance but is typically unsafe and can lead to system crashes or security vulnerabilities. We propose integrating safe manual memory management with garbage collection in the .NET runtime to get the best of both worlds. In our design, programmers can choose between allocating objects in the garbage collected heap or the manual heap. All existing applications run unmodified, and without any performance degradation, using the garbage collected heap. Our programming model for manual memory management is flexible: although objects in the manual heap can have a single owning pointer, we allow deallocation at any program point and concurrent sharing of these objects amongst all the threads in the program. Experimental results from our .NET CoreCLR implementation on real-world applications show substantial performance gains especially in multithreaded scenarios: up to 3x savings in peak working sets and 2x improvements in runtime.

Rather than trying to solve safe manual memory management using compile-time reasoning, you can move some of it into the runtime and raise dynamic failures on use-after-free and other hazards. With some judicious special types that track ownership and a type of borrowing, and some reasonable restrictions on how these types can be handled, you can achieve a nice framework for integrating manual and automatic memory management. The performance benefits for large heaps looks pretty clear.




The Syntax and Semantics of Quantitative Type Theory

Tue, 25 Jul 2017 17:28:17 +0000

The Syntax and Semantics of Quantitative Type Theory by Robert Atkey:

Type Theory offers a tantalising promise: that we can program and reason within a single unified system. However, this promise slips away when we try to produce efficient programs. Type Theory offers little control over the intensional aspect of programs: how are computational resources used, and when can they be reused. Tracking resource usage via types has a long history, starting with Girard's Linear Logic and culminating with recent work in contextual effects, coeffects, and quantitative type theories. However, there is conflict with full dependent Type Theory when accounting for the difference between usages in types and terms. Recently, McBride has proposed a system that resolves this conflict by treating usage in types as a zero usage, so that it doesn't affect the usage in terms. This leads to a simple expressive system, which we have named Quantitative Type Theory (QTT).

McBride presented a syntax and typing rules for the system, as well as an erasure property that exploits the difference between “not used” and “used”, but does not do anything with the finer usage information. In this paper, we present present a semantic interpretation of a variant of McBride's system, where we fully exploit the usage information. We interpret terms simultaneously as having extensional (compile-time) content and intensional (runtime) content. In our example models, extensional content is set-theoretic functions, representing the compile-time or type-level content of a type-theoretic construction. Intensional content is given by realisers for the extensional content. We use Abramsky et al.'s Linear Combinatory Algebras as realisers, yield a large range of potential models from Geometry of Interaction, graph models, and syntactic models. Read constructively, our models provide a resource sensitive compilation method for QTT.

To rigorously define the structure required for models of QTT, we introduce the concept of a Quantitative Category with Families, a generalisation of the standard Category with Families class of models of Type Theory, and show that this class of models soundly interprets Quantitative Type Theory.

Resource-aware programming is a hot topic these days, with Rust exploiting affine and ownership types to scope and track resource usage, and with Ethereum requiring programs to spend "gas" to execute. Combining linear and dependent types has proven difficult though, so making it easier to track and reason about resource usage in dependent type theories would then be a huge benefit to making verification more practical in domains where resources are limited.