How expressive should the language be?

[lassik]

Continued from #17

More expressiveness is always good

This is an excellent discussion. We fundamentally disagree on this point and it has far-reaching implications on many central design decisions.

Maybe you can explain this in detail in another issue. By your measures, Scheme would be an extremely bad language and C a very good one.

I don't mean that expressiveness is bad in itself, but it easily leads to complexity and many ways to solve the same problem. Empirically, both of these seems to be the case for languages like Haskell as well as Common Lisp. Not sure about dependent typed languages.

Scheme's expressiveness is strongly centered around closures and recursion which are simple things that can be applied to countless problems. So (as an unproven conjecture) it would seem that expressiveness is good so long as it pulls toward some center of gravity in the conceptual space. This also means that there isn't a need to add new concepts over time.

In something like CL and Haskell, the core is still lambdas, and in Haskell the core of the type system is something like HM, but I don't get the sense that there's an attempt to stick to this core; Haskell programmers push up the ceiling of the type system, CL programmers expand CLOS with a meta-object protocol. There's no end in sight. This suggests that they are not going toward any conceptual kernel, just building new stuff that would be fun to build.

[lassik]

Maybe what I'm looking for is minimum "cost per unit of expressiveness". Fewer concepts to achieve the same level of expressiveness is better. If there's a tradeoff, I'd usually pick having fewer concepts instead of having more expressiveness. Lisp is of course close to the theoretical minimum in "cost per unit of expressiveness" so there's not much argument there :)

[mnieper]

In something like CL and Haskell, the core is still lambdas, and in Haskell the core of the type system is something like HM, but I don't get the sense that there's an attempt to stick to this core; Haskell programmers push up the ceiling of the type system, CL programmers expand CLOS with a meta-object protocol. There's no end in sight. This suggests that they are not going toward any conceptual kernel, just building new stuff that would be fun to build.

In Haskell, the core of the type system is no longer HM, but it remains (almost?) compatible to it. In defence of Haskell, one should note that Haskell has been conceived as a language to do PL research so it is clear that we have been seeing lots of extensions. That the current core of Haskell may not be obvious is also partly due to history. GHC is a complex piece of software and rebasing it would need a lot of programming effort.

This is where Steme has an advantage. Steme starts over 20 years later than Haskell so we can incorporate from the beginning what the other functional languages had to learn the hard way. Today, Haskell wouldn't have started as an implementation of HM, I suppose.

As why the original Haskell, for example, is really not enough check multi-parameter type classes. You cannot model a lot of concepts with Haskell 98 type classes.

Said differently: The less expressive your type system or language is, the less exact or precise you can model your objects in the language.

[lassik]

In defence of Haskell, one should note that Haskell has been conceived as a language to do PL research

Indeed, a big part of the problem is that we conflate research and production languages. There's something psychologically irresistible about doing that: if a research language is promising, it's just too much fun to start writing production software in it. We all do it. And there's ultimately no clear line between research and production.

I strongly believe that genius is about making things simple. So I view a complex language like Haskell as a work in progress (i.e. research) that, if the research is successful, will later be reduced to something vastly simpler than it now is. Engineering is not like the natural sciences where nature gives us something complex and we are stuck with it. We are free to stick to a subset the possibility space, and indeed should always do so. If Haskell doesn't become simpler over time, they are going in an unfruitful research direction and should change course at some point.

Same thing with CLOS and the meta-object protocol: it's used as a production language, but is there any problem that requires that level of complexity? Understanding, implementing and optimizing these languages is extremely difficult.

The less expressive your type system or language is, the less exact or precise you can model your objects in the language.

This is actively desirable in my book. The more complex a model, the fewer people that can effectively work with it. When I was a teenage Lisp programmer, I built extremely complex abstractions for no reason because the tools were there. Those are research experiments, and what we should keep in mind that most experiments fail.

[lassik]

Put another way: Programs are models of the world. All models are lies. I prefer simple, regular lies to complex, idiosyncratic lies.

[lassik]

Put yet another way: Brilliant people can make a complex language, but only a genius can make a simple (expressive) one. So any research project that complexifies a language is waiting for a genius to come at some point in the future and sort it all out for them. The more that time goes by and complexity piles up, the harder it becomes to believe that this hypothetical genius is going to show up.

[mnieper]

I strongly believe that genius is about making things simple. So I view a complex language like Haskell as a work in progress (i.e. research) that, if the research is successful, will later be reduced to something vastly simpler than it now is. Engineering is not like the natural sciences where nature gives us something complex and we are stuck with it. We are free to stick to a subset the possibility space, and indeed should always do so. If Haskell doesn't become simpler over time, they are going in an unfruitful research direction and should change course at some point.

