Hello Nim enthusiasts.
I'm an absolute beginner being familiar with Nim for about a week and having troubles using astar nimble package. Looks like my question is fairy general, though, so I post it here.
Module astar defines the following:
type Graph* = concept g
## The graph being traversed.
## * `nieghbors`: Iterates over the neighbors of a node in the graph
## * `cost`: Returns the price for moving between two nodes
neighbors(g, Node) is iterator Node
cost(g, Node, Node) is Distance
iterator path*[G: Graph, N: Node, D: Distance](graph: G, start, goal: N): N
Basically user has to define concrete types for Graph, Node and Distance and implement neighbors and cost procedures.
So far so good. But what if I need different cost functions? First thought is to define cost as a nested proc in the same block there call to path is located. But for some reason only global definitions accepted by the compiler. For nested one I get
Error: attempting to call undeclared routine: 'cost'
Is it a bug or intended behavior? If latter is the case, what's the idiomatic way of parametrizing the code in such situations in Nim?
I guess thats only possible if the concept is extended with your own cost functions or the cost function gets a procvar for the calculation.
Notice that the concept is used to implement different Graph implementations not for creating one Graph implementation with different distance cost calculations.
@Varriount, of course. Here is something I'd like to be able to write (rephrased example from astar readme)
import astar, hashes
type
Grid = seq[seq[int]]
## A matrix of nodes. Each cell is the cost of moving to that node
Point = tuple[x, y: int]
## A point within that grid
template yieldIfExists( grid: Grid, point: Point ) =
## Checks if a point exists within a grid, then calls yield it if it does
let exists =
point.y >= 0 and point.y < grid.len and
point.x >= 0 and point.x < grid[point.y].len
if exists:
yield point
iterator neighbors*( grid: Grid, point: Point ): Point =
## An iterator that yields the neighbors of a given point
yieldIfExists( grid, (x: point.x - 1, y: point.y) )
yieldIfExists( grid, (x: point.x + 1, y: point.y) )
yieldIfExists( grid, (x: point.x, y: point.y - 1) )
yieldIfExists( grid, (x: point.x, y: point.y + 1) )
proc heuristic*( grid: Grid, node, goal: Point ): float =
## Returns the priority of inspecting the given node
asTheCrowFlies(node, goal)
# A sample grid. Each number represents the cost of moving to that space
let grid = @[
@[ 0, 0, 0, 0, 0 ],
@[ 0, 3, 3, 3, 0 ],
@[ 0, 3, 5, 3, 0 ],
@[ 0, 3, 3, 3, 0 ],
@[ 0, 0, 0, 0, 0 ]
]
let start: Point = (x: 0, y: 3)
let goal: Point = (x: 4, y: 3)
proc print_route1(g:Grid, p1,p2:Point):void =
proc cost(grid: Grid, a, b: Point): float =
## Returns the cost of moving from point `a` to point `b`
float(grid[a.y][a.x])
for point in path[Grid, Point, float](g, p1, p2):
echo point
proc print_route2(g:Grid, p1,p2:Point):void =
proc cost(grid: Grid, a, b: Point): float =
## Returns the cost of moving from point `a` to point `b`
float(grid[a.y][a.x] - grid[b.y][b.x] + 1)
for point in path[Grid, Point, float](g, p1, p2):
echo point
print_route1(grid, start, goal)
print_route2(grid, start, goal)
Notice that the concept is used to implement different Graph implementations not for creating one Graph implementation with different distance cost calculations.
@OrderWat but that's precisely what I need. I have a single data structure and I want to try to build several paths according to different criteria. I thought of concept's members as of something similar to implicit params in Haskell or Scala. Maybe I completely miss the idea, though. Can you please elaborate a bit more on your idea of overloading? Please, notice, We have a single library module declaring concepts and other module using it.
This looks to be more a limitation in the current concept implementation (although whether the limitation will be lifted is a design decision that Araq will have to make).
Currently the compiler only considers globally-scoped procedures when testing of a concept "fits" a type, likely for complexity reasons.
For example, what would happen in your code if a global 'cost' procedure is already declared? What happens if you try to pass g in print_route1 to another procedure expecting a Graph argument (g may be considered a Graph in the scope of print_route1, but not in the scope of sub-procedure calls).
Again, this appears to be more of a limitation of the current concepts implementation than a limitation in the abstract idea of concepts.
As a workaround, you can either just use plain generics (I think), templates, or as a final resort, procedure parameters or procedure tables/structs (like C++ vtables).
@Varriount. Looks like a tough question. At first I was tempted to say concepts should obey the same scoping rules as variables do. After all, it's hardly a surprise that the following snippet prints '10'.
var a = 5
proc tst() =
var a = 10
echo a
tst()
That made me realize what concepts already obey some kind of dynamic scoping. Currently it's limited to modules, though. I don't know is it a good idea to expand it to nested procedures. Not everyone is happy with that feature in Lisp, afaik. Still it looks so nice and intuitive to be able to parametrize path in first example by just writing nested procs. Creating several separate modules for such a tiny task looks like a total overkill.
Creating several separate modules for such a tiny task looks like a total overkill.
Is that any worse than needing a file for each class in Java? Module-scoping seems crystal clear to me. And you're right about Lisp -- excessive dynamic scoping.
This is all an excellent question though. I'm still trying to wrap my head around "concepts" fully.
@cdunn2001
Let us not speak about Java :) Why not to compare with something like implicit parameters in Haskell or Scala instead? It's a variation on theme of dynamic scoping too, albeit more organized one. And work quite good in my experience. Just don't overdose them.
Hey again!
You can accomplish this using distinct types. The unit tests for AStar are a bit convoluted, but that's how they work:
https://github.com/Nycto/AStarNim/blob/master/test/astar_test.nim#L7-L12
For your example, I believe this should compile:
import astar, hashes
type
Grid = seq[seq[int]]
## A matrix of nodes. Each cell is the cost of moving to that node
Point = tuple[x, y: int]
## A point within that grid
GridOne = distinct Grid
GridTwo = distinct Grid
AnyGrid = GridOne|GridTwo
template yieldIfExists( grid: AnyGrid, point: Point ) =
## Checks if a point exists within a grid, then calls yield it if it does
let exists =
point.y >= 0 and point.y < grid.len and
point.x >= 0 and point.x < grid[point.y].len
if exists:
yield point
proc `[]`( grid: AnyGrid, index: int ): seq[int] =
Grid(grid)[index]
converter toGrid(g: GridOne): Grid = Grid(g)
converter toGrid(g: GridTwo): Grid = Grid(g)
iterator neighbors*( grid: AnyGrid, point: Point ): Point =
## An iterator that yields the neighbors of a given point
yieldIfExists( grid, (x: point.x - 1, y: point.y) )
yieldIfExists( grid, (x: point.x + 1, y: point.y) )
yieldIfExists( grid, (x: point.x, y: point.y - 1) )
yieldIfExists( grid, (x: point.x, y: point.y + 1) )
proc heuristic*( grid: AnyGrid, node, goal: Point ): float =
## Returns the priority of inspecting the given node
asTheCrowFlies(node, goal)
proc cost(grid: GridOne, a, b: Point): float =
## Returns the cost of moving from point `a` to point `b`
float(grid[a.y][a.x])
proc cost(grid: GridTwo, a, b: Point): float =
## Returns the cost of moving from point `a` to point `b`
float(grid[a.y][a.x] - grid[b.y][b.x] + 1)
# A sample grid. Each number represents the cost of moving to that space
let grid = @[
@[ 0, 0, 0, 0, 0 ],
@[ 0, 3, 3, 3, 0 ],
@[ 0, 3, 5, 3, 0 ],
@[ 0, 3, 3, 3, 0 ],
@[ 0, 0, 0, 0, 0 ]
]
let start: Point = (x: 0, y: 3)
let goal: Point = (x: 4, y: 3)
proc print_route(g:AnyGrid, p1,p2:Point):void =
for point in path[AnyGrid, Point, float](g, p1, p2):
echo point
echo "Cost Function 1:"
print_route[GridOne](GridOne(grid), start, goal)
echo "Cost Function 2:"
print_route[GridTwo](GridTwo(grid), start, goal)