A language for programming recursive circuits

2. Language
2.3. Varieties and recursion
2.3. Varieties and recursion

Ko has lambdas (functional values) and closures (creating functional values by fixing some or all arguments) as in other languages. In Ko, functional values are called varieties , whereas the operation of fixing arguments of a variety (to produce a new, restricted variety) is called augmentation .

The exact syntax of augmentation is described in the syntax chapter . In brief, augmentation uses the same syntax as invocation, replacing the round brackets, () , with square ones, [] . In the following example we assume that a function Max3(a, b, c) which returns the maximum of its three arguments is given.

ReturnTheMax(x, y, z) {
	max2: Max3[a: x]   // fix the a-argument of Max3 to x
	max1: max2[b: y]   // fix the b-argument of max2 to y
	max0: max1[c: z]   // fix the c-argument of max1 to z
	return: max0()

Calling ReturnTheMax(x: p, y: q, z: r) (for some arguments p , q and r ) is equivalent to calling Max3(a: p, b: q, c: r) .


Varieties are particularly important when implementing recursive functions. Consider the following implementation of a function computing the n-th Fibonacci number.

import "integer"

Fib(n?) {
	branch: Yield(
		if: Or(   // If n is a base case (0 or 1),
			integer.Equal(n, 0)
			integer.Equal(n, 1)
		then: [1]   // then Yield returns a variety that will return 1 when invoked,
		else: fibSum[n]   // otherwise Yield returns a variety for the recursive step.
	return: branch()   // Whichever variety was returned, invoke it.

fibSum(m?) {
	return: integer.Sum(
		Fib(integer.Sum(m, -1))
		Fib(integer.Sum(m, -2))

The key point in this example is that the Yield step does not invoke the recursive function fibSum , rather it returns a variety to it. If the function were to be invoked (by writing fibSum(n) instead of fibSum[n] ), then Fib would hang in an infinite recursive loop. This follows from the rule that once a function starts executing (in this case Fib ) all of its elements will be executed and waited on to complete before the function completes itself.