Why dependent type theory?

It seems to me that if you are working with structures, i.e. do structural Mathematics you need to understand what they are and they cannot be reduced to their encodings. Hence what is the equality of structures, if not their structural
equality? If I remember correctly, in your talk at Nottingham you discussed a construction by Grothendieck where he used equivalence of structures as if it were equality. This seems to be an omission and you and your students were able to address this, I think
by choosing a canonical representation. However, the funny thing was that you were using a system which doesn’t allow you to express any non-structural properties but because of the way equality is done in Lean you cannot exploit this.

There is something subtle going on which I do not really understand, but it would not surprise me if there are plenty of people on these lists who do. Our problem with formalising the work of Grothendieck was that he assumed that objects which were “canonically” isomorphic were in fact equal. Canonical isomorphism is this weasel word which mathematicians often do not define properly, but in this particular case (we had a proof of P(A) and I could not deduce a proof of P(B) when B was “canonically” isomorphic to A) we solved the problem by noticing that in this particular case “canonically isomorphic” meant “satisfied the same universal property”. We then changed our proof of P(A) to prove instead P(anything satisfying the universal property defining A), and then we were OK. I think it is interesting that at the point in my talk when I explained this, I said “and we couldn’t believe it – our proof barely needed changing” and you laughed and said something like “of course it didn’t!”. We are mathematicians learning how mathematics works :slight_smile: But we did not go “full univalence”, we did not argue that isomorphic objects were equal, we only needed that “canonically” isomorphic objects were equal. In my experience of mathematics, this is the principle which is used. My fear of univalence is that because it goes a bit further, and that extra step seems to rule out some basic principles used in Lean’s maths library and hence makes a whole bunch of mathematical proofs far more inconvenient to write. I am still learning about theorem provers but am urging my community to start formalising mathematics and this sort of thing is one of many issues which deserves to be better understood – certainly by mathematicians!

I don’t know what Mathematics is actually happening in Maths departments but you seem to agree that it can be done in Type Theory, e.g. in Lean. Indeed, in a way Type Theory is not far away from Mathematical practice (if we ignore the question
of constructiveness for the moment). And it is different from set theory in that it structural by nature. I just find it strange if one cannot go the last step and exploit this fact. It seems somehow this is a blast from the past: because we cannot have univalence
in set theory we don’t need it in type theory either?

I just do not know whether we need it in “Fields Medal mathematics” or whatever you want to call it, because so little “Fields Medal mathematics” is being done in theorem provers. I have this other life when I am going round maths departments arguing that current mathematical practice is extremely unhygenic, producing example after example where I think that pen and paper mathematics has got completely out of control. One thing I have learnt from a couple of years of doing this is that most mathematicians are (a) completely aware of the issues and (b) don’t care. A mathematical historian told me that in fact mathematics has often been like this, basically saying that it is the nature of progress in mathematics research.

Ok, this is a different topic (and I didn’t say anything about constructive Maths in my original posting). I think the sort of Maths you are doing is very much influenced by what you are using it or what it has been used for in the past.
It seems to me that until recently natural science and hardware engineering was the main application of Mathematics and hence influenced what Mathematicians considered as important. The world is changing and computer science and information technology are
becoming an important application of Mathematics. For historical reasons and also for reasons of funding a lot of the Maths for Computer Science is actually done at Computer Science departments. I am just thinking that you, the Mathematicians, maybe miss a
trick here; and so do we, the Computer Scientists because we could profit more from the wisdom of Mathematicians like yourself.

