469,613 Members | 1,274 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,613 developers. It's quick & easy.

Deferred Evaluation in Recursive Expressions?

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 10 '06 #1
8 1716
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
May 10 '06 #2
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'>)

May 10 '06 #3
How about mutual recursion?

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

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

May 10 '06 #4
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
May 10 '06 #5
The first 'typedef' line will have a NameError when it tries to
evaluate LinkedListB

May 10 '06 #6
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 '06 #7
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 '06 #8
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
May 10 '06 #9

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

8 posts views Thread by der | last post: by
2 posts views Thread by webposter | last post: by
21 posts views Thread by dragoncoder | last post: by
77 posts views Thread by berns | last post: by
9 posts views Thread by sturlamolden | last post: by
54 posts views Thread by Rasjid | last post: by
11 posts views Thread by Pietro Cerutti | last post: by
reply views Thread by devrayhaan | last post: by
reply views Thread by gheharukoh7 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.