Arc Forumnew | comments | leaders | submitlogin
Some of my thoughts on Nulan's type system
2 points by Pauan 4445 days ago | 6 comments
So, I've been thinking a lot about types in Nulan.

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
We've defined a first-class trait called "equality?" that requires a single implementation function. We haven't yet defined any functions that use the equality? trait, nor have we defined any data that implements it either.

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
Here we've defined a crude mathematical set[3]: the function "set" accepts any number of args, which is generally a list.

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
Okay, here's what happened. The first argument to "is" is something that must implement the equality? trait. It will then destructure it, putting the data into "Self" and the single implemented function into "F". We then call the function with the arguments "Self" and "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
...where the first function is equality checking and the second is lower-than checking... but I'd really rather not have to repeat myself, so instead, let's just say that the ordered? trait inherits from the equality? trait:

  $deftrait ordered?
    inherit equality?
    require 1
What this means is that anybody implementing the ordered? trait must also implement equality?. In other words, ordered? is a subtype of equality?, so we can use all ordered? data with the "is" function defined above.

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
The definition of "lt" is the same as "is" except it specifies "ordered?" rather than "equality?". But as said before, there's no set contract on the implementation functions. I could instead have defined it so that the function is only passed "Y" and not "Self":

  $defn lt: (ordered? Self F) Y -> F Y
Anyways, by implementing ordered? you get "is" and "lt". You also get "gt", "lt-is", and "gt-is" for free. But how do you actually implement it? You could create some data that implements equality...

  new equality? foo
    ...
...and then compose it...

  $let X: new equality? foo
            ...
    new ordered? X
      ...
...but that's common enough that there's a vau called $multi-new that does it for you:

  $multi-new foo
    equality?
      ...
    ordered?
      ...
The above creates data that implements both equality? and ordered?, thus it fulfills the trait's contract.

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?
That's it. It's a trait that has no requirements at all, which means anything can implement it:

  # 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
So this functions exactly like Arc's annotate/type/rep: it lets you tag arbitrary data types, determine whether they are a particular type, and extract the raw data. But obviously this is much more powerful than Arc's system, since data can easily have multiple traits and the wrappers are flat/transparent: no more needing to deal with multiple nested types.

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)
Now if you add the fn? trait to something, it will automatically be treated as a callable object that when called will first evaluate all its arguments and then pass them to the underlying data.

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
    ...
But it's nice to actually define a named trait because now other traits can inherit from it.

---

* [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.



1 point by Pauan 4445 days ago | link

Oh yeah, and I just realized: if traits aren't restricted to functions, you can use them to define new data, just like Racket's structs:

  $deftrait foo?

  new foo? 1 2 3 4 5
Here we've defined a new "struct" called foo? which has a variable number of "fields". You can then destructure it like so:

  (foo? A B C D E)
This gives a much more flexible and simpler alternative to Racket's struct system, but combines it with the full power of trait inheritance. Thus, this trait system solves a huge number of problems:

You can use it to define new data. You can use it to define new behavior for data. You can use it to specify interfaces and protocols that data must conform to. You can use it as a flat/transparent wrapper to tag data...

And it's all handled in a very simple and straightforward and flexible way. And traits work extremely well with immutability too: you can "extend" a trait with more behavior and "extend" some data with more traits, simply by adding them in an immutable fashion, just like a dictionary/list/etc.

---

Also, I didn't cover "meta-traits", which are traits that can be applied to traits, since traits are first-class data like everything else. Unfortunately, I haven't yet thought of any use for such a meta-trait system...

-----

2 points by Pauan 4445 days ago | link

And another thing I just realized... if I got rid of "new" and instead said that simply calling the trait defines something of that trait... then this solves the dichotomy between [] pattern matching and the type system.

To explain, [1 2 3] is expanded by the parser into (%seq 1 2 3). That is, it is a concrete implementation of the sequence trait. But I can actually combine those two... by having it instead expand to (seq? 1 2 3). And then seq? would be defined something like this:

  $deftrait seq?
    provides immutable?
    provides orderable?
    provides ordered?
    provides iterable?
      ...
That is, it's an abstract trait that accepts 0 or more arguments, is immutable? and orderable? and ordered?. Now, calling (seq? 1 2 3) will create a new "instance" of the trait seq? and using (seq? A B C) with pattern matching will destructure it...

Oh yeah, and I didn't mention before, but I want to provide a pattern-matchable? trait. This lets you define custom behavior when pattern matching. So then the dictionary trait could be defined like so...

  $deftrait dict?
    inherits seq?
    
    provides iterable?
      ...
    
    provides pattern-matchable?
      ...
And I want the ability to remove traits. So you could create a dictionary that inherits from seq? but is not immutable:

  $deftrait mutable-dict?
    inherits seq?
    removes immutable?

-----

1 point by rocketnia 4441 days ago | link

While it seems fine to get rid of 'new, your reason for doing so doesn't make sense. Can't (%seq 1 2 3) be implemented as a procedure that calls (new seq? 1 2 3)?

-----

1 point by akkartik 4445 days ago | link

Can you comment on similarities to and differences with Go? http://golang.org/doc/effective_go.html#interfaces_and_types

-----

1 point by Pauan 4445 days ago | link

Well, from what I understand, Go has a separation between "interface" and "implementation", correct? You use this blob of code to specify the interface and this blob to implement the implementation of the interface.

In most of my examples, I showed how you can use traits like interfaces/protocols: the trait specifies traits and functions implement the behavior. But you can also use "provide" to implement the behavior directly in the trait. So my traits system blends the two together.

And you can use them as wrappers and data structs, something that I don't think you can do with interfaces in Go.

---

In addition, from what I understand, Go basically says, "if ANY type implements these functions with these signatures, it's a member of this interface."

My traits are more restrictive than that: the data type has to be tagged with a trait in order to be recognized as possessing that trait.

In other words, Go's system is a lot like Python's system: if it has these methods, it's a member of the type. Except Go also uses the function's argument and return signatures to further disambiguate, so Go avoids a lot of the problems of Python's system.

-----

2 points by akkartik 4445 days ago | link

Go basically says, "if ANY type implements these functions with these signatures, it's a member of this interface."

Yes, this is I think the most innovative aspect of Go interfaces, and one of Go's best features. It's duck typing in a statically type-checked language. It avoids Java's problem of tagging classes with long lists of interfaces that they implement.

Well, from what I understand, Go has a separation between "interface" and "implementation", correct?

Given the above property there isn't really an implementation anymore. Individual types just have to implement the right functions, but that isn't really a blob of code to implement any single interface.

http://www.airs.com/blog/archives/277

-----