Algebraic Expression Languages [6]
Variations in syntactic style and semantic domain
Once we have abstracted out the structure from both the data type and the fold,
it is especially easy to vary the details of the syntactic representation and/or
semantic domains we use for expressions. As mentioned before, we could reasonably use
strings, lists of digits, Peano numerals, Ints or Integers
for the representation of literals.
We might also use strings, characters or values of an enumerated
type for operators. If we use meta-language integers for the literals, it might
be considered reasonable to use meta-language functions to represent the operators:
then the fold required to evaluate the expressions is just fold id id!
{ Semantics in numerals (rather than integers). Semantics in other numeric types. }
This flexibility and the plethora of options raises the question of what counts as
a representation (syntax) and what counts as meaning (semantics): there is no
straightforward answer to this question (perhaps the distinction between the
two is only a red herring), but we can sketch out some of the issues:
- To the extent that we use "looser" representations (such as strings),
we leave ourselves open to the possibility of ill-formed terms that
must be considered meaningless (or worse, accidentally given some bogus meaning);
using "tighter" representations (such as enumerated types) obviates some
of the burden of checking for well-formedness (or shifts it to the
meta-language, e.g., Haskell's type system). Strings over an inclusive
alphabet are an especially loose representation and make structure
particularly implicit: perhaps they are thus the ultimate syntax.
- To the extent that we use meta-language values for meanings (e.g., Haskell
Ints), we obscure some of the work we would otherwise
need to do to implement operations on more explicit representations,
since the work is done for us transparently by the meta-language: this
might be considered an advantage (less work) or a disadvantage (important
details obscured).
- If we use integers in our representations (e.g., as literals in
algebraic expressions), we can always convert back to a string
representation for the purposes of checking equality or printing. But if
we use functions (infinite ones, in any case) in "syntactic" representations,
we cannot print them (in any full or sensible way) nor can we check them
for equality. Perhaps the possibility to print or check for equality might
be considered characteristic of syntax.
- If we can faithfully implement the operations relevant to our semantics
in terms of some representation, then perhaps that representation should
qualify as a medium for semantics, since we can work with the representations
of values to compute results. But then we should ask what we mean by
"faithfully"; i.e., we ought to ask what is the specification or
theory of the intended models.
- Finally, no matter what domains we consider appropriate for syntax or
semantics, as computer scientists we should be sensitive at least to
the tension between abstract behavior and real computation, where the
latter includes the consumption of resources such as space and time.
type AExp0 = Expr Int AOp
eval0 = fold id sem where sem Add = (+) ; sem Mul = (*)
-----
type AExp1 = Expr Nat AOp
eval1 = fold id sem where sem Add = add ; sem Mul = mul
-- here "add" and "mul" are the iterative algorithms on Nats
-----
type AExp2 = Expr String String
eval2 = fold num sem where sem "+" = (+) ; sem "*" = (*)
-----
type AExp3 = Expr Int AOp -- semantics as [Bit]
eval2 = fold bits sem where sem Add = addbs ; sem Mul = mulbs
-----
prt = fold show (inf . syn)
syn Add = "+"
syn Mul = "*"
inf o l r = par (unwords [l, o, r])
par s = "(" ++ s ++ ")" |
Notes
