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.

Data composition from functional composition in Python

Previous post describes code that does functional composition. Let's now add operators that convert this functional composition to become data composition, and allow what is produced to be 'executed later'. Github drop for these code snippet here.

Key insights in writing code this way are:

• Data objects are derived from the functions which define their semantics.
• This is meta-programming 'done backwards'. Like with meta-programming we capture 'what could be interpreted', but we do so through the execution semantics, not by adding an additional meta-language.
• Data objects execution semantics can be ambiguous until ambiguities are removed. Not far from a "quantum-like" execution model!
• There are strong ties here to laziness and trampolining.
• Blockchains are as much about composition of data, as about composition of functions.

These example code snippets are very short (<100 active lines). Two design choices make this possible: 

1. Focus on arguments, not return value, nor object state
2. Make everything composable 

What these examples hint at is:

• Return values are really just arguments to further calls. 
• Object states are really just arguments, references (e.g. function reference), and contexts of possible further calls.

This is in fact true at the most simple level, such as in the code tied to this posting. 

All original content copyright James Litsios, 2021.

Point-free reversible Python

Have you ever wanted to to write 'formal style' in Python?

If so, these snippets of code which I shared on gitbub might please you.

What is a formal style of programming

Formal "code", like formalism in mathematics, is to solidly tie what you write to what you mathematically mean. And that connection goes both ways: from math to expression, from expression to math. 

The traditional way to write formal code is to prove as much as you can 'along the way' of writing code. The difficulty of this approach is that proofs are hard, which either limits the complexity of your code, or limits your ability to be productive.

Another way to write code with mathematical properties is to assemble pieces of code that already have mathematical properties. When this assembly preserves these mathematical properties, and even better when it scales them, the resulting code has mathematical properties.  A key concept here is that these "pieces of code with mathematical property" are "at different levels", as it is the interplay between these levels that give the code its semantic depth.  (This last point explains why languages like Prolog are hard to scale).

Dualities are good place to find mathematical properties.  An example of duality is symmetry: something can be 'one way' and 'the other', and we know "mathematically" what that means. This is why reversible code,  reversible types, adjoint structures, and pretty much anything that goes 'one way' and 'the other' (e.g. like rows and columns) are a good basis on which to build systems with formal properties.

What is reversible programming?

Reversible expressions can be evaluated 'one way' and 'another'. This might be execution evaluation that might be reversed, yet might also mean that the interpretation of the expression can be seen from a reversed perspective at different semantic level (e.g. types, external view).

Reversibility is also a way to approach multi-party programming: Say I am party Alice having received B from Bob, after having previously shared A with Bob. Alice can reverse compute B to A to validate that Bob computed B from A. That is a simplified view of things, but it captures the idea that reversibility enables trust.

Reversibility is much like immutability that has been weakened, but which has not lost its magical properties.

What is point-free style?

A point-free (or tacit) style of programming traditionally means coding by composition without naming arguments (and without assignments). In a Python centric view that could mean to only use 'positional arguments', and to use only Callable objects (so as not to have method names), but you need to ask yourself: "Is that important"? In fact within the scope of reversible programming, point-free is best approached as composable and reversible. That you name things or not is of lesser importance. In fact, it is of lesser importance also because the traditional point-free is to focus on 'expression space'. Yet modern programming happens much at the type level, or the meta-type level, and a strict point-free approach would lead us to writing code where types are nameless, as well as meta-types. That would be tricky!

Note here: Point-free much leads to array, stream and structural oriented programming. This is not lost here. In fact a main reason to write code like this in Python is to write structural oriented ML. Reversibility is also a vital piece of blockchain and smart contracts theory too.

Why should you care?

Wikipedia's programming paradigm page enumerates many ways to code. Reversibility is one of the concepts that brings together all of these different ways of expressing software. Putting reversibility 'underneath' a paradigm gives it bridges to other paradigms that have also been given reversibility properties. 

All original content copyright James Litsios, 2021.

Retrospective on "my bookshelf picture"

 My previously shared bookshelf picture got a hit peak and this got me thinking: 

