[FOM] Formation Rules

[John McCarthy]

I think it is too limiting to regard formal languages as sets of
strings.  It is better consider them as algebraic structures, of which
strings are an example.  I proposed abstract syntax in my 1962 IFIPS
Congress paper "Towards a mathematical science of computation".
Interpretations, inference rules, and compilation rules are more
readily defined using appropriate abstract syntaxes.  Making formal
languages algebraic structures permits imposing conditions like such
as, for example, And(p,q) = And(q,p) if one wants to make
commutativity of And part of the language definition.