u/mttdin r/ProgrammingLanguages • Recommends
On the Expressive Power of Programming Languages by Shriram Krishnamurthi PWLConf 2019
0:00 / 0:00
#expressive-power#matthias-felleisen#lambda-calculus
On the Expressive Power of Programming Languages by Shriram Krishnamurthi [PWLConf 2019]
PapersWeLove
23K subscribers • 33 videos on Hallway • Community channel
- Recommended by 8 people: 5 on Hacker News, 1 on Lobsters, 1 in engineering communities and 1 curated list.
- A classic. People kept recommending it from 2019 to 2026.
- Presented by Shriram Krishnamurthi, Prof. of Computer Science, Brown University
- Linked in the descriptionpapers-we-love/pwlconf-info
Intermediate. Assumes working knowledge.
27K views7 years ago8 recommendations
Programming languagesComputer scienceLanguage design and type systemsComputation and complexity
Shriram Krishnamurthi explains Matthias Felleisen's formal definition of programming language expressiveness and how to determine if a feature adds power.
PWLConf 2019 Link: pwlconf.org/2019/shriram-krishnamurthi/ Slides / Captions: github.com/papers-we-love/pwlconf-info/tree/master/2019/shri… On the Expressive Power of Programming Languages Shriram Krishnamurthi, Prof. of Computer Science, Brown University Papers are like poems. Some are dazzling, some are pedestrian, some are insightful, and some reward long periods of quiet contemplation. They stir up an emotional reaction that goes beyond the strictly rational, and can often be deeply personal. In graduate school, during a period of identity crisis, I came across Matthias Felleisen's “On the Expressive Power of Programming Languages”. At a time when the world was ruled by C++, I had immersed myself in Scheme, so I always looked skeptically at mainstream linguistic claims. However, the language wars seemed beyond rational discourse. So the idea that someone could take a concept as nebulous as “expressiveness&rdquo and formalize it was already a revelation. But the beauty of this paper goes well beyond that: it also lies in the cleanliness of the approach, the correspondence of the formalism to intuition, and the tautness of its execution. It was the most stunning paper I had ever read, and remains so. It's like the poem that never leaves your soul. Unfortunately, this paper may not be easy to read for the uninitiated: it depends on a certain amount of “cultural knowledge” of programming language theory. I hope to peel off some of those layers and help you, too, understand the paper — hopefully while preserving the joy and beauty I experienced. References ------------------ On the expressive power of programming languages Felleisen M. (1991) Science of Computer Programming, 17 (1-3) , pp. 35-75. sciencedirect.com/science/article/pii/016764239190036W Biography ---------------- Shriram is the Vice President for Programming Languages at Brown University in Providence, RI, USA. He’s not, really, but that’s what it says on his business card. At heart, he's a person of ill-repute: a Schemer, Racketeer, and Pyreteer. He believes tropical fruit are superior to all other kinds. He is terrified of success, because he may be forced to buy a suit. He is known to interrogate his audiences to ensure they’re paying attention. So, be alert. You can read email later. Twitter: twitter.com/ShriramKMurthi Site: cs.brown.edu/~sk/ DBLP: dblp.uni-trier.de/pers/hd/k/Krishnamurthi:Shriram ----------------------------------------------------------------------------------------------------------- Video Sponsor: Comcast (jobs.comcast.com/) Captioning Sponsor: Two Sigma (twosigma.com/careers/) -----------------------------------------------------------------------------------------------------------Why it's here
8 people recommend thisWhat people say. Recommended as an approachable explanation of Matthias Felleisen's paper on comparing the expressive power of Turing-complete languages.
Moments people linked to
wrylon Lobsters • Recommends
On the Expressive Power of Programming Languages PWLConf 2019
programming-talkscurated list on GitHubRecommends
Under “Programming Language Design”
On the Expressive Power of Programming Languages 00:59:03 by **Shriram Krishnamurthi** (2019)
opnitroon Hacker News • Recommends
On “Rust's type system is Turing-complete (2017)”
On this notion, a very good talk "On the expressive power of programming languages"12 which attempts to provide a formal basis for distinguishing between expressive power of turning complete languages. 1 link to this video 2 The paper it's based on link
Twisolon Hacker News • Recommends
On “All you need is call/cc (2013)”
…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. link to this video…
fanf2on Hacker News • Recommends
On “Is Go an object-oriented programming language?”
Worth reading Felleisen’s paper “on the expressive power of programming languages” (or watch this talk link to 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.
Hirroloton Hacker News • Recommends
On “Algebraic Data Types for C99”
…d 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 link to this video…
hayley-pattonon Hacker News • Recommends
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 link to this video might be a useful walkthrough of the ideas being presented
u/raiphin r/ProgrammingLanguages • Mentions
On “On the Expressive Power of Programming Languages by Shriram Krishnamurthi [PWLConf 2019]”
**Update:** Would downvoters please explain what's wrong with my comment?
Here's an excerpt of Shriram's wrap up towards the end of their talk:
>So let me wrap up now first what have we learned:
>
>\* definition of equality ... it's used all over the literature ...
>
>\* definition of expressiveness ... we can now make distinctions between language features inside the space of turing completeness with mathematical truth not just a matter of opinion ...
>
>\* expressiveness \vs\ local expressiveness
>
>\* expressive features \are\ a little bad ... because they break existing equivalences and that's something you should do *very* cautiously ... they also have benefits…
u/rain5in r/ProgrammingLanguages • Mentions
PL Reading Group: Week 13 - Bohms Theorem
Hello! Welcome back to the PL reading group. This time we are reading a secondary paper (this was not the original paper that first proved the result) covering a very important fundamental theorem about lambda calculus.
* https://fermatslibrary.com/p/fd35470f
* Related watching: link to this video
Previous week
u/ecksxdieghin r/ProgrammingLanguages • Mentions
On “On the Expressive Power of Programming Languages (1990)”
This is a great paper. It’s nifty to think that there’s a good way to formally reason about and differentiate between Turing-complete languages.
Also worthwhile is Shriram Krishnamurthi’s talk about this paper, if you’re looking for a good one-hour-ish overview.
u/moon-chilledbonsai (apl+macros+types)in r/ProgrammingLanguages • Mentions
On “Do you know any interesting talks about PL design/compilers/interpreters?”
On the Expressive Power of Programming Language--bit more theoretical, but still fascinating, and very good presentation.
u/ElronndBonitoin r/ProgrammingLanguages • Mentions
On “Which programming languages empower us in general to make the most complicated abstractions?”
Turing equivalence doesn't mean that all programming languages are isomorphic, except in the very strictest sense. For instance, there is no concept of a pointer or a type in shell, and you can't make either no matter how hard you try. You can implement another language *in* shell which has those concepts, but that doesn't mean they're present in shell; therefor, if you compare shell to another language which is identical except that it has types (and whatever other affordances are required to facilitate that), it seems sensible to say that the latter empowers more complicated abstractions.
Also check out on the expressive power of programming languages for a formal definition of expres…
u/jasonchen66in r/ProgrammingLanguages • Mentions
On “Can anyone recommend a book to understand what are the fundamental differences between all programming languuages?”
Matthias Felleisen has a paper called “On the Expressive Power of Programming Languages” which tries to capture the notion of language feature “expressiveness” with some theory. It’s really cool. This talk explains it well
u/raiphin r/ProgrammingLanguages • Mentions
On “On the Expressive Power of Programming Languages by Shriram Krishnamurthi [PWLConf 2019]”
> the summary made me want to sit down to watch the full talk properly more now
That was partly why I wrote it. Shriram discussed a *practical tension* that is *logically (mathematically) inescapable*. You've got to be able to compare expressions in a programming language (and in a compiler, especially for optimization) and comparisons in turn rely on assumptions about "equality", but you break these assumptions and thus comparisons if you add "non-local" expressivity to a programming language.
I felt this ground was centrally important to readers of this sub, and that he presented it wonderfully well if one paid enough attention. But there was clearly scope for thinking it was mere theo…
u/consytrin r/ProgrammingLanguages • Mentions
On “What 'features' can be replaced/made obsolete?”
There is a great talk by Shriram Krishnamurthi on a paper about the expressive power of programming languages. Could be interesting to you! it is on youtube