Two years ago while hiking at Chautauqua Park at the end of LambdaConf, I first met Harold Carr. A fellow Lisper and a Jazz bass player, Harold is precise and relaxed. His main focus is a blockchain project that he works on at Oracle Labs.
Originally a Jazz musician on the road for ten years before being a programmer, when his daughter was four and his son was two he decided “I didn’t want to miss them growing up.” “I almost made the gigantic mistake of getting an MBA.” He “ended up in the Computer Science Department. And my plan was just to take a few courses non-matriculated … So when music was thin, I could make a few dollars. Trouble is, I got absolutely fascinated by it and ended up with a PHD. By mistake.” Ralph Waldo Emerson in his essay Experience says: “Where do we find ourselves? In a series of which we do not know the extremes, and believe that it has none.” How many of us became passionate about programming without expecting it? When does it take over as an endless joy?
Harold got his start in Lisp, a language with minimal syntax that is the origin of many functional programming concepts: “It just knocked me out.” “I was fortunate enough when I entered the department at the University of Utah to have run in immediately to Martin Griss who was just leaving to be a director of research over at Hewlett Packard … I went to his office (this is before he hired me) and I said wow this language is so great. Is there work in it? Can I get a job? And he said: ‘no.’ And I said: ‘of course not.’ In literature I love poetry, which of course is a total niche thing nobody pays you for poetry, for the most part…In music I love Jazz, another niche thing that’s really hard to make a living in. And of course, I picked a language that is a niche thing, you can’t make a living at it. I figure this is just par for the course. Fortunately, I did actually make a living at it.”
Harold and Paul Hudak were both at the University of Utah at the same time: “He was telling me about Haskell early on. He said you couldn’t do heterogeneous lists.” Harold thought: “Why would anyone want a language like that? That’s crazy!” A heterogenous list just being a list where the items can be of different types (Haskell now does support heterogenous lists). “If the program is data and it’s just a list structure: you have to have a heterogenous list…it was a lot, lot later when I discovered Haskell and typed functional programming.”
“My initial specialty was Lisp programing design and compiler writing. We got funded by various people - Schlumberger, Fairchild, Hewlett Packard - to do this thing that one of the ex-professors that then worked at HP-labs was building a multiprocessing machine that was connected in a twisted toroidal mesh … We were doing Lisp for that, but, then of course the funding changes said: ‘you have to do C++.’
So I did C++, long story short, we were making computers communicate. I became a “remoting” expert. Remoting just means at a level above the network … you make computers talk to each other and that’s things like DCE and SOAP and CORBA and various RPC mechanisms. … So I did that for a very long time at Sun and then I became interested in blockchain thanks to a person here in Utah named Phil Windley … And he told me at a Meetup, Blockchain is the thing you need to check out.”
Currently Phillip J. Windley is the chair of the Sovrin Foundation who called it “An Internet for Identity.” A good introduction to Sovrin by Windley is the article: Is Sovrin Decentralized?
This is around the same time that Harold rediscovered Haskell. According to wiki.haskell.org/Introduction:
Haskell is a computer programming language. In particular, it is a polymorphically statically typed, lazy, purely functional language, quite different from most other programming languages. The language is named for Haskell Brooks Curry, whose work in mathematical logic serves as a foundation for functional languages. Haskell is based on the lambda calculus, hence the lambda we use as a logo.
Harold continued: “and that became basically what I’m doing now is blockchain research at Oracle labs and we’re using Haskell as our language to write everything in and to design and run our experiments.” I asked how Lisp helped prepare him for Haskell:
“Only in respect with the recursion. I felt very comfortable with recursion. If there was not a for loop, no problem. Some people that have only programmed in imperative languages, the minute there’s no while loops or for loops or anything like that, they can throw you for a loop! Actually I used to get frustrated with Java because I couldn’t write everything in recursion because, Java? You’d blow the stack too easily. I always wanted to write recursively and couldn’t. Lisp prepared me recursively, but not much else.”
I asked what a new functional programmer should study:
“If you’re talking about Haskell, which I actually think is the right language. Haskell, because of its laziness and because if you do something that has a side effect it shows up in the type signature, it forces you to really do functional programming. In ML you can cheat. In F# you can cheat. You can just do a side effect anywhere you want and it doesn’t show up in the type signature. You can have tools look for that stuff, but I would rather have the tool be the typechecker.
For me I would recommend Haskell and if you’re brand new to it, I would recommend Chris Allen and Julie Moronuki’s book. Their book unfortunately came about two years too late for me. I’d already gone through most of the pain myself of the things you’d learn in the book. But their book’s nice, it really shows you. Sometimes with arrows to show you the space between these two things means this. Sometimes that can get really confusing.”
The book is entitled Haskell Programming from first principles. If you are a new functional programmer looking to get started at LambdaConf, this is a great read to get started with before you arrive. I cannot describe their approach better than their own website:
Our approach is based on experience teaching Haskell to many people from a variety of walks of life, and the approach pays off. Spaced repetition and iterative deepening are effective strategies for learning, and we rely on those techniques throughout the book. You may notice we mention something only briefly at first, then return to it over and over. As your experience with Haskell deepens, you have a base from which to move to a deeper level of understanding. By working through exercises and returning to concepts you’ve seen earlier in the book, you develop a solid intuition for the functional style of programming.
This book is designed to help you get to a place where you could begin applying Haskell to the everyday problems you want to solve. It can also serve as a bootstrap suitable for beginning to learn programming language and type theory. Readers of this book have found that a facility for Haskell can translate into better F#, Scala, or Swift code. This is partly because Haskell pushes you to write the code you should be writing in functional’ish languages anyway.
Harold and I turned to different concepts that a new Haskell programmer should learn:
“Over time you’re going to run into Monads, right away. They turn out to be really useful. In a certain sense, monads let you write imperative programmings, but they’re not imperative. An imperative program says: ‘Do this. Then do this. Then do this. Then do this. Then do this. And maybe do this depending on the step before or do something else like an if statement. With a monad, you can write in that style but its still pure unless you’re in IO. So you’re going to run into monads right away.
The thing is, rather than reading monad tutorials, you’re better off just looking at the simpler monads like maybe or either. Just seeing what the monad definition is. It’s just doings some code under the covers so that you don’t have to do it in your code. Then when you get into slightly more complicated monads like state, they’re still just doing some things underneath the covers that allow you to pass some parameters around even though you don’t even see those parameters in your program. Don’t start with monads. Fibonnaci is always the good one to write. Monads come whether you like it or not; they show up. And, of course, if you really want to know monads, you read Alejandro’s book, The Book of Monads.”
I asked: “Do you have any challenge programs you think are worth writing?”
“When I do interviews, I tend not to go for challenge programs. I really don’t like those things. I want to know about Haskell strings. ‘Tell me about Haskell Strings!’ Unfortunately Haskell has three main kinds of strings. In a way there’s even a few more … There’s one you want to avoid.
I’ll definitely ask some certain things about exceptions because exceptions turn out to be very tricky in Haskell. And the world expert, I think, on exceptions is Michael Snoyman who of course is teaching Applied Haskell again at LambdaConf this year. I took it the previous two years and just learned so much. I’d even take it again this year, but don’t have the time to do it. I’ll miss it this year. Even though he’s repeating some of the same material, it’s just worth sitting through again. Michael’s an excellent teacher and super knowledgeable, and a really great teacher, too. He just really knows his stuff and presents it well.”
Next we moved on to Harold’s talk:
“It’s a work we did as part of our blockchain research. We have as one of our smart contracts and smart contract is a fancy word for saying it’s just some code that runs when somebody submits something to your blockchain. It’s the thing that interprets what that is and decides what to do. I don’t know why its called smart. It’s code that runs on the blockchain.
For one of our smart contracts we just have a key-value store, but we do a thing where our key-value store might not be complete. We bring verifiers in and ou of the consensus protocol. So for scaling we do sharding and plus dynamic membership. We have somebody join, but if they join and now their key -value store is not going to be up-to-date with the consensus of the world. To get it up-to-date you’ve got to send the whole thing to them and of course it might be a gigabyte thing. And you only need two keys out of it so that’s kind of overkill.
So we started doing some experiments where we had pages. Even though it was just a map, it would be broken up into pages. We’d also have caches, too. So when you started up we would give you maybe the cache and the rest would be empty. And if somebody was lucky enough and you probably would be because the cache usually has all the most recent things: great! That’s all they needed. It’s a much smaller thing.
But when they did get a page miss, then we go on the network and go grab a page from somebody else. That page comes back not only with the data, but a proof that the data is correct. And that’s another big deal with these kinds of systems. Not only do you want to ask if the value is present, but prove to me it was present in your thing. You get the value back in a proof of how you got that value. The person who receives the value can verify that the proof is correct.
We’re layering all of this stuff onto just a map interface; an API. So we wanted a way to add caches,, bloom filters and a paged system, but we didn’t want the API to change. The way we did that is basically like monad transformers where you can put in a cache, like that’s the first level thing that anyone using the API will hit. That’s the implementation, they don’t see that. And if it’s in the cache great. It’ll give you that. If not it sends it through to the bloom filter.
The bloom filter will say whether it’s not there or maybe it is there. So you can reject things early. If makes it through the bloom filter then it will hit the pages. If it’s in the page great, it will not only get your value from the page, but it will also put the value in the cache. But if its not there it will say its not there and an out of band mechanism would get a new page for you and install it. We wanted to be able to do different versions of that and do timing measurements and such all behind the scenes.
So that is what my talk is about , not the blockchain part, but how to build a single API and yet plug in different capabilities of how that API will behave. The main thing about that is the monad transformer trick, so every layer that you add just transforms the value up to the next layer. It lifts it up to the next layer. That way the API, your code that’s using it doesn’t change at all. Just the implementation.”