4 ms·

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 suppo

by frou_dh 12y ago

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.

rtpg 12y ago
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.
kazinator 12y ago
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.
chowells 12y ago
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.
- poizan42 12y ago
  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.
  - belovedeagle 12y ago
    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...
  - tome 12y ago
    It works in OCaml too, where lists certainly are not functions! let rec ones = 1 :: ones;;
    - poizan42 12y ago
      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.
      - tome 12y ago
        It's not a function, an infinite list or an iterator. It's a cyclic linked list.
derefr 12y ago
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.)

by frou_dh 12y ago

rtpg 12y ago

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.

kazinator 12y ago

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.

chowells 12y ago

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.

poizan42 12y ago
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.
- belovedeagle 12y ago
  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...
- tome 12y ago
  It works in OCaml too, where lists certainly are not functions! let rec ones = 1 :: ones;;
  - poizan42 12y ago
    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.
    - tome 12y ago
      It's not a function, an infinite list or an iterator. It's a cyclic linked list.

derefr 12y ago

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.)