Chapter 7: Signatures and Structures

Where types and values collide.

You endured all that tedious talk about types; but it wasn't for nothing.

Now, you'll see types in action, as they take a new shape... and a new purpose.

Many programming languages have some kind of module system or polymorphism system.

You know what I'm talking about.

Object-oriented languages have classes with methods that can be overriden by their subclasses. The moment you call one of those methods on an object, the run-time system selects for you the correct implementation, based on the class hierarchy.

Or maybe you come from Haskell, where they have type-classes, that basically perform the same process, but during compilation. Types are checked, instances get picked, and the proper functions and constants get plugged-in.

Or may, you come from the world of ML (specially Standard ML), where they have a module system based on... (drumroll, please) signatures and structures. In those systems, the function implementations you want don't get selected for you automatically (you have to pick them yourself), but you tend to have more control when it comes to choosing what to use.

OK. Now you know the origin of Lux's module system. I... um... borrowed it from the SML guys.

But I added my own little twist.

You see, module/polymorphism systems in programming languages tend to live in a mysterious world that is removed from the rest of the language. It's a similar situation as with types.

Remember Lux's type system? Most languages keep their types separate from their values. Types are just some cute annotations you put in your code to keep the compiler happy. Lux's types, on the other hand, are alive; for they are values. Nothing stops you from using them, transforming them and analyzing them in ways that go beyond the language designer's imagination (that would be me).

Well, there's a similar story to tell about module/polymorphism systems. The run-time/compiler chooses everything for you; and even when you choose for yourself, you're still somewhat limited in what you can do. Modules are not values, and there is a fundamental division between them and the rest of the language.

But not in Lux.

Lux's module system is actually based on regular types and values. And because type are values, that means it's just turtles values all the way down.

But, how does it work?

Read on!

Signatures

Signatures are like interfaces in other programming languages. They provide a description of the functionality expected of proper implementations. They have a list of expected member values/functions, with their associated types.

Here's an example:

(sig: #export (Ord a)
  (: (Eq a)
     eq)

  (: (-> a a Bool)
     <)

  (: (-> a a Bool)
     <=)

  (: (-> a a Bool)
     >)

  (: (-> a a Bool)
     >=))

That signature definition comes from the lux/control/ord module, and it deals with ordered types; that is, types for which you can compare their values in ways that imply some sort of sequential order.

It's polymorphic/parameterized because this signature must be able to adapt to any type that fits its requirements.

Also, you may notice that it has a member called eq, of type (Eq a). The reason is that signatures can expand upon (or be based on) other signatures (such as Eq).

How do signatures differ from types?

They don't. They're actually implemented as types. Specifically, as record/tuple types.

You see, if I can create a record type with one field for every expected definition in a signature, then that's all I need.

Structures

They are the other side of the coin.

If signatures are record types, then that means structures must be actual records.

Let's take a look at how you make one:

(struct: #export Ord<Real> (ord;Ord Real)
  (def: eq Eq<Real>)
  (def: < r.<)
  (def: <= r.<=)
  (def: > r.>)
  (def: >= r.>=))

This structure comes from lux/data/number.

As you may notice, structures have names; unlike in object-oriented languages where the "structure" would just be the implemented methods of a class, or Haskell where instances are anonymous.

Also, the convention is Name-of-Signature<Name-of-Type>.

(struct: #export Monoid<List> (All [a]
                                (Monoid (List a)))
  (def: unit #;Nil)
  (def: (append xs ys)
    (case xs
      #;Nil          ys
      (#;Cons x xs') (#;Cons x (append xs' ys)))))

Here is another example, from the lux/data/struct/list module.

The reason why structures have names (besides the fact that they are definitions like any other), is that you can actually construct multiple valid structures for the same combination of signatures and parameter types. That would require you to distinguish each structure in some way in order to use it. This is one cool advantage over Haskell's type-classes and instances, where you can only have one instance for any combination of type-class and parameter.

Haskellers often resort to "hacks" such as using newtype to try to get around this limitation.

The upside of having the run-time/compiler pick the implementation for you is that you can avoid some boilerplate when writing polymorphic code.

The upside of picking the implementation yourself is that you get more control and predictability over what's happening (which is specially cool when you consider that structures are first-class values).

What's the big importance of structures being first-class values? Simple: it means you can create your own structures at run-time based on arbitrary data and logic, and you can combine and transform structures however you want.

Standard ML offers something like that by a mechanism they call "functors" (unrelated to a concept of "functor" we'll see in a later chapter), but they are more like magical functions that the compiler uses to combine structures in limited ways.

In Lux, we dispense with the formalities and just use regular old functions and values to get the job done.

How to use structures

We've put functions and values inside our structures.

It's time to get them out and use them.

There are 2 main ways to use the stuff inside your structures: open and ::. Let's check them out.

## Opens a structure and generates a definition for each of its members (including nested members).
## For example:
(open Number<Int> "i:")
## Will generate:
(def: i:+ (:: Number<Int> +))
(def: i:- (:: Number<Int> -))
(def: i:* (:: Number<Int> *))
## ...

The open macro serves as a statement that creates private/un-exported definitions in your module for every member of a particular structure. You may also give it an optional prefix for the definitions, in case you want to avoid any name clash.

You might want to check out Appendix C to discover a pattern-matching macro version of open called ^open.

## Allows accessing the value of a structure's member.
(:: Codec<Text,Int> encode)

## Also allows using that value as a function.
(:: Codec<Text,Int> encode 123)

:: is for when you want to use individual parts of a structure immediately in your code, instead of opening them first.

Psss! Did you notice :: is piping enabled?

Also, you don't really need to worry about boilerplate related to using structures. There is a module called lux/type/auto which gives you a macro called ::: for using structures without actually specifying which one you need.

The macro infers everything for you based on the types of the arguments, the expected return-type of the expression, and the structures available in the environment.

For more information about that, head over to Appendix F to read more about that.

Structures as Values

I can't emphasize enough that structures are values. And to exemplify it for you, here's a function from the lux/control/monad module that takes in a structure (among other things) and uses it within it's code:

(def: #export (mapM monad f xs)
  (All [M a b]
    (-> (Monad M) (-> a (M b)) (List a) (M (List b))))
  (case xs
    #;Nil
    (:: monad wrap #;Nil)

    (#;Cons x xs')
    (do monad
      [_x (f x)
       _xs (mapM monad f xs')]
      (wrap (#;Cons _x _xs)))
    ))

Monad is a signature and the mapM function take arbitrary structures that implement it and can work with any of them without an issue.

Signatures and structure are the main mechanism for writing polymorphic code in Lux, and they allow flexible and precise selection of implementations.

It may be the case that in the future Lux adds new mechanisms for achieving the same goals (I believe in having variety), but the spirit of implementing things in terms of accessible values anybody can manipulate will likely underlie every such mechanism.

Now that we've discussed signatures and structures, it's time to talk about a very special family of signatures.

See you in the next chapter!