SRFI 41 for Guile

SRFI 41 for Guile

[Chris K. Jester-Young]

Hi all,

Just writing to say that after many months of being busy with other
stuff, I finally got around to finishing my Guile port of SRFI 41:

https://github.com/cky/guile2-modules

Basically, both the code and the tests are based on the reference
implementation, albeit with somewhat significant changes (as Andreas
Rottmann pointed out ;-)) to make better use of Guile's features:

+ The tests use Guile's (test-suite lib) test framework.

+ define*/lambda* is used for handling optional arguments, rather than
  manual argument unpacking. In the odd case of stream->list where the
  optional argument is the leftmost one, I used case-lambda instead.

+ Guile's SRFI 45 is used directly, rather than reimplemented as in the
  reference implementation.

+ stream-match and stream-unfolds are complete rewrites. stream-match
  uses (ice-9 match), and stream-unfolds uses (ice-9 q) to store the
  unread results.

+ stream-constant uses circular-list to hold the values of interest,
  rather than...whatever the reference implementation does with append
  (see for yourself, if you're curious ;-)).

The long and short is that whatever functionality is covered by an
existing Guile module or builtin feature, I tried to make the best use
of it. Still, I don't know every Guile module there is, so if I missed
something, please let me know!

Before anyone asks, though, I can't use (ice-9 streams)---it works on
a very different streaming model from SRFI 41, as explained in the
latter's introduction.

Comments are very welcome. :-)

Enjoy!
Chris.

Re: SRFI 41 for Guile

[Ludovic Courtès]

Hello!

"Chris K. Jester-Young" <cky944@gmail.com> skribis:

> Just writing to say that after many months of being busy with other
> stuff, I finally got around to finishing my Guile port of SRFI 41:
>
> https://github.com/cky/guile2-modules

Nice, thank you!

Could you integrate it in the Guile tree in a branch, as you proposed on
IRC?  It would make it easier to review it.

What you be OK with assigning copyright for your changes to the FSF?

Also, to what extent is the reference implementation modified?  If the
modifications are well isolated, it would be nice to see if we could
import the upstream files unmodified, and then just “patch” them at
compile-time as is done for match.scm, sxml-match.scm, lalr, and a few
others.

Likewise, it may be possible to adapt the original test suite just by
defining macros that map the expected test suite API to Guile’s.

The idea is that it would make it easier to see how Guile’s
implementation differs from upstream, and to update Guile’s copy
eventually, if needed.

What do you think?

Also, what about moving all or most of the code in srfi-41.scm, instead
of having several helper modules?

(This has been partly discussed on IRC while I was writing this
message; I hope it’s still relevant.  ;-))

Thanks,
Ludo’.

Re: SRFI 41 for Guile

[Chris K. Jester-Young]

On Wed, Dec 14, 2011 at 03:28:07PM +0100, Ludovic Courtès wrote:
> Could you integrate it in the Guile tree in a branch, as you proposed on
> IRC?  It would make it easier to review it.

Indeed. I might only get to do that in the weekend, and with Christmas
and all that coming up, I can't even promise it'd get done this weekend.

> What you be OK with assigning copyright for your changes to the FSF?

Of course! Just for the record, I've already signed all the necessary
paperwork, but you knew that already. The copyright notices will get
updated when they go "in-tree".

> Also, to what extent is the reference implementation modified?  If the
> modifications are well isolated, it would be nice to see if we could
> import the upstream files unmodified, and then just “patch” them at
> compile-time as is done for match.scm, sxml-match.scm, lalr, and a few
> others.

The changes are very extensive. Almost no function was left intact,
except perhaps the stream-of macro. (It stuck out as one that I wasn't
able to "do better" on.)

I chose to do this because I don't expect the reference implementation
to receive any maintenance at this stage. This is in contrast to the
modules you mentioned above, where you do want to touch base with
upstream from time to time, so leaving them unchanged would reduce the
maintenance burden.

In the case of SRFI 41, I would expect that we'd have an independent
implementation that would become its own thing, and eventually diverge
more and more from the reference implementation as we find things to
improve. Again, this is because I feel the reference implementation
is no longer maintained.

The most important change is that any place where some function can use
another module to do its work, I choose to use the external module to
do so. A prime example is SRFIs. Whereas the reference implementation
goes to extraordinary lengths to avoid depending on other SRFIs, I do
the opposite, and use any and all SRFIs available in Guile that do the
job. For example, I use Guile's SRFI 45 for lazy promises instead of
replicating the whole thing as the reference implementation does.

Other than that, for most functions, the changes followed a predictable
pattern, which didn't change the logic at all, but rather just made the
functions easier to read (for me, at least).

In particular, the reference implementation uses this format:

    (define (stream-foo strm)
      (define (stream-foo strm)
        ...)
      (if (not (stream? strm) ERROR))
      (stream-foo strm))

