C++ Siberia, 2015
August 28, 2015, Новосибирск, Россия
C++ Siberia, 2015
Video
Ranges for the Standard Library at C++ Siberia 2015
Available
In cart
Free
Free
Free
Free
Free
Free
Add to favorites
2.79 K
I like 0
I dislike 0
Available
In cart
Free
Free
Free
Free
Free
Free
  • Description
  • Transcript
  • Discussion

About speaker

Eric Niebler
Software Engineer at Facebook

He has written code for Microsoft Research, Microsoft Visual C++, and Boost.org, where he has authored 4 Boost libraries: Proto, Foreach, Xpressive, and Accumulators. He is also a release manager for Boost, a member of the Boost Steering Committee.

View the profile

About the talk

Eric Niebler will be giving the opening keynote. He is a freelance software developer, consultant, trainer and author. His specialty is C++ library and application development, with special emphasis on modern C++ techniques, and extra special emphasis on domain-specific languages.

Share

All right. Wow, okay before we get started like I'm super excited. Okay, great. I have never been to Russia before this has been an exciting week. I would like to thank everyone for being here. Thanks for having me. Thanks, especially to Yandex for sponsoring my trip and putting me up. It's been really terrific. Everyone has been just really really nice and I've been just really Blown Away by the hospitality and by everyone's English which is way better than my Russian. But I really didn't know how good everybody's English would be.

So I made a presentation that was almost all cplusplus because I figured we all speak that I hope you appreciate the fact that this is this talk is going to be just all code might start to finish. So if your English isn't that great, that's okay. You can follow along and in you know, are are chosen language. Okay, so I am, you know a little bit about me than active in the open source Community for about 13 years member of boost. I got for libraries and boost. I'm a member of

the Boost steering committee on Boost release manager. I've been on the C plus plus standardization committee for about 12 years and my Full-time job at the moment is to bring the standard Library into the Modern Age. So that's what I'm going to be talking about today. And when we talkin about my pet project, which is now become my full-time job, which is rejuvenating the standard Library by adding ranges range support to the standard Library. so I should say that dumb. You don't feel free to stop me at any time and ask me questions happy

to answer questions. I don't want to be leaving people behind. There's a lot of new Concepts in a lot of strange looking toad this coat the solution that I'm going to be working through in this talk is probably not going to be looking like a lot of code that you guys deal with on a day-to-day basis. So we got questions fire away, okay. When we talk about ranges we talkin about what they're good for my talking about what all the pieces are that make up the whole of ranges how they all work together and

talk a little bit about why you should care about what ranges are in particulars because it's completely different programming model lets you program in a way that does very expressive very concise barely functional correct by Construction. I'm going to talk a little bit at the end about standardization and where we are in the process what's been proposed and what's going to be proposed and when you might expect to see this stuff showing up in your standard length. I said the time I completely stole the idea for this talk from does anybody

know D the D programming language? Yeah. Okay. There's a d wiki somebody did a really interesting post on the d wiki about no ranges and using ranges to solve a particular problem. I thought this is a great problems going to make a great talk. So I stole it packed it and implemented it in C plus plus and I think it would be better. So here's the goal in a command line program that format command line the calendar for any year that you type in calendar 2015 Prince it all out to

the console. Pretty interesting about this problem is on the dates and times are these really awful human systems that are nasty and inconsistent months have different number of days and we start on different days each month some months or longer than others of formatting is going to be really weird. There's this sort of impedance mismatch because obviously in the order in which the candidates appear in the calendar, but that's not the order that things get written out to the console consoles this cereal thing so somehow we're going to have to rearrange

data on the Fly formatted correctly and print it all out. Seems like it's going to be you know, it's going to be really buggy. Imagine if you sat down to write this and with a bunch of nested for Loops calculating offsets and manipulating strings. The chances are good. Nichole is going to be a horrible mess is going to be ugly in long and you're going to be finding bugs in it until the cows come home. But we're going to do it a little differently and we're going to do it in a way that guarantees, correct.

Houston solution really working through this one line at a time and you guys go to see how all of the different pieces fit together in the process. We're going to learn all the different parts of the ranges library and how they all work together to make Solutions. Stop number ones pretty simple. Just create a range of dates. Prius I'm going to use the date time library from boost. Does anybody use the Tuesday time Library? Some people are pretty handy. I don't want to have to do all the nasty date manipulation myself fortunate if there's a library that does it for me.

This is terrific. I can create a date. November 5th 1955 I can print it out to the console. And there it is. 1955 November 5th, okay easy enough now I can create a range. Ranges in this talk of me taking from my library, which is range V3 Library. You can find it on GitHub. That's the link right there. So this particular range called The View iota? It's going to print out all it's going to be a range of all the integers between 1 and 11. And what a view is

about what a view is. We all know what container is like objector. If you was kind of like a container except for the fact, the view does not own its elements. The views ever reference elements stored elsewhere or they compute elements on demand. In this case. This range computes elements on demand actually just spits them out one after another until when I have to keep this code. It's just going to print all the integers between 1 and 11. So the library comes with some

iostream inserters extractors for making sure that you can just dump the rain out to the console and formatting some default way for us. And that's what weekend. simple enough questions about that Yes. Where's what? Where's the 1137 it's a half open range. I'm just like iterator pairs. You got up again than an end and the element that the end it'll reader points to is not included in the Rain's Gonna Break Your idiot the way you deal with any standard algorithm just

like when you have a container and you call begin and end, that's how those It Works Greens just like everything. Professor Banks What I was saying Rings views to any object that has two member functions begin and end just like a container and begin returns an iterator and returns. It could return in an iterator could also return something that is merely comparable to an iterator at call that a sentinel so iterator Sentinel pairs kind of a generalization of

