Scale By The Bay 2019: Umayah Abdennabi, Thank you, next: Iterators

Scale By The Bay 2019: Umayah Abdennabi, Thank you, next: Iterators

Recording: Scale By The Bay 2019: Umayah Abdennabi, Thank you, next: Iterators

[Music] okay I think we should be good so I'm Amaya I work at grammerly I'm a software engineer at on the data platform team where we build internal data analytics platform and I've been there for about three and a half years and I've been interested throughout that time I've been learning about big data systems and functional programming so just a little bit about Graham really we're writing an enhancement tool that helps you write wherever you are on the Internet we're AI powered our goal is to you know improve your life by improving your communication we have four offices our headquarters in San Francisco and about 200 employees worldwide and we have about 20 million daily active users and around 2000 institutions use us through our business and the main idea is that we help you write it's a writing assistant that helps you correct your grammar clarity engagement and delivery and we work everywhere that you write on the internet whether it's on Chrome your mobile app or desktop and office Adhan and here's kind of a trajectory of since our inception of where we're at right now okay so that's gramley and what I do there is I work on a internal data analytics platform that allows our internal stakeholders to run reports on like user interaction with our product whether it's our as you saw we had 20 million users that use different products they go to our websites they download the app they upgrade their accounts and all these different events users are submitting they come to our platform and we do some aggregations and transformations and we allow users to run reports on that data and it's called NAR because we're like shredding the data so the goal of that thing is to support a few things who our users are how they interact with a product and how do they engage in how long they stay stuff like that and allows us to make data-driven decisions and the way it works is we have this incoming data we have this blob of our analytics platform and we generate a report and that analytics platform is built on top of SPARC and that's where kind of like the inspiration of like iterators came from because we're consistently dealing with iterators and sparks like a core abstraction in it and you have to constantly write custom iterators to do what you need to do and inspire this talk so the idea was you know I was I was inspired last year out so I was listening to a talk that you know they talk about key things then you know the essence of things we use on a daily basis that seems simple and you know ariana grande came out with their song thank you next and then I had this idea that iterators are one of those concept where you use on a constant basis but I wanted to deeply understand them and preparing for the talk it was kind of difficult because you have to come up with it's hard to like go through the fluff on the internet cuz it's kind of like a basic concept so there's a lot of stuff that you know you have to go through the fluff and kind of find that information that you know you're looking for and so sometimes you would like search on the internet for keywords and you just throw Haskell or Scala or monad in there even though they have nothing to do with it just to like filter results yeah so what our iterators if we just decomposed the word iterators is you know you have iterate and or and iterate is to perform something repeatedly and the or part is a thing that does something so iterators repeats something repeatedly on something and well that's the term that's used in commonly Oh like you came up with it or teased in a email archive he was saying that the term iterators is not accurate and a term cursor is more accurate and he said that when you use a term of iterators like the term that's used in C++ it's more as that access ER and the iterator itself is not actually doing the iteration it's just being iterated over so it's not an accurate terminology but that's a good analysis but it's it's still used in common day even though it's not accurate so to kind of understand where the iterators came from I kind of look through different white papers and try to understand where they came from and you start around in like you know the end of the 50s and early 60s that's when you know a big time in programming languages and data abstraction that's when they were actually being developed the ideas of iterators of abstraction polymorphism and the idea for as you see IPL this is a excerpt from IPL so IPL in Lisp are some of the oh they're the oldest list processing languages and the idea in I peel they had a thing called generators which as you can see it allows you to iterate do something repeatedly on some sort of list and IPL is like an assembly language so in that language they developed like a generator to do something consistently they saw that they commonly had this need to do something consistently over some data or some collection and IPL took like a more imperative approach and then Lisp is you know has a more functional approach which how they approached iteration and doing something repeatedly and this is an expert from so clue was developed around the 70s and there this is what they call an iterator and they call it as some mechanism which incrementally generating the elements of a collection and Barbara Liskov who was the researcher in data abstraction polymorphism the idea came from looking doing research with other institutions and looking what other like languages like Alfred were doing and they were like impressed with they saw the Alfred approach and they thought it was a little too complicated so they came up with their own form of iterator and their form of iterator is more of a generator which you would be like familiar in Python it's out an object-oriented type of iterator and here's another expert from paper by Stephen watt he also says something similar and this is an expert from essence of iterator patterns and this is I feel like a great example because what Jeremy Gibbons in this paper is trying to do is figure out how to do something that you can accomplish with iterators in a functional way so it's kind of to solve a problem that is commonly done in an imperative world in a functional world and you know programmers we like you just need to look at the type so when you've seen Scala this is what iterator is this is the definition of a iterator and the key idea is next in has neck and that's probably what you guys are familiar with has next and has next as state mutates imperative okay and reading all these papers I saw different classifications of how people would look at iterators one classification is control based first object based control based is kind of the where iterator started with clue and Alfred and different original like older programming languages they started with control based mechanisms for iteration which are having in in the language a form to iterate it's a part of the language is part of the semantics of the language a mechanism to iterate over the data and it maintains the state for you the state machine that's maintained for you and something like this would be a yield and Python generator you saw in clue those are examples of the control based and then object based is you know as data abstraction employee morphism and inheritance were being developed in the 80s and you saw people come up with realize that you can actually do the iteration in the language itself in the libraries of the language not give it as a part a core part of the language instead you have users write libraries to do the iteration and that's where object based iterators come from you encapsulate the idea of iteration in an object and it maintains the state of the object and I'll give you a minimal interface to go over some type of thing whether it's a collection or even an API another thing you see is external versus internal so external is that like an object based iterator generator where you you're controlling the iteration and it's in your hands of one to iterate and one to iterate next and then the internal iterator is similar to a map fold where you're you you're passing something and you you're letting the programming language or the library do the iteration for you you're not doing it yourself manually and the nice thing about internal iteration is that it kind of you know reifies the transformation being done your a function and you know it's gonna be applied to a collection and it it can have cleanup code inside of it you don't have to maintain this like opening files or closing closing certain things it does that for you but again it's not as low-level and gives you the powerfulness that external iterators give you which gives you the ability to like defer the control of the iteration process and then processes later another one is this is actually from kind of like C++ land where traversal guarantees is what are you promising the user of the iterator are you / are you promising just forward going once forward and then the iterator expires after that like a single pass algorithm only needs to iterate over a piece of data a collection once or are you guaranteeing for past multiple times like a single linked list you can pass over it multiple times some algorithms need to pass over a data multiple times or going random access iterators where you need random access so these are iterators developed in c++ it's part of the standard library the template library there where they look at iterators and say what guarantees do we want to give you and state size is one way of looking at it raters is how is the state within the iterator is it a constant state like if you're going over a sequence that's constant state if you're going over a binary tree the state yeah your internal within the iterator is proportional to the depth of the tree so you have state iterators which can have state dynamic state that consistently constantly increases with the size of the collection and you have iterators would have which have constant state they don't need to maintain they mean you only need to maintain one element or even zero if it's like just doing some random number generator and then you have the pool verse pushed and this came about and when they're developing reactive programming or rx and c-sharp the they they said they Eric major saw that you if you look at you have iterators which is a pool based approach you're pulling the data you manually pull the data and get what you want and there's pushing you can what's the opposite of pulling is pushing instead of pulling the data can you push it can it be pushed to you and there's idea that iterators are the dual of observers and the pull is a dual of a push here's the idea that these are the characteristics of you know interval is many it's pulling synchronously the idea of iterator is you know relatively synchronous ting sequential synchronous ting you do have a sync iterators and like c-sharp and other languages and but the idea the main idea is that you're sequentially accessing data one at a time and you're pulling it as you need it whereas the observable kind of switches that says we have you just push the data to it and you have subscribers which subscribe to the data and well one way I thought nice of looking at it is that iterators you know so you start with a value but you end with nothing and the opposite of that is you start with nothing and end with a value and here's kind of that transformation how they came up with that is that if you take this interface and you this is the this by the way this is a Scala you know Java kind of idea of iterator and another way of implementing it is the c-sharp way of iterators it has its pros and cons but one of the pros of this approach here is that the you the mutation and everything is happening in that one operation called move next and then the current is not doing any mutation so you have a kind of a better understanding of where the mutations happen here it's not clear if a mutation is happening in has sex and mutations typically do happen in hasnext but here it's more clear that only one there's only one place where mutation happens but if you take this and you just reduce it to like just like functions you like all this is doing is like all iterator is doing is returning you something of type a and then you take that and you just reverse the arrows to get the dual of it you get the idea of observers in iterators you can see is covariant on type a and when you do the dual of that you get that the observer takes the type a that's contravariant and that's how you and then from that you can make the interface once you take this core idea simplified then you can go back and make the interface of the observer and that's where kind of the idea of observer and iterator were connected through this idea and you can see that and the idea here is that you can do anything you like you could do it erasers you can use observers for observers you can do iterator do leave shoot each other so you could transform one to be used like the other and you could transform the other to be used like the other one and that's kind of a cool feature and depending on what you're working on it's you know good to know that and know the different approaches to dealing with data and I mean you could add effects as needed here if you wanna you know capture the idea the effect of a null value or the effect of exception you would add it here scholar doesn't you do this it's not both for legacy reasons and mainly for legacy reasons also when it was developed probably it was boxing and it's not efficient since then you have specialization which wouldn't make this operation efficient but for legacy reasons you don't want to kind of use try an option or any sort of like monad or encapsulation in the core idea of iterators in Scala the core of idea of iterator is you take it's a unit to a value and you know iterate any shape here's an idea of what either is you would state here's like a tree or ordering over this tree you could iterate over sets and the idea of iterators is you don't care what's there you don't care what's behind it you're just iterating over it you don't care if it's a set a hashmap anything you just want to iterate over it your algorithm only cares to iterate over here's a you don't care if it's a file black box a database a API you just want to iterate over it and it's this idea that it's a consumer your that you have a consumer and this iterator is this you know barrier blocking you from knowing what's going on inside and you know if everything goes smoothly everything should operate as planned but you know you don't want to break this idea you don't want to do stuff that is not guaranteed by the iterator or promise things that the iterator doesn't guarantee you want to keep the iterator interface minimal as possible next has next if you try to break this and do stuff that or promise things that isn't guaranteed you start to have problems that's the problem with ik you know iterators that they offer you a lot of power but they have state they're mute they're mutating and they're kind of ugly to deal with in the real world you could have a lot of problems for example if you have this example where you do some asynchronous computation and you wrap it in or await that result you know if someone's using this iterator they'll be all I know is I could use this iterator and get data or what if they call next to get data next time they call next they have to wait then they have to wait and then they have to wait and they don't know this from the you know API well this is Picasso and he was his on the left-hand side is his when he was 15 years old 25 years old and then his 89 years old his different ideas of a portrait here's another example with iterators there's no guarantee about how do you close resources who handles the resources that you're opening there you could have closeable iterators but that still is not clear of where does that closing happen and iterators are used everywhere databases you know the query plan which is and you know if sparks equals based off of the vote you know they were inspired by the volcano model which was that if you model a sequel query as a you know a set of operations you know select scan filter you can like combine those operations with a iterated iterator like interface and you can like go over these algebra of this with it open next you know going through the operations like an iterator this isn't used in the real world like when a spark sequel when you use data frames or actual databases you know they actually don't do this iterator model because it's not efficient you have vectorization and code generation so but the idea is still there like even when you're making your own query plans you or expressions you still kind of use the idea but then you optimize it later it's core abstraction and like spark when you're dealing with spark you kind of at the core of it is this iterator model also with Kafka you know Cassandra when you're reading data when you're doing certain things you're given an iterator and you're using an iterator API which is kind of with the example I gave of having await that result sometimes that's not sometimes you have to be forced to do something where you're dealing with an asynchronous source and a synchronous API or you have to do something ugly sometimes SPARC makes you do some ugly stuff with that that you want to map a partition you're given an iterator you're not given some asynchronous thing and you know programming languages every Perl has a write different idea of what iterator is this is the API of you know Scala they read in 213 they revamped it they got rid of the traversable and they made a simple with iterable ones and every interval once outputs the iterator and it underlines the collection library in scala so every basically all scala collections are internally using iterators if you look at the api if you go through the library iterators are used everywhere in scala collections for example all these operations filter and flatmap flan are used in internally if you look at the operation they're using iterators to do the operations all collections give a iterator use iterators internally there there are exceptions like lazy lists who which do not but the vast majority are using iterators internally one thing nice about iterators is that they compose and they are composable but they also fuse operators which isn't what you get with normal mute Scala collections Scala collections while they use iterators internally every time you do a map that outputs a new iterator then you do it again it outputs a new iterator and instead of doing this operation multiple times whether as iterator your you know form you're morphing the transformations together your compote you're fusing the operations together because you're operating one element at a time so you're you can use it one at a time you can get this functionality if you do you know seek that view or seek that iterator you'll get that functionality but at the core collections you know purposefully don't do this they don't fuse operations and that's on that design was purposeful for example here's the iterator you map he's going to return another abstract iterator in the user abstract iterator as a you know a stub method so that you don't have this like huge class files but the idea is you map create an iterator and then you do map again and it'll just wrap the previous/next and you create that and you just keep doing it fusing these operators scholar iterators flexible efficient sequential same thread and in grammerly we use iterators all over the place we have is last iterator do something on the last element Kinesis shard iterator we use Kinesis and kind of like a asynchronous synchronous way where we have to prefetch data and then serve it to we're feeding it to spark so that's where the kind of we have to force it to be synchronous because we're doing some batch processing where we need the Kinesis api but we want to feed it to spark in a batch like math matter show that later if I have time merging tuple query iterators you know we have internally we have different types of iterators for our queries like or for we like embed an algorithm inside that iterator and interest continue it arrays are just basic container let's say you have you want to generate 0 or more values you can use the iterator you know you just want a base minimum API little time left let me quickly so functionally they came up with ideas of iterators you have it arati the idea is that you're fondling data kind of like a plumbing example used by Oh like we develop the idea of a dirty and you are you're able to have this iterative numerator numerator generated objects in a dirty is like the stateful this are you know no state it's immutable thing that takes this data stream and does some operations over so that's kind of ways we in the functional world you want to do these abstractions you want to do iteration but you think about it differently you would do in a different fashion here's an idea of how it works like share this later and you have applicative functors which was developed by a sense of iterator pala pattern where the implicit of functor the traverse operation kind of encapsulates this idea of iterators you can see here this tree and its composable its you can compose different and you can do both accumulating and mutating behavior and the idea is that iterators have this idea of you know accumulating and mapping how do you do that in the functional world you can use applicative functors they solved that issue and this was actually recently I mean it's not recently in the 2000s that 10 10 11 years ago this CAI Diaz came about you know for like 40 years we've been using this like stateful imperative way and then here comes more functional approaches in the future there'll be more and more ideas of iteration but basically the idea is iterators are a fundamental constant in programming and they solve issues but you could anywhere you can use iterators you don't have to use them you can use a functional approach that's the core here the idea is that you don't need them either nice to use but there's also functional approaches to it there's different if you change the way you view it the problem you can solve it in a different way and we're running out of time so I want to show some code examples well maybe if anyone has wants to see it I can show you later and gramley were hiring here but I wanted to show hopefully I can do okay so here I wanted to just show the you know start with the iterator interface not working here probably show that for whoever is interested but that should be it any questions much do we have any questions oh thank you for a great talk oh my it's great to have Graham early for the first time presenting we all know this as a product so it's exciting to see there is skull inside of it I just wonder how we found that NOP people like Scala a lot of research and development is done on it so I wonder if there is something about that we're appealing the language human language geeks and programming language geeks how is it evolving inside grammar like Anna tell us a little bit about like how adoption happens is I think people pick up is it something which is kind of coming from the top how does the culture enable kind of interesting programming language learning and education and adoption so if you're talking about programming language and grammar early so a lot of so we're very functional we love functional programming and grammerly multiple team of you Scala but also multiple teams use a closure and Lisp and we try also interesting job reactive programming in like you know when you're doing reactive and also in JavaScript we have functional like we build functional libraries in a functional manner in our front-end extension with JavaScript and kind of we find try we it's kind of ingrained in the culture to use these higher level abstractions in programming to make a better product we've noticed it makes the product better it makes lives of engineering engineers better and it offers you know engineers nice something that they're interested in doing you don't want to use like be stuck with this imperative world hi this might not be directly related to it but have you considered applying the principles of machine learning etc to help programmers write better code as well as sense of iterator you talk the essence of iterator printer I'm sorry which one were you talking about Oh Cuba Pete I mean grammarly helps with grammar and word choice and stuff syntactic you know help like that I was wondering can that be applied to writing programming language programs um that's uh so it I think so the idea of it's more I think that probably the I don't think they're Coralie like the ideas behind you know the natural language and programming languages are kind of far apart so I don't they can't really be applied in the programming sense [Music]