Arc Forum | Streams

Arc Forum

2 points by malisper 3915 days ago | 15 comments

I wrote a basic implementation of streams/lazy-seqs[0]. Currently it uses a naming convention where an 's' is appended to the beginning of all the functions in order to differentiate between the stream version and the normal function. I was thinking that it may be better to just type tag the streams and then use defextend to extend all of the functions to work on the streams. I realized that there are two issues with this:

1. Tagging: when to tag the streams becomes an issue. They would have to be tagged sometime during scons but problems come up when you have infinitely long streams where they have to be tagged as you access the next element. Also when you are sconsing something onto an actual stream instead of a function that returns a stream you may wind up tagging the stream twice.

2. Efficency: by tagging all of the streams, there would be a pretty large overhead because of the need to access the the actual data that is tagged. When accessing elements that are far down the stream, this extra time can add up.

In order to make way for the convention, I had to rename the original scar and scdr, set-car and set-cdr. There shouldn't be much of a problem there.

Unfortunately I have not written any tests for the streams, so if someone wanted to help, that would be much appreciated.

[0]https://github.com/arclanguage/anarki/blob/master/lib/streams.arc

2 points by zck 3915 days ago | link

Land of Lisp also has a good discussion of this topic, but refers to it entirely as "lazy lists" and the like. I think it also convinced me that I want laziness to be almost transparent, so you don't need to have different functions to work with lazy data types versus strict ones. Of course, I'm not opposed to some sort of library adding them in a way that's elegant, even if that library isn't included in Arc.

I'll have to read this more this later, but if you aren't using a unit test library yet, I'd like to pimp mine again: https://bitbucket.org/zck/unit-test.arc/ . I'm willing to write some tests, but that will have to wait until next week, as I'm away this weekend.

-----

1 point by akkartik 3915 days ago | link

That reminds me: I never did get around to adding your test harness to anarki like I promised. I'll do that if I get around to adding some lazy tests this weekend. Otherwise feel free to do so when you look at this again.

-----

1 point by akkartik 3910 days ago | link

Now that anarki has its first suite of tests using your harness, I've designated all prior tests as "old tests" to encourage us to move away from our patchwork of prior solutions.

https://github.com/arclanguage/anarki/commit/a30d51ce87

-----

2 points by akkartik 3915 days ago | link

Hmm, I think you need to do more to redefine scar and scdr:

  arc> (= x '(1 2 3))
  arc> x
  (1 2 3)
  arc> (= car.x 4)
  4
  arc> x
  (4 2 3)
  arc> (load "lib/streams.arc")
  *** redefining scar
  *** redefining scdr
  nil
  arc> (= car.x 5)
   scar: arity mismatch;
   the expected number of arguments does not match the given number
    expected: 1
    given: 2
    arguments...:
     '(4 2 3 . nil)
     5

The problem is that prior uses of scar and scdr (such as assignment to car[1]) will try to call your version. It's usually a bad idea to repurpose names for something unrelated. At the least we need to go through and fix callers of the old name.

Not a huge deal at the moment since your library isn't loaded by default. So we have some time to think about how to fix this.

[1] https://github.com/arclanguage/anarki/blob/3662afea89/arc.ar...

-----

2 points by malisper 3915 days ago | link

The simplest fix would be to overload scar/scdr based on the number of arguments. While it's a nice quick fix, I do not like the idea of using the same name for two different functions.

-----

1 point by akkartik 3915 days ago | link

Yeah, especially since one of them is destructive and one isn't!

If we can get regular car and cdr to handle lazy streams then this issue will be moot. I'm investigating this. I didn't understand your point 1 above regarding when to tag, so I'm trying to recreate the primes example from SICP 3.5 to better understand the issue.

Can you point me at any sample calls to your library, maybe things you tried on the commandline while you built it?

-----

2 points by rocketnia 3915 days ago | link

Now may be a good time to mention almkglor's lazy list library for Arc 2, which did extend 'car and 'cdr like you're talking about:

https://github.com/arclanguage/anarki/blob/arc2.master/lib/s...

---

Meanwhile, here's a generator library for Arc 2 by rkts: https://github.com/arclanguage/anarki/blob/arc2.master/lib/i...

And here are three relevant libraries I made as part of Lathe:

- A lazy list library, which happens to use a multimethod framework I made: https://github.com/rocketnia/lathe/blob/master/arc/orc/oiter...

- A generator library: https://github.com/rocketnia/lathe/blob/master/arc/iter.arc

- An amb operator library: https://github.com/rocketnia/lathe/blob/master/arc/amb.arc

I've never actually found much use for these, heh.

-----

1 point by akkartik 3914 days ago | link

Thanks for the links! Too bad none of them show example usage.. :) But no matter, I'll add some to this version. It's looking promising so far, I'll push it later today.