the model that's currently in the IPL. You can come to think of these is algorithm think it turned inside out, you know an algorithm as you are already familiar with it from the SPL is you passed to iterators in in the algorithm equally does all the work between those two elements. When you turn that inside out what you get is something that gives you two iterators and lets you walk through the range and behind-the-scenes. The algorithm is executing as you step through it. So it's lazy and it's on demand. These things don't own their elements.

So you can pass them around. You don't have to worry about Spence's copies near composable Outlaws. Say what I mean about that in a little later. It's going to be one of the most powerful. Sorry one of most powerful parts of of ranges and abuses that they can compose with sorts of actions are powerful way and then on mutating so as you iterate through they to sequence you were pretty sure that you're at no point is any of underlying data getting mutated so you can do things in a purely functional way and you don't have to worry about

threading issues or anything like that. Okay, so we've got dates we've got this really handy view Iota thing which generates sequence of elements from start to finish so we should be able to combine the two of them to rain today it's so why use view iota And two days beginning date and end date like to think that this would be a range of dates for 28 doesn't compile. Can you get this message here a certain message US Weekly income in Savannah to the object pasture view Iota must

model the weekly incremental concept that is it must have pre and post increment operators and it must have a difference type. What is the exciting developments in C plus plus is that we're getting a new feature out of the language called Concepts. Concepts will let us check at compile time different properties of types, you know, if you guys have used the SPL chances are you've experienced horrible error messages when you've done something wrong right Concepts into address that

problem by giving us a way of saying in code what the requirements are on the types that you passed it generic algorithms. This is a concept check. BYO the only works with things that I can increment. If you can't increment something I can't count from start to finish. Okay, what time is out dates from the post date time library or not incremental? I don't actually know why I talk to the author of the boot date boost a Time library and he's like, I know I'm sorry. So anyway, it was just kind of a snafu. So he's going to add increment operator

to boost a Time library. But in the meantime, we'll have to hack it and I should say that obviously the reins library that I'm using here. You don't need a compiler that has concept support a kind of implemented in a conservative way to emulate contest but you do get some pretty nice error messages on this pretty good. Okay. So this is the hack. I just kind of like open up the Boost namespace Define The Operators that I think really should be there. Enclosed boost namespace and I can kind of a store that after

doing that okay dates are actually incremental now, they satisfy this concept. He was to say I mean, it's not very polite to go opening other people's name spaces the jamming your own stuff in there. So in practice this is probably not the right way to do it. Anyway. It works and when you do that, right I can save you Iota I skipped over that part. And I can either read over all of the elements. Are the first 10 elements at least to them who I want to talk about that

take the first 10 elements from this range from into and print out all of the dates a couple of interesting things going here run. Is this pipe operator? When is the earlier that dumb ranges and Views compose? This is what I'm talking about this creates of you. Are the range of dates from into and this is an operation that can input a range and output arranged by adapting it in an inch and the pipe operation and how we compose these operations on dues. If you've used the Unix command line, you probably

pipe the result of one executable into another executable and you can chain operations on the Unix command line using pipes. This is exactly the same thing except for training Ranch operation. So as you might think this print out the first date 10 dates of the year. What's going on there any questions about this code? Everlast everyone already eu4 expression view Iota from to buy view take 10 suppression templates or your library books brother. So am I using expression templates? No, this is not use expression templates at all. This is This

is just an operator. That takes in a range and spits out of range. It doesn't create an expression tree that then gets turned into a range later equally create a new range. Okay. Thank you your question. Russian about range for contract, right? Why use this stupid macro when people thought the leaven has this really convenient range based for loop, I would mention that sometimes Rangers have generators Sentinels. So begin returns amiibo reader and returns a sentinel Sentinel can actually have a different type than the other Raider as long as

these two things can be compared to equality and inequality that meets my definition of a range. But it doesn't satisfy. She perfected weapons range based for Loop which really expect begin and end to have exactly the same type. So if if the types differ between what is the game returns and what ends returns range for the built-in range for shows up at ants kind of pukes This macro is a temporary hacked until we can change the language to support begin and end having different types and it actually

support on the committee for making that change. So in the future you will need to do this is just a temporary thing. Okay, great. So you can print out the first 10 dates of the year. But don't go reaching into people's names bases and hacking their code for them. Okay. So our next step now that we've got a range of dates as we start manipulating our range of dates and weighs interesting to us what you find is that when you're dealing with ranges. The interesting programming

model is creating structure within a range and then breaking the structure down and interesting ways. The first thing we're going to do when we're going to create structure. We're going to turn a range of dates into a range of ranges of dates by grouping the dates that are in the same month. We can do that pretty simply with. This this guy right here a few Group by okay, what we do as we say all the dates in the year and date of the years view Iota and he was like all the date start January 1st Stop,

January 1st of the next year. It's all the dates in the year. Okay, and then group them. By this predicate takes two dates. And returns to if they're in the same month. otherwise So what that does is like for every adjacent date in your range group together all the ones that are in the same month and turn that into another except range and what you end up with the range of ranges of dates where each interval range is a month. So I can arrange over the months. Where this is going to be now

a range of dates and I can print out. first day of the month and when I do that I get the first days of the months in the year. Have you Group by is? A really handy an incredibly powerful adapter. We're going to see it used again. It's just one of many views that come built-in with brains V3. So one of the things that you might be able to see you in a future version of the people at the standard. I'm just for readability. What's refactor this a little bit. This is the exact same view Group by the same predicate that we had in the previous

