Planet Mozilla

In my previous Dada blog post, I talked about how Dada enables composable sharing. Today I’m going to start diving into Dada’s permission system; permissions are Dada’s equivalent to Rust’s borrow checker.

Goal: richer, place-based permissions

Dada aims to exceed Rust’s capabilities by using place-based permissions. Dada lets you write functions and types that capture both a value and things borrowed from that value.

As a fun example, imagine you are writing some Rust code to process a comma-separated list, just looking for entries of length 5 or more:

letlist: String =format!("...something big, with commas...");letitems: Vec<&str>=list.split(",").map(|s|s.trim())// strip whitespace
.filter(|s|s.len()>5).collect();

One of the cool things about Rust is how this code looks a lot like some high-level language like Python or JavaScript, but in those languages the split call is going to be doing a lot of work, since it will have to allocate tons of small strings, copying out the data. But in Rust the &str values are just pointers into the original string and so split is very cheap. I love this.

On the other hand, suppose you want to package up some of those values, along with the backing string, and send them to another thread to be processed. You might think you can just make a struct like so…

struct Message{list: String,items: Vec<&str>,//         ----
// goal is to hold a reference
// to strings from list
}

…and then create the list and items and store them into it:

letlist: String =format!("...something big, with commas...");letitems: Vec<&str>=/* as before */;letmessage=Message{list,items};//                      ----
//                        |
// This *moves* `list` into the struct.
// That in turn invalidates `items`, which 
// is borrowed from `list`, so there is no
// way to construct `Message`.

But as experienced Rustaceans know, this will not work. When you have borrowed data like an &str, that data cannot be moved. If you want to handle a case like this, you need to convert from &str into sending indices, owned strings, or some other solution. Argh!

Dada’s permissions use places, not lifetimes

Dada does things a bit differently. The first thing is that, when you create a reference, the resulting type names the place that the data was borrowed from, not the lifetime of the reference. So the type annotation for items would say ref[list] String¹ (at least, if you wanted to write out the full details rather than leaving it to the type inferencer):

let list: given String = "...something big, with commas..."
let items: given Vec[ref[list] String] = list
    .split(",")
    .map(_.trim()) // strip whitespace
    .filter(_.len() > 5)
    //      ------- I *think* this is the syntax I want for closures?
    //              I forget what I had in mind, it's not implemented.
    .collect()

I’ve blogged before about how I would like to redefine lifetimes in Rust to be places as I feel that a type like ref[list] String is much easier to teach and explain: instead of having to explain that a lifetime references some part of the code, or what have you, you can say that “this is a String that references the variable list”.

But what’s also cool is that named places open the door to more flexible borrows. In Dada, if you wanted to package up the list and the items, you could build a Message type like so:

class Message(
    list: String
    items: Vec[ref[self.list] String]
    //             ---------
    //   Borrowed from another field!
)

// As before:
let list: String = "...something big, with commas..."
let items: Vec[ref[list] String] = list
    .split(",")
    .map(_.strip()) // strip whitespace
    .filter(_.len() > 5)
    .collect()

// Create the message, this is the fun part!
let message = Message(list.give, items.give)

Note that last line – Message(list.give, items.give). We can create a new class and move list into it along with items, which borrows from list. Neat, right?

OK, so let’s back up and talk about how this all works.

References in Dada are the default

Let’s start with syntax. Before we tackle the Message example, I want to go back to the Character example from previous posts, because it’s a bit easier for explanatory purposes. Here is some Rust code that declares a struct Character, creates an owned copy of it, and then gets a few references into it.

struct Character{name: String,class: String,hp: u32,}letch: Character=Character{name: format!("Ferris"),class: format!("Rustacean"),hp: 22};letp: &Character=&ch;letq: &String =&p.name;

The Dada equivalent to this code is as follows:

class Character(
    name: String,
    klass: String,
    hp: u32,
)

let ch: Character = Character("Tzara", "Dadaist", 22)
let p: ref[ch] Character = ch
let q: ref[p] String = p.name

The first thing to note is that, in Dada, the default when you name a variable or a place is to create a reference. So let p = ch doesn’t move ch, as it would in Rust, it creates a reference to the Character stored in ch. You could also explicitly write let p = ch.ref, but that is not preferred. Similarly, let q = p.name creates a reference to the value in the field name. (If you wanted to move the character, you would write let ch2 = ch.give, not let ch2 = ch as in Rust.)

Notice that I said let p = ch “creates a reference to the Character stored in ch”. In particular, I did not say “creates a reference to ch”. That’s a subtle choice of wording, but it has big implications.

References in Dada are not pointers

The reason I wrote that let p = ch “creates a reference to the Character stored in ch” and not “creates a reference to ch” is because, in Dada, references are not pointers. Rather, they are shallow copies of the value, very much like how we saw in the previous post that a shared Character acts like an Arc<Character> but is represented as a shallow copy.

So where in Rust the following code…

letch=Character{...};letp=&ch;letq=&ch.name;

…looks like this in memory…

        # Rust memory representation

            Stack                       Heap
            ─────                       ────

┌───► ch: Character {
│ ┌───► name: String {
│ │         buffer: ───────────► "Ferris"
│ │         length: 6
│ │         capacity: 12
│ │     },
│ │     ...
│ │   }
│ │   
└──── p
  │
  └── q

in Dada, code like this

let ch = Character(...)
let p = ch
let q = ch.name

would look like so

# Dada memory representation

Stack                       Heap
─────                       ────

