Recursive Types and Null

In Irken, like in Rust, types are not automatically allowed to be null. As a result, accidental runtime null pointer errors are impossible. Instead, if you wish for a type to be optionally present, you can use an algebraic datatype such as maybe.

(datatype maybe 'a  
  (:yes 'a)
  (:no))

Working with types like maybe is safe because it requires an explicit unfold operation. This unfold comes in the form of match and pattern matching, which requires you handle every case explicitly. For example, consider the following function:

(define (print_value x)  ;; type is : ( (maybe string) -> #u )
  (match x with
    (maybe:yes x_value) ->  (printf "yes: " x_value "\n")
    (maybe:no)          ->  (printf "no\n")
  ))

We use match to unfold the possible values of maybe, and Irken's pattern matching requires us to handle every possibility. If we had omitted the case for (maybe:no) it would be a compiler error.

Type Recursion and Infinite Types

Because NULL is not an allowed value for every type, for a recursive type-construction to be valid, it must contain variant branches which allow it to be optionally non-recursive. For example, the following type construction is invalid, because it is an infinite type:

(datatype nested
  (:t nested))

There is no way to construct a finite version of the above type, because every construction must contain another construction! To see why this is the case, try to write a finite construction of the type.

(nested:t (nested:t (nested:t ...

There is no way to end the construction, because every (nested:t ...) must contain another one. There is no optionality to the recursion. Compare that to (list 'a) where the non-recursive (list:nil) variant allows us to end the construction.

(datatype list 
  (:cons 'a (list 'a))
  (:nil))

(list:cons 1 (list:cons 2 (list:cons 3 (list:nil))))

Records types are non-recursive

Because types can not be optionally Null, Irken records are not allowed to be directly recursive. Consider the following record type:

(typealias nested { next=nested } )

This type is infinite, and thus invalid, because there is no way to construct a finite version of this type, for the same reason as our nested datatype example above above. In order to create a valid type, we must introduce optionality to the recursion, as in:

(typealias nested { next=(maybe nested) } )

Mutually Recursive Types

Invalid infinite type constructions are not limited to single types. Multiple types may be combined, possibly via parametrics, to form invalid infinite type constructions. For example:

;; valid parametric container
(typealias container {contains='a})

;; invalid infinite type
(typealias b1 (container b1))
(typealias b2 (container (container b2)))
(typealias b3 (container (container (container b3))))

These are all invalid infinite types, because there is no optionality to the recursion.

The simplest way to avoid this is to use the maybe type to introduce optionality to the recursion.

;; parametric container
(typealias container {contains='a})

;; valid types, with optionality in recursion
(typealias b1 (container (maybe b1)))
(typealias b2 (container (container (maybe b2))))
(typealias b3 (container (container (container (maybe b3)))))

---

Next: Exceptions

---

References

• Cornell lecture on Infinite Types, isorecursion, and eqirecursion