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, turning

          length 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 pick

          vlast_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, ie

          vlast_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

Reply via email to