line all we did when we moved it out of here and into its own function. Let's call it by month. Okay, and use C plus plus for teens Autumn automatic return type to Dakshin. So I don't have to say what type of returns which is good because this actually returns kind of a complicated type. So just say just by why don't you figure out what the return type is? Okay. I just want to give this thing a name call if I'm on so that I can do this with it. For each month in a year that has been carved

up by months. Do this thing? I think Otis was on the last Light is just refactored for readability. Nothing else Drake We're going to use that trick again. I need to know who buys just one of many view adapters that come with range Me 3 here's a bunch of the others. Lots of powerful things to choose from here these things combined together and really interesting ways. So the stuff that you might expect, you know, concatenate two different ranges intersperses value in a Range,

you know, make the range you meet. Is it a couple of different ranges into one range stuff like that? Okay, well then except for the obvious ones regroup in the months. We want to group the months into weeks. Okay, we're going to do the exact same trick use view good-bye again. I mean, yeah, we group together all of the dates that are in the same week that if they have the same week number. Oh, yeah. I want to talk about group by should the range be sorted before so the question is should Rings be sorted before I called the group by it doesn't

have to be sorted know what it does is it walks through the veins beginning to end and if there are Jason elements for which the predicate returns true those get grouped together. It doesn't scan the entire sequence to find things that need to be grouped together. It only groups together adjacent elements. Chris Eric, I have a little silly question why I oughta is cold as it is. Why is Iota call does it so there I picked Iota because there's already a standard algorithm that does this called Iota in numerics header

and wide is the standard Library have a function called Iota and I think it's from I want to say Ada or some other programming language and it's just like it's some like crazy Greek function that comes from some other programming language word means exactly what the committee members wanted it to mean so they just stole the name is just a placeholder is IC just a placeholder. Okay, so you could be months into weeks. It's the exact same thing as what we were expecting. The only snag is that we've already grouped. A year in two months. So we're dealing with a a

range of range of dates. Never going to end up with after recruit. The months into weeks is a range of range of ranges of dates things are getting complicated now. Okay, and in order to effect that transformation we have to first either rate over all of the months and then carve all of those months up in 2 weeks. So we use view transform. If you transform visits every element in a range and apply the transformation function. Yeah, another question here regarding by week function and C plus size 14 is I

remember in C plus plus 11 you couldn't really take decal type of an expression that contains the Lambda and what is effectively Happening Here is that we can just keep the decal type return type in by which function so I'm wondering how does it really work when you cannot do that? I know honestly, I'm not a core language guy. I don't know why this is okay. And the other thing, isn't it? That's a mystery to me, too. I wish I had an answer for you. I don't

know. All I know is this actually works. And it's cool. I've always wanted to be able to decal type of Lambda. This kind of gives me an easy out. One of those things like, you know, it's kind of like the Heisenberg uncertainty thing if you if you don't ask the question then if it's okay. Okay, so so here we are we transform every month by carving it up in 2 weeks. That's that's the storm guy over here transform each month like carving it up in 2 weeks and now I can iterate over every month. Dayton

year by month and carve the months into weeks. So we got a range of range of Ages of dates and what hurts your head, but now we can iterate over the months and then for each month we can we can visit each week and each week is going to be a range of dates. I can transform each week by showing only the days. I like slicing off the year in the month. I want to show that okay and print it out. And here's what we get. I'm starting to look like a calendar already isn't it a bit

kind of squint and see that so little by little we're kind of massaging this range of dates that we started with into something that's starting to look a little bit like a calendar. Crete-monee problem with this is like the week's need to be formatted a little bit more nicely. Got to get everything all lined up in Collins and stuff. So we need to do a little bit. But there's libraries to help you with string price and there's one in light and boost called boost format, but it'd be using that pretty heavily.

And I had to teach myself boost format in order to do this. And so like I don't expect you guys to know boost format already and it's going to take me a while to explain it. So I'm just going to kind of like wave my hands and say like this magic format string does what I say it does and take my word for it. Okay. so what type of function that takes a date and returns a string and it's just going to format that day in an element. That's three characters wide. That's all it does going to

right justify a day in a field with three characters line. And you do that by saying this magic format string format line pipe 3 pipe. and take out the day ignore the month and ignore the year just print the day into a few other three carriages fine. That's all of that does. Okay, let's break this down. It's called format weeks. So I'm going to be transforming a week. Which is a range of dates. Okay, that's what I'm going to do with it. I'm going to take the week. I'm going to transform

it transform each day turning it into a string thats 3 characters each day get to Spring Street and I'm going to join all the strings together. That's what this guy doesn't know what to talk about more about this guy a little later, but you can kind of think it is just might take all these different strings around them all together again what you get is a week formatted week. If you remember from the beginning not every formatted week started on a Sunday. So it's going to need to be in some cases some white

space in the front, right? So if your week only has three days in it and Thursday, Friday Saturday, you need a bunch of white space in the front. And that's what this does figure out how much white space we need right world one string that has that money whitespace characters in it. Animal Jam all that together and that's are formatted week. Okay. Now I can walk over all the months Target up in 2 weeks form at 2 weeks. Okay, and talk about join the second. Okay. And if I format the weeks will see you will see you in a

couple of slides the result of discontent summary. D2 I'm going to talk to check about action join join. You can kind of think like a mansion a lazy join a reason to join the takes a couple of ranges. I did read over it when I finish decorating with the first Rain by jump to the next range. Okay, that's not what this is. But this is his do something equally take a bunch of characters join them all together into a new string do it legally and the result is actually a container that going to tell him it's so it's totally different thing than a lazy join. It's an

