digitalmars.D - [OT] On the Expressive Power of Programming Languages
- Paul Backus (11/11) Nov 14 2020 What do we mean when we say that one programming language is
- Dibyendu Majumdar (5/9) Nov 14 2020 I am not sure what is meant by expressiveness in general.
- Paul Backus (9/13) Nov 14 2020 Expressive compared to what? I think pretty much everyone would
- H. S. Teoh (25/28) Nov 14 2020 [...]
- Paul Backus (2/14) Nov 15 2020 Then you haven't watched the talk. :)
- Timon Gehr (7/9) Nov 14 2020 It only seems that way because it is the first and only one that was
- David Gileadi (2/15) Nov 14 2020 I quite enjoyed watching this, thank you.
- Russel Winder (14/18) Nov 15 2020 [=E2=80=A6]
- Dibyendu Majumdar (5/17) Nov 15 2020 I completely agree.
- Paul Backus (5/9) Nov 15 2020 What if I told you there's a way to mathematically formalize the
- Paolo Invernizzi (2/14) Nov 15 2020 Interesting talk, I've enjoyed it, thanks!
- Russel Winder (10/22) Nov 15 2020 Except that I see/hear no mathematical definition of the concept of
- Paul Backus (11/13) Nov 15 2020 The talk defines a relation, "more expressive than", between
- Steven Schveighoffer (11/24) Nov 16 2020 I enjoyed the talk and like the principles shown.
- Petar Kirov [ZombineDev] (7/20) Nov 16 2020 string mixins kind of ruined this distinction for us - even AST
- Petar Kirov [ZombineDev] (3/25) Nov 16 2020 s/expressed via/locally re-written (lowered to)/
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (10/14) Nov 16 2020 What are the principles?
- Steven Schveighoffer (11/25) Nov 16 2020 That you can measure expressiveness via checking if two expressions are
- Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= (16/20) Nov 16 2020 Yes, human factors and programming culture should not take a back
What do we mean when we say that one programming language is "more expressive" than another? Is it just a matter of opinion and personal taste, or is there some underlying objective truth? And is more expressiveness necessarily a good thing? Based on a 1991 paper by Matthias Felleisen, this presentation by Shriram Krishnamurthi is an accessible and easy-to-digest introduction to some of the programming-language theory that goes into answering the above questions. If you have even a passing interest in programming-language design, it's well worth your time to give this a watch. https://www.youtube.com/watch?v=43XaZEn2aLc
Nov 14 2020
On Sunday, 15 November 2020 at 01:01:09 UTC, Paul Backus wrote:What do we mean when we say that one programming language is "more expressive" than another? Is it just a matter of opinion and personal taste, or is there some underlying objective truth? And is more expressiveness necessarily a good thing?I am not sure what is meant by expressiveness in general. For instance, Rust seems to be the first and only language where the lifetime of objects in memory can be expressed at compile time. Is Rust expressive or not?
Nov 14 2020
On Sunday, 15 November 2020 at 01:40:08 UTC, Dibyendu Majumdar wrote:I am not sure what is meant by expressiveness in general. For instance, Rust seems to be the first and only language where the lifetime of objects in memory can be expressed at compile time. Is Rust expressive or not?Expressive compared to what? I think pretty much everyone would agree that Rust is more expressive than, say, Brainfuck, but some would probably argue that it is less expressive than Lisp. Of course, that's a rather hand-wavy explanation. If you want to understand how this kind of intuitive sense of relative expressiveness can be modeled mathematically, that's what the linked presentation is all about. :)
Nov 14 2020
On Sun, Nov 15, 2020 at 01:55:49AM +0000, Paul Backus via Digitalmars-d wrote: [...]Expressive compared to what? I think pretty much everyone would agree that Rust is more expressive than, say, Brainfuck, but some would probably argue that it is less expressive than Lisp.[...] By what are you measuring expressiveness here? Mathematically speaking, BF has the same expressiveness as Lisp, and Lisp has the same expressiveness as D: they are all Turing-complete. I have not seen a *mathematical* definition of expressiveness that would measure these languages differently. OTOH, if by expressiveness you mean conciseness of expressing common computations, then you can probably argue BF is the least expressive of them all, since you need to write a LOT of BF just to express what can probably be expressed in a few lines of D; and Lisp is probably somewhere up there above D. But that would require that you define what you mean by "common", and that's where you'll get into a tarpit because reasonable people will disagree on what exactly constitutes a "common computation". Also, trying to find the "most expressive" language in terms of conciseness is futile task, because that's equivalent to finding a language whose constructs let you express any computation in the shortest form possible, and this can be reduced to finding the optimal compression algorithm. But finding the optimal compression algorithm is equivalent to the halting problem, which is unsolvable. T -- It only takes one twig to burn down a forest.
Nov 14 2020
Paul Backus <snarwin gmail.com> On Sunday, 15 November 2020 at 06:36:16 UTC, H. S. Teoh wrote:On Sun, Nov 15, 2020 at 01:55:49AM +0000, Paul Backus via Digitalmars-d wrote: [...]Then you haven't watched the talk. :)Expressive compared to what? I think pretty much everyone would agree that Rust is more expressive than, say, Brainfuck, but some would probably argue that it is less expressive than Lisp.[...] By what are you measuring expressiveness here? Mathematically speaking, BF has the same expressiveness as Lisp, and Lisp has the same expressiveness as D: they are all Turing-complete. I have not seen a *mathematical* definition of expressiveness that would measure these languages differently.
Nov 15 2020
On 15.11.20 02:40, Dibyendu Majumdar wrote:Rust seems to be the first and only language where the lifetime of objects in memory can be expressed at compile time.It only seems that way because it is the first and only one that was marketed to you. http://web.cs.ucla.edu/~palsberg/tba/papers/tofte-talpin-iandc97.pdf In programming languages, theory is quite far ahead of and detached from practice. I would be surprised to find any type theory concept that is less than 20 years old in any popular language.
Nov 14 2020
On 11/14/20 6:01 PM, Paul Backus wrote:What do we mean when we say that one programming language is "more expressive" than another? Is it just a matter of opinion and personal taste, or is there some underlying objective truth? And is more expressiveness necessarily a good thing? Based on a 1991 paper by Matthias Felleisen, this presentation by Shriram Krishnamurthi is an accessible and easy-to-digest introduction to some of the programming-language theory that goes into answering the above questions. If you have even a passing interest in programming-language design, it's well worth your time to give this a watch. https://www.youtube.com/watch?v=43XaZEn2aLcI quite enjoyed watching this, thank you.
Nov 14 2020
Paul, On Sun, 2020-11-15 at 01:01 +0000, Paul Backus via Digitalmars-d wrote:What do we mean when we say that one programming language is=20 "more expressive" than another? Is it just a matter of opinion=20 and personal taste, or is there some underlying objective truth?=20 And is more expressiveness necessarily a good thing?[=E2=80=A6] I'd say it is a matter of personal prejudice, so most likely different for each individual.=20 Where two people agree on the "expressiveness" of different programming languages, you have the beginnings of a clique. --=20 Russel. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Dr Russel Winder t: +44 20 7585 2200 41 Buckmaster Road m: +44 7770 465 077 London SW11 1EN, UK w: www.russel.org.uk
Nov 15 2020
On Sunday, 15 November 2020 at 12:31:15 UTC, Russel Winder wrote:Paul, On Sun, 2020-11-15 at 01:01 +0000, Paul Backus via Digitalmars-d wrote:I completely agree. Also different languages express different things better - and that was my point about Rust being expressive in a particular scenario.What do we mean when we say that one programming language is "more expressive" than another? Is it just a matter of opinion and personal taste, or is there some underlying objective truth? And is more expressiveness necessarily a good thing?[…] I'd say it is a matter of personal prejudice, so most likely different for each individual. Where two people agree on the "expressiveness" of different programming languages, you have the beginnings of a clique.
Nov 15 2020
On Sunday, 15 November 2020 at 12:31:15 UTC, Russel Winder wrote:I'd say it is a matter of personal prejudice, so most likely different for each individual. Where two people agree on the "expressiveness" of different programming languages, you have the beginnings of a clique.What if I told you there's a way to mathematically formalize the idea of "expressiveness" while preserving many of our intuitions about which programming languages are more expressive than others? Are you curious? If so, watch the talk--it's all in there. :)
Nov 15 2020
On Sunday, 15 November 2020 at 13:08:58 UTC, Paul Backus wrote:On Sunday, 15 November 2020 at 12:31:15 UTC, Russel Winder wrote:Interesting talk, I've enjoyed it, thanks!I'd say it is a matter of personal prejudice, so most likely different for each individual. Where two people agree on the "expressiveness" of different programming languages, you have the beginnings of a clique.What if I told you there's a way to mathematically formalize the idea of "expressiveness" while preserving many of our intuitions about which programming languages are more expressive than others? Are you curious? If so, watch the talk--it's all in there. :)
Nov 15 2020
On Sun, 2020-11-15 at 13:08 +0000, Paul Backus via Digitalmars-d wrote:On Sunday, 15 November 2020 at 12:31:15 UTC, Russel Winder wrote:Except that I see/hear no mathematical definition of the concept of "expresiveness". --=20 Russel. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D Dr Russel Winder t: +44 20 7585 2200 41 Buckmaster Road m: +44 7770 465 077 London SW11 1EN, UK w: www.russel.org.ukI'd say it is a matter of personal prejudice, so most likely=20 different for each individual. =20 Where two people agree on the "expressiveness" of different=20 programming languages, you have the beginnings of a clique.=20 What if I told you there's a way to mathematically formalize the=20 idea of "expressiveness" while preserving many of our intuitions=20 about which programming languages are more expressive than others? =20 Are you curious? If so, watch the talk--it's all in there. :)
Nov 15 2020
On Sunday, 15 November 2020 at 14:53:04 UTC, Russel Winder wrote:Except that I see/hear no mathematical definition of the concept of "expresiveness".The talk defines a relation, "more expressive than", between languages. As I'm sure you're aware, a relation between pairs of elements of a set is sufficient to define an ordering of that set. In this case, I believe it is entirely reasonable to refer to the ordering so defined as "expressiveness", even if it is not explicitly referred to by that name in the talk itself. Also, I remind you that you are the one that brought the word "expressiveness" into this discussion in the first place. In my original post, you will note that I took care to use the term "more expressive" to refer to the aforementioned relation.
Nov 15 2020
On 11/14/20 8:01 PM, Paul Backus wrote:What do we mean when we say that one programming language is "more expressive" than another? Is it just a matter of opinion and personal taste, or is there some underlying objective truth? And is more expressiveness necessarily a good thing? Based on a 1991 paper by Matthias Felleisen, this presentation by Shriram Krishnamurthi is an accessible and easy-to-digest introduction to some of the programming-language theory that goes into answering the above questions. If you have even a passing interest in programming-language design, it's well worth your time to give this a watch. https://www.youtube.com/watch?v=43XaZEn2aLcI enjoyed the talk and like the principles shown. But I think this doesn't really answer the question of which language is more expressive than another, because they are completely separate languages. It's more of a test as to whether a language feature adds expressiveness to an existing language (that is, when language A is equivalent to language B + feature F). And the bar is pretty high. I don't know if there are many "expressive" features left to add to D if we go by this definition unless we go AST-macros. -Steve
Nov 16 2020
On Monday, 16 November 2020 at 16:37:07 UTC, Steven Schveighoffer wrote:On 11/14/20 8:01 PM, Paul Backus wrote:string mixins kind of ruined this distinction for us - even AST macros would have a hard time proving that they can't be expressed via (mixin(genCode(params))) :D Anyways, Paul, thanks for sharing the talk, I also enjoyed watching it![...]I enjoyed the talk and like the principles shown. But I think this doesn't really answer the question of which language is more expressive than another, because they are completely separate languages. It's more of a test as to whether a language feature adds expressiveness to an existing language (that is, when language A is equivalent to language B + feature F). And the bar is pretty high. I don't know if there are many "expressive" features left to add to D if we go by this definition unless we go AST-macros. -Steve
Nov 16 2020
On Monday, 16 November 2020 at 16:40:56 UTC, Petar Kirov [ZombineDev] wrote:On Monday, 16 November 2020 at 16:37:07 UTC, Steven Schveighoffer wrote:s/expressed via/locally re-written (lowered to)/On 11/14/20 8:01 PM, Paul Backus wrote:string mixins kind of ruined this distinction for us - even AST macros would have a hard time proving that they can't be expressed via (mixin(genCode(params))) :D[...]I enjoyed the talk and like the principles shown. But I think this doesn't really answer the question of which language is more expressive than another, because they are completely separate languages. It's more of a test as to whether a language feature adds expressiveness to an existing language (that is, when language A is equivalent to language B + feature F). And the bar is pretty high. I don't know if there are many "expressive" features left to add to D if we go by this definition unless we go AST-macros. -Steve
Nov 16 2020
On Monday, 16 November 2020 at 16:37:07 UTC, Steven Schveighoffer wrote:I enjoyed the talk and like the principles shown.What are the principles?And the bar is pretty high. I don't know if there are many "expressive" features left to add to D if we go by this definition unless we go AST-macros.Oh, there is a ton of stuff to add. Logic programming, idris/agda like type system, an smt engine, verified concurrent actor concepts etc... In reality, expressiveness is not the challenge, but bridging the gap between modelling and implementation while ensuring correctness and maintainability with little performance loss and low labour costs...
Nov 16 2020
On 11/16/20 11:54 AM, Ola Fosheim Grøstad wrote:On Monday, 16 November 2020 at 16:37:07 UTC, Steven Schveighoffer wrote:That you can measure expressiveness via checking if two expressions are equivalent before and after the feature is added. It gives a nice measurable distinction for features that might be considered "primitives" for what a language can express.I enjoyed the talk and like the principles shown.What are the principles?I agree that I don't measure expressiveness in the same way. For example, they removed traditional for-loops from Swift because they can be expressed via while loops or foreach loops. But that doesn't help when what I need is a for loop. Syntax sugar has tangible benefit that shouldn't be dismissed. -SteveAnd the bar is pretty high. I don't know if there are many "expressive" features left to add to D if we go by this definition unless we go AST-macros.Oh, there is a ton of stuff to add. Logic programming, idris/agda like type system, an smt engine, verified concurrent actor concepts etc... In reality, expressiveness is not the challenge, but bridging the gap between modelling and implementation while ensuring correctness and maintainability with little performance loss and low labour costs...
Nov 16 2020
On Monday, 16 November 2020 at 17:09:16 UTC, Steven Schveighoffer wrote:For example, they removed traditional for-loops from Swift because they can be expressed via while loops or foreach loops. But that doesn't help when what I need is a for loop. Syntax sugar has tangible benefit that shouldn't be dismissed.Yes, human factors and programming culture should not take a back seat to the math perspective when designing a language. In some sense it is good that many programmers now get trained on Python, so that we have shared frame of references and conceptualizations. We can create minimalistic expressive languages, but the resulting code is hard to read for most humans, in some sense the programming language should allow us to express algorithms in terms of our physical experience which we often use to understand complicated systems: objects, actions, roles, stereotypes/concepts/interfaces/subclasses, actors... Anyway, there is a cross cutting field in CS that try to abstract the semantics of various programminglanguages to find the essence of programming language design, I guess it is comparable to how category theory tries to describe key patterns i math.
Nov 16 2020