Better generator and iterator support in guile w.r.t. speed

Better generator and iterator support in guile w.r.t. speed

[Stefan Israelsson Tampe]

Hi guilers!

Inspired by wingo's recent blogage on wingolog in combination with my
portings of racket and cl loop frameworks, I did some thinking about 
generators. Especially inlining.

1. Can we make stubs like this inlinable
(iterate (generator g (iterate (for x in l-i-s-t)
                               (when (even? x) (yield (f x)))))
	 (collect (+ (next g) (next g))))

A generator would be somthing like
(define-syntax-rule (generator _thunk)
  (lambda ()
    (let ((thunk (lambda () (_thunk) (finish))))
      (call-with-prompt tag
	 thunk
	 (lambda (k . l)
	   (set! thunk k)
	   (apply values l))))))

(define-syntax-rules (yield x)
  (abort-to-prompt tag x))

With this kind of generator, as wingo says, we will get what we want but 
slowly. Might matter sometimes and not somtimes. What we would have 
liked 
here is some way of noticing that the liveness of "tag" is somewhat 
lexical
and cannot be hidden in f. With that information a compiler would be 
able to
inline code quite efficiently and make extensive use of gotos. How?

Let's see how finish is working
(define-syntax-parameter finish)
(define-syntax-rule (iterate c ...)
  (syntax-parametrize ((finish (syntax-rules () 
				 ((_ x) (apport-to-prompt tag2 x)))))
    (call-with-prompt
        (lambda () loop  code)
	(lambda _  final code))))

This whole setup would then be identified to something like

(seqence
  loop: 
  (with-frame g (generator thunk)
      code ...)
  finish:
  finish-code)

To make the compilation to glil simple we mean by with-frame that
we can setup a stack area where we can inline the thunk code and 
then a call to g like (next g) == (g) we can identify that
1. if (g) returns it will be from the abort clause in the prompt
because the next part will jump to the finish part in the section
which is below the generator frame and then it's possible to mark that
stack space void. 

2 The usage of the continuation is that we overwrite the 
same stack space with continuos versions of k's e.g. this is a 
characterizatin that we can keep the stack as a storage for this 
continuation. 

3 with-frame is not recursive in g e.g. g is not visible inside thunk


4 So we should be able to make this work with intelligent usage of 
gotos. No, (f x) will be a problem because that we cannot know how
much stack-space that function is needing.

5 What is interesting with the rtl format is that function applications 
are setuped at the end of the stack frame. This means that imersion of
a generator is pretty simple using gotos and for rtl we would be able to
manage quite general iterators and inline them with quite simple means.
 
My conclusion is that for wip-rtl we should really start working on a
prompt ideom that is lexical. But is it general enough. probably, but if 
you If you consider the main use case to be inlinable code, 
then you would need to consider the following tree-il extension

(lexical-rec-prompts 
   (name thunk abort-lam) 
   ...)
	 
where name ... is visible inside the thunk's and abort's sections. 
Of cause not all versions of this code will be possible to manage 
without long-jumps and old pompt like features.
(to note, CL's tagbody seams to be a very similar notion)

Am I out in the blue or do you agree?

Cheers Stefan.

Re: Better generator and iterator support in guile w.r.t. speed

[Stefan Israelsson Tampe]

Hi all, 

In my previous mail I did some discussions about what structure to use
in order to allow efficient implementatin og generators and one main
observation is that the curretn rtl strategy can be used.

Now Have you all thought about the stack beeing a must to execute
funcitons. Well we have threads but we can get lightweight in process
threads quite naturally in the rtl version of guile. We could call it
a coroutine and let it be an object

co = (code,stack,ip,outer-stack)

The idea here is that the code will have a fixed sized stack that is
just enough room to store all locals and intermediate variables
e.g. all the registers needed to execute the function. Any call would
then need to hook onto the outer stack. The stack is typically of the
form
stack =
 
[IP
 OUTER-FP
 LOCALS
 ...]

At the creation, IP points to the starting code position and then
after each exit the next ip is stored in IP and so on.

To support this we need a few new operations
* MULTIMOVE,       from the local stack to outer stack
* MULTIMOVE,       to the local stack from the outer stack
* OUTER-TAIL-CALL  This re-uses the outer call frame used to call this
                   coroutine and resets the IP to the initial value
* OUTER-CALL       This will setup a new call frame on the outer stack
                   execute the function there
* RESET-IP         RESET the IP value to the initial start value
* STORE-IP         Store an local ip adress in IP using a label.
* OUTER-RETURN     Simply return using the OUTER-FP and make sure 

* CALL-CO          This will call a CO routine by setting up the 
* TAIL-CALL-CO     call frame or reusing the current one (in tail 
context)
                   then set the OUTER-FP and jump to the IP value if a
                   number else throw an error. And then setting IP to
                   #f and start executing
  


This will probably work quite ok. But the question is how well it play
with call/cc and classic prompts as well as usage of the same object
many times. 

1. This object can only be located one time in the stack because when
in use IP = #f and another application of the object down the stack
would throw an error at the application

2. call/cc prompt code dynwinds and fluids inside co needs to have
special versions

3. When one store the stack space one need to make sure that the co
routines also get copied.

To note is that these objects should be able to live immersed in the
stack space for quick allocation when we inline them inside functions.

----------------------------------
Anyway I will explore this concept semewhat more and see if all scheme
features can be made to interop in a good way with it.
----------------------------------

I would also come back to the question if we should have a special
tree-il concept that can be used to model this behavior. I'm now
inclined to concider something like.

(lexical-prompts
    ((g #:exits     (a ...) 
        #:body      (th thunk)
        #:exit-case (((a) (lambda (k kind arg ...) code2)) ...))
     ...)
  code ...)
    
The default expansion of this woule then be something like
(letrec  ((g . l)   (let* ((tag (make-tag))
	 	         (th  thunk))
	           	 (call-with-prompts tag
		      	 (apply th l)
		      	 (lambda (k kind arg ...)
		         	 (case kind ((a) code2 ...) ...)))))
          ...)
   code ...)

So if we can prove:
1. The only references of g ... inside th is through e.g. (a g arg ...)
   where we mean ( g arg ...) = (abort-to-prompt tag 'a g arg ...).

2. these (a ...) forms is not included in any lambda definitions or
   entering any funciton via it's argumnets.

3. g is never feeded as an argument to a function or located inside a
   closure definition anywhere in the form.

4. in ((code2 ...) ...) ... any applications of g ... is located in
   tail position.

5.th is always setted to either k or the initial thunk or never setted
  in any of the ((a) ...) forms.

with these things satisfied we should be able to inline the co routine
or generator inside of the function with quite good
characteristic. This is interesting this should be a logically step up
in generality from CL's tagbody.

Of cause there is a lot of substructure and combination of the general 
construct.

From the rtl code we would manage just ok with the old instructions
just fine except for the need to be be able to store a label value and
goto to a stored label value aka named goto.

WDYT?

/Stefan