To better understand how x7's FFI system works, we'll need to quickly cover how x7 represents types internally. All types, from numbers to lists to functions are instances of the Expr enum:

pub enum Expr {
    Num(Num),
    String(String),
    Symbol(Symbol),
    List(Vector<Expr>),
    Function(Function),
    Nil,
    // ... some elided variants
}

Fundamental to the FFI system is being able to convert foreign data types like u64 to a sensible Expr variant like Expr::Num. x7 only understands Expr, and it's impossible to use any other type. Throughout this article I will refer to non-Expr types as foreign, as they really are.

The next fundamental concern is converting foreign functions to x7's Function struct. The struct contains a few useful things, like the actual function pointer that actually does the work, and some auxiliary information like minimum number of arguments and whether to evaluate arguments or not.

In subsequent sections of the article we'll cover the rust traits responsible for the conversion.

My original motivation was embedding x7 as a scripting language in the database redis-oxide.

In particular, I wanted this to be possible:

;; basic x7 program, running inside of redis-oxide
(+ "redis-oxide returned: "
   (redis "get" "mykey"))

That redis function is foreign, so as alluded to in the FFI example above, it operates on it's own foreign types. This implies that x7's FFI system will need to transparently and automatically convert between foreign types and it's own native type Expr.

An implementation detail of the redis-oxide database is that it operates internally on the RedisRefValue type. So concretely we need a way to convert "get" and "mykey" into a RedisRefValue. On the other end, redis-oxide returns the same type after an operation, so we need to convert that to something x7 understands (Expr), so it can operate on that.

At a minimum we need to support:

1. A nice way to transparently operate on foreign data types.
2. Foreign functions being typed in their native types, not x7's Expr.
   1. If you've worked with other FFI systems, like Python's excellent FFI system, functions added to the interpreter are typed in Python's types, not the types of your program. This is fine, but not convenient as you need to manually convert python to your types and back.
3. A nice way to construct and add these functions to the interpreter.

A fundamental concern of an FFI system is to reason about data passed between the foreign program and x7. In x7's FFI system, this behaviour is captured in the ForeignData trait:

pub trait ForeignData
where
    Self: Sized,
{
    /// Convert from Self to x7's Expr type.
    fn to_x7(&self) -> Result<Expr, Box<dyn Error + Send>>;
    /// Convert x7's Expr type to Self.
    fn from_x7(expr: &Expr) -> Result<Self, Box<dyn Error + Send>>;
}

This trait encodes a fallible forward-and-backward mapping between some foreign type and x7's Expr type. If you're not familiar with rust, this adds methods to a type, and each operation either results in a Result, which encodes a success path, and a failure path of type Box<dyn Error + Send>.

If the conversion fails for any reason, we try our best to type erase that error in terms of Box<dyn Error + Send>. This error trait object helps a lot with wrangling different error types into just one that we can reason about. That Error trait is the std::error::Error trait, which helps interoperability between different rust programs. The Send trait bound is required as our motivating example is redis-oxide, which requires that errors be sent between threads. There's creates some unfortunate boilerplate around handling errors, but thankfully it's only around twenty lines.

To maximize convenience and skirt around rust's orphan rule, we'll provide ForeignData implementations for common types like String and u64. There's a lot of these implementations in the ffi.rs file in x7.

impl ForeignData for u64 {
    fn to_x7(&self) -> Result<Expr, Box<dyn Error + Send>> {
        Ok(Expr::Num((*self).into()))
    }

    fn from_x7(expr: &Expr) -> Result<Self, Box<dyn Error + Send>> {
        expr.to_u64()
    }
}

This will allow users to make functions using common rust types, and not worry about the details.

Now that we can reason about foreign data, we want a way to convert functions written in terms of foreign data types into something x7 can use. We'll use a technique known as extension traits to add a .to_x7_fn() method to functions. We'll ignore variadic (any number of arguments) functions for now, and only focus on functions with a known number of arguments.

The basic ingredients for a x7 function is:

1. A X7FunctionPtr, the pointer to the x7 function, which has some serious restrictions.
   1. The function has the shape Fn(Vector<Expr>, &SymbolTable) -> LispResult<Expr>.
   2. We require Sync + Send bounds to ensure thread safety (and make it compile).
2. A minimum number of arguments.
3. A symbol to represent the function (my-ff, etc).

We can use some trait magic to automate the first two, by having a trait that takes self and and returns the minimum number of args, and the X7FunctionPtr:

pub trait IntoX7Function<Args, Out> {
    fn to_x7_fn(self) -> (usize, crate::symbols::X7FunctionPtr);
}

An interesting part of this trait is the <Args, Out> types. We need those types to help differentiate our implementations of IntoX7Function, and support variadics later on. The general implementation concept for a function that takes n arguments is:

1. Make an x7 function: Fn(args: Vector<Expr>, _sym: &SymbolTable) -> LispResult<Expr>
2. Verify that exactly n arguments are passed (args.len()==n).
3. Convert each x7 Expr argument to the type we need with ForeignData::from_x7().
   1. Return a nice error message if that fails.
4. Call the foreign function with those now-converted arguments.
   1. Then capture and convert the function output with Out::to_x7() - x7 needs an Expr!
   2. Massage any errors into the error type x7 expects (anyhow::Error)

With that in mind, here's what the two argument implementation looks like without comments:

impl<F, A, B, Out> IntoX7Function<(A, B), Out> for F
where
    A: ForeignData,
    B: ForeignData,
    Out: ForeignData,
    F: Fn(A, B) -> Out + Sync + Send + 'static,
{
    fn to_x7_fn(self) -> (usize, crate::symbols::X7FunctionPtr) {
        let f = move |args: Vector<Expr>, _sym: &SymbolTable| {
            crate::exact_len!(args, 2);
            let a = convert_arg!(A, &args[0]);
            let b = convert_arg!(B, &args[1]);
            (self)(a, b).to_x7().map_err(|e| anyhow!("{:?}", e))
        };
        (2, Arc::new(f))
    }
}

And here's what it looks like with comments:

// We're working with a function with two arguments,
// that returns a single output type Out.
impl<F, A, B, Out> IntoX7Function<(A, B), Out> for F
where
    // All inputs and outputs to this function require ForeignData
    A: ForeignData,
    B: ForeignData,
    Out: ForeignData,
    // X7FunctionPtr requires Sync + Send, so we add that restriction to F
    F: Fn(A, B) -> Out + Sync + Send + 'static,
{
    fn to_x7_fn(self) -> (usize, crate::symbols::X7FunctionPtr) {
        // This closure conforms to the shape X7FunctionPtr requires,
        // namely a function that takes a Vector<Expr> and a symbol table reference.
        //
        // args: (<ff-symbol> 1 2) -> vector![Expr::Num(1), Expr::Num(2)]; actual args passed
        // _sym: A symbol table reference. Unused.
        let f = move |args: Vector<Expr>, _sym: &SymbolTable| {
            // exact_len: macro to throw an error if args.len() != 2.
            crate::exact_len!(args, 2);
            // convert_arg: macro that calls A::from_x7(&args[0]) and return a nice error if that fails
            let a = convert_arg!(A, &args[0]);
            let b = convert_arg!(B, &args[1]);
            (self)(a, b) // (self)(a,b) calls the foreign function with args a, b
                .to_x7() // convert the output to an x7 Expr
                .map_err(|e| anyhow!("{:?}", e)) // massage error type to x7's error type (anyhow)
        };
        // Finally, return a tuple of minimum args + our function
        (2, Arc::new(f))
    }
}

x7's FFI system contains similar implementations for functions that take one args to five args. The appendix will cover variadic functions. All of this gives us the power to do:

let my_ff = |a: u64, b: u64| a + b; 
let my_ff_x7 = my_ff.to_x7_fn();

