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

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]

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

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.

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]

> 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

> 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: [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.

Post Scriptum: one way to prove this is that we could use [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.

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