Introduction to Redex

Getting started with combinators

Combinators provide a simple and concise way of composing functional code. They may compose, be used by, be mixed with other combinators or standard python functions.

import operator as op
from redex import combinator as cb

The Serial combinator allows function composition.

serial = cb.serial(op.mul, op.add, op.sub)
serial(1, 2, 3, 4)

1

## The same may be achieved with the code:
x1 = 1
x2 = op.mul(x1, 2)
x3 = op.add(x2, 3)
x4 = op.sub(x3, 4)
x4

1

The Parallel combinator applies given functions in parallel to its inputs. Each function consumes a span of inputs. The span sizes are determined by a number of required arguments of these functions.

parallel = cb.parallel(op.add, op.sub)
parallel(1, 2, 3, 4)

(3, -1)

## The same may be achieved with the code:
x1 = op.add(1, 2)
x2 = op.sub(3, 4)
(x1, x2)

(3, -1)

The Branch combinator combines multiple branches of given functions and operate on copy of inputs. Each branch includes a sequence of functions applied serially.

branch = cb.branch(cb.serial(op.mul, op.add), op.sub)
branch(1, 2, 3)

(5, -1)

## The same may be achieved with the code:
x1 = op.mul(1, 2)
x2 = op.add(x1, 3)
x3 = op.sub(1, 2)
(x2, x3)

(5, -1)

The Select combinator may be used to rearrange or copy inputs.

select = cb.select(indices=[0, 0, 1, 1])
select(1, 2, 3, 4)

(1, 1, 2, 2, 3, 4)

## The same may be achieved with the code:
xs = (1, 2, 3, 4)
(
    xs[0],
    xs[0],
    xs[1],
    xs[1],
    *xs[2:],
)

(1, 1, 2, 2, 3, 4)

The Dup combinator is a convenient way to make a single copy of inputs.

dup = cb.dup()
dup(1, 2, 3, 4)

(1, 1, 2, 3, 4)

## The same may be achieved with the code:
xs = (1, 2, 3, 4)
(
    xs[0],
    xs[0],
    *xs[1:],
)

(1, 1, 2, 3, 4)

The Drop combinator allows to drop some inputs.

drop = cb.drop(n_in=2)
drop(1, 2, 3, 4)

(3, 4)

## The same may be achieved with the code:
xs = (1, 2, 3, 4)
xs[2:]

(3, 4)

Check out the documentation to find out about other combinators.

Creating new combinators

Stack

Combinators operate on the stack of function arguments. They take inputs off the stack, execute a function, then push its outputs back onto the stack. If a function output is a tuple, it gets flattened before placed on the stack. If an input argument is a tuple, each tuple parameter is considered as an independent item on the stack. These parameters are reshaped before get passed to the function as arguments.

from redex.stack import constrained_call, stackmethod, Stack

The built-in function operator.add would take two arguments off the stack and push a single output back onto the stack.

constrained_call(func=op.add, stack=(1, 2, 0, 0))

(3, 0, 0)

The stackmethod wrapper provides a convenient way to transform arguments of an arbitrary function to the stack when implementing combinators.

class Add:
    @stackmethod
    def __call__(self, stack: Stack) -> Stack:
        return constrained_call(func=op.add, stack=stack)

add = Add()
add(1, 2, 0, 0)

(3, 0, 0)

Note that to create a true combinator we would need to derive it from the Combinator class and specify explicitly the number of its inputs and outputs. In most cases, we would calculate these values dynamically from signatures of nested functions.

Type annotations

To pass data through the stack, combinators need to know exact number of outputs, inputs, and input shapes of functions. This information may be inferred from type annotations of nested functions or set explicitly.

Note that:

• when return annotation isn’t available, a single output is assumed (to support buit-in functions).

• any input argument without default value is counted as a single input.

• for tuples used in type annotations, a number of tuple parameters must be definite (e.g. tuple parameters must be specified and variadic tuples must not be used).

from redex.function import infer_signature

As an example, the built-in function operator.add has two inputs and a single output.

infer_signature(op.add)

Signature(n_in=2, n_out=1, start_index=0, in_shape=((), ()))

Combinators are able to work with functions accepting composite types and returning multiple outputs. To prove that, let’s create such functions. The function create_pair would accept a single argument of type int and output a pair, tuple[int, int]. Another function, add_pairs, would accept two arguments of the pair type and output a single pair.

Pair = tuple[int, int]

def create_pair(value: int) -> Pair:
    return (value, value)

def add_pairs(lt: Pair, rt: Pair) -> Pair:
    return (lt[0] + rt[0], lt[1] + rt[1])

We see that output n_out=2 of the function create_pair consists of two values. When used with a combinator, tuple[int, int] will be flattened and each int get placed onto the stack individually.

infer_signature(create_pair)

Signature(n_in=1, n_out=2, start_index=0, in_shape=((),))

The function add_pairs accepts two tuples: two parameters per tuple, four inputs in total, in_n=4. These four inputs would be taken off the stack, reshaped, and only then passed to the function as arguments.

infer_signature(add_pairs)

Signature(n_in=4, n_out=2, start_index=0, in_shape=(((), ()), ((), ())))

To demonstrate the above functions in action, let’s create create_then_add_pairs combinator. Given 2 and 3 values, it would create two pairs (2, 2) and (3, 3) using create_pair, then pass these pairs further to add_pairs.

create_then_add_pairs = cb.serial(
    cb.parallel(create_pair, create_pair),
    add_pairs,
)

create_then_add_pairs(2, 3)

(5, 5)

Debugging combinators

With debug logging enabled, we can inspect how data flow within combinators.

import logging

For the above combinator, enabling debug level of the logger gives information about signatures of nested functions and stack usage.

logging.getLogger().setLevel("DEBUG")
create_then_add_pairs(2, 3)
logging.getLogger().setLevel("INFO")

DEBUG:root:constrained_call :: Parallel             stack_size=2  signature=Signature(n_in=2, n_out=4, start_index=0, in_shape=((), ()))
DEBUG:root:constrained_call :: create_pair          stack_size=1  signature=Signature(n_in=1, n_out=2, start_index=0, in_shape=((),))
DEBUG:root:constrained_call :: create_pair          stack_size=1  signature=Signature(n_in=1, n_out=2, start_index=1, in_shape=((),))
DEBUG:root:constrained_call :: add_pairs            stack_size=4  signature=Signature(n_in=4, n_out=2, start_index=0, in_shape=(((), ()), ((), ())))