Dear epigrammers...
I hope the attached code isn't considered too long for a mailing list.
No it's not. It's good to see programs. Often helpful if you attach the file as that makes it slightly easier for others to bung in to the system to see what happens.
Here's the train of thought: Define a Tuple type parameterised by the list of types of its elements, define vectors of length n as usual. Now if a tuple happens to be such that it contains only vectors over the same type X, but of possibly different lengths, there should be a tuple concat function.
Quite so.
I tried to define it, but epigram thinks there is a type error in my last clause.
Hmmm...
[..]
------------------------------------------------------------------------------
( f : X -> Y -> Y ; a : Y ; ns : List X ! let !-----------------------------------------! ! fold f a ns : Y ) fold f a ns <= rec ns { fold f a x <= case x { fold f a nil => a fold f a (cons x xs) => f x (fold f a xs)
} } ------------------------------------------------------------------------------
I always find it a little ironic when people define recursion operators in Epigram, given that Epigram translates pattern matching programs into applications of recursion operators.
( ns : List Nat ! let !---------------! ! sum ns : Nat ) sum ns => fold plus zero ns
This may be shorter, but given the interactive generation of lhss, the direct first-order definition is not much more work.
Anyhow...
------------------------------------------------------------------------------
( ns : List Nat ; t : Tuple (nvecs ns X) ! let !-----------------------------------------! ! tconcat t : vec (sum ns) X ) tconcat t <= rec t { tconcat x <= case x { tconcat x <= case ns { tconcat unit => vnil } tconcat x' <= rec ns { tconcat x'' <= case x { tconcat (tcons x' t) [=>append x' (concat t)]
} } } } ------------------------------------------------------------------------------
It's hard to follow non-interactively, due to the way epigram renames variables.
Yes, this requires effort to fix, but I think I know what to do. It's just taking names from the types of the eliminators. For case, these come from the names you supply when you declare data structures. For rec, it's even more annoying, because it's always x. My proposed fix is to make beta-0 do alpha. I mean, when you have an abstraction instantiated by a _variable_, eg
(lam xs => blah) ys
not only should we get [ys/xs]blah; we should also change x to y in all of blah's _bound_ variables. This fix would mean that rec preserves names, and that case chooses names more sensitively with respect to the name of the scrutinee.
Furthermore when I reimport this into epigram en masse it gets confused, now flagging type errors at the case statements. It looks like it is generating variable names differently now.
It's a pain, I know. There's inevitably a difference between (1) just printing out names from an interactively generated lhs (2) establishing the correspondence between a program-supplied lhs and the programming problem it's meant to represent.
The way it's done just now, the wheels do have a tendency to come off the wagon, especially when you use variables on the rhs which aren't explicitly bound on the left (mutter unhiding).
I just replaced the whole body of tconcat with a shed, and now I have the following mystifying information from horace:
: List Nat ; ' : * ; x : Tuple (nvecs ')
It seems to have renamed ns to empty string, and X to emptystring primed.
Yes, that's the cumulative effect of two non-cooperative hacks. (1) Horace doesn't do any renaming apart from capture avoidance; it just blats out what it's given. (2) The lhs checker (as opposed to the lhs generator) works by erasing all the names, then filling back in just those names which get bound on the left.
Hence (1) Horace prints out variations on the empty name for hidden variables in reloaded programs and (2) if you use a name out of scope when programming interactively (because I'm book-keeping the scope of values, not their names, bad Conor), your program is pretty much guaranteed to break when you load it back in.
Going back to the interactive approach (putting the type declaration of tconcat back into sheds and re-elaborating fixes the variable name problems), this time doing the case statements in the other order, I get as far as:
tconcat t <= rec t { tconcat x <= case ns { tconcat x => vnil tconcat x' <= case x' { tconcat (tcons x' t) [=>append x' (tconcat t)]
} } }
Horace helpfully tells me that the type of tconcat (tcons x' t) is supposed to be:
vec (plus x (fold (lam n;m => plus n m) zero xs)) X
and that it already knows;
x': vec x X t : Tuple (nvecs xs X)
it seems to me that it should be able to typecheck (append x' (tconcat t)) as having precisley the required type, but it doesn't seem to.
I have a suspicion about what's going on and what may fix it. For once, (I hope), Epigram is behaving reasonably. I think Epigram is mystefied by this problem because it can't figure out the implicit list-of-lengths argument to tconcat all by itself. Because this arg is implicit, it's actually trying to solve
Tuple (nvecs xs X) = Tuple (nvecs ? X) plus x (sum xs) = plus x (sum ?)
It's not clever enough to figure out that ? = xs, and rightly so: this conclusion only follows from the injectivity of nvecs, and there's no way Epigram is going to spot that without some help. Of course, it's very plausible to take ? = xs, but I'm very nervous about making an automatic system take choices which are merely plausible, as opposed to most general.
I'd suggest making ns an explicit argument of tconcat: this will resolve the scoping problem and also (hopefully) let you supply the extra clue which the system needs. In any case, inferring ns from the tuple involves running nvecs backwards!
Why not give that a go; shout if it's still broken?
Must dash
Conor
