I was originally planning to have some kind of algebraic data type[1] which honestly seems a lot like Racket's structs to me. That seemed a natural way to go, given Nulan's pattern matching...

But I can't shake the feeling that this is too rigid for my needs. Maybe I just don't understand ADTs, given how little reading I've done about them. Anyways, if I'm not using ADTs, what should I use instead?

I don't like the traditional idea of types as being concrete, where you say "such and such data is of such and such type". I really want to emphasize the idea of interfaces: "such and such data is capable of being used in such and such ways".

So what I am referring to as a "type" is really an interface: something is a number if it behaves like a number. But I really really dislike Python's duck-typing which dispatches on the method name: in Python, you say, "something is a number if it supports such and such method".

But just because something has a particular method doesn't mean it is a number or a dictionary or whatever: something else may have defined a method with the same name but very different behavior.

And I don't like classes. And although prototypes are pretty neat and flexible, they don't seem very good at specifying interfaces. I really wanted something that is flexible enough to specify both an interface and implementation...

That meant classes, prototypes, and traditional interfaces were out, since they all separate the two concepts: you use an interface to specify an interface, and a class/prototype to actually implement it.

I also wanted something that was a bit more functional-like: I didn't want to be mucking about with dictionaries. Even with immutability, that smells too OOP to me. I wanted it to be nice and flat. And I wanted the ability to arbitrarily compose them, so that meant that any kind of inheritance scheme was a no-go.

I had read a few years ago about traits, specifically the implementation in JS[2]. I went back and read that page again and it seemed a lot like what I wanted, but of course it was written for JS, which meant it used dictionaries and methods a lot.

So I had to "functionalize" it. I really like the end result, but I want to get your guys' opinions on it: maybe point out some flaws, room for improvement, or an alternate system.

---

First, let's define an "equality" interface which says that the data supports equality comparisons:

  $deftrait equality?
    require 1

Let's try writing some data that implements the above trait:

  $defn set; @Args ->
    new equality? Args
      X Y -> all? X; X ->
               any? Y: Y -> is X Y

It will then call "new", which allows you to attach a trait to arbitrary data. The first argument to "new" is the trait, and the second argument is the data. Any further arguments are the concrete implementations of the trait. The equality? trait has one required implementation, so we only pass in one function.

That function will check that all the elements in the first argument "X" are contained in the second argument "Y".

How do we make use of this new set implementation? Let's define a generic "is" function which can work on anything implementing the equality? trait:

  $defn is: (equality? Self F) Y -> F Self Y

There's a nice duality here. That is, any `new foo X Y...` is destructured using `(foo X Y ...)`. The trait system doesn't impose any constraints on things like function arguments or anything like that: if you're implementing a trait, you're expected to follow the user conventions.

This gives you complete flexibility in how the traits are defined and how the concrete implementations are used. Though generally speaking, functions will throw a pattern-fail if you use them in a way they didn't expect, so it should be manageable rather than chaotic.

This means Nulan's type system leans more towards JavaScript/Ruby/Python's "we're all adults here, just be responsible" style of programming, rather than the rigid "everything must be specified and enforced by the system" style found in Haskell.

Okay, that's great and all, but now let's define an "orderable?" trait which is useful for things like binary search trees which require an order. Well, we could do this...

  $deftrait ordered?
    require 2

  $deftrait ordered?
    inherit equality?
    require 1

But let's implement new functionality. We want a "lt" function which implements lower-than functionality, and then by combining "lt" and "is" we can define "gt", "gt-is", and "lt-is":

  $defn lt: (ordered? Self F) Y -> F Self Y
  $defn lt-is: X Y -> $or: lt X Y; is X Y
  $defn gt:    X Y -> not: lt-is X Y
  $defn gt-is: X Y -> $or: gt X Y; is X Y

  $defn lt: (ordered? Self F) Y -> F Y

  new equality? foo
    ...

  $let X: new equality? foo
            ...
    new ordered? X
      ...

  $multi-new foo
    equality?
      ...
    ordered?
      ...

By the way, the "new" function simply creates a one-level-deep wrapper which specifies which traits are implemented and their implementations. Thus traits are inheritently flat: even though it's called "inherit", there's no inheritance going on.

Thus far, we've been creating new data that implement some protocol. We can also use traits to implement custom wrappers:

  $deftrait my-wrapper?

  # wrap the number 5 in the my-wrapper? trait and assign it to foo
  $def foo: new my-wrapper? 5
  
  # unwrap it
  $let (my-wrapper? Self) foo
    # Self is 5
    Self

Another thing I haven't covered yet is "provide", which lets you create a trait that already implements another trait. An example would be the vau? or fn? traits which implement callable?:

  $deftrait vau?
    provide callable?
      $case-vau Env2; [Lex Env Args Body] @Args2 ->
        $lets: Lex: pattern-match Lex Env  Env2
               Lex: pattern-match Lex Args Args2
          eval Lex Body

  $deftrait fn?
    provide callable?
      $case-vau Env: X @Args -> X @(each Args eval)

And the vau? trait represents vaus as a list of 4 items: the vau's lexical scope, environment name, arguments, and body. It then implements callable? so that vaus can be called. This means that you can define new data in Nulan that behaves exactly like vau/fn. And as you can see from the above code, it's quite easy (though I didn't define the "pattern-match" function, it's easy enough to implement).

But of course you don't need any of that since you can create anonymous data that implements callable?:

  new callable? foo
    ...

---

* [1]: http://en.wikipedia.org/wiki/Algebraic_data_type

* [2]: http://soft.vub.ac.be/~tvcutsem/traitsjs/index.html

* [3]: It's crude because it has O(nm) lookup time, because it's implemented in a list. Using a dictionary would be much faster, but I wanted to show off the ability to create new data and dictionaries already support equality.