Deferred Evaluation in Recursive Expressions?

[birchb@ozemail.com.au]

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(obj ect):
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(lambd a: Linked_List)) # linked
list of int

but I am not satisfied with the "look".

Any suggestions?

[Diez B. Roggisch]

Re: Deferred Evaluation in Recursive Expressions?

birchb@ozemail. com.au wrote:
[color=blue]
> 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(obj ect):
> 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(lambd a: Linked_List)) # linked
> list of int
>
> but I am not satisfied with the "look".
>
> Any suggestions?[/color]

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

[Peter Otten]

Re: Deferred Evaluation in Recursive Expressions?

birchb@ozemail. com.au wrote:
[color=blue]
> 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(obj ect):
> 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(lambd a: Linked_List)) # linked
> list of int
>
> but I am not satisfied with the "look".
>
> Any suggestions?[/color]

(1) Wait until the class is defined:

class LinkedList: pass
LinkedList.type def = 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__(*a rgs)
try:
typedef = cls.typedef
except AttributeError:
pass
else:
cls.typedef = tuple(fix_typed ef(typedef, cls))
return cls

class TypeDef:
__metaclass__ = Type

class LinkedList(Type Def):
typedef = (int, SELF)

print LinkedList.type def
# (<type 'int'>, <class '__main__.Linke dList'>)

[birchb@ozemail.com.au]

Re: Deferred Evaluation in Recursive Expressions?

How about mutual recursion?

class LinkedListA(Typ eDef):
typedef = (int, LinkedListB)

class LinkedListB(Typ eDef):
typedef = (int, LinkedListA)

[Peter Otten]

Re: Deferred Evaluation in Recursive Expressions?

birchb@ozemail. com.au wrote:
[color=blue]
> How about mutual recursion?
>
> class LinkedListA(Typ eDef):
> typedef = (int, LinkedListB)
>
> class LinkedListB(Typ eDef):
> typedef = (int, LinkedListA)[/color]

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("typed ef", ())
cls = type.__new__(mc l, 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_ty pedef, set_typedef)

class TypeDef:
__metaclass__ = Type

class LinkedListA(Typ eDef):
typedef = (int, types.LinkedLis tB)

class LinkedListB(Typ eDef):
typedef = (int, types.LinkedLis tA)

print LinkedListA.typ edef
print LinkedListB.typ edef

I'm sure it will break down somewhere :-)

Peter

[Lonnie Princehouse]

Re: Deferred Evaluation in Recursive Expressions?

The first 'typedef' line will have a NameError when it tries to
evaluate LinkedListB

[birchb@ozemail.com.au]

Re: Deferred Evaluation in Recursive Expressions?

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 makeAnonymousRe cursiveType(T):
# anonymous type expression with local scope
LinkedList = (T, lambda: LinkedList)
return LinkedList

local = makeAnonymousRe cursiveType(int )

[birchb@ozemail.com.au]

Re: Deferred Evaluation in Recursive Expressions?

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?

[Peter Otten]

Re: Deferred Evaluation in Recursive Expressions?

birchb@ozemail. com.au wrote:
[color=blue]
> 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 makeAnonymousRe cursiveType(T):
> # anonymous type expression with local scope
> LinkedList = (T, lambda: LinkedList)
> return LinkedList
>
> local = makeAnonymousRe cursiveType(int )[/color]

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("typed ef", ())
cls = type.__new__(mc l, name, bases, dict)
cls.all[name] = cls
return cls
def get_typedef(cls ):
def get(item):
result = cls.all.get(ite m)
if result is None:
result = type(cls).all.g et(item, item)
return result
return tuple(get(item) for item in cls._typedef)
def set_typedef(cls , value):
cls._typedef = value
typedef = property(get_ty pedef, set_typedef)

class TypeDef:
__metaclass__ = Type

class LinkedListA(Typ eDef):
typedef = (int, types.LinkedLis tB)

class LinkedListB(Typ eDef):
typedef = (int, types.LinkedLis tA)

print LinkedListA.typ edef
print LinkedListB.typ edef
print LinkedListA.typ edef

def LocalTypeDef():
class LocalTypeDef(Ty peDef):
all = {}
return LocalTypeDef

def makeAnonymousRe cursiveType(T):
class LinkedList(Loca lTypeDef()):
typedef = (T, types.LinkedLis t)
return LinkedList

print makeAnonymousRe cursiveType(int ).typedef
print makeAnonymousRe cursiveType(str ).typedef

Go with lambda, I'd say...

Peter