Iterator-based programming vs. functional programming

Ecosystem
1

[This is just a little “trip report” from my time programming in Rust. A top-level observation that I would make: OCaml programmers ought to have a look at Rust. It’ll convince you that the OCaml way of thinking is completely applicable to low-level high-performance systems code. Great stuff.]

Lately I’ve been writing a lot of code in Rust, for a project that requires high performance and multithread-capability. It also … well, it’ll tax the memory of the 6TB 32-core machine I have available (and need all the cores), so there’s that, too. In the past, I would have written such code in C++, but after 2.5 weeks of programming in Rust, I’ve changed my mind completely, and now Rust is a tool in toolbox. But that’s not the subject of this post (and question).

Instead, I’d like to focus on one particular aspect of Rust: the heavy use of “iterators” and “iterator transformation”. They seem the achieve the same things we in FP-land do with our map-then-map-then-concat style of programming, but without all the intermediate construction of lists. In short, a bit of sort-of-automatic deforestation. [ok, ok, I’m no longer a PL guy, so that’s just random brain-fart] Necessarily, this also implicates Rust’s “traits”, which are a version of typeclasses. I hope these snippets are comprehensible …

  1. First, some variables:
z: &Vec<bool>,
x: &Vec<bool>,
coeff: Complex64,
phase: i64,
group_phase: bool,
twos_array : Vec<u64>,
indptr : Vec<u64>
  1. iterate over x (with indices), filter out only true bools, map those indices thru twos_array, and add up the values.
            x.iter().enumerate()
            .filter(|(_,x)| **x)
            .map(|(i,_)| twos_array[i])
            .sum() ;
  1. iterate over indptr, checking a predicate on each value and producing coeff or -coeff, then collect into a vector.
            indptr.iter()
            .map(|ind| {
	        if (ind & z_indices).count_ones() % 2 == 1 {
		    -coeff
	        }
	        else {
		    coeff
	        }
            })
            .collect() ;

There’s lots more, and much more complicated. The interesting thing to me, is that even though the implementations of these iterators and iterator-transformers are imperative, the code one writes seems amenable to referential transparency-style reasoning. Part of why, is that these mutable values are only ever owned by one owner (Rust’s type system guarantee) and so lots of things that we would do by creating new values, Rust does by modification-in-place.

This also brings in the heavy use of typeclass-like “traits”, and the way that something like

a.f1(args1).f2(args2).f3(args3)

is not compiled like

a |> f1 args1 |> f2 args2 |> f3 args3

(that is, f3 args3 (f2 args2 (f2 args1 a))) but rather more like
f3 (f2 (f1 a args1) args2) args3
One could imagine a bit of new syntax, |.>, with syntax rule
a |.> f b c d rewritten to f a b c d, and in combination with modular implicits, maybe you could do this style of programming in OCaml. Of course, without the “one owner” typing rules.

OK, so that was a bit rambling. I throw this out, as a long-standing “value-oriented programming” aficionado bigot, who sees this new (to me) style of programming and sees great value in it. And I wonder if others see the same thing.

7 Likes
2

The rust iterators are very nice indeed, and the use of a trait with default methods where you just have to define next to get them all for free, is great ergonomics.

For the deforestation aspect, I personally hope that the standard Seq.t will get more and more optimized in the future. Flambda2 might be able to inline it better, for example. That said it already has the property that it doesn’t allocate full intermediate results and you can write the same chaining as in rust, with potentially infinite results, as long as you consume a finite prefix.

6 Likes
3
  1. yes, compiler improvements to avoid allocation and do more inlining will be great stuff.
  2. even so, the way that you can write this code today, and without such compiler improvements, to get the same result (no intermediate aggregates constructed) is great. At the cost of mutability in the Iterator structs, sure.
  3. and of course, to make all this work without intolerable verbosity, typeclasses traits modular implicits seem mandatory.
4

