← CoRecursive: Coding Stories
CoRecursive: Coding Stories
Tech Talk: Generic Programming with Miles Sabin
01:00:38
Tech Talks are in-depth technical discussions. When Miles Sabin applied to speak at a conference on generic programming, he bluffed a little bit. He would present on porting Simon Peytons Jone's scrap your boilerplate functionality to Scala. Once his ...
Loading summary
Transcript52 lines
- [00:01]
Miles Sabin
I basically submitted a talk proposal for FP Exchange. So I put in a talk proposal which was how we need a scrape in Scala with the idea of forcing myself to actually sit down and work out how to make this thing work. Otherwise I was going to be extremely embarrassed, not least because the keynote speaker, so someone who was actually going to be in the audience, was going to be Simon Peyton Jones. So I was going to have to come up with something at least moderately, moderately convincing to be able to get that past him.
- [00:32]
Interviewer
When Miles Sabin applied to speak at a conference on generic programming, he bluffed a little bit. He would present on porting Simon Peyton Jones's scrap your boilerplate functionality to Scala. Once his talk was accepted, he only had one thing left to implement the solution. Generic programming is the type of polymorphism your language does not directly support. To me, this definition seems paradoxical, as once you implement a solution, the language, or at least a library within the language, can now support it. This recursive definition and a speaking deadline led Miles to create Shapeless. Years later, he's still pushing the bounds on what you can do in Scala, including recently getting support for literal types added to the Scala C compiler. So Miles, in some point around 2014, I was writing some Scala and I had to write a function that grouped a tuple. So I had like a tuple with two values and I needed to kind of turn it into a. Sorry, I had a list of tuples and I needed to kind of group it by the first element into a map. And so I wrote that out and then a week later I have to write something that takes like a three element tuple and does the same thing, takes the first element and kind of groups the second elements into a map based on that value. And then I had the thought at that time, like I should be able to write something generic over this. And it's at this point that I learned about generic programming and shapeless. I don't think I ever got the generic version done, but it did take me on a path to learn about shapeless and generic programming. So what is generic programming?
- [02:21]
Miles Sabin
That's a big question. So for quite a few years now there has been a satellite workshop of icfp, the International Conference on Functional Programming, which is kind of the main sort of academic stroke industry sort of functional programming conference annually. And this, this workshop title has been the Workshop on Generic Programming wgp. And I guess I've been going to that sort of at least as regularly as I've been going to icfp. And a few years Ago, the workshop chair sort of had a sort of a kickoff session and I was always trying to sort of bat around ideas. I think a few years ago, generic programming was perhaps less visible outside academia than maybe it is now. And one of the things he wants to do was, you know, what's the sort of the elevator pitch for generic programming that we could sort of use to make it sort of more accessible, more visible to people kind of outside the academic community that was mainly involved with it at the time. And there were lots of various different kinds of ideas. But the sort of the catchy one liner that the group in the workshop came up with at the end was something along the lines of generic programming is kinds of polymorphism that your programming language doesn't support yet. Which I think, which I think is kind of nice. It really is about ways of abstracting which are perhaps richer than we're used to in the context of standard parametric polymorphism or subtype polymorphism in language like Scala, which has both. It's an idea of being able to abstract over shapes of data more generally than you typically find it easily expressed or represented. There are, there are lots of sort of gray fuzzy areas. Where does the kind of polymorphism that people typically tend to talk about in terms of generic programming, where does it begin, where does it end? What are the kinds of things that are included and what aren't? And it really isn't particularly clear, I think, as sort of type systems that people are get used to working with become richer and richer and more expressive. I think in some respects generic programming is a sort of separate, independent kind of discipline is likely to sort of disappear, be submerged into the general sort of discipline of programming the types. But at the moment, I think the way you would tend to characterize it as it's having a. It's programming which depends on having a representation of the shape of data in some very general sense of what the shape of a data type values of a data type might be. Being able to abstract over those shapes in ways that allow you to perform a variety of interesting operations on data independently of the particular shapes that it comes packaged into.
- [06:06]
Interviewer
A two tuple and a three tuple. They actually have no commonalities from the, from the perspective of the language. But actually there's a very clear relationship where it seems like I should be able to get the first element and then get the rest and group the rest by the first, but you can't do that in the language. So generic programming is a way of. Does that make sense?
- [06:32]
Miles Sabin
Pretty much I think you're definitely right to observe that there is a commonality between those types which is at least not directly captured in the language per se. There is actually a trivial and very, very uninteresting and unhelpful common type. Both of those types, tuple 2 and tuple 3 in Scala, share a common type called product, which is. And serializable as well, both of which are extremely unhelpful in this kind of context. It's not quite true to say that the commonality can't be expressed directly in Scala. The commonality most definitely can. What might be more awkward in this case, it's not particularly awkward, but in more complex cases it might be more awkward, is actually working out how to find what that common type is without having to write a certain amount of boilerplate code, for example. So in the case of tuple 2 and tuple 3, the thing they have in common is that they are. I mean, this is in a sort of slightly mocking way captured by the Scala product trait. What they have in common is they are both product types. You can think of them as being. In the case of tuple 2, it's product of two times A and B. In the case of tuple 3, it's a product of three types, A, B and C. And here I mean product in the same way that you might think of a product in terms of sort of a vector space. So the difference is, if you like the dimensionality of the space that you're talking about, but ultimately these things are represented by a product of the different dimensions, different types that are involved here. So if you can come up with some way of representing generally a product of types, then you've got. And then also work out some mechanism for generally computing over types which represent products of types, then you're pretty far along with being able to work in an abstracted way over tuples.
- [09:13]
Interviewer
This is a product type, like in terms of a algebraic data type, as opposed to a sum type.
- [09:21]
Miles Sabin
It's a product type in the sense. Well, a sum type represents A is a CO product. It's something which represents a choice between different possibilities. A product is something which represents several things. So if we have a product of A, B and C, then if you have an instance of that type, you have all three of an A, A, B and a C. In the case of a sum type, you can have a sum of A or B or C. And in that case, actually I prefer to use co product. In this context, we can come back to what the difference between CO products And sums is later. But if you have a co product of those three types, you have exactly one of A, B or C. So there is a difference here in terms of what you get here, what the elements that the type is composed of are.
- [10:23]
Interviewer
There's a relationship here, I guess, between generic programming and dependent types, it seems to me. I'm not quite clear on. Seems like you're pushing the language towards having first class types. What are your thoughts?
- [10:38]
Miles Sabin
I suppose so. I'm certainly enormously enthusiastic about dependent types. I think they are a. I think being able to bring dependent types into languages that people can use in their day jobs as opposed to. Well, there are some people who can already use languages like in their day jobs, but they are a minority of us. I think making dependent types more widely accessible I think would be a wonderful thing. I saw that you had Edwin Brady talking about Idris on an earlier edition of this podcast. I have enormous respect for the work that Edwin's been doing. I think it's fantastic stuff and I think I draw a huge amount of inspiration from what he's doing. I think, to be honest, much as I would love to see it, I don't really see there as being any particularly natural evolution of Scala in the direction of a sort of Idris, like full spectrum dependently typed programming language. I think there are too many, there's too much historical baggage, I think, to make that work particularly well. In truth, I also think the same is true of Haskell. I think there's lots of work being done on dependent Haskell. I. I will be very interested to see how that plays out over the next few years, but I kind of think that the cleaner slate approach that IDRIS has taken is likely to lead to a more comfortable, better ergonomics, I guess in general for the language. But I think all of these things are pointing in the same direction. I think at least in the part of the software world where types matter to us, I think it's pretty clear that the direction of travel is in the direction of dependent types. And I think that as much as we can do to kind of move things along in our own corners of the ecosystem, I think the better. So to what extent? So I don't want to overcloud. I think I've definitely shown a lot of interesting ways that people can use Scala's forms of dependent types in fairly explicit ways, some of which I think were perhaps not expected and slightly unanticipated. But it's important to remember that dependent types have been a part of Scala since the very beginning. I mean, so the very, very earliest descriptions of Scala and semantics make absolutely essential use of at least a form of dependent typing. You know, path dependent types are something which has been part of the Scala language specification since 2004 and they really are dependent types. There's a little bit of controversy about how broadly the term dependent type should be used as far as programming language is concerned. But Conor McBride is I guess, one of the most visible people when it comes to talking about and promoting dependent types, perhaps more in academic context than amongst working programmers. But nevertheless, I think he takes a fairly liberal view, which is that there are an awful lot of programming languages which can be viewed quite reasonably as having aspects of dependent typing. Certainly in conversation with him, he's quite comfortable to say that Scala is one of those languages. Haskell is as well, even prior to things like dependent Haskell just gadts on their own get you some aspects of dependent typing. So we are slowly getting there. I mean, it's one of, I mean it's actually kind of interesting that in some respects that, you know, although, you know, shapeless, the techniques around shapeless, sort of, they are pointing in the direction of dependently typed programming. Actually, to some extent, the ways that they use Scala's intrinsic dependent types is almost accidental actually in many ways the sort of the techniques that shapeboose uses are actually closer to some of the techniques in Haskell that you might use for simulating dependent types without really having first class dependent types. Even though Scala does actually have a form of first class dependent typing, which I think is kind of amusing.
- [15:48]
Interviewer
I saw. So Edwin wants to use this term. Ellison and Idris like first class types. And I saw a Stack Overflow post where somebody was asking. He has a very simple example of a function that takes a Boolean argument and then based on whether it's true or false, it returns a different type. Like it returns either string or int. And you know, it's like three lines of interest. But I saw you answer and you showed how to do it in Scala and you were able to accomplish the goal. But I think it highlighted the fact that like having functions over with the return types is not like a first class construct in Scala. Like it.
- [16:30]
Miles Sabin
No, that's. Yeah, that's absolutely right. I think pretty much everything that you can find in Edwin's book can be translated to Scala, but the translation in many, many cases is just going to be hopelessly unwieldy. It's going to be very, very, very difficult to work with. So it's actually interesting because sometimes you hear an objection to adding supposedly advanced programming language features to a language which wants to claim that it's mainstream on the grounds that adding these fancy programming language features it, it adds this weight, this burden of complexity. I actually think that's almost completely.
- [17:25]
Interviewer
Looking.
- [17:26]
Miles Sabin
At things almost completely the wrong way around. Typically people are faced with solving pre existing problems which have a degree of complexity of some sort of intrinsic complexity and the nature of the problem themselves. They are going to have to somehow or other encode that complexity in their programming solution. If there is a natural way of expressing something, then the resulting program is at least with respect to the the problem domain, simpler. If you force people to kind of model things by complicated encodings or indirect ways of representing indirect ways of representing their problem domain, then you end up with maybe a solution which uses very simple programming language contracts. But the actual overall solution is extremely complex. There's inevitably there's a kind of law of conservation of complexity, I suppose in a sense in as much as you squeeze it out in one place, it pops up in another. So, okay, you remove your sophisticated forms of abstraction and polymorphism from a programming language and you end up with enormous gobs of boilerplate and you can go in the opposite direction and you can eliminate boilerplate. But to be able to do that as effectively as possible, you'll typically end up having to add non trivial programming language features of some sort or another. And I think reasonable people can disagree about where along those scales it makes sense to set the dial. My gut feeling is that as we become more accustomed to using type systems to work for us, then it will become more and more natural to set the dial a bit further in the direction of adding expressive power to our language of types and going in that direction.
- [19:46]
Interviewer
And also the complexity at the language level. You learn that once and you can apply it anywhere. The language used, the complexity boiled into an ad hoc implementation in your application. It's not as reusable.
- [20:01]
Miles Sabin
The thing I guess I'm quite happy to use an example now is take a look at the implementation of the lazy macro in Shapeless and then compare it with the implementation of bio name implicits in the scala compiler in 2.13, at least in the pull request. I think whatever you might think about the internals of the Scala compiler, which I think has been unjustly maligned.
- [20:29]
Interviewer
In.
- [20:29]
Miles Sabin
Fairly unhelpful ways over the years, it's not a bad code base and it can be really quite pleasant to work with. Notwithstanding the fact that the internals of this Scala compiler are perhaps not completely straightforward. I think the implementation of binomial implicit arguments is orders of magnitude easier to understand in the Scala compiler than it is in the shapeless macro. And I think if people are concerned about complexity and fragility, then they should be even more concerned about one off ad hoc implementations of stuff which, which aren't relied on by multiple parties.
- [21:19]
Interviewer
That seems to me there's a sense in which, you know, like doing the go back to my dependent type example, like doing that bool or int type in Scala compared to Idris is sort of like doing functional programming in like an early version of Java, you know, compared to Scala, like there's some sort of equivalence right, where you're encoding. You have to understand what this looks like in a theoretical language that supports it and back translate it into the constructs that are available.
- [21:51]
Miles Sabin
Yeah, I think that's right. Sorry. I was going to say, for what it's worth, I think that if people want to program in this style, you would absolutely be doing the right thing if you spent some time, even if it's just, you know, hobby time, tinkering time playing around with Idris or one of the other dependently type programming languages just to get a feel for what's possible. I think one of the things that's an enormous enabler is just seeing just what can be done. I think until it's clear that.
- [22:31]
Interviewer
Just.
- [22:31]
Miles Sabin
How broad the possibilities are, I think people don't even begin to think of solving problems in those kinds of ways. And I think that can be enormously helpful.
- [22:42]
Interviewer
So one thing you mentioned earlier was sum versus co product. You want to briefly touch on that?
- [22:51]
Miles Sabin
Oh, right, okay. Yeah, so. So the difference between a sum type and a co product type is that a sum type doesn't represent either order or duplication. So for example, it doesn't make any sense to have a sum of a and a and a. The sum of A and a and A is just a, whereas the co product of A and a and A is quite distinct from just a and one way you can think about these things. I mean, to be honest, I think I've learned a lot in the process of working through the various iterations of Shaplist. One of the things I realized that was a complete mistake was to actually have first class H list and co product types. There's really no particular reason why they would be needed in preference to say, having representing H lists, well, representing product types as nested pairs terminated by unit or something. And in the case of CO products, there's nested eithers terminated by some terminal type. Nothing maybe. But if you compare, for example, an either type, think about a nested either. There is quite clearly a difference between either of A and either of a or nothing and plan A. Okay, so they're different types. Does it matter? The answer is it kind of does matter. Because one of the things that sort of the fact that these things are called coproducts, the CO prefix should be a little bit of a clue. Coproducts and products are essentially dual to one another. It's the usual flip all the arrows and you preserve truths. So one of the things that drops out of working with a CO product type like the one in Shapelist is that. Is that pretty much everything you can do with an H list or, sorry, a product type can also be done in exactly the same way for a CO product. So for example, there's a huge set of type classes and shaplist for manipulating H lists, doing things like concatenating them, transposing them, finding elements in them. All those kinds of things, all of those operations translate directly to CO products. And they translate directly because the structure of a CO product type and the structure of a product type are to all intents and purposes identical. And that's something that you don't get with the sum type, because the sum type has this different structure. It has a structure which doesn't reflect order or repetition.
- [26:14]
Interviewer
I guess I'm missing how they're. Sorry, I'm missing how they're identical. Could you. Are there structures?
- [26:24]
Miles Sabin
Well, they have the same inductive structure in terms of a head and a tail, I guess is the main thing. They. They both have a particular kind of monoidal structure which, which essentially means that you can. I'm trying to think of a good example of a. Of something which is. Let me think. Well, okay, so there's something that you might. I think the thing to do would be to look at any of the OPS type classes in Shapeless. So they're defined for age lists and CO products separately. So, for example, you want to compute the type level length of an H list, for example. So there is a type class that will compute the type level length of an hlist. There is also a type class which will compute the type level length of a CO product, although they are not currently in Shapeless, the same code. If you look at the structure of the type classes in the instances instances.
- [27:53]
Interviewer
Which.
- [27:55]
Miles Sabin
Are provided for them, they are essentially identical. Modulo the fact that one is parameterized in terms of H lists and the other is parameterized in terms of co product. There is a single underlying abstraction which would allow both of those, which would allow those two type classes to essentially become one. And I think that's. That. I think that is potentially very powerful additional abstraction. That's something I've done a little bit of.
- [28:30]
Interviewer
So does it, does it make sense to think of it in terms of and. And. Or like one is a certain structure?
- [28:39]
Miles Sabin
Yes, exactly. Absolutely. Exactly that. Exactly that, yes. And this, a lot of this stuff comes from a. A paper called Data types titled Data types a la carte from the General Functional Programming a few years back. It's well worth reading. And that's in many ways a lot of the. It's sort of been foundational for quite a lot of the most interesting work on generic programming.
- [29:10]
Interviewer
I think I saw somewhere that you had based some of your earlier work on the scrap your boilerplate paper. I don't know if that's true or.
- [29:19]
Miles Sabin
That's absolutely true. Yes. So there's a number of different strands in the literature which I guess have been circling around themselves in various different ways. I guess where Shapler started right at the very outset was as a sort of challenge, I set myself to see if I could translate the variant of scrap your boilerplate that is described in the paper scrap your boilerplate with class. That's Simon Paton Jones. And the reason I started out with scrap your boilerplate is because for a start, it's a mechanism which is. So the general idea behind scrapier polar blade is to be able to perform general traversals over arbitrary data types and general transformations on arbitrary data types. And the mechanism that was being described particularly in that paper was one based on type classes. And it had some particularly interesting twists in it when it was first presented at ICFP in 2005. I think the way that it was being described sounded as though it might actually be particularly amenable to translation to Scala. Because one of the issues that I can remember SPJ saying that he had trying to put together this model was the fact that in Haskell there is no first class representation of type classes. Type classes are different from types and type class instances aren't first class values in the way in which seemed intuitively that they seem to be required for taking the approach that he was taking in this paper. And one of the innovations that, that he and the co authors came up in this paper was working out a mechanism for coming up with something that's to all intents and purposes equivalent to Having a first class representation of type classes and instances. And I thought, oh, that's interesting. I mean, we kind of have that for free in Scala via type classes represented as types with implicit values as instances. It seems like we have that kind of for free. Maybe it would be interesting to see how straightforward it would be to translate that approach, to translate that approach to Scala directly. And it turned out, I won't say, I mean, in retrospect, it's actually a fairly simple translate translation from the one to the other. At the time it was enormously difficult. I mean, it took a very, very long time, I think, to see exactly how to make that work. I think people's sort of general ability to kind of map Scala concepts onto Haskell concepts and vice versa has improved dramatically. I know for sure that mine has at any rate has improved dramatically over the years. I think people are much quicker to spot how idioms that you find in the one language can be translated over to the. The facilities available on the other. I think much more swiftly than used to be the case. Yeah, so that's kind of the origins, I suppose, of the origins of Shapeless.
- [33:18]
Interviewer
So did you sit down, did you have a goal in mind or was this a fun project?
- [33:25]
Miles Sabin
It was kind of partly a fun project, but I'd also set myself, I mean, the way I set myself up for this was I basically submitted a talk proposal for, I'm trying to remember which conference. So it was a small conference put on by Skills Matter in London, I think it was. They ran a number of conferences which they add exchange to as a suffix. So there was the Scala exchange. They also had an FP exchange, a functional programming exchange, and there's a Haskell exchange. I think this is one of the first FP exchange workshops that they had. So I put in a talk proposal which was how will you implement scrap your boilerplate in Scala? And then with the idea of forcing myself to actually sit down and work out how to make this thing work, otherwise I was going to be extremely embarrassed, not least because the keynote speaker, so someone who was actually going to be in the audience was going to be Simon Paton Jones. So I was going to have to come up with something at least moderately convincing to be able to get that past him. Yeah, so, I mean, I very deliberately sat down to see if I could actually work out how to do this thing and spent this, a fair chunk of time doing it. I have to say that although at the time I convinced myself that the first iteration was doing the right thing, in fact, in retrospect, I realized there was a whole slew of things that I completely missed and misunderstood. And it took me, I guess, probably another couple of years worth of experience trying to use Shapeless to do interesting things before I fully, fully got to grips with what the various missing pieces of the picture were. I think one of the most important missing pieces of the picture was the fact that I hadn't fully appreciated the extent to which recursion in data types was actually going to be an issue. I think some of the first things that people look at with generated programming is things a little bit like the examples that you were describing at the beginning, where you were talking about whether you want to abstract over things of different arity, things tuples of different sizes and be able to work with them generically. In most of those cases, we're not really talking about recursion in any interesting sense. We're talking primarily about types which are products, and types which are products, at least in strict languages like Scala, aren't recursive. Because if they were recursive and they were just products, then they would be infinite, which is something that doesn't tend to work terribly well in Scala, but at least not without clever trickery. So it wasn't until people started seriously starting to want to play around with using shapeless and generic programming to work with ADTs. So things which are using the typical scalar representation of an att, namely a sealed trait extended by some number of case classes which you can think of as a sum of products or a co product of products representation of a data type. It's at that point that recursive things begin to show up very, very naturally and very quickly.
- [37:12]
Interviewer
So.
- [37:15]
Miles Sabin
A list data type, for example, has two branches. It has a nil case and it has a cons case. The cons case has a list of t, will have a t element, and it will also have another list. So as you work your way through a value of the data type, you will typically find yourself revisiting the type that you started with. As I walk through the structure of a list of T, I will repeatedly revisit the type list of till eventually I hit the end of the list. And this is something you don't see until if you're only working with product types, because as I said, the recursion there won't show up. But as soon as you do, you tend to hit it almost immediately. And in those circumstances, the kinds of mechanisms which, in Scala in general and Checklist in particular, you would use to be able to compute over these types, implicit resolution is almost immediately going to basically fail for you, as you're trying to, if you like, summon a type class instance for a recursive data type. The moment the compiler hits the first recursive occurrence of the data type you started with, it's going to complain that, that the implicit expansion that you're currently working with is diverged, and then the compiler will bail with a diverging implicit expansion error and everything grinds to a horrible halt. Getting to understand exactly what was going on with that and working out how to deal with that kind of case, I think it was both interesting from the point of view, actually solving that problem, which at least initially in Shapeless was via Shapeless lazy pseudeptide. That was both very encouraging in the sense that perhaps somewhat amazingly, it turned out that it was possible to solve this problem via a Scala macro, which is, I think, surprising. So that was kind of nice. It was encouraging because that actually opened up a whole whole new range of things that Shapeless could practically be used for. So, for example, most of the type class derivation type applications that Shapeless is used for these days, which I suppose I haven't mentioned, I haven't actually given explained what type class derivation is yet. But very briefly using the sort, if you like, the generic structure of data type to drive the automatic generation of typeclass instances for that data type. So type class derivation isn't the same thing as generic programming, but generic programming can certainly be used for type class derivation that I think is now the main application of Shapeless.
- [40:24]
Interviewer
So what's an example? Well, to kind of add some meat to it.
- [40:30]
Miles Sabin
Typical examples that you find almost everywhere are deriving codecs, for example, for algebraic data types. So I think one of the first libraries to do this in a really, really nice, elegant way was Michael Pilquist's escodec or scodec, depending on how you pronounce it. Things like Circe, for example. Travis Brown's JSON library for Scala is another really nice example of the same thing. So there the idea is that at least in some modes of operation, you should be able to present your serialization deserialization library with a value of some data type it knows nothing about, and have the library infer the appropriate serializer and deserializer typeclass instances for that data type without any runtime reflection, for example, just working off the structure, the generic structure of the data types in question.
- [41:44]
Interviewer
So like, if we're talking about serialization to JSON, like we're talking about adding A type class that can do this conversion based on the structure of the adt.
- [42:00]
Miles Sabin
Well, the type class will be defined by the library, but providing an instance for that typeclass for a user's supply data type. Yes, that's right.
- [42:12]
Interviewer
I wonder if we could dig into this example. So I could have, as you're saying, a product and co product type. So maybe I have. Actually, do you have a good example?
- [42:22]
Miles Sabin
Might as well use the list example that we had earlier on. So a list being a co product of nil and cons, and cons being a product of a T and a list of T, maybe. So in this case, the codec has to be able to serialize and deserialize a recursive value. The list itself is recursive, that its type is recursive. So what that means is that basically any type class instance which is capable of serializing or deserializing a list itself has to be recursive. So if the type class instance is being computed by implicit resolution, it means that somehow or other implicit resolution has to produce a recursive value, a value which refers to itself. And that's precisely the thing that the Scholar divergence tracker is intended to prevent from happening. It's supposed to prevent you from attempting to make recursive implicit resolutions. I mean, it's on the assumption that there is no way of, as it were, implicitly tying the knot to make a finite sort of lazily constructed recursive value. So the lazy type constructor was basically a mechanism to provide just exactly that mechanism to provide a means by which an implicit resolution can produce a recursive value. I mean, it provides a mechanism for implicitly tying a recursive knot. That was, I think, an absolutely critical part of making Shapeless actually useful for doing real work, pretty much. And it wasn't until I'd actually run into this problem, attempting to put together an automatically derived extension for a serialization library, that I realized that this was a critical missing feature. And then I went back to the original Simon Paton Jones scrap free wallet plate paper, realized there's a whole big chunk, there's a big section on how he had to extend GHC to support something he called recursive dictionaries, which I had completely glossed over, I had completely missed, because at the time I'd only been thinking about product types. So the need for such things was not at all clear to me. And I realized that basically I had, in effect, rediscovered the same problem that he'd solved several, numerous years before and effectively Reinvented a very similar kind of solution, which was also, I think, really kind of interesting. By the way, this relates to some work I am doing currently in conjunction with Light Bend. One of the things I have been working on is actually adding something with more or less the same semantics as Shapeless as lazy directly, directly to Scala. So this is some work I'm doing on the Scala compiler right now I'd spoken to. One of the things I suppose I've been thinking about for a while is Shapeless. I have a very mixed feelings about macros in Scala. On the one hand, they are used quite significantly by Shapeless to do various things that can't be done in any other way. On the other hand, I mean, shapeless is all about. It's all about using the power of types directly in a programming language as opposed to sort of escaping out to sort of extra linguistic mechanisms like, I don't know, code generation or whatever. And macros are basically the same as code generation. So in a way it's always felt slightly uncomfortable that shapeless language is supposed to be based on sort of principled typefall type driven development style is actually under the hood, is very much in hoc to Scalar macros. There's practical issues as well, which is that there's absolutely no chance whatsoever that Scala macros will be in any way shape or form portable to DOTI and in many ways the existing macro API because it exposes so many internal components details, it's a bit of a boat anchor on the current Scala implementation. Independently of dotting, it's very difficult to change internals when those internals are actually exposed and things which are relied on and used by people in macros. So it's always been in the back of my mind that I've wanted to try and work out some mechanism for basically adding the minimal set of additional primitives to, to Scala to be able to either reduce the use of or ideally just eliminate the need for macros and Shapeless altogether. So as part of that I've been thinking about what could you do to replicate Chocolate's lazy. It turns out that there is a hole in, well, not so much a hole as there is, if you like, an empty space in Scala syntax. Just almost crying out for being repurposed for exactly this purpose, which is by name implicit arguments. So in current Scala, implicit arguments are only allowed to be standard strict arguments. It's not possible to have binomial arguments. And it goes to me, well, we have potentially, I mean, you can attempt to write a binary Implicit argument, and it will just be rejected by unsupported implicit arguments. Must be strict or something along those lines. But it gets me. You could potentially use that syntax anywhere where lazy is currently used in shapes code, which does that kind of thing. And this is actually a really, really smooth, easy transition path from the language that exists now to something has this rather interesting extra feature because basically the syntax is currently unused. There are no existing programs which need to have their meaning changed or adjusted in any way whatsoever. And so I think I'm trying to remember what it was. I think it was a couple of years ago I bumped into Martin adersky@scalaio and kind of mentioned that I was toying with the idea of seeing if I could, I could add those semantics to Bino implicit arguments. And he sort of hummed and hummed about and thought about it, went away, and the next thing I knew he'd added that feature to Dottie. So Dottie has, has binary implicit arguments. I was sort of briefly, kind of slightly encouraged that that was great because Martin had done it. That means I wouldn't need to write a sip, which is the Scala Improvement Document specification document, which, which is supposed to accompany any new Scala language feature. Unfortunately, although I thought that that would mean that Martin or one of his students would do it, that hasn't actually transpired. So I ended up having to write the zip myself. But anyway, so with the precedent of this habit having been done in Dossy, it seemed like a bit of a no brainer to just add this as a feature to Scala. If we're lucky, there's a pull request sitting in Scala, Scala, GitHub, repo. There is a SIP currently going through the SIP committee and if we're lucky, we should, with any luck, see Binance implicits, either as described there, or with some tweaks and adjustments arriving in Scala 2.13, which will be really, I think, really quite a nice addition to the language. And from my point of view as the sort of maintainer of shapeless, it will be an absolute godsend, because the shapeless macros that support the lazy type constructor are absolutely horrendous. They're not pieces of code that I would wish on anybody, because to do the things that they do, they have to rely on all sorts of really horrific. They have to go beyond the official public macro API and make use of various nefarious bits of Scala compiler internals to do the work they do. And the actual direct implementation directly as part of the language is hugely simpler, much less fragile.
- [51:54]
Interviewer
I Mean, sort of the definition you had for generic programming was that things that you can't do, like first class in the language. So, you know, is your path here to constantly kind of try to get things added to the language until the story begins?
- [52:09]
Miles Sabin
I think so, yes.
- [52:10]
Interviewer
Is this an example?
- [52:11]
Miles Sabin
Definitely an example of that. I think I would actually be very, very pleased to see Shapeless disappear, more or less. It just simply become a bunch of ways of just using first class features of the language itself. I think that there are a number of things that I'm quite proud that Shapeless is sort of raised to prominence in Scala programming in general. I think generic programming is one of them. Programming with singleton types and dependent types I think is another. These things all sort of play and hang together quite nicely in various different kinds of ways. I think most of the most interesting uses of Shapeless tend to use more than one of them, I suppose. I mean, it's very common to find singleton types being used in conjunction with generic programming. So singleton types, for people who don't know, are very, very precise types. So they are types which have a single inhabitant. So for example, as well as the type string which represents the strings foo, bar, baz and all the rest of them, you might have a type foo which is inhabited only by the value foo. Now, on the face of it, it might not seem particularly useful to have a type with a single inhabitant of that form, but in fact it is enormously valuable in that it allows you to lift a number of interesting sort of value level constructs to the type system. So for example, one of the things that you might want to be able to do with say a case class when you're working with it generically is represent not just the types of the elements that it contains. So for example, if I have a case class which is contains an int and a string, as well as being able to represent the fact that it's an int and a string, which you could represent as, I don't know, a tuple 2 of an int and a string. You might also want to capture the fact that the label, the name, the field name for the integer is, I don't know, for example, age, and the label for the string is name. And if you can do that in an interesting way, which allows you to actually work with labeled types or labeled records in a similar way to the way that you might work with them as values, then you can do an awful lot of very, very interesting things. Compile time. So one of the applications, for instance.
- [55:20]
Interviewer
The serializer we were talking about earlier. Right. Would require absolute.
- [55:23]
Miles Sabin
Yes. So if the serializer is going to make use of labels rather than just sort of positional information, then yes, it absolutely needs to be able to have some kind of access to some representation of the labels that are used to pick out the fields. There are other things you can do with it as well. I mean, there are some very interesting things that people have done with using these kinds of techniques to model database migrations. So, for example, if you're moving a, you're moving a table from one schema to another and you've reordered some columns, you've added some columns, you've got some values of the old data type, and maybe you've got some mechanism for adding, I don't know, adding or computing values of, say, the new columns or swapping things around. It would be very nice if you could just ask the compiler to infer for you the transformation that's required to turn a value of the old row type into a value of the new row type. Row type, if, you know, provided with additional sort of supplementary values to fill out the missing elements. And that's something that you can actually do really, really quite nicely if you are able to. If you're able to line up, align the columns not just by their type, because obviously very, very often we'll find the same type appearing in many columns in the schema, but also by their name as well. And if you can perform that kind of permutation, or at least have the schema for that kind of. Sorry, not the schema, you can have the, if you have the description of that permutation can be computed for you at compile time. That can be really quite nice. And you can in effect write a migration of sorts just once and have that apply to any, any mapping from one row type to another. And I think that's also kind of quite a nice, interesting use of these kinds of techniques. So that requires singleton types. Singleton types are making their way. Well, they have made their way into Scala both in DOTI and just recently in Scala 2.13 by way of the literal types language extension, which has gone through the SIP process. It's been around for a very, very long time now. It's taken many years to actually land in the Scala compiler, but it's there now for 2.13. So I guess that is another shapeless which has made its way into the language, which I think is also a great thing.
- [58:27]
Interviewer
I'm interested to hear about this process where you have the type level compiler and you're trying out ideas there and then hoping to get them into mainline Scala 2 or what's the process?
- [58:42]
Miles Sabin
Well, the type of Scala compiler, it's been very much testbed for trying out approaches to problems which particularly traditionally, have been of interest to people working at the more functional and typeful end of the Scala programming language spectrum. Things like literal types certainly made their first appearance in the types level Scala compiler talk. At this precise moment, most of my effort is actually involved on getting things out of the type level Scala compiler fork and into the language proper. I think that's always been the goal. I think the really great news is that for the last year or so, I think we've actually been making really quite significant progress in actually doing that, having a type level fork as an environment where people can actually get some real experience with, with language extensions. And just for example, maybe you can just learn that a particular approach doesn't really work.
- [59:59]
Interviewer
So I want to be somewhat conscious of your time. If I learn one important lesson, it's that I should apply to speak at a conference for something I haven't created and then several years later.
- [60:13]
Miles Sabin
Absolutely do it. Yes, I highly recommend it.
- [60:20]
Interviewer
All right, Miles, it's been great to talk to you, thanks so much for your time.