When is a recursive function not a recursive function? | Hacker News Reader

When is a recursive function not a recursive function?

russet.org.uk

31 pointsr4um20 comments

That's the usual late-binding semantics for global functions in Lisp.

Note that in Common Lisp a compiler can assume that the recursive call is actually the same function:

> Within a function named F, the compiler may (but is not required to) assume that an apparent recursive call to a function named F refers to the same definition of F, unless that function has been declared notinline. The consequences of redefining such a recursively defined function F while it is executing are undefined.

I've always thought that in languages where functions are first-class, a function referring to itself via a name binding is strange, since the function is supposed to be a value just like any other. Values like 33 or the list of foo,"bar",7.5 aren't aware of which names (if any) are bound to themselves and that's how it should be.

The so-called recur* in the post sounds like an improvement.

well technically they aren't aware of it, just like literals aren't necessarily aware.

But when you write the code, that resolution happens. So when I write:

f x = if x=0 then 1 else f (x-1)

it looks at the definition and resolves the naming of f at that moment. Just like it does for x.

The idea that the identifier f is referring to "whatever f is bound to at the moment this function is run" seems extremely scary: the obvious alternative is to simply pass in a continuation!

Given the simple alternative, I can't see anyone defending the behaviour described in the article.

This is a non-issue if those languages are also pure, so that the name binding cannot be redefined.

Part of the reason why the function is called "first class" is that it has a captured environment. And that name binding which it is using to refer to itself is just an element of that environment: in other words, it comes from the function itself.

If you have some built in means for self-reference, like some special (self) expression or special symbol or something, that is possibly going to be implemented as some hidden symbol in the function's environment anyway, or a hidden parameter.

You can go the opposite direction: Why do only functions get to refer to themselves in their definitions?

    ones :: [Integer]
    ones = 1 : ones

There. That's valid Haskell. A non-function value whose definition depends on itself. Haskell doesn't have a rule that functions are privileged, and get to be the only bindings that get to refer to themselves. And that's really handy - though the simple examples like that one are kind of contrived, it can pay off big time in more complex cases.

Because selfreference is meaningless for something that isn't a function in the usual sense of the word. Your example only shows that "lists" in Haskell really are functions, or at least what you would call an iterator or enumerable in other (non-lazy) languages.

Not so at all. As soon as the runtime decides to head-normalize the "second" element of that list, then there are no more thunks left to evaluate; ones ends up being a circular data structure that you could have written in C. Self-reference is no more meaningless in Haskell than it is in C; that is, it's perfectly well-defined, a pointer back onto itself.