eager joint. So I need your ego sequence algorithms. They can operate them return containers as opposed to the Views, which can't But they're composable like the fuse and I'm like the fuse they could potentially mutate their underline sequin. Okay. This Is How They stack up with views fuses raising ranges range actions are eager He's a lightweight non owning. These are essentially heavyweight cuz they take return containers. pitbulls composable Here's some of the actions that become like North End Library

split sort slice. These are pretty useful operations things that you might want to do two containers smell taken return container. Okay to give him a call that we had on the previous slide right we can. Arrangements dates private Apartments layout each month now print it out for you tomorrow print out. All the weeks in the month and this is what we get. Looks a lot like the calendar now. And just a checkpoint. Wee Britain. no beeps Are you guys seeing a single if statement anywhere in this code? No, it's statements. No, loops.

Every function that we've seen so far in fact is nothing but a return statement. pretty cool and we've got something that there's something quite sophisticated program is totally stepless. I'm not mutating any State anywhere in the program. When you meet a state that's what bugs happen if you don't mutate state. Pretty hard to write a book. pretty cool Okay, now what's missing here obviously we need like month titles Am I going to need to lay things out

Monday side by side? So the month title and we need to pad the week. So all the months to take the same amount of vertical space. Monster does not that hard whose daytime. Let's just do it has this month as long straight member function, so I don't have to localize my month names. So all I'm doing is changing the layout must function that we had in the previous line. So in addition to which is what we saw already month by week for Maddie's week. I'm going to

take month title of the first day of the month. I could have picked any day of the month. They all have the same one that I know. Turn it into a view. A range of one element few single takes an element turns into a range. MN concatenate that range by this other range This is the range of strings representing 4matic weeks guy is a range of one element contains the month title and content in mentos together and that will put the name of the month the top of Des Moines.

I want to do that now I get to January, February March. Anybody seen code any luck if you sat down and started working on this problem. This is probably not how you would do it is it? Okay. We're going to be wingman South Side by Side going to make our jobs a lot easier. If each month taped up the same amount of vertical Bass. Don't know if you noticed here. February takes up five lines January takes up six lines. That won't work. So well if we tried to lay these out next week, but we got to make it all the same 4matic months takes his fuse for in as many as six

lines. I want to pad to sort months with empty lines going to do. Same codes we had before except we're adding something. When are here. We have this mutant cat that we saw before. We're going to concatenate another range. This is like the brains of blank lines. First thing you do is we count how many weeks we got. And then six- the week count. That's how many blank lines we need. Repeat n takes an element repeated a certain number of times. Let me do that. Now we get some blank spaces here. Let's make our job easier when we try to leave stuff outside by side.

questions about that Okay. So far so good right here at the range of months months of range of strings. each month has exactly seven lines in it. We sure were guaranteed by the construction. Buy Mountain layout months reusable, they work even if the input range is infinite. Say instead of laying out. One calendar year we lay out every calendar year you can just keep spilling out for matted months forever. Nothing about our solution says that we need to stop

anywhere. And we're not doing. Any other location? Right, so we're not going to run out of memory just keeps going. Alright, please. Give me an interesting now. You have to figure out somehow getting things from this format into that format. This is where I had to do some really hard thinking. It's actually a little bit easier than it looks because what we have is we have a range of range of strains you can kind of think of a range of ranges as a matrix printer brain just rows and columns and we need to get the Matrix from here.

over here That's the transformation that we're looking for. describe in words how to go from that picture so that picture got to really think about it. Yeah question You should grab them by 3 by 3 by 3. Then we still have things going horizontally. Instead of the ladies over there so you can you recovery March January, February March. I think we need to transport the mattress from hell, so rude by 3 by 3 by 3 transpose. Exactly, right it took me a lot longer

to see that the new junk the months in the groups of Threes for each group of three months transpose the rows and columns. They can everybody see that the top three and then transpose them transpose the rows and columns we end up like that and then the transpose rows and columns be kind of like them all together. That's exactly the Transformer that we need to get from our way out. That was just one month after another today in side by side layup. Okay.

Turn the trunks on the strings of the inner ranges that is you know, you'll have three strings representing the three formatted weeks on a line side by side only knows that the rest of the day off. Go to the bar. Okay. Chunking it wasn't when I sat down to write this solution. My rings Library didn't have any way of chunking arrange. Something is an example of like taking a range and turning into a range of ranges structure. So somehow we have to implement this range so far. What we've been doing is taking existing pieces of the Rings library in assembling them to do

interesting things. Now, we have to wait create something new. We have to feed a newborn to doctor chunk adapter. That's what I'm going to show you next. Write a range adapter. In Woodbury comes with a handy range of daptor, but let's is actually Implement new range at types. What we're going to do, to chunk View. At parameters parameterize on an input range you take in a Range turn it into a range of ranges by chunking it. It blocks it three or four, whatever. Antenna store like the trunk size is in right

and the range adapter itself is going to be storing the underlying range for us. The real action is going to be going on in this adapter class. That's how we specify how we are changing the behavior of the underlying range and we're going to be doing is like instead of returning elements. We're going to return groups of elements. Posted that over there. Here's the adapter. Right. That's the sky. And this is mostly boilerplate. But what I want to show you

in particular is current this is like when you dereference an iterator, what should be returned Superchunk in the range into a range of range is the elements are now ranges. So when they touch the current element, the current element is actually three elements in a Range. whoops so here whatever our current iterator is Make a range from this point to the very end of the range and then take the first n elements of that that's going to be 3. So our current rather than returning element is

returning three elements. That's what this line does. and when we advance in it erator events at three elements This is how we Implement junk. Okay. Now, okay, we want to be able to take a range pipe it I will remember how we use the pipe operator to chain operations. So we need some chunking pipe operation. This is how we do it. We use something called make pipeable. And this is going to be kind of weird a little confusing. So I want to spend a little bit of time talking about make pipeable. This is how we build these adapter types junk