ch: Character {
    name: String {
            buffer: ───────┬───► "Ferris"
            length: 6      │
            capacity: 12   │
    },                     │
    ..                     │
}                          │
                           │
p: Character {             │
    name: String {         │
            buffer: ───────┤
            length: 6      │
            capacity: 12   │
    ...                    │
}                          │
    }                      │
                           │
q: String {                │
    buffer: ───────────────┘
    length: 6
    capacity: 12
}

Clearly, the Dada representation takes up more memory on the stack. But note that it doesn’t duplicate the memory in the heap, which tends to be where the vast majority of the data is found.

Dada talks about values not references

This gets at something important. Rust, like C, makes pointers first-class. So given x: &String, x refers to the pointer and *x refers to its referent, the String.

Dada, like Java, goes another way. x: ref String is a String value – including in memory representation! The difference between a given String, shared String, and ref String is not in their memory layout, all of them are the same, but they differ in whether they own their contents.²

So in Dada, there is no *x operation to go from “pointer” to “referent”. That doesn’t make sense. Your variable always contains a string, but the permissions you have to use that string will change.

In fact, the goal is that people don’t have to learn the memory representation as they learn Dada, you are supposed to be able to think of Dada variables as if they were all objects on the heap, just like in Java or Python, even though in fact they are stored on the stack.³

Rust does not permit moves of borrowed data

In Rust, you cannot move values while they are borrowed. So if you have code like this that moves ch into ch1…

letch=Character{...};letname=&ch.name;// create reference
letch1=ch;// moves `ch`

…then this code only compiles if name is not used again:

letch=Character{...};letname=&ch.name;// create reference
letch1=ch;// ERROR: cannot move while borrowed
letname1=name;// use reference again

…but Dada can

There are two reasons that Rust forbids moves of borrowed data:

• References are pointers, so those pointers may become invalidated. In the example above, name points to the stack slot for ch, so if ch were to be moved into ch1, that makes the reference invalid.
• The type system would lose track of things. Internally, the Rust borrow checker has a kind of “indirection”. It knows that ch is borrowed for some span of the code (a “lifetime”), and it knows that the lifetime in the type of name is related to that lifetime, but it doesn’t really know that name is borrowed from ch in particular.⁴

Neither of these apply to Dada:

• Because references are not pointers into the stack, but rather shallow copies, moving the borrowed value doesn’t invalidate their contents. They remain valid.
• Because Dada’s types reference actual variable names, we can modify them to reflect moves.

Dada tracks moves in its types

OK, let’s revisit that Rust example that was giving us an error. When we convert it to Dada, we find that it type checks just fine:

class Character(...) // as before
let ch: given Character = Character(...)
let name: ref[ch.name] String = ch.name
//            -- originally it was borrowed from `ch`
let ch1 = ch.give
//        ------- but `ch` was moved to `ch1`
let name1: ref[ch1.name] = name
//             --- now it is borrowed from `ch1`

Woah, neat! We can see that when we move from ch into ch1, the compiler updates the types of the variables around it. So actually the type of name changes to ref[ch1.name] String. And then when we move from name to name1, that’s totally valid.

In PL land, updating the type of a variable from one thing to another is called a “strong update”. Obviously things can get a bit complicated when control-flow is involved, e.g., in a situation like this:

let ch = Character(...)
let ch1 = Character(...)
let name = ch.name
if some_condition_is_true() {
    // On this path, the type of `name` changes
    // to `ref[ch1.name] String`, and so `ch`
    // is no longer considered borrowed.
    ch1 = ch.give
    ch = Character(...) // not borrowed, we can mutate
} else {
    // On this path, the type of `name`
    // remains unchanged, and `ch` is borrowed.
}
// Here, the types are merged, so the
// type of `name` is `ref[ch.name, ch1.name] String`.
// Therefore, `ch` is considered borrowed here.

Renaming lets us call functions with borrowed values

OK, let’s take the next step. Let’s define a Dada function that takes an owned value and another value borrowed from it, like the name, and then call it:

fn character_and_name(
    ch1: given Character,
    name1: ref[ch1] String,
) {
    // ... does something ...
}

We could call this function like so, as you might expect:

let ch = Character(...)
let name = ch.name
character_and_name(ch.give, name)

So…how does this work? Internally, the type checker type-checks a function call by creating a simpler snippet of code, essentially, and then type-checking that. It’s like desugaring but only at type-check time. In this simpler snippet, there are a series of let statements to create temporary variables for each argument. These temporaries always have an explicit type taken from the method signature, and they are initialized with the values of each argument:

// type checker "desugars" `character_and_name(ch.give, name)`
// into more primitive operations:
let tmp1: given Character = ch.give
    //    ---------------   -------
    //            |         taken from the call
    //    taken from fn sig
let tmp2: ref[tmp1.name] String = name
    //    ---------------------   ----
    //            |         taken from the call
    //    taken from fn sig,
    //    but rewritten to use the new
    //    temporaries

If this type checks, then the type checker knows you have supplied values of the required types, and so this is a valid call. Of course there are a few more steps, but that’s the basic idea.

Notice what happens if you supply data borrowed from the wrong place:

let ch = Character(...)
let ch1 = Character(...)
character_and_name(ch, ch1.name)
//                     --- wrong place!

This will fail to type check because you get:

let tmp1: given Character = ch.give
let tmp2: ref[tmp1.name] String = ch1.name
    //                            --------
    //       has type `ref[ch1.name] String`,
    //       not `ref[tmp1.name] String`

