Writing Polymorphic Functions

Kronos functions can be polymorphic. At the lowest level, you have access to a compile time if. Yes, it is Turing complete. Making full use of that is probably not a good idea - most type systems are incomplete by design. Fortunately we have quite reasonable abstractions for you to fall back on.

Interestingly, the Kronos runtime is Turing incomplete due to having no dynamic branches or loops.

Pattern matching

Usually the best way is to pattern match against data. To demonstrate, let's write a monomorphic function:

Square-Number(x) {
	x * x
}

Square-Number(3)9


; Unfortunately,
Square-Number("horse")
* E-9995: Fatal{Eval (Anon-Fn nil) Fatal{eval nil Fatal{Square-Number horse Fatal{ (horse horse) Fatal{:Fallback:Binary-Op (:Fn{:Mul} Mul horse horse) Fatal{:Fallback:No-Match (Mul horse horse) Exception{Type mismatch{Could not find a valid form of ' Mul ' for arguments of type ' (horse horse) '}}}}}}}}

| Square-Number(horse)
|  (horse horse)
Cannot 'Mul' these types at compile time
Received (horse horse)

Cannot 'Mul' these types natively
Received horse

|    :Fallback:Binary-Op(:Fn{:Mul} Mul horse ... )
|      :Fallback:No-Match(Mul horse horse)
Could not find a valid form of ' Mul ' for arguments of type ' (horse horse) ' (Type mismatch)
Received (Mul horse horse)

The compiler barfs its type grievances. The salient information is on the last line: there's no 'Mul' for horses.

Now, let's devise an ingenious plan to make polymorphic Square that works for both numbers and strings, and also for a pair.

Square(x) {
	Square = x * x

	Square = String:Append("[" String:Append(x "]"))

	; For a pair, let's square both elements
	(a b) = x
	Square = (Square(a) Square(b))
}

Square(3)9


Square("horse")[horse]


Square(10 9)100 81


; Our definition of 'square of pairs' has some serendipitous
; consequences
Square(1 2 3 4 5)1 4 9 16 25


Square((1 2) (3 4 "foo") 5 6)(1 4) (9 16 [foo]) 25 36

We have three definitions for the polymorphic function. The compiler tries them in reverse source order. Destructuring a pair and String:Append are low level operators that match against a type; if its input is not a string, the enclosing function form is rejected.

A good rule of the thumb is to write the forms from the least specialized to the most specialized.

Higher Order Functions

The Algorithm package contains some functional staples, like Map to apply a function to all elements in a set, and Reduce to combine elements of a set. Internally, they make use of polymorphism. In the rest of this example, we build small equivalents. If you wish, take a look at the implementations in the standard library.

Fold

Fold is a simple function that can be used to combine elements of an ordered set. It takes the head of the set, recursively folds the tail of the set, and applies a combinator function to the results.

MyFold(f set...) {
	; if the set can't be destructured, assume it's a scalar
	MyFold = set...

	; pattern match against a destructurable set
	(x xs) = set...
	MyFold = f(x MyFold(f xs))
}

MyFold(Add 1 2 3 4 5)15

Unfortunately, this fold does not know how to operate on nil-terminated lists, because it thinks nil is a scalar.

MyFold(Add [1 2 3])
* E-9995: Fatal{Eval (Anon-Fn nil) Fatal{eval nil Fatal{MyFold (:Fn{:Add} Floatx3 nil) Fatal{MyFold (:Fn{:Add} Floatx2 nil) Fatal{MyFold (:Fn{:Add} Float nil) Fatal{f (Float nil) Fatal{:Fallback:Binary-Op (:Fn{:Add} Add Float nil) Fatal{:Fallback:No-Match (Add Float nil) Exception{Type mismatch{Could not find a valid form of ' Add ' for arguments of type ' (Float nil) '}}}}}}}}}}

| MyFold(:Fn{:Add} Floatx3 n ... )
|  MyFold(:Fn{:Add} Floatx2 n ... )
|    MyFold(:Fn{:Add} Float nil ... )
|      f(Float nil)
Cannot 'Add' these types at compile time
Received (Float nil)

Cannot 'Add' these types natively
Received nil

|        :Fallback:Binary-Op(:Fn{:Add} Add Float ... )
|           Coerce-Binary(Float nil)
|             Type-Conversion:Implicit(nil Float)
No match
 in C:\ProgramData\Kronos\Cache\kronoslang\core\0.12.9\Implicit-Coerce.k(8;19)
	Coerce-Binary = (Type-Conversion:Implicit(b a) b)
	                 ^^^

|             Type-Conversion:Implicit(Float nil)
No match
 in C:\ProgramData\Kronos\Cache\kronoslang\core\0.12.9\Implicit-Coerce.k(7;21)
	Coerce-Binary = (a Type-Conversion:Implicit(a b))
	                   ^^^

No match
 in C:\ProgramData\Kronos\Cache\kronoslang\core\0.12.9\Implicit-Coerce.k(15;10)
	func(Coerce-Binary(a b))
	     ^^^

|          :Fallback:No-Match(Add Float nil)
Could not find a valid form of ' Add ' for arguments of type ' (Float nil) ' (Type mismatch)
Received (Add Float nil)

The salient information is at the end: The compiler is trying to perform 3 + nil. Let's extend our understanding of a terminating condition:

; append a form after the fact with #[Extend]
MyFold(f set...) #[Extend] {
	(x xs) = set...
	When(Nil?(xs) x)
}

MyFold(Mul [1 2 3])6

Map

We can build a Map function similarly. This time, we accumulate a list on the return side:

MyMap(f set...) {
	; map trailing scalar
	MyMap = f(set...)

	; always map terminating nil to nil
	MyMap = When(Nil?(set...) nil)

	; destructure, map head and recur on tail
	(x xs) = set...
	MyMap = (f(x) MyMap(f xs))
}

MyMap((* 100) 7 3 2 1)700 300 200 100

MyMap(Math:Sqrt [1 2 3 4 5 6])1 1.4142135 1.7320508 2 2.236068 2.4494898 nil

If you are experienced in functional programming, you might worry that these fúnctions are not tail-recursive. You would be correct in the case of MyFold. However, MyMap is good: the way Kronos operates, you can generally assume tail consing. In other words, the compiler produces constant-space recursions even if structuring or destructuring happens after the recursive call.

DSP with Map and Fold

You can plug any combinator/mapping function into the constructs we just wrote, including the standard library oscillators.

Import Gen

vibr = Gen:Sin(5) * 0.01 + 1
freqs = MyMap((* vibr) 220 275 330)
oscs  = MyMap(Gen:Tri freqs)
snd = MyFold((+) oscs) * 0.1