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

What Hacker News said

Recommends opnitro · 2021-03 · on “Rust's type system is Turing-complete (2017)”

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]

Recommends Twisol · 2021-08 · on “All you need is call/cc (2013)”

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! [L

Recommends fanf2 · 2023-05 · on “Is Go an object-oriented programming language?”

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.

Recommends Hirrolot · 2024-05 · on “Algebraic Data Types for C99”

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

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

> 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

Cites pron · 2020-01 · on “C++20 Reference Card”

> 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 al

Cites Ygg2 · 2022-07 · on “How I went about learning Rust”

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.

Cites Ygg2 · 2024-06 · on “in Rust, methods should be object safe”

> 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]