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

What people said

hayley-patton · 2026-08 · Recommendation

> 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 [VIDEO] might be a useful walkthrough of the ideas being presented

Read the original HN comment ↗

Hirrolot · 2024-05 · Recommendation

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

Read the original HN comment ↗

fanf2 · 2023-05 · Recommendation

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.

Read the original HN comment ↗