Cf. Scheme: (define list (cons 1 '())) (set-cdr! list list) The only difference with the Haskell is that it requires no mutation (and the same difference exists between Haskell and C). Insofar as that is the case, I suppose you're right in that self-reference by name requires thunks, which are kind of like functions, but not really...

It works in OCaml too, where lists certainly are not functions!

    let rec ones = 1 :: ones;;

I don't know OCaml, but logically it cannot be an actual realized list as the would take up an infinite amount of memory. Whether or not it acts like a function in the language wasn't really the point - internally it must still be an iterator unless you have a computer with an infinite amount of memory.

It's not a function, an infinite list or an iterator. It's a cyclic linked list.

Functions referring to themselves by name is what allows Erlang's hot-code-upgrade to happen.

There are two types of function call opcodes in the BEAM VM: local calls, which call a function by offset within the same module they're defined in; and remote calls, which store module and function name symbolically, and pass them off to the code server to dereference.

All you have to do is update which module is referred to by a given symbol in the code server's module table, and then all remote calls to that module will jump to the new module's code instead of the old one's. Since the idiomatic way to define an Erlang process is in terms of a message-loop step function that makes a remote recursive-tail-call to itself at the end, each process will silently "jump into" the newest version of its module code after each message-loop step.

(Possibly more interesting for some of you is the fact that all loops in Erlang are defined in terms of tail-call-optimized recursion—even infinite loops, such as process message-loops. This means that a function body can be guaranteed to run in O(1) time, since it will have to make a call (either a tail-call or a regular stack call) to continue processing—which allows the scheduler to just reschedule at call-sites, rather than having to preempt functions in the middle of possibly doing something atomic.)

TL;DR:

(defn foo baz)

does not mean the same thing as

(defn (foo n) (baz n)) == (defn foo (lambda (n) (baz n)))

because in the former case baz is dereferenced when foo is defined and in the latter case it's dereferenced when foo is called. So in the former case, if baz changes between when foo is defined and when it is called, you'll get surprising results.

cdown is not "no longer recursive"!

It is either "still recursive" or "never had been recursive" depending on your point of view.

Evidence for "still recursive": when you call it, the countdown is consed up.

Evidence for "never had been recursive": nowhere in the code was there ever a call to cdown, other than the top-level one.

> (def cdown #'countdown) ... This works but is rather counterintuitive; with a Lisp-1 you get used to refering to functions directly rather than with a quoted symbol, but here we have to use both a quote and a #.

It is counterintuitive not because of Lisp-1 versus Lisp-2 but because in (def cdown countdown) the symbolic reference to the function countdown is immediately evaluated to an object that is bound to cdown, such that cdown doesn't follow a redefinition of countdown. Yet, in (def cdown #'countdown), the #'countdown is deferred so that the countdown symbol is re-evaluated. This means that def has strange evaluation rules, or that #'countdown has nothing to do with the Common Lisp #'countdown: namely, it produces some kind of proxy object which resolves to a function, using late binding with a symbol that is captured in its innards. Or possibly #'countdown produces a wrapper function which takes the call and defers to countdown, by symbol. That's what is "counterintuitive": that countdown and #'countdown do not evaluate to the same thing based on experiences with some other dialect.

This is a good example of why it is better to be lexically scoped (at least by default, with a possible way to escape that). But I would have thought that clojure would be. Is it really not?

It is, but in this case the variable is in global scop rather than lexical. You get the same behaviour if you translate the example into e.g. Scheme.

The issue is that the name referred to in the recursive call is a global variable access, and so redefining the value of that variable produces some strange effects. However the simple solution to this (which basically boils down to having no global variables, just lexical variables at the top level) has other problems -- it would require that every function be defined before it is used, which would enforce a bottom-up ordering to the file. If you want to be able to place the definitions in the file in any order, and you want to have the ability to redefine functions, then this is pretty much inevitable (even if you special case simple recursion like this, you probably can't reasonably deal with mutual recursion).

If you need to refer to a particular function without the risk of it being redefined, it is possible (at least in Scheme) by abusing let and set! a little...

  (define countdown #f)

  (letrec ((cd
             (lambda (n)
               (if (> n 0)
                   (cons n (cd (- n 1)))
                   '(liftoff)))))
    (set! countdown cd))

I don't know Clojure enough to say what the equivalent would be, but it should make sense anyway (the (define x #f0) ... (set! x y) is to produce a top-level definition of x).

In this case, the recursive call is to a lexically scoped variable inside the let, that is then preserved in the closure, thus the closure will always call itself regardless of what is done to the names at the top level. You can also use the Y combinator to do it (again, the recursive call is made to a variable in lexical scope rather than global scope).

My brain automatically refactors what you wrote into the following:

  (define countdown
    (letrec ((cd
              (lambda (n)
                (if (> n 0)
                    (cons n (cd (- n 1)))
                    '(liftoff)))))
      cd))

Which should be equivalent. As for what Clojure provides, the Clojure docs say this: "No letrec, labels or flet - use (fn name [args]...) for self-reference, letfn for mutual reference. Thus, this would be the Clojure version:

  (def countdown
    (fn cd [n]
      (if (pos? n)
          (cons n (cd (- n 1)))
          '(LiftOff))))

In fact, it also works to use the name "countdown" in the fn form. You could define your own version of "defn" that used fn like this, to make internally self-recursive functions (as opposed to ones that go through the current global binding of the function's name) by default. I am not actually sure that this is a bad default behavior. (The main problem that comes to mind is if someone replaces it with a "traced" version, that debug-prints its arguments in addition to what it normally does, and expects to see debug-printing of the recursive calls.)

I see, thanks for the clarifications.

> having no global variables, just lexical variables at the top level

That is what OCaml does. Compare Racket:

    Welcome to Racket v5.3.6.
    > (define (countdown n) (if (> n 0) (cons n (countdown (- n 1))) '(LiftOff)))
    > (countdown 10)
    '(10 9 8 7 6 5 4 3 2 1 LiftOff)
    > (define cd countdown)
    > (countdown 10)
    '(10 9 8 7 6 5 4 3 2 1 LiftOff)
    > (cd 10)
    '(10 9 8 7 6 5 4 3 2 1 LiftOff)
    > (define (countdown n) (if (> n 0) (cons n (countdown (- n 2))) '(LiftOff)))
    > (countdown 10)
    '(10 8 6 4 2 LiftOff)
    > (cd 10)
    '(10 9 7 5 3 1 LiftOff)

to OCaml:

            OCaml version 4.01.0

    # let rec countdown n = if n > 0 then n :: (countdown (n - 1)) else [0];;
    val countdown : int -> int list = <fun>
    # countdown 10;;
    - : int list = [10; 9; 8; 7; 6; 5; 4; 3; 2; 1; 0]
    # let cd = countdown;;
    val cd : int -> int list = <fun>
    # cd 10;;
    - : int list = [10; 9; 8; 7; 6; 5; 4; 3; 2; 1; 0]
    # let rec countdown n = if n > 0 then n :: (countdown (n - 2)) else [0];;
    val countdown : int -> int list = <fun>
    # countdown 10;;
    - : int list = [10; 8; 6; 4; 2; 0]
    # cd 10;;
    - : int list = [10; 9; 8; 7; 6; 5; 4; 3; 2; 1; 0]

which is way better in the "principle of least astonishment" department (at least in that case).

Why would you alias your functions? I don't write in clojure, but I haven't encountered it in java/javascript/c++/Matlab

Because of clarity ?

A function can have a really broad use, and the particular use case is unclear when you call it. In this hypothetical but likely situation, aliasing the general function to a more-specific name is good neighbor behavior, isn't it ?

Note that it's particularly frequent when you are used to code with lot of purity and high-order applications, when you define few pure functions with lot of parameters and specialize them in your modules by fixing some of the parameters. Sometimes you don't want to (or can't) fix a parameter but still want the function to have the specialized name.

The aliasing is just an example. The real use case involved pulling functions out of a map.

The main use of "aliasing" is to alias a namespace (to save typing) or to rename a function from one namespace where it clashes with one in local.

Reply on news.ycombinator.com