Practical Uses of Dependent Types in Programming

Scala has full intersection types built into the language:

trait IX {...}
trait IY {...}
trait IB {...}

class A() extends IX with IY {...}

class B() extends IX with IY with IB {...}

def fn(): IX with IY = if (...) new A() else new B()

Type declarations and static analysis

Since no value typed as NIL can exist, the use of the NIL type is mostly relevant for static analysis. T and nil respectively represent the top (⊤) and bottom (⊥) types and might be used when inferring the type of expressions. Consider the following example:

(defun the-thing () (length (1+ (read))))

• The type of (read) is T, because if reading succeeds, the returned value can be anything.
• The type of (1+ (read)) is necessarily NUMBER, because the returned value exists only if no error is signaled. And if this is the case, we know from the type analysis of + that the result is a number.
• The type of (length (1+ (read))) is NIL, because length returns a value only for sequences. Giving a number is guaranteed to signal an error, and thus the possible values returned by the function is represented by the empty type (an empty set of values).

This kind of analysis is not only theoretical, it actually happens with SBCL:

* (defun the-thing () (length (1+ (read))))
; in: DEFUN THE-THING
;     (LENGTH (1+ (READ)))
; 
; caught WARNING:
;   Derived type of (+ (READ) 1) is
;     (VALUES NUMBER &OPTIONAL),
;   conflicting with its asserted type
;     SEQUENCE.
;   See also:
;     The SBCL Manual, Node "Handling of Types"
; 
; compilation unit finished
;   caught 1 WARNING condition

THE-THING

Moreover, here we can see the derived type of THE-THING:

* (describe #'the-thing)

#<FUNCTION THE-THING>
  [compiled function]

Lambda-list: ()
Derived type: (FUNCTION NIL NIL)
Source form:
  (SB-INT:NAMED-LAMBDA THE-THING
      NIL
    (BLOCK THE-THING (LENGTH (1+ (READ)))))

The NIL type means: this functions will not return successfully. For example, in SBCL, the error function has the following declared type:

(FUNCTION (T &REST T) NIL)

... because it never returns a value but signals a condition. You can use NIL in function type declarations explicitely if you want. By the way, please notice that SBCL only gives a warning and still compiles your code: you can call the function and it will trigger the dynamic checks that will lead you to the debugger, etc.

NIL implies the absence of "normal" termination. If the body of your function is (loop), the return type is also NIL. But sometimes you can return normally but you do not have any value to return (like void in C). That is why (values &optional) is more appropriate as a type declaration when you return no value successfully. This is done by using the (values) expression in your code. The &optional keyword in the type declaration is necessary because the type (values) would allow you to return more values (see comments).

Is nil necessary?

Some implementations might not care about nil. Since you wonder if we could remove it without causing any harm, maybe trying to remove the nil type from an implementation could be an nice experiment, to see how much does effectively break in practice.

Foreign types

Regarding foreign types, I doubt it can be used like in Haskell, while conforming to the spec, because:

1. the behavior is undefined if a value does not match the declared type, and
2. there is already a type for foreing values in CL (but maybe I did not understand exactly what you mean with foreign types and Haskell).

This is purely speculative, but maybe a variable (or an array) of type nil allocated by a CL runtime could be handled to some foreign code (using implementation-specific means). This is not how it is done in CFFI.

The case of nil arrays

I don't know why (maybe just because there is no check) some implementations like SBCL allow arrays of elements of type nil, defined as follows:

(type-of (make-array 10 :element-type nil) )
=> (SIMPLE-ARRAY NIL (10))

However, one can't access an element of such an array:

(aref (make-array 10 :element-type nil) 5)

The following type error is caught: "The value 5 is not of type (MOD 4611686018427387901)." Moreover, the backtrace contains the following line, where the actual content of the array is seen containing random values:

(AREF "¿[¦^D^P^@^@^@×[" 5)

Accessing uninitialized arrays has undefined consequences (see comments). Consequences are undefined even if the actual data is only referenced and not effectively used for its content, as in:

(LENGTH (LIST (AREF (MAKE-ARRAY 1) 0)))

The example is taken from the "Issue UNINITIALIZED-ELEMENTS Writeup".

I see no reason to allow the creation of arrays of type NIL in the first place, apart maybe from allocating (useless?) memory. As said above, maybe there is an implementation-specific, totally not portable way for some lisp to use such arrays, and pass them to foreign functions, but I doubt it.

Finally, in Maclisp's manual (note that Maclisp predates Common Lisp), it is said that NIL arrays can be used as arrays of type T but make the garbage collector behave as if no objects were referenced. However, here is what the manual says about them:

Type NIL arrays are discouraged even for those who think they know what they are doing.