Mathematics is an incredibly broad discipline nowadays, as you say, and serious mathematics is being done in plenty of places other than mathematics departments. The group of people I am trying to “represent”, not necessarily by being one of them, but at least by having what I think is a good understanding of their desires, are those people who do not care about any of these applications, and just want to prove stuff like the p-adic Langlands conjectures, abstract conjectures saying that some class of infinite-dimensional objects coming from analysis are related to actions of an infinite group on some spaces coming from algebra – results which I personally suspect will never have any applications to anything, but which are just intrinsically beautiful and are hence funded because part of the funding system in mathematics firmly believes in blue sky research. The people I’m talking about are beautifully caricatured in “The Ideal Mathematician” https://personalpages.manchester.ac.uk/staff/hung.bui/ideal.pdf by David and Hersh (in fact I slightly struggle to see what is so funny about that article because I so completely understand the point of view of the mathematician). In fact the only difference between some of the mathematicians I know doing “Fields Medal mathematics” and the “ideal mathematician” described in that article is that the areas the “Fields Medal mathematicians” actually work in areas which are taken much more seriously (like the p-adic Langlands philosophy), with very big communities containing powerful people who are making big decisions about where the funding is going within pure mathematics. These people might seem very extreme to many of the people reading these mailing lists – most do not care about computation or constructivism, they spend their lives doing classical reasoning about intrinisically infinite objects, and they do not see the point of these proof assistants at all (and they also do not care about bugs in computer code because the only point of the computer is to check a gazillion examples to convince us that our deep conjectures are true, and we know they’re true anyway). The reason that the computer proof community should be bending over backwards to accommodate these people is that these people are the important ones within pure mathematics, and many of them have very entrenched ideas about what is and isn’t mathematics, and what is and what isn’t important. Thorsten makes some excellent points about all the other places where mathematics is being used but it’s the people at the top of this particular tree who I want. It is these people who should be telling us what kind of type theory should be being used, at least for the system or systems that I believe they will ultimately adopt. But until they notice that the systems exist it is very difficult to get clear answers – or indeed any answers.

As I said to me it seems that too much surface stuff is moved into the core of systems like Lean.

What Lean has going for it is that in practice it is turning out to be very easy to quickly formalise the kind of mathematics which these “top of the tree” pure mathematicians care about. However this might be because of some social phenomena rather than because of its underlying type theory.

Kevin

1 Like

I’d be interested to see a “canonical isomorphism” that isnt reducible to some form of “satisfies the same universal property”. Do you have examples?

For reference, we (Kevin and the hott community) had a discussion
about canonical isomorphisms here:
https://groups.google.com/d/msg/homotopytypetheory/NhIhMd7SM_4/tKvejHGiAwAJ

It seems to me that if you are working with structures, i.e. do structural Mathematics you need to understand what they are and they cannot be reduced to their encodings. Hence what is the equality of structures, if not their structural equality? If I remember correctly, in your talk at Nottingham you discussed a construction by Grothendieck where he used equivalence of structures as if it were equality. This seems to be an omission and you and your students were able to address this, I think by choosing a canonical representation. However, the funny thing was that you were using a system which doesn’t allow you to express any non-structural properties but because of the way equality is done in Lean you cannot exploit this.

There is something subtle going on which I do not really understand, but it would not surprise me if there are plenty of people on these lists who do. Our problem with formalising the work of Grothendieck was that he assumed that objects which were "canonically" isomorphic were in fact equal. Canonical isomorphism is this weasel word which mathematicians often do not define properly, but in this particular case (we had a proof of P(A) and I could not deduce a proof of P(B) when B was "canonically" isomorphic to A) we solved the problem by noticing that in this particular case "canonically isomorphic" meant "satisfied the same universal property". We then changed our proof of P(A) to prove instead P(anything satisfying the universal property defining A), and then we were OK. I think it is interesting that at the point in my talk when I explained this, I said "and we couldn't believe it -- our proof barely needed changing" and you laughed and said something like "of course it didn't!". We are mathematicians learning how mathematics works :slight_smile: But we did not go "full univalence", we did not argue that isomorphic objects were equal, we only needed that "canonically" isomorphic objects were equal. In my experience of mathematics, this is the principle which is used. My fear of univalence is that because it goes a bit further, and that extra step seems to rule out some basic principles used in Lean's maths library and hence makes a whole bunch of mathematical proofs far more inconvenient to write. I am still learning about theorem provers but am urging my community to start formalising mathematics and this sort of thing is one of many issues which deserves to be better understood -- certainly by mathematicians!

I am wondering whether this idea of “canonical isomorphism” is just a bit of a stop gap which comes from set-theoretic thinking. I was laughing because anything you can do in type theory is stable under structural isomorphism. Hence certainly proofs can be transported along structural isomorphism. I just wonder if you have two mathematical objects which have all the same properties, then what would you call them if not equal?

But more practically: indeed you are right if you accept this point (i.e. univalence) then you have to give up some properties of equality in particular that it is propositional, i..e a property. This can be annoying because it may mean that you have to deal with coherence issues when using equality, but I suspect you should be used to this. However, as long as you only deal with simple objects, i.e. as in the “world of numbers” everything is fine and nothing changes. It is only when you leave the realm of “set level Mathematics” and talk about structures (as in the Grothendieck example) you encounter equalities which are not propositions (but structures themselves).

