ShenDoc 30


 

 

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].

Acknowledgements

History
Basic Types in Shen and Kλ
The Primitive Functions of Kλ
The Syntax of Kλ
Notes on the Implementation of Kλ
Boolean Operators
The Syntax of Symbols
The Semantics of Symbols in Shen and Kλ
Packages
Prolog
Shen-YACC
Strings
Strings and Pattern Matching
Lists
Streams
Character Streams and Byte Streams
Bytes and Unicode
Reader Macros
Vectors
Standard Vectors and Pattern Matching
Non-standard Vectors and Tuples
Equality
I/O
Generic Functions
Eval
Type Declarations
External Global Variables
Property Lists and Hashing
Error Handling
Numbers
Floats and Integers
The Timer
Comments
Special Forms

Built by Shen Technology (c) Mark Tarver, September 2021