3.4 Lists

The need for homogeneous   lists came naturally when designing an abstract syntax. However one may have to make a choice between ``+-lists'' (which cannot be empty) and ``*-lists'' (which can be empty). This is in particular the case when both kind of lists (of the same base elements) can be found at different points in a program.

The easiest solution is to have only a ``*-list'' in the abstract syntax. Allowing at some point empty lists that must be rejected later on, for example by a type-checker.

exp_s : Exp* -> Exp_s;

A more rigorous solution is to use a ``+-list'', and a special node allowed when the list is optional.

exp_s : Exp+ -> Exp_s;
none : -> Opt_Exp;
Exp < Opt_Exp;

The same sort of problem occurs when we have to give an abstract syntax to bounded lists, or even lists.

List operators