On the Expressive Power of Programming Languages by Shriram Krishnamurthi [PWLConf 2019]
Channel:PapersWeLove · Length:59:03 · Published:2019-09-19 · Views:27256
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
- Saving Voyager 1! - Bruce Waggoner at !!Con 2024 · !!Con · 35:25
- Visualizing the 4d numbers Quaternions · 3Blue1Brown · 31:50
- How to Detect Extra Dimensions · PBS Space Time · 15:48
- Java on a 1000 Cores - Tales of Hardware / Software CoDesign · Google TechTalks · 1:12:01
- Ruby Conf 12 - Y Not- Adventures in Functional Programming by Jim Weirich · Confreaks · 53:21
- How Python was Shaped by leaky Internals, Armin Ronacher, Flask framework · Видео с мероприятий {speach! · 49:55
- The Soul of Erlang and Elixir • Sasa Juric • GOTO 2019 · GOTO Conferences · 42:02
- "Simple Made Easy" - Rich Hickey (2011) · Strange Loop Conference · 1:01:38
- "Making Impossible States Impossible" by Richard Feldman · elm-conf · 25:06
- William Byrd on "The Most Beautiful Program Ever Written" [PWL NYC] · PapersWeLove · 1:31:05
- The Value of Values with Rich Hickey · InfoQ · 31:43
- Why Isn't Functional Programming the Norm? – Richard Feldman · Metosin · 46:09
- Maybe Not - Rich Hickey · ClojureTV · 1:03:28
- Solving Problems the Clojure Way - Rafal Dittwald · Clojure/north · 1:02:26
- Lecture 1A: Overview and Introduction to Lisp · MIT OpenCourseWare · 1:12:55
- Conway's Game Of Life in APL · Dyalog · 7:47