On Fri, Sep 03, 2004 at 11:16:35AM +0100, Conor T McBride wrote:
[sum defined in terms of fold]
> This may be shorter, but given the interactive generation of
> lhss, the direct first-order definition is not much more work.
Indeed not, but it takes up more paper/screen realestate. Or it would
in a program which contained more than one use of fold, anyway.
> 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.
That would be nice.
> 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.
So I need to make my implicit arguments explicit, then. The only
problem with this is that when I define what I think is the type of a
function, it isn't always obviously to me which of the implicit
arguments are going to end up being explicitly used...
> 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.
Whereas in my head I'm thinking of nvecs as a type constructor, and
hence obviously injective. But actually it isn't a type constructor,
it's a general function on types which I just happen to know is
injective. (Epigram can do this inference with type constructors,
can't it?)
> 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?
Yep, that fixed it, thanks.
I also managed to define rev on lists (needs a 'cons-on-the-right'
otherwise the tyep checker can't 'see' how the recursion works, I
think), and then work up to rev on tuples (trev: Tuple XS -> Tuple
(rev XS)). It was quite satisfying defining the latter and watching
case statements collapse away...
It was also quite clear from Horace's output that the system would be
well placed to make good guesses for what you might want to
write. E.g.:
( t : Tuple XS !
let !-------------------------!
! trev t : Tuple (rev XS) )
trev t <= rec t
{ trev x <= case x
{ trev unit => [*]
trev (tcons x t) => [**]
}
}
*: at *, horace knows the return type is Tuple nil; and it knows that
Tuple has only one constructor for Tuple nil, namely unit. Of course,
there might be functions which return Tuple nils as well... but still,
it would only be a suggestion
**: a bit messier, but horace's type information here is Tuple (rcons
X (rev XS)). There isn't a constructor in that form (indeed rcons
and rev are functions not constructors anyhow), but there is the
function rtcons : X->XS->Tuple (rcons X XS). In a sufficiently big
program there might be unfeasibly many possible functions which return
suitable shaped types, but it would be a cool feature indeed to
provide some guesses...
It could even guess the first argument, since x is the only type
in scope of type X. The second argument, well... that would be really
clever stuff if you can guess the recursive application. Mind you, it
is not unexpected: I've already declared my intent to recurse, so the
subexpression (tconcat t) is expected to occur somewhere (since this t is
the only subterm of the original t).
Jules