¶There shouldn't be any names in S₀

2023-09-24

One of the points I made in my Strange Loop talk is that a defining characteristic of a stack language is that it doesn't use names to refer to the values that the program operates on.

Concatenative programming and stack-based languages

The first iteration of S₀ was not stack-based, and was instead heavily based on names. For instance, in the name-based S₀, we had a test case that we could load an empty module. It looked like this:

module empty.load_empty_s0 {
  $load:
  containing ()
  receiving ($loaded, empty.s0)
  {
    $module = closure containing (empty.s0) -> main;
    -> $loaded ($module);
  }

  main:
  containing (empty.s0)
  receiving ($finish)
  {
    $return = closure containing ($finish) -> main@exit;
    -> empty.s0 drop ($return);
  }

  main@exit:
  containing ($finish)
  receiving ()
  {
    -> $finish succeed ();
  }
}

Many of the details are irrelevant for this note. But note that values have names (and typically receive their values through a `name = something` statement of some kind). And blocks have names too! There are three in this example: ‘$load’, main, and ‘main@exit’. (There is a syntax to give named blocks multiple named branches, which isn't shown here. These three blocks all have a single branch, whose name is the empty string.)

Last year I decided to change S₀ to be concatenative.

Should Swanson be concatenative?

In the current stack-based iteration of S₀, the above test now looks like:

module empty.load_empty_s0 {
  # loader
  nil <1
  # [] loader
  :>load (empty) <2 cons <1
  # [empty] loader
  :drop
  # [empty]
  enclosed %empty.load_empty_s0
  # test

  &&
  # harness [empty]
  uncons >1 dropnil
  # harness empty
  :drop
  :succeed
}

I'm not describing the syntax here, but note that there are no names, either for values or for blocks! The lack of names for values was very intentional — the primary thought was to replace the “environment” (a mapping from names to values) with a stack (a list of unnamed values). But in putting this together, it turned out there were no names for blocks either. At first I assumed this was just a oversight. Or maybe not an oversight — something that I would punt on at first. At some point down the line, I would figure how to bring named blocks back into the S₀ syntax. I assumed that this would be necessary to make it easier to write maintainable S₀ code.

But I no longer think that's true! Higher-level languages will have all sorts of named entities that they'll need to track. And the current hunch is that should all be simulated inside of an interpreter for each of those languages. There will end up being various “symbol table” or “environment” types, as needed by each of those higher-level languages. But S₀ is not higher-level, (now) does not have any names, and we shouldn't spackle them on in attempt to solve some other language's problems.

..