HN Explorer

22 comments

[ 3.1 ms ] story [ 63.7 ms ] thread
gravypod
Sadly, a little known construct from javascript that I've fallen in love with is the closure. I feel like it is an easier way of expressing the idea of a generator.

  var fib = (function () {
          let current = 0;
          let next = 1;
          return function (increment) {
                  for (var i = 0; i < increment; i++) {
                          [current, next] = [next, current + next]
                  }
                  return current
          }; 
  })();
This is an example of an implementation of a Fibonacci sequence as shown in this post. The same optimizations still apply, but I think this is nicer (in my opinion) then using yield.

Edit: Altogether, good show. I enjoyed the post.

bruxis
a little known construct from javascript [...] is the closure

o_O

gravypod
Please see my response to cyphar.
cyphar
Closures predate JavaScript by at least 30 years (it's a construct in Lambda calculus which was being discovered in the 60s). Lisp had closures before many of us were born.
gravypod
By from I mean easily represented within.

Most people don't think of a function with an inherited scope as a closure since by the standard PLT people will tell you that Javascript does not provide "real" closures.

I'm sure you know what I meant. It's the "Javascript Way" TM of doing this.

My "little known" I mean that most programmers do not think of doing this out right. It took me seeing an amazing talk by the creator of JSON called "Javascript the Good Parts" to realize how powerful this construct was, and how Javascript made it so easy.

onion2k
People who write JavaScript in the sense of "jQuery with a few native calls", embedded in a webpage, don't tend to use closures, so searching for JS examples doesn't often throw them up. That might give you the impression they're unusual, but if you look at any substantial app you'll see them a lot. In fact, you can take a function closure and turn it in to a JS module that can be used with asynchronous loaders and dependency injection without much extra work - http://ifandelse.com/its-not-hard-making-your-library-suppor...
dionidium
I'm going to push back a little further on this. Closures are fundamental to JS and widely known about and used. Crockford, too, is famous in JS circles, as is the talk you mention.
dvlsg
Closures aside, a somewhat significant difference between the two is that the generator would yield each value in the sequence, whereas yours would just return a single value from the sequence. Which might be perfect, depending on the use case, but they're not quite the same.
PeCaN
No, that would return all of them in sequence via successive calls to the returned function. It's just a ghetto generator anyway.
gravypod
Please see my response to symbiosis
symbiosis
This is just custom iterator/generator. Saw many like this before Babel.

The point is that ES2015 defines clear interface for iterating over iterables. With help of Symbol and *.

If you would use this code in production, probably you would document it: ... returns iterator function.

  next = fib()
  next() // 0
  next() // 1
  next() // 1 ...
But if you would use Symbol.iterator

then you can do

  for (f of fib()) 
    console.log(f)
or use gathering, spreading etc..
gravypod
While I do agree generators offer some amazing features, I think they also offer some complexity that we are currently not ready to handle.

from a given for loop:

  for (x in function())
Please tell me when this for loop will end. You cannot.

If you instead did...

  next = fib()
  while (true) {
    number = next();
  }
You are instantly presented for every case in which this loop will terminate.

Now don't get me wrong, I DO fully agree that a generator is the correct method for doing this, I'm just pointing out another construct to allow you to do this.

stepvhen
One of the exercises in chapter 1 of SICP is writing a Fibonacci function using successive squaring[1]. It's fast, not recursive, and doesn't rely on floating point arithmetic. It would be interesting to see the author's results with a stronger algorithm.

https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.htm...

Johnny_Brahms
I remember trying out different approaches a long time ago, and I believe that the fastest way was through "fast doubling" [0]. I applied FFT-based multiplication to it for larger numbers, and it got really really fast :)

Edit: using karatsuba like the page below is probably preferrable, though.

[0]: https://www.nayuki.io/page/fast-fibonacci-algorithms

bhrgunatha
> it's fast, not recursive, and doesn't rely on floating point arithmetic

I think using 'iter' in the name is misleading. Recursion is a form of iteration. In that exercise fib-iter is recursive - it calls itself. That's the very definition of recursion. I think they use the name 'iter' because the overall process is linear in time the same way an iterative loop in other languages is. In this case it's logarithmic in time. The additional arguments and tail call optimisation (guaranteed by the Scheme standard) avoid a stack of intermediate values so it's constant space as well.

If you delve further it's not actually constant space OR logarithmic times since the numbers get large so fast that storage, addition and multiplication and evaluation are no longer atomic and will have an effect on the time and space characteristics.

Still it's one of my favourite exercise from the book and they use it and reference it in Racket's number theory module.[1]

[1] https://github.com/racket/math/blob/5cc1080d90d2603f790abd41...

jeffwass
>"In that exercise fib-iter is recursive - it calls itself. That's the very definition of recursion."

Yet SICP addresses exactly this point!

The authors still mandate it's not truly recursive in that the required state is passed along to each iterative call.

From the parent's SICP link, but many paragraphs back :

"In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written. It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process."

bhrgunatha
It's been a long time since I read it and I'd forgotten about that explanation. I understand the distinction they are making but it still it seems a confusing use of terminology, especially when you read it out of context - like the comment I replied to.

They were clearly aware of that too ... "It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. "

[dead] throwaway_exer
> Closures predate JavaScript by at least 30 years

Thanks for "being that guy", the pedantic asshole.

HN needs more people like you. Wait, no it doesn't.

tzs
The memoized version does not even remotely work.

  a = fib(5);
  for (i = 0; i < 7; ++i) console.log(a.next());
gives the expected

  Object {value: 0, done: false}
  Object {value: 1, done: false}
  Object {value: 1, done: false}
  Object {value: 2, done: false}
  Object {value: 3, done: false}
  Object {value: undefined, done: true}
  Object {value: undefined, done: true}
But then

  b = fib(3)
  for (i = 0; i < 5; ++i) console.log(b.next());
gives the completely wrong:

  Object {value: 1, done: false}
  Object {value: 0, done: false}
  Object {value: 1, done: false}
  Object {value: 1, done: false}
  Object {value: undefined, done: true}