Generic Programming

Miles: I basically submitted a talk proposal for AP Exchange. So I put it in a talk proposal on which was [inaudible 00:00:11] 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 I was the keynote speaker, someone who was actually going to be in the audience was going to be Sam Payne Jones. So I was going to have to come up with something at least moderately convincing to be able to get that past him.

Adam: 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’ Scrap Your Boilerplate functionality to Scala. Once his talk was accepted, he only had one thing left to do, 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 scale of C compiler. So Miles, some point around 2014, I was writing some Scala and I had to write a function that grouped a tuple.

So I had a tuple with two values and I needed to turn it into… Sorry. I had a list of tuples and I needed to 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 a three element tuple and does the same thing, takes the first element and groups the second elements into a map based on that value. And then I had the thought at that time 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 both shapeless and generic programming. So what is generic programming?

Miles: 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 Program, which is kind of the main sort of academic stroke industry of functional programming conference annually. And this workshop title has been the Workshop on Generic Programming, WGP. I guess, I’ve been going to that at least as regularly as I’ve been going to ICFP. And a few years ago the workshop had a kickoff session, and 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 it wants to do is, what’s the sort of the elevator pitch for generic programming that we could use to make it more accessible, more visible to people 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 catchy one-liner that sort of group in the workshop came up with at the end was something along the lines of a generic programming is kinds of polymorphism that your programming language doesn’t support yet, 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 standards parametric polymorphism or subtype polymorphism, and language like Scala, which has both. It’s an idea of being able to abstract over shapes of data more generally than you typically easily expressed or representative.

There are lots of gray, fuzzy areas where the kind of polymorphism that people typically tend to talk about in terms of general 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 get used to working with become richer and richer and more expressive, I think in some respects, generic programming as a sort of separate independent kind of discipline is likely to sort of disappear, be submerged into general discipline of programming the types. But at the moment, I think the way you would tend to characterize it as, it’s programming, which depends on having a representation of the shape of data in some very general sense of what the shape of the data type, values of 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.

Adam: A two tuple and a three tuple, they have no commonalities 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?

Miles: 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 uninteresting and unhelpful common types, both of those types. Tuple two and tuple three and Scala share a common type called products 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 particular, 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 sort of boilerplate code, for example.

So in the case of in the case of tuple two and tuple three, the thing they have in common is that they in a sort of slightly mocking way captured by the Scala products trait. What they have in common is they are both product types, you can think of them as being. In the case of tuple two, its product of two types A and B. In the case of tuple three, 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 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 types that are involved here.

So if you can come up with some way of representing generally a product of types and then also work out some mechanism for generally computing over the types which represent products or types. Then, you’re pretty far along with being able to work in an abstracted way over tuples.

Adam: This is a product type in terms of algebraic data type, as opposed to a sum type set?

Miles: It’s a prototype in this as well. Sum type is a co-product. It’s something which represents a choice between different possibilities or 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 A, a B, and a C. In the case of a some 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 sum types later. But if you have a co-product of those sum types, you have exactly one of A, B or C. So there is a difference here in terms of in terms of what do you get here, what the elements the type is composed of.

Adam: There’s a relationship here, I guess, between generic programming and dependent types. It seems to me, I’m not quite clear on it. It seems like you’re pushing the language towards having first class types. What are your thoughts?

Miles: I suppose so. I’m certainly enormously enthusiastic about dependent types. I think being able to bring dependent types into languages that people can use in their day jobs as opposed to well… Okay, there are some people who can already use languages in their day jobs. But there 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 addition of this podcast. I have enormous respect for the work that Edwin’s been doing. I think it’s fantastic staff. I draw a huge amount of inspiration from what he’s doing. To be honest, much as I would love to see it, I don’t really see that as being any particularly natural evolution of Scala in the direction of Idris full spectrum dependently types, programming language.

I think 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. There’s lots of work being done on dependent Haskell. We’ll be very interested to see how that plays out over the next few years, but I kind of think that sort of 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 parts of the software world where types matter to us, I think it’s pretty clear that the direction of travel is in direction of dependent types.

