Wanted: support for some structurally recursive types

Bug #1214610 reported by Jan Moringen on 2013-08-20
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
SBCL
Undecided
Unassigned

Bug Description

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) wrote :

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

To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers