Hi. Okay. I'm Monk. And I'm Stoker. And we're going to babble about off-grid communications with Android. So there's us. Two e‑mail addresses for both of us. One is corporate. One is not. Depending on your question or which one to talk about, pick which one to e‑mail us. We both work at MITRE. It's a FFRDC funded to do R and D along with quite a few other things. You probably know us because we do CVE but we don't actually have anything to do with that. Too long didn't read. We're dropping source. It went up around midnight last night. So if you get bored and want to walk out, if I babble too much, which I tend to do, sources up, grab it and have fun. That's really what we're here to do is evangelize Mesh. So I start babbling. First off, there's a lot of people that have played with Mesh over the years. We will mention some of them if you do Mesh and we do not mention you. Please don't get pissed off at me. E‑mail me instead and let me know. It's something that people play with and then they give up and then they play with and then they give up and we try to catalog some of the work that's been done but there's a lot out there of half baked projects, full projects we don't know about. Let us know. We really just want to collaborate. If all you're doing is Wi‑Fi tether, awesome but please don't e‑mail me. It's a little boring. Sorry. So the first problem that we really want to end assault with Mesh is what happens in situations like this. Fukushima, horrible disaster, cell networks went down, Wi‑Fi went down. There was a lot of people that wanted to call their family and just say, hey, I'm okay. Or people that needed emergency help and networks went down. They're basically stuck back in the dark ages. Happened in Katrina, happened in Haiti. Put any recent natural disaster you can think of. Cell networks go down. The towers are designed to handle about an 80% capacity. They go above that and the hardware dies. I mean, it's just what happens. There are other times where networks go down that this is also kind of meant to combat. So why do I care about Mesh?  I think it's flawed in something we used to have to have. I really don't think we do anymore. As technology progresses, just we don't need single points of failure. They're hopefully becoming obsolete if we get our point across today. Cell networks die. I've kind of already mentioned that.  Plus to get a Wi‑Fi network in a remote area, which you've got to have power, you've got to have Internet. All that just to send an SMS between two people is really not necessary. Having said that, with the Mesh that we're dropping today, if you do want to hook up to another network, Internet, whatnot, we can bridge between them. But the main point of the Mesh that we're doing is to be a headless, infrastructureless paradigm. So again, single point of failure.  I think they're dumb. They're also kind of a single point for sniffing, single point for filtering. Also not really great things. We don't like that. I don't trust someone else being able to basically jack into that single point. So I don't want to have it. There should really be a funny pick below. But I cleared my phone out before I came to DEF CON of all personal information and lost it. But it's a story we'll talk about later. But we actually got flagged as terrorists when we were doing a demo earlier this year that was kind of funny. It's basically a skinny guy in a tree and me in a tree climbing up duct taping phones to trees. Stick around to hear the story. You can imagine how close a phone duct tape to a tree looks like a bomb. Especially with like two battery packs jacked onto it. So I mean, I've been trying to evangelize this for a while. We've all got smartphones and they're pretty cool. Except for the people that are really smart and have flip phones at DEF CON. Y'all guys rock. But I mean, they've got a Wi-Fi chip. They've got basically dual processor. Tons of sensors which I'll babble about later again. Lots of memory and power. And the most boring thing on the smartphone to me is that screen that blinks. I don't know. Once you get to the blinky screen you're writing apps which is awesome but boring. So I'm going to hand it over to Stoker because I've babbled for a while. But basically we've done the boring part of coding all the framework and he's going to go over that. And then I'll come back and babble some more. All right. So I'm Stoker. Before I jump in I just want to say this is my first DEF CON. And it's also my first time speaking at DEF CON. So if anything goes wrong with this presentation, blame the noob. All right. So Monk gave the overview. I will go deep. I am a software engineer by design. And here we have our technical architecture. So in general we're running a span on top of Android. On Android devices. Started with Android you want to eventually branch out to iOS. Windows 8, Symbian, what have you. At the top here you see we've got various apps. You've got a Blinky on a map which many government organizations like they have a lot of maps and a lot of things on maps. You can run like a peer-to-peer chat app, another app like VOIP. And all of those speak IP. So we use the standard Java networking interface on Android. You can speak TCP or UDP. And what happens is using net filter on the device because we've got root. We can actually redirect all those packets to a transparent proxy we have running on the device. And then we can inspect them, take them apart, add things, do whatever we want. The cool thing about this is whatever app you have running, it doesn't need to be programmed against a specific mobile ad hoc network API. It just works transparently. You don't need to change your app whatsoever. And when we went out to Kansas City to test this stuff, we used a government app we won't speak about but it did work. And they didn't need to make any modifications. So what happens is our transparent proxy intercepts these packets and we route them to a Android service, which we call the reliable transmission layer, which takes care of security, encrypts the data, does a public-private key encryption, and manages a TCP session if you want a persistent connection which is kind of something you don't get over an ad hoc network. So there's a lot of trickery involved in doing that right that we're going to be investigating in the future. The thing about our service is the main thing it does is routes the data. So one of our primary concerns with this research is how do you route data reliably in an ad hoc network when devices enter and leave at will? The thing about an ad hoc network is you basically route the data through phones to get to your destination. So if you route it through three phones, then one of those phones in the middle drops out, you've got to replan your route on the fly. So later on in this talk we'll talk about routing protocols and what they are and the good ones and the bad ones and how to make them better. So that's the gist here. There are two kinds of routing protocols we'll get into and our goal is to develop this framework to support any number of routing protocols as long as you implement them to work with our API. So under the hood there's plug and play, change at will. So here's the data flow. You've got one app on one device, let's call it a chat app and another app on another device, also a chat app. Data that goes through the Java networking interface, you know, you've got your TCP, UDP socket, whatever, intercepted transparent proxy, goes to a reliable transmission layer. We route it using our protocol and then it goes back up to the transparent proxy and gets sent over to another device because I call this transparent proxy because the user doesn't even know it's running and the app using it doesn't even know it's there. And the idea is because the data goes through these transparent proxies, it can kind of be called like a virtual VPN or it's something that the app doesn't know about in that sense. So it's just a data pipe which we think is really cool. So any app you have running on your smartphone can run over the man-a. And won't know. So ad hoc mode, this was the biggest trick. These smart phones by design are intended to stay in what's called managed mode which is what they use to connect to an access point. You can imagine that the vendors and carriers don't really want you to put your phone in a mode that allows you to speak directly to another phone because then you don't have to send it over their data network. And that's why there's a lot of controversy around like Wi-Fi tethering. Essentially, we took Harold Moeller's Wi-Fi tether for root user's app, took it apart and used it as the basis for what we have. So thank you, Harold, if you're listening or will ever look at a DEF CON presentation. So what we needed to do is we looked at Harold's stuff. And what he has there is an edify script for putting the phone in ad hoc mode to do Wi-Fi tethering. An edify script is basically used on Android to do like over-the-air updates. So we take the same approach just to sending the phone in ad hoc mode because you could do some cool things inside the script they can't really do from a typical Android app. Harold eventually stopped putting phones in ad hoc mode to do Wi-Fi tether. He started using something called soft AP which allows your phone to act like an access point. That does not work for Wi-Fi. It does not work for the mesh network because the phones actually have to be in ad hoc mode and that is access point. So what we needed to do with some of the phones, specifically the Galaxy Nexus, is recompile the kernel with wireless extension support. So thankfully, most of these, most vendors open source their stuff so that we can recompile it. You know, using typical Linux means, using menu config, selecting the things you want in it. And then we dumped the Z image in the any kernel tree so thanks to the guy for developing any kernel. And from there we flashed the resulting image using clockwork mod recovery. So this is all stuff any Android hacker knows about. What we do want to say is that we love Broadcom. The Broadcom Wi-Fi chipsets are awesome, we think. They work really well for our needs. Have them in Android phones, have them in iOS, have them in Windows phones. That's why we think that eventually we can get this working on a variety of different devices. So here on the left we have a number of devices and they're on the right, the wireless chip. As you can tell, typically a Broadcom, BCM, 4.3, something, something. Tends to work really well. Right here we got an ASUS e-pad transformer. It's running the Azure Wave wireless chip which is actually just a rebranded Broadcom chip. So that works well for us. The thing we don't like in this list is the Motorola Razr Max which uses a Texas Instruments wireless chip. And we tried hacking at that for a while but for the sake of time we kind of gave up. So we currently don't support Motorola devices. Once we got the right chip we need to make sure it has wireless extensions support. So then we can use IW config to set it in ad hoc mode. Galaxy Nexus doesn't have it. That's why we had to compile it in the kernel. The e-pad didn't have it. We had to compile it in the kernel. But the Galaxy S2 did and the Nexus S4G did. So that was awesome. So just a little note to the vendors, you know, please leave wireless extension support in your stuff or provide your kernel source to communities and we can add it back in. I would appreciate that. All right. So here was an interesting pitfall I ran into. When you have an ad hoc network you're constantly broadcasting, hey, I'm alive.  I can send info to him and I can add him to my mesh and I can route through him. So your device is always on. It's always sending out these hello messages. And that's really the core of a mesh network. Problem is we're doing this over UDP because we don't want to do the whole SINAC thing with TCP and that just eats up more bandwidth and it's not a reliable network so it doesn't make sense. Problem with the UDP on Android, ICS devices, and lower is that if the screen is off it can't receive UDP. Why? I don't know except that we think it's because they wanted to save battery life. So somewhere down in the Wi-Fi driver level they're actually filtering out UDP messages when the screen is off. So it's the first thing we wanted to do. We'll force the screen to always be on. That makes a lot of sense. It's up a lot of battery but we'll strap on a big, fat battery pack to the back and move forward. All right. So we actually got it to the point where you could press the power button and the screen would come right back on. Which is kind of a cool little hack and we did it using a wake lock and an intent filter listening for the action screen off intent. And it seemed to work pretty well but when we were in Kansas City we realized that the phones would go dead pretty quick and there has to be a better way, right? So second approach. You can actually set this flag so that the Wi-Fi kernel doesn't do that filtering anymore. Which is awesome. I'm glad I eventually found this but I wish I found it like three days earlier. So you can sometimes set this flag when you're actually using InzMod to load the kernel. Some kernels don't have this flag setable via the command line. So you got to actually recompile the driver. So we recompiled the driver. And I'll pass this slide off to Monk. Awesome. So now we basically have the devices ready to go into ad hoc mode. They're in ad hoc mode. We should be able to actually create a network. Okay problem solved. Now routing packets and fast moving dynamic devices. That's painful. We'll babble a little bit more about this now. Basically we wrote, we are going to talk about two open source projects that are doing ad hoc routing and then our headaches with writing another five or so. And where we are. Yeah. So this slide should really not be needed. But if you're asking why you need a network and why you need a routing protocol, there's your list. And please don't e-mail me. All right. So ad hoc network routing. What is it? How does it happen? What are these things called Batman and OLSR? Let's get into it a little bit. All right. So this is a node graph. Basically each node is a phone. They can talk to each other. If there is an arrow between nodes, it means data can be sent from example D to A, but not A to D. Because these links between these phones are always symmetric. Sometimes there's interference or sometimes one phone transmits data at a higher power level than another phone. So you've got to manage all of this in your mesh and it affects your routing algorithm. In the middle, we show a one-hop route, A to B. And on the right we show a two-hop route, A to B to D. And you can keep chaining these nodes together to expand the range of your network. You just keep sending data through relay points. Specifically, we tested it and two Android phones, say a Galaxy Nexus to a Galaxy Nexus, you can send information over the span of about 150 to 200 feet. And we bumped up the transmission power to 32 DBMs which is the most they can support. We're actually thinking about taking off the back panel and hooking up a patch antenna to see if it can get more range. Essentially, these things are turning into little tiny push-and-talk radios, which is kind of what we want. So OLSR, what is this? Optimized link state routing protocol. This is the most popular ad hoc routing protocol to date. It's built into a lot of router firmware directly. So if we're using OLSR and smartphones and your router supports it, such as DDWRT, you can just add that router to the mesh. Which is nice. It's actually an RFC. It has a lot of support. It's been out for a while. It's not the best, we think, and we'll go into why. It's a link state protocol which means that the nodes know who they can talk to. They know the edges in the network, but they don't know, like if Monk had a phone, I don't know what routes he is using. I only know the routes I'm using. I only know that I can talk to Monk. And the problem with this is that each node has to calculate a route to every other node in the mesh. If there's tons of nodes in the mesh, you're going to spend a lot of time turning on that data. It's proactive. And this is one of the most important things in an ad hoc network. It's proactive versus a reactive network. Proactive is where you plan your routes in advance. So when you send data, the route is there, you blast it off. Reactive is, I don't know when anybody else exists until I want to send data. I'm lazy. So I want to send data. I plan my route on the fly. Data kind of gets buffered up for a while. It's a little bit laggy. And then we can send it out once we plan that route. But OLSR is proactive. People like it because when they need to send data, the route is there. It uses Dykstra's open shortest path first algorithm for people that remember their comp sigh. And it works at the networking layer. Some algorithms work at the one layer lower than that. All right. So kind of how do you figure out that your neighbor exists? Well, A constantly broadcasts out hello messages at like five second intervals, which is very quick and you can understand it burns a lot of power. B is eventually going to say, oh, I got a hello message from A. And then B is going to send a hello message of its own and A is going to get it. But in B's hello message, it's going to say, it's going to list all of the nodes that it knows about. So A sends to B. B learns that A exists. B sends back to A. And in that message, B had told A that B knows about A. And then A says, oh, okay, cool. B exists and B knows about me. Let's form a symmetric link. A knows about B. B knows about A. They're best friends forever. So that was like a one hop link. But you can also like do two hop links where A sends to B. B sends to C. And then C knows that through B, it can talk to A. Because B basically rebroadcasts A's message. And so through this series of proliferating broadcasts, everybody knows that everybody exists. You can understand there's a lot of data on the network. You can run into throughput problems, which is why a reactor protocol might be a little bit better. There's also a thing called a multipoint relay in OLSR, which is like you choose one of your neighbors to send all your data to and he sends it to everybody else. Sounds good in theory because now that one guy takes care of most of the work and if he's plugged into the wall, he has a limited battery. He has a limited power. He can take care of most of the heavy lifting. Problem isn't that ad hoc mesh network with smartphones is that guy can drop out. So if you assign a guy to be your oracle or whatever and you send him all your data and he drops out, well now you've got to find another one.  That's why we don't really like the idea of multipoint relays. What these bullets on this slide are saying is you choose your multipoint relay based on the node you send data through to get to your most two hop neighbors. So C and D in this are the two hop neighbors of A. B talks to both C and D. So A chooses B as its NPR. Wow, I wonder what's happening over there. Okay. OLSR. Pros. Not everybody shares everything. Most of the topology jumps, most of the information about the network is only shared between the NPRs and that's kind of the reason they came up with them is to try and reduce the amount of data dumps of topology which are quite large. And there's been incremental improvements but NPRs are choke points and even though each node plans an entire route in advance, it knows all the hops it needs to go through to get to its destination. When you send that data to the next step in the route, that next guy, he can do whatever he wants with it. He can use a completely different route. So why would you plan your whole route when as soon as I pass it off to Monk, he plans a whole new different route? It gives you warm fuzzy knowing you can get data from point A to point B but after you send it to the intermediary step, you don't really know where it goes. You don't know how it gets there. So Batman. Batman is in advance to OLSR and it was designed by the same guys behind OLSR, came out in 2006. No single point has all the data, no NPRs. Each node still sends out messages, hey, I exist but what's cool about this is that you keep track, so if I send out a broadcast and that hops through multiple nodes, the node that eventually gets it knows how many hops that broadcast had to go through before it received it. So if A sends out a broadcast and I get A's message and A went through 20 hops and A sends out a message and I get that broadcast through a different means, through only 10 hops, I know the best route to use, the one that only took 10 hops and not 20. And I know the last guy who sent me that message so I can blast the data off in his direction so that he takes care of it. So I can blast it off in the direction of the 10 hops instead of the 20 hops because that makes a lot more sense. It's going to get there a lot quicker. So in that sense, you kind of have a very local scope, you don't have to do as much data churning at all. And basically I just said what's on the slide. So where are we today? OLSR is the most popular Batman's gaining traction. We'd like to add you to Batman a lot more but we can do better and so can you. And I'll pass it off to Monk. Yes, so if you want to work on writing protocols with us, because you see flaws in these, please, please, please email me. I think I get to babble about reactor now. Oh yeah, okay. So thinking inside the phone, blah, blah, blah. Smartphones have sensors. We should really use them. Both of the protocols that Jeff talked about, they burn battery like crazy. I hate it. They're also not optimized for the actual platform. So the first thing that we should be doing with writing protocols is the phone itself knows when it's charged. It knows how much battery it has. It would be kind of awesome if the network itself routed around that data. So if I'm plugged into a wall and charging, you know, route through me. It's not like you're going to burn my battery down. If I've got 10% left, please maybe find another route. GPS. GPS is really costly to hit. Assisted GPS is quite a bit cheaper. But it at least lets you start clustering devices. So you know, don't pick routes that just kind of go around in a circle. Try to optimally figure out where your phone is and where two or three other phones are. If you're physically trying to send data from point A to point B, you know, look along that line. And the accelerometer. So GPS is expensive, expensive, expensive to hit as far as battery. Accelerometer is damn near free. And you can get all your vector information out of it. You can get speed. The other bonus of speed if you're looking at routing protocols is if I'm moving fast through an area, don't route through me. That's dumb. Don't build a routing table around me being there. I'm not going to be there. So then on the flip side, if I'm sitting still, maybe prioritize me in your routing tables. So reactive. I love these things. Don't really keep a routing table. There's no reason to map out the network beforehand. I mean, why? We're talking about highly mobile devices, highly dynamically changing topologies. There's just not much point if you're actually doing phones in people's pockets. If you're doing phones taped to batteries, duct taped to trees, then yeah, by all means. But we're moving around. Our protocol should really be cool with that. So once we get into reactive, then we can start looking at the sensors on the phone. We can start playing with motion. We can start playing with location. And start adding these in to actually optimize how the data is moving through the network. We can basically power level the whole network so you're not burning one person's battery a whole lot more than someone else. Which is kind of cool. So downside comes with throughput. We can, every time you want to send a packet, basically you have to build a route to that packet. Which you know, a route from point A to point B. Which means that throughput, at least for initial handshakes and whatnot, is considerably slower. Okay. So delay tolerance, which is really, really, really what I love. There's a lot of times that we are doing network communications where we don't need real-time data flows.  But I actually looked at this RFC, which I love. And you can look it up if you don't recognize the number. It was an April Fools one that I actually thought was really cool. Basically taking phones and saying I want to get a packet to someone else that I'm not connected to on the mesh. But I know a lot of phones. And so let me send my packet to those phones. And when those phones move around the environment, they will hit another phone. That phone will hit another phone. And finally your data will get from point A to point B, even though there's no network connection in between. It's using humans as carrier pigeons, which is fun but really, really laggy, obviously. But it does expand the scope of your network when you don't have one. It also adds some interesting things that we'll get to at the end. Okay. Scale, most of the projects that we've talked about already, Batman does a lot better. OLSR, if you're dealing with the physical products that are being sold on the market right now that support OLSR, they actually scale really, really well. The Android and iPhone implementations that we've seen don't, what we've seen like 20 to 40, we hooked up 40 phones. But I think the limit that we've talked to anyone is about 200. It's not really useful. I'd like to see the thousands or the tens of thousands. We should be able to get there but I don't think we can get there with what's on the shelf right now, which is why we've been spending a lot of time on this. We should be able to scale a lot more with Reactive. And if we mix the two, we should really be able to scale with no foreseeable limit. So that's all you. Okay. So you have your mesh. Phones can talk peer to peer but maybe you want to use the internet or maybe you want to bridge to a larger network. Well, this is really important for an application that we tested out which had a central server. In a mesh network, you kind of want to avoid servers or any phones acting as a server because if they drop out, well, then that service is gone. Or you want to try to make it redundant. That's my aside. So what we have is some managed infrastructure. And we want to get the phones talking to devices on that managed infrastructure. And how did we do it? Well, all right, well, this is going to be a shameless plug for alpha. But this is a wireless USB dongle that we have hooked to the USB port of this ASUS transformer prime. And what that does, it provides the prime with a second network adapter. So it has its internal Wi-Fi and it has an external Wi-Fi now. It uses its internal one to talk to an access point. And it's using the external one to talk to phones on the MAN-A, like this guy. This is the Galaxy Nexus. So because we have two network adapters on two different networks, we can bridge them. And basically, we just use IP forwarding between them. And all data that comes in to the ASUS over the mesh can now be sent out through the alpha wireless USB dongle. And the mesh is netted behind the routing done on the ASUS. So essentially, you can kind of think of this like a VPN where, all right, ASUS is a gateway to the rest of the world. We have cluster of phones. We have a mesh hidden behind the ASUS. It's netted. Well, let's say we have another ASUS in another state. Can we get the mesh on this ASUS talking to the phones in the mesh on the other ASUS? Yeah. Well, because the internet connects them both. So both ASUS's are bridging to the internet. The internet is basically our backhaul to send all that information from one ad hoc network to another. All right. So IP address assignment. Mesh networks, there's still a lot of open questions. And we would appreciate it if anybody here is an expert in this field and has some recommendations. There's a lot of white papers, a lot of college grads looking into this stuff. But IP address assignment, how does it happen on a managed network? Oh, DHCP. What is DHCP? It's a server. We don't like servers on an ad hoc network. So how do we send out IPs? Well, you can do it statically, which is going to work. But what if two phones assign themselves the same IP? Well, then you run into all sorts of problems. Can we generate a unique IP based on the phone MAC address, IMEI, other sorts of information unique to the phone? That's an option. So this is still like an open question. And right now we do it statically, but in the future, especially next year, we're going to be looking to alternative means. One thing I do want to say here is, if you get to the last slide, there's this mesh network in Germany called Fryfunk. And they do IP address assignment by having people register on their web page and then they just give you an IP. So we kind of want to avoid doing that. All right. Security. How can you secure the mesh network? Well, this is still an open question. And we're still looking at best ways to do it. But one of the ideas we had is, well, maybe we can exchange, you know, a symmetric key by doing a bump and using NFC. So let's say it's a crisis situation. Cell towers are down. There's an earthquake whatever. Volunteers show up to the Red Cross. They have their personal smartphones. And they want to set up their own mesh network to stay in communication with each other because the Red Cross guys aren't going to give them radio. They don't have enough radios. So let's say I'm in the mesh and Monk wants to get in the mesh. How does he configure his phone to get into my mesh? Well, let's do a bump. Send that config file over to his phone. He knows the symmetric key. He knows the SSID. He knows the IP range. He knows all that stuff that's in the config file. He hits go ad hack and he's in. We like it to be that easy. We're also thinking instead of using a symmetric key, we can use public private keys and do encryption that way. And we'd also like to encrypt the data in such a way that the backhaul, the internet, or the bounce nodes that we're sending information through can't decrypt and inspect the data. So this is an off-grid network. Only devices in the mesh can look at this information. All right. So we talked about exchanging stuff via NFC. We can do symmetric encryption using the free helming key exchanges, but then again, there's still a lot of overhead with doing that every time. We want to talk to a new peer. I still like the idea of the public private key pair. The thing is we don't want to use a certificate authority or third party to try and manage distribution of the keys because we're in a mesh and you might not have access to one and that's just additional overhead.  They're in Australia. I don't know where that is from here. But they have really looked at a lot of these tough questions and we have some links at the end of the slide. I don't know if we'll get to. But Serval has come up with a solution where they basically take a 256-bit public key and they generate it and that becomes your IP address. And that IP address is basically intrinsically distributed over the network because that's what networks do.  People know who's on there. And if you get a hello message, you can basically inspect the header, say, oh, I got it from this IP, that's his public key. Now if I ever want to communicate with that guy, I use that to the public private encryption. He uses something called CryptoBox to do the encryption. And he also uses something called CryptoSign so that people can sign the broadcast traffic. Basically, I guess CryptoSign is a way to use some handwritten gesture or something on the device to prove that it truly is you who is sending this traffic. So that's how they sign the broadcasts. So then some guy who just realizes there's a mesh network set up can't just send his own broadcasts and try to get on the mesh. We want to talk about a new features in ICS. Apparently Ice Cream Sandwich has this android.net.wifi.peer-to-peer API. And it's like, oh cool, it seems like something we can use for an ad hoc mesh network. And it's supposed to be an implementation of Wi-Fi Direct, if any of you guys are familiar with that. Essentially Wi-Fi Direct is supposed to bring this internet of things or even your toaster can be in your mesh. To the present day, they're trying to get everything to be on the internet and everything communicating wirelessly. And that's kind of what Wi-Fi Direct is all about. And apparently these devices have a Wi-Fi chip that will support it. It's just the driver implementation or something else is locking out all the features. So it's kind of a lame, partial implementation of the spec. It didn't really work for us. It kind of works like Bluetooth pairing where one guy has to be like in discovery mode and basically it's a very manual process of saying, oh well, I have to be discoverable and Monk notices that I'm available to talk to and then he has to click me on a list so then we can establish a link. It's cool for sharing video and whatnot, but it's very manual, not good for an ad hoc network where you want everything to happen behind the scenes. Maybe this will change in Jellybean. I haven't really looked into it very much. I think it's going to be a few more iterations beyond that to implement the full spec if they choose to do so. Okay. So root is required. We have open source this stuff, but it's not going to work unless you have roots. Your phone sports wi-fi or wireless extensions, those are like the two prerequisites to getting this stuff working on your phone. Why do we need root? Well, because we modify IP tables so we can redirect packets to our proxy and we do things at the low-level Linux networking layer to modify the routing tables which also requires root access. You also need root to put the wi-fi chip in ad hoc mode for managed mode. So maybe to make this more palatable to people who aren't like we are that don't do hacking in their spare time, we could try to wrap like an exploit up in the installer script that will get root whenever needed. Yeah, there's a lot of issues with that, but it was an idea. It worked. So like for an over-the-air installer or something, you need to provide a way to get root on the fly dynamically. And once we did whatever we needed to do as root, we could drop out of it, but there's a lot of trust issues there. So we've talked about Android. I'll chat pretty quickly about the iPhone. Short answer is yes. Black Berry Y. We poked at it. I kind of jumped on the playbook because it was QNX and that's kind of sexy. And maybe, but Black Berry is just kind of mean. The Windows phone, it seems to work, at least the OLSR portion because it's Windows phone. It runs Windows software. It was kind of like download from the Internet and install. Arduino and gumsticks, both yes. The gumsticks are really fun to add to the mesh. Any box you're carrying in your bag will pretty much jump on the mesh right now, today. And your toaster, I guess, if it's running Linux, sure. Basically anything that runs Java or C and has a, I guess I should also specify, has a network or a Wi-Fi card we can get on the mesh. Yeah. So iOS tends to be way more locked down than Android and it's fun that way. But they also gave us these really cool Wi-Fi proxy stuff. Basically in the iPhone configuration utility. So the main issue that we talked about earlier was trying to route all of the data that like any app, Facebook, Twitter, what not, are trying to actually push through the phone and grab that and say, you know, push through us instead. Android we do it by injecting the proxy at that low layer. iOS we can basically just force the phone to say, hey, use your internal proxy. So it's oddly easier because we can just pretty much hard code the APN and Wi-Fi proxy to just point back to a different point on the phone. And we can do it all through this awesome tool that Apple gave us. So there's like no coding involved, which is really, really, really, really, really easy. And this is actually set up to deploy to multiple phones so you can set it up once and then push to like 100,000 phones, whatever. We don't have that many. So what else is the mesh for? This coming year we're playing with security and the other thing that I really, really am looking forward to is pushing the torrent protocol over the mesh. So let's say you're in a situation where you actually want to share data across all the phones, but you're not always guaranteed to get all the phones back to wherever you came from. If you use torrent, you can basically replicate all the data across the whole mesh network and use the mesh kind of as a RAID 5. At which point, let's say you deploy 200 phones and you get 50 of them back. You haven't actually lost any data that you collected out in the field or at an event or wherever you actually had the mesh living and breathing. And I kind of, I mean, the typical network doesn't really use all 100 percent of the bandwidth. So and smartphones have a ton of storage so we can pretty much utilize that. We've also played a little bit with actually doing multi-processing over the mesh, which is kind of cool, spinning threads off on different nodes. Played in enough to know that it's possible, but haven't really poked past then. So we have a demo running. I jumped the gun, but we have like three phones and they're all talking and mesh together, which is a lot of fun. Let's see if I can get some screen sharing actions so those weren't in the front row can actually see what we're doing. All right. Okay. So using the processing visualization engine, we are actually showing you now the three nodes in our mesh. This ASIS and two Galaxy Nexus phones, the blue dot represents the ASIS because that's what we're doing screen sharing from and you can see that there's a line between each pair of nodes, meaning there's symmetric link between them all. Not very exciting right now, but proves to you that we can do this.  You can see they all have an IP and really that's about it at this point in time. It's and go back to the presentation here. It went back to the beginning. So let's get some scrolling action here. What? All right.  These are going to be up here at the end if you want to take a closer look at the app itself.  We have really appreciate that. All right. So what else is out there? We talked about Serval. We talked about Fryfunk. Let's give you a little bit more information on what those guys are. We would like to do some collaboration in the future, if that's possible. So Fryfunk, these are the guys we can register for an IP on their website. It stands for German for free radio. As you can read, it's like a grassroots initiative to get open radio networks in Germany. They use specialized open WRT firmware to get OLSR and Batman running over that network. They have tested a mesh with 500 plus nodes. So like Bravo to them. They have proven that this stuff actually does work. And through them, there have been many improvements to these two routing protocols. Serval, these are the guys in Australia. It's led by Dr. Paul Gardner Steven. And their idea was very similar to ours. They started before us and they have some things we don't and we have some things they don't. And they wanted to get an Android ad hoc network up and running in the remote regions of Australia. So they got VOIP working, which is something we're still working on. You can then send SMS over their stuff. They have distributed mesh data called Rhizome. They have a map. They have micro blogging. They have a lot of stuff. Some of it works great. Some of it's still being developed. The thing they have though is a special API for using their services. I don't know if they have a special API for sending data over their network either. But we really wanted to avoid that so that any app running on our stuff can work without knowing about the mesh. I don't know if their stuff supports that at this point in time. So future work for us. VOIP, you got these phones, you like to use them to talk to each other. Using SipDroid, we can pull out a lot of their stuff and get it working over the mesh. IP address assignment still open. Static works. Static is not going to work when you have 500 people on the mesh. There's going to be a lot of collision there, most likely. Evaluate Serval's approach to security. Like I said before, that's using your public key as your IP address. Work more on iOS and Windows 8 supports. So once again, this is the GitHub repo. Monk set it up, so I guess he gets all the credit for that. We got five things up there right now. We got a manager, which is the user facing UI used to set up the mesh. The service runs in the background. You don't really see that. That is a communication, a logger, so you can log info about the mesh. We use it for debugging. Visualizer, which you saw up on screen. And customized version of OLSR running in the background. Eventually we're going to be using Batman. So these are the open source projects used. You can take a closer look. We did the right thing by GNU and we open sourced our stuff too. So we're going to open the floor up for Q&A. And if not, if we have click checking. We haven't carried at that level yet. How about that? So our main focus this year has been providing the low-level network that people can build off on. So I'm worried less about things like click jacking and the higher-level things than I am about spoofing. I guess we could talk more if you want to talk. Anybody else have another question? If not, we'll take them over to Q&A number 4. And you can ask the questions there. Thank you. Thank you, everyone.


