Expression in Programming Languages

Source: My Quora Answer :

If Clojure is so expressive, and is basically Lisp, hasn’t there been any progress in expressivity in the last 50 years?
Well, as Paul Graham put it quite well, Lisp started as a kind of maths. That’s why it doesn’t go out of date. Or not in the short term.
You should probably judge the evolution of expressivity in programming languages by comparing them to the inventions of new concepts / theories / notations in maths (or even science), not by comparison to other kinds of technological development like faster processors or bigger hard drives.
What I’d suggest is that it turns out that function application is an amazingly powerful and general way to express “tell the computer to calculate something”.
Once you have a notation for defining, composing and applying functions (which is what Lisp is), then you already have an extraordinarily powerful toolkit for expressing programs. Add in Lisp’s macros which let you deconstruct, manipulate and reconstruct the definitions of functions, programmatically, and you basically have so much expressive power that it’s hard to see how to improve on it.
You can argue in the case of macros that, in fact, while the idea has been in Lisp for a while, the notation and semantics is still being actively fiddled with. We know that macros in principle are a good idea. But we’re still working on the right language to express them.
Perhaps we can also argue that there’s still room for evolving some other bits of expressivity. Eg. how to best express Communicating Sequential Processes or similar structures for concurrency etc. In Lisp all these things look like functions (or forms) because that’s the nature of Lisp. But often within the particular form we are still working out how best to express these higher level ideas.
Now, the fact that functions are more or less great for expressing computation doesn’t mean that the search for expressivity in programming languages has stopped. But it’s moved its focus elsewhere.
So there are three places where we’ve tried to go beyond function application (which Lisp serves admirably) and improve expression :

  • expressing constraints on our programs through types.
  • expressing data-structures
  • expressing large-scale architecture

These are somewhat intertwined, but let’s separate them.
Types
Types are the big one. Especially in languages like Haskell and the more exotic derivatives (Idris, Agda etc.) Types don’t tell the computer to DO anything more that you can tell it to do in Lisp. But they tell it what can / can’t be done in general. Which sometimes lets the compiler infer other things. But largely stops the programmer shooting themselves in the foot. Many programmers find this a great boost to productivity as it prevents many unnecessary errors during development.
Clearly, the type declarations in languages like Haskell or Agda are powerfully expressive. But I, personally. have yet to see a notation for expressing types that I really like or find intuitive and readable. So I believe that there is scope for improving the expressivity of type declarations. Now, sure some of that is adding power to existing notations like Hindley-Milner type systems. But I wouldn’t rule out something dramatically different in this area.
One big challenge is this : by definition, types cut across particular bits of computation. They are general / global / operating “at a distance”. One question is where to write this kind of information. Gather it together in standard “header” files? Or spread across the code, where it’s closest to where its used? What are the scoping rules for types? Can you have local or “inner” types? Or are all types global? What happens when data which is typed locally leaks into a wider context?
Data Structures
Lisp’s lists are incredibly flexible, general purpose data-structures. But also very low-level / “primitive”.
I don’t really know other Lisps. But it seems to me that Clojure’s introduction of both a { } notation for dictionaries / maps. And a [ ] notation for data vectors has been useful. Complex data literals can now be constructed out of these by following the EDN format. And it’s given rise to things like Hiccup for representing HTML and equivalents for other user-interfaces or configuration data. EDN is pretty similar to the way you define data in other contemporary languages like Javascript’s JSON etc. So it’s not that “radical”. But it’s nice to have these data structures completely integrated with the Clojure code representation.
Can we improve expressivity for this kind of data representation language?
I’m inclined to say that things like Markdown or YAML, that bring in white-space, make complex data-structures even more human readable and writable and therefore “expressive” than even JSON / EDN.
In most Lisps, but not Clojure, you can define reader-macros to embed DSLs of this form within programs.
So Lisps have highish expressivity in this area of declaring data. In Clojure through extending S-expressions into EDN and in other Lisps through applying reader-macros to make data DSLs.
Can we go further?
By collapsing data-structure into algebraic types, Haskell also comes up with a neat way of expressing data. With the added power of recursion and or-ed alternatives.
This leads us to imagine another line of developments for expression of data structures that brings these features. Perhaps ending up like regular or context free grammars.
Of course, you can write parser combinators in any functional language. Which gives you a reasonable way to represent such grammars. But ideally you want your grammar definition language sufficiently integrated with your programming language that you can use this knowledge of data-structure everywhere, such as pattern-matching arguments to functions.
Haskell, Clojure’s map representation, and perhaps Spec are moves in this direction.
But for real expressivity about data-structures, we’d have a full declarative / pattern-matching grammar-defining sub-language integrated with our function application language, for things like pattern matching, searching and even transformations. Think somewhere between BNF and JQuery selectors.
Shen’s “Sequent Calculus” might be giving us that. If I understand it correctly.
A third direction to increase expressivity in defining data-structures is to go beyond custom languages, and go for custom interactive editors (think things like spreadsheet grids or drawing applications for graphics) which manipulate particular recognised data types. These increase expressivity even further, but are very domain / application specific.
Architecture
“Architecture” is everywhere. It describes how different modules relate. How different services on different machines can be tied together. It defines the components of a user-interface and how they’re wired up to call-back handlers or streams of event processors. “Config files” are architecture. Architecture is what we’re trying to capture in “dependency injection”. And class hierarchies.
We need ways to express architecture, but mainly we rely either on code (programmatically constructing UIs), or more general data-structures. (Dreaded XML files.)
Or specific language features for specific architectural concerns (eg. the explicit “extends” keyword to describe inheritance in Java.)
OO / message passing languages like Smalltalk and IO do push you into thinking more architecturally than many FP languages do. Even “class” is an architectural term. OO languages push you towards thinking about OO design, and ideas like roles / responsibilities of various components or actors within the system.
Types are also in this story. To Haskell programmers, type-declarations are like UML diagrams are to Java programmers. They express large scale architecture of how all the components fit together. People skilled in Haskell and in reading type declarations probably read a great deal of the architecture of a large system just by looking at type declarations.
However, the problem with types, and OO classes etc. is that they are basically about … er … “types”. They’re great at expressing “this kind of function handles that kind of data”. Or “this kind of thing is like that kind of thing except different in these ways”.
But they aren’t particularly good to express relations between “tokens” or “concrete individuals”. For example, if you want to say “this server sits at address W.X.Y.Z” and uses a database which lives at “A.B.C.D:e”, then you’re back to config. files, dependency injection problems and the standard resources of describing data-structures. Architecture is treated as just another kind of data-structure.
Yes, good expressivity in data-structure helps a lot. So EDN or JSON beats out XML.
But, really, it feels like there’s still scope for a lot of improvement in the way we talk about these concrete relationships in (or alongside) our programs.
OK, I’m rambling …
tl;dr : function definition / application is a great way to express computation. Lisp got that right in the 1960s, and combined with macros is about as good as it gets to express computation. All the other improvements in expressivity have been developed to express other things : types and constraints, data-structures and architecture. In these areas, we’ve already been able to improve on Lisp. And can probably do even better than we’ve done so far.

Leave a comment