I use this format instead:

    (define (stream-foo strm)
      (must stream? strm)
      (stream-let recur ((strm strm))
        ...))

The latter is better, in my view, because I don't have to remember that
inside stream-foo, there's an internal binding for stream-foo that
shadows the outer one. stream-foo means one thing only.

stream-drop-while and stream-reverse are further refactored to use a
new stream-do macro.

All the eager-folding functions (stream->list, stream-drop, stream-fold,
stream-length) are refactored to use a common stream-fold-aux function.
This reduces code duplication quite a bit.

For functions that take 1+ streams (stream-for-each, stream-map), I
used case-lambda to both optimise for the one-stream case, and to block
calling the function with no streams.

The above covers changes that don't change the actual logic, they just
reformulate it in a different way.

There are also functions where the actual logic is changed, particularly
stream-constant, stream-match, and stream-unfolds. Those do not bear any
similarities to the reference implementation; they are indeed complete
rewrites. You will want to review those in full.

> Likewise, it may be possible to adapt the original test suite just by
> defining macros that map the expected test suite API to Guile’s.

This is hard, for several reasons.

Guile's test framework has labels for each test, to easily identify
which ones fail. The reference tests do not have such labels. Coming
up with good labels is not something a macro can do, I believe. In
particular, I don't think a stringification of the form under test is
a good, human-readable label.

Also, Guile's test framework has explicit functions for testing for
expected exceptions. The reference tests do not. They simply catch
exceptions, return the message string, and the tests simply expects
the message string. It works in a pinch, but is nowhere as useful as
Guile's pass-if-exception.

There are a number of tests that test whether a given stream has the
expected contents. The reference tests use stream->list to materialise
the whole stream, then compare to the expected values. I don't do that.
Instead, I wrote a stream-equal? function that stops as soon as the
first mismatched element is found.

> The idea is that it would make it easier to see how Guile’s
> implementation differs from upstream, and to update Guile’s copy
> eventually, if needed.

As stated above, because my intention is for Guile's version to be
independent of upstream, my stance is that if the tests do test
everything in the reference test suite (and they do, and some more),
and they all pass, then it's a valid implementation.

When I first started the port, I wanted to be as faithful to the
reference implementation as possible, just to reduce my work. However,
when I realised that it basically reimplemented most everything already
available in Guile modules, I decided that using the modules is more
appropriate. Then updates to those modules would benefit SRFI 41 too.

Case in point: (ice-9 match) still gets upstream updates. By using that
module for matching, we get all its future benefits for free.

> Also, what about moving all or most of the code in srfi-41.scm, instead
> of having several helper modules?

I don't oppose this per se, but I should state for the record what the
purpose of the primitive/derived split is.

(streams primitive), as it's called in SRFI 41, provide the basic
operations needed to have streams. It's totally bloat-free, and if you
want to create your own stream utility module, you would import just
this module.

(streams derived), as it's called in SRFI 41, provide utility functions
and macros atop the (streams primitive) streams. Most end-users will
want to import this module, but it's probably a bit bloaty for stream
library authors to use.

So, while I don't oppose moving all of the _implementation_ into the
top-level (srfi srfi-41), it'd be good to retain the primitive/derived
submodules that can be used to do selective imports of (srfi srfi-41).
That way, people who want bloat-free can do so without having to rewrite
their own import lists.

(In so saying, (streams derived) isn't very useful without (streams
primitive), so perhaps a (srfi srfi-41 derived) selective import module
is probably not useful, and people should just import (srfi srfi-41)
straight. But (srfi srfi-41 primitive) is still, IMHO, useful.)

> (This has been partly discussed on IRC while I was writing this
> message; I hope it’s still relevant.  ;-))

Sure; if nothing else, this puts the whole conversation "on the record".
:-)

Cheers,
Chris.

Re: SRFI 41 for Guile

[Andy Wingo]

Cky!  Clearly I should have finished ploughing through guile-devel
before we had the pleaseure of meeting up last week.  Because if I had,
I would have asked you to deliver two files: srfi-41.scm, and
srfi-41.test :-)

WDYT about that? :-)

Andy
-- 
http://wingolog.org/

Re: SRFI 41 for Guile

[Chris K. Jester-Young]

Hi Andy,

On Sat, Jan 07, 2012 at 01:47:29AM +0100, Andy Wingo wrote:
> Cky!  Clearly I should have finished ploughing through guile-devel
> before we had the pleaseure of meeting up last week.  Because if I had,
> I would have asked you to deliver two files: srfi-41.scm, and
> srfi-41.test :-)

Wow, I must have fallen off the edge of the world for the last 3+ weeks,
as I'm only just (vaguely) catching up with the list now. ;-) I haven't
forgotten about this. While I can't promise for it to be completed this
weekend, I will work on this as I find time to.

It was good meeting up! Hopefully we'll get another chance to do so. :-)

Cheers,
Chris.