8 ms·
Algebraic Subtyping (2016) [pdf]
- Patient0 10y agoI've only read the introduction so far - but already it has taught me something. As a lay-person I am finding it very readable and accessible. I'd always thought that subtyping inference was only something you need for OO style languages. But he begins with two very clear, non-OO, motivating examples and a key insight: failing to support subtyping ignores the data flow of the program.
- vog 10y agoI just had a look at it, and this thesis is really well-written. A beautiful piece of work, with the right mix of concrete examples, abstract concepts, and meta-concepts that describe why and how the author developed their concepts. Can't wait to read more of it.
- Munksgaard 10y agoI've been waiting for this paper ever since I saw Stephens presentation of MLsub [0] at ICFP 2015. I thought the paper had an interesting take on type checking, and it has given me some ideas that I've been wanting to try out for myself. I look forward to reading the dissertation over the weekend. [0]: https://www.cl.cam.ac.uk/~sd601/mlsub/ https://www.cl.cam.ac.uk/~sd601/mlsub/
- vog 10y ago[deleted] Stupid misunderstanding. Sorry, forget what I wrote. I wanted to delete my comment, as it provides no insight and not even an interesting question. But unfortunately the delete button disappeared here in Hacker News.
- deleted 10y ago[deleted]
- Manishearth 10y ago"PhD" stands for "Doctor of Philosophy".
- deleted 10y ago[deleted]
- runeks 10y agoI believe I had the exact same thought as you, in that I was surprised to read "Doctor of Philosophy" on what I assumed was a computer science paper. Now I know better.
- ezyang 10y agoThe lesson of "algebra before syntax" is one that I have seen before, and it is very gratifying to see it pay off such dividends here. There is also discussion on LtU here: http://lambda-the-ultimate.org/node/5393 http://lambda-the-ultimate.org/node/5393
- agumonkey 10y agoHa, seems like ltu is having issues; cached version https://webcache.googleusercontent.com/search?q=cache:http%3A%2F%2Flambda-the-ultimate.org%2Fnode%2F5393 https://webcache.googleusercontent.com/search?q=cache:http%3...
- xyzzy123 10y agoLots of positive comments. Given that I'm an idiot, can anyone summarise why this is interesting? My view is that this extends the work possible with the type system at compile time (e.g. in an integer sense, which would be pretty cool if you scoped it as that) but doesn't extend to "real" numbers or byte manipulation of data. Like do I need this level of structure in my data, and am I being short-sighted by thinking of it as constraining? Perfectly happy to get smashed to heck in exchange for being enlightened :) Thanks! EDIT: sorry in advance for the degree of my ignorance.
- ezyang 10y agoThe thesis is about designing a type system that supports both type inference and subtyping. If you program Java but hate writing explicit type annotations all day, the thesis offers the tantalizing possibility of having a type system that supports all the subtyping you want, but at the same time has as convenient and predictable type inference as ML or Haskell. Conventional wisdom is that this is hard; in this respect, the thesis proves a very surprising result.
- xyzzy123 10y agoThat's not super interesting (to me personally, an acknowledged idiot) because working programmers are hardly ever confused about types. Intellij pretty much already does that thing. I have this idea that this paper does something super interesting that I'm too stupid to understand. Is there a correctness angle I'm totally missing where you can constrain subtypes and ... not sure? EDIT: I watched a thing earlier today where people felt they could reasonably subtype zero away and therefore never think about NAN as in the range or domain of their mathematical functions. I want to learn more. Probably my degree of ignorance is such that I'm unable to ask the right questions. Can you help? This is probably an unfortunately hilarious question.
- ocharles 10y agoThe point is that you don't need to write the types down anymore. The program is still typed, but the compiler can figure out what the type of variables (in a well typed program) needs to be. As said, this has previously been a hard problem. If you're familiar with the `auto` keyword, think of that - but everywhere.
- deleted 10y ago[deleted]
- rjtobin 10y agoAlso by Stephen (and previously discussed on HN): https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf As usual, he injects just the right amount of humour. Eg. this footnote in his thesis: "*This paper is out of print, in Russian, and quite difficult to get a hold of, so the interested reader is directed to a shorter proof by Conway [Con71, p. 105], which is merely out of print."
- myst 10y agoIt's not difficult to get a hold of tho http://umj.imath.kiev.ua/article/?lang=en&article=10002 http://umj.imath.kiev.ua/article/?lang=en&article=10002
- yrhz90 10y agoIt looks like that volume was produced after this thesis was submitted.
- fpoling 10y agoOr this footnote: 1 Eficient in the same sense as ML: tends to run fast, but with some effort pathological cases can be constructed.
- benmos 10y agoI don't think that's really humour - that's an important piece of information.
- xyzzy123 10y agoThanks. Do you have any useful insights such as programming in a relevant language? Shoot from github first if you want to hulk smash demonstrating competence. P.S: let me know if I'm not adequately rating your contributions.
- dang 10y agoIncivility like this will get your account banned on HN, so please don't do it here. We detached this comment from https://news.ycombinator.com/item?id=13782112 https://news.ycombinator.com/item?id=13782112 and marked it off-topic.
- auggierose 10y agoJust read the introduction, and it hits all the right spots in explaining why people (including me) have failed to come up with good subtyping in Hindley-Milner world. I expect people to rush to update their various HM-based systems to this new approach. This seems like a really big thing to me.
- acjohnson55 10y agoFrom just skimming the intro, this seems like very exciting work. And the formulation of the problem in terms of data flow was really novel to me. I was surprised that I couldn't find any references to Martin Odersky in the paper, whose work for years at EPFL has been focused on unifying functional and object oriented programming under a sound type system. This work produced the Scala programming language. More recently, he reworked the foundations of Scala using a system he developed called the calculus of dependent object types (DOT) [1]. I couldn't seem to find any references to this in the thesis. It's hard to imagine the author was unaware of this work, but I'm really interested in hearing more about how the two approaches compare. Anyway, I'm imagining this work could have great applications for things like TypeScript, and maybe even Scala. [1] http://scala-lang.org/blog/2016/02/03/essence-of-scala.html http://scala-lang.org/blog/2016/02/03/essence-of-scala.html
- richard_todd 10y agoExactly, the first thing I searched for was scala, to see how the paper's ideas relate to scala's approach. I was surprised to see no obvious references. One would think it would be high on the list of existing material for anyone researching this area.
- Jweb_Guru 10y agoI'm really enjoying the thesis (it's super awesome!), but it does do a very, very bad job of citing related work. For example, it completely fails to cite logical relations literature despite using a bunch of techniques from it.
- ezyang 10y agoScala's type inference is not complete; it is marketed as a way to "omit certain type annotations". One of the reasons why Hindley-Milner is so influential is because you really don't need any type annotations: the inference algorithm always works. As for DOT https://www.cs.purdue.edu/homes/rompf/papers/amin-wf16.pdf https://www.cs.purdue.edu/homes/rompf/papers/amin-wf16.pdf DOT is an explicitly typed calculus (similar to System F), for which no attempts at type inference are made. So... they're not really comparable at all.
- fpoling 10y agoAnd now I know why record-like types are so awkward in many functional languages. A classical type inference just cannot type them requiring heavy type annotations.
- Ericson2314 10y ago> Disjoint union is the coproduct in the category of sets, so we have a good excuse to use the symbol + This is definitely making fun of somebody
- infinity0 10y ago"The primary tool by which this was achieved was not advanced or complicated algorithms, but attention to the minutiae of basic definitions."