Class constructors are “just” special functions

So now, if we go all the way back to our original example, we can see how the Message example worked:

class Message(
    list: String
    items: Vec[ref[self.list] String]
)

Basically, when you construct a Message(list, items), that’s “just another function call” from the type system’s perspective, except that self in the signature is handled carefully.

This is modeled, not implemented

I should be clear, this system is modeled in the dada-model repository, which implements a kind of “mini Dada” that captures what I believe to be the most interesting bits. I’m working on fleshing out that model a bit more, but it’s got most of what I showed you here.⁵ For example, here is a test that you get an error when you give a reference to the wrong value.

The “real implementation” is lagging quite a bit, and doesn’t really handle the interesting bits yet. Scaling it up from model to real implementation involves solving type inference and some other thorny challenges, and I haven’t gotten there yet – though I have some pretty interesting experiments going on there too, in terms of the compiler architecture.⁶

This could apply to Rust

I believe we could apply most of this system to Rust. Obviously we’d have to rework the borrow checker to be based on places, but that’s the straight-forward part. The harder bit is the fact that &T is a pointer in Rust, and that we cannot readily change. However, for many use cases of self-references, this isn’t as important as it sounds. Often, the data you wish to reference is living in the heap, and so the pointer isn’t actually invalidated when the original value is moved.

Consider our opening example. You might imagine Rust allowing something like this in Rust:

struct Message{list: String,items: Vec<&{self.list}str>,}

In this case, the str data is heap-allocated, so moving the string doesn’t actually invalidate the &str value (it would invalidate an &String value, interestingly).

In Rust today, the compiler doesn’t know all the details of what’s going on. String has a Deref impl and so it’s quite opaque whether str is heap-allocated or not. But we are working on various changes to this system in the Beyond the & goal, most notably the Field Projections work. There is likely some opportunity to address this in that context, though to be honest I’m behind in catching up on the details.

Righty-ho, I’m back from Rust Nation, and busily horrifying my teenage daughter with my (admittedly atrocious) attempts at doing an English accent¹. It was a great trip with a lot of good conversations and some interesting observations. I am going to try to blog about some of them, starting with some thoughts spurred by Jon Seager’s closing keynote, “Rust Adoption At Scale with Ubuntu”.

There are many chasms out there

For some time now I’ve been debating with myself, has Rust “crossed the chasm”? If you’re not familiar with that term, it comes from a book that gives a kind of “pop-sci” introduction to the Technology Adoption Life Cycle.

The answer, of course, is it depends on who you ask. Within Amazon, where I have the closest view, the answer is that we are “most of the way across”: Rust is squarely established as the right way to build at-scale data planes or resource-aware agents and it is increasingly seen as the right choice for low-level code in devices and robotics as well – but there remains a lingering perception that Rust is useful for “those fancy pants developers at S3” (or wherever) but a bit overkill for more average development³.

On the other hand, within the realm of Safety Critical Software, as Pete LeVasseur wrote in a recent rust-lang blog post, Rust is still scrabbling for a foothold. There are a number of successful products but most of the industry is in a “wait and see” mode, letting the early adopters pave the path.

“Crossing the chasm” means finding “reference customers”

The big idea that I at least took away from reading Crossing the Chasm and other references on the technology adoption life cycle is the need for “reference customers”. When you first start out with something new, you are looking for pioneers and early adopters that are drawn to new things:

What an early adopter is buying [..] is some kind of change agent. By being the first to implement this change in the industry, the early adopters expect to get a jump on the competition. – from Crossing the Chasm

But as your technology matures, you have to convince people with a lower and lower tolerance for risk:

The early majority want to buy a productivity improvement for existing operations. They are looking to minimize discontinuity with the old ways. They want evolution, not revolution. – from Crossing the Chasm

So what is most convincing to people to try something new? The answer is seeing that others like them have succeeded.

You can see this at play in both the Amazon example and the Safety Critical Software example. Clearly seeing Rust used for network services doesn’t mean it’s ready to be used in your car’s steering column⁴. And even within network services, seeing a group like S3 succeed with Rust may convince other groups building at-scale services to try Rust, but doesn’t necessarily persuade a team to use Rust for their next CRUD service. And frankly, it shouldn’t! They are likely to hit obstacles.

Ubuntu is helping Rust “cross the (user-land linux) chasm”

All of this was on my mind as I watched the keynote by Jon Seager, the VP of Engineering at Canonical, which is the company behind Ubuntu. Similar to Lars Bergstrom’s epic keynote from year’s past on Rust adoption within Google, Jon laid out a pitch for why Canonical is adopting Rust that was at once visionary and yet deeply practical.

“Visionary and yet deeply practical” is pretty much the textbook description of what we need to cross from early adopters to early majority. We need folks who care first and foremost about delivering the right results, but are open to new ideas that might help them do that better; folks who can stand on both sides of the chasm at once.

Jon described how Canonical focuses their own development on a small set of languages: Python, C/C++, and Go, and how they had recently brought in Rust and were using it as the language of choice for new foundational efforts, replacing C, C++, and (some uses of) Python.

Ubuntu is building the bridge across the chasm

Jon talked about how he sees it as part of Ubuntu’s job to “pay it forward” by supporting the construction of memory-safe foundational utilities. Jon meant support both in terms of finances – Canonical is sponsoring the Trifecta Tech Foundation’s to develop sudo-rs and ntpd-rs and sponsoring the uutils org’s work on coreutils – and in terms of reputation. Ubuntu can take on the risk of doing something new, prove that it works, and then let others benefit.