Which is great, but now we need a way to make a x7 interpreter instance and actually add that my_ff function to it.

This part is thankfully much simpler than previous sections. We only need a struct holding a SymbolTable and a way to run programs on it.

#[derive(Clone)]
pub struct X7Interpreter {
    symbol_table: SymbolTable,
}

And a way to make a new one:

impl X7Interpreter {
    /// Make a new interpreter instance.
    pub fn new() -> Self {
        X7Interpreter {
            symbol_table: crate::stdlib::create_stdlib_symbol_table_no_cli(),
        }
    }
   // elided...
}

Finally, we need a way to run programs. We'll just take the program string as a &str, and call the usual lisp function of read and eval:

impl X7Interpreter {
    /// Run a x7 program.
    pub fn run_program<T: 'static + ForeignData>(
        &self,
        program: &str,
    ) -> Result<T, Box<dyn Error + Send>> {
        let mut last_expr = Expr::Nil;
        for expr in read(program) {
            last_expr = expr
                .and_then(|expr| expr.eval(&self.symbol_table))
                .map_err(ErrorBridge::new)?;
        }
        T::from_x7(&last_expr)
    }
}

This function parses the input (read), and then for every expression in the program call eval and return errors as necessary. We need to return something, so we default to Expr::Nil and return the last expression. The user needs to specify the output type T, as we want to actually return something. It's now possible to do:

fn main() {
    let interpreter = X7Interpreter::new();
    let output = interpreter.run_program::<u64>("(+ 1 1)").unwrap();
    println!("output: {}", output);
    // prints "output: 2"
}

Finally, we need a way to add functions to the interpreter. This is also straightforward thanks to IntoX7Function:

impl X7Interpreter {
    /// Add a function to the interpreter under the symbol `function_symbol`
    pub fn add_function(
        &self,
        function_symbol: &'static str,
        fn_tuple: (usize, crate::symbols::X7FunctionPtr),
    ) {
        let (minimum_args, fn_ptr) = fn_tuple;
        // The `true` at the end tells x7 to evaluate arguments passed in.
        let f = Function::new(function_symbol.into(), minimum_args, fn_ptr, true);
        self.symbol_table
            .add_symbol(function_symbol, Expr::Function(f));
    }
}

All we're doing is making a new Function struct instance, and adding the function to the interpreter with under the symbol function_symbol. Here's an example:

fn main() {
    let interpreter = X7Interpreter::new();

    // Make and add the function to x7 under the symbol my-ff
    let my_ff = |a: u64, b: u64| a + b;
    interpreter.add_function("my-ff", my_ff.to_x7_fn());

    let output = interpreter.run_program::<u64>("(my-ff 1 1)").unwrap();
    println!("output: {}", output); // prints "output: 2"
}

Interestingly, we can also see our careful handling of errors has paid off. The following x7 program:

(my-ff 1 "i am a string")

Fails with this error message, as my-ff expects a u64 not a string:

Error in Fn<my-ff, 2, [ ]>, with args (1 "i am a string")

Caused by:
    Error: Expected num, but got type 'str': "i am a string"

    Caused by:
        BadTypes

The x7 FFI system was very interesting for me to figure out, and this is what came out. I hope you enjoyed the article - it's certainly more code and concept heavy than previous articles.

Overall I think there's some room for improvement in the FFI system, but it's powerful and convenient enough to be embedded into redis-oxide, so I am content for now.

Thanks to the signature of IntoX7Function, we can add a type Variadic and implement IntoX7Function in terms of it.

pub struct Variadic<T>(Vec<T>);

impl<T> Variadic<T> {
    pub fn to_vec(self) -> Vec<T> {
        self.0
    }
}

Note: The underlying Vec<T> forces us to use the single type for every variadic argument. This isn't necessary a big deal, but it is something to keep in mind.

We now implement IntoX7Function in terms of Variadic:

impl<F, T: ForeignData, Out> IntoX7Function<(Variadic<T>,), Out> for F
where
    T: ForeignData,
    Out: ForeignData,
    F: Fn(Variadic<T>) -> Out + Sync + Send + 'static,
{
    fn to_x7_fn(self) -> (usize, crate::symbols::X7FunctionPtr) {
        let f = move |args: Vector<Expr>, _sym: &SymbolTable| {
            let args = match args.iter().map(T::from_x7).collect::<Result<Vec<_>, _>>() {
                Ok(v) => v,
                Err(e) => return Err(anyhow!("{:?}", e)),
            };
            (self)(Variadic(args))
                .to_x7()
                .map_err(|e| anyhow!("{:?}", e))
        };
        (1, Arc::new(f))
    }
}

For interest, this is what using Variadic in redis-oxide looks like:

let send_fn = move |args: Variadic<RedisValueRef>| {
    let args = args.to_vec();
    // ... use args as a vec ...
    // ... implementation details coming in future article ..
};
self.interpreter.add_function("redis", send_fn.to_x7_fn());

This variadic FFI interface allows us to provide a fully featured redis-oxide API in about 20 lines of code, as commands are converted directly into the internal representation for command processing:

;; No special API code! Directly converted and passed to the command processor
(redis "mset" "key1" "value1" "key2" "value2")
(redis "lpush" "list-key" "value1" "value2")

To run x7 programs, we need to parse the incoming strings into a form we can actually evaluate. Central to this is the type Expr, which represents all possible types in the interpreter:

pub(crate) enum Expr {
    Num(Num),
    Symbol(Symbol),
    List(Vector<Expr>),
    Function(Function),
    // elided variants...
}

The shown members of that enum are the minimum required variants to evaluate simple expressions like (+ 1 1). If you're not familiar with lisps, this is the same thing as 1 + 1.

The string "(+ 1 1)" needs to get transformed into a type we can operate on. The details of the parser aren't relevant this article. All we really need to know is that (+ 1 1) gets transformed into the following Expr type:

Expr::List(
    Expr::Symbol("+"),
    Expr::Num(1),
    Expr::Num(1),
)

This form is very convenient as we can recursively evaluate it to facilitate computation.

Crucial to lisps is the expression, or the idea that types just exist and propagate through computation. Evaluation simply stated is a computation process of taking an expression, and returning another expression. For example, typing 3.3 in the x7 interpreter returns 3.3, another expression. In contrast, (+ 1 1) is considerably more complex, as it represents a function call to add two numbers. We'll need to work our way there.

To build our way to evaluating (+ 1 1), we'll need to discuss core concepts like Expressions, Symbols, and Lists.

To represent types which are internally stateful, we'll add a trait called Record to the language. It needs to express following behaviours:

1. Call methods with arguments.
2. Represent the type in a display and debug way.
3. Represent the type name as a string, and it's methods.
4. Uniquely identify the type (hash).
5. Clone the type safely.

Aside from calling methods, most of these items are related to making sure error messages are nice, or slotting it in cleanly with the rest of the interpreter machinery.

Here's the trait in rust:

/// Fundamental trait for records.
///
/// Records allow x7 to represent a variety of internally mutable types
/// while not expanding the Expr enum too much. These types are responsible for
/// implementing RecordDoc if they want to have documentation.
pub(crate) trait Record: Sync + Send {
    /// Call a method on this record.
    /// (.method_name <rec> arg1 arg2 arg3)
    /// Becomes:
    /// (&self: <rec>, sym: "method_name", args: vector![arg1, arg2, arg3])
    fn call_method(&self, sym: &str, args: Vector<Expr>) -> LispResult<Expr>;

    /// Uniquely identify this record
    fn id(&self) -> u64 {
        0
    }
    /// Nicely display the record type.
    fn display(&self) -> String;

    /// Add more information for debug printing
    fn debug(&self) -> String;

    /// Clone the object.
    fn clone(&self) -> RecordType;

    /// Return the names of the methods for help messages.
    fn methods(&self) -> Vec<&'static str>;