And I think that as much as we can do to move things along in our own corners of the ecosystem. I don’t know want to over-claim. I’ve definitely show a lot interesting ways that people can use Scala forms of dependent types in fairly explicit ways, some of which I think were perhaps not expected and slightly anticipated. But it’s important to remember that dependent types have been a part of Scala since the very beginning. The very, very earliest descriptions of Scala semantics make absolutely [inaudible 00:13:45] of at least a form of dependent typing. Path dependent types are something which has been part of the Scala language specifications 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 programmatic language is concerned. [inaudible 00:14:13] I guess one of the most visible people when it comes to talking about pronouncing dependent types, perhaps more in academic context than amongst working program. But nevertheless, I think he takes it, he takes a fairly liberal view, which is that there are a lot of programming languages which can be viewed quite reasonably as having aspects of dependent typing. So in conversation with him, he’s quite comfortable to say that Scala is one of those language. Haskell is as well, even prior to things like Mascot, there’s JIDTs gets you some aspects of dependent typing. So we are slowly getting there. It’s actually kind of interesting in some respects that although shapeless, with techniques shapeless, they are pointing in the direction of dependent types programming.

Actually, to some extent, the ways that they use Scala’s intrinsic dependent types is almost accidental actually. In many ways, the techniques that shapeless [inaudible 00:15:32] are actually closer to some of the techniques in Haskell that you might use for simulating dependent types without really having a first-class dependent types, even though Scala does actually have a form of first-class dependent typing, which is kind of convoluted.

Adam: So Edwin wants to use this term at least in Idris, first-class types. And I saw a Stack Overflow posts 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. It returns either string or int. It’s like three lines of Idris, 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 I highlighted the fact that having functions over with the return types is not like a first-class construct in Scala.

Miles: 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 sort of claim that it’s mainstream on the grounds that adding these fancy programming language features, it adds this weight, this burden of complexity. I actually think that’s looking at things almost completely the wrong way round. Typically people are faced with solving pre-existing problems which have a degree of complexity of some sort. So intrinsic complexity in the nature of the problems themselves.

They are going to have to somehow rather 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 problem domain, simpler. If you force people to kind of model things by complicated encodings or indirect ways of representing the 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 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 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 a boilerplate, but to be able to do that as effectively as possible, you’ll typically end up having to add nontrivial [inaudible 00:19:08] language features of some sort or another. 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 adding expressive power to our language types and going in that direction.

Adam: and also the complexity at the language level, you learn that once and you can apply it anywhere the language’s used. The complexity boiled into an ad hoc implementation in your application.

Miles: Absolutely.

Adam: It’s not as reusable.

Miles: 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 by-name implicit in the Scala compiler in 213, 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, in fairly unhelpful ways over the years, it’s not about code base and it can be really quite pleasant to work with. And not withstanding the fact that the terms of the Scala compiler are perhaps not completely straightforward. I think the implementation of by-naming plus arguments is orders of magnitude easier to understand in the Scala compiler than it is in the shapeless macro. 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 aren’t relied on by multiple parties.

Adam: That seems to me, there’s a sense in which doing the, back to my dependent type example, like doing that Boolean or in-type in Scala compared to Idris is sort of doing functional programming in an early version of Java, 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.

Miles: Yeah, I think that’s right. 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 hobby time, tinkering time playing around with Idris or one of the other dependency 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 what can be done. I think that until it’s clear just 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.

Adam: So one thing you mentioned earlier was sum versus co-product, do you want to briefly touch on that?

Miles: Oh, right. Okay. Yeah. So the difference between a sum type and a co-product is that 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-products of A, and A, and A is quite distinct from just A. And one way you can think about these things… To be honest, I think I’ve learned a lot in the process of working through the various iterations of shapeless. One of the things I realized that was a complete mistake, was to actually have a first class HList and co-product types.

There’s really no particular reason why they would be needed in preference to say having representing HLists… Well, representing product types as nested pairs terminated by unit or something. And in the case of co-products, this nested either is terminated by some terminal type nothing, maybe. But if you compare for example an either type, think about a nested either, and there’s quite clearly a difference between either of A, and either of A or nothing and plain A. So the different types, does it matter. The answer is it kind of does matter because one of the things that’s sort of… The fact that these things are called co-products and co-prefix should be a little bit of clue, co-products and products are essentially due 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 shapeless, is that pretty much everything you can do with an HList, or 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 in shapeless for manipulating HLists, 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 reputation.

Adam: I’m missing how they’re identical, their structures.

Miles: Well, they have the same inductive structure in terms of a head and a tail. I guess, is the main thing. They both have a particular kind of monodal structure, which essentially means that you can… I’m trying to think of a good example of something which is… Let me think. Well, okay, so there’s something that you might… I think the thing too, would be to look at any of the ops type classes in shape. So that they’re defined for HList and co-products separately. So for example, you want to compute the type level length of an HList, for example. So there is a type class that each will compute the type level length of an HList.

