2 ms·
Once upon a time, I wanted to back a stack with a linked list in Python. I had been reading a lot of compiled bytecode, and had recently learned that CPython i
by boothby 11mo ago
Once upon a time, I wanted to back a stack with a linked list in Python. I had been reading a lot of compiled bytecode, and had recently learned that CPython is a stack-based language capable of unrolling and popping tuples as singular bytecode instructions. I also learned about the freelist.
I ended up with the notation
Initialization:
head = ()
Push:
head = data, head
Safe Pop:
if head:
data, head = head
Safe Top:
head[0] if head else None
And for many stack-based algorithms, I've found this to be quite optimal in part because the length-2 tuples get recycled (also due to a lack of function calls, member accesses, etc). But I'm rather embarrassed to put it into a codebase due to others' expectations that Python should be beautiful and this seems weird.
- plant-ian 11mo agoI guess the only downside might be if you need to push a bunch of things at once. But maybe just a loop is faster than calling extend on a list? This is cool.
- boothby 11mo agoYep, that's the main exception when I said "many stack-based algorithms". It's worth mentioning that examining the stack while debugging is annoying because of the number of parens involved.
- Asooka 11mo agoIf you can afford a function call, you can just borrow LISP's names for these functions, as these are literally LISP lists, e.g.: def cons(head, tail=()): return (head, tail) def snoc(pair): ''' Decompose (kind of) pair, transforming () to None, (). So you can write slightly clearer code: pair = cons(head, tail) head, tail = snoc(pair) ''' if pair: return pair else: return (None, ()) def car(pair): return pair[0] if pair else None def cdr(pair): return pair[1] if pair else () def cons_iter(stack): ''' Iterate stack, e.g. for item in cons_iter(stack): ... ''' while stack: head, stack = stack yield head May you write much LISP in Python.
- boothby 11mo agoWell part of the point is that I detest the function call overhead of CPython but yes what I described is precisely how lispers roll their linked lists! And several years later I am writing about as much lisp as I am Python (and making people's eyes bleed with macros and functional approaches to problems if I let my worst instincts take over, but alas)