In D language we can tie function to a template by alias:
struct BinaryTree(T, alias cmp_fun) {
alias V = T
alias compare = com_fun;
}
void main() {
alias Tree = BinaryTree!(int, (a, b) => a < b);
}
void insert(T)(T tree, T.V value) {
...
if(T.compare(value, node.value)) {...}
}
The same nim code failed to compile:
type
BinaryTree[V, compare] = object
value: V
proc insert(tree: BinaryTree, value: BinaryTree.V): bool =
BinaryTree.compare(value, tree.value) # Error: a type conversion takes exactly one argument
var a = BinaryTree[int, proc(a, b: int): bool = a < b](value: 10)
echo insert(a, 20)
I tried 4 different ways, 2 fails, 2 works.
Using a proc as a generic (failure):
type
BinaryTree[V; compare: proc(a, b: V): bool] = object
value: V
proc insert[V; compare](tree: BinaryTree[V, compare], value: V): bool =
# Error: attempting to call routine: 'compare'
# found 'insert.compare [declared in /home/beta/Programming/Nim/Arraymancer/build/bintree.nim(5, 16)]' of kind 'type'
compare(value, tree.value)
var a = BinaryTree[int, proc(a, b: int): bool = a < b](value: 10)
echo insert(a, 20)
Using a proc as a static (failure):
type
BinaryTree[V; compare: static proc(a, b: V): bool] = object
# Error: cannot generate VM code for proc (a, b: V): bool
value: V
proc insert[V; compare](tree: BinaryTree[V, compare], value: V): bool =
compare(value, tree.value)
var a = BinaryTree[int, proc(a, b: int): bool = a < b](value: 10)
echo insert(a, 20)
Using a compile-time switch (success):
type
CmpKind = enum
GreaterThan
LowerThan
BinaryTree[V; cmp: static CmpKind] = object
value: V
proc insert[V; cmp](tree: BinaryTree[V, cmp], value: V): bool =
when cmp == GreaterThan:
value > tree.value
elif cmp == LowerThan:
value < tree.value
var a = BinaryTree[int, LowerThan](value: 10)
echo insert(a, 20)
Using a compile-time dispatch table (success):
import macros
type
CmpKind = enum
GreaterThan
LowerThan
BinaryTree[V; cmp: static CmpKind] = object
value: V
let funcTable {.compileTime.} = [
GreaterThan: ident">",
LowerThan: ident"<"
]
macro dispatch(a: typed, cmp: static CmpKind, b: typed): untyped =
result = newCall(funcTable[cmp], a, b)
proc insert[V; cmp](tree: BinaryTree[V, cmp], value: V): bool =
dispatch(value, cmp, tree.value)
var a = BinaryTree[int, LowerThan](value: 10)
echo insert(a, 20)
That isn't exactly what I'm looking for, but anyway thank you.
I found that this works (need additional brackets around the definition of proc):
type
BinaryTree[V; compare: static[proc(a, b: int): bool]] = object
var b: BinaryTree[int, proc(a, b: int): bool = a < b]
echo b.compare(10, 20);
type
BinaryTree[V; compare: static[proc(a, b: V): bool]] = object
var b: BinaryTree[int, proc(a, b: int): bool = a < b]
echo b.compare(10, 20);
type Foo[T] = object
type Bar[T; F: static[Foo[T]]] = object
var bar: Bar[int, Foo[int]()]
This causes an ICE (internal compiler error):
type Vector[T; N: int] = object
data: array[N, T]
var v: Vector[int, 3]
fatal.nim(39) sysFatal
Error: unhandled exception: int128.nim(72, 11) `arg.sdata(2) == 0` out of range [AssertionError]
I also believe that generic parameters should be static by default:
type Foo[T, N: int] should be treated as type Foo[T, N: static int]
For your last proposition, there is no way to disambiguate between a type restriction and a static:
type Vector[T; N: int or uint] = object
var v: Vector[int, uint]
is different from
type Vector[T; N: static[int or uint]] = object
var v: Vector[int, 10]
Tying a procedure to a type is typically done by adding an overload. In the binary tree example, you would want to define a function such as cmp or the < operator for the Key type used to instantiate the tree. In the binary tree module itself, you would typically use the mixin keyword to indicate the functions that should be defined in the scope of the caller.
Sometimes, we need stateful comparison function (for example, we might be sorting coordinates by their distance to a particular point). Then the binary tree may hold an abstract "Comparison State" value that can be passed as an additional parameter to the cmp function.
type
BinaryTree[T, CmpState = void] = object
rootNode: ref BinaryTreeNode[T]
when CmpState isnot void:
cmpState: CmpState
BinaryTreeNode[T] = object
value: T
left, right: ref BinaryTreeNode[T]
proc insert[T, CmpState](tree: var BinaryTree[T, CmpState], val: T) =
mixin cmp # We allow the user to overload `cmp` for the value type
var curNode = tree.rootNode
while curNode != nil:
# Here, we make sure to call `cmp` with the right parameters
let cmpRes = when CmpState is void: cmp(val, curNode.value)
else: cmp(tree.cmpState, val, curNode.value)
# The search continues according to the result above
if cmpRes == 0:
...
elif cmpRes > 0:
...
else:
...The above solution is probably the most idiomatic at the moment (before concepts become stable). Now, if you really want to have the associated proc sitting as a generic parameter, you can either go for static and file issues for the encountered problems, or you can use techniques similar to tag dispatching in C++. The BinaryTree type can feature an extra type parameter that will be used for overload selection (typically with templates) to fetch constants, procs and other items associated with the type:
import strutils
type
ComparisonStyle1 = object
ComparisonStyle2 = object
template cmpFunction(x: type ComparisonStyle1): untyped =
cmp
template cmpFunction(x: type ComparisonStyle2): untyped =
cmpIgnoreStyle
echo cmpFunction(ComparisonStyle2)("foo_bar", "fooBar")I also believe that generic parameters should be static by default:
The reason why the generic parameters are not static by default is historic. When you specify a type for a generic parameter, it acts as a constraint. The generic will be instantiatable only with types matching the constraint and you would usually use a type class to specify it.
I definitely can use a compile-time known function as static parameter:
https://play.nim-lang.org/#ix=1LCk
type
BinaryTree[V; compare: static[proc(a, b: int): bool]] = object
var tree: BinaryTree[int, proc(a, b: int): bool = a < b]
echo tree.compare(20, 30);
Another strange artifact:
type
BinaryTree[V; compare: static[typed]] = object
const less1 = proc(a, b: int): bool = a < b
var tree1: BinaryTree[int, less1]
echo tree1.compare(20, 30); # works
proc less2(a, b: int): bool = a < b
var tree2: BinaryTree[int, less2]
echo tree2.compare(20, 30); # error: in expression 'tree2.compare(20, 30)': identifier expected, but found 'tree2.compare'
No, those your examples don't really work too — the procedure gets remembered at first variable's declaration, and those of other variables will be ignored.
type
BinaryTree[V; compare: static[proc(a, b: int): bool]] = object
var tree1: BinaryTree[int, proc(a, b: int): bool = (echo 1; a < b)]
echo tree1.compare(20, 30)
var tree2: BinaryTree[int, proc(a, b: int): bool = (echo 2; a < b)]
echo tree2.compare(20, 30) # will call the first procedure, printing "1"
The same for const.
Seemingly this last issue may be bypassed with a macro.
type
BinaryTree[V; compare: static[untyped]] = object
# different ways of providing a procedure
# an `echo` is added to each of them, to distinguish
const less1 = proc(a, b: int): bool = (echo 1; a < b)
type T1 = BinaryTree[int, less1]
var tree1: T1
const less2 = proc(a, b: int): bool = (echo 2; a < b)
var tree2: BinaryTree[int, less2]
proc less3(a, b: int): bool = (echo 3; a < b)
type T3 = BinaryTree[int, less3]
var tree3: T3
proc less4(a, b: int): bool = (echo 4; a < b)
var tree4: BinaryTree[int, less4]
var tree5: BinaryTree[int, proc(a, b: int): bool = (echo 5; a < b)]
import macros
# the macro can be just one line, if to restrict to just one of formats above
macro compare(v: typed): auto =
var p=v.getImpl[1]
if p.kind == nnkSym:
p = p.getImpl
expectKind p, nnkTypeDef
expectKind p[2], nnkBracketExpr
expectKind p[2][2], nnkSym
p = p[2][2]
else:
p = p[2]
if p.kind == nnkSym:
p = p.getImpl
else:
p = p[0]
if p.kind == nnkProcDef:
p = p[0]
p
# testing
var n = 20
echo compare(tree1)(n, 30)
echo compare(tree2)(n, 30)
echo compare(tree3)(n, 30)
echo compare(tree4)(n, 30)
(Another issue, only for the first kind (const + type), if n in the example is a constant or is replaced with a literal, that is the procedure may be evaluated at compile-time, then it is (the side-effect will occur at compile-time, for pure functions there's no difference).)
This version does type-checking (correctly pointing to procedure definition), and allows that simple method invocation syntax.
type
BinaryTree*[V; cmp: static[proc(a, b: auto): bool]] = object
# different ways of providing a procedure
# an `echo` is added to each of them, to distinguish
const less1 = proc(a, b: int): bool = (echo 1; a < b)
type T1 = BinaryTree[int, less1]
var tree1: T1
const less2 = proc(a, b: int): bool = (echo 2; a < b)
var tree2: BinaryTree[int, less2]
proc less3(a, b: int): bool = (echo 3; a < b)
type T3 = BinaryTree[int, less3]
var tree3: T3
proc less4(a, b: int): bool = (echo 4; a < b)
var tree4: BinaryTree[int, less4]
var tree5: BinaryTree[int, proc(a, b: int): bool = (echo 5; a < b)]
import macros
proc desymbolize(node: NimNode): NimNode =
result = node
while result.kind == nnkSym:
result = result.getImpl
# the macro can be quite short, if to restrict to just one of formats above
macro compare(v: typed): auto =
var p=v.getImpl[1]
var ty: NimNode
if p.kind == nnkSym:
p = p.getImpl
expectKind p, nnkTypeDef
expectKind p[2], nnkBracketExpr
expectKind p[2][2], nnkSym
ty = p[2][1]
p = p[2][2]
else:
ty = p[1]
p = p[2]
if p.kind == nnkSym:
p = p.getImpl
else:
p = p[0]
let prm = params(desymbolize p)
if prm.len != 2 or prm[1].len != 4 or prm[1][2] != ty:
error("Wrong comparison procedure provided, signature should be " &
"``proc(a, b: " & $ty & "): bool``.\n", p.desymbolize)
if p.kind == nnkProcDef:
p = p[0]
p
template compare*[T: BinaryTree, V](bt: T, a, b: V): bool =
compare(bt)(a,b)
# testing
var n = 20
echo tree1.compare(n, 30)
echo tree2.compare(n, 30)
echo tree3.compare(n, 30)
echo tree4.compare(n, 30)
echo tree5.compare(n, 30)