There’s also a type class which will compute the type level length of a co-product. And although they are not currently in shapeless, the same code, and if you look at the structure of the type classes and the instances which are provided for them, they are essentially identical modular the fact that one is from joins, in terms of HLists. And the other is [inaudible 00:28:03] in terms of co-products. There is a single underlying abstraction, which would allow both of those, both of which would allow those two type classes to essentially become one. And I think that is a potentially very powerful additional abstraction. That’s something I’ve done a little bit of-

Adam: So does it make sense to think of it in terms of and, and, or like one is a certain structure?

Miles: Yes, exactly. Absolutely. Exactly that, yes. And a lot of this stuff comes from a paper called datatypes and entitled data types [inaudible 00:28:51] from the General Functional Programming, a few years back. It’s well worth reading. And in many ways, a lot of the sort of been foundational for quite a lot of the most interesting work on generic programming.

Adam: I think I saw somewhere that you have based some of your earlier work on the Scrap Your Boilerplate paper. I don’t know if that’s true or?

Miles: That’s absolutely true. Yes. So this 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 shaped started at the very outset was as a sort of challenge I set myself to see if I could translate the variants of Scrap Your Boilerplate that is described in the paper Scrap Your Boilerplate with class, the Simon Peyton Jones. And the reason I started out with Scrap Your Boilerplate is because for start it’s a mechanism, which… So the general idea behind Scrap Your Boilerplate is to be able to perform general traversals over arbitrary data types and general transformations on arbitrary datatypes. 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 put together this model was the fact that in Haskell, there is no first-class representation of tight classes. Tight classes are different from types and tight class instances aren’t first class values in the way in which seems intuitively that they seem to be required taking the approach that he was taking in this paper. And one of the innovations that he and [inaudible 00:31:36] 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 tight classes and instances. And I thought, “Okay, that’s interesting.” I mean, we kind of have that for free in Scala and 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 Scala directly.

In retrospect, it’s actually a fairly simple translation from the one to the other. At the time it was enormously difficult. It took a very, very long time, I think, to see exactly how to make that work. I think people sort of general ability to kind of map Scala concepts onto Haskell concepts and vice versa has improved… 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 that language can be translated over to the facilities available and the other, I think much more swiftly than used to be the case. So that’s kind of the origin of the origins of shapeless.

Adam: Did you have a goal in mind or was this a fun project?

Miles: It was partly a fun projects, but I also set myself… The way I set myself up for this was I basically submitted a talk proposal for… I’m trying to remember which [inaudible 00:33:43]. It was a small conference put on by Skills Matter in London. I think they run a number of conferences, which they add exchange as a suffix. So there was 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 on 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 I was the keynote speaker, 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 convincing to be able to get that past him. I very deliberately sat down to see if I can actually work out how to do this thing and spent 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 realize there is 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 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 datatypes was actually going to be an issue. I think some of the first things that people look at in generic programming is things a little bit like the examples that you were just describing in the beginning, where you were talking about when you want to abstract other things of different heritage, tuples of different sizes and being able to work with them generically. And 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 straight languages, is like Scala don’ts aren’t recursive because if they were a cursive and they were just products, then they would be infinite. Which is something that doesn’t tend to work terribly well in Scala, at least not without clever trickery.

So it wasn’t until people started seriously starting to want to play around with using shapeless in generic programming to work with [ADTs 00:36:43], so things which are using the typical Scala representation that ADT, namely a sealed trait extended by some number of case classes. And which you can think of as a sum of products or a co-product of products representation of the datatype. It’s at that point that recursive things begin to show up very, very naturally and very quickly. So a list of data type, for example, has two branches. It has a Nil case, and it has a Cons case. The Cons case has the list of T, or have a T element. And it also have another list.

So as you work your way through a value of the datatype, you will typically find yourself revisiting the type that you started with. As I walked through the structure of a list of T, I will repeatedly revisit the type list of T, until 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 shapeless in particular, you’d use to be able to compute over these types of resolution. And is almost immediately going to basically fell before you. If you someone that a type class instance for a recursive datatype, the moment that the compiler hits the first recursive occurrence of the datatype you started with, it’s going to complain that the implicit expansion that you’re currently working with is diverged.

And then the compiler will fail with a diverging implicit expansion error and everything grinds to a horrible halt. And getting to understand exactly what was going on with that and working out how to deal with that kind of case… And it was both interesting from the point of view, actually solving that problem, which at least initially in shapeless was via checklist [inaudible 00:39:13]. That was both very encouraging in the sense that, perhaps somewhat amazingly turned out that it was possible to solve this problem via a Scala macro. It’s just, I think, surprising. That was kind of nice. It was encouraging because that actually opened up a 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’m haven’t actually explained what types of derivation is yet.