logically, takes two arguments change the rain to junk and it takes the number of elements in each junk two arguments in a timer stream. Send text right? Here's the first argument the range. Here's the second argument the number of elements in each junk. This is the syntax that we want. It's kind of like a function that takes two arguments, but with a really weird syntax. So how we do that you think about it chunk of n Must remember in and return an object. That's got an overloaded type operator. And it is that what this make pipeable helper

which seems kind of like it would be a hard complicated thing. There's actually only a couple of lines of code. Make pipeable takes a function of one argument. And everything is the pipeable thing. I just remembered that function with one argument. And pipeable remembers that function and has this operator pipe that takes one argument. And passes it to that function basically just rewrites. A function call into a pipe B. That's what that does simple enough.

Organic how it's actually used here. We've got Junk you pass it the chunk size. And to make pipeable we're going to pass a function of one argument. What is a Lambda that captures? Trunk size. So if you've done functional programming functional programming a lot of people with partial evaluation and carrying are you have a function that takes two arguments you call it was one argument what you get back is a function of one argument and that's what's going on here. We take this argument. We bind it in a Lambda. So we were members

that argument and now we get the second argument which is this rain and now we have both documents that companies we can create a junk for you from it. token junk View and we say password all of the elements from this range and we were turn it on for you. now I know what's really loopy and interaction like stop think about it for a while should make sense. And it seems like that. bathroom vanities Chunk the director of integers in two groups of three. I need to print them out.

There's the first chunk. There's a second sound. There's a third jump and this last Trump doesn't have three elements in it. That's okay. Just get as many as you can fit in there. Any questions about like how to create a range adapter? Dartmouth complicated I know it's a lot going on. Yeah. What does it mean if a friend? And it is a function. this guy friends Will be in Defiance. Dr. Douglas, I could have defined it as a just a regular free function, but dumb. At this is just

another way of another way of doing it. What was that? Yeah, so it doesn't get her back in her interact with the name look up so different functions to automatically generated, but really making it a free function probably would have been less confusing and also would have been found just fine. So it doesn't need to be a friend from him to answer your question. If on the other hand I had made this a private beta member which I should have done if I were being cleaner. So if this were a private then making it a friend

would you would access here to that private member? Look, like maybe you didn't get that Quinn so much. Okay, so it's for friends have access to your privates. I bet you didn't know that. So if this were a private beta member and If This Were instead of being a friend or just a free function declared say right there then that three function right would not be able to access this if it will private data member. Play free functions don't have access to private data members of glasses

in Scott's friends. However, do that's the only difference. Yeah. Plus start instead of class. He is actually the public remember, which is the point was it doesn't need to be a friend to it doesn't need to be a friend. If this had been a certain private. He doesn't then it does need to be a friend. Okay. Okay. Here, that's how we write on a range adapter. So it's kind of interesting. It's good to know that if the rains Library doesn't have the adapter that you need to get your job done. You could always

just write your own. Transposing a range of ranges. Remember we had said that our first step is to chunk into groups of three. Okay. We got the chunk adapter. That's great. Now we need to transpose ranges ranges. I have no idea how to do this. I really didn't I tried a whole bunch. Nothing was working. So I had to sit with the problem for a couple of days and what the problem really is that these things when I transposing data that's being generated on the Fly

and you need to do it in a lazy sort of way certainly like if I have a Range of ranges that is basically in a matrix if I had that Matrix saved in memory somewhere. Okay, if it weren't being generated enough life it we like Dune factors, but I can certainly transpose stuff easily enough, right? Cuz I can like me to pay stuff in place and jam values from here and sit here and vice versa price of transposing would be a piece of cake. That's not the situation here. We have sedated. It's being generated on the fly. It comes at us in a

certain format. We want to resent it in a in a different way in a different order and we need to do that transformation also on the Fly. So I have no idea really how to do that. Then I had. And I'll ha. Okay. What do you have right now? We got Make It Rain GIF ranges strings and we have it laid out like this. Now what we can do it. We got this structure. We can destroy the structure by doing it has a certain kind of trouble so we can enter leave all the elements. And get back something that's flat. We turn the range of ranges of strings into a

Justice at the range of strings. But you're the reading in this order. Okay, so when you see that so far. And now we junk. How many Rupees guys? Brent we get this we group these guys and we get that. And now we just transported. a range of Ages that are generated on the plane Ricci I did that we enter leave like this Okay. And then we junk. And that's transpose transpose is an interview followed by a tank. Okay. Okay, we already have chunk sweets already wouldn't worry about that part. We just have to worry about either leave now, okay. Create a new

interleaf adapter. Logically what it works. The way it works is we've got three ranges. We want to stay with three iterators. And we Garnet we're going to March all three iterator down like in lockstep and visit each element and then advance and then visit each element and then Advanced visit each element. That's how we're going to do the interleaf. Not a vector. arranges we're going to be using range facade. This is another helper rather than adapting and underline range. We're going to be creating a range from

scratch. Okay, I'm going to implement a curse or you can come to think of a cursor is an iterator, but without the complicated iterator interface. When you're implementing a cursor rather than implementing operator, + + 932 - - and all that other stuff. He just Implement current and next and that's an iterator. Okay, what's the temperature? I said we have a vector of iterators. Write this is a vector Victor Raiders the current element. Where am I in my marching across? My

