Specialization and Polymorphism

One of Kronos' core capabilities is polymorphism. Functions can behave differently based on the type of their input. This article shows you how to make use of this capability.

Specialization

Kronos source code has few type annotations. The code is generic: the compiler will figure out the types based on context.

The state-of-art type systems out there make use of type inference - solving typing via algorithms like Hindley-Milner.

Kronos uses simple type derivation instead; think auto in C++, var in C# and their ilk. Because derivation requires global analysis, the aforementioned languages usually stop deriving at function boundaries and require manual type annotations. Unless you are working with C++ templates. But I digress.

The reason Kronos gets away with global type derivation is that the scope of Kronos programs is much more limited. Even a large signal processing graph will not approach the complexity of say, MS Word, by several orders of magnitude.

Derivation has a couple of upsides as well: it always works with no user intervention, for one.

In broad terms, Kronos will run your program, once at compile time, as a dynamically typed fragment, in order to figure out the static types it will use during run time. This is not unlike the way C++ templates work. Apart from the fact that Kronos is usually very quick about it, and will not balk at big recursions.

Polymorphic Function

As an example, let's construct a function that takes an arbitrary number of inputs and sums them:

Sum-All(set...) {
	; fallback form
	Sum-All = set...

	; while multiple elements are bound to set, destructure
	; and recur.
	(x xs) = set...
	Sum-All = x + Sum-All(xs)
}

Sum-All(1)1


Sum-All(1 2 3)6

This is the simplest kind of polymorphic function; one that relies on just implicit pattern matching.

Specialization Flow Control

Sum-All has two definitions; one of them relies on x and xs, which are obtained by destructuring the argument set....

Soft and Hard Failures

Destructuring does implicit pattern matching. That is, for an argument that is not destructurable, (x xs) = set... is not legal, and ends in a specialization failure. This is a soft failure; it causes the current form to be rejected, and the compiler will try the next available form. In our simple example, the second form merely returns set....

Let's introduce a different kind of type mismatch:

Sum-All(1 "two")
* E-9995: Fatal{Eval (Anon-Fn nil) Fatal{eval nil Fatal{Sum-All (Float two) Fatal{ (Float two) Fatal{:Fallback:Binary-Op (:Fn{:Add} Add Float two) Fatal{:Fallback:No-Match (Add Float two) Exception{Type mismatch{Could not find a valid form of ' Add ' for arguments of type ' (Float two) '}}}}}}}}

| Sum-All(Float two)
|  (Float two)
Cannot 'Add' these types at compile time
Received (Float two)

Cannot 'Add' these types natively
Received two

|    :Fallback:Binary-Op(:Fn{:Add} Add Float ... )
|       Coerce-Binary(Float two)
|         Type-Conversion:Implicit(two 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 two)
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 two)
Could not find a valid form of ' Add ' for arguments of type ' (Float two) ' (Type mismatch)
Received (Add Float two)

Tracing the specialization, we destructure (1 "two") and recur with Sum-All("two"). This call falls specializes to the first form, and we return to the initial iteration with an expression 1 + "two".

This results in a hard failure. The compiler will immediately stop trying to specialize this form at all, because + will not implicitly pattern match.

If + behaved like destructuring, we would simply reject this form and the confusing result of Sum-All(1 "two") would be (1 "two") as per the fallback form.

In summary, the rationale for soft and hard failures is to make the common case effortless, but bail when the results would likely be astonishing.

Explicit Flow

Sometimes we want to explicitly control specialization, especially when dealing with the Kronos compile time constants like strings "Hello World" and invariants #10. Here is a function to compute a compile time factorial, where an explicit branch is used via When.

F!(n) {
	When(n > #1
			n * F!(n - #1)
		 Otherwise
		 	#1)
}

; generate a compile time tuple of numbers 1..20
xs = Algorithm:Expand(#20 (+ #1) #1)
xs#1 #2 #3 #4 #5 #6 #7 #8 #9 #10 #11 #12 #13 #14 #15 #16 #17 #18 #19 #20 nil


; compute compile time factorials
Algorithm:Map(F! xs)#1 #2 #6 #24 #120 #720 #5040 #40320 #362880 #3628800 #39916800 #479001600 #6227020800 #87178291200 #1307674368000 #20922789888000 #355687428096000 #6402373705728000 #1.21645100408832e+17 #2.43290200817664e+18 nil

When is the explicit specialization branch, taking one or more clauses, each of which consists of a (compile time) condition and an expression. The conditions are evaluated in argument order, and the first matching expression is chosen. Otherwise denotes a catch-all expression, an else clause. When-nodes are also useful without Otherwise - if no condition is true, When emits a soft failure. This is demonstrated in the next example.

Function Attributes

We can also extend the polymorphic behavior of functions after the fact, even for third party or core library functions.

F!(n) #[Extend] {
	When(
		Not(Constant?(n))
		Raise("I can only compute factorials of compile time constants."))
}

F!(10)
* E-9995: Fatal{Eval (Anon-Fn nil) Fatal{eval nil Fatal{F! Float Exception{I can only compute factorials of compile time constants.}}}}

| F!(Float)
I can only compute factorials of compile time constants.
Received Float




F!("foo")
* E-9995: Fatal{Eval (Anon-Fn nil) Fatal{eval nil Fatal{F! foo Exception{I can only compute factorials of compile time constants.}}}}

| F!(foo)
I can only compute factorials of compile time constants.
Received foo




; does not trigger for invariants.
F!(#10)#3628800

There is, in fact, a pretty big hole in our Sum-All implementation: it can not cope with lists, which are nil-terminated tuples.

is = Algorithm:Expand(#5 (+ 1) 1)
is1 2 3 4 5 nil

Sum-All(is)
* E-9995: Fatal{Eval (Anon-Fn nil) Fatal{eval nil Fatal{Sum-All (Floatx5 nil) Fatal{Sum-All (Floatx4 nil) Fatal{Sum-All (Floatx3 nil) Fatal{Sum-All (Floatx2 nil) Fatal{Sum-All (Float nil) Fatal{ (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) '}}}}}}}}}}}}

| Sum-All(Floatx5 nil)
|  Sum-All(Floatx4 nil)
|    Sum-All(Floatx3 nil)
|      Sum-All(Floatx2 nil)
|        Sum-All(Float nil)
|          (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)




; This is because of the terminating condition
Sum-All(nil)nil

We can #[Extend] Sum-All to behave sensibly in this case:

Sum-All(set...) #[Extend] {
	When(Nil?(set...) #0)
}

Sum-All(nil)#0


; revisit the motivating case
Sum-All(is)15


; we can now reduce lists
Sum-All([100 1])101


; or using shorthand
Sum-All[100 1]101


; because `#0` will implicitly coerce to all runtime types, the type
; of the reduction is preserved
Class-Of(Sum-All[1d 2d 3d])#:Double

This makes use of most of the polymorphic capabilities mentioned prior: We #[Extend] the function Sum-All, appending a form that uses When to explicitly check for nil. In that case, we return a compile-time constant #0. When has no fallback form, so non-nil sets cause soft failure, and specialization proceeds to the next form.