• Most of my books are more than 20 year old. Some are from my dad and his older brothers. That means they are sixty+ years old! (FYI my dad, Socrates Litsios, recently passed away, had a PhD from MIT (operational research in EE department)).
• I have never been a linear student (except with audio books). I tend not to read books but to read publications. And even then, I skim the publications, I do not read them. However, I do a lot: I program prototype on prototype during my spare time. I implement software for real professionally, mostly in rocket science areas that rely on math. Therefore most of these books still resonate with me, having used much what is in them. That is why I keep them.
• Once a year I throw out the books that no longer resonate. A month ago I put 30 of these books on a chair on the sidewalk, including my Collected Algorithms from ACM books (mostly Fortran in print). At the end of the day only three books were still there! Explanation: many people work for Google or in finance in Zurich.
• None of my books are actually what I work on. Yet many of my books are still inspirational.
• For example: category theory. When I hired a Haskell team here in Zurich I was a bit surprised to find how much they thought lowly of category theory. Or to be more specific, they did not find category theory useful. Yet that is mostly because to know something is not about reading up and know the theory. To know something is to push your knowledge until you feel its limits, and by doing so become even more productive, because you know what works. With category theory, only "mechanized category theory" is valuable for a developer.  The difficulty then is a Haskell developer will say "Haskell is mechanized category theory", when in fact it is just one way to do that mechanization projection.
• My back burner long term theme this year has been to have a better understanding of theoretical physics. I have reading math book for this purpose.
• The side note here is that when I was about seventeen, I was pretty upset when I understood that no model in physics "was for ever".  Now I find the limits of modelling reality a pretty cool subject, but it took me some time to get over the "feeling of uncertainty" of physics. This also explains why I have always been a math aficionado.
• Another side note is that I don't read books like these cover to cover. I keep them beside my bed and read a few pages here and there over a period which typically is more than a year.
• Last side note: I listen to audio books while driving, shopping, etc. These are books I very much enjoyed to listen on the subject of people in theoretical physics. Graham Farmelo is the star author here with his genuine understanding of what makes these physicist tick:
• Quantum Man: Richard Feynman’s Life in Science (L. M. Krauss)
  
• Quantum Physics: What Everyone Needs to Know (M. G. Raymer)
  
• Professor Maxwell's Duplicitous Demon (B. Clegg)
  
• The Universe Speaks in Numbers (G. Farmelo)
  
• The Strangest Man: The Hidden Life of Paul Dirac (G. Farmelo)

All original content copyright James Litsios, 2021.

Stream oriented processing

Here is a presentation on designing stream processing systems which I uploaded to YouTube today. Recorded in ~2014, and given in one form or another a few times since about 2005, it is how I "model with streams", something I learned designing market making and algo systems. What I like most about this old deck is how it stays aligned with modern abstraction expressed in higher-order FP semantics.

I wrote a bit on stream processing here in 2011.  I see also that I have a draft for publishing this presentation in 2013. Yet I had wanted to add Scala or Haskell code that captured the "nice figures" of this presentation, and that is why I held back from sharing it earlier. 

All original content copyright James Litsios, 2021.

Single class refactoring exercise (in Python)

This week I needed to extract a little piece of computational geometry, imbedded in a single Python class of application specific logic. Therefore I proceeded to create a second class and migrate the computation geometry code over to it. On of the pleasures of Python is the ability to do this type of refactoring at low cost, and pretty much follow a recipe. Which I include here: 

1. Start with class A
2. Create new class B, derive A from B
3. Move part of A.__init__ to B.__init__
4. Move initial subset of member functions A to B, implicitly creating a first API between A and B (API A-B)
5. Iterate and apply one or more of:
1. Split / merge methods within API A-B
2. For A still accessed directly (through self) by B,  extend API A-B to provide additional A content.
3. Find flow/bundle/fiber/ data of A and B, refactor these to be within new classes C0, C1, .... Alternatively refactor them to be within additional Numpy axes (e.g. for ML applications).
4. Move selected Cs to from A to B or B to A. If appropriate adapt API
5. Move selected Cs into API A-B or take out of the API
6. Find variants within the Cs. Bring these under new protocol classes P0, P1, ... Adapt API A-B to depend on Ps. Alternatively, find Numpy axes with shared "basis",  and refactor towards abstract shape/axes properties, then adapt API.
6. Stop when all traces of A have been removed from B, and the API A-B is generic enough for the desired future usage of B.

