hackertube.io

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

PapersWeLove · talk · Watch on YouTube

Programming language designFunctional programming

What it is

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 Hacker News recommends it

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

  • 5 people recommended it
  • 5 different months
  • 0 strong recommendations
  • first 2020, last 2026

What HN commenters said

  1. “a very good talk "On the expressive power of programming languages"[1][2]”

    Formal basis for comparing expressive power of Turing-complete languages

    opnitro, 2021-03 · Recommendation · in “Rust's type system is Turing-complete (2017)”

  2. “Shriram Krishnamurthi's talk from two years ago on this paper might be more approachable.”

    More approachable talk version of Felleisen's expressive power paper

    Twisol, 2021-08 · Recommendation · in “All you need is call/cc (2013)”

  3. “Worth reading Felleisen”

    Explains expressiveness as needing global refactoring to emulate a feature

    fanf2, 2023-05 · Recommendation · in “Is Go an object-oriented programming language?”

  4. “There's also a great talk on the matter [1], if somebody is interested in formalities.”

    Formal treatment of language power and local vs global transformation

    Hirrolot, 2024-05 · Recommendation · in “Algebraic Data Types for C99”

  5. “might be a useful walkthrough of the ideas being presented”

    Useful walkthrough of what macros can and cannot express

    hayley-patton, 2026-08 · Recommendation · in “Gödel, Escher, Elisp: The Beauty of Macros”

Excerpts from Hacker News comments, linked to the originals. Summaries and labels were written by a language model from those comments.

Topics: expressive power, felleisen, language design, macros, type systems

Also recommended by the same people