I cannot disagree more about the last sentence. Academic research is first and foremost not about applicability. Of course, applicability can and will guide research but that's not the reason why to do academic research in the first place. In research, it may even be interesting and possibly very fruitful to study a language that is more powerful than a Turing machine although this would mean that it couldn't be implemented on current hardware.

Same thing with CLOS and the meta-object protocol: it's used as a production language, but is there any problem that requires that level of complexity? Understanding, implementing and optimizing these languages is extremely difficult.

I cannot comment on CLOS because I am luckily not yet tainted by CL. 😁

The less expressive your type system or language is, the less exact or precise you can model your objects in the language.

This is actively desirable in my book. The more complex a model, the fewer people that can effectively work with it. When I was a teenage Lisp programmer, I built extremely complex abstractions for no reason because the tools were there. Those are research experiments, and what we should keep in mind that most experiments fail.

Abstractions for the sake of abstraction aren't helpful unless abstraction improves clarity (which is often does, by the way). But abstracted guided by the problem at hand is a very valuable tool.

For example, in physics, I can write 1 m + 3 inch. The more expressive a programming language is, the better I can translate it in a safe way (i.e. where the language's type system more or less guarantees me that the units are not messed up and where I cannot add temperature to distance, etc.).

[mnieper]

Put yet another way: Brilliant people can make a complex language, but only a genius can make a simple (expressive) one. So any research project that complexifies a language is waiting for a genius to come at some point in the future and sort it all out for them. The more that time goes by and complexity piles up, the harder it becomes to believe that this hypothetical genius is going to show up.

The subject of algebraic geometry in mathematics is originally about the study of solutions of polynomial equations in several variables using geometric reasoning. A huge (complex) body of results had been built up by the middle of the 20th century. A similar rich theory had been built up in number theory. It took a genius like Alexander Grothendieck to unify all this by introducing the concept of a scheme. A scheme is much more abstract than the solution set of a polynomial equation or the number of places of a function field but it was just due to the abstractness and generality of the term that it helped to not only simplify both subjects tremendously but also to unify both. The newly-won simplicity enabled all the progress algebraic geometry and number theory had made since then (culminating, for example, in the proof of Fermat's last theorem by the end of the century). This, however, didn't mean that the subject is now easier to understand for a newcomer. I would have a much easier time explaining the solution set of polynomial equations to you than to explain the definition of a scheme. The point is that restricting to the former concept doesn't help one in the long run because of the intrinsic complexity in the matter. This would be like trying to understand general relativity without using concepts from differential geometry.

[lassik]

Academic research is first and foremost not about applicability.

Over a long enough timeframe, it is. Haskell is 30 years old and it hasn't yet shown a single (externally observable) sign of ever reducing to a tool whose complexity is commensurate to the job at hand. People build successful software all the time in tools vastly simpler than Haskell. If the inner circle is on to something, they are not communicating it.

I cannot comment on CLOS because I am luckily not yet tainted by CL. 😁

CL is excellent in many ways, but they didn't know when to stop and say "this is enough" :)

This, however, didn't mean that the subject is now easier to understand for a newcomer.

That's the difference between theoretical and applied subjects. Theory tries to encircle everything; what can we include? An applied solution is the opposite: what can we exclude? The best applied solution excludes and simplifies as much as it can while still getting the job done. And the job is not to represent everything, but to solve problems effectively.

A trivial example of a successful applied invention is JSON: it has very few data types, but for that reason, it's easier to apply in more places and easier for the applications to communicate, making it much more useful in practice.

[lassik]

restricting to the former concept doesn't help one in the long run because of the intrinsic complexity in the matter

This may even be the fundamental problem posed by computer science: what is the intrinsic complexity of each problem? It's a hard question to answer. In essence, CL and Haskell are betting that the intrinsic complexity of writing production software is on a level that requires metaclasses and higher-kinded types. (Barring the later appearance of the PL equivalent of Grothendieck who can not only unify the concepts but simplify them as well :)

[lassik]

Scheme works well as both a research and production language because it was started from genius ideas (lambda calculus, GC, macros, lexical scoping) and hasn't grown much from there; things like vectors and record types are details. Basic ML is similar: started from genius ideas (HM, the merging of types and modules) and didn't venture that far. Same thing with Smalltalk, Prolog, APL, Forth.

Empirically it seems that if the constitutional ideas are genius, and the language sticks to them and doesn't constrain or expand them too much, then it'll be a good vehicle for both research and production for decades to come.

But if the founding ideas are not genius-level stuff, or if some brilliant-but-not-genius people later add or change them substantially, the language winds up with something that looks to outsiders like complexity for the sake of complexity. All the complex FP and OO languages end up like this in my book.

My prognosis for statically typed Scheme is that since we have brilliant people but no Turing award geniuses are in sight, we'll wind up creating the same thing that most PL researchers create: something intricate and somewhat self-consistent but ultimately hard for an external observer to distinguish from complexity for its own sake. Another cause for concern is that I can't think of one existing language that started out complex and was later simplified. It seems the fate of all languages is to grow in complexity until replaced by other languages (which usually takes decades during which people have to keep using the existing complex language).

[mnieper]

Academic research is first and foremost not about applicability.

Over a long enough timeframe, it is. Haskell is 30 years old and it hasn't yet shown a single (externally observable) sign of ever reducing to a tool whose complexity is commensurate to the job at hand. People build successful software all the time in tools vastly simpler than Haskell. If the inner circle is on to something, they are not communicating it.

People have been building successful software in C. And C is much simpler than Scheme when it comes to (efficiently) implement it. So I question your measures here.

Moreover, even if Haskell weren't or didn't become a tool for practical programming, it would have influenced so many tools used in practice so that there would be no question whether all the research that has gone into Haskell was well-invested.

The same situation is with Scheme, actually. Highly influential, but not the everyday tool (at least for the vast majority).

(This doesn't mean that one shouldn't aim for applicability, of course.)

This, however, didn't mean that the subject is now easier to understand for a newcomer.

That's the difference between theoretical and applied subjects. Theory tries to encircle everything; what can we include? An applied solution is the opposite: what can we exclude? The best applied solution excludes and simplifies as much as it can while still getting the job done. And the job is not to represent everything, but to solve problems effectively.

By this definition, it is the theory that moves us forward.

[lassik]

Definitely agreed that theory is what moves us forward in the long term - no question. The problem is that the theoretical advances that are practically useful, tend to be quantum leaps. Those are rare and quite unpredictable. The intermediate theory (incremental work on top the previous quantum leap) tends to be something quite complex and somewhat impractical.

Another problem is that the quantum leaps tend to come from left field. The incremental work may well inspire them, but it's not clear that the next quantum leap can be built on top of the last incremental work. It's also not clear that the inspiration comes from computers in general, let alone type systems or evaluation models specifically. For example, Smalltalk was inspired by biology. Software has an extremely substantial empirical/soft-science aspect in addition to the formal aspect, a fact which is overlooked in academia.

[lassik]

The thing is that Scheme is extremely well suited as an everyday tool because it's built directly on top of quantum leaps with not much incremental work on top. Same with ML, Prolog, etc. Building incremental research on top of Scheme is fine on its own terms, but the resulting language no longer has this character of Scheme. Common Lisp is like that. It's complex because it's so much incremental stuff on top of Lisp + lexical scoping. Arguably Smalltalk was a quantum leap, and CLOS is incremental work on top of Smalltalk. But Smalltalk embedded Lisp in objects; CL is embedding objects in Lisp and it doesn't work out as effortlessly.

[mnieper]

Scheme works well as both a research and production language because it was started from genius ideas (lambda calculus, GC, macros, lexical scoping) and hasn't grown much from there; things like vectors and record types are details. Basic ML is similar: started from genius ideas (HM, the merging of types and modules) and didn't venture that far. Same thing with Smalltalk, Prolog, APL, Forth.

That's not accurate. Scheme didn't start with macros. Hygienic macros was a substantial addition, as was the library system, multiple values, promises, and even record types (as they are not at all obvious).

But if the founding ideas are not genius-level stuff, or if some brilliant-but-not-genius people later add or change them substantially, the language winds up with something that looks to outsiders like complexity for the sake of complexity. All the complex FP and OO languages end up like this in my book.

If you really mean what you say, you do the theoreticians behind Haskell a great wrong, for sure.

My prognosis for statically typed Scheme is that since we have brilliant people but no Turing award geniuses are in sight, we'll wind up creating the same thing that most PL researchers create: something intricate and somewhat self-consistent but ultimately hard for an external observer to distinguish from complexity for its own sake. Another cause for concern is that I can't think of one existing language that started out complex and was later simplified. It seems the fate of all languages is to grow in complexity until replaced by other languages (which usually takes decades during which people have to keep using the existing complex language).

Optimal programming languages tend to become as expressive (call it complex if you want) as the natural language because whatever a programmer can formulate in natural languages, they may want to implement in a language one day. The "types" in the natural language are not restricted by rank, nor is the natural language predicative, so it is quite clear why people regularly run across barriers in programming languages and think of how to get rid of these barriers. Of course, not every such move will be optimal.

[lassik]

I would view hygienic macros, record types and the others as polish on the main ideas.

Re: Haskell, lazy evaluation and purity look to be genius ideas akin to HM and lexical scope. But both have probably existed in simpler contexts (if only earlier versions of Haskell), and like Smalltalk's dynamic object system brought into CL, it's not clear how to place it in another context. It's like in art, fusing two complex genres is extremely difficult. Wayne Shorter's Emanon recently fused jazz and classical music to an astonishing degree but the result is very complex and the seams still show a bit. Crucially, in art there isn't a similar impetus to minimize complexity as in tools.

Nobody yet knows what an optimal language looks like. It's possible that the optimal answer is a network of several restricted languages. Empirically, adding restrictions to programming languages is produces great windfalls (GC, purity), but once restricted, digging our way back out from the restrictions to the previous level of expressiveness is really difficult. We should ask John about this since he has a long held interest in linguistics.

[lassik]

Anyway, IMHO the implications for statically typed Scheme:

• We have the talent to copy existing quantum leaps and to do incremental research on top of them. We don't have the talent to make a new quantum leap.
• I'd like to have a practical language. Languages built directly on top of quantum leaps with modest additions make for ideal practical languages - simple, effective, and tractable to implement. Scheme, Smalltalk, APL, Forth all show this.
• Languages that add significant incremental research tend to become very complex (mixing OO and FP, static and dynamic typing, pure and impure, etc.) It seems that any project mixing A and B, where A and B are very different things that no-one has been able to simply merge before, is prone to be like this. These are fine as research vehicles, but suboptimal for practical programming.

It follows that we should clearly decide whether the new language is intended as a research or production language. I explicitly want to make a production language by copying existing quantum leaps; if I'm reading correctly, you prefer a research language first and foremost. It's in our best interest to acknowledge that we are not Turing award winners who can make a really good language for both purposes at once. Even the few who manage that feat do it by accident.

[mnieper]

I do not want just a research language; the language we build should be practical. But I would like to take a look at the research languages to find a sensible subset that will make a great language that offers a bit more than just ML in parentheses.

After all, progress in PL theory and design didn't stop when ML was fixed.

[lassik]

The thing is, I don't believe the goal is achievable. We have insufficient genius. Work toward that goal would be best filed under research.

The core of ML is simple in large part because it promises to do less - not pure. The languages that do more are complex. CL integrates Lisp and OO; Haskell integrates effects and purity. I haven't heard of any simple solution to these problems. If there is one, we should probably go with it, but it would be so appealing to so many people that I suspect we'd have already heard of it.

[mnieper]

1. We have to believe that even we can create something new. The point is that even if we wanted, we cannot just copy the ML semantics and type system for example because Scheme has multiple arguments and values and there is a wish that Steme supports them as well in a natural fashion.

2. What is not "simple" to Haskell's approach to purity? One doesn't need to understand category to use the I/O monad, after all.

[lassik]

We can and do create new things all the time, but it's unlikely we can create something that has an effortless brilliance.

Removing features is the first place I'd start. That's how mere mortals succeed in creating good things: by copying from geniuses and leaving out all the things we can't handle.

Haskell's purity is probably not too complex in isolation, but when you combine it with everything else in the language, it is. Same thing with CL. If CL was nothing but CLOS classes and multi-methods, it would probably be OK. But they merged that with everything else and now the language is impossible to "walk around the perimeter of the language" in your head. It's designed like a zen garden: no matter where you look, part of the garden is always out of view.

I continue to think we are attempting a genius project without actually being geniuses. Countless designers have been in this situation before.

[johnwcowan]

I can't comment on this in detail, but here's a bit about CLOS:

Smalltalk and Loops, one of the ancestors of CLOS, escaped Xerox at about the same time, the early 80s. It's doubtful that either was based on the other: the ideas of OO were "in the air" at the time. ANSI CLOS is a fifth-generation design: Interlisp Loops -> Common [Lisp] Loops -> Portable Common Loops -> mixed with MIT New Flavors (itself the descendant of MIT Flavors) to produce CLOS + MOP -> ANSI CLOS (with MOP typically available and de facto standardized). Loops grew into CLOS because of the limitations of the earlier versions as encountered in actual use, not because of research goals, nor was it a matter of throwing in every interesting feature the designers could think of. In addition, many features were dropped because they were too hard to support portably.

Also, take a look at Robert Strandh's papers on SICL, a new CL implementation in progress that is CLOS-first.

[lassik]

Thanks for the enlightening history of CLOS! It's Interesting to hear they removed stuff too.

Limitations in actual use begat C++, indeed most of the technology around us. This problem is ancient; there is no long-term solution to the most difficult design problems other than genius out of left field. There is no formula the rest of us can follow to make something that stands the test of time by adding existing concepts together when others before us have not been able to do so. The best safeguard for the rest of us is to have a complexity budget, and just accept defeat and try another approach whenever it is exceeded.

[mnieper]

Removing features is the first place I'd start. That's how mere mortals succeed in creating good things: by copying from geniuses and leaving out all the things we can't handle.

Removing features that manifest to be unnecessary or problematic is, of course, never be a bad idea. Maybe we are not that far apart. I think my main point is that in order to develop a "simple" language, we have to understand a lot of "complex" subject matter for otherwise we don't know where to cut, so to speak. I am currently writing a book on rather elementary algebra. But in order to write a good book (I hope it will be one), I absolutely have to know a lot more about the field of algebra than what will finally be in the book.

[aijony]

One of the things that makes scheme both simple and powerful is its ability to expand its expressiveness via macros, continuations, etc. I think the goal should be to come up with the simplest core language possible that can expand itself to express the even the most complex ideas.

Haskell is not a good example of this, as even though the language is a bit of a laboratory GHC is not well exposed to the user and difficult to expand upon.

(I've never programmed in it but I think) Racket has done a good job in having a simple base language, exposing internals, but still the average user is able to make very complex and new languages.

How expressive should the language be?

Just expressive enough to make itself more expressive.

[lassik]

Maybe we are not that far apart.

Indeed, it's both a blessing and a curse of working around Scheme that our people have so many ideas we are constantly arguing about some aesthetic issue or other :) For what it's worth, I feel grateful to be in a community so full of talent, and it's a great education too.

Whenever we have disagreements in Scheme, I always try to keep in mind that the big picture is we agree on so much. Most importantly, we agree on the general direction or the end goal, mainly disagree on how to get there. We'll be wise not to take our disagreements about intermediate steps or side issues too seriously. The best ultimate outcome would be to support all of these languages in one system, with as much interop as is practical.

I think my main point is that in order to develop a "simple" language, we have to understand a lot of "complex" subject matter for otherwise we don't know where to cut, so to speak.

It's definitely true that if we don't understand everything, we'll end up cutting off features at an arbitrary point. That's not necessarily a bad thing if we cut off at the same point as other people before us, and those people knew what they were doing. For example, if we cut off at the same point as Haskell, SML, or Elm, we know approximately what we get. But as you say, it means we cannot be sure whether our decisions are optimal.

My fear is the opposite: if we go into novel territory, we'll end up not cutting enough, and the resulting language will be complex while not being proven. If a better idea is later discovered, we'll have put features into our language that are a suboptimal version of the new, better idea and if our language is already entrenched, it'll be hard to backtrack. It's funny that we have essentially the same fear of making design mistakes, but to counter it, we like to make the opposite bets.

Maybe we should keep try the two approaches in parallel (bottom-up from ML and top-down from the latest research), try to let each take its own course, and see if they converge.

I am currently writing a book on rather elementary algebra.

You are very talented to be able to research a complex book while simultaneously putting so much effort into Scheme!

[mnieper]

One of the things that makes scheme both simple and powerful is its ability to expand its expressiveness via macros, continuations, etc. I think the goal should be to come up with the simplest core language possible that can expand itself to express the even the most complex ideas.

Haskell is not a good example of this, as even though the language is a bit of a laboratory GHC is not well exposed to the user and difficult to expand upon.

(I've never programmed in it but I think) Racket has done a good job in having a simple base language, exposing internals, but still the average user is able to make very complex and new languages.

How expressive should the language be?

Just expressive enough to make itself more expressive.

I agree with everything you wrote. And that's why it is not a trivial task to design a type system. Static types put us in chains so we have to be careful that we lock up only those things we don't want.

[lassik]

Indeed, a large number of very bright people have worked on static type systems for about 40 years (Milner's seminal paper appeared in 1978; the Miranda language appeared in 1985). That the main reason I fear our chances :)

[aijony]

And that's why it is not a trivial task to design a type system. Static types put us in chains so we have to be careful that we lock up only those things we don't want.

Yeah, I honestly highly doubt if such a free-formssystem such as scheme could exist in the same realm as static types.

But I think it is worth a shot.

[lassik]

Closing this for now; the unexpectedly fruitful recent work on effect inference may let us have our cake and eat it too.