We are back on Roblox and we're gonna be doing a scary story named I didn't see we're here with this quad. What's up y'all say? What's up Twitter?  Okay, so let's go up in this theater and see what's up with this scary story My god, there's a lot of different stories over there. Okay, the entrance is over here. Hey, what's up, man? Oh, it's that guy with the funny mustache. Okay. Let's go this way. Oh Oh, I hear the music already entrance I didn't see shocking. Oh, no. Oh my god No, never playing that game again. My god. Well, how scary can this be? Okay, it says Dan and Melanie were getting married in a week So they invited their best friends over to Melanie's house for a party Okay So it's like this is Dan and Melanie right here They got all their closest friends over to their house because they're getting married in a week Okay, so it says Melanie still lived in her childhood home Which was always their favorite place to hang out since they were kids. All right, but she still lives back at home Okay, they all started talking about their favorite childhood game hide and seek Okay, so there they are chitchatting catching up They decided that they had to play the game and Dan was picked to be the seeker Okay, dad. So it seems like Dan must be good at seeking or something since they chose it Dan began counting to a hundred as everyone ran from the room to hide.  I mean hide and he's gonna go seek in about a couple seconds Does dad finish counting ready or not here I come he yelled loudly. All right, Dan boy. Let's see how good He really is at this game It says he went through the house looking for all of his friends. Okay, so here's Dan Searching through the house nice house, man. Dude. This house looks like it's humongous or something Okay, um, he looked everywhere, but was having a hard time finding anyone. Oh, no It seems like Dan is having trouble finding the rest of the people. Okay, he finally found you're out in the kitchen Pantry eating pretzels. Oh, he found them. Dude. He was hey, what are you doing in there, man? Okay, so he found me eating pretzels Kind of sounds like me man You like hiding and eating at the same time Dan and Jero went back to the living room and yelled for everyone to come out. Okay, so here they are in the living room That and everybody else to come out even though he has to search for them everyone came running back into the living room They were having so much fun. All right. It seems like a nice party a nice gathering here. My god now I want chips. Thanks a lot Dan for your party. Okay, they all started talking about where they were hiding They laughed and laughed. Okay, wait, where's the wife? The wife is missing. Yo Have they not noticed? After a few minutes, they noticed that Melanie wasn't there. Oh my god, where's Melanie? You're not Melanie.  Okay, it's kind of close Emily and uh That's a little too close. Okay, uh, everyone began shouting her name Melanie. You can come out now But there was no answer. Oh my god. What happened to Melanie yo? My god, okay, this is getting fishy guys. They were all getting nervous now Okay, let's split up and look for a Dan said they all agreed and went to look for Melanie Okay, so they're gonna split up like an uh, what's that cartoon called could we do they're not gonna take squads and go to social Melanie.  Okay says they search every square inch of the house but could not find the Melanie Oh my god, okay, so where could she have gone? Okay, so they're here. They are searching for her under the bed. She's not there in the cabinet It's not in the cabinet either. Where could she have gone guys? My god, okay, um, Jorale and Grace even looked in the attic, but Melanie was nowhere to be found Okay, um, that is the creepy mannequin up here Oh my god, the door Okay, so they can't find Melanie anywhere. It's just getting strange Melanie's parents just got home from their night out Dan told them everything. Okay, so they're the parents What is going on here? I think he's stuck. Oh my god, okay, so Melanie's parents look very fancy and elegant You got a tuxedo and she has like a Cinderella dress on Okay, an hour had already passed on Melanie's parents decided to call the cops Okay, so it's been quite some time since Emily has disappeared The police searched the entire property and questioned everyone but there was no sign of Melanie anywhere Oh my god, okay, so the cops have arrived and they're questioning everyone Because Melanie's still gone Okay, they made a full report and put on an APB but said that there was nothing else they could do at this time They slowly left the house Okay, so they just put a report out for Melanie that she's like missing or whatever wait that Melanie What is she doing? No one ever saw or heard from Melanie again. Oh my god poor girl Okay, Dan blamed himself thinking that maybe Melanie just didn't want to marry him. So perhaps she ran away. Oh poor Dan No, dad. Don't don't let your thoughts get to you my boy. Oh my god, okay So it seems like Santa's getting depressed or like sad over this Okay, 15 years later Dan was a very successful architect, but he never got over Melanie. Oh my god Okay, so 15 years have passed That is quite some time you guys and look at his house. It's so nice and fancy. Okay. I'll poor Dan You can't forget about his lover Okay, the one day Dan's mother called him. She told him that Melanie's parents were selling the house Oh, no, I don't think he's gonna be too happy to hear about that His heart was broken, but then she told him something terrible. Oh, oh Don't tell me they found her She told them that when Melanie's parents brought in a moving company to pack up all her things they found something Oh my god, what could they have found? I don't know man. Okay in the basement they found a very heavy trunk and when Melanie's parents unlocked it and opened it Oh my god, don't tell me she was hiding in there And they got like locked and she couldn't get out. They found Melanie inside That was where she was hiding the trunk lid must have locked when she had gotten inside Oh, no poor Melanie. So she was trapped inside that shrunk the whole time.  No one please. They did not check was the basement No one had ever hid there before Yeah, because who goes to the basement is creepy or the attic. I would never hide in either places Gotta be crazy, man. Dan imagined poor Melanie calling out for help from the trunk inside dad Help me dad, but dad never came because he couldn't hear her dude Okay, I don't know how dad is gonna take this. I mean if I was in dad's situation I would have felt like it was my fault, too Then has nightmares about Melanie and the trunk all of the time. He can hear her screaming for him to help her Oh my god, it's like a skeleton inside while on top of the trunk Dude, that is freaky. Oh my god. Okay. Let's keep going. Oh That's it. Don't forget to visit our other attractions to Golden Arm and the passenger which we have done both already and they're pretty awesome So let's go over here. Okay, this brought us back to the lobby. What's up my boy? Okay, we see what this guy has to say here What? He doesn't even have anything. Okay, join our group Join the scary stories ride group for coming up coming updates and stories and more all right I need to join this group man. I haven't joined it. I'm slacking. Okay, so they just takes his Oh the teleports is back to the lobby. That's pretty neat. Let's go check out the upcoming ones coming soon Okay, coming soon. I see you. I really want to do that one now looks crazy Oh, it looks kind of creepy and then we got the babysitter. Oh my god. There's somebody back there All right, well poor Melanie man All they wanted to do is play hide and seek and like I wonder why she chose to hide down there in the Basement if she knew that nobody would like would even go down there I don't know man for resting piece of Melanie man and poor Dan We might never know if he would like gets over her or not Well, that was hiding seek you guys in Roblox scary stories, right? You guys enjoyed the video make sure to slap the like button for your boy if you're new to the channel Make sure to subscribe and turn that notification bell on and I will see you guys in the next one. Bye Maggie was so excited about going to her senior dance at the high school. She could hardly contain herself Okay, so as we see here Maggie is getting pretty because she's about to go to the dance So let's see how that goes as soon as she was ready. She grabbed her sweater and ran out front the girls would pick her up soon Okay, so she's ready. She's waiting for her friends outside of her house She is ready to lay to the dance before she knew it the girls were there She jumped into the car and off they went. All right, so her friends came for her.  Hey, everyone was so excited. They rushed into the school And straight to the gymnasium to see the decorations. Okay, so we're at the school right now guys Everybody just arrived. That's a nice school man. That's a high school. I think looks like the college or something Okay, so there they are. Oh, okay, we're in the high school dance the decorations were wonderful


