Iterators and Generators


#1

Do you mean like documented here?

I’m not even a JavaScript expert and I can probably figure out how to implement an object that satisfies that interface. All generators appear to be are syntactic sugar for writing functions that make it easy to generate the next member of an unbounded sequence when called. Or am I missing something?


Why coffeescript?
#2

Well, not the exact interface because it has new syntax. I also don’t think it’s possible to do a pause/resume equivalent at the semantics level. However, I do believe that any algorithm you can do with generators can be done without them. You have to code in a different mindset but that’s not a problem if you don’t code with generators, like we don’t now.

@carlsmith, give me the smallest code you can think of that requires generators. I’d love to see if I can code the same problem without them that performs mostly the same. I would have no problem eating my words.


#3

Not the declarative syntax, no. I meant the interface of the object returned. Because all I see in the simple example there is:

var gen = idMaker();

console.log(gen.next().value); // 0
console.log(gen.next().value); // 1
console.log(gen.next().value); // 2

So that’s:

  1. A function that returns the generator object
  2. The generator object has a next method that when called returns a value object
  3. The value object has a value property on it that contains the value

In CoffeeScript this would be:

class FooGenerator
  value = 0
  
  next: () ->
    { value: @value++ }

The only thing different is the declaration syntax. I would bet that it is just as performant as well because I suspect that this is the code that is produced behind the scenes when you write a generator.

To be fair and clear, generators (or sequences or whatever you want to call them) do make certain classes of problems easier. But the syntactic sugar is by no means necessary. Also, keep in mind that even though object-oriented programming is just syntactic sugar on top of imperative programming … I’m still a big fan of object-oriented programming and would be loathe to use an imperative language that doesn’t support it.


#4

You have shown an iterator which is what a generator also creates. This is from mdn at https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Iterators_and_Generators

“Generators: a better way to build Iterators
While custom iterators are a useful tool, their creation requires careful programming due to the need to explicitly maintain their internal state. Generators provide a powerful alternative: they allow you to define an iterative algorithm by writing a single function which can maintain its own state”.

I personally don’t find that holding the state is a big deal.


#5

Yep, we’re agreeing. We’re just coming at it from different directions. I’m keying off of the word “necessary” that @carlsmith used, which I took to mean “required to solve a certain class of problems” or “without which said class of problems cannot be solved”. I do not agree that the generator declarative syntax is necessary to solve any class of problem. I do agree that the generator declarative syntax makes solving certain classes of problems simpler.


#6

Iterators and Generators are nothing new. They have a long history in Functional Programming. And I consider the fact that more and more historically imperative languages are subsuming functional concepts to be a Good Thing.

See also:


#7

The problem I mentioned is part of a feature that’s not that important here, so I’ll try and just outline the generator part. Please assume there’s a good reason for doing this in practice.

Imagine you have an array of strings, where each string is some CoffeeScript. For a simple example, ["a=1", "console.log a"].

There’s a need to compile and evaluate each string in order. Each evaluation must be in the same namespace. The evaluation must not be global. The evaluation must have access to the global scope and the DOM [so workers are out].

The obvious thing to do would be to create a function that iterates over the array, compiling and evaluating each string locally. The problem is that the user needs to be able to run the first string, then do other stuff, then whenever they’re ready, run the next string. Using generators, the function could be a simple co-routine that yields undefined after each evaluation, and the UI would call the generator’s next method to run the next string.

Without a generator, it’s difficult to see how you could keep the namespace intact, while indefinitely yielding execution to the main thread on each iteration.

Again, I’m not saying it can’t be done, or that this is a commonplace problem, just that there are times in a single threaded, graphical environment where co-routines are required, or at least very difficult to live without.


#8

I would write it like this. I’m going to use CoffeeScript because it just makes things easier (and shorter :grinning:):

class EvalVisitor
  list = null
  position = 0

  constructor: (@list) ->

  visit: () ->
    codeToEval = @list[@position++]

    # Compile codeToEval
    # Evaluate codeToEval

    undefined

I didn’t call the class EvalGenerator because you’re not really generating anything (and that is what generators are for). And even though it isn’t a strict implementation of the Visitor pattern, I figured that was a better name.

So you create a new instance of the EvalVisitor class by giving it a list of strings to compile and evaluate. Each time you want to compile and evaluate the next one, you call visit(). It returns undefined at the end really just to mimic the generator pattern you mentioned.


#9

So if I do…

e = new EvalVisitor(["a=1", "console.log a"])
e.visit()
e.visit()

…the second instance of e.visit would throw a ref error as it wouldn’t have access to the namespace of the first instance of e.visit, where a = 1 was evaluated. With a generator, you could something like…

runtime = (list) ->
    for item in list
        compile item
        eval item
        yield undefined

e = runtime(["a=1", "console.log a"])
e.next()
e.next()

Now, both strings are evaluated in the same space, runtime.


#10

Ah, good point. I wasn’t looking at the code to be evaluated. And you’re right, this does make things much, much simpler. I’m sure there is a way to hoist the successive call contexts into some previous closure … but yes, I don’t know how to do it either.

Thanks for walking me through it!


#11

No worries. I should’ve probably outlined the problem better in the first place. Thanks for taking the time to look at it.


#12

Yes that example requires a generator. However it also requires an eval which should never be used. Can you come up with an example that runs in strict mode?

In other words that example serves as proof that such an example exists, but it is worthless to convince anyone that generators are needed in real code.


#13

BTW, there is actually a way to meet your needs in that example. It looks something like this (with some pseudo-code):

setup = (list) ->
  compiledList = []
  for code in list
    compiledCode = compile code
    # at this point you extract first line from compiled code that starts with var
    # then for each var you do eval "#{var} = null"
    compiledList.push compiledCode
  listIndex = 0
  next = ->
    eval compiledList[listIndex++]
  next

next = setup ["a=1", "console.log a"]
next()
next()

I know this is ugly but technically it meets your requirements. And your use of eval proves we are just studying technical proofs.

Edits: Fix code


#14

Thanks @mark_hahn, but I don’t think that’d really do what’s needed in practice. Cheers anyway.

On never using eval, Chromium [ergo Opera and Chrome] and FireFox have added features to eval recently, so vendors recognise its useful to developers, and could be better. It’s Chrome’s sourceURL in eval trick that makes it possible for CoffeeShop to name each evaluated string of compiled code, so it’ll be identifiable in tracebacks. There’s a lot of applications that depend on eval ~ IDEs, web shells, online judges, code academies, programming games and then just general applications that support scripting, and there’s libraries that depend on it too.

Either way, it is currently possible to write generators in Chrome without having to use strict mode, so it can be done at least, and would be useful in real code. I put a demo online if you want to play with it (you’ll need to enable Experimental JavaScript Features in Chrome for generators to work).

Thanks again.


#15

As far as I can see, the function * () {} syntax is able to put the function into Extended Mode based on the star. Because the function [now a generator] body is in Extended Mode, it can safely use yield. It’s safe to extend ES5 here even though yield is not reserved in ES5, except in Strict Mode, because the star is invalid in ES5.

There plenty of support for the idea of using Extended Mode to allow ES5 Classic code to work with new features, so older libraries work in modern contexts. This would allow for dropping out of Strict Mode where it doesn’t make sense, without giving up anything that could still work.