But very briefly using the generic structure of data type to drive the automatic generation of type instances for all that data type. Type class derivation isn’t the same thing as generic programming, but generic programming can certainly be used for all type class derivation. That I think is now the main application of shapeless.

Adam: What’s an example to add some beat to it.

Miles: The typical examples that you find almost everywhere are deriving codex, 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, Scodec or Scodec depending on how you pronounce it. Things like [inaudible 00:40:56] 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 the value of some data type it knows nothing about and have the library infer the appropriate serializer and deserializer type classes [inaudible 00:41:27] for that data type without any runtime reflection for example, just working off the structure, the generic structure of the data types in question.

Adam: So if we’re talking about serialization to JSON, we’re talking about adding a type class that can do this conversion based on the structure of the ADT?

Miles: The type class will be defined by the library but providing an instance for that type class for uses [inaudible 00:42:09]. Yes, that’s right.

Adam: I wonder if we could dig into this example. So I could have as you’re saying product and co-product type, so maybe I have… Actually do you have a good example?

Miles: 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 T and [inaudible 00:42:37], maybe. So in this case, the codec has to be able to serialize and deserialize a recursive value. The list itself is recursive. It’s type is recursive. So what that means is that basically any type class instance which is capable of serializing and deserializing a list, itself has to be recursive. So if the type class instance is being computed by implicit resolution, it means that somehow rather, implicit resolution has to produce a recursive value, a value which refers to itself. And that’s precisely the thing that the Scala divergence checker is intended to prevent from happening. It’s supposed to prevent you from attempting to make recursive implicit resolutions.

It’s on the assumption that there is no way of implicitly tying to knot and to make a finite sort of easily constructed recursive value. So the Lazy type constructive was basically a mechanism to provide just exactly that mechanism, to provide a means by which an implicit resolution can produce a recursive value, provides a mechanism for implicitly tying your recursive knot. That was, I think an absolutely critical part of making shapeless actually useful 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 that I realized that this was a critical missing feature. And then I went back to the original Sam Payne Jones, Scrap Your Boilerplate paper and realized there’s a whole big chunk. There’s a big section on how he had to extend [inaudible 00:45:08] to support something he called recursive dictionaries which I had completely glossed over. I had completely missed because at the time, I had only been thinking about product type, so the need for such things was not at all clear to me.

And I realized that basically I had ineffective, we discovered the same problem that he’d solved several numerous years before and effectively reinvented a very similar kind of solution, which was also really interesting. By the way, this relates to some work I am doing currently in conjunction with [inaudible 00:45:49]. One of the things I have been working on is actually adding something with more or less the same semantics as Lazy directly to Scala. So this is more coming to the Scala compiler right now.

One of the things I suppose I’ve been thinking about for a while is I have very mixed feelings about macros and Scala. On the one hand, that they are used quite significantly by shapeless to do various things that can’t be done in any other way. On the other hand, it’s all about using the power of types directly in the programming language, as opposed to sort of escaping out to sort of extra linguistic mechanisms like cogeneration or whatever. And macros is basically the same as cogeneration. So in a way, it’s always felt slightly uncomfortable, but that shapeless, which is supposed to be based on principles type, full type driven development style is actually under the hood is very much in hock to Scala macros. There’s practically issues, as well, which is that there’s absolutely no chance whatsoever that Scala macros will be in any way, shape or form possible to [inaudible 00:47:18].

And in many ways the existing macro API, because it exposes so many internal compiling defenses, it’s a bit of a boat anchor on the current Scala limitation. Independently adopting it is very difficult to change internals when those internals are actually exposed on things which are relied on and used by people in macros. So it’s always been in the back of my mind that I’d wanted to try and work out some mechanism for basically adding the minimal sets of additional parameters to Scala to be able to either reduce the use or ideally just eliminate the need for macros and shapeless altogether.

So as part of that, I’ve been thinking about, well, what could you do to replicate shapeless’ Lazy. It turns out that there is a hole in… Well, not so much a whole as that there is a there’s 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 a standard strict documents. It’s not possible to have by-name arguments. If you can attend to rights, I bind them into some argument and it will just be rejected by unsupported, implicit arguments must be strict or something along those lines.

You could potentially use that syntax anywhere where it Lazy is currently used in shapeless code, that kind of thing. This is actually a really, really smooth, easy transition path from the languages that exist now to something which has this 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. I’m trying to remember what it was, I think it was a couple of years ago, I bumped into Martin Odersky at Scala IO. And I mentioned that I was toying with the idea of seeing if I could add those semantics to by-name implicit arguments hummed and hummed about it and thought about it, and went away.

