Ko

A language for programming recursive circuits

Ko
2. Language
2.1. Computational model
2.1. Computational model

Ko is based on a new, simple, general-purpose computational model, called Recursive Circuits or simply circuits.

The basic building block of computation is captured by a circuit. Whereas a program comprises one or more circuits that can refer, i.e. use, each other.

Circuits uniquely correspond to (mathematical) functions that map (zero or more) input values into a single output value.

An individual circuit describes how the values of zero or more named arguments (the input values) are to be transformed into an output value.

Circuits

Formally, a circuit is a named directed-acyclic graph with (a) zero or more named “argument” vertices with no inbound edges, and (b) exactly one “return” vertex, with a single inbound edge and no outbound edges.

The argument and return vertices of the circuit are called “bounadry” vertices, and they correspond to the input values and the output value of the circuit.

All non-boundary vertices, called “steps” or “elements” (of the circuit), represent transformations of the values arriving on their inbound edges into the value delivered to all of their outbound edges.

Every circuit element has a label identifying the transformation that it performs. Labels can (recursively) refer to circuits (using their names), or they may refer to transformations provided by the runtime (and implemented in another language).

The edges incoming a circuit element are labelled after the name of the input argument (of the element transformation) they correspond to.

Example

Take for instance the mathematical function $$ F(x,y)=x^{\sin(y)}+\frac{1}{x^{\sin(y)}} $$ Supposing circuits for sine, exponentiation, addition and division are provided, \( F(x,y) \) can be implemented by the circuit in the following figure .

F(x, y) {
	return: Sum(
		left: Ratio(
			nom: 1
			denom: Exp(base: x, exp: Sin(angle: y))
		)
		right: Exp(base: x, exp: Sin(angle: y))
	)
}

TOP: Circuit implementation of the function \( F(x,y)=x^{\sin(y)}+\frac{1}{x^{\sin(y)}} \).
BOTTOM: Ko source code corresponding to the circuit.

Circuit diagrams follow a few conventions. A circuit definition is represented by a bounding box with argument vertices at the top and return vertex at the bottom.

Circuit elements are circles within the bounding box. Edges are directed downwards with respect to the page. Labels inside circuit elements indicate the transformations they refer to. Labels on edge endpoints represent the name of the argument (of the following transformation) that they provide.

Circuit diagrams have a corresponding source code representation, also shown in the figure.

Expansion

Notice that the circuit for \(F(x,y)\) has a repeated subgraph corresponding to \(x^{\sin(y)}\), as does the original formula. This repetition is highlighted in the figure below .

Circuit implementation of \( F(x,y)=x^{\sin(y)}+\frac{1}{x^{\sin(y)}} \), highlighting the repetition of \(x^{\sin(y)}\).

To accomplish this, we can capture the repeated logic into an auxiliary function, say \(G(x,y)=x^{\sin(y)}\), and substitute the corresponding subgraphs in F with references to G .

G(x, y) {
	return: Exp(
		base: x
		exp: Sin(angle: y)
	)
}

Circuit implementation of \( G(x,y)=x^{\sin(y)} \) (top) and its corresponding Ko source (bottom).

The updated implementation of F is shown below.

F(x, y) {
	return: Sum(
		left: Ratio(
			nom: 1
			denom: G(x: x, y: y)
		)
		right: G(x: x, y: y)
	)
}

Circuit for \( F(x,y)=G(x,y)+\frac{1}{G(x,y)} \) with its corresponding Ko source code.

Making this substitution saves writing (or drawing) and makes code more readable. However, the computation of F remains unchanged: At runtime the two invocations of G will be effectively expanded into two copies of G 's circuit logic.

Entanglement

Naturally, we would like to reuse the value from a single computation of \(G(x,y)\) to save computation. This is accomplished in the following modification of F 's implementation.

F(x, y) {
	g: G(x: x, y: y)
	return: Sum(
		left: Ratio(nom: 1, denom: g)
		right: g
	)
}

Circuit for \( F(x,y)=G(x,y)+\frac{1}{G(x,y)} \) which avoids computing \( G(x,y) \) twice. The label g , attached to the result of \( G(x,y) \), is a way of reusing the value in multiple locations.

Here the value of \(G(x,y)\) is computed by a single invocation to G . A purely-syntactic circuit-scope label, g , is assigned to it so that it can be refered to (in the two places in the code for F ) where needed.

(Note that circuits can recursively invoke themselves to implement self-referential functions like the Fibonacci function. This is accomplished through the use of varieties .)