Part 1

Operators as Lifts

Part 2

• (Also see:)

A gar (short for "generalized and rephrased") is a 3-tuple $(S, A, \iota)$ where $\iota : A \to (S \to S)$.

The intuition is that $S$ represents "values" or "states", $A$ represents "actions", and $\iota$ represents "interpreting" those actions.

Some gars exhibit interesting properties. For instance:

• A gar with identity is one where $id \in \iota(A)$, i.e., $\exists a_0 : \iota a_0 = id$
  • Meaning: "do nothing" is one of the actions
• A composable gar is one for which we have some function $\star : A^2 \to A$ which composes actions; precisely, $\iota(a \star b) = \iota a \circ \iota b$ for any $a, b \in A$
  • Meaning: we can compose actions
• A reversible gar is one for which $\forall a \exists a^- : \iota a^- \circ \iota a = id$.
  • Meaning: actions can be undone
• A preventable gar is one for which $\forall a \exists a^- : \iota a \circ \iota a^- = id$
  • Meaning: actions can be prevented
• A gar is homogeneous if $S = A$
  • Meaning: instead of a 3-tuple $(S, A, \iota)$, we have a 2-tuple $(S, \iota)$, which we can think of as a set $S$ of objects/states where $\iota : S^2 \to S$ lifts a state into an (interpreted) action.
• A gar with homogeneous composition is a homogeneous composable gar where $\iota = \star$
  • Meaning: instead of a 4-tuple $(S, A, \iota, \star)$, we have a 2-tuple $(S, \iota)$ which we can think of as a set $S$ of object/states where $\iota : S^2 \to S$ can be interpreted either as lifting a state into an action or as (pre-)composing two states.

Some examples of gars are as follows:

• For every $X$, $(X, X \to X, id)$ forms a gar with identity $a_0 = id$ and composition $\star = \circ$
• For every finite $\Sigma$, $(\Sigma^*, \mathbb N, \text{repeat})$ forms a gar with identity $a_0 = 1$ and composition $\star = \times$
• For every $X$ and $Y$, $(X, Y, \text{const})$ forms a rather interesting gar where every $y \in Y$ is an identity and every function $Y^2 \to Y$ is a composition. This is because $\iota(Y) = \{id\}$.
• For every finite $\Sigma$, $(\Sigma^*, \Sigma, \text{prepend})$ forms a gar without identity, compsition, reversibility, or preventability. Similarly with $\text{append}$.
• For every finite $X$, $(\text{Set } X, X, \text{insert})$ forms a gar without identity, composition, reversibility, or preventability. Similarly with $\text{delete}$.