I write quite a bit of OCaml code in this style, and I’ve come to really like it. Iter.t style iterators suffice for the majority of my use cases, and they’re very efficient. I like that I can write data structure transformations in multiple steps without feeling like I’m paying a performance penalty for all of the intermediate allocations.

You might be interested in index (streaming.index). It’s a little more sophisticated than Iter, and lets you avoid mutation in more cases. Trying it out has been on my todo list.

9 Likes
5

In fact this is exactly what @bobzhang implemented in ReScript: Pipe | ReScript Language Manual (OCaml syntax operator is |.).

2 Likes
6

For the second time in as many months, I am feeling a great and pressing need for modular implicits.

grin

4 Likes
7

I’ve been doing a ton of Rust work myself of late, and it’s a really interesting language. The stacked iterator style is indeed very powerful. Also, the presence of typeclasses makes me yearn yet more for modular implicits.

8

An email I sent a friend about my Rust odyssey. I wonder what you think of it, @perry .

In every GCed language I’ve ever known of, the default is “boxed”. Got a type of struct? The fields are pointers (or primitive ints). Got a type of array of that struct? the array entries are pointers to blocks, one for each struct. Etc. Boxes everywhere. And it is well-known that boxing isn’t free. OCaml floats are the full 64 bits – no room for a bit saying whether the datum is a pointer or a primitive value. So by default, a float is boxed. But OCaml has a hack where they can have special “float arrays” that are unboxed, which saves enormous memory and instruction-count. Critical for making any sort of numeric code not suck. Just an example. There are a ton. Java has had this problem too – I remember me and P.A. were trying to figure out how to do unboxed structs in Java: it was a PITA and it sucked.

There was an attempt to build an ML compiler at CMU, called “TIL” (IIRC, “typed intermediate language”). The idea was what they called "nonparametric polymorphism. So a function that takes array could be compiled into multiple versions, one for array<struct{int, int}>, another for array, another for array (for all the rest). The idea being that along with the type-parameter, flowed “boxing information”.

It worked, from what I remember, but never caught on.

Time passes, and Rust comes along. And in Rust, everything is unboxed except for a few types: “Vec”, “Box”, “Rc”, “String”, a few others. Everything else is unboxed. And there’s even a “trait” that you can put on a type, that demands that its size be known at compile-time (“Sized”) to facilitate this. So what’s the point of this? Well, Rust tries to put everything on the stack. Everything. And when you have a Box, that Box … tries to have everything in the tree beneath it, all unboxed in the block it points at. So Rust privileges and biases toward unboxing everywhere. Boxing is what costs you thought and care and preparation.

This is a fundamentally different way of organizing code (and probably, your compiler too). And I wonder if it accounts for much of what makes Rust so fast.

9

This response is meant for Chet since he asked and made public so that others can see it. I seriously considered making it private but did want Chet to be able to share it as needed so am leaving it public. As such if I only reply to Chet don’t take that the wrong way.

