473,695 Members | 2,405 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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

May 10 '06 #1
8 1914
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(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?


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


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

May 10 '06 #3
How about mutual recursion?

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

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

May 10 '06 #4
bi****@ozemail. com.au wrote:
How about mutual recursion?

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

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

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

local = makeAnonymousRe cursiveType(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("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
May 10 '06 #9

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

8
3346
by: der | last post by:
Hello all, I've a question about order of evaluations in expressions that have && and || operators in them. The question is: will the evalution go left-to-right, no matter what -- even if the || operator is before the && operator? e,g, In an expression like a = (z>x) || (x<0) && (z-y>9); is it guaranteed that z>x will be checked first?
2
4120
by: webposter | last post by:
Hi, I am looking for information on a data structure (and associated algorithm) to do short-circuit evaluation of boolean expressions and haven't found a single one even after googing for two days! Can anyone point me to good resources (or implementations) that do this. Basically is there any way to optimize a boolean expression expressed in RPN (reverse polish notation)? I want to implement the algorithm/data structure in C. If you...
2
4282
by: Jeffrey Ganping Chen | last post by:
I'm trying to build a generic runtime C# expression evaluation engine to allow the user to evaluate any C# code blocks at runtime within the application's context. For example, obj4.p4 = obj1.m1() + obj2.m2(p1, p2) - Class3.m3() or if (obj1.p1 > obj2.m2()) {
21
4116
by: dragoncoder | last post by:
Consider the following code. #include <stdio.h> int main() { int i =1; printf("%d ,%d ,%d\n",i,++i,i++); return 0; }
77
4718
by: berns | last post by:
Hi All, A coworker and I have been debating the 'correct' expectation of evaluation for the phrase a = b = c. Two different versions of GCC ended up compiling this as b = c; a = b and the other ended up compiling it as a = c; b = c. (Both with no optimizations enabled). How did we notice you may ask? Well, in our case 'b' was a memory mapped register that only has a select number of writable bits. He claims it has been a 'C...
9
3508
by: sturlamolden | last post by:
Python allows the binding behaviour to be defined for descriptors, using the __set__ and __get__ methods. I think it would be a major advantage if this could be generalized to any object, by allowing the assignment operator (=) to be overloaded. One particular use for this would be to implement "lazy evaluation". For example it would allow us to get rid of all the temporary arrays produced by NumPy. For example, consider the...
32
3306
by: silpau | last post by:
hi, i am a bit confused on expression evaluation order in expressions involving unary increment.decrement operators along with binary operators. For example in the following expression x += i + j + k++;
54
3920
by: Rasjid | last post by:
Hello, I have just joined and this is my first post. I have never been able to resolve the issue of order of evaluation in C/C++ and the related issue of precedence of operators, use of parentheses. 1) "The order of evaluation of subexpressions is determined by the precedence and grouping of operators."
11
1665
by: Pietro Cerutti | last post by:
Hi group, here I come with a question which is quite simple per se, but for which I can't find an answer. Does the C standard guarantee that inside an expression such as (x && y) "y" is not evaluated if "x" evaluates to 0?
0
8649
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9004
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
8864
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
1
6506
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
5842
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4351
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
1
3025
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2289
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
1986
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.