Remember how the Crossing the Chasm book described early majority people? They are “looking to minimize discontinuity with the old ways”. And what better way to do that than to have drop-in utilities that fit within their existing workflows.

The challenge for Rust: listening to these new adopters

With new adoption comes new perspectives. On Thursday night I was at dinner⁵ organized by Ernest Kissiedu⁶. Jon Seager was there along with some other Rust adopters from various industries, as were a few others from the Rust Foundation and the open-source project.

Ernest asked them to give us their unvarnished takes on Rust. Jon made the provocative comment that we needed to revisit our policy around having a small standard library. He’s not the first to say something like that, it’s something we’ve been hearing for years and years – and I think he’s right! Though I don’t think the answer is just to ship a big standard library. In fact, it’s kind of a perfect lead-in to (what I hope will be) my next blog post, which is about a project I call “battery packs”⁷.

To grow, you have to change

The broader point though is that shifting from targeting “pioneers” and “early adopters” to targeting “early majority” sometimes involves some uncomfortable changes:

Transition between any two adoption segments is normally excruciatingly awkward because you must adopt new strategies just at the time you have become most comfortable with the old ones. [..] The situation can be further complicated if the high-tech company, fresh from its marketing success with visionaries, neglects to change its sales pitch. [..] The company may be saying “state-of-the-art” when the pragmatist wants to hear “industry standard”. – Crossing the Chasm (emphasis mine)

Not everybody will remember it, but in 2016 there was a proposal called the Rust Platform. The idea was to bring in some crates and bless them as a kind of “extended standard library”. People hated it. After all, they said, why not just add dependencies to your Cargo.toml? It’s easy enough. And to be honest, they were right – at least at the time.

I think the Rust Platform is a good example of something that was a poor fit for early adopters, who want the newest thing and don’t mind finding the best crates, but which could be a great fit for the Early Majority.⁸

Anyway, I’m not here to argue for one thing or another in this post, but more for the concept that we have to be open to adapting our learned wisdom to new circumstances. In the past, we were trying to bootstrap Rust into the industry’s consciousness – and we have succeeded.

The task before us now is different: we need to make Rust the best option not just in terms of “what it could be” but in terms of “what it actually is” – and sometimes those are in tension.

Another challenge for Rust: turning adoption into investment

Later in the dinner, the talk turned, as it often does, to money. Growing Rust adoption also comes with growing needs placed on the Rust project and its ecosystem. How can we connect the dots? This has been a big item on my mind, and I realize in writing this paragraph how many blog posts I have yet to write on the topic, but let me lay out a few interesting points that came up over this dinner and at other recent points.

Investment can mean contribution, particularly for open-source orgs

First, there are more ways to offer support than $$. For Canonical specifically, as they are an open-source organization through-and-through, what I would most want is to build stronger relationships between our organizations. With the Rust for Linux developers, early on Rust maintainers were prioritizing and fixing bugs on behalf of RfL devs, but more and more, RfL devs are fixing things themselves, with Rust maintainers serving as mentors. This is awesome!

Money often comes before a company has adopted Rust, not after

Second, there’s an interesting trend about $$ that I’ve seen crop up in a few places. We often think of companies investing in the open-source dependencies that they rely upon. But there’s an entirely different source of funding, and one that might be even easier to tap, which is to look at companies that are considering Rust but haven’t adopted it yet.

For those “would be” adopters, there are often individuals in the org who are trying to make the case for Rust adoption – these individuals are early adopters, people with a vision for how things could be, but they are trying to sell to their early majority company. And to do that, they often have a list of “table stakes” features that need to be supported; what’s more, they often have access to some budget to make these things happen.

This came up when I was talking to Alexandru Radovici, the Foundation’s Silver Member Directory, who said that many safety critical companies have money they’d like to spend to close various gaps in Rust, but they don’t know how to spend it. Jon’s investments in Trifecta Tech and the uutils org have the same character: he is looking to close the gaps that block Ubuntu from using Rust more.

Conclusions…?

Well, first of all, you should watch Jon’s talk. “Brilliant”, as the Brits have it.

But my other big thought is that this is a crucial time for Rust. We are clearly transitioning in a number of areas from visionaries and early adopters towards that pragmatic majority, and we need to be mindful that doing so may require us to change some of the way that we’ve always done things. I liked this paragraph from Crossing the Chasm:

To market successfully to pragmatists, one does not have to be one – just understand their values and work to serve them. To look more closely into these values, if the goal of visionaries is to take a quantum leap forward, the goal of pragmatists is to make a percentage improvement–incremental, measurable, predictable progress. [..] To market to pragmatists, you must be patient. You need to be conversant with the issues that dominate their particular business. You need to show up at the industry-specific conferences and trade shows they attend.

Re-reading Crossing the Chasm as part of writing this blog post has really helped me square where Rust is – for the most part, I think we are still crossing the chasm, but we are well on our way. I think what we see is a consistent trend now where we have Rust champions who fit the “visionary” profile of early adopters successfully advocating for Rust within companies that fit the pragmatist, early majority profile.

Open source can be a great enabler to cross the chasm…

It strikes me that open-source is just an amazing platform for doing this kind of marketing. Unlike a company, we don’t have to do everything ourselves. We have to leverage the fact that open source helps those who help themselves – find those visionary folks in industries that could really benefit from Rust, bring them into the Rust orbit, and then (most important!) support and empower them to adapt Rust to their needs.

…but only if we don’t get too “middle school” about it

