Hi Jules, hi all,
Good to hear from you. Nice to see that you've tripped over a whole bunch of issues which arise mostly because things are still a bit sketchy. So I'm doing what I usually do on this list: apologizing for the fact that I have no better source of round tuits than anyone else.
Jules Bean wrote:
On Thu, Sep 02, 2004 at 04:38:39PM +0100, Thorsten Altenkirch wrote:
Why won't length type check? the 'n' is on a yellow background.
Because there is no n on the left hand side, hence the variable is not bound.
This is true.
Surely there is an n on the left hand side, inside the type of v? Certainly horace gives me that impression
This is also true.
The unfortunate truth is that the information available from Horace when you click on a shed is computed by a routine which I knocked together in no time flat, without paying sufficient attention to ensuring that everything has a distinct (nonempty!) name and that the names which you can actually refer to are distinguished from those you can't.
The situation here is this: the length value is in scope (it's got
to exist; it's bound in the underlying programming problem); its
_name_ is not (it's not explicitly mentioned on the lhs). What
should happen instead?
(a) Horace should supply all the information, but distinguish
pattern variables you can refer to (these have `hard'
names) from things which you can't, but which need
arbitrary local names so you can see the dependencies.
(b) If you want to refer to some hidden information, there
should be some way to `unhide' it interactively, turninglength v
into
length_n v
thus bringing the n into scope.
Two (not mutually exclusive) ways this might happen:
(1) If you click on any expression or lhs, Horace should display
its fully elaborated form, showing you all the implicit
information, together with its shown/unshown status. It
should then be possible to edit the expression by toggling
the latter.
(2) When Horace shows you a context, it should distinguish
visible variables from hidden ones; you should be able to
request that a hidden variable be made visible; the machine
should then reveal a piece of information which binds the
variable explicitly. Unlike (1), there's a choice to be
made about which occurrence of the variable to show;
perhaps a sensible choice is one which minimizes firstly
the size, then the nesting depth of the revealed info.
e.g. if we're writing(xs : Vec (suc n) X --- vlast_n xs : X)
vlast (vcons x xs)
we might like to look at the length to decide whether x is
last; so we ask Horace to show it; Horace should pickvlast_n (vcons x xs)
not
vlast (vcons_n x xs)
because n is less deeply nested in the former. Another,
perhaps more canonical choice is that we should get all
occurrences, ievlast_n (vcons_n x xs)
simply because this reveals the full role n plays.
My feeling is that (1) is vital, and that (2) would be nice as well.
A further related observation. It's `bad form' to force an implicit argument to a function if you haven't specifically positioned that argument in the function's declaration. Otherwise, there's no good reason why the length arg to vlast should come first---the element type might come first. If you only force specifically positioned implicit arguments, you're protected from changes to the implementation's choice of how to assign positions when they're not given specifically. I am planning such a change (to move implicit args as far left as possible).
Moreover, an implicit argument specifically positioned should be visible by default when the function is being defined interactively. Even without interactive unhiding as suggested above, that would resolve a lot of the nastiness we currently experience when we have functions which have arguments inferrable when the function is being _used_ but which we exploit directly when the function is being _defined_.
Question: we could (at the cost of a little extra book-keeping) police against the above `bad form', distinguishing implicit arguments positioned by the programmer from those positioned by the system and only allowing the former to be forced with _. Would this be sensible, or wasting police time?
Moving on...
BUT I don't understand why you would want to define a function like that, the n is
already in the type of v, hence you know the answer already statically.
Perhaps I have some polymorphic function on containers which requires me to pass in a container and the appropriate length function.
That's a possibility. Not all containers are statically sized; statically sized containers are just the cheap instances of sized containers...
Or perhaps I don't currently grok dependent types enough and this is in fact totally unecessary :)
...but then again, given an unsized container and a size function, I could define the sized container via a propositional constraint:
sized F size n X => (ex x : F X => size x = n)
It's probably easier to write generic operations over statically sized structures than over structures which possess a size function.
What makes writing the length function less than satisfactory is that it discards information rather than computing it. That's to say, if
xs : Vec n X
then
length xs
is just another element of Nat; it's not a priori the length of xs, whereas n is! Fortunately, the choice of computational behaviour
length_n xs => n
means that length xs is just a long way of saying n. However, the same ain't true of the recursive length function. Simon PJ points out that we could make the length function return not just any old Nat, but the singleton type `Only n', re-establishing the connection. This isn't completely daft: why compute values of singleton types when we already know the only inhabitant statically? Because we might prefer to discard it dynamically and recompute it only when we need it, paying some time to reduce space.
Relating to your initial message.
Why not nil : List X ?
What's going on here is Hindley-Milner-style generalization, and the issue with that is always where to generalize: at what point do we scoop up all the unresolved variables and abstract them? HM uses `let' as the trigger for this behaviour in programs. Epigram uses --- in type signatures. So when you say nil : List X, Epigram thinks you're talking about a specific X which you haven't got round to declaring yet. It's only the --- which makes it look for generalization. By the way, if you do write (--- nil : List X), then go back and declare X, Epigram will protect your earlier generalization by inserting a shadow, thus: (X --- nil : List X). Otherwise, the type would suddenly become more specific and programs might break.
Hypotheses declared in one order and used in another: nothing wrong with this in principle, so long as the permutation respects dependency. The only (not necessarily good) reason why Epigram is so rigid about this is my own laziness: it's easier to discharge arguments in exactly the order they occur in the context. However, as I'm thinking of permuting the implicit arguments to produce more sensible behaviour, I might as well allow permutations in the explicit arguments.
Lastly:
* If you define a function type without dummy arguments (i.e. plus: Nat -> Nat -> Nat instead of plus x y : Nat) then I can't work out how to write the program interactively. I tried "lam x <= case x" but that didn't work... (shoudl there be a new 'abstr' strategy for defining by lambda abstraction?)
Er, yes. It's just not implemented yet. That and the `with' rule for abstracting intermediate computations. They're both desperately needed as the workarounds are very clunky. Moreover, we shall have not only
lam ..... <=
for local function definition by elimination, but also
all ..... <= ex ..... <=
for defining dependent function and tuple types which compute their ranges. That's actually the reason why the syntax for binders is currently
bindop sigs => expression
It's upwardly compatible with
bindop sigs rhs
Anyhow, I'll send now, before reading your new message, otherwise I won't get anywhere this morning.
Cheers
Conor