Hello and a warm welcome to everyone joining this session today, we have Michael Bilquist with us today to share his experience of building the functional streams for Scala. He'll be talking about FS2 chunks, the chunk data structure powers the functional streams for Scala stream library. And we have Michael will be taking us to the design of chunk and in particular. Oh, he'll be explaining the design constraints that guided its evolution. So I'm pretty much excited for the talk. Without any further ado, let's head over to Michael. Thank you so much. I'm happy to be here. So yeah, I'm here today to talk about the FS2 library, and particularly the chunk data type. For the folks that don't know me, Michael Bilquist, I have been with Comcast for about 17 years where I've had a career that sort of started with C and C++ and went through a Java sort of enterprise phase and then for about the last decade I've been heavily involved in functional programming. I maintain a bunch of functional libraries in the open source ecosystem. In particular the FS2 library as well as things like SCODEC and a couple others. Normally when I give a talk on FS2, I kind of get into the, the internals of the streaming approach or some of the novel ways we do concurrency. But what I really like about today's talk is that it shows that there's still really interesting problems to solve with sort of simple data types with data types that maybe don't attempt to, you know, boil the ocean with their capabilities. So with FS2, we have this chunk data type. And the chunk is a collection. And if we look at the SCODEC of the chunk data type, we end up with a definition that looks somewhat like this. It says that a chunk is an immutable strict and finite sequence of values, and that it supports efficient index based random access of elements. Okay. The problem is that in Scala we already have a data type that meets these constraints. We have the persistent vector data type. Persistent vector is immutable, it's strict, right, it doesn't delay computation anyway. It's finite, it doesn't allow, you know, infinite values to be represented. It supports, you know, effective constant time indexing. So maybe the first question to ask about the FS2 chunk type is why does it exist at all? Why aren't we just using the vector type in the library? And so to understand that, we have to look at some of the APIs that get built with the FS2 stream data type. So here I have two sort of example capability traits. Maybe there's a trait that represents reading bytes from a network socket in some effect F.  So like if our effect type here was IO, then in order to generate that byte stream, it's going to invoke IO computations. And likewise, you know, you can imagine a files API, right, to read all of the bytes from a file on the file system, and again streaming those bytes back by evaluating some arbitrary effect. These are both very common signatures that you see in the FS2 library, and all of the operations on our stream data type, let us manipulate values of the output type of the stream. Right, so here we have stream of bytes.  But internally that would not be an efficient way to represent a stream data type. Just all of the sort of machinery involved in the streaming approach sort of adds up if we're manipulating individual pieces, individual, you know, values in the stream. So rather we move stuff around in the stream as chunks, as these densely packed, you know, maybe arrays of bytes you can imagine. Right, move those around within the API lets you sort of ignore the fact that these chunks exist and operate on individual elements. Now, why not use vector instead of using chunk to move around those densely packed sets of bytes. And there's a bunch of reasons we're going to walk through them. But one of the key ones we can see right away just by looking at these two sample API is that if we tried to use vectors, then we're going to have to do a lot of copying. You can imagine a socket API that's interfacing with the operating system, maybe providing, you know, byte arrays directly, or maybe having directly allocated byte buffers that, you know, sort of the network API is putting data into for us. And so we want, we want to be able to be efficient if we're using this for IO. But before we even get into the details on on copying. It's worth pointing out that vector, really the thing that caused us to first move away from vector years and years ago is that vector is not particularly space efficient. So here, you know from left to right in this table we have the size of the collection. And from top to bottom we have a bunch of different types. And so in Scala 2.12, you can see the overhead of vector was pretty, pretty big. An empty vector was 56 bytes up through a vector of 10,000 elements being, you know, 47,000 bytes. In Scala 2.13, vector was rewritten thanks to Stefan Ziegler and a few other folks. The 2.13 vector is significantly better. And in particular, small vectors are much smaller, right, vectors with few number of elements take up much less keep space. And even with the improvements in the 2.13 vector, you can still see, like if we wanted to actually store bytes in a vector, the overhead, you know, is still significant. And that's because vector is not specialized on the byte data type. And so every byte we put into a vector actually gets boxed, right, so we actually store object references to individual bytes, pretty, pretty inefficient. Now, moving arrays around would be sort of the best we could do. But if we move to raise around, we have to deal with the mutability of arrays and this is a functional programming conference. So chunk is, is our first reaction to that chunk gives us a way to have the efficiency of arrays but be immutable. We can sort of think of it as an immutable array. So we can alter the definition of chunk of it, we can say a chunk is not only an immutable strict finite sequence that supports efficient look up, but we want it to be memory efficient for all sizes for small chunks for large chunks, etc. And we want to avoid copying as much as possible right interfacing with those IO boundaries. So let's walk through those constraints and see how they manifest in Scala. So we say a chunk is finite. So you can imagine that a trait here called chunk that stores values of type a, and it has a size, the size will be an integer. We don't need to worry about representing sizes as long, right because FS2 is a streaming library so you know if you, if you have a chunk that's larger than a signed in, then you can just use two chunks and manipulate them together through a stream. So a chunk is finite. We want this efficient random access. And so we have this apply operation that, you know, you pass an index and you get back the value at that index. And right away, you know, we've only added the second method to our data type here right away we have made a trade off. In this case, we are trading off the safety of making this method total, right, like, we could pass a negative one we could pass an index out of bounds. But rather than getting back an option or getting back some type of, of safe value that prevents that we're going to throw an exception will throw an index out of bounds exception. And we're going to do that specifically because of the need for efficient random access. If someone's writing an algorithm that's sort of traversing through different indexes of a chunk chances are they're going to be doing a lot of those, right. They're going to be going around, you know, pulling out different or different values different indices, etc. We don't want to pay that boxing cost of wrapping those values in option. We want to avoid copying and making sure we have these memory efficient implementations. And so here's like three data constructors for the chunk trait that we just created. Here's an empty data constructor which actually caches that value off as a value. You know, the type of this value is actually a chunk of nothing indicating that it's a, it's a chunk of any type, right, and chunk is covariate in its only type parameter. We have a singleton chunk where it just wraps a single value. So the only overhead we pay for that singleton chunk from a heat perspective is the single object reference, as well as the size of the object we're pointing to. And then finally we have an array constructor, which just sort of lifts in a mutable rain. And again, you know, we've made another concession. Right. The safest implementation of this array data constructor would do a defensive copy of this mutable array. So you could argue is chunk really immutable even now, given that it has this data constructor that can reference mutable arrays in which post construction someone go and manipulate that underlying array.   So here's two example ones you could you could come up with. There's an index seek data type in the scholar collections library, which is basically a immutable sequence that has a fast indexing lookup operator. So we can lift those right into chunk. And then, you know, because we work with bite streams a lot. It's often, or it's probably convenient to have a way to interoperate with like the job and I owe bite buffer interface. Right. And once again, we don't do defensive copies of those underlying buffers. Okay. We've avoided copies in our data constructors but how about the operations on our data type itself. You can imagine some code like this, we have some huge chunk of bites that we got from somewhere doesn't really matter. And maybe we've got some algorithm that wants to take that huge chunk and, and take the, you know, first 10 elements and process them and then maybe delay the processing of the remainder. Right, maybe it's like a binary parsing protocol or something. And that more efficient right off the bat is by thinking about the operations that we're providing to our clients. Right, so rather than having a take and a drop. Maybe in this case it'd be better to offer a split at right just to have that knowledge in the implementation of split at that we, we need both pieces, and we can avoid some, some duplicate work if we know the client wants both a prefix and a cell. So how can we make split at efficient, right, a naive implementation of it maybe would have to pattern match and all the data constructors we've defined so far. And then handle like array copying bite buffer copying etc. You know, and generate duplicate arrays. We don't want to do that. So instead, we can introduce a new data constructor. In particular, the array slice data constructor holds a reference to an underlying array, but then also holds a view, a subset view on that array. And that view is identified by an offset into the, the wrapped array and then a number of bytes from that point forward or another, a number of values from that point forward. The apply operation we've written before is just normal index based look up just, you know, adjusting for the offset and the size. And then split at, we can implement in a way that is zero copy. Split at can say, in essence just create two views of our underlying array and just do some offset arithmetic. Now, we've given up a little bit of strictness in this case. Right. When you call split at the API makes it look like, like, you know, when we said split at 10, the API made it look like we had a small prefix and a large suffix. But if, you know, we were relying on that small prefix, like we want to accumulate a lot of these small prefixes. We have to be careful that we're really referencing like huge underlying arrays beneath that, right.  We're giving up a little bit of strictness in this case for performance and efficiency of the split operation. Okay, let's let's add some combinators to our data type. Maybe the first combinator we might add is a for each a side affecting for each operation, right apply this function to every element in the chunk and just perform some side effect. And since we have a finite size, and we have an efficient apply operation, then this is really just a while loop. Right, we started index zero and just rip through all of the elements of the chunk, calling our function f. In other words, we can do side affecting with an index, right for each with index, basically the same exact implementation we're just passing that index into our function that's passed to us. So far so good. But this is again a functional programming conference so let's let's look at more functional combinators how about Mac. Let's look at function f over our chunk, right transforming each individual element. How might we go about implementing map, given our definitions so far. So, maybe a first take at the implementation of map could look something like this. We can create an array of our target type B. We're going to go with the size of that array because maps not going to alter the structure of our chunk at all right. And so we allocate an array of that size. And then maybe with for each with index we just side effect, you know, array mutations through all of the indexes of our source. And then we return an immutable chunk referencing this brand new array we just created. We're not going to work in school. And in particular, we need, we need this thing called a class tag from the scholar reflection library to be able to allocate an array of a polymorphic type B. We can't just create an array of any type in scholar, as a result of running on the JVM. And as a result of the JVM having primitive array types built in. If someone was to instantiate this map operation with be equal to bite, for example, we want a primitive bite array created on the JVM we don't want like an object array, where the individual bytes get box. So, we can, we can't quite write this code. The way it is here. So one option or one option to address this is to add that class tag constraint. So here we've added this constraint to the type parameter be one map, and I changed the name to map compact now. That class tag basically acts as a witness that we're able to create these primitive arrays. Right so if be ends up being a primitive JVM type we got a primitive array of the corresponding type. If be ends up being like an object type we're just going to get a regular object array. So this is fine this works, there's no problems here. But it doesn't really scale. Right like this, this works fine for this one operation map, but really do we want these class tag constraints propagating through all of our APIs on chunk. As we continually run into operations that maybe need to allocate new chunks. Or the definition there is interesting but it's, it's not as performant as it may look like we want, we want these primitive byte arrays to be created on the heap. But we had a function argument, and that function argument said you know map, for example a bite to a bite, or map a into a bite, you know and so forth. So the function trait that's used in scholar to sort of implement function values is specialized on some primitives but not all. And in particular it's not specialized on bite. So, even if we're mapping a chunk of bite to another chunk of bite. Each of those bites will get boxed past to the function one, and then the return to the resulting bite will then have to be unboxed. So there's tons of boxing going on even though we thought you know we were working with these densely packed by the race. I mentioned these class type constraints, virally property right anyone that wants to call a map compact in a generic context right where they don't have a concrete known type are going to need to pick up that same class type constraint they'll continue to propagate until until reaches a concrete case. And you know and then furthermore, we end up with with different implementations. If we implement map compact, where we maybe have like an efficient version in the compact case and an inefficient or maybe it doesn't doesn't normally matter right or a default implementation in the non compact in case. And if we were to really offer both of those API is then we're making our users of our library pick in each case, which one to use. And it's just too much of a burden on everyone to pick constantly all of the time. So, map compact isn't really a great solution. So instead, we can take some of these facts and put them together and say, well we're going to end up boxing here anyway. Right. Like I like I mentioned the, the bite sort of flowing through this function one are going to end up getting boxed as a result of just scholar, not specializing functions for bites. And so, really we don't, in this case we don't necessarily need a primitive array underneath, so we can construct an array of any. And this will really be in a an array of object references on the heat, right so this is not space efficient. Or it's unsound, right like we have an array of any and we're claiming, you know, or sort of trying to treat that as an array of type B. And that's that's not a safe thing to do. So in this case, we can work around it, this is the same trick that's used in the scholar collections library internally in a bunch of similar cases. We're not evaluating these array of any is, but as long as we never reference that array of any as an array of B, then it's okay, then it's safe. And in this particular case we never expose this underlying array right we're constructing it locally, and then encapsulating it and keeping that array private. There's no way to access it. So in this case, even though the operation is unsound, overall, it is a safe operation. Okay, so what about compacting what about when we really want those densely packed fight arrays on the heap. Well, in those cases we can just ask for right we can keep our operations perhaps inefficient that we just from a space perspective like we just saw, and just add compacting as a separate operation. And so in this case, we've added two operations to chunk to array, which just copies all of the elements into a brand new array. And in this case this to array will have a class tag constraint, because from an API perspective, we're saying this is going to allocate a primitive array. And then likewise compact just does the chunk wrapper around a call to to array. And in reality in the library, the implementation of these type of operations is a bit more complex significantly more complex because we have all sorts of special cases to avoid these copies when possible. Or in the case of like underlying array slices, we can implement to array by actually doing like a native array copy of just the part of the, you know the slice of the array that we care about. All of these same constraints and trade offs that we just made still apply, even in the optimized cases of these operations. All right, let's look at another one, filter operation just like map, but this time, we don't know the size of the elements. So we can't just construct an array of the same size as the starting chunk right. So here, we lean on the scholar collections library again, and we use an immutable array builder. And the mutable array builder in the collections library is very much like a Java array list right it will. It basically has some algorithm to resize periodically by factors of two. We run into the same problem, though, with respect to class tags. So again, well, in this case, create an array builder of type any knowing that that's going to, you know, in the end give us an array of object references. And then we're going to do that same unsound cast that we did before. One thing that's kind of interesting here is that we can choose to do size hinting to the array builder. And so the question is like if we have a huge chunk, and someone calls filter on it. Is it more likely that they end up with a chunk that, you know, is near the size of the input chunk, or is it more likely they end up with a chunk that's that's near empty. Of course there's no way to import to answer that question in a totally generic sense right but in a data type that's in a streaming library that met much of the time works with bytes. We can use that context to make a better implementation here. And so here we choose to say you know what we think most the time when folks use filter, they're going to keep elements in. And so we're going to size hint the underlying array builder towards the size of the input collection. And of course that will be the absolute wrong decision sometimes right like if you filter all elements out. But in practice I think it ends up working out for our use cases. Okay. So, let's take a look at this next example we've got a huge chunk of bytes again.  And we have two examples of how those two chunks maybe combined into a stream. Right so in the discouraged case. We just a single chunk into the stream API. And we the chunk that we lift is the result of concatenating the huge chunk with a little chunk. And we want to discourage that because we don't want to do any copy right we don't want this plus plus operation to sort of have to do a whole big array copy right that huge array plus two more bytes on the end just to stick those elements rather we want folks to use this encouraged example right of, there's no need to create a single chunk representing each of those two constituents. Because with the stream API you can just lift both chunks and concatenate those streams, and that's actually constant time in FS to. So the question is like from an API perspective how can we encourage folks to do the latter. And the answer really is that, you know, when we write software we tend to be lazy about about things right we want our API is to be elegant and simple and not have a lot of craft. And so in this case we discourage it by just not offering the API by saying like hey if you want to, if you want to concatenate two chunks, then we're going to kind of make it ugly. We're going to make you kind of put those chunks to want to concatenate into a list, and then call this concat function. Right and this is sort of just a speed bump it's it's just as expressive as the previous example, but this speed bump making it just a little bit more inaccessible and making a little bit more ugly to call actually has a material impact on how often folks end up using it. All right, how would we implement concat though. So here's one possible implementation of the concat operation, we take a sequence of chunks as an argument. We sum all the sizes of each constituent chunk. We allocate an array, and then we just copy all the elements in. And sort of manipulating all the offsets. And in this case since concat right we're going to concatenate a bunch of individual chunks we, we think it's a good idea to keep concat as a primitive backed, you know array. So we're going to pick up the class tag constraint again. Let's see how we might use this concat operation to implement something maybe sort of complicated an FS to. So here's this uncons and operation. We're not going to get into all the details of this API, it's not particularly relevant. But I want to show just the way concat the decision that we just made in the concat operation sort of impacts usage. So concat cons and is a stream combinator it says, given some stream s. Take from it n values, and then emit them sort of in a chunk. So we want to output this chunk of n values, and we're also going to output the remaining, or the remainder of the input stream. The full data type is a is a functional data type that lets us recursively build up the stream computations. And so, typically it looks something like this you have like an internal recursive driver function in this case I called it go goes going to close over some state in this case like a queue of chunks. This is the stream that we're pulling from and the number of remaining elements we're waiting on. And then it pulls on the source stream and says give me the next chunk that's available in the source stream. And if we reach the end of the source stream, we we reached it before coming up with our n elements. So we can just admit whatever we've got will admit the concat nation of our accumulated chunk so far. The remainder stream is empty. If instead we got a chunk of elements from the source stream plus a tail plus the remaining remainder of the stream. Then we want to sort of, you know, add that head to chunk to our accumulator queue and recurs. And if we reach the right number of elements then we do some splitting and concatting right and then finally admit the net result. Okay, so don't worry too much about that API. The important part is that in multiple cases we called concat. And as we saw concat requires this class tag constraint. And so, we have some options on how we can address that. And to make that code compile one option again is adding the class tag constraints to this generic Oh type parameter on the uncons and method. And if you do that, then all methods that call uncons and are going to need to pick up that same constraint, we're back to that viral propagation case we talked about earlier. Another option is to just change. The problem entirely. Right, rather than concatting, which is going to require this class tag constraint. What if we just admit our accumulator without concatting we just give the queue of chunks back directly. Right. So sometimes it it's difficult to see these types of options right we get so focused on the problem we're trying to solve. We don't realize we can just change the problem. The third option is we can remove the class tag constraint from concat, just like we did with Matt. So let's look at that third option, it seemed to work nice for map, can we do it here. And of course we can write it's the same exact trick we allocate an array of any we're going to, you know, trade off the fact that we, and we have this generic operation now but we lose the ability to create these densely packed primitive arrays. And the operation like concat that sort of matters.  So this was, this was our attempt at fixing this a long time ago. In essence, we, we sort of taught chunks, how to know what their element types were like, if we could just capture some, some knowledge at data construction time. Saying like, oh you put bytes in here. If we can then query that later and say like hey, if someone wants to concat a bunch of chunks together, if we know that all of the chunks only contain bytes, then we can use an optimized version of concat that allocates a bite array. Right, and we can do that for each primitive type, and only if you put a non primitive into a chunk then we could fall back to the untagged based operate or you know approach. And the question, you know, with with this type of approach, how do you do this efficiently like you don't want to do a linear scan over chunk.  There were some fallback cases for some of the other constructors. It roughly worked until we started getting more adoption on Scala JS. In particular the HTTP for us library, a functional Scala web library got ported to Scala JS. And so you can do, you know, web servers and node, you can do web clients you can use it on browser based API etc. And that library uses FS to as its underlying mechanism for moving bytes around. And as Scala JS adoption increased we eventually ran into this case where the, the assumptions made in our implementation of this optimized concat no longer held. And in particular because of Scala j, or sorry because of JavaScript's approach to like a number tower being different than the jbms we end up with operations like this, right where the, the number one is an instance of bite. And so the whole scheme we came up with didn't, didn't in fact work. So option threes out, we can, we can't do the untagged version and still get, you know, specialized tagged behavior or efficient behavior in those cases. So rather than falling back to option one or two, we sort of combined options. And then, well, what, what if we created a new data constructor for chunk. That's just a subtype of Q. And so the idea is that the chunk queue data constructor just references an underlying set of constituent chunks.  We can support pending a chunk or pre pending a chunk. Take care to make sure we don't put empty chunks into our constituent chunk queue, just to preserve some asymptotic complexity. And then indexing through this, you know our efficient index based look up ends up just being a sort of a walk of our constituent chunk queue, right just looking for the right offset. And with this new data constructor, we can actually go back and add that plus plus operation, right, because now that operation is no longer linear in the size of the input chunks. It's rather logarithmic in the size of the constituent chunk. And we can use this new implementation in unconsent and the trade off seem really good. Like our accumulator now is just a chunk of Oh, our output, you know, is the accumulators just the same as our output type chunk of Oh, and in each of the cases throughout the code were before we were calling can cat. Right. Now we're just emitting our accumulated chunk. And when we want to add elements to that we're just concatenating. So we're just hiding all of that underlying Cuban, but all is not well. There's one big problem here. And it's in the asymptotic runtime performance of that index based look up on Q base chunks. Right. When the constituent chunk queue is small. And then we have effectively constant time runtime performance. Right if there's only like two or three elements in that constituent chunk you. And when you go and look up an index it's real quick to kind of jump through them and say what's the size of the first one's the size of the second one. Oh, your target index must be in the third. As that constituent chunk you size approaches in, or another way to say that is that as the size of the individual constituent chunks approach one. Then our runtime performance now linear. Because each of those bounds checks really just moves you over one element. And now let's go back to our for each. Our fundamental building block operations that we use in all of our other companies. If apply can be linear in some cases, then for each is quadratic. Because for each is already linear in of itself. We're going to say each time through that loop or potentially making a linear operation. That's not good. So we can fix for each, and we can fix for each with index real easily. We can say, we'll just don't index. Like we can specialize the definition of for each on the queue constructor to say, you have no need to index in this case just for each over each of the elements in the constituent chunk you. And that works fine that works great. And the other combinators that were implemented with apply still have this potential for for nasty asymptotic performance. So how do we fix that. This was an idea from a maintainer of FS to the general idea here is that we're just going to binary search and index table. So let me show you what I mean. Our constituent chunk you as five elements with these sizes size three 10 one so on. We want to build this lookup table of accumulated sizes. Say, the accumulated size after the first element is three after the second element is 13 and then 14 and so on. We also create an array that references each of these elements in the queue. And then we will binary search this accumulated sizes array for the target index. So in this case, if we binary search this array for 20, we start at 14, move over to 34. And now we know that the target element is in this position. Right, so we can move up to here. Let me say the target element is in. So the implementation of that is shown here. Both the creation of this set of lookup tables, as well as all of the sort of index arithmetic needed to binary search it and then lookup. Feel free to take a look at the slides. Go ahead. Yeah, just to change the reminder, in the last few minutes of the session. Yes, yes, thank you. And so the net result of that implementation is that the first call to apply is linear in the number of constituent chunks. The subsequent calls to apply are logarithmic in the number of constituent chunks, chunks. With this implementation, even in the worst case where you have a chunk you have singleton elements. That for each implementation, for example, the one that used index base lookup would have been n log n instead of quadratic. Okay. So in the parting moments here, I just wanted to say that we made a lot of compromises on our initial definition of what a chunk was right. And those compromises are okay. No, we traded off all of these sort of hard constraints that we started with for good reasons. And I think that's something we have to remind ourselves in functional programming is that we got to look for those balances and find the right approach. I don't want you to leave this talk thinking this design is this series of logical decisions that we just walked through. Rather this was years of a created knowledge, based off of all sorts of use cases. So this is like over like a five year period there were 20 issues and pull requests, just manipulating chunk. And so that that's really my talk for today. You know, I'm happy to take questions maybe in the hangout area. But in general, I hope that's an interesting walk through sort of the design process that we went through, even for a relatively simple. So what a message to us to design is an iterative process of success and failures. Remember that. Thanks a lot for the wonderful time.