And the next thing I knew, he’d added that feature to [inaudible 00:49:54]. So [Dosi 00:49:57] has by-name implicit arguments. I was briefly kind of slightly encouraged that that was great because Martin had done it, so I wouldn’t need to write a SIP which is the Scala Improvement Documents, specification documents, which is supposed to accompany any new Scala language feature. Unfortunately, although I thought that, that would mean that Martin [inaudible 00:50:22] do it. That hasn’t actually transpired, so I ended up having to write this up myself, but anyway. With the precedent this has been done in [Dosi 00:50:34], 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 system in [inaudible 00:50:46] Scala repo. There is a sit currently going through these community and if we’re lucky, we should within [inaudible 00:50:57] by-name implicit, either as described, there will be some tweaks and adjustments arriving in Scala 2.13 which will be I think really quite a nice addition to the language. And from my point of view, is sort of the maintainer of shapeless, it will be an absolute godsend because the shapeless macros that supports 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 to make use of various nefarious bits of Scala component internals to do the work they do. And the actual direct implementation directly as parts of the languages is hugely simpler, much less fragile.

Adam: Sort of the definition you had for generic programming was things that you can’t do first class in the language. So is your path here to constantly try to get things added to the language until the story becomes better, or what?

Miles: I think so, yes.

Adam: Is this an example?

Miles: I think this is 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 has sort of raised to prominence in Scala programming, in general. I think genetic programming is one of them programming with singleton types, and dependent types I think is another. This things all sort of play and hang together quite nicely in various different kinds of ways. I think the most interesting uses of shapeless tend to use more than one of them, I suppose.

It’s very common to find singleton types being used in conjunction with generic programming because… Singleton types for people who don’t know, are very, very precise types. So they are types which have a single inhabitants. So for example, as well as the type string, which represents, the strings, [inaudible 00:53:31] rest of them, you might have a type [Foo 00:53:38], 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 and that it allows you to lift a number of interesting sort of value level constructs to the time 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 had a case class which contains an internal string, as well as being able to represent the fact that it’s an internal string, which you could represent with… I don’t know. With a tuple, tuple two of an internal string. You might also want to capture the fact that the label, the name, the field name for the integer is, 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 also an awful lot of very, very interesting things compiling time.

So one of the applications-

Adam: For instance, the serializer we were talking about earlier, would require this?

Miles: Absolutely. Yes. So the sterilizer 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. There are some very interesting things that people have done with sort of using these kinds of techniques to model database migrations. So for example, if you’re moving a type 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 certain 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. If provided with additional sort of supplements value to fill out the missing elements. And that’s something that you can actually do really, really, quite nicely, if you’re able to line up, align the columns, not just by the type, because obviously, very often we’ll find the same type of paring in many codes 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 purpose… Sorry, not the scheme. If you have the description of that permutation can be [inaudible 00:57:16] for you. At [inaudible 00:57:17] that can be really quite nice and you can in effect, right a migration of sorts, just once and have that apply to any mapping from one row type to another. I think that’s also quite nice and interesting use of these kinds of techniques.

That requires singleton types. Singleton types are making, or they have made their way into Scala, both in Dosi, and just recently in Scala 2.13 by way of the literal types language exemption, which has gone through the set process. It’s been around for very, very long time. It’s taken many, many years to actually land in Scala compilatory, but it’s there now for 2.13. So I guess [inaudible 00:58:17] shapeless which has made its way into the language, which I think is also a great thing.

Adam: I’m interested to hear about this process where you have the type level compiler and you’re what? Trying out ideas there and then hoping to get them into mainline Scala too or what’s the process?

Miles: Well, the type level compiler, it’s been very much tested for trying out approaches to problems which are particularly, traditionally have been of interest to people kind of working in a more functional and type full ends of the Scala programming language spectrum. Things like literal types certainly made their first appearance in the types level Scala compiler [inaudible 00:59:14]. At this precise moment, most of my effort is actually involved on getting things out of the type level Scala compiler before going 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 and actually doing that, having a type level [inaudible 00:59:45] as an environment where people can actually get some real experience with language extensions. For example, maybe you can just learn that a particular approach doesn’t really work.

Adam: I want to be somewhat conscious of your time. If I learned one important lesson it’s that I should apply to speak at a conference for something that I haven’t created and then, several years later.

Miles: Absolutely do it. Yes. I highly recommend it.

Adam: All right, Miles. It’s been great to talk to you. Thanks so much for your time.