One thing I learned from malisper's code was the existence of afnwith in anarki (https://github.com/arclanguage/anarki/blob/87d986446b/lib/ut...), which is a neat alternative solution to my http://arclanguage.org/item?id=18036.

-----

1 point by akkartik 3914 days ago | link

Ok, I've turned streams into a tagged type. I had to just support them in car and cdr and carif to get common list operations to work. However, existing operations still return regular (eager) lists when you pass them lazy streams, so I followed malisper's idea of creating lazy variants that preserve laziness in the result.

I've also added unit tests for them in lib/streams.arc.t, which is my first serious attempt at using zck's nice unit-test harness with suites.

malisper, I took some liberties with your code, such as renaming the 's' prefix to 'lazy-'. I'm not attached to these things, so feel free to revert any of my changes you don't like. Thanks for a fun exercise!

I'm not sure how you're measuring overhead, but let me know if it seems slower than before.

https://github.com/arclanguage/anarki/commit/6180f0e65

-----

2 points by malisper 3914 days ago | link

Why append lazy to the beginning when we can just extend all of them to use scons when given a stream.

-----

1 point by akkartik 3914 days ago | link

Well, you need it for cons and the generator lazy-gen and other functions that don't take a stream. Maybe the others don't, but it seemed to me that sometimes it makes sense to return a list and sometimes not. So especially since functions like firstn do something useful without changing anything, maybe we should keep that behavior around. But it's just an idea. What do you think? Since you're using them for project Euler, it'll be good to hear your experiences.

-----

2 points by rocketnia 3914 days ago | link

I'm a little surprised to see 'afnwith. Anarki also has aw's 'xloop, which is the exact same thing as 'afnwith but with the "self" anaphoric variable renamed to "next".

-----

1 point by akkartik 3914 days ago | link

Ah, that's a much nicer name. I (too) found the presence of fn to be misleading since the afn is called immediately after it's created.

I've deleted afnwith from anarki: https://github.com/arclanguage/anarki/commit/a0052f031

In wart the name can be nicer still -- just loop since for does what arc's loop does, in the footsteps of classical C.

Edit 20 minutes later: I ended up going with recur instead of next, to form a loop.. recur pair. I also considered with loop.. recur to strengthen the connection with with for the alternating var/val syntax. (The other pair of keywords in wart is collect.. yield in place of accum acc.) https://github.com/akkartik/wart/commit/b7b822f4fb has has an example use, which had me hankering for absz's w/afn (though with a better name; http://arclanguage.org/item?id=10125)

Edit 25 minutes later: It turns out xloop nests surprisingly cleanly. This does what you expect:

  loop (a 0)
    loop (b 0)
      prn a " " b
      if (b < 5) (recur ++b)
    if (a < 5) (recur ++a)

Edit 29 minutes later: Oh, loop.. recur is precisely what clojure uses!

-----

3 points by shader 3906 days ago | link

I feel like we need to extend the documentation on arclanguage.github.io to include the extra libraries on anarki, to improve discoverability.

-----

2 points by malisper 3914 days ago | link

I don't know what I was thinking. Of couse we could just tag the streams when they are created with scons. If we really wanted to we could just extend all of the basic operations for working with lists.

There still is the problem of efficiency though. For what I have been using them for (project euler) efficiency is a big deal.

-----