On the Expressive Power of Programming Languages by Shriram Krishnamurthi [PWLConf 2019]

Channel:PapersWeLove · Length:59:03 · Published:2019-09-19 · Views:27256

Watch on YouTube

Summary

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.

Why HN recommends it

Recommended as the approachable way into a precise definition of language expressiveness for language-design arguments.

Shriram Krishnamurthi's talk from two years ago on this paper might be more approachable. — HN, 2021

Programming language design · Functional programming

Subtitles (excerpt)

[Music] hello I am Shriram this work that I'm presenting is most assuredly not mine I will do my best to not lapse and talk as if it's mine and if I do it is not mine I'm not wearing a lanyard because apparently it's interfering with the audio and that's more important I am a green lanyard in case that matters to anyone and so what is this paper about it's got this slightly obscure looking title it says what is you know it's on the expressive power of programming languages the actual author's photograph is up there that's Matias for licence so in spirit he's hovering over us right now so what is this paper about well you know there's a lot of things that we know about what can and can't be done in different computational models right so we have very sharp mathematical distinctions if you've ever had the fortune or misfortune depending on who taught it a course on theory of computation or you've cracked open a book on the topic you know that there's these very fine-grained distinctions we know how to draw and yet somehow and so these are actually useful to us as a language designer this is invaluable to me when I design languages I think if I add this what does my theory textbook tell me might happen is that a consequence I'm ok with when I build

On Hacker News

> 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 wh… — hayley-patton, 2026-08
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 … — Hirrolot, 2024-05
Worth reading Felleisen’s paper “on the expressive power of programming languages” (or watch this talk [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. — fanf2, 2023-05
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… — Twisol, 2021-08
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] [VIDEO] [2] The paper it's based on [LINK] — opnitro, 2021-03

Related videos