Backquotes and Iterators

One of the intended features of Wombat was to firmly disengage names from values. The process of incorporating holes into Wombat revealed that I’d got it wrong. I want to use a backquote (`) prefix to mean “this is a new name, unrelated to any outer use of this name”, but also to indicate that this was a hole waiting for a value. As always, any such confusion between names and values causes things to not fit together. Here is the new syntax:

The backquote introduces a new name and is only used on the first appearance of that name. This also applies for free variables. For ordinary variables the scope extends to the end of the current explicit closure or current file if at file level. For free variables it just extends to the the next use of backquote on that name. This allows reuse of free variable ids, which is something mathematicians do a lot.

When the thing being defined by unification is the result of a function call then there is a separate hole for each possible input value. So we can add unifications for other input values as long as they are compatible:

   `fact 0 = 1;
   fact 1 = 1;
   fact (`n:Int >? 0) = n * fact (n - 1);

The 2nd line is redundant, but harmless. The 3rd line implicitly contains

   fact 1 = 1 * fact 0;

But since both left and right sides are already defined, it is just a check.

If you have mutual recursion, you just put the backquote on the forward reference. The fact that it starts out life as a hole doesn’t matter as long as it is filled before its value is needed. This allows forward references in procedures defined in the multiple pattern style shown here for fact. This means the first occurrence at the same level. Forward references in inner explicit closures don’t need and shouldn’t have a `, and indeed putting one there would create a new and different name.

Every value starts out life as a hole and acquires a list of unifications that it has to satisfy. A hole can only be filled once - it is not a mutable value. Every time a hole gets filled then all the unifications that are associated with that hole are rerun and either resolved or updated to have that new value instead of the hole. So:

   `x + 1 = 7 # sets x to 6
   `y + 1 = `z # guaranteed relation between x and y
   z = 42 # resolves z and y

Once a hole is filled it has a value and a type.

Note that you can put new names separately, with optional constraints, and not use backquotes in actual expressions.

   `x:Int;
   x + 1 = 7 # sets x to 6

---

Iterators

Iterators are nice, but I didn’t want to introduce them without sticking to the “everything is a procedure” plan. Here’s the construct, which replaces the previous use of `{...}. Note that the uses below of backquote in operators `{, `yield and `( have nothing to do with its use for names as above.

A value of type Stream(X) is just a procedure which takes no input (Unit) and returns the head of type X and the tail which is a new Stream(X). At the end it fails non-fatally. Convenient syntax for this is now provided:

   `{ … yield expr … }

Creates a Stream(X). Each yield expression returns a head, and the tail part is a “magic” procedure that just continues execution. Note that the yield matches with the lexically enclosing `{ iterator, which will normally be in an outer procedure.

But often we just want to put a bit of a shim around one stream to create another. For this we have `yield:

   `yield {... `( expr ) ...}

The expr will be Stream(X), but `(expr) just gives the head. What is yielded is the result of the explicit closure. When going to the next result it reexecs the whole thing, but advancing all the lexically enclosed streams in `(..). If one of those finishes they must all finish, and then it moves on looking for other yields. [It has to be a closure for repeated execution.]

So to take a list and return a stream of pairs of lists which partition it:

`unappend = `{
   yield ([],$); # first partition is empty list and input list
   case $ of [
       { $=[];} # no yield, will end Stream
       { $=prepend(`h,`t);# prepend should have some nicer syntax like (`h | `t)
         `yield {(`pre,`post)=`(unappend(t)); (prepend(h,pre),post)} ;}
   ];
}

Well it’s not logic programming, but it’s pretty cute. So I think I’ll give up on logic programming.

I think I’ve resolved all the issues that were worrying me, so I plan to implement a first version of wombat with dynamic typing, no attempt at optimization, and built around python3 as the combined compiler/wctl/target. Hopefully I’ll get something onto github some time this year. Implementation will doubtless reveal errors in the design, and I’ll put updates here, and hopefully also write some better documentation.