iteration what Reigns am I iterating in? And then when I when I say next. okay, I'm going to increment and Check to see whether I reach the end. okay, that's going to go from 02301 to and then when it reaches three it wraps and then I pump all the iterators forward one. This Is How We Do interleaving Okay. And we're done. When at least one of the innovators has reached the end of its range. Okay, let me say okay. Well, I can't go any further one of these ranges is

expired. So done. Okay. And here's make pipeable. Now we do enter leave just the same way. We did junk the function of one argument. And now we can enter leave elements. So say we have arrange 012 I repeat it three times. So I have arranged of ranges 01201 2012. And I interleaving. I get 000 111 222 I start with a range of ranges. And I interview destroying the structure that's their flattening a range of ranges into a single range in a very particular way into leaving the elements. Remember view

Story 3 iterators before an iterator that points here at points there and that points there. And when I income in theater it is first I print this one and I print this one then I sent that one. Then I bumped all the iterators forward 1 there their and they're and someone now that I have junk and I have interleaf I have transpose. Transpose is just an interleaf followed by a chunk. I'm out taking that same input range. I can transpose and starting with 0 1 2 0 1 2 0 1 2 I go 0 0 0 1 1 1 2 2 2 2 I transpose the rows and columns Yeah

question. He was a lazy and actions are eager to check the action action. So it could be an action you could have a transpose action. If you wanted the input here though is dated a lazy and being generated on demand. And the advantage of having a lazy transpose is that you've preserved that it's still lazy and it's still on demand I can transpose. a range of infinite ranges Right if I have a range of the infinite ranges, it goes like this forever. I can transpose that right and I end up with an infant. Names

of ranges that goes down this way. If you tried to do that eagerly, you know, what would happen? Blow your memory is so one more question is are lazy eye by design that vectors that you mentioned before. So you need to know the length of their interval you need to wrap into the trunk of either a turd far as I see you there when you so you need to stop somewhere. You cannot create an internet Vector of its writers. So it's already became Eagles are there

in one direction right? So I had The example that I gave you fight a range of infinite ranges that works. Transposing an infinite range of ranges doesn't work given this implementation because I would be trying to create a vector of an infinite Vector of iterators and you can't do that. So how can you solve the basic there a limitation is that you need to work on limited Rangers somehow right? So if you're going to transmit it is a limited solution. You can't trip transpose an infinite range of ranges and I suppose you might be able to figure out something clever Maybe by doing some sort

of like a Canter diagonal exactly. The one Easton. I haven't really investigated it that deeply yet and I was happy just to figure this out. Call okay. Thank you. Okay. Let's go bolts are on time Spirit incomparable incorporate business perform. That's a good question. I didn't implement this in a traditional way to Benchmark against are they would have been really kind of an awful solution as I mentioned at the beginning like months for Loops pontiff offset manipulations. I didn't implement it. So I couldn't speak from experience on how

this performance I can say. There is some overhead here, like every interleave iterator is going to store a vector iterators vectors of iterators are dynamically allocated. So copying. Those are the Raiders is going to be kind of expensive. That's one thing. What is the computation that's being done here though is being done. Lazily without a location. You're generating elements on demand rather than like. Allocating a range of ranges of strings and doing string manipulations that are going to be creating a lot of temporary streams and doing string

concatenation. That stuff is not happening so much you're typing sound but not so much when you're generating stuff on the Fly you don't have to preallocate a whole bunch of memory just to have scratched face to do your work is very little scratch space is needed by the solution. In other cases things can be done in tirely lazily and without any allocation at all and in a way that is very transparent to the compiler to be in line and optimize very well. business about the bike

Cycle Center and training Cycles in conditioner Gilchrist Ranger send iTunes various to find them. How do you find the errors in the code? The first point is that? bike riding code this way what I have found is that if your code compiles It is going to do the right thing. It might not give you the result that you want. Right, but you can tweak things until the Dells give you the result that you want. And then your code is theirs. It handles error cases naturally like border cases off by ones. You never really dealing with off by one error as they just don't appear in Solutions like this.

If you are experiencing problems one problem that might typically come up in a solution like this would be a memory error that is arranged that is referring to data that has gone away. They can actually be really difficult to find a night. I'm sorry. I don't have it. You know a Magic Bullet here is debugging these applications can be really tricky when you have a memory error. What's the difference of errors that you're likely to see you're not likely to see a whole lot of logic errors off by ones that sort of thing. I found that debugging an

application like this is much simpler because I can use the compiler to find my errors for me. Where was using for Loops calculating offsets by hand. I'd say it's all on me to find the books. I asked a question that you said that there is something here compiles then it probably works. Right and is highly functional medical high school. So maybe you recognized the interleave function from the Haskell play lewd. Yeah. Yes. It was exactly where I got it from

and there's there's a lot of functional programming that goes on behind the scenes, but the the programming model is definitely different for cplusplus because Well, it is much different than you would think but sometimes you really need to do things equally and in Haskell, that's very hard. But in C plus plus it's very simple to do things eagerly or are you just a Dorito over it all at once and put it all in a container and pass it around and you're done. We are going to a school you

don't really have that option so much. So, yes, it's inspired largely by functional programming but in a way that we also have the power of the imperative language Andy grewe valuation. So I would like to join that there is a simple solution of that don't suppose problem and I use the recursive function with steaks. The Testament of Youth orange which conference ranges in the maps over there to spell the name so all this orange and text for I tried to

Port the transfers from the Haskell Prelude into ranges and found that I couldn't the transpose function from Haskell Prelude works on lists and lists of lists and it's really easy when the types of things don't change when you transpose them, but when the types do change right to the Haskell preludes function takes a list of lists. And outputs a list of lists and that makes it so much easier to write. This unfortunately, you have a range of ranges where you know, each internal rain has a the types of the internal range differ from the types of the out turn external range. And so