Hello, my name is Simon Francis. I'm from Indian Brook, Nova Scotia. I'm going to be talking about the Mi'kmaq Go-To-Person program. We're doing its online program now. It's from the Mi'kmaq Heritage Restoration Association by Delina Pettipaw now. It's fun. Curtis is the instructor, Curtis Michael, and we got to do online videos. We were given a lesson, and we got to do it online, that video, and we got to put it on this website. It's a secret website. There's 23 people from Nova Scotia, Newfoundland, New Brunswick, P.E.I., who selected for this program. It's a Go-To program, and I'm what considers the right person to for this program because a lot of people come up to me for Mi'kmaq words because I was around it. I grew up with it. My mother, my father, my grandfather was all fluid, and they really influenced me when I was young. I learned it from I was three years old right up to I was, oh, I took care of my mother until she passed away, until she was 82. I was still learning, and it's still a learning process today. I grabbed my my dictionaries, and I'm looking at them every night, and I was like, wow, I didn't know that. That's just extension of words. I said, oh, I knew that, but I didn't know how it was spelled, and simple things like now, I don't have to run to the books now when I want to stop right on Mi'kmaq online. I got it all in my mind. I knew how to spell it out. Like, uh, kueh, emsit nogama, hello all my relations, and well, the exit book, how good, good morning, and stuff like that, little things. You know, just something to say Mi'kmaq in the morning. I won't say nothing in English until I write something Mi'kmaq every morning, but that's, that's me.  And there's people like from my mother's hometown, and they're in their 60s, and they don't know their language. It surprised me, and I'm in 54, and I know a lot more because I was exposed to it as a younger person, and taking a course, and I took a course in 2017 for a six-month course with Curtis, and it really opened my eyes. I was like, wow, he say one word. I was like, wow. I said, I've never heard this word since I was three years old, and I was like, and it just opened a new world to me. And I was like, it was just a new world, a whole new world, language. But it was always there in the back of my mind, and I just kind of put it on hold. But nowadays, I got people coming up, we got worded a day. They play, I play worded a day of our band office with a secretary, a part-time secretary. I'll go in there, well, the Exit Book, I'm in the medallion, now where they belong, and we'll play, hello, how are you doing? I'm doing fine, you know. It's a nice day, we'll say that, or we play worded a day. And she goes, what's a worded a day? I now look outside, it's misty, or ill-naked, foggy, or wellie-kisco, it's sunny. And she goes, wow. And now she's, now when I go in there, I find she's speaking Miigma to me. I was like, and these are my dreams to keep our language going. And I find my dreams are coming true now. And it's surprising, it's eye-opening for people. And this girl, she's in almost her 60s, and she's starting to learn now.  I said, yeah, thank you. I said, I was surprised, that really surprised me, I actually learned. It was a plan in life, I think, to keep me, keep the language going. And I still have my nephew and his niece, my niece, his daughter come in. Uncle Muccas, no more this, and medallion uncle Muccas, hello, how are you doing uncle? And things like that, they're speaking their language. And I was like, wow, and they're learning it from me. Or when I leave, I said, um, what's the word today? And the mother said, they said, what's that mean? See you all later. Things, little things like that, but they're learning.  And we call it word today. It's these games we play with the family and they love it. But things like that, we need more education, more programs, things like Curtis, the six month programs, but commitment and space. That's one thing we do not have. You got to be committed right from the beginning. I mean, I was loved it. I mean, I was committed right from the beginning to this program. I was there every week. You know, it was, I opened it. I mean, because I didn't forget the language. I thought I forgot it, but I didn't. Like Curtis has this, uh, Pictionary Games for adults. That's excellent.  And that means soap bed, which means hungover or things, simple things like that.  Get them out of the classroom, get them in a home. Don't get them in the classroom, especially with adults. They do not like the classroom. Make it a home environment, coffee there, make a little lunch, make a flower Indian bread, invite everybody in, make it family settings. But you got to get them out of the classroom for learning because that's not the whole place to learn for adults. That's what I found. We had a hard time with that. In our program right now, it seems to be from anywhere in the mid 30s to 60, 70s, all age, right around. And our go to the language person and then make my go to the language person is, it's all everybody. Everybody's learning that the same process, but it's, everybody's at different points. Like I'm at a different point than these guys because it's just all natural to me. I find, even being Curtis, we're talking at it. He goes, you're pretty fast at these lessons. I said, it's all natural because boom, boom, boom, boom, I can shoot her right out and I record it and put it online. Now I'm done. I don't have to worry about it and wait for the next lesson to come out. But we need more programs, more programs like that. We have a secret group and Curtis would come up and he'll show a video, word video, word video, and we got to pronounce these words. Then he'll, now he's getting the omit endings and we got to do a homework and we got to find the right endings and add it. Like S-B, S-B or S-B, that's hot, I'm hot and certain things like it. Little things that S-B add a I-T or E-N or N to different endings, make it add a different language, different word, different endings. Now we're getting things like that more, he's adding homework now. I was like, but it's fun. It's all fun. And he goes, you're getting faster, but I love it this way. You got to love it. You got to be committed to do it. Like the like button, love button. Everybody comments, wow, you're doing good on these videos. I mean, geez, the process is good. I love it because all your technique is beautiful. We need more of this. I love it. I love to see your technique in the classroom. And it's simple things like that, encouragement. And we have, everybody has a chance to put their own videos like we have till February 5th for lesson six, but I would put mine on because I'm like that. I'll just get it done like that. So I don't have to worry about it. But it's a success. I find it's in different levels. Everybody has their struggles and some of them find it easy. But like one lady's last comment, she goes, oh, I had a little hard time with this lesson, but I need more practice. That's all because she's not exposed to it. She's in town. She's in town material. Like I'm exposed to it. I'm always online talking. Curtis, Curtis is the word online chatting in Mi'kmaq. He's a phone call away. I go to my brother's and he's talking to Mi'kmaq. And we're comparing from the Mi'klish now. What they're speaking out there now is Mi'klish. What I learned was the old way. My grandfather was born in 1886. And I learned his way. And my father's way, my mother's way. And that was the old way. Like for say no, nowadays they go moho. But I was taught moho. Like my grandfather, that's the old way. But either way is acceptable nowadays. But we know one is Mi'klish automatic. But it's still all, it's changing. But I don't like to change. I would still stop on the original way. We're exposing techniques. Techniques and more like pronunciation. Different pronunciations. You got to get the blends. Once you get the blends in, like the T, the T sounds like a D. The K sounds like a G. And things like that. It's no problem. You can pronounce anywhere. You can read it. It's once you get the blends and how the words sound, the pronunciation, you can, it's easier to read. And now I just, when I do my homework, I write it down. Then I got to expand it. I expanded. I do it all on one page and I make my video. And currently we were talking and he goes, then he goes, you're fast.  I said, wow, I love it. He goes, you got to love what you're doing. And it's just come natural. I even told it's all natural. It gives me something to look forward to. People even, I'm the go-to person. I actually, I'm the go-to person. I got messages. A lady was doing a painting. She wanted to learn a word. I get a message. I said, no, I'll send a message out and send the word out. Next year, you know, she sends me a painting with the word on it. I was like, wow. I was like, oh my God, it's beautiful. Her language is beautiful. You can even paint it on a picture. And it means things. And so a buddy was walking his dog. And I said, what's your dog's name? He goes, Misty. I said, oh, Messier Walk. He goes, what's that mean? I said, that's Misty. He goes, that's beautiful. Can you write that and make him out for me? So I said, come on in.  He goes, I'm going to take that to my wife.  And meet him up.  And boy, she comes running now. I was talking to him. And he goes, I said, you still call her that? You Missier Walk? I said, yeah. That's most probably about six months now. Simple things like that. It makes me happy. Even on my knees. She goes, when I'm talking now, in Mi'gma, she goes, I remember that uncle. I remember that school uncle. I said, wow. I said, I said, we remember your chance. And I was exposed to chance, making my chance when I was young. I was like, and I'm just getting learned and learning them now. And it opens my eyes. I never heard these since I was like four or five years old. And it's a new beginning. Our language is a high priority. I mean, I want to see that go in places. When you call in public, Que Medaulain, hello, how are you doing? I like to see places like that in public. Now they're doing that to band office. There's one, that part-time secretary, she always write on it. She's on it, man. And she talks Mi'gma to me all right off.  And she's there learning up there. That's just from a minute's point. And she whispers my ear and she's, what's up? I've got her, I got to learn. She wanted to, I was at New Year's, New Year's powwow. And she whispers my ear. How do you say, I want to wish you happy New Year's? I said, okay. And so it's either way. I'm so when she was, what did you say?  She's, wow, she's, I just learned I never knew that. And I said, it's simple things like that. How do you learn? Ask questions. Ask questions. And I learned that from my grandfather when I was six years old. When, what that word I, what I just said. Our culture bead, and my mother was a big beader. Oh, she was good with her hands. I mean, she did the beadwork like rose, non-fabric, like straight loom, everything. She worked with her hands. She did everything. She cooked. She was, she made pies, pies. Everybody loved her pies. Oh my God, she was best. And she, she learned. She taught people that little girls how to dance. Me, my dance, because she was brought up around that.  They got together at groups every week. My mom, my mom and the girls, the little girls, and we still got pictures of them. And all the little girls in their leather dresses, and they, she took them out to dance for people. And they had fun.  And they remember that today.  So, you know, I mean, she taught us a lot. I was like, wow, you remembered all that. She made these leather dresses for us and took us everywhere to dance. And I said, yeah, I know, I know. She did that. I didn't think you guys would remember, though. And this is maybe 20, 30 years later, 20, 35 years later. And they're still remembering this. I love it to see it more, more programs, even in the, like, off the reserve. There's like, we have one native lady who goes off the reserve in local schools. She maybe once or twice a week. But I like to see programs offered every day. A Mickey Mouse program in our local schools, like Dawn Reserve programs. We have it every day, that they're exposed to the language in there. Right from the Head Start kindergarten preschool, right from grade 12, one right to kindergarten, right to grade 12, they're exposed to language on the reserve. I like to see this off the reserve. Now they're maybe, they're lucky to be exposed to once, once a week, once a month. I like to be exposed more. We need more exposure for our language and our culture. Because I learned, in the 70s, going to elementary, and I still remember my, my lessons from a lady coming in. And that was, it was stuck right to me, what, what I learned. And it helped me, lady coming in, elder coming in from the, from our local res, coming to our schools, off the reserve. Because I, I did the day school too, and I did the off-reschool. But I learned a lot from her when she came in. And I still remember that day.