    /// Return the type name for nice help messages
    fn type_name(&self) -> &'static str;
}

Now that we have a trait, we need a fundamental type we can export and use throughout x7. Since we want to use trait objects, a Box is a natural choice:

pub(crate) type RecordType = Box<dyn Record>;

I'll elide the implementation details to get Record implemented for RecordType, but if you're curious, they can be found here.

Without getting too much in the parser weeds, .method is parsed into an Expr::Symbol. We can modify the parser to recognize the period, and instead parse it into a Function that calls our method for us.

The parse_symbol function is defined as:

fn parse_symbol<'a>(i: &'a str) -> IResult<&'a str, Expr, VerboseError<&'a str>> {
    map(take_while1(is_symbol_char), |sym: &str| {
        Expr::Symbol(sym.into())
    })(i)
}

So all it does is try to recognize a symbol, and then transform the type when it fully parses one. We'll modify it to recognize if a symbol starts with a period, and if so, call make_method_call and return an Expr::Function.

Let's first make make_method_call: ((if (random_bool) + -) 10 5)

fn make_method_call(method: String) -> Expr {
    // Import some useful types
    use crate::symbols::Function;
    use std::sync::Arc;
    let method_clone = method.clone();
    // This is the cool part. We're making a closure that obeys
    // the X7FunctionPtr type.
    // When we call .write, it'll call this function.
    let method_fn = move |args: Vector<Expr>, _sym: &SymbolTable| {
        // First item is a record, and get it
        let rec = match args[0].get_record() {
            Ok(rec) => rec,
            Err(e) => return Err(e),
        };
        // `rec` is a record, so call the method.
        // Note that we move `method_clone` into this this closure!
        use crate::records::Record;
        // The layout of `args` is: (<record> <arg1> <arg2> ...),
        // and the type signature we have is Record::call_method(method, args)
        rec.call_method(&method_clone, args.clone().slice(1..));
    };
    // Make a Function struct
    let f = Function::new(
        format!("method_call<{}>", method), // function name
        1,                                  // number of args
        Arc::new(method_fn),                // function pointer
        true,                               // eval args
    );
    // Return an Expr::Function
    Expr::Function(f)
}

This is pretty cool - we're transforming a symbol into a function. All we need to do is to add an if-gate into parse_symbol, and we're set!

fn parse_symbol<'a>(i: &'a str) -> IResult<&'a str, Expr, VerboseError<&'a str>> {
    map(take_while1(is_symbol_char), |sym: &str| {
        if sym.starts_with('.') {
            make_method_call(sym[1..].into()) // sym[1..] => drop the period
        } else {
            Expr::Symbol(sym.into())
        }
    })(i)
}

We can start x7 and test it out:

>>> .read_to_string
Fn<method_call<read_to_string>, 1, [ ]>

Nice, we're getting a function from our parser. We can try using it:

>>> (def f (fs::open "hello-world.txt"))
>>> (.read_to_string f)
"hello"

And that's it! We've implemented records in x7. I hope you enjoyed reading the article!

Iterators are very common in Rust, and if you've written Rust you have likely used them. Here is a basic example:

for val in 0..10 {
  // ... use val
}

0..10 is a Range, which implements Iterator, which is central to the function of for-loops (desugar here).

You may have written something more complex as well:

let v1 = vec![1, 2, 3];
let v2 = vec![4, 5, 6];

let dot_product: u32 = v1
    .iter()
    .zip(v2)
    .map(|(l, r)| l * r)
    .sum(); // 32

Either way, we're iterating and operating on some sequence of values. The Iterator trait provides convenient ways to construct, transform, and consume these sequences.

The Iterator trait could be thought as having three parts:

1. The foundation: a next() function which returns some type Item if it can.
2. Lots and lots of methods for iterator transformations (e.g. functional tools like map and filter).
3. A function called collect(), which allows you to evaluate iterators into some collection type.

To get more familiar with the trait, let's make a useful construct: The Natural Numbers.

To implement this, we'll need a struct holding the current value:

// Book keeping struct
struct NaturalNumbers {
    curr: u32,
}

// Start at 0 because computers
impl NaturalNumbers {
    fn new() -> Self {
        Self { curr: 0 }
    }
}

And implement Iterator by incrementing curr:

impl Iterator for NaturalNumbers {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        let ret = self.curr;
        self.curr += 1;
        Some(ret)
    }
}

Nice! We have a struct NaturalNumbers which will yield every natural number until it panics on overflow.

This is certainly useful, and will serve as a bedrock for later functions. Unfortunately our terminals don't appreciate printing millions of integers, so we'll use the method Iterator::take(N) which limits the number of iterations to at most N.

We can then test NaturalNumbers with:

fn main() {
    for i in NaturalNumbers::new().take(5) {
        println!("{}", i);
    }
}

Which outputs:

~ cargo run
   Compiling iterator-article v0.1.0 (/home/david/programming/iterator-article)
    Finished dev [unoptimized + debuginfo] target(s) in 0.15s
     Running `target/debug/iterator-article`
0
1
2
3
4

You can the run this example yourself on the Rust playground!

So now that we can generate a sequence of values, let's implement some familiar functional friends: map, filter, and reduce (fold).

The following code is certainly nice:

let nat = NaturalNumbers::new().take(4);
let doubled = Map::new(nat, |e| e * e);
let mut seq = Filter::new(doubled, |e: &u32| *e % 2 == 0);
let prod = reduce(seq, 1, |acc, ele| acc * ele);

But this is far easier to read:

let prod = NaturalNumbers::new()
    .take(4)
    .map(|e| e * e)
    .filter(|e: &u32| *e % 2 == 0)
    .reduce(1, |acc, ele| acc * ele);

The question is then: How does Iterator provide this interface?

As mentioned above, Iterator provides a whole bunch of default methods to facilitate this clean API. To better understand how this works, let's define our own Iterator trait:

trait MyIterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

And update our previous Iterator implementations:

-impl<Iter, Predicate> Iterator for Filter<Iter, Predicate>
+impl<Iter, Predicate> MyIterator for Filter<Iter, Predicate>
...

You can view the whole refactor on the rust playground. Unfortunately, our changes don't compile as we no longer have a Iterator::take(N) method:

error[E0599]: no method named `take` found for struct `NaturalNumbers` in the current scope
   --> src/main.rs:116:37
    |
