How to implement recursive types?

[capr]

Hi!
Consider the following:

local Node = terralib.newstruct()
Node.entries = {{'children', dynamic_array(Node)}}

Let's say that Node has a special requirement to know the size of its fields in order to complete its layout (eg. it might want to reorder them to pack them better). Calling sizeof() on the types of the fields triggers their completion. Now, dynamic_array(Node) has no problem with completing itself on a type that isn't complete (i.e. its struct layout is independent of sizeof(Node)). However, dynamic_array(Node) also needs to create methods on its resulting type and those methods do need to call sizeof(Node), but it cannot create those methods in __staticinitialize because Node is not complete yet (remember, we're in Node.__getentries at this point and we're trying to get sizeof(each field)).

Looks like eager typechecking strikes again :) Any ideas on how to solve this appreciated. Thanks!

PS: In case it's not clear, dynamic_array(T) is a Lua function that returns a new Terra type that models a dynamically-allocated array of T.

[elliottslaughter]

Could you make the offending methods of dynamic_array be macros, or model them with __methodmissing? Otherwise you'd have to split the dynamic_array factory into two parts, one which defines the type, and one which defines the methods.

[capr]

I think __methodmissing could work, I've used it before to defeat the eager type-checking dragon :) So basically the lesson here is "always define containers lazily through __methodmissing".

[capr]

doesn't that kinda defeats the purpose of eager typechecking though?

Btw, can you elaborate a bit on why is it that macros couldn't get the type of their arguments with lazy typechecking? I mean what prevents quote:gettype() to trigger a typechecking cascade just like sizeof(T) triggers a completion cascade?

[elliottslaughter]

In the original version of lazy type checking, symbols were untyped. So while it wasn't generally recommended, you could do things like:

local x = terralib.newsymbol("x")
local x_plus_1 = `(x + 1)

terra f()
  var [x] = 1 -- x is an int
  return [x_plus_1]
end

terra g()
  var [x] = 3.14 -- x is a double
  return [x_plus_1]
end

What is the type of x? It depends entirely on the context where the quote is spliced, and it can actually be different in different places. This means that quotations in general can't be typed without being in the context of a specific function. You can work around this in certain cases, but my understanding is that there were edge cases where that would just fail, and it wasn't always obvious to users why.

There was also some implementation complexity with keeping a stack of functions to be compiled (remember: mutual recursion), but I believe this is just an implementation detail and shouldn't have any user-visible implications.

I think if we were going to go back to more lazy typechecking, it would be an explicit goal to avoid any API changes, so that symbols would still be typed, and therefore it would be possible to type check quotes just by cascading the type checking on any not-yet-type-checked functions, like you describe.

[capr]

I see, thanks for the info as always. I ended up adding all methods in the first call to __getmethod().