Deferred Evaluation in Recursive Expressions?

[Peter Otten]

birchb at ozemail.com.au wrote:

> While working on type expressions I am rather stuck for a
> way to express recursive types.  A simple example of this is a
> singly-linked list of integers. In some languages you have compiler
> syntax
> which suspends evaluation so you can have recursive types. e.g.
> 
>    typedef Linked_List := int, Linked_List
> 
> In LISP I would use a macro.
> 
> I have tried using classes:
> 
>    class Linked_List(object):
>          typedef = (int, Linked_List)
> 
> The closest I have got in Python is the following:
> 
>    Linked_List = (int, lambda: Linked_List)      # linked list of int
> 
> this is OK, because lambda makes closure which is not executed. However
> it required the user of the type expression to call any lfunctions
> found whilst traversing the tree.
> 
> To make this a little more OO, I could use a constructor to wrap the
> function:
> 
>    Linked_List = (int, recursive(lambda: Linked_List))      # linked
> list of int
> 
> but I am not satisfied with the "look".
> 
> Any suggestions?

(1) Wait until the class is defined:

class LinkedList: pass
LinkedList.typedef = int, LinkedList

or 

(2) Use a marker object as a placeholder for the class yet to be defined.
Fancy example:

SELF = object()

def fix_typedef(td, cls):
    for item in td:
        if item is SELF:
            yield cls
        else:
            yield item

class Type(type):
    def __new__(*args):
        cls = type.__new__(*args)
        try:
            typedef = cls.typedef
        except AttributeError:
            pass
        else:
            cls.typedef = tuple(fix_typedef(typedef, cls))
        return cls

class TypeDef:
    __metaclass__ = Type

class LinkedList(TypeDef):
    typedef = (int, SELF)

print LinkedList.typedef
# (<type 'int'>, <class '__main__.LinkedList'>)