This last part may sound obvious, but it’s harder than it sounds. When you’re embedded in open source, it seems like a friendly place where everyone is welcome. But the reality is that it can be a place full of cliques and “oral traditions” that “everybody knows”⁹. People coming with an idea can get shutdown for using the wrong word. They can readily mistake the, um, “impassioned” comments from a random contributor (or perhaps just a troll…) for the official word from project leadership. It only takes one rude response to turn somebody away.

What Rust needs most is empathy

So what will ultimately help Rust the most to succeed? Empathy in Open Source. Let’s get out there, find out where Rust can help people, and make it happen. Exciting times!

OK, let’s talk about sharing. This is the first of Dada blog posts where things start to diverge from Rust in a deep way and I think the first where we start to see some real advantages to the Dada way of doing things (and some of the tradeoffs I made to achieve those advantages).

We are shooting for a GC-like experience without GC

Let’s start with the goal: earlier, I said that Dada was like “Rust where you never have to type as_ref”. But what I really meant is that I want a GC-like experience–without the GC.

We are shooting for a “composable” experience

I also often use the word “composable” to describe the Dada experience I am shooting for. Composable means that you can take different things and put them together to achieve something new.

Obviously Rust has many composable patterns – the Iterator APIs, for example. But what I have found is that Rust code is often very brittle: there are many choices when it comes to how you declare your data structures and the choices you make will inform how those data structures can be consumed.

Running example: Character

Defining the Character type

Let’s create a type that we can use as a running example throughout the post: Character. In Rust, we might define a Character like so:

#[derive(Default)]struct Character{name: String,class: String,hp: u32,}

Creating and Arc’ing the Character

Now, suppose that, for whatever reason, we are going to build up a character programmatically:

letmutch=Character::default();ch.name.push_str("Ferris");ch.class.push_str("Rustacean");ch.hp=44;

So far, so good. Now suppose I want to share that same Character struct so it can be referenced from a lot of places without deep copying. To do that, I am going to put it in an Arc:

letmutch=Character::default();ch.name.push_str("Ferris");// ...
letch1=Arc::new(ch);letch2=ch1.clone();

OK, cool! Now I have a Character that is readily sharable. That’s great.

Rust is composable here, which is cool, we like that

Side note but this is an example of where Rust is composable: we defined Character once in a fully-owned way and we were able to use it mutably (to build it up imperatively over time) and then able to “freeze” it and get a read-only, shared copy of Character. This gives us the advantages of an imperative programming language (easy data construction and manipulation) and the advantages of a functional language (immutability prevents bugs when things are referenced from many disjoint places). Nice!

Creating and Arc’ing the Character

Now, suppose that I have some other code, written independently, that just needs to store the character’s name. That code winds up copying the name into a lot of different places. So, just like we used Arc to let us cheaply reference a single character from multiple places, it uses Arc so it can cheaply reference the character’s name from multiple places:

struct CharacterSheetWidget{// Use `Arc<String>` and not `String` because
// we wind up copying this into name different
// places and we don't want to deep clone
// the string each time.
name: Arc<String>,// ... assume more fields here ...
}

OK. Now comes the rub. I want to create a character-sheet widget from our shared character:

fn create_character_sheet_widget(ch: Arc<Character>)-> CharacterSheetWidget{CharacterSheetWidget{// FIXME: Huh, how do I bridge this gap?
// I guess I have to do this.
name: Arc::new(ch.name.clone()),// ... assume more fields here ...
}}

Shoot, that’s frustrating! What I would like to do is to write name: ch.name.clone() or something similar (actually I’d probably like to just write ch.name, but anyhow) and get back an Arc<String>. But I can’t do that. Instead, I have to deeply clone the string and allocate a new Arc. Of course any subsequent clones will be cheap. But it’s not great.

Rust often gives rise to these kind of “impedance mismatches”

I often find patterns like this arise in Rust: there’s a bit of an “impedance mismatch” between one piece of code and another. The solution varies, but it’s generally something like

• clone some data – it’s not so big anyway, screw it (that’s what happened here).
• refactor one piece of code – e.g., modify the Character class to store an Arc<String>. Of course, that has ripple effects, e.g., we can no longer write ch.name.push_str(...) anymore, but have to use Arc::get_mut or something.
• invoke some annoying helper – e.g., write opt.as_ref() to convert from an &Option<String> to a Option<&String> or write a &**r to convert from a &Arc<String> to a &str.

The goal with Dada is that we don’t have that kind of thing.

Sharing is how Dada copies

So let’s walk through how that same Character example would play out in Dada. We’ll start by defining the Character class:

class Character(
    name: String,
    klass: String,  # Oh dang, the perils of a class keyword!
    hp: u32,
)

Just as in Rust, we can create the character and then modify it afterwards:

class Character(name: String, klass: String, hp: u32)

let ch: given Character = Character("", "", 22)
      # ----- remember, the "given" permission
      #       means that `ch` is fully owned
ch.name!.push("Tzara")
ch.klass!.push("Dadaist")
   #    - and the `!` signals mutation

The .share operator creates a shared object

Cool. Now, I want to share the character so it can be referenced from many places. In Rust, we created an Arc, but in Dada, sharing is “built-in”. We use the .share operator, which will convert the given Character (i.e., fully owned character) into a shared Character:

class Character(name: String, klass: String, hp: u32)

let ch = Character("", "", 22)
ch!.push("Tzara")
ch!.push("Dadaist")

