Lowering your continuations while lifting your functions (in Python)

 A Previous post describes Python code that does functional composition on reversible code. A question that one asks when starting to write compositional code is: how does one compose functions 'at different levels'? And I purposely express this a bit ambiguously as 'different levels' can mean different things. Today we will care about levels within a hierarchy of data containers and simple objects, and note a thing or two on the way.

The map function is Python's builtin tool to apply a function over each data of a container. Combined with a lambda or a function definition we can convert fonctions on container elements to functions on containers. Jargon for this type of code is that we are lifting a function to the container. The idea being that a function on a container is higher than function on container elements.

An important detail to note, is that while the mapped function is being lifted, the continuation context needs to be 'lowered'. This is because the lifted function will later be called with a continuation context for the container, yet internally the original mapped function is called, and it will need 'additional' continuation context. Therefore an extra level of continuation is added in to 'lower it' down to the level of the mapped function. Two examples are given, the first  

• "Lowers down" a detached generic continuation context. 

python

The second

• "Lowers down" a location carrying continuation. 

python (container), python (object)

Another particularity of this mapping code is that these extended / lowered continuation are data constructors. Which makes sense because for each element we need its return value to be become data to be put into the resulting mapped container.  This data constructor nature of the continuation extension also reflects the nature of the continuation changing as it enters the data container that is being mapped.

And this brings up an anecdote:

As I wrote these mapping functions, I was immediately reminded of the Newton programming language by Prof. Rapin EPFL. Sadly, I could not find a freely available document on Newton, yet if my memory serves me well, Newton had a higher order container location abstraction that provided a service not very different to our subject here. (One of my CS MS semester projects had me extending the Newton compiler,  in ~1985).

This continuation 'extension' technic has strong ties to the zipper structures for container traversals.

Yet more importantly it reminds us that within a more formal approach to code function arguments may be expressing:

1. What is coming in to the function.
2. The call contexts to the function.
3. Contexts of immediate use of the function's results.

Within a continuation passing style, it is therefore perfectly ok to decorate your continuations to communicate more context to your functions. In the example code referred to here, the 'lowered' continuation carries index positions, dictionary keys, and dataclass field names. 

All original content copyright James Litsios, 2021.