However, here comes a technical issue, which I think is overrated. Namely, Lean uses strict equality (I think I introduced this in a paper in ’99 to deal with extensionality) which means any two proofs of a proposition, e.g. a set level equality are “definitionally equal”, i.e. the type system knows this. Now the problem is that being a proposition in HoTT is a proposition itself while for a strict Prop you need it to be a judgement, i.e. static. However, both concepts can coexist in the same system: you can have strict and weak Prop. The weak Prop gives you a subobject classifier but the strict Prop is more convenient to use and only gives you a quasi-topos, I think.

So I think you can have your cake and eat it.

Thorsten

P.S. I agree with all the rest and appreciate that you want to reach the top of the tree Mathematicans.

This message and any attachment are intended solely for the addressee
and may contain confidential information. If you have received this
message in error, please contact the sender and delete the email and
attachment.

Any views or opinions expressed by the author of this email do not
necessarily reflect the views of the University of Nottingham. Email
communications with the University of Nottingham may be monitored
where permitted by law.

I’m in the process of writing my thesis on proof assistant performance bottlenecks (with a focus on Coq). I’m having some trouble finding prior work on performance engineering and/or benchmarking of proof assistants (other than the paper on the Lean tactic language (https://leanprover.github.io/papers/tactic.pdf)), and figured I’d reach out to these lists.

Does anyone have references for prior work on performance analysis or engineering of proof assistants or dependently typed languages? (Failing that, I’d also be interested in papers about compile-time performance of compilers.)

Thanks,
Jason

1 Like

Hi Jason,

You may be interested in my github repos: smalltt, normalization-bench. I haven’t yet updated the smalltt repo, but there’s a simplified implementation of its evaluator, which seems to have roughly the same performance but which is much simpler to implement.

The basic idea is that in elaboration there are two primary computational tasks, one is conversion checking and the other is generating solutions for metavariables. Clearly, we should use NbE/environment machines for evaluation, and implement conversion checking in the semantic domain. However, when we want to generate meta solutions, we need to compute syntactic terms, and vanilla NbE domain only supports quote/readback to normal forms. Normal forms are way too big and terrible for this purpose. Hence, we extend vanilla NbE domain with lazy non-deterministic choice between two or more evaluation strategies. In the simplest case, the point of divergence is whether we unfold some class of definitions or not. Then, the conversion checking algorithm can choose to take the full-unfolding branch, and the quoting operation can choose to take the non-unfolding branch. At the same time, we have a great deal of shared computation between the two branches; we avoid recomputing many things if we choose to look at both branches.

I believe that a feature like this is absolutely necessary for robust performance. Otherwise, we choke on bad asymptotics, which is surprisingly common in dependent settings. In Agda and Coq, even something as trivial as elaborating a length-indexed vector expression has quadratic complexity in the length of the vector.

It is also extremely important to stick to the spirit of Coquand’s semantic checking algorithm as much as possible. In summary: core syntax should support no expensive computation: no substitution, shifting, renaming, or other ad-hoc term massaging. Core syntax should be viewed as immutable machine code, which supports evaluation into various semantic domains, from which sometimes we can read syntax back; this also leaves it open to swap out the representation of core syntax to efficient alternatives such as bytecode or machine code.

Only after we get the above two basic points right, can we start to think about more specific and esoteric optimizations. I am skeptical of proposed solutions which do not include these. Hash consing has been brought up many times, but it is very unsatisfying compared to non-deterministic NbE, because of its large constant costs, implementation complexity, and the failure to handle sharing loss from beta-redexes in any meaningful way (which is the most important source of sharing loss!). I am also skeptical of exotic evaluators such as interaction nets and optimal beta reducers; there is a good reason that all modern functional languages run on environment machines instead of interaction nets.

If we want to support type classes, then tabled instance resolution is also a must, otherwise we are again smothered by bad asymptotics even in modestly complex class hierarchies. This can be viewed as a specific instance of hash-consing (or rather “memoization”), so while I think ubiquitous hash-consing is bad, some focused usage can do good.

Injectivity analysis is another thing which I believe has large potential impact. By this I mean checking whether functions are injective up to definitional equality, which is decidable, and can be used to more precisely optimize unfolding in conversion checking.

I’d be very interested in your findings about proof assistant performance. This has been a topic that I’ve been working on on-and-off for several years. I’ve recently started to implement a system which I intend to be eventually “production strength” and also as fast as possible, and naturally I want to incorporate existing performance know-how.

Jason Gross <jasongross9@gmail.com> ezt írta (időpont: 2020. máj. 8., P, 0:20):

1 Like

In the case of Isabelle, performance analysis has always been part of the development process and we keep an eagle eye on the runtimes in our nightly builds. Much of this is routine software engineering rather than research. But then there’s all of Makarius’s work on multithreading...

Larry Paulson

You may be interested in my github repos: smalltt
<https://github.com/AndrasKovacs/smalltt&gt;, normalization-bench
<https://github.com/AndrasKovacs/normalization-bench&gt;\. I haven't yet
updated the smalltt repo, but there's a simplified implementation
<https://gist.github.com/AndrasKovacs/a0e0938113b193d6b9c1c0620d853784&gt; of
its evaluator, which seems to have roughly the same performance but which
is much simpler to implement.

Very interesting, thank you.

It is also extremely important to stick to the spirit of Coquand's semantic
checking algorithm as much as possible. In summary: core syntax should
support *no* expensive computation: no substitution, shifting, renaming, or
other ad-hoc term massaging. Core syntax should be viewed as immutable
machine code, which supports evaluation into various semantic domains, from
which sometimes we can read syntax back; this also leaves it open to swap
out the representation of core syntax to efficient alternatives such as
bytecode or machine code.

[ Hmm... I kind of vaguely understand what that entails, but can't quite
  see how that would work in practice. I guess I'll have to dig deeper
  into your above Git repositories. ]

Only after we get the above two basic points right, can we start to think
about more specific and esoteric optimizations. I am skeptical of proposed
solutions which do not include these. Hash consing has been brought up many
times, but it is very unsatisfying compared to non-deterministic NbE,
because of its large constant costs, implementation complexity, and the
failure to handle sharing loss from beta-redexes in any meaningful way
(which is the most important source of sharing loss!).

Could you elaborate on this "sharing loss from beta-redexes"?

        Stefan

Could you elaborate on this “sharing loss from beta-redexes”?

We may have a huge Peano numeral which is represented by a small term, because we can use iteration/recursion to give short descriptions of large numerals. Then, we can beta-reduce from a small term to a large numeral, but we cannot go from a large numeral to a small term. In particular, Peano numerals are incompressible by hash consing. Hash consing only does “delta-contraction”, i.e. contracting terms by maximally introducing let-definitions, but it is intractable to invent small terms which beta reduce to a given term (related: Kolmogorov complexity).

Stefan Monnier <monnier@iro.umontreal.ca> ezt írta (időpont: 2020. máj. 12., K, 16:30):

So technically, the lost sharing is the second-order sharing that is preserved
in ``optimal reduction'' of lambda calculi [Levy-1980, Lamping-1990, Asperti-Laneve-1992],
while hash consing normally is directly usable only for first-order sharing.

Wolfram

Thanks! This is very interesting. (And thanks all for sources.)

I’m still digesting this, but have one question already:

Clearly, we should use NbE/environment machines for evaluation, and implement conversion checking in the semantic domain.

Does this mean that we can’t be agnostic about whether or not we’re supporting HoTT, because we either have to pick set theory/irrelevant equality proofs or cubical (or some other model of HoTT) when normalizing proofs of equality?

I’d be very interested in your findings about proof assistant performance.

I’d be happy to share once I have my thesis in a sufficiently ready state! Broadly, the message of my thesis is that performance of (dependently-typed) proof assistants / interactive theorem provers is an interesting area of research sorely in need of systematic study. (My thesis will also include some of the research work I’ve done, which can be rendered as “how to work around some of the asymptotics in Coq without needing to change the system”, but I think that’s a bit less broadly interesting.)

-Jason

1 Like

As Larry said, there has been a lot of work on this over the years. A few references off the top of my head (slightly HOL-centric)

https://link.springer.com/chapter/10.1007/3-540-44659-1_2

https://www.researchgate.net/publication/2390013_Efficiency_in_a_Fully-Expansive_Theorem_Prover

Related to this is work on sound interfaces to external tools, also an enduring topic:

https://www.cs.utexas.edu/~kaufmann/itp-trusted-extensions-aug-2010/summary/summary.pdf