let ch1: shared Character = ch.share
      #  ------                -----
      # The `share` operator consumes `ch`
      # and returns the same object, but now
      # with *shared* permissions.

shared objects can be copied freely

Now that we have a shared character, we can copy it around:

class Character(name: String, klass: String, hp: u32)

# Create a shared character to start
let ch1 = Character("Tzara", "Dadaist", 22).share
    #                                       -----

# Create another shared character
let ch2 = ch1

Sharing propagates from owner to field

When you have a shared object and you access its field, what you get back is a shared (shallow) copy of the field:

class Character(...)

# Create a `shared Character`
let ch: shared Character = Character("Tristan Tzara", "Dadaist", 22).share
      # ------                                                       -----

# Extracting the `name` field gives a `shared String`
let name: shared String = ch1.name
        # ------

Propagation using a Vec

To drill home how cool and convenient this is, imagine that I have a Vec[String] that I share with .share:

let v: shared Vec[String] = ["Hello", "Dada"].share

and then I share it with v.share. What I get back is a shared Vec[String]. And when I access the elements of that, I get back a shared String:

let v = ["Hello", "Dada"].share
let s: shared String = v[0]

This is as if one could take a Arc<Vec<String>> in Rust and get out a Arc<String>.

How sharing is implemented

So how is sharing implemented? The answer lies in a not-entirely-obvious memory layout. To see how it works, let’s walk how a Character would be laid out in memory:

# Character type we saw earlier.
class Character(name: String, klass: String, hp: u32)

# String type would be something like this.
class String {
    buffer: Pointer[char]
    initialized: usize
    length: usize
}

Here Pointer is a built-in type that is the basis for Dada’s unsafe code system.¹

Layout of a given Character in memory

Now imagine we have a Character like this:

let ch = Character("Duchamp", "Dadaist", 22)

The character ch would be laid out in memory something like this (focusing just on the name field):

[Stack frame]              [Heap]         
ch: Character {                           
    _flag: 1                              
    name: String {                        
        _flag: 1         { _ref_count: 1  
        buffer: ──────────►'D'            
        initialized: 7     ...            
        capacity: 8        'p' }          
    }                                     
    klass: ...                            
    hp: 22                                
}                                         

Let’s talk this through. First, every object is laid out flat in memory, just like you would see in Rust. So the fields of ch are stored on the stack, and the name field is laid out flat within that.

Each object that owns other objects begins with a hidden field, _flag. This field indicates whether the object is shared or not (in the future we’ll add more values to account for other permissions). If the field is 1, the object is not shared. If it is 2, then it is shared.

Heap-allocated objects (i.e., using Pointer[]) begin with a ref-count before the actual data (actually this is at the offset of -4). In this case we have a Pointer[char] so the actual data that follows are just simple characters.

Layout of a shared Character in memory

If I were to instead create a shared character:

let ch1 = Character("Duchamp", "Dadaist", 22).share
          #                                   -----

The memory layout would be the same, but the flag field on the character is now 2:

[Stack frame]              [Heap]         
ch: Character {                           
    _flag: 2 👈 (This is 2 now!)                             
    name: String {                        
        _flag: 1         { _ref_count: 1  
        buffer: ──────────►'D'            
        initialized: 7     ...            
        capacity: 8        'p' }          
    }                                     
    klass: ...                            
    hp: 22                                
}                                         

Copying a shared Character

Now imagine that we created two copies of the same shared character:

let ch1 = Character("Duchamp", "Dadaist", 22).share
let ch2 = ch1

What happens is that we will copy all the fields of _ch1 and then, because _flag is 2, we will increment the ref-counts for the heap-allocated data within:

[Stack frame]              [Heap]            
ch1: Character {                             
    _flag: 2                                 
    name: String {                           
        _flag: 1         { _ref_count: 2     
        buffer: ────────┬─►'D'        👆     
        initialized: 7  │  ...      (This is 
        capacity: 8     │  'p' }     2 now!) 
    }                   │                    
    class: ...          │                    
    hp: 22              │                    
}                       │                    
                        │                    
ch2: Character {        │                    
    _flag: 2            │                    
    name: String {      │                    
        _flag: 1        │                    
        buffer: ────────┘                    
        initialized: 7                       
        capacity: 8                          
    }                                        
    class: ...                               
    hp: 22                                   
}                                            

Copying out the name field

Now imagine we were to copy out the name field, instead of the entire character:

let ch1 = Character("Duchamp", "Dadaist", 22).share
let name = ch1.name

…what happens is that:

1. traversing ch1, we observe that the _flag field is 2 and therefore ch1 is shared
2. we copy out the String fields from name. Because the character is shared:
   • we modify the _flag field on the new string to 2
   • we increment the ref-count for any heap values

The result is that you get:

[Stack frame]              [Heap]       
ch1: Character {                        
    _flag: 2                            
    name: String {                      
        _flag: 1         { _ref_count: 2
        buffer: ────────┬─►'D'          
        initialized: 7  │  ...          
        capacity: 8     │  'p' }        
    }                   │               
    class: ...          │               
    hp: 22              │               
}                       │               
                        │               
name: String {          │               
    _flag: 2            │               
    buffer: ────────────┘               
    initialized: 7                      
    capacity: 8                         
}                                       

“Sharing propagation” is one example of permission propagation

This post showed how shared values in Dada work and showed how the shared permission propagates when you access a field. Permissions are how Dada manages object lifetimes. We’ve seen two so far

• the given permission indicates a uniquely owned value (T, in Rust-speak);
• the shared permission indicates a copyable value (Arc<T> is the closest Rust equivalent).

