Deferred Evaluation in Recursive Expressions?

B

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?
 
D

Diez B. Roggisch

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
 
P

Peter Otten

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'>)
 
B

birchb

How about mutual recursion?

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

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

Peter Otten

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
 
L

Lonnie Princehouse

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

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)
 
B

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?
 
P

Peter Otten

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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top