On the Expressive Power of Programming Languages by Shriram Krishnamurthi [PWLConf 2019]
On the Expressive Power of Programming Languages by Shriram Krishnamurthi [PWLConf 2019] on HackerTube: recommended by 5 Hacker News commenters across 5 separate months, 2020–2026.
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.
What HN commenters said
9 Hacker News comments link this video. Each one links back to its thread.
hayley-pattonAug 2026Recommends
> 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
in “Gödel, Escher, Elisp: The Beauty of Macros” · View on HN
HirrolotMay 2024Recommends
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
in “Algebraic Data Types for C99” · View on HN
fanf2May 2023Recommends
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.
in “Is Go an object-oriented programming language?” · View on HN
TwisolAug 2021Recommends
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 “All you need is call/cc (2013)” · View on HN
opnitroMar 2021Recommends
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]
in “Rust's type system is Turing-complete (2017)” · View on HN
Ygg2Mar 2026Cites it
> It is, for some definition of object-oriented. Sure, for some definition of red, green is red. E.g., colorblind people. I'm interested in more broadly accepted jargon. The problem is, Rust isn't really object-oriented either. I'm interested in a mostly consistent and hopefully majority definition. It's not message-passing sense (can't do cool fancy things* a la Ruby or Smalltalk); nor is it inheritance-based (can't do inheritance-based nor prototype-based OOP patterns). There is one more mathematical definition of whether two features are equal, but it involves languages, local macros, and Turing machines. See ▶ this video * There was some kind of message recorder and playback in Ruby/Smalltalk, that I can't find. Basically send methods to objects and record them, then playback them at later date. Will update if I find it.
in “Zig – Type Resolution Redesign and Language Changes” · View on HN
Show 3 more comments
Ygg2Jun 2024Cites it
> Python OOP != Rust OOP, but you naturally already knew that. No. Bold of you to assume that. I wasn't aware that one OOP isn't another OOP. I see, so OOP is a fuzzyish definition that you check more checkboxes to satisfy. If Rust is OOP, and Python is OOP and C is OOP, then the that circles back to my initial claims. A category that is so wide it's effectively useless. Compare this to sync and async. A precise definition, much greater informational content. You can prove something is pure or not[1]. Compare this to OOP, imprecise, less informational context, impossible to (dis)prove something is OOP or not. [1] ▶ this video
in “in Rust, methods should be object safe” · View on HN
Ygg2Jul 2022Cites it
Post Scriptum: one way to prove this is that we could use ▶ this video as a base. How to prove. Assume that we add struct inheritance to Rust (it looks similar to JS) - call it RustInh. Does adding inheritance to Rust increase expressive power? If yes, then right now Rust can't express OOP concept as inheritance. I.e. is there a C[RustInh] = C[Rust]. And way to prove it is to look at Deref anti-patterns [link] I'm still not sure that fully captures my intuition of easy to write.
in “How I went about learning Rust” · View on HN
pronJan 2020Cites it
> besides you don't want to go read the implementation of your functions every time do you ? IDEs show us only prototypes for a reason The IDE can be changed to show you assertions in addition to the signature, just as it also shows doc comments. That the signature is special isn't some law of nature, it's just habit (and users of untyped languages don't even have those). > How would you for instance specialize a generic function in Zig ? ... and properly dispatches between both ? No, you'd need a single definition with a comptime branch. > I'd be hard pressed to say that it is "as powerful" given what I'm seeing for now. What you're seeing is personal taste. In my taste, that Zig doesn't allow overloading and has clear dispatch is clearer is more preferable (in fact, it's touted as one of Zig's biggest strengths); in yours, it is less preferable. That's perfectly OK, but it's got nothing to do with expressive power (which has a pretty good and precise definition: ▶ this video ). There is a reason why some languages are more complicated while others are simple -- some people aesthetically prefer the more complex languages while others prefer simpler ones. What is impressive about Zig is that despite being simple, it's not giving up power, at least in those aspects I mentioned. C, another simple language, cannot do those things.
in “C++20 Reference Card” · View on HN