Deferred Evaluation in Recursive Expressions?

[birchb]

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?

[Diez B. Roggisch]

bi****@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?

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]

bi****@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'>)

[birchb]

How about mutual recursion?

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

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

[Peter Otten]

bi****@ozemail.com.au 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

[Lonnie Princehouse]

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

[birchb]

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)

[birchb]

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]

bi****@ozemail.com.au 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