Deferred Evaluation in Recursive Expressions?

Discussion in 'Python' started by birchb@ozemail.com.au, May 9, 2006.

  1. Guest

    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?
     
    , May 9, 2006
    #1
    1. Advertising

  2. 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?


    If you are after lazy evaluation: no - there is no chance python will grow
    that (Well, maybe there is some PEP out there - but if, it weould be for
    Py3K)

    The natural approach for your actual example though would be a generator.
    Which, when used in for .. in .. even looks natural to the eye:

    def squares():
    c = 1
    while True:
    yield c ** 2

    for n in squares():
    ... # do something fancy


    Diez
     
    Diez B. Roggisch, May 9, 2006
    #2
    1. Advertising

  3. Peter Otten Guest

    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'>)
     
    Peter Otten, May 9, 2006
    #3
  4. Guest

    How about mutual recursion?

    class LinkedListA(TypeDef):
    typedef = (int, LinkedListB)

    class LinkedListB(TypeDef):
    typedef = (int, LinkedListA)
     
    , May 9, 2006
    #4
  5. Peter Otten Guest

    wrote:

    > How about mutual recursion?
    >
    > class LinkedListA(TypeDef):
    > typedef = (int, LinkedListB)
    >
    > class LinkedListB(TypeDef):
    > typedef = (int, LinkedListA)


    class Names(object):
    def __getattribute__(self, name):
    return name

    types = Names()

    class Type(type):
    all = {}
    def __new__(mcl, name, bases, dict):
    assert name not in mcl.all, "name clash"
    assert "_typedef" not in dict
    dict["_typedef"] = dict.pop("typedef", ())
    cls = type.__new__(mcl, name, bases, dict)
    mcl.all[name] = cls
    return cls

    def get_typedef(cls):
    get = cls.all.get
    return tuple(get(item, item) for item in cls._typedef)
    def set_typedef(cls, value):
    cls._typedef = value
    typedef = property(get_typedef, set_typedef)

    class TypeDef:
    __metaclass__ = Type

    class LinkedListA(TypeDef):
    typedef = (int, types.LinkedListB)

    class LinkedListB(TypeDef):
    typedef = (int, types.LinkedListA)

    print LinkedListA.typedef
    print LinkedListB.typedef

    I'm sure it will break down somewhere :)

    Peter
     
    Peter Otten, May 9, 2006
    #5
  6. The first 'typedef' line will have a NameError when it tries to
    evaluate LinkedListB
     
    Lonnie Princehouse, May 9, 2006
    #6
  7. Guest

    That's a good fix. But I have misgivngs about needing a global name
    registry. I need to support anonymous types and types with local
    (lexical) scope. For example:

    def makeAnonymousRecursiveType(T):
    # anonymous type expression with local scope
    LinkedList = (T, lambda: LinkedList)
    return LinkedList

    local = makeAnonymousRecursiveType(int)
     
    , May 10, 2006
    #7
  8. Guest

    If we -are- limited to lambdas, I see two options. Either embed lambdas
    for each circular link, or have the whole expression in one lambda. ie

    LinkedList3 = (int, lambda: LinkedList3, lambda: TypeNameX)

    vs

    LinkedList2 = lambda: (int, LinkedList2, TypeNameX)

    The second option looks neater. Maybe both are OK?
     
    , May 10, 2006
    #8
  9. Peter Otten Guest

    wrote:

    > That's a good fix. But I have misgivngs about needing a global name
    > registry. I need to support anonymous types and types with local
    > (lexical) scope. For example:
    >
    > def makeAnonymousRecursiveType(T):
    > # anonymous type expression with local scope
    > LinkedList = (T, lambda: LinkedList)
    > return LinkedList
    >
    > local = makeAnonymousRecursiveType(int)


    class Names(object):
    def __getattribute__(self, name):
    return name

    types = Names()

    class Type(type):
    all = {}
    def __new__(mcl, name, bases, dict):
    assert "_typedef" not in dict
    dict["_typedef"] = dict.pop("typedef", ())
    cls = type.__new__(mcl, name, bases, dict)
    cls.all[name] = cls
    return cls
    def get_typedef(cls):
    def get(item):
    result = cls.all.get(item)
    if result is None:
    result = type(cls).all.get(item, item)
    return result
    return tuple(get(item) for item in cls._typedef)
    def set_typedef(cls, value):
    cls._typedef = value
    typedef = property(get_typedef, set_typedef)

    class TypeDef:
    __metaclass__ = Type

    class LinkedListA(TypeDef):
    typedef = (int, types.LinkedListB)

    class LinkedListB(TypeDef):
    typedef = (int, types.LinkedListA)

    print LinkedListA.typedef
    print LinkedListB.typedef
    print LinkedListA.typedef

    def LocalTypeDef():
    class LocalTypeDef(TypeDef):
    all = {}
    return LocalTypeDef

    def makeAnonymousRecursiveType(T):
    class LinkedList(LocalTypeDef()):
    typedef = (T, types.LinkedList)
    return LinkedList

    print makeAnonymousRecursiveType(int).typedef
    print makeAnonymousRecursiveType(str).typedef

    Go with lambda, I'd say...

    Peter
     
    Peter Otten, May 10, 2006
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Noah
    Replies:
    5
    Views:
    970
  2. Ilias Lazaridis
    Replies:
    2
    Views:
    398
    Ilias Lazaridis
    Apr 24, 2005
  3. Ilias Lazaridis
    Replies:
    74
    Views:
    780
    Ilias Lazaridis
    Apr 4, 2005
  4. Ilias Lazaridis
    Replies:
    18
    Views:
    355
    Bill Guindon
    Apr 9, 2005
  5. Replies:
    6
    Views:
    214
    Thomas 'PointedEars' Lahn
    Feb 22, 2006
Loading...

Share This Page