RE: mutually-recursive types and an old puzzle

[Chris Lattner <sabre at nondot dot org>]

Joe Buck wrote:

> OK, here's the problem: how should we define T?  It seems that T must be
> the same type as "pointer to function returning T" (this was the K&R
> days, where you could ignore the type of the argument list, but that
> doesn't really change the puzzle any).  That is,
...
> It's a recursive type, and so cannot be declared in C.  As I recall,
> people proposed various workarounds that relied on casts to allow this
> sort of coding style.

> Now, to try to make this little distraction relevant:
> 1) can this kind of thing be represented in Ada?
> 2) can this kind of thing be represented in GIMPLE?

Not that anyone necessarily cares, but this is directly implementable in
LLVM.  Here's a trivial .ll testcase:

;; T is a pointer to a function that takes an int as an argument and
;; returns a T.
%T = type %T (int)*

implementation

;;; Foo is a function that take an int and returns a T
%T %foo(int) {
        ret %T %foo    ;; return the address of foo
}

As you can see, our type-system is more generic than C's (you can even
define a pointer to a pointer to a pointer...

If you delete the "T" entry from the symbol table, you get an exactly
similar, and more telling view of the LLVM type system:

\2 (int)* %foo(int) {
        ret \2 (int)* %foo
}


That probably looks like greek to everyone, but the basic idea is very
simple.  An upreference just refers to some # of containing type.  A
pointer to pointer to pointer could be named as "\1 *", for example.
A linked list of integers might be "{ \2, int}*".

Anyway, just possibly interesting trivia for ya all.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/