Lists
In Shen as in Qi, a list consists of a series of items, seperated by whitespace, and flanked by [ and ] to the
left and right. [] is the empty list as is (). Note that Kλ does not understand [...] and that the Shen reader
translates this idiom into Kλ. The basic constructors are 'cons', 'hd' and 'tl' and 'cons?' corresponding to CONS,
CAR and CDR, and CONSP in Lisp.
It is an error to apply 'hd' or 'tl' to anything but a list.
There is the question of how to treat the application of 'hd' to the empty list []. Ideally this should produce
an error. In Common Lisp the CAR of the empty list is the empty list. Actually coding 'hd' so that it returns
an error in Common Lisp requires encoding a non-empty list test into the definition of 'hd'. This is generally
unnecessarily expensive in such a heavily utilised function, because often the programmer knows before applying
hd that the list is non-empty. Hence in Shen 'hd' does not presuppose a non-empty list test and the result of
applying 'hd' to the empty list is platform dependent. For implementors building Kλ from scratch we recommend
raising an error, as applying 'hd' to the empty list is a deprecated operation.
For that reason in Shen, 'hd' is not given a type since its behaviour is type unpredictable. There is a function
'head' of type (list A) --> A in Shen which is well-behaved and which does make a non-empty list test and which
raises an error if applied to the empty list.
Similar observations apply to 'tl' which if applied to the empty list in Common Lisp produces an empty list. In
other languages, an error may arise. Hence by parity of reasoning, the result of (tl ()) is platform dependent
and there is no type for 'tl'. There is a function 'tail' of type (list A) --> (list A) in Shen which is well-behaved
and which does make a non-empty list test and which raises an error if applied to the empty list.
Note that 'cons' applied to X and Y where Y is not a list provides a result which is called a dotted pair . This
form of application is needed in Shen in the internals of Shen Prolog. In Shen 'cons' does have a type because
the type checker is capable of failing dotted pair applications as type insecure. Hence the type of 'cons' is
A --> (list A) --> (list A). In Shen, the dotted pair (cons a b) is printed off as [a | b]. |