In future posts we’ll see the ref and mut permissions, which roughly correspond to & and &mut, and talk out how the whole thing fits together.

Dada is more than a pretty face

This is the first post where we started to see a bit more of Dada’s character. Reading over the previous few posts, you could be forgiven for thinking Dada was just a cute syntax atop familiar Rust semantics. But as you can see from how shared works, Dada is quite a bit more than that.

I like to think of Dada as “opinionated Rust” in some sense. Unlike Rust, it imposes some standards on how things are done. For example, every object (at least every object with a heap-allocated field) has a _flag field. And every heap allocation has a ref-count.

These conventions come at some modest runtime cost. My rule is that basic operations are allowed to do “shallow” operations, e.g., toggling the _flag or adjusting the ref-counts on every field. But they cannot do “deep” operations that require traversing heap structures.

In exchange for adopting conventions and paying that cost, you get “composability”, by which I mean that permissions in Dada (like shared) flow much more naturally, and types that are semantically equivalent (i.e., you can do the same things with them) generally have the same layout in memory.

Let’s continue with working through Dada. In my previous post, I introduced some string manipulation. Let’s start talking about permissions. This is where Dada will start to resemble Rust a bit more.

Class struggle

Classes in Dada are one of the basic ways that we declare new types (there are also enums, we’ll get to that later).

The most convenient way to declare a class is to put the fields in parentheses. This implicitly declares a constructor at the same time:

class Point(x: u32, y: u32) {}

This is in fact sugar for a more Rust like form:

class Point {
    x: u32
    y: u32
    fn new() -> Point {
        Point { x, y }
    }
}

And you can create an instance of a class by calling the constructor:

let p = Point(22, 44) // sugar for Point.new(22, 44)

Mutating fields

I can mutate the fields of p as you would expect:

p.x += 1
p.x = p.y

Read by default

In Dada, the default when you declare a parameter is that you are getting read-only access:

fn print_point(p: Point) {
    print("The point is {p.x}, {p.y}")
}

let p = Point(22, 44)
print_point(p)

If you attempt to mutate the fields of a parameter, that would get you an error:

fn print_point(p: Point) {
    p.x += 1 # <-- ERROR!
}

Use ! to mutate

If you declare a parameter with !, then it becomes a mutable reference to a class instance from your caller:

fn translate_point(point!: Point, x: u32, y: u32) {
    point.x += x
    point.y += y
}

In Rust, this would be like point: &mut Point. When you call translate_point, you also put a ! to indicate that you are passing a mutable reference:

let p = Point(22, 44)     # Create point
print_point(p)            # Prints 22, 44
translate_point(p!, 2, 2) # Mutate point
print_point(p)            # Prints 24, 46 

As you can see, when translate_point modifies p.x, that changes p in place.

Moves are explicit

If you’re familiar with Rust, that last example may be a bit surprising. In Rust, a call like print_point(p) would move p, giving ownership away. Trying to use it later would give an error. That’s because the default in Dada is to give a read-only reference, like &x in Rust (this gives the right intuition but is also misleading; we’ll see in a future post that references in Dada are different from Rust in one very important way).

If you have a function that needs ownership of its parameter, you declare that with given:

fn take_point(p: given Point) {
    // ...
}

And on the caller’s side, you call such a function with .give:

let p = Point(22, 44)
take_point(p.give)
take_point(p.give) # <-- Error! Can't give twice.

Comparing with Rust

It’s interesting to compare some Rust and Dada code side-by-side:

Design rationale and objectives

Convenient is the default

The most convenient things are the shortest and most common. So we make reads the default.

Everything is explicit but unobtrusive

The . operator in Rust can do a wide variety of things depending on the method being called. It might mutate, move, create a temporary, etc. In Dada, these things are all visible at the callsite– but they are unobtrusive.

This actually dates from Dada’s “gradual programming” days – after all, if you don’t have type annotations on the method, then you can’t decide foo.bar() should take a shared or mutable borrow of foo. So we needed a notation where everything is visible at the call-site and explicit.

Postfix operators play more nicely with others

Dada tries hard to avoid prefix operators like &mut, since they don’t compose well with . notation.

Following on my Fun with Dada post, this post is going to start teaching Dada. I’m going to keep each post short – basically just what I can write while having my morning coffee.¹

You have the right to write code

Here is a very first Dada program

println("Hello, Dada!")

I think all of you will be able to guess what it does. Still, there is something worth noting even in this simple program:

“You have the right to write code. If you don’t write a main function explicitly, one will be provided for you.” Early on I made the change to let users omit the main function and I was surprised by what a difference it made in how light the language felt. Easy change, easy win.

Convenient is the default

Here is another Dada program

let name = "Dada"
println("Hello, {name}!")

Unsurprisingly, this program does the same thing as the last one.

“Convenient is the default.” Strings support interpolation (i.e., {name}) by default. In fact, that’s not all they support, you can also break them across lines very conveniently. This program does the same thing as the others we’ve seen:

let name = "Dada"
println("
    Hello, {name}!
")

When you have a " immediately followed by a newline, the leading and trailing newline are stripped, along with the “whitespace prefix” from the subsequent lines. Internal newlines are kept, so something like this:

let name = "Dada"
println("
    Hello, {name}!
    
    How are you doing?
")

would print

Hello, Dada!
How are you doing?

Just one familiar String

Of course you could also annotate the type of the name variable explicitly:

let name: String = "Dada"
println("Hello, {name}!")

You will find that it is String. This in and of itself is not notable, unless you are accustomed to Rust, where the type would be &'static str. This is of course a perennial stumbling block for new Rust users, but more than that, I find it to be a big annoyance – I hate that I have to write "Foo".to_string() or format!("Foo") everywhere that I mix constant strings with strings that are constructed.

Similar to most modern languages, strings in Dada are immutable. So you can create them and copy them around:

let name: String = "Dada"
let greeting: String = "Hello, {name}"
let name2: String = name

Next up: mutation, permissions

OK, we really just scratched the surface here! This is just the “friendly veneer” of Dada, which looks and feels like a million other languages. Next time I’ll start getting into the permission system and mutation, where things get a bit more interesting.

Waaaaaay back in 2021, I started experimenting with a new programming language I call “Dada”. I’ve been tinkering with it ever since and I just realized that (oh my gosh!) I’ve never written even a single blog post about it! I figured I should fix that. This post will introduce some of the basic concepts of Dada as it is now.

Before you get any ideas, Dada isn’t fit for use. In fact the compiler doesn’t even really work because I keep changing the language before I get it all the way working. Honestly, Dada is more of a “stress relief” valve for me than anything else¹ – it’s fun to tinker with a programming language where I don’t have to worry about backwards compatibility, or RFCs, or anything else.

That said, Dada has been a very fertile source of ideas that I think could be applicable to Rust. And not just for language design: playing with the compiler is also what led to the new salsa design², which is now used by both rust-analyzer and Astral’s ty. So I really want to get those ideas out there!

I took a break, but I’m back baby!

I stopped hacking on Dada about a year ago³, but over the last few days I’ve started working on it again. And I realized, hey, this is a perfect time to start blogging! After all, I have to rediscover what I was doing anyway, and writing about things is always the best way to work out the details.

Dada started as a gradual programming experiment, but no longer

Dada has gone through many phases. Early on, the goal was to build a gradually typed programming language that I thought would be easier for people to learn.

The idea was that you could start writing without any types at all and just execute the program. There was an interactive playground that would let you step through and visualize the “borrow checker” state (what Dada calls permissions) as you go. My hope was that people would find that easier to learn than working with type checker checker.

I got this working and it was actually pretty cool. I gave a talk about it at the Programming Language Mentoring Workshop in 2022, though skimming that video it doesn’t seem like I really demo’d the permission modeling. Too bad.

At the same time, I found myself unconvinced that the gradually typed approach made sense. What I wanted was that when you executed the program without type annotations, you would get errors at the point where you violated a borrow. And that meant that the program had to track a lot of extra data, kind of like miri does, and it was really only practical as a teaching tool. I still would like to explore that, but it also felt like it was adding a lot of complexity to the language design for something that would only be of interest very early in a developer’s journey⁴.

Therefore, I decided to start over, this time, to just focus on the static type checking part of Dada.

Dada is like a streamlined Rust

Dada today is like Rust but streamlined. The goal is that Dada has the same basic “ownership-oriented” feel of Rust, but with a lot fewer choices and nitty-gritty details you have to deal with.⁵

Rust often has types that are semantically equivalent, but different in representation. Consider &Option<String> vs Option<&String>: both of them are equivalent in terms of what you can do with them, but of course Rust makes you carefully distinguish between them. In Dada, they are the same type. Dada also makes &Vec<String>, &Vec<&String>, &[String], &[&str], and many other variations all the same type too. And before you ask, it does it without heap allocating everything or using a garbage collector.

To put it pithily, Dada aims to be “Rust where you never have to call as_ref()”.

Dada has a fancier borrow checker

Dada also has a fancier borrow checker, one which already demonstrates much of the borrow checker within, although it doesn’t have view types. Dada’s borrow checker supports internal borrows (e.g., you can make a struct that has fields that borrow from other fields) and it supports borrow checking without lifetimes. Much of this stuff can be brought to Rust, although I did tweak a few things in Dada that made some aspects easier.

Dada targets WebAssembly natively

Somewhere along the line in refocusing Dada, I decided to focus exclusively on building WebAssembly components. Initially I felt like targeting WebAssembly would be really convenient:

• WebAssembly is like a really simple and clean assembly language, so writing the compiler backend is easy.
• WebAssembly components are explicitly designed to bridge between languages, so they solve the FFI problem for you.
• With WASI, you even get a full featured standard library that includes high-level things like “fetch a web page”. So you can build useful things right off the bat.

WebAssembly and on-demand compilation = compile-time reflection almost for free

But I came to realize that targeting WebAssembly has another advantage: it makes compile-time reflection almost trivial. The Dada compiler is structured in a purely on-demand fashion. This means we can compile one function all the way to WebAssembly bytecode and leave the rest of the crate untouched.

And once we have the WebAssembly bytecode, we can run that from inside the compiler! With wasmtime, we have a high quality JIT that runs very fast. The code is even sandboxed!

So we can have a function that we compile and run during execution and use to produce other code that will be used by other parts of the compilation step. In other words, we get something like miri or Zig’s comptime for free, essentially. Woah.

Wish you could try it? Me too!

Man, writing this blog post made ME excited to play with Dada. Too bad it doesn’t actually work. Ha! But I plan to keep plugging away on the compiler and get it to the point of a live demo as soon as I can. Hard to say exactly how long that will take.

In the meantime, to help me rediscover how things work, I’m going to try to write up a series of blog posts about the type system, borrow checker, and the compiler architecture, all of which I think are pretty interesting.