doing the transfers. You need to create something totally different type and it makes the solution much more complicated. I was unable to put half transpose into C plus plus in a straightforward way. I think you okay. So we're pretty much done. These are the only steps that remain and I'm kinda going to skip them. Because we already know how to do all that stuff. Begotten by month layout months chunk into groups of 3 transpose the months. Join does transpose months together and then join

the strings on each line, and that's it. Just write it out to the output iterator. Transpose monsters as you would think right giving a range of range of strings transpose them. and then three months for each month join each string in each month And when you do that you get to calendar. the whole thing still not a single group anywhere in the program and I think there was one if statement. Right kind of cool. Baby one more time. I say all of this stuff composes really? Well, we seen a

bunch of parts that compose really well with the pipe operator. Everything is pretty much reusable. This stuff works with infinity. I can sew in one side by side right notice. If I change this to a four I get four months side by side and then I'll just works for 5 or whatever. I can make that a command line parameters. I could have people telling me how many months before Matt side-by-side ready to start all that for free. I think the loop the code is correct by Construction. I'm pretty sure this

Bud handles all of boundary cases doesn't have a whole lot of bugs in it. I'm sure if I did the other way, I'd be less confident to say that. So let's look again at the whole solution. But I can hold it in yellow here is stuff that has to do with the problem specific to this problem like formatting a calendar manipulating dates and string manipulation that sort of thing. What's in green is code that is perfectly General and totally reusable junking. interleaving transposing Look at that coat has

anything to do with this particular problem can be reused in other projects. This is how I like to write toad. I like to write code so that as much of the solution is possible is totally General in reusable. So I think we did a pretty good job here with the balance. Half and half Don't know Library developer and that's how I operate. Okay. Yeah question. Different interesting way to I think about problems and thank you for the ideas about that before but I'm going to rephrase it. Look at what

assembly called does this program produce interesting to think about what what kind of food does get optimized out completely and what's actually exact you so nice of you right? Okay, that's actually really good question and dissolution. I did not look at the generated assembly, but for other Solutions I have if you go on my blog Eric ebay.com and you look for a blog post called. Range compositions range in a minute. What what is the feature in a better is like python has no comprehension rains comprehension python has a feature called list comprehensions

Haskell has them to that lets you generate data on the fly in a list in a very concise kind of like they're almost like a sequel like syntax, right? I did. I realize that using a little bit of functional programming magic seasoning similar with ranges and have brains comprehensions very concise syntax for generating the data on the flag reading due to generators. And the the example that I work through in that don't post is generating the infinite list of Pythagorean triples so things for which a squared plus b squared

equals c squared through like all of them as fast as you can. And I programmed it in Haskell and I programmed it in C plus plus using my rings library and the Rings Library totally blew Haskell out of the water. If you can pile with GCC, if you compile with playing the claim code was 17 times slower, then the DCC code and that's because the plane Optimizer Works in a totally different way and mr. Fundamental optimization with caused an enormous of code did not get in line when it should of GCC had the right

optimization and did the right thing so your mileage may vary and it really depends a lot on your compiler and and and how good your compiler Rider team is so I should say that like nothing about what you see here. that should keep a compiler from optimizing the code to Optimal assembly and in gcc's case on that particular example, it was it all optimized away and it was like whooping 5% of like hand coated see with raw loops and go to's enter Okay speaking about performance

and the memory consumption. Could you analyze the results logic in terms of B O notation? How much does it come to your memory how much it's Racing for some kind of performance monitor you have so far as I see you're at a Rangers are completely functional so they have no state but I think there may be some problems analyzing the results of the Joe it's actually quite simple to analyze the the complexity of ranges and Views views in particular because they iterate through

there as you read through the result range if it is adapting an underlying range. It reverses that underlying range just wants as you go through it. So these things composed like, you know, if you are the transform view, right you take a vector you apply a transformation. To each element now if I get a read through the resulting view underlying right? I literally just once you Traverse each element just once so, it's all right. That's my complexity. It's all o n okay looking at this solution the calendar application. I can have it spew out an

infinite my infinitely formatted calendar and I just going to keep stealing and spewing and spilling memory usage for that program going to be constant time. Doesn't grow it allocates as much memory is it needs and then it's just like a loop just keeps going. order one memory usage and you talked you said that week starts with Sunday's usually supposed it starts with Monday. So your program to wait. So that's actually a really easy change to make and let me see all the way back to where we are formatting formatting the weeks and see if I could go all the way, you know, if I had it in front

of me I could just jump there. Who did you do today? What we're looking at for is by week. Where did that go? Okay. You know what this comment right here plus plus a because week number is Monday through Sunday, and we want the Sunday through Saturday. Well, I'm an American I want I want Sunday through Saturday, right? But you are not an American and you don't want a Sunday through Saturday. So you would nuke this + + + nuke that + + and you would get the European calendar instead of the American calendar a good

question. I have a question about the place when we brought this month. We saw was a short amount of these. Could you please settle next flights? Okay. What was the question you keep when you patted with extra extra space? We got it 3-inch. You should be finished here. Yes, you did throw for if we win we run this program for potentially infinite range. We can be certain that this is not an infinite range, right? Because this is a range of dates representing exactly one month

months are finite guaranteed. Both think someone seem longer than others though. Okay. Yeah another question. A single guy simple question about debugging complicated and two-step except Saturday is at The Crush song. Everybody say 655 + 35 radio called a ladybug is conveniently if the counter so I might just Beat It by 4 for the biking session and they are in San Marcos. Well, I don't really have a good answer for that. Certainly, you know, when we the Rings library has its own adapters. Those are implemented using

