Goal

Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary.

Why Haskell data

• Simple
• Nice pattern matching
• Functional (immutable)

What we want to avoid

• mutablility (harder to reason about)
• inheritance (type heirarchies should be encapsulated in functions, not data. Data just is)

Example

data Maybe a = Just a | Nothing

• Let's start with the the value constructors:

Just a | Nothing

Data types

Data types have four parts:

• A constructor function (turn a series of labeled values into one typed value)
• A predicate (returns true for all values of this type)
• A deconstructor function (given an instance and a series of labels, return to me those values)
• type info function (given a function, return me the metadata (field labels) for that type)

Definition (srfi-99)

Back to the Future

 (define $data-type 
   (make-rtd 'data-type 
    '#((immutable type); procedure
       (immutable constructor) ; procedure
       (immutable predicate) ; procedure
       (immutable destructor)) ; procedure
    #f 'sealed 'opaque))

Constructing data type

• We could use a function ...
  (define Just (make-data-type 'Just '(value)))
(define Nothing (make-data-type 'Nothing '()))

• but a macro makes it pretty
  (define-data-type Just (value))
(define-data-type Nothing)

De-structuring data-types

Everything is built on this:

 (define (call-with-data-type data-type proc)
    (call-with-values (lambda () (data-type-destructor data-type)) proc))

Examples

(define-syntax new
  (syntax-rules ()
    ((_ type values ...)
    (call-with-data-type type (lambda ($ @ ? *) (@ values ...))))))

(define (instance-of? type obj)
      (call-with-data-type type (lambda ($ @ ? *) (? obj))))

Example (destructure data)

(define (data-ref obj type fields)
  (cond 
   ((list? fields)
    (call-with-data-type type 
     (lambda ($ @ ? *)
      (if (? obj) 
       (call-with-values (lambda () (apply * obj fields)) (lambda result result))
       (assertion-violation 'data-ref "Invalid type!" type obj)))))))

Re-imagining λ

• Factor (or any other concatenative language) -- deconstructs (pops) a stack and return's values (pushed) back on a stack.

• Lisp -- deconstructs a list and return's values

• type-lambda -- deconstructs data and return's values

de-structuring values

(type-lambda x
   (Just (a) a)
   (Nothing () 'nothing)
   (else 'not supported))

• type-lambda generates a function where, given a single argument,
  • It will run that argument through each clause until it finds a matching data type.
  • Once found, it decomposes the type into it's parts and executes your expressions with those arguments.

destructure values (expansion)

remember data-ref?

(lambda (x)
  (call-with-data-type Just 
     (lambda ($ @ ? *)
      (if (? x)
       (call-with-values (lambda () (apply * x 'a)) (lambda (a) a))
       (call-with-data-type Nothing 
    (lambda ($ @ ? *)
     (if (? x)
      (call-with-values 
       (lambda (apply * x '())) 
       (lambda () 'nothing)))
      'not supported)))))))

type-lambda features

examples are type-lambda clauses

• rename fields
  (Point ((a y) (b x)) (+ a b))
• destructure hashtables
  (hashtable ((x 'hello) (y 'world))) (+ x y))
• destructure vectors
  (vector ((x 1) (y 3)) (+ x y))
• destructure list
  (list (x y z) (list z y x))
• handling booleans (#t, #f)
  (\#t "this is true")

type-lambda features (cont)

• any (predicate . destructure) combo
  (((type-lambda (Point (x y) (and (> x 0) (> y 0))) (else \#f)) . (destructor Point)) (x y) (list x y))

But sometimes I really want to have a mutable type

• No Problem! Use closures
  • Example:
    (MuPoint (x y) (x 5) (y))
  • Advantages
    • You can specify different types of places (scalar, vector, lifo, fifo, etc).
    • You can specify locking strategy for multi-threaded environments.

Sum Types

(define maybe? (type-lambda (Just (a) \#t) (Nothing () \#t) (else #f)))
(when (maybe? x) 
   (type-case x (Just (a) a) (Nothing () 'nothing) (else \#f)))

• But wouldn't it be nice if we had some syntax so that when I call maybe, I had to provide both Just and Nothing

• Did someone say syntax?

Sum Types (as macro)

(define-type Maybe (Just a) (Nothing))

expands to:

(define-data-type Just a)
(define-data-type Nothing)
(define-syntax Maybe
 (syntax-rules (Just Nothing)
  ((Maybe x (Just clauses (... ...)) (Nothing clauses (... ...)))
   (type-case x
    (Just clauses ...)
    (Nothing clauses ...)
    (else \#f)))))

Recursive Types

• Similar to a sum type, but more advanced predicate

(define-data-type Nil)
(define-data-type Node x l r)
(define tree? (type-lambda (Nil () \#t) (Node (x l r) (and (tree? l) (tree? r)))))

Type Classes

• Type Classes are a set of functions that can have different implementations depending on the the type of data they are given.

• Let's examine the structure of a type class. Using Eq as an example.

• (define-type-class (Eq type) (equals)
  • type is our type variable
  • equals is our function

Type Classes

• We also need:
  • A "constructor" that takes these and returns nothing (we run this for the side effects.)
  • A predicate where, given an object, returns true if the type of the object was construct by our constructor.
  • A destructor that returns the functions that we previously constructed.

What's a data type again?

 (define $data-type 
   (make-rtd 'data-type 
    '#((immutable type); procedure
       (immutable constructor) ; procedure
       (immutable predicate) ; procedure
       (immutable destructor)) ; procedure
    #f 'sealed 'opaque))

What is a Type Class?

• A type class is a kind of data type
• As long as we implement our 4 procedures, we can customize how a "data type" behaves.

make-type-class

(define (make-type-class name type-parms fields)
(let ((library '())
      ($funcs (make-rtd name (list->vector (map (lambda (f) `(immutable ,f)) fields)))))
  (let ((funcs@ (rtd-constructor $funcs))
    (funcs* (rtd-destructor $funcs))) 
   (define ($ proc) (proc 'type-class type-parms fields library))
   (define (@ . rest) 
    (let ((parms-fields (fold-left 
            (lambda (a e) 
             (cond 
              ((< (length (car a)) (length type-parms)) 
               (cons (cons e (car a)) (cdr a))) 
              (else (cons (car a) (cons e (cdr a)))))) (list '()))))
        (cons (cons (reverse (car parms-fields)) (apply funcs@ (reverse (cdr parms-fields)))) library)
        #f))

make-type-class cont

   (define (? . instances)
    (assp (lambda (parms) (for-each (lambda rest (apply instance-of? rest)) (map list parms instances))) library))
   (define (* objs . fs) (apply funcs* (cdr (apply ? objs)) fs))
   (make-data $ @ ? *))))

Conclusions

• Data Types provides a simple, extensible way to handle values.

• The same structure can handle data as well as type classes

• macros makes it pretty and friendly.

• λove the λambda

Play @ home

• Slides http://smyles.com/haskell-data-types-scheme/
• Code http://smyles.com/haskell-data-types-scheme/data.scm
  • Code is in the Public Domain. Copy, Steal, take credit (or the blame), but by all means improve it and share. I trust you.
  • This code depends on my r6gambit library http://code.smyles.com/projects/r6gambit. Mostly implemented w/ Gambit's type system.

The Prestige

Thank you