call/cc in Python — Possible?

Question

Say, we have the following code in Scheme

(define cc #f)
(define bar 0)

(define (func)
  (print "This should show only once")
  (call/cc (lambda (k) (set! cc k)))
  (print bar)
  (set! bar (+ bar 1)))

(define (g)
  (func)
  (print "This should show multiple times"))

(g)
(cc)

which prints something like

This should show only once
0
This should show multiple times
1
This should show multiple times

And suppose we want to do the same in Python. http://wiki.c2.com/?ContinuationsInPython this approach doesn't work, because they save only the code and not the stack. I've tried to implement my version of call/cc in Python, saving and restoring the stack context. I'm not 100% sure that I've implemented continuations logics correctly, but this is not important now.

My idea is to save stack and instruction pointers of the function invoking callcc and its callers in Continuation constructor and then, in continuation's __call__ method, reset the instruction pointers in the saved stack frames, point the current stack frame f_back pointer to the saved stack frame and return to magically appear in the function which called callcc.

The problem is that even though the output of the traceback.print_stack() shows that the current stack has been replaced, the code is still executes as if I haven't touched the current stack at all. Here is my implementation https://ideone.com/kGchEm

import inspect
import types
import ctypes
import sys
import traceback


frameobject_fields = [
    # PyObject_VAR_HEAD
    ("ob_refcnt", ctypes.c_int64),
    ("ob_type", ctypes.py_object),
    ("ob_size", ctypes.c_ssize_t),
    # struct _frame *f_back;      /* previous frame, or NULL */
    ("f_back", ctypes.c_void_p),
    # PyCodeObject *f_code;       /* code segment */
    ("f_code", ctypes.c_void_p),
    # PyObject *f_builtins;       /* builtin symbol table (PyDictObject) */
    ("f_builtins", ctypes.py_object),
    # PyObject *f_globals;        /* global symbol table (PyDictObject) */
    ("f_globals", ctypes.py_object),
    ####
    ("f_locals", ctypes.py_object),
    ("f_valuestack", ctypes.POINTER(ctypes.py_object)),
    ("f_stacktop", ctypes.POINTER(ctypes.py_object)),
    ("f_trace", ctypes.py_object),
    ("f_exc_type", ctypes.py_object),
    ("f_exc_value", ctypes.py_object),
    ("f_exc_traceback", ctypes.py_object),
    ("f_tstate", ctypes.c_void_p),
    ("f_lasti", ctypes.c_int),
]
if hasattr(sys, "getobjects"):
    # This python was compiled with debugging enabled.
    frameobject_fields = [
        ("_ob_next", ctypes.c_void_p),
        ("_ob_prev", ctypes.c_void_p),
    ] + frameobject_fields
class PyFrameObject(ctypes.Structure):
    _fields_ = frameobject_fields


class Continuation:
    def __init__(self, frame):
        self.frame = frame
        self.lasti = frame.f_lasti
        self.lastis = []

        frame = frame.f_back
        while frame is not None:
            self.lastis.append(frame.f_lasti)
            frame = frame.f_back

    def __call__(self):
        print('\nbefore')
        traceback.print_stack()

        cur_frame = PyFrameObject.from_address(id(inspect.currentframe()))
        PyFrameObject.from_address(cur_frame.f_back).ob_refcnt -= 1
        cur_frame.f_back = id(self.frame)
        PyFrameObject.from_address(id(self.frame)).ob_refcnt += 1

        frame = self.frame
        _frame = PyFrameObject.from_address(id(frame))
        _frame.f_lasti = self.lasti + 4

        frame = frame.f_back
        for lasti in self.lastis:
            if len(frame.f_code.co_code) != frame.f_lasti + 2:
                break
            _frame = PyFrameObject.from_address(id(frame))
            _frame.f_lasti = lasti + 4
            frame = frame.f_back

        print('\nafter')
        traceback.print_stack()


def callcc(f):
    f(Continuation(inspect.currentframe().f_back))


cc = None


def func():
    bar = 0
    print("This should show only once")
    def save_cont(k):
        global cc
        cc = k
    callcc(save_cont)
    print(bar)
    bar += 1


def g():
    func()
    print("This should show multiple times")

sys.stderr = sys.stdout
g()
cc()

isn't a generator an abstract type of continuation? It nominally tracks/saves the state of the stack after each yield... — cowbert, Jan 30 '18 at 17:09
@cowbert man, if I wanted to use `yield`, I would have used `yield`. — Current Continuation, Jan 30 '18 at 17:18
I'm finding it hard to understand _why_ you want to do this, and not use a generator. With as little offence as possible, you're writing terrible Python. A resumable function is a generator is a resumable function. Don't reinvent the wheel. — Adam Barnes, Jan 30 '18 at 17:28
But again, _why_? "The whole stack" is something you should _never_ be thinking about in Python. It's an implementation detail that is purposefully out of reach. — Adam Barnes, Jan 30 '18 at 17:29
@AdamBarnes call/cc is more general than generator. For example, how do you implement [amb operator](https://www.rosettacode.org/wiki/Amb) — Xwtek, May 03 '20 at 12:51
@Akangka imperatively. This is Python. We write simple clear code, not magic that makes us feel incredibly clever. — Adam Barnes, May 04 '20 at 17:05
@AdamBarnes "We write simple clear code" Simple clear code is in the eye of the beholder. For example, writing a C code and linking to Python via FFI may disqualify, and yet It's important for the implementation of a library like NumPy. Call/cc is not something you use to make an application. However, it's important for building a continuation-based web framework, for example. — Xwtek, May 04 '20 at 23:01
A widely used, successful, Pythonic web framework is Django. I write code like Django's source every day I'm at work. I look at Django's source about as much as I look at its documentation. I am not fired for writing unreadable "look how clever I am" code such as what appears in the OP. It follows that there may be some connection between that, and the lack of a "continuation-based web framework" competitor to Django. — Adam Barnes, May 06 '20 at 00:07
As Akangka pointed out, continuations can be used for many purposes such as implementing backtracking, a web-server or multitasking. They are also a useful device for doing programming language research. — ftl, May 06 '20 at 14:55
People write code for various reasons such as exploring what a computer (and/or) language can do for them. Not all programming is required to have a useful outcome or even a specific goal. I highly recommend that you try [Seaside](http://www.seaside.st/) if you haven't done so. It will broaden your horizon. — ftl, May 06 '20 at 15:05

score 4 · Accepted Answer · answered Jan 31 '18 at 01:05

The problem is that the standard interpreter — CPython — is a stackful interpreter, i.e. every invocation of Python function results in recursive call inside the interpreter. So the Python FrameType objects are just views (.f_back is a read-only attribute for the good reason) of the C stack frames, there is no point to change the f_back pointer.

If you really want to manipulate the stack, you will have to write a C module, like the greenlet module does.

Goog luck!

score 1 · Answer 2 · answered May 22 '20 at 00:22

This answer does a great job of explaining why it's hard to capture the state of the Python interpreter. This package does it for you. It doesn't implement call/cc, but it does implement longjmp and setjmp, which is just some syntactic sugar away from call/cc.

call/cc in Python — Possible?

2 Answers2