What is a sort in Programming Language Semantics?

It appears in chapter four that sorts are for syntax and types are for semantics.

The example syntax chart on page 40 deals with the sorts in the language L{num str}. Apparently sorts are categories in the syntax of the language.

In particular, "plus" has a sort, which is the syntactic category of its result. The sort of the operator "plus" is named "Exp". That represents the fact that syntactically, an invocation of the operator "plus" is an expression. An invocation of the operator "plus" can fill a position in an abstract syntax tree where an expression is permitted. That's what kind of construction a "plus" is. That's how it fits into the structure of a text that represents a program.

The type system on page 41 deals with the types in language L{num str}. The type of operator "plus", given that its operands have type "num", is "num". This judgment is a partial description of the semantics of operator "plus". That is, part of the meaning of the operator "plus" is the combining of two numbers to produce a number. This meaning distinguishes "plus" from other expressions.

Furthermore, there is a sort named "Typ" that contains the two types, "num" and "str".

It depends on what semantics we would take for types and sorts. -- However a brief - little informal - definitions could be - Sorts are classes of ASTs and types are classes of values.

This is all from memory - I have not looked at it for quite a while, and I do not have the book you mention.

There is actually much similarity between sorts for the abstact syntax and types as usually understood. But sorts are a formal syntactic concept. Then, AS trees are syntax too.

An AST may be seen as a term in a multisorted algebra, i.e. an algebra where operators are typed (to speak informally) and characterised by a signature specifying the sort of arguments (i.e. subtrees, subterms) and the sort of the resulting tree. Thus operators cannot be used to build arbitrary trees. Now formal algebras can receive interpretation, and then sorts would be interpreted as types, as domains of values. However, in the case of the AS of a programming language, the types corresponding to the sorts in a semantic interpretation are the domains used to describe this interpretation. They are not the types used by programmers writing programs with that language.

Things may sometimes be a bit more complicated in practice, because some forms of abstract syntax allow some operators to buid trees (expressions) that belong to several sorts (an informal way to look at it). For example there could be a sort for syntactic constructs that represent variables (assignable entities), and another for expressions. But any variable can be used as an expression, the converse being false.

Early papers on this, for programming languages, date back to the mid-seventies. The conceptualization at the time was intended for the production of syntax conscious (the word "directed" was then used) programming environments. Look for Mentor and Centaur in Europe and for Cornell Program Synthesizer in the USA. They were the first two system to actually use such concepts in a practical way. Many others were developped afterwards.

But abstract syntax predates these systems. The Lisp language (1958) had abstract syntax, which is no surprise as it was developed by a logician, and for the purpose of making programs that manipulate programs (see also ML and LCF ... that came later). But Lisp was not sorted : everything was syntactically a list and more refined structure was essentially semantics dependent. This lead some people to consider, somewhat incorrectly, that Lisp had no syntax.

I would think that multi-sorted algebras are older than that. But I do not really know.