Notes:

• "Flow data" are typically found in arguments to functions.
• Writing generic axes logic in Numpy is super hard as Numpy gives little help for pure pointfree-style functional code. However it can be done, and you can for example write 1d, 2d, and 3d logic as just one common piece of Numpy code.
• I was going say always retest as you refactor. Yet in my usage above I did not, and regretted it when my first test failed after a few hours of work. Given that I had "changed much", I quickly reapplied my changes to the original code, but this time running tests each time.

All original content copyright James Litsios, 2021.

Market participants, structural dysfunctions and the GameStop event

At least eight dimensions can be used qualify the way financial participants trade:

1. Transaction speed from slow to quasi-instantaneous.
2. Transaction rate from rare/infrequent to quasi-continuous.
3. Selection of transactions from disorganized to very organized (e.g. backed by mathematics and research).
4. Transaction's future obligations from no future obligations to with future obligations (e.g. backed by personal wealth).
5. Time scope of transaction's obligation from immediate (e.g. transfer cash) to long term (e.g. payout bond coupon after 30y).
6. Number of participants on "same side of transaction" from small to large
7. Size of single transaction from small to large.
8. Influence of fundamental/"real world" properties of traded contract from none to very important.

In the context of the GameStop event we note the following: 

Traditionally,  retail investors execute transactions:

1. Slowly
2. Infrequently
3. In a disorganized way
4. With no future obligation
5. With only immediate obligation
6. As part of a very large group of similar participants
7. On transactions of small size
8. With more care about the image/brand of the traded products than the fundamentals

To differentiate, one type of hedge fund's transactions might be qualified as:

1. Quasi-instantaneous
2. Quasi-continuous
3. Organized with algorithms and machine learning
4. Including much future obligation
5. With future obligations up to ~1Y
6. As part of a small group of similar hedge funds
7. On transactions of small size and of complementary transactions of larger size.
8. With a combination of caring only about short term machined learned properties to some caring about longer term fundamentals

And to differentiate with at least thirty other market participant profiles going from broker to settlement bank, or insurer. This last point being important: it is not "just" about the retail investors and certain types of hedge funds, there is a whole "ecosystem" out there of financial interdependence. Also coming back the hedge fund example: important are the strong future obligations, the hedge funds "have promised" something. In this case to give back the GameStop shares they have borrowed, or pay out options that depend on the high value of the stock.

Now then, the key changes in the GameStop event are the retail investors GameStop transactions becoming:

1. Slow
2. More frequent
3. Very organized: buy only, "buy for ever"
4. With no future obligation
5. With only immediate obligation
6. As part of a very large group of similar participants
7. On transactions of small size, (probably bigger average)
8. Caring about "beating hedge funds", making a killing with the rising share price, the charismatic"gaming product" brand, with absolutely no caring about fundamentals.

The "very organized on one side" is the killer ingredient here. All trading strategies are a form of balancing act, and all participants assume some amount of future market behavior will support their trading strategy. The traditional retail investors assume that someone will be there to buy back what they have purchased. Hedge funds assume they will be able to take advantage of the different needs and random nature of the different market participants, and more importantly, they assume that they can rebalance their risk "on the fly" within their trading strategy.  One can visualize a hedge fund as a bicycle that is pulled to the left or the right as trades are made, and that actively needs to rebalance from time to time by making selected trades, to avoid "falling over". However, if all the trades are "one sided", and worse, they are all counter the initial assumptions of the hedge fund, things go bad quickly, as the hedge fund is mostly only able to make trades that imbalance it further, leading to it hitting its financial limits, and either being acquired by a bigger fish, or going bust. 