I don’t do Rust yet, mostly Prolog these days, but having spent decades doing imperative coding (C) then objects (Java) then functional (F#) and now logic (Prolog) at every progression learned more impressive ways of transforming complex data. Currently my favorite way is to use Definite Clause Grammars (DCG) which often look and act like BNF. An example I posted a few days ago is here, notice how the code looks a lot like BNF and even has regular expressions for * and + in the example code. However one really interesting piece is the construction of a decimal number, (integer, ., integer) which if you can think of the open list like pointers is just constructing the decimal number via pointer manipulation. NGINX does something similar with pointer manipulation instead of string copying for speed.

While I mostly work with SWI-Prolog, the noted example was posted for Scryer Prolog which is being written mostly in Rust.

So while you are noting iterators, reason with iterators beyond one level and one type. In Prolog you can even think of an unbound variable as a type. As a matter of fact one can create Red-Black trees with the key being unbound variables that can latter be bound. (ref).

So now you know what I see (think) that is similar.

10

There’s been some work on getting more support for unboxed types into OCaml (see RFCs/unboxed-types.md at 881b220adc1f358ab15f7743d5cd764222ab7d30 · ocaml/RFCs · GitHub). I hope that it eventually makes its way upstream, because I think there are some exciting performance opportunities.

1 Like
11

Just an FYI, “nonparametric polymorphism” is, from what you describe, probably polymorphism by polyinstantiation, in which specialized functions are created at compile time for the types that are actually seen?

Generally, Rust has a lot of advantages. Precise memory management, no boxing, an LLVM based compiler (much slower than the OCaml compiler but much more thorough and it takes advantage of modern stuff like vector instructions in modern processors), much more use of the stack, mostly polyinstantiation (you can request run time type resolution if necessary but it’s rare), etc.

12

Something like that. It’s been forever since it all happened, but more-or-less yeah.

The thing that impresses me about Rust, is not just that it does this specialization at polymorphic instantiation sites, but that the “default to unboxed” strategy seems so effective.

That said, I’m not giving up on “ref(any)”. It seems clear that at some point of complexity, Rust gets more and more painful, where languages like ML just keep on scalin’.

3 Likes
13

As a no-GC language, that’s natural, right? C/C++ have the same bias (even more so since they lack Rust’s ‘static GC’).

14

To correct the impression that all this is new in Rust, old C++ was already based on unboxing and stack allocation by default, template monomorphisation, ownership via destructors, and since C++11 move semantics with unique pointers (automatic memory management) and efficient lambdas. All this is explicitly taken by Rust straight from C++ (but Rust manages something that C++ could not, which is to bring the nice feeling of “when it compiles it works” from OCaml). In fact it is likely that Rust was partly influenced by the capabilities of its LLVM back-end, which has supported C++11 early-on.

But I must be missing part of the message since Chet is a much more experienced C++ programmer than I am. What am I missing, that you see in Rust but not in, e.g., C++11?

1 Like
15

Go-lang at least purports to favor unboxed values, and attempts to keep things on the stack (IIUC at least)

1 Like
16

YES! Precisely my point! YES! [BTW, I’m not disagreeing with anything you wrote. It’s all true. And also, I fully agree that C++ let’s you do all that unboxing and stuff. But it’s not a language with safe pointers now, is it?]

Back in 2016, somebody asked me what I thought of Rust, and I pretty much answered this: “I already know C++, and have written sizable codes in it, hacked in massive C++ codebases with reasonable success, and if I need performance I can get it that way; why should I learn another language?” At the time, I agreed that for somebody who isn’t already an experienced C++ programmer, Rust makes perfect sense.

OK. That was my position in 2016. A way of putting it might be:

Programming C++ is like walking barefoot on the edge of a knife: you get a lot of papercuts, but also, it’s a fine balancing act. If you’re not careful, you’ll fall off, and it’s a long way down, screaming all the way.

Another way of putting it:

Well-written C++ is indistinguishable from badly-written C++ to any but experienced and careful C++ hackers. So as you write, unless you’re paying careful attention, you can knife yourself in the groin and bleed out long before you even notice the wound.

But recently, for reasons I won’t go into, I was forced to pick up Rust. Now, I’d been away from C++ for a while, so … well, for instance, I had forgotten whether to add a value to the end of a vector, it was append, or push_back, or put_back. But that’s easy enough to use Google to find, right? And so, I started hacking in Rust, and a few things became obvious within two weeks:

  1. Rust’s type system feels like ML, only with all these extra annotations. Those annotations are tiresome and a PITA, but once you get past that, it sure feels like ML.

  2. **Unlike C++*, when I make a mistake regarding memory-ownership, the compiler catches me. It’s actually more productive than C++, even for an experienced C++ hacker, b/c he can program without as much care and attention.

Back to those two descriptions above: basically, Rust appears to make it possible to write low-level high-performance code, without having to pay the sort of careful attention that we’re used-to, in C++. Of course, there are tradeoffs, and in this case, the tradeoff is that you have this incredibly complex and hard-to-understand type system. It’s not free. It’s not free.

Already, only three weeks in, Rust has become my fourth language (next to Perl, OCaml, and C++). And it’s clear that for most performance needs, Rust has supplanted C++.

5 Likes
17

As a user of Rust, it’s not so obvious that it’s “no GC”. Now, that sounds completely wrong. But what I mean is:

  1. sure, for really complex data-structures, Rust lacks a GC and that’s problematic. [I’m setting aside the rudimentary GC that you can find if you look]

  2. For less–complex data-structures, the user is forced to do the annotation that allows the compiler to insert the automatic reclamation code. In this sense, it “feels” like there’s a GC.

I’m still only three weeks in, but it definitely feels like there’s a limit to the complexity of system that one can program in Rust before it starts to get painful, and you end up reaching for “unsafe”. But within that domain, it sure does feel like just a much-more-tedious-to-typecheck GCed language. With excellent performance.

2 Likes
18

Ah yes, you are putting in words a feeling which I believe is shared by many (perhaps even dozens!) of researchers.

However you do not insist on the differences between the old C++ and the new, so I feel like tempering what you wrote. Compared to the old life-on-a-knife’s-edge C++, many simplifications have been brought by the new C++, the one where you never have to write new or delete, and where deep copies and many crazy corner cases are eliminated. It will not catch lifetime bugs but it did make pointers safer in general. Perhaps, only with enough expertise. But my experience was that old C++ was much crazier. It happened to me more than once to fix bugs, including lifetime issues, simply by converting code to use smart pointers. On the other hand it is likely that static support for the lifetime and uniqueness discipline was needed to unleash the full potential. For instance “fearless concurrency” is Rust, still not C++.

My point was not so much to say that this existed before, but to recognize that among the stuff that makes it possible, some of it which is new is due to C++11, and without this stuff (which is lower-level, more about language abstractions than typing constraints) there is also no fancy type system since there is nothing to apply the typing to. And one can see a continuity in terms of methodology between old C++, new C++ and Rust. If you compare to the academic side (e.g. Cyclone), both C++11 and Rust brought novel ideas. And this on the other hand is often overlooked in academic papers which cite Rust.

(Now, you did not ask about academic papers. My bias is showing.)

19

It’s all good, and I’m glad that C++11 is progressing in this way.

So … I’m not a researcher, though I used to be once. I’m an industrial programmer, trying to get code working, but with a sense of taste and esp. of what it takes to build systems. And where you write “fearless concurrency” I write “can I code in that language while drunk?” C++ has never felt that way to me: I needed to be sober and certainly not even sleepy. By contrast, OCaml and Perl always felt like I could program drunk (and esp. Perl). Rust begins to feel like one can program drunk: you might not actually make any progress, but you won’t wake up in the morning with a massive pile of core-dumps.

I don’t know anything about C++11, sadly. Last I learned anything, it was std::move and related things. And that was 7yr ago, too.

Everything you write about old C++ is truth. It was madness, and I don’t forget that a big reason Java caught on, was that C++ sucked so, so, so hard. New C++ is much, much better, and with the Google Style Guide, it’s tractable even for massive systems. But even still, GCed languages are even more tractable.

Re: academic papers, I’m very aware that there’s been a ton of research into making C-family languages safe for drunk programmers, and that one of the outcomes is Rust. I didn’t realize that some of that work influenced C++, and that’s great to know.

More than anything, again, where some write “fearless concurrency”, I would write

you write the algorithm, and then dispute with the compiler to get it to type-check. Once it does, you’re more than likely going to be done – assuming your algorithm is correct to begin with.

This was one of the original selling propositions of ML, and I feel like Rust is like that (again, for small-to-medium-sized code).

20

Hey Chetan R., I even cite your papers! (not while drunk)

Regarding the influence of academic research on C++11: this is certainly clear for lambdas and the memory model. However for RAII and move semantics, crickets. There are these Baker papers on linear logic which almost nobody has cited ever (in particular exactly nobody in the “linear types” community), but the C++ people have told me that they were not aware of them either.