PapersWeLove
5 HN recommenders · recommended in 9 months, 2020–2026
59:04 · 27K views · Sep 19, 2019
Shriram Krishnamurthi's PWLConf 2019 talk on the formal notion of expressive power of programming languages, based on Felleisen's paper. It explains how to tell when a feature adds power by whether emulating it requires global rewriting.
Recommended as the approachable way into a precise definition of language expressiveness for language-design arguments.
9 comments from Hacker News
Certainly adding call/cc doesn't allow you to represent more computable functions by programs. But there are plenty of internal features of programs that we're interested in, that let us meaningfully distinguish amongst programs that otherwise have the exact same observable behavior. I like coroutines as an example here, because I have very direct experience writing programs with similar behavior in systems that either do or do not have coroutines. By far, I found the coroutine-based programs far easier to understand and extend. Mattias Felleisen wrote the seminal paper on comparing expressive power of Turing-complete languages. It's worth a read if it's not come across your radar before! [LINK] Although, Shriram Krishnamurthi's talk from two years ago on this paper might be more approachable. this video
In programming language design, we tend to distinguish between global and local analysis. While type checking and elaboration is an example of global analysis, desugaring is inherently local to some piece of code. Therefore, "power" or "expressiveness" usually mean that something cannot be syntactically "expanded"; e.g., while type classes elaborate into explicit dictionaries, they still require information from the type checker, and therefore considered a "real" feature of a programming language. On the other hand, nested pattern matching can be formulated as local syntax transformation, and therefore it doesn't bring anything fundamentally new to the type system or dynamic semantics. There's also a great talk on the matter [1], if somebody is interested in formalities. [1] this video
> If macros can implement arbitrary language features Not really your question--others have provided examples of type systems as macros--but they can't, they can only do local rewrites. You couldn't, for example, express mutation or non-local control flow if you didn't have them already; On the expressive power of programming languages [0] is rather theoretical but does set out the boundary of what macros can and can't do. That they're local means everyone has to buy into your type system if you want it to be a macro, though. [0] [LINK] though this video might be a useful walkthrough of the ideas being presented
Worth reading Felleisen’s paper “on the expressive power of programming languages” (or watch this talk this video ) which argues that if a language A has a feature that would require global refactoring to implement in language B, then A is more expressive than B.
On this notion, a very good talk "On the expressive power of programming languages"[1][2] which attempts to provide a formal basis for distinguishing between expressive power of turning complete languages. [1] this video [2] The paper it's based on [LINK]