Friday, June 7, 2019

The Semantic Trinity

I've been thinking a lot recently about what people mean when they use the word "semantics", specifically in relation to programming languages. If you go on Wikipedia, you'll find many different kinds of semantics described that are used in computer science.

A macroscopic view of the work that compilers do, is that it's simply a translation of semantics that are ergonomic for humans into semantics that are ergonomic for machines. From this view, we get a 2-Semantic model. To put it more concretely, we have one set of semantics for source code (let's call it HS for high-level semantics), and one set for executing on hardware (let's call it LS for low-level semantics).

One of the problems of computer science (and also a reason why it's exciting) is that the field is constantly changing. This means that both HS and LS designs change. With the 2-Semantic model we are constantly throwing away old code that works, either because it makes assumptions about hardware that are no longer true, or because it's written in old languages that don't interface with new languages.

Many modern languages have moved to more of a 3-Semantic model that utilize a semantic layer between HS and LS, which we can call MS. We've entered an era of virtual machines and abstract runtimes. This buffer layer means that it's easier to swap out the semantics on the human side or the machine side, and still preserve the usefulness of legacy code. But what about the design of the semantics for this middle layer?

There are many modern choices for MS. Most of them come from a clear Turing machine heritage, like JVM, CLR, LLVM, etc. Some functional languages choose a lambda calculus based MS, although there doesn't seem to be any standardized MS shared between functional languages (hopefully GRIN will change that).

Semantics that are easy for humans to understand come with human baggage, and semantics that are easy for machines to understand come with machine baggage. What about developing semantics that have as little baggage as possible? It seems that that is the domain of mathematics, although the mathematical community has its own baggage.

I would like to see a MS that lasts 50-100 years, and becomes almost universal among languages. I don't think any of the current layers are viable for that sort of longevity or mass adoption.

So what are the problems with the current MS designs?
  1. They don't capture semantics from HS that are relevant to optimization in LS
  2. They expose too many low-level details that aren't relevant to high-level languages
  3. They are more complex than they need to be
  4. They are biased towards particular HS designs
I think it's possible to make that long-lived MS, and I'm working on an attempt to do so, although it would involve some compromises to the HS layers. Hopefully most language designers will agree with the problems I've laid out, because what I will propose as an alternative is fairly radical.

2 comments:

  1. I have been working for several years on the issue of a notation that would survive 50 to 100 years. It is a very challenging thing, but i have made a lot of progress. Perhaps you might be interested in my work. Not sure how to give you my email without creating a spam avalanche, e-dejong.com

    ReplyDelete
  2. Interesting!

    From taking a quick look, it seems you're taking a very different approach than me. I'll have to spend more time on it later.

    ReplyDelete