Mirror of forum.nim-lang.org

3344 :: About recursive procedural types

• woggioni (orginal) [2017-11-16T22:54:09+01:00] view original

  It seems that it nim it's only possible to create recursive procs not recursive procedural vars e.g.

  this works fine:

  proc fibo(n : int) : int=
      if n > 1:
          fibo(n-1) + fibo(n-2)
      else:
          1
  echo fibo(5)
  Run

  this does not compile:

  let fibo = proc(n : int) : int=
      if n > 1:
          fibo(n-1) + fibo(n-2)
      else:
          1
  echo fibo(5)
  Run

  this is how I implemented a javascript function to gracefully fade out an html element and finally remove it from the DOM:

  proc `[]`*(node : Element, key : cstring) : cstring=
      {.emit: [result, "=", node, ".style[", key, "]"].}
  
  proc `[]=`*(node : Element, key, value : cstring) =
      {.emit: [node, ".style[", key, "] = ", value, ";"].}
  
  proc remove*(n : Node) = n.parentNode.removeChild(n)
  
  proc fadeAndRemove*(el : Element, then = proc() = discard) =
      var opacity = parseFloat(el["opacity"])
      if isNaN(opacity):
          opacity = 1
      var step = opacity / 20
      var cb2 : proc()
      let cb = proc() =
          opacity -= step
          el["opacity"] = $opacity
          if opacity > 0:
              discard window.setTimeout(cb2, 25)
          else:
              el.remove()
              then()
      cb2 = cb
      discard window.setTimeout(cb, 25)
  Run

  It was necessary to use a recursive callback to accomplish this and and I could not declare the proc at module level because I needed to capture local variables el, opacity and step. The workaround I used seems to work (creating an empty proc var cb2 before the real one cb, calling cb2 inside cb and immediately after declaring cb, assigning cb to cb2) but I think it is ugly, is there a better way to do this?

---

• Udiknedormin (orginal) [2017-11-17T04:53:52+01:00] view original

  Let's see what the compiler says to your example:

  rec.nim(3, 9) Error: undeclared identifier: 'fibo'
  Run

  Just what it says. In JS, variables are dynamic. When the function's body is created, it doesn't "know" about the variable it will be binded to but it doesn't matter. Nim is statically typed so it does matter --- it's just like any other undeclared symbol.

  Using a var to forward-declare the function before the body is type-checked solves your problem:

  var fibo: proc(n: int): int
  fibo = proc(n: int): int =
    if n > 1:
      fibo(n-1) + fibo(n-2)
    else:
      1
  echo fibo(5)
  Run

  A little verbose, I suppose, but you can prettify it using future module and templates:

  # using a `var`, it can be rebind:
  import future
  
  template recFun(name, signature, body) =
    var name: signature
    name = signature => body
  
  recFun fibo, (n: int) -> int:
    if n > 1:
      fibo(n-1) + fibo(n-2)
    else:
      1
  
  echo fibo(5)  # 8
  
  # evil rebind:
  fibo = (n: int) => n
  Run

  # Clojure-style recur!
  import future
  
  template recFun(signature, body): untyped =
    block:
      var recur {.inject.}: signature
      recur = signature => body
      recur
  
  let fibo = recFun((n: int) -> int):
    if n > 1:
      recur(n-1) + recur(n-2)
    else:
      1
  
  echo fibo(5)  # 8
  
  # evil rebind prevented:
  # fibo = (n: int) => n
  Run

  Unluckily, you have to specify return type of the body as the compiler is not smart enough to figure out recursive calls' types (please, don't say it should, sometimes it's impossible and would result in an infinite loop it should also notice and break it).

---

• woggioni (orginal) [2017-11-17T08:52:13+01:00] view original

  @Udiknedormin thank for your answer, forward declaring the var seems a much better solution than declaring a second proc var, I think I will simply go that way. The example you posted with templates are very interesting but I think they are a bit overkill. I understand that it is not possible for the compiler to infer the return type of a recursive function as I've already seen it in Scala, but I think it should be able to make the binding if I declare the type:

  let fibo: proc(n: int): int = proc(n: int): int =
    if n > 0:
      fibo(n-1) + fibo(n-2)
    else:
      1
  Run

  this also does not compile and I think it should (it does in Scala), I understand Nim is a statically typed language but all the compiler has to do here is to capture the variable fibo into the closure while creating the proc, it can check its type because it has been declared, it should not need to know which proc the fibo var will contain (even though this could prevent inlining I guess, but for a target like javascript this does not really matter)

---

• Udiknedormin (orginal) [2017-11-17T10:13:25+01:00] view original

  @woggioni Well, I guess Nim's philosophy is different here. If the let-binding exists, it must have a value. But you're in the middle of describing the proc's body so the value isn't ready yet. Why is it practical? Let's say you call a macro from within your fibo's body. A macro on a recursive call, let's say (maybe you want to do some memoization, lazyseq or any other recursion optimization). What now? The compiler would get a symbol for a let binding, which always has a value. But it doesn't have it. The AST is ill-formed. Here is why, I think, it's agains Nim rules to do what you say.

---

• Araq (orginal) [2017-11-17T10:34:16+01:00] view original

  Everything Udiknedormin says here is to the point.

---