Leaf

Adding the first type expression to Leaf: type_infer

I’ve added the ability to type a variable based on an expression. The type_infer type operator resolves to the type of the provided expression — a useful feature for parametrics. Though not a challenging feature to implement it did introduce a new twist to the parsing.

1
2
var a : type_infer(1+2)  //a is `integer`
var b : type_infer(a) //b is `integer`

In parametrics

type_infer has a variety of uses but it is primarily useful when working with parametric functions and classes. The basic scenario is to create a variable of the same type as a parameter:

1
2
3
4
defn pine = (x)-> {
    var y : type_infer(x)
    ...
}

The type of y is the same as is we had written var y = x, but it gets default initialized here rather than doing the actual assignment. This is why the operator is called type_infer: it determines the type the same way as the type inference during assignment does.

type_infer doesn’t have the exact same type as the expression it contains due to the inference. This is usually desired. For the cases where the exact type is desired a separate type_exact will be introduced.

Implementation

I primarily had to modify the parser to get this feature working. Detecting the type_infer part is obviously easy. I also already had code to parse an expression. The interesting bit is that there is no such thing as a pure type anymore. Any type can include an arbitrary expression, thus creating a link both ways between the parsers and the data structures.

Determining the type also required that the typing code can evaluate expressions, creating another two-way link between the code. It’s more of conceptual oddity than actual technical problem: the implementation is simply calling a function that processes the expression.

The typing system already knew about the compilation context. It needed that resolve the member and context(...) type identifiers for classes. If this were not already in place it would have been a lot more work to get type_infer working.

There’s a small limitation here now: the expression is compiled as though it will actually be used. This was the simplest way to implement it, but it can have side-effects. In particular, symbols referenced in this expression can actually be pulled into the current context (captured in a closure), thus changing the resulting memory structure. While this shouldn’t have any impact on the high-level semantics, it is a performance issue that needs to be addressed at some point.

Categories: Leaf

Tagged as: , , ,

5 replies »

  1. I am sorry for obvious question, but Leaf is dynamically typed language, correct? Because otherwise (i.e. in statically typed language), any `foo(expr T)` would have that type right away as `T`.

    • It’s a statically typed language.

      The addition is for the function body to be able to refer to type with which it is instantiated.

      Classes have the classic notation for explicit instantiation, as will functions eventually, but in the common case they don’t have formal type arguments. In this example you can see it’s simply the lack of a type argument that denotes it as a parametric function.

    • @ mortoray, the comment engine stripped angle brackets in my example, there is generic type parameter `T` after `foo`. So, why you cannot use `T`? I somehow cannot see a clear example where it is really needed. What I know it is needed is strong and weak `typedef` (similar to C++ one). Maybe I am simply slow :-)

    • There are a couple of reasons why you use `type_infer`:

      – Leaf parametric functions, as in the article, don’t require an explicit parameter name. `(x)-> {` is enough to get a parametric function. There is no `T` to refer to here.
      – Even if you had an explicit name you often don’t want that type explicitly, but truly the result of some operation: `var a : type_infer( random_transform_func( T() ) )`
      – `type_infer` can also be used in non-parametric contexts. It’s not a very common need, but it’s come up a few times for me in C++ where I just want one variable to match that of another auto-typed variable.

  2. @macias I thought it might be worth mentioning that Leaf is indeed statically typed. However probably its biggest selling feature at least as I see it is the advanced type inference system that mortoray has custom developed for the compiler. You should therefore not need to specify the type in declarations unless it cannot be inferred. Maybe that’s obvious but I thought I’d mention it for clarity.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s