search

nim-lang / RFCs

A repository for your Nim proposals.
136 stars 26 forks source link

can iterators be implemented as a library solution / syntax sugar over regular procs? #272

Closed timotheecour closed 3 years ago

timotheecour commented 3 years ago

see https://github.com/nim-lang/Nim/pull/15655 for a simple macro that allows defining something that acts very similar to an iterator:

Not only that but it solves major long existing limitations with iterators, eg:

this is not a complete 1:1 replacement (see limitations below) but could become one. This could potentially be a basis for replacing iterators with regular procs + syntax sugar, which would simplify nim language by removing all custom compiler code handling iterators.

example 1

import std/iterates

# analog to:
when false:
  iterator myIter[T](s: seq[T]): auto =
    for ai in s: yield ai*10

proc myIter[T](s: seq[T], cont: proc(_: T)) =
  for ai in s: cont ai*10

# analog to:
when false:
  iterator myIter2(a, b: int): auto =
    for ai in a..b:
      yield (ai, $ai)

proc myIter2(a, b: int, cont: proc(a1: int, a2: string)) =
  for ai in a..b:
    cont ai, $ai

template main() =
  block:
    var ret: seq[int]
    # analog to:
    # for x in myIter(@[2,3]):
    #  ret.add x
    for x in iterate myIter(@[2,3]):
      ret.add x
    doAssert ret == @[20, 30]

  block:
    var ret: seq[(int, string)]
    for k,v in iterate myIter2(2,5):
      ret.add (k,v)
    doAssert ret == @[(2, "2"), (3, "3"), (4, "4"), (5, "5")]

static: main()
main()

(EDIT) example 2: recursion

see example showing recursion works in https://forum.nim-lang.org/t/7020#44149

note

limitations

EDIT

nc-x commented 3 years ago

Even if this works, I would prefer the core language to be implemented in the compiler and not through macros (for better compile times and sane error messages), at least unless and until the macros are mapped to compiler plugins which should improve the performance of macros significantly (see v2 milestone), image

Araq commented 3 years ago

D ranges is still the superior abstraction, offering better composition and support for 0-cost lazy functional programming

It's still worse as there is no ownership system so you're left with a tracing GC or more-expensive-than-you-think-it-is reference counted slice type which diverges quite a bit from the naive (ptr, len) pair implementation. Plus writing the code required to support these ranges is much harder to write than using a yield statement.

mratsim commented 3 years ago

I'd like a report on CPS, what was tried, what is missing so far so that we can evaluate this RFC with its most obvious alternative (besides what is implemented today).

disruptek commented 3 years ago

The initial CPS impl in master represents an untyped macro. The tests and demos work.

The typed version (I think it's in a typed branch), solves several performance and ergonomic warts but doesn't work yet due to apparent compiler bugs, at least one of which requires a breaking fix. I think it's in 1.4, but I'm honestly unsure.

What remains to be implemented (or demonstrated, at least):

Maybe @zevv has some clearer ideas about what's missing; this is just the stuff off the top of my head.

I personally really want properly bulletproof concepts so I can play with some ideas for CSP; the abstraction over CPS where we'll implement go-channel/clojure-core.async-type machinery.

zevv commented 3 years ago

Right, @disruptek kind of tells it all. The Nim CPS project is basically an implementation of the mechanics described in the paper "Continuation-Passing C - Compiling threads to events through continuations". Linear Nim code is transformed into a number of separate procs that pass continuation objects among them. What used to live on the stack is now in the continuations, which allows non-linear code flow.

On top of Disruptek's CPS work I prototyped some basic constructs like:

From a technical point of view, this all works, although the syntax is sometimes lacking or plain weird, still.

We are stuck for some time on motivation and a compiler bug, although I'm not even sure at this time what exactly the bug was (something sym vs ident, I believe). I think the goal was to prove this was all feasible and usable, but we already know that a definitive implementation should probably do the transformations in the compiler instead of using macros.

timotheecour commented 3 years ago

Can you share any relevant link? EDIT: links were now added above

zevv commented 3 years ago

TBH: I'm not sure if the above links actually compile with the current state of CPS - stuff was very much in flux, we had a few days of hacking frenzy but broke API's on the way a few times. But I'm sure the above snippets show the gist of what we were trying to do.

disruptek commented 3 years ago

There are two forms of bug that I consider blockers:

timotheecour commented 3 years ago

in https://github.com/disruptek/cps/blob/master/stash/iterator.nim instead of:

var a = counter(3, 7)

# Resume the iterator a bunch of times

var v = a.produce()

echo "produced ", a.produce()
echo "produced ", a.produce()
zevv commented 3 years ago

Hmm, it's all some time ago, so I'd have to get back into all that to tell, but I think with the for loop macro that should work...

Araq commented 3 years ago

This is not an RFC, this is an interesting question.

timotheecour commented 3 years ago

It's not just an "interesting question", the suggestion is that maybe the language can be simplified by mapping (via syntax sugar enabled by the compiler) the existing iterators to a pure library implementation, also fixing https://github.com/nim-lang/Nim/pull/15818 (vm + js not supported) and support for recursion (https://forum.nim-lang.org/t/7020#44149) in the process.

Araq commented 3 years ago

Sure but an RFC is what you write after you have established that it's possible and a good idea. Then you write an RFC to convince others that we should change Nim.