1   | struct NaturalNumbers {
    | ---------------------
    | |
    | method `take` not found for this
    | doesn't satisfy `NaturalNumbers: std::iter::Iterator`
...
116 |     let nat = NaturalNumbers::new().take(4);
    |                                     ^^^^ method not found in `NaturalNumbers`
    |
    = note: the method `take` exists but the following trait bounds were not satisfied:
            `NaturalNumbers: std::iter::Iterator`
            which is required by `&mut NaturalNumbers: std::iter::Iterator`
    = help: items from traits can only be used if the trait is implemented and in scope
    = note: the following trait defines an item `take`, perhaps you need to implement it:
            candidate #1: `std::iter::Iterator`

It's looking like we'll need to implement Take ourselves. It's a very similar process as before. We'll need a struct and Iterator implementation:

struct Take<Iter> {
    iterator: Iter,
    left: usize,
}

impl<Iter> Take<Iter> {
    fn new(iterator: Iter, left: usize) -> Self {
        Self { iterator, left }
    }
}

impl<Iter: MyIterator> MyIterator for Take<Iter> {
    type Item = Iter::Item;
    fn next(&mut self) -> Option<Self::Item> {
        if self.left > 0 {
            self.left -= 1;
            self.iterator.next()
        } else {
            None
        }
    }
}

Now that we have the struct, we need to modify MyIterator to achieve the desired API. Things will get a bit introspective, as we cannot refer to any concrete types. We instead rely on the Self language feature to specify that types which implement MyIterator will be the ones used in the method calls. We'll want to transfer ownership of iterators in these methods, so our MyIterator::Take(N) signature will read:

fn take(self, left: usize) -> Take<Self>

The other wrinkle is that this won't compile, as the Rust compiler is not confident it can layout the Take struct properly, as Self can be !Sized. This can seem obscure, but the error message is pretty good:

error[E0277]: the size for values of type `Self` cannot be known at compilation time
   --> src/main.rs:116:37
    |
90  | struct Take<Iter> {
    |             ---- required by this bound in `Take`
...
116 |     fn take(self, amount: usize) -> Take<Self> {
    |                                     ^^^^^^^^^^- help: consider further restricting `Self`: `where Self: std::marker::Sized`
    |                                     |
    |                                     doesn't have a size known at compile-time
    |
    = help: the trait `std::marker::Sized` is not implemented for `Self`
    = note: to learn more, visit <https://doc.rust-lang.org/book/ch19-04-advanced-types.html#dynamically-sized-types-and-the-sized-trait>

To better understand this error, what is the type of seq in the following?

let seq = NaturalNumbers::new()
    .take(4)
    .map(|e| e * e)
    .filter(|e: &u32| *e % 2 == 0);

The answer is Filter<Map<Take<NaturalNumbers>, fn#1>, fn#2>.

Recall that Map, Filter, and Take all take a type Iter: MyIterator by value, so it needs to physically store that iterator in the struct memory layout. The Rust language tracks this information in the Sized trait. So if a type is Sized, Rust can properly lay out the struct. If a type is !Sized, then indirection or obscure language features are required to embed that type in the struct. The compiler has helpfully told us to add a Sized bound on Self:

 fn take(self, amount: usize) -> Take<Self>
+where
+    Self: std::marker::Sized,
 {
     Take::new(self, amount)
 }

This compiles and works! Let's run our main again:

fn main() {
    let nat = NaturalNumbers::new().take(4);
    let doubled = Map::new(nat, |e| e * e);
    let seq = Filter::new(doubled, |e: &u32| *e > 0);
    let prod = reduce(seq, 1, |acc, ele| acc * ele);
    println!("{}", prod);
}

Which outputs:

~ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.03s
     Running `target/debug/iterator-article`
36

We can now do the same procedure for Map and Filter. We can reuse the constructors but replace Iter with Self:

trait MyIterator {
    // elided ...

    fn map<Out, F>(self, f: F) -> Map<Self, F>
    where
        F: FnMut(Self::Item) -> Out,
        Self: std::marker::Sized,
    {
        Map::new(self, f)
    }

    fn filter<F>(self, f: F) -> Filter<Self, F>
    where
        F: FnMut(&Self::Item) -> bool,
        Self: std::marker::Sized,
    {
        Filter::new(self, f)
    }
}

Our main function is now:

fn main() {
    let seq = NaturalNumbers::new()
        .take(4)
        .map(|e| e * e)
        .filter(|e: &u32| *e > 0);
    let prod = reduce(seq, 1, |acc, ele| acc * ele);
    println!("{}", prod);
}

Which outputs 36 as before. Now we just need to implement reduce in a similar way as before:

trait MyIterator {
  // elided...

  fn reduce<Acc, ReduceFn>(mut self, acc: Acc, mut reducefn: ReduceFn) -> Acc
  where
      ReduceFn: FnMut(Acc, Self::Item) -> Acc,
      Self: std::marker::Sized,
  {
      let mut acc = acc;
      while let Some(ele) = self.next() {
          acc = reducefn(acc, ele);
      }
      acc
  }
}

And change our main function to be:

fn main() {
    let prod = NaturalNumbers::new()
        .take(4)
        .map(|e| e * e)
        .filter(|e: &u32| *e > 0)
        .reduce(1, |acc, ele| acc * ele);
    println!("{}", prod);
}

Which outputs 36 as expected (rust playground):

~ cargo run
   Compiling iterator-article v0.1.0 (/home/david/programming/iterator-article)
    Finished dev [unoptimized + debuginfo] target(s) in 0.15s
     Running `target/debug/iterator-article`
36

Phew, 3.6k words later we've accomplished our goal. We've recreated the Iterator, and delved into it's mechanics. I hope you've learned something from his article, as I certainly learned a lot writing it. I really like this language feature, and think it represents some of the best API design Rust offers.

We started our journey by defining the NaturalNumbers, so it would be cool if we could generate an infinite sequence of Primes:

struct Primes {
    seen: Vec<u32>,
    curr: u32,
}

impl Primes {
    fn new() -> Self {
        Self {
            seen: vec![],
            curr: 2,
        }
    }
}

impl Iterator for Primes {
    type Item = u32;

    fn next(&mut self) -> Option<u32> {
        for ele in self.curr.. {
            if !self.seen.iter().any(|prime| ele % prime == 0) {
                self.seen.push(ele);
                self.curr = ele + 1;
                return Some(ele);
            }
        }
        None
    }
}

Which can we use:

fn main() {
    println!("{:?}", Primes::new().take(20).collect::<Vec<_>>());
}

And this outputs the first twenty primes (rust playground):

~ cargo run
      Finished dev [unoptimized + debuginfo] target(s) in 0.19s
       Running `target/debug/iterator-article`
  [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

It's just that easy to generate a sequence of Primes using Iterator in Rust. The reader is encouraged to use MyIterator::reduce to achieve the same effect.

The redis folks were kind enough to simply document the v3 protocol on their website. The protocol is CLRF (\r\n) delimited, with each word carrying a type. The simplest types are Simple Strings and Errors, which look like:

+OK\r\n
-Error Msg\r\n

There's also bulkstrings, which are strings with a length:

$3\r\nFOO\r\n

We also have integers:

:1337\r\n

And finally we have arrays, which simply have a size indicating how many redis values follow.

*3\r\n$3\r\nSET\r\n$3\r\nfoo$3\r\nbar\r\n

We can read the array resp as:

*3\r\n        -- We have three elements in this array
$3\r\nSET\r\n -- First element is a bulk string of length 3 with value SET
$3\r\nfoo     -- Second element is also a bulk string of length 3 with value foo
$3\r\nbar\r\n -- Third element is also a bulk string of length 3 with value foo

Now that we're familiar with the protocol, lets get an idea on what parsing combinators actually are.

The basic idea behind parsing combinators is that you build more complex parsers from simpler parsers. A simple parser could do something like fetch a word, and then we can use that later to parse sentences, as they're composed of words.

From the RESP examples above, we can see that it's a series of words delimited by CLRF, so it would be very handy to have a word parser. We can implement one pretty simply by collecting all bytes until we hit a CLRF. As we'll see later, almost everything in RESP will be parsed by varying the output of our word parser.

All parsing combinators need a way of representing position in the input. The strategy I'll be using is to have a cursor which I'll track the position of (starting at 0).

Now that we understand RESP, and have an idea on what a parser combinator is, we'll need to understand how we can avoid copying in redis oxide. For context, I previously heap allocated almost all bytes in redis-oxide. Without digging too deep into the details, my fundamental types were defined as:

/// These types are used by state and ops to actually perform useful work.
pub type Value = Vec<u8>;
/// Key is the standard type to index our structures
pub type Key = Vec<u8>;

Which meant my parser needed to output Vec's, which are heap allocated. Value and Key are used almost everywhere in the application to represent almost all values in a redis command. So we need to change these types to be small, stack allocated items. No matter what direction we take, we need to play nice with tokio's codec scheme.

Now it should be understood that tokio's Decoder trait works as follows:

1. redis-oxide uses the tokio framework which provides services to listen on sockets.
2. One of the APIs provided is the Decoder trait, which you use to carefully read bytes off a socket to produce a type.
3. Tokio maintains a large buffer and will copy bytes received off a socket into this buffer.
4. It will pass this buffer to the parser until the parser signals that a type can be produced.
5. The tokio managed buffer is smart, and allows for several byte slices to be made safely (Bytes type).
6. The parser will cleave off enough bytes from the buffer when producing a type to allow tokio to safely copy later received bytes.
7. We bypass lifetime issues as the Bytes type maintains reference counts, so we can pass slices up further up the application.
8. Once redis-oxide is done with the produced types, we'll drop the slice references, and memory can be reclaimed.

So our parser will need to dance this careful dance. As described above, we can safely share byte slices of this underlying buffer using the Bytes type. So we'll redefine our fundamental types in terms of Bytes:

/// These types are used by state and ops to actually perform useful work.
pub type Value = Bytes;
/// Key is the standard type to index our structures
pub type Key = Bytes;

Aside from a massive related refactoring job, we now need to just write the parser 😛.

Writing the parser will require us to solve a few problems:

1. Data representation and type transformations.
2. Error handling and type setup.
3. Writing the fundamental parsers.
4. Dealing with arrays.

Now that we understand our data representation and errors, lets write our first parser! As mentioned several times, RESP is a word based protocol. So lets write a word parser! The only thing we care about is finding the position (index) of the next CLRF.

As this is infallible, we don't necessary need to use the RedisResult type. So our function can have the following signature:

fn word(buf: &BytesMut, pos: usize) -> Option<(usize, BufSplit)>

So we'll take the tokio provided buffer buf, and our current position pos, and if we can, output Some((next_pos, BufSplit)). We'll use burntsushi's fantastic memchr crate to accelerate searching for CLRF (\r\n):

/// Get a word from `buf` starting at `pos`
#[inline]
fn word(buf: &BytesMut, pos: usize) -> Option<(usize, BufSplit)> {
    // We're at the edge of `buf`, so we can't find a word.
    if buf.len() <= pos {
        return None;
    }
    // Find the position of the b'\r'
    memchr(b'\r', &buf[pos..]).and_then(|end| {
        if end + 1 < buf.len() {
            // pos + end == first index of b'\r' after `pos`
            // pos + end + 2 == ..word\r\n<HERE> -- skip to after CLRF
            Some((pos + end + 2, BufSplit(pos, pos + end)))
        } else {
            // Edge case: We received just enough bytes from the client
            // to get the \r but not the \n
            None
        }
    })
}

Great! We can now efficiently grab individual words from our input buffer. Even better, simple strings and errors are simple type transformations of this:

fn simple_string(buf: &BytesMut, pos: usize) -> RedisResult {
    Ok(word(buf, pos).map(|(pos, word)| (pos, RedisBufSplit::String(word))))
}

fn error(buf: &BytesMut, pos: usize) -> RedisResult {
    Ok(word(buf, pos).map(|(pos, word)| (pos, RedisBufSplit::Error(word))))
}

If that syntax isn't super familiar, both of the above are equivalent to:

fn simple_string(buf: &BytesMut, pos: usize) -> RedisResult {
    match word(buf, pos) {
        Some((pos, word)) => Ok(Some((pos, RedisBufSplit::String(word)))),
        None => Ok(None),
    }
}

So all we're doing is wrapping the BufSplit returned by word in the appropriate RedisBufSplit type.

Nice! So our easy types are out of the way. We now need to parse ints, bulk strings, and finally arrays.

Ints are the first non-trivial type to parse. RESP represents signed 64 bit integers as a base 10 string, so we'll need to:

1. Grab a word (BufSplit, can turn into byte slice with BufSplit::as_slice)
2. Convert byte slice to a str
3. Convert the str to an i64

This process can fail on steps 2 and 3. Rust requires that strings are uft-8 encoded, so converting to a str can fail. Then someone could pass "abc" as the int, so converting to i64 can fail. Keeping those in mind, we can now write the int function:

fn int(buf: &BytesMut, pos: usize) -> Result<Option<(usize, i64)>, RESPError> {
    match word(buf, pos) {
        Some((pos, word)) => {
            // word.as_slice(buf) is the method call BufSplit::as_slice(&self, &BytesMut) to access the byte slice.
            let s = str::from_utf8(word.as_slice(buf)).map_err(|_| RESPError::IntParseFailure)?;
            // Convert the string to an i64. Note the `?` for early returns.
            let i = s.parse().map_err(|_| RESPError::IntParseFailure)?;
            Ok(Some((pos, i)))
        }
        None => Ok(None),
    }
}

Nice, so we can grab ints from the input. We only need a trivial function to get the desired RedisResult type:

fn resp_int(buf: &BytesMut, pos: usize) -> RedisResult {
    Ok(int(buf, pos)?.map(|(pos, int)| (pos, RedisBufSplit::Int(int))))
}

So bulk strings in RESP start with a length (i64), and then the string content (delimited by CLRF of course). So we can use our previous int function, and then work through the possible cases (see second code block for comments).

Here's the code without comments:

fn bulk_string(buf: &BytesMut, pos: usize) -> RedisResult {
    match int(buf, pos)? {
        Some((pos, -1)) => Ok(Some((pos, RedisBufSplit::NullBulkString))),
        Some((pos, size)) if size >= 0 => {
            let total_size = pos + size as usize;
            if buf.len() < total_size + 2 {
                Ok(None)
            } else {
                let bb = RedisBufSplit::String(BufSplit(pos, total_size));
                Ok(Some((total_size + 2, bb)))
            }
        }
        Some((_pos, bad_size)) => Err(RESPError::BadBulkStringSize(bad_size)),
        None => Ok(None),
    }
}

And here's the same code with comments explaining what's going on:

fn bulk_string(buf: &BytesMut, pos: usize) -> RedisResult {
    // recall that the `pos` returned by `int` is the first index of the string content.
    match int(buf, pos)? {
        // special case: redis defines a NullBulkString type, with length of -1.
        Some((pos, -1)) => Ok(Some((pos, RedisBufSplit::NullBulkString))),
        // We have a size >= 0
        Some((pos, size)) if size >= 0 => {
            // We trust the client here, and directly calculate the end index of string (absolute w.r.t pos)
            let total_size = pos + size as usize;
            // The client hasn't sent us enough bytes
            if buf.len() < total_size + 2 {
                Ok(None)
            } else {
                // We have enough bytes, so we can generate the correct type.
                let bb = RedisBufSplit::String(BufSplit(pos, total_size));
                // total_size + 2 == ...bulkstring\r\n<HERE> -- after CLRF
                Ok(Some((total_size + 2, bb)))
            }
        }
        // We recieved a garbage size (size < -1), so error out
        Some((_pos, bad_size)) => Err(RESPError::BadBulkStringSize(bad_size)),
        // Not enough bytes to parse an int (i.e. no CLRF to delimit the int)
        None => Ok(None),
    }
}

Now we have only one type left: Arrays.

Arrays are fundamentally more complex than other types as they are a sequence of redis values. We'll have to be more clever. They are defined as a size (i64) and then a size number of redis values. This is naturally recursive, as we can have arrays inside arrays.

The issue is that we need a function which will parse redis values, as fn array(..) is only responsible for redis arrays. But that generic parse function will also need to call the array parser!

Thankfully we can use some first year CS.

Lets first define our top level parse function. It's responsible for taking a buffer and returning a RedisResult, agnostic to particular RESP types. RESP tags every element with a type byte, so our function is short:

fn parse(buf: &BytesMut, pos: usize) -> RedisResult {
    if buf.is_empty() {
        return Ok(None);
    }

    match buf[pos] {
        b'+' => simple_string(buf, pos + 1),
        b'-' => error(buf, pos + 1),
        b'$' => bulk_string(buf, pos + 1),
        b':' => resp_int(buf, pos + 1),
        b'*' => array(buf, pos + 1),
        _ => Err(RESPError::UnknownStartingByte),
    }
}

So parse(..) will check the byte at pos (initially 0), and use that to delegate to the correct function. Now this is very useful, and will allow us to write the array parser.

Here's the code without comments:

fn array(buf: &BytesMut, pos: usize) -> RedisResult {
    match int(buf, pos)? {
        None => Ok(None),
        Some((pos, -1)) => Ok(Some((pos, RedisBufSplit::NullArray))),
        Some((pos, num_elements)) if num_elements >= 0 => {
            let mut values = Vec::with_capacity(num_elements as usize);
            let mut curr_pos = pos;
            for _ in 0..num_elements {
                match parse(buf, curr_pos)? {
                    Some((new_pos, value)) => {
                        curr_pos = new_pos;
                        values.push(value);
                    }
                    None => return Ok(None),
                }
            }
            Ok(Some((curr_pos, RedisBufSplit::Array(values))))
        }
        Some((_pos, bad_num_elements)) => Err(RESPError::BadArraySize(bad_num_elements)),
    }
}

And the same code with comments:

fn array(buf: &BytesMut, pos: usize) -> RedisResult {
    match int(buf, pos)? {
        // Not enough bytes to determine the array size
        None => Ok(None),
        // special value: NullArray. Has size -1.
        Some((pos, -1)) => Ok(Some((pos, RedisBufSplit::NullArray))),
        // Happy path. We have a valid size (num_elements > 0)
        Some((pos, num_elements)) if num_elements >= 0 => {
            // As we're recieving a dynamic number of elements, we need to heap allocate our BufSplits.
            let mut values = Vec::with_capacity(num_elements as usize);
            // We're going to forward iterate on `curr_pos`
            let mut curr_pos = pos;
            for _ in 0..num_elements {
                // Mutual Recursion! We need to parse the value at `curr_pos`
                match parse(buf, curr_pos)? {
                    // We got a value, so add it to the `values` vector and
                    // update `curr_pos`.
                    Some((new_pos, value)) => {
                        curr_pos = new_pos;
                        values.push(value);
                    }
                    // Not enough bytes. Abandon parsing and free vec.
                    None => return Ok(None),
                }
            }
            // We had enough bytes to fully parse the array! Return it.
            Ok(Some((curr_pos, RedisBufSplit::Array(values))))
        }
        // Client sent us a garbage size (num_elements < -1)
        Some((_pos, bad_num_elements)) => Err(RESPError::BadArraySize(bad_num_elements)),
    }
}

So we can now parse arrays, and can now put everything together.

We're so close! We just need a few conversion functions before we can implement Decoder. Once we're done parsing, we're guaranteed to have a contiguous slice of memory that corresponds to the RedisBufSplit types we've generated until this moment. So we just need two functions:

1. Take the large Bytes buffer and a BufSplit(start,end) slice into it to make a byte slice (also Bytes type)
2. Take the RedisBufSplit and the large Bytes buffer and produce RedisValueRef types.

The conversion function is actually pretty mechanical:

// First, we need a convenient way to convert our index pairs into byte slices.
impl BufSplit {
    /// Get a lifetime appropriate slice of the underlying buffer.
    ///
    /// Constant time.
    #[inline]
    fn as_slice<'a>(&self, buf: &'a BytesMut) -> &'a [u8] {
        &buf[self.0..self.1]
    }

    /// Get a Bytes object representing the appropriate slice
    /// of bytes.
    ///
    /// Constant time.
    #[inline]
    fn as_bytes(&self, buf: &Bytes) -> Bytes {
        buf.slice(self.0..self.1)
    }
}
// Second, we'll need to convert a RedisBufSplit -> RedisValueRef given a Bytes buffer.
impl RedisBufSplit {
    fn redis_value(self, buf: &Bytes) -> RedisValueRef {
        match self {
            // bfs is BufSplit(start, end), which has the as_bytes method defined above
            RedisBufSplit::String(bfs) => RedisValueRef::String(bfs.as_bytes(buf)),
            RedisBufSplit::Error(bfs) => RedisValueRef::Error(bfs.as_bytes(buf)),
            RedisBufSplit::Array(arr) => {
                RedisValueRef::Array(arr.into_iter().map(|bfs| bfs.redis_value(buf)).collect())
            }
            RedisBufSplit::NullArray => RedisValueRef::NullArray,
            RedisBufSplit::NullBulkString => RedisValueRef::NullBulkString,
            RedisBufSplit::Int(i) => RedisValueRef::Int(i),
        }
    }
}

We can now implement the Decoder trait so our parser fits in with the tokio machinery:

/// The struct we're using. We don't need to store anything in the struct.
/// Later on we can expand this struct for optimization purposes.
#[derive(Default)]
pub struct RespParser;

impl Decoder for RespParser {
    type Item = RedisValueRef;
    type Error = RESPError;
    fn decode(&mut self, buf: &mut BytesMut) -> Result<Option<Self::Item>, Self::Error> {
        if buf.is_empty() {
            return Ok(None);
        }

        match parse(buf, 0)? {
            Some((pos, value)) => {
                // We parsed a value! Shave off the bytes so tokio can continue filling the buffer.
                let our_data = buf.split_to(pos);
                // Use `redis_value` defined above to get the correct type
                Ok(Some(value.redis_value(&our_data.freeze())))
            }
            None => Ok(None),
        }
    }
}

We did it! We can now decode RedisValueRef's from bytes off a socket! A complete parser includes encoding RedisValueRef's, but the code is pretty simple so you can read it here. You can view the tests here and how it's actually used in redis-oxide here.

Overall this 500+ line journey has netted us an efficient, zero copy RESP parser using parsing combinators. It was a lot of work to get the project refactored, but I am proud to have a solution I wrote myself and actually understand (no offense to the combine people).

Hopefully it's clear by now that I find Linux familiar and comfortable, if nothing else. I recently built a PC and decided to install Arch Linux for the first time, and it pretty much worked! I had an operating system in which I installed all of the required bits, and had a greater understanding of all the parts required to keep it running. The feeling of leaving that chroot and praying I made the boot entries properly was a thrill.

The fact that this new computer, shoddily constructed by myself and my brother, boots into a viable and familiar operating system that I control is fucking amazing. God bless the opensource community.

It doesn't seem right to write a love letter blog about Linux and not share my setup.

The setup I've roughly used since my CrunchBang days is to have four virtual desktops¹ setup as follows:

1. The web browser. Used to be Chrome before Firefox became good again.
2. Emacs.
3. Terminal.
4. Empty. Used for temporary or less important applications. Things like graphical file browsers, word processors, or music clients.

I deeply enjoy this setup as it's baked into my muscle memory. There's no distinct advantage in and of itself, aside from maybe separation of concerns. The base system doesn't matter much. I used Antergos until they shutdown and now I just use vanilla Arch Linux (btw). My window manager is i3 with some scripts to polish the experience. In fact, at work, I encode this setup fairly well on the OSX machines we work on. The individual tools (emacs) don't work as well or in the same way, but it's similar.

I feel at home in my Linux setup. It's comfortable. I'm responsible for it, and can tweak it to my needs. And it looks pretty. And so on.

I get fuzzy feelings thinking about it sometimes.

Combinators are nice as they allow for concise, and often more readable, type transformations. Both examples have similar line length, but differ in visual complexity. The first example has the match keyword, a block, and pattern matches on option's variants. Visually this is more text to parse and understand, especially when you're tired after work. The second, "combinated", example is in my opinion easier to read. We're reading our state, transforming the hash type into a Count, and then discarding the None case by defaulting to 0.

We'll see that there's a few more advantages, such as eliminating branches and general purity.

Combinators are a realization of a pretty common pattern: "I can't deal with this type. I'll just return it." You've likely used this pattern many, many times. Do you recognize the following snippets?

In python:

def sketchy_legacy_code(n):
    if n is None:
        return None
    return n * 2

Or in javascript:

function sketchyLegacyCode(n) {
  if (n === undefined || n === null) {
    return n;
  }
  return n * 2;
}

This pattern certainly occurs more frequently in weakly typed or dynamically typed languages. A (sometimes reasonable) solution to this problem is exceptions, but rust doesn't have them. And exceptions can be problematic, as you can forget to catch them or catching them makes the code harder to understand.

Combinators are then a generalization of this concept. If I can operate on this type, I'll do so. Otherwise, I'll pass it along. This is a very powerful pattern. You can focus on the happy path and errors will be propagated automatically if they occur.

In the same way that monads saved haskell, combinators help save rust. Rust is notorious for it's error handling as you're forced to encode your errors directly in the type system. This usually takes the form of returning Option<T> and Result<T, E>, which your callees consume.

So rust provides a thousand tools to cut through these types. I'll focus on Option<T> this article as I'm working with a forgiving database. An Option<T> in rust is an enum:

enum Option<T> {
    Some(T),
    None
}

So if I receive an Option<T>, it's either got data for me (Some(T)) or nothing for me (None). This type is very common in redis-oxide and most rust projects. Sometimes you don't care if it's None, so you can use if let Some(value) = myoption {...}, or just let value = myoption.unwrap(). But sometimes you end with a pathological case.

The redis command ZSCORE zset_name member is such an example. It has the following (observed behaviour):

1. If the sorted set does not exist, return Nil.
2. If the sorted exists, and the member isn't found, return Nil.
3. Otherwise, return the score of the member as Int.

Let's code this using match statements:

// Inputs: zset_key, member
match read_zsets!(state, &zset_key) {
  // The sorted set may not contain `member`, so another option!
  Some(zset) => match zset.score(&member) {
    // Notice that we have to explicitly give the ReturnValue type.
    // We can't wrap it as we need to return Nil!
    Some(score) => ReturnValue::IntRes(score),
    None => ReturnValue::Nil
  },
  None => ReturnValue::Nil
}

Now this can nest even deeper if we have more options or results to deal with. And we're repeating ourselves with ReturnValue::Nil.

Thankfully, we can use the and_then combinator to un-nest one of our match statements. Let's ignore the None from read_zsets!, as it's not different than the None from zset.score.

match read_zsets!(state, &zset_key).and_then(|zset| zset.score(&member)) {
  Some(score) => ReturnValue::IntRes(score),
  None => ReturnValue::Nil
}

Ok, it's better. But now the line is long and awkwardly formatted. Using and_then transformed our type into Option<Score>, and we would like Option<ReturnValue::IntRes>. We can get there with a map:

read_zsets!(state, &zset_key)
    .and_then(|zset| zset.score(&member))
    .map(ReturnValue::IntRes)

Now our only problem is the return type. We've reached Option<ReturnValue::IntRes>, so we can use the unwrap_or method to deal with the missing key case:

read_zsets!(state, &zset_key)
    .and_then(|zset| zset.score(&member))
    .map(ReturnValue::IntRes)
    .unwrap_or(ReturnValue::Nil)

We did it! We've concisely encoded ZSCORE in rust in a hard-to-fuck-up way. Any sweeping refactors won't forget to change a branch, as there's no branches. You've just transformed the types a few times to achieve the desired result.

The example above may seem clear to you, but sometimes it's easy to get caught up in a flow.

So what exactly does map do, and how is it different from and_then?

Thanks to modern software engineering practice, we can just check the source code.

Here's how rust implements map on an Option<T>. The signature below says: I take a function with one parameter, T, which returns a type U. I will then give you can an Option<U>.

pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> Option<U> {
    match self {
        Some(x) => Some(f(x)),
        None => None,
    }
}

So this seems reasonable. It's similar to the python and javascript examples above. However, that Some(f(x)) can cause issues. What is my function returns an option, like zset.scores? Welp, this expression:

read_zsets!(state, &zset_key)
    .map(|zset| zset.scores(&member))

Has type Option<Option<Score>>. Not good. That's why and_then exists:

pub fn and_then<U, F: FnOnce(T) -> Option<U>>(self, f: F) -> Option<U> {
    match self {
        Some(x) => f(x),
        None => None,
    }
}

So and_then will not wrap our result in Some, and instead relies on the passed function to return an Option. So that's why we used it in our previous example. zset.score returns an option, so let's just use its option instead!

Overall, combinators are useful for making concise type transformations. You can decompose your problem into a series of handy transformations, and work your way to the solution. This is very common in functional languages, like haskell's do notation or clojures threading macro (nil punning).

For sure, if this ends up on hackernews, someone will point out the issues with combinators. The worst of them is probably the "what type am I working with?" or borrowing issues.

That said, their use in redis-oxide is likely of great benefit, especially for future maintenance.

The best investment you can make to get through UW is to invest your spare time and resources into bettering yourself. There's the obvious advice: hit the gym, eat better, and sleep longer. That advice is well elaborated elsewhere.

I think there's some bigger advice that's often less-internalized than it should be.

What I feel is underappreciated is the need to focus on what you want, and determine pathways to get there. You're probably young and if you're at UW, you're surrounded with opportunity.

This is not new advice, as most self-help resources ask you to set a goal, and sub-goals to work towards it. This is easy to think about and easy to apply in linear pathways (e.g. you can do assignments one question at a time), but difficult to apply in less linear pathways, like life.

Life winds about. Things happen. You have successes, upsets, and plateaus. It can be easy to get caught up in the moment; survive day-by-day.

Long term planning, by contrast, is more difficult. There are many things working against you here:

1. Failure is something most people don't want to ponder. It's often sickening.
2. It's easy to excuse yourself (and not others!). Your brain is wired to protect itself.
3. It's easy to dream unrealistic dreams; easier to think than act.
4. You're human. You're not "ideal". You will make mistakes, miss things, and probably be hypocritical.

These points center around failures of one kind or another. I obsess over these four points as they offer great advice on how to get to where I want to be. So, with these flaws in mind, what should you do?

First things first, you need to determine what you want. I want financial success and a stable career, and use this a platform for some sort of philanthropy. I'm sort of wired for this stuff, as I've known this from my early teens. So, unless you've been blessed like me, you'll need to determine your values and use those to guide you. Note: If you don't know what you want, that's OK. You should ensure you're always keeping opportunities open for yourself when you figure it out.

Then, you need to make plans. I've developed a system I call the "delta system". I'm sure someone else has invented it prior (or its common knowledge), but in the same way I don't blog unless I've made the blogging platform, I won't follow it. This simple system is then: Measure where you are today, where you were previously, and where you want to be.

The measuring part is obviously an important part. Look critically at your life. If you experienced a failure, what caused it? If you had a success, what lead to it? Are you happy with plateauing, or can you achieve more?

Now, once you've accessed where you are, determine the delta required. What actions can you take to get closer to your goals? What actionable item could you be doing in the short-term, to invest in long-term success? For example, if you want long term financial stability, setting up a budget is an immediate delta to achieving it. Or if your long-term goal is career success, and you're failed previously at communication, your immediate delta is to find advice. Your later deltas would be to implement identified solutions.

Now, this is simultaneously a little robotic and highly personal, and that's on purpose. If modern times have shown anything, it's that gamified systems are easier to follow. (see: mobile games, snowball debt repayment, Chinese social credit score)

A personal example of this is the process I underwent to get into UW. I had long wanted a good career, and it was now time to identify pathways. At this time tech was ballooning despite the economic crisis, and this was a topic I had interest in.

Now, I was a pretty bad junior high-school student, with subpar grades to get into a good university. I had to get serious. I took to khan-academy and took a serendipitously timed math course in the summer between grades nine and ten. Great! I had the grades, but I realized I needed more. My next delta would be to build a portfolio, to help me get into UW and land my work tech job. So I built a portfolio. And then things worked out.

I made the necessary investments, and often little more. Do keep in mind that this paragraph does not detail the years of blood, sweat, and tears that go into something like this. A five hundred character "delta system" does not guarantee success, it merely organizes the effort that goes into being successful.

My final note on investing in yourself is just this: Just a Gödel showed a mathematical system cannot prove itself¹, an imperfect character cannot perfectly determine his own character. You need to surround yourself with positive, supportive people, and carefully learn from them.

Now that we've made it past personal philosophy, we can talk about more practical matters. As a UW student, you'll need to compete against your fellow students for coveted positions. This means you need to good at what you do. For CS, in particular, there are a few areas to get good at:

1. You should understand common algorithms data structures, and internalize their concepts.
2. You should be proficient in at least one industry language (One of C/Python/Java/JS² is fine), along with proficiency with industry tech.
3. You should understand that getting an interview, doing an interview, and working a full-time job are three separate skills.

So, let's wade deeper.

This section will probably yield the best time savings relative to the effort.

In my previous blog article I described the importance of having an optimized system for editing text, and this section will deal with having optimized systems for producing documents.

I've developed a few such templates, and I'll share three of them.

All said UW is like any university, plus the constant job-finding part. It's a lot of work, but if you make good investments, it's way easier.

David Briggs

I've been programming for around ~7 years now, and have been using emacs for like 6 years. It's really like home for me. I used a really crappy laptop (bad at the time even), so GUI programming wasn't a question. So I started out building things like calculators, zork style games, and other text based things. My timeline would then be:

1. Create god-awful scripts & games using Python's IDLE on Windows. All text of course.
2. Experiment with Linux, finding out IDLE doesn't come by default, and not understanding you can just install it
3. Trying out vim and noping out (how do I exit?)
4. Use emacs with cua-mode, which lets you use windows keybindings for copy/paste (ctrl+c/ctrl+v). Feel like a HackerMan.
5. Pickup clojure as hey, lisp and emacs are like PB&J. (paredit is something special).
6. Develop repetitive motion injury (emacs pinky) developing my first real project.
7. Shop around for an alternative, and read about vim's modal paradigm. How it prevents your hands from moving too much.
8. Get frustrated with evil-mode (vim keybinding for emacs), discover spacemacs.
9. Spend the next year flipping between emacs mode and vim mode. Learn enough vim to be dangerous.
10. Learn and tinker with spacemacs ad-infinitum.

The biggest thing that comes to mind is uniformity.

I literally don't need to think, it's all in my hands. Everything just sort of works the same or similarly¹. For example, I had to recently learn scala for my latest job, and the Spacemacs scala layer (functionality related to something) works pretty much the same as all of the other layers. I just add the scala layer to my .spacemacs file, carefully read the documentation, and I'm up to speed. All of the keybindings and behaviors I expect are there. It's a beautiful thing.

The second biggest thing, is that spacemacs just works. I mean that everything mostly works out of the box. If you've been in this scene for years, that's just a treat. Take for example, the footnotes at the bottom of this blog article. Those didn't exist in version 303f29b of my site. To implement that, I literally just:

1. SPACE+b+b, type blo, this fuzzy finds blog.rs, hit enter, this opens the file, and I add the footnote field to the OrgModeHtml field.
2. / to quickly search though blog.rs for slug (the closest field to footnote), and add the parsing logic.
3. SPACE+p+f to open a fuzzy searcher for all project files, and add the footnote section to blog_article.tera.html.
4. cargo test to make sure I didn't break parsing somehow.
5. Spend another few minutes coding after you realize footnotes aren't nested, as you need a Option<Vec<String>> to collect footnotes.

This whole process took less than six minutes. You're following an optimized² text editing paradigm. You've spent years slowly memorizing a myriad of obscure keybindings³, so you get quick at making changes.

This is mostly thanks to vim's modal text editing model, and Spacemacs fantastic keybinding system.

So if you're already familiar with this concept, this section won't do you much. Otherwise, lets talk about it with some examples.

In most IDE's and text editors, you probably use the mouse for at least some things. If you're just starting out, you'd probably use the mouse quite a lot (I did anyway, that's what you're used to).

The central idea of advanced text editing techniques is that using the mouse is slow and (for me) bad for your wrists. So, ditch it. Try not to use it.

Ok, so now we can't use the mouse. How do we move around in a file? We have, uh arrow keys?

No, we literally learn another language to move around in and edit a file.

In particular, vim's syntax is more-or-less <repeat> verb modifier object. You more-or-less program your editor to program things for you. Then verbs are things like "move" or "change", modifiers are kinda complicated ("in", "find"), and objects "words", "blocks", "matching". The <repeat> is a cheap way of running the same sentence over again <repeat> times. It's just a number.

Furthermore, it's called "Modal" because there's modes. In vim, you start in normal mode. This is where you can use most of the features of vim. There's also insert mode, where vim functions like most editors (i.e. you can actually type text), and then visual and visual-block mode. As you don't have a mouse, you sometimes want to select a big chunk of text. You can visually do that with visual or visual-block mode. Or you can use more complex vim sentences 😅. There's a lot of choice in this stuff.

If you're not familiar with the topic already, this may seem complicated. But it's scary just like Привет ("hello") looked scary before I took Russian 101. Lets do some quick examples. As there's no mouse, you'll have to pay attention to the cursor (denoted |).

Aside from being emacs, offering a solid vim experience, Spacemacs has plenty for the average developer.

1. Its layer system makes it very easy to add further languages and other random bits of functionality
2. Its consistent and discoverable key sequences. Seriously, hit SPACE read all the crazy stuff you can do.
3. Its emacs, and therefore, literally infinitely customizable. I recently spent a day getting Firefox to work in a buffer just so I don't have to leave emacs
4. If the programming language exists, it's got an emacs mode (roughly translate to a spacemacs layer).
5. Spacemacs tries it's best to make vim work everywhere in emacs.

What's crazy is that this stuff 1 - works 2 - works together. That section above on Visual-Block mode also works in the Emacs file browser (generally dired). Need to prefix 45 test files with "test_" (so that foo.py becomes test_foo.py)? It's the same stuff, over again. Enter the dired edit mode, enter visual block mode, select the start of every file (hit G), add test_, and hit escape. you just renamed 45 files in like 5 seconds. No need for bash scripts like:

for i in $(ls); do
  mv $i test_$i
done

All you really need is emacs.

Expanding on the list above, here's some useful techiques I use frequently:

Rocket makes it pretty quick to get a website started. The simplest rocket project would involve:

0 - Making sure you're on a nightly toolchain:

➜  rustup toolchain install nightly
➜  rustup default nightly

1 - Making a new project

➜  cargo new my-rocket

2 - Adding rocket to my-rocket/Cargo.toml

[dependencies]
rocket = "0.4.0"

3 - Adding the rocket route & server launch in my-rocket/src/main.rs

#![feature(proc_macro_hygiene, decl_macro)]
#[macro_use]
extern crate rocket;

#[get("/")]
fn hello() -> &'static str {
    "Hello, world!"
}

fn main() {
    rocket::ignite().mount("/", routes![hello]).launch();
}

4 - Running the project (cargo run), and view localhost:8000 in a browser (or just curl it) (images aren't supported yet 😅)

➜ curl localhost:8000
Hello, world!%

(the % is just indicating there's no newline at the end)

There's three pieces to talk about here: Rust/Rocket, Tera/Bootstrap, and Production.

1. For Rust/Rocket, we'll need to figure out how to represent the website, and then wire things together.
2. For Tera/Bootsrap, we'll need to figure out to make and style the content.
3. For Production, we'll need to figure how to get certs for HTTPS, and how to serve our content.

If you just want the code, you can take it from the first commit of this website.