Wanted: support for some structurally recursive types

[Jan Moringen]

It would be nice to be able to use structurally recursive types such as

(deftype proper-list (&optional (element-type t))
  `(or null (cons ,element-type (proper-list ,element-type))))

It would also be nice to handle invalid types such as

(and . #1=(t . #1#))
#1=(and #1#)

more gracefully.

This seems to be within the possibilities outlined in X3J13 Issue RECURSIVE-DEFTYPE (http://clhs.lisp.se/Issues/iss291_w.htm).

An initial implementation draft can be found at:
https://github.com/scymtym/sbcl/commits/wip-recursive-types-with-back-edge

Major and minor issues with the above implementation:

* It is not clear, which additional extensions of type methods are necessary to cover all possible uses of recursive types

* Documentation is incomplete

* VALUES-SPECIFIER-TYPE requires a kludge to work in cold init

* Another kludge: a particular special variable only works when put into src/code/primordial-type.lisp

* #+sb-simd-pack tests never ran because the development platform was x86

* Unit tests are minimalistic

* Some CTYPE structure slots can no longer be :READ-ONLY

* Compiler warnings and error can easily contain circular structures which can make the session unusable when printed

[Jan Moringen (scymtym)]

One more issue: the various circularity detections use special variables, lists and linear search (slow but easy to implement for initial exploration)