brains Prasad range adapter arrange facade and range adapter. They have numbers you can set breakpoint on like the current member function would be references with with gets called when you do reps in a traitor the next member function. So you would figure out what operation is causing the crash, you know, is it when I intermittent iterator is it when I do reference the iterator and then you can figure out like what member to set a breakpoint on and try to step through the code that way I'm not going to lie to you stepping through a range hood like this is

an exercise in frustration. If you if you think about like the final solution red, I have this input range and I typed it through all of these adapters and I end up with like this Mongoloid complicated range at the end. I pull out an iterator. This is an iterator that is going to perform at the entire calendar. You can imagine how much could that gets executed when you do reference that iterator or when you increment that iterator its layers and layers and layers. Do you think this is actually going

to be quite hard if you actually need to I think that you're going to spend less time debugging if you write code like this though. It was a good case. Of course, you can buy land as soon as you can file your kids result. I'm sorry. What was the question in there some old-fashioned if I go to a Kijiji? In that case why I found works and I haven't spent a lot of time doing this is to break it up into parts and use printf debugging. Yeah. To continue to allow that for you ask questions how to

tell this called. How to test it I don't know you have and if I will have more complexity composition in the in my work presentation. I don't know how to get it to you have these different elements that you can compose the compose orthogonally chunks. You enter leave you transpose. Okay, you can test Chunk in isolation. You can test transpose in isolation. You can test those two operations together. You can test the entire sequence. You can do some black box testing on this thing and end

right when you have operation pipelines you have these these things that can be tested in isolation in addition to end and you can break the problem up that way test individual play pieces, or is that answering your question? Is this way we should use our test data for every operator players. Yes, you can you can send your data in like end-to-end. You can create new test cases to test just individual pieces. That's how I've done it myself. Okay, baby. Thank you.

Okay, so now I got to get all the way back to the end and see how do I I apologize to make you guys sit through all of this. Okay. The reason standardization you guys might wonder where we are in the process of the Rings Concepts in the range algorithms are already been proposed and are currently working their way through the standardization committee The View adapters the actions and the facade of the adopter helpers haven't been proposed yet. Haven't written the proposals just cuz I don't like time but they absolutely will be

proposed. I'd like to see all of this in the standard. So here's where we are in May. I presented a paper the cursory review of the wording what's going on right now is the detailed wording having regular teleconferences with the committee members about going through the proposal which is 120 pages long going through it line by line. making sure that says what I intended it to say And then in October, hopefully we'll get a TS that's technical specification without initial wording in and we're going to continue refining the wording and at some point.

In a while that's going on. I'll make other Arrangement puzzles for infant ranges range fuse and actions facades doctors that sort of thing. At some point the PS will be approved. That means like we will ship ranges as a separate standard. Ultimately what this is is like a separate version of the standard Library that's going to be in a different name space. So you'll have all of the things that are currently in the standard library in a different name space may be STD to whatever. And at some point that's all to be merged into

cplusplus proper. That's the idea. Okay, here's where you can go to find out more. Here's the actual papers that the committee is working on. Okay, and here's where you can get my rings V3 Library where all of this stuff is implemented in CPAP us 11. Okay. Thank you guys a lot for listening and if you guys have any more questions and I have to take him. You're just like we did, you know what to do with influence the shop and I think if I I can write and search for

humans to shop for without loops and that you statements and that are there any advantages of a NICU or it is kind of feeling sensation in c-bus. What kind of identification it is an awful lot like link and I don't claim to you don't have invented these ideas, you know, certainly there was a lot and stolen from Haskell. There's there's some ideas from from Link in and I think that's a good thing. These ideas have been proven elsewhere and and I'm just not a C sharp guy. So I wanted in C plus plus I don't want to pay for you know, they're managed runtime environment. I want it. I want native

code. I wanted to compile Downs tight tight as small as possible anywhere else. Putt-Putt programmers here, right so. Cool any other questions? I think we're finishing a little early you guys get to hang out and no cool. Thanks a lot guys. buckets at 12:30 and the cops break out starts at at noon. I'm sure no questions. Just keep guys with Haskell in the head and also, yeah, it'll take a while. But I hope you'll be here for next day today and tomorrow yet. So I think any discussion like not here, but after hopefully feel free to ask them.

Thank you again for coming and for the great.

Cackle comments for the website

Buy this talk

Access to the talk “Ranges for the Standard Library at C++ Siberia 2015”
Available
In cart
Free
Free
Free
Free
Free
Free

Доступ ко всем записям докладов мероприятия

Get access to all videos “C++ Siberia, 2015”
Available
In cart
Free
Free
Free
Free
Free
Free
Ticket

Interested in topic “Software development”?

You might be interested in videos from this event

September 28, 2018
Moscow
16
159
app store, apps, development, google play, mobile, soft

Similar talks

Till Schneidereit
Senior Research Engineering Manager, Developer Technologies at Mozilla
+ 1 speaker
Lin Clark
Prinicipal Research Engineer at Mozilla
+ 1 speaker
Available
In cart
Free
Free
Free
Free
Free
Free
Piotr Padlewski
Masters student at University of Warsaw
Available
In cart
Free
Free
Free
Free
Free
Free
Andrew Kelley
Creator at Zig Programming Language
Available
In cart
Free
Free
Free
Free
Free
Free

Buy this video

Video

Access to the talk “Ranges for the Standard Library at C++ Siberia 2015”
Available
In cart
Free
Free
Free
Free
Free
Free

Conference Cast

With ConferenceCast.tv, you get access to our library of the world's best conference talks.

Conference Cast
558 conferences
22058 speakers
8197 hours of content