Imp: core language

Last updated 2019-09-30

This is a part of a series - start at the beginning.

What do I want out of the core language?

• simple denotational semantics
• no evaluation order
• logical data independence
• amenable to parallel evaluation
• amenable to incremental maintenance

The datalog family of languages fits the bill, but they struggle to express and compress many kinds of patterns that we take for granted in other languages. So let's start in that vicinity and see how much expressiveness we can claw back without sacrificing the goals above.

This page is running a (very naive) imp interpreter. You'll need a reasonably modern browser with javascript enabled to see the examples.

imp requires javascript!

All the examples are editable - just click on the input text and type.

Sets

The value of an imp expression is always a set of tuples of scalar values (integers, strings etc).

If you just type in a single scalar value, you get back a set containing one tuple containing that scalar value.

The repl displays a set of tuples as a table, where each row is one tuple.

We can build more complex sets by using union (`|`), product (`x`) and intersect (`&`).

We can name things.

Names are lexically scoped, can shadow older names and do not allow recursive definitions.

There are two important sets that have their own names - `none` is the empty set and `some` is the set containing a single empty tuple.

Coincidentally, these sets behave like booleans, where `none` is falsey and `some` is truthy.

We can check if a set is empty or not using negate (`!`).

We can use `none` and `some` to imitate conditionals.

This is a bit hard to follow though, so we'll add some sugar.

Lastly, the equals (`=`) operator allows testing if two sets are equal.

Apply

So far, pretty simple. The next operator is a weird one. Here is the pseudocode.

``````fn apply(set_a, set_b) {
let mut result = Set::new();
for tuple_a in set_a {
for tuple_b in set_b {
let n = min(tuple_a.len(), tuple_b.len());
if tuple_a[0..n] == tuple_b[0..n] {
result.insert(
product(
tuple_a[n..],
tuple_b[n..],
)
)
}
}
}
result
}
``````

It will make more sense with some examples.

Applying a scalar to a scalar effectively just tests if they are equal.

(Remember that we think `none` is falsey and `some` is truthy.)

Applying a set to a scalar behaves like a lookup.

Applying a set to another set lets us lookup multiple values at once.

We can keep on applying values to test if a particular tuple is in a set.

Apply works in either direction, so we can also use it to chain lookups.

(Apply is left-associative, so `"apples" colors fancy` means `("apples" colors) fancy`.)

Apply is a pretty flexible operator. Maybe too flexible. We'll see.

Abstract

The abstract operator creates functions.

Hang on...

Isn't every expression supposed to return a set?

Well, the value of `inc` is a set of tuples. It just happens to be an infinite set, containing the tuples `0 x 1 | 1 x 2 | 2 x 3 ...` and so on. When we say `inc 0` we're just looking up the value `0` in that infinite set and finding a `1`.

Infinite sets aren't very space efficient though, so it happens that the interpreter stores `inc` as a closure.

But that doesn't change the important fact that we have a clearly defined meaning for `inc`. Which means that if someone writes something crazy like...

...we have a way to decide whether or not that was the correct result. Or at least we will in the next post when I actually write down the denotational semantics.

In the meantime, let's see what functions are good for.

We can project or rearrange the values within a set.

That last two might be surprising.

What does `fruit -> some` mean? It's a set where for any value we look up, we got `some` ie that value is in the set. So `fruit -> some` must be the set of all possible tuples of length 1.

Similarly `fruit -> none` is a set where for any value we look up, we got `none` ie that value is not in the set. So `fruit -> none` must be the empty set.

The interpreter is not smart enough to calculate that directly though. Not yet.

We can also use functions to define sql-style queries.

``````SELECT name, salary
FROM employees, departments, salaries
WHERE employees.name = departments.name
AND empoyees.name = salaries.name
AND departments.department = 'marketing'
``````

Here is the direct translation.

Not bad, but we can do better. This isn't datalog, after all.

That's it for now. Come back next time for semantics and interpreters.