The flash crash, was another example of "structural dysfunction" to the market, when the prices plunged because most quotes were pulled. With the GameStop event, the prices exploded because a large enough group of participants suddenly decided only to buy and hold. 

There are many markets with an imbalance of buyers and sellers. What is new here is: in a market with future obligations a disproportionate amount of participants suddenly decided to actively participate only on one side of the transaction (here buying). A learning that hedges funds will integrate at the cost of limiting their leverage.

All original content copyright James Litsios, 2021.

From sparse tensor parameter space to orchestrated stream of distributed processes

In 1996, my team adopted a tensor view of its application parameter space.

Credit must be given to one of my partners at QT Optec/Actant, who presented the following view of the world: each client could "tie" each parameter to any point/slice in "high-dimensional" cartesian space of primary and secondary keys. It was an advanced concept which took me many years to fully master. The simple statement is: "it ain't easy"!

Higher dimensional data views are "all the rage" now, but not in 1996. I'll try to illustrate the concept as follows:

Imagine we have a parameter P1 used in formula F that goes from X to Y. Imagine that X can be queried with keys kx0 and kx1 (it is two dimensional) and Y is three dimensional with "axis" ky0, ky1, and ky2. P1 is a parameter, which means that it is a "given value". The question is then: is P1 just one value? Should we use a different P1 for the different values of X tied to its 2d mapping to kx0 and kx1? We could even imagine that P1 is different depending on F producing Y in different values of the three dimensions ky0, ky1, ky2. We could even do better. We might say that P1 sometimes depends on X, and sometimes depends on Y, this would especially make sense if F was dependent on yet another set of data Z, and the new condition is that the choice of P1 depends on Z.

With hindsight, the key learning is that no data is static. Therefor P1 is not "a parameter", P1 is a stream of values. The simple rule is nothing is "just data", it is always data within a process of update of that data, parameters do not exist. To simplify: we can say that P1 is a stream of data. Yet to get the design model right, we need to say that P1 is a stream of data constrained by a very specific process. 

All of the examples above are about P1 being parallel streams of data. And the second key learning is that most often this means that P1 is a distributed process of streamed data that must follow a very specific distributed process of data.

The original problem/solution formulation was somewhat OO or DB. Put in an orchestrated stream of distributed processes form we actually have most of the tools we need to make this concept scale and work.  

All original content copyright James Litsios, 2021.

What works in higher order Python (Functional Programming, early 2021)

 Here is what works for me to write higher order typed Python:

1. Use class with __call__ instead of lambdas or functions (aka explicitly specify each closure).
2. Favor constraining types with Callable, ParamSpec and Concatenate (not with class constructions).
3. Replace *args by immutable list (Tuple[a,Tuple[b, ...) when ParamSpec fails to scale. 
4. Replace **kwargs with object using @overload with Literal typed arguments (sadly TypedDict seems not to support generic typing) .
5. Use Generic to “store” multiple polymorphic types
6. Use Protocol to separate semantic tiers of types (e.g. ownership in a smart contract)
7. No nested functions, lambdas or classes.
8. Use cast to type "unmanaged" types (e.g. eval)
9. Use phantom typed "dummy" arguments (and type casts) to get around "wrong direction" type dependencies
10. Visual Code's Pyright works. Early 2021, pycharm fails.

The untyped application scope is a broader Python 3 stack. Note this is 3.10 Python typing (e.g. ParamSpec).  

Not all is easy. Deeply typed Python seems to be magnitudes more expensive to write than "classical" Python. Also, Union types may be needed to "break out" from "tight" type relations. My current feeling is that one is sometimes forced to introduce Unions to allow complex trace joins and bifurcation, to then need to add additional layers of type constraints to control the generality of these Unions. All of this needs to be done with careful "locking" of types. Not the best of situations!

Python is known to be a dynamically typed language, which is ok, as static typing is more of a luxury than a necessity. I learned the above this 2020-2021 Xmas holiday writing lens/optic like python code. Initially with no types, fully lambda centric. Then I thought: let’s try to make it typed in Python!

All original content copyright James Litsios, 2021.