Daniel Friedman Code Mesh 2016 Interview

Daniel Friedman will be giving a talk at Code Mesh 2016 with Jason Hemann. He is Professor of Computer Science at Indiana University and the co-author of many great books, including The Little Schemer. His talk is about microKanren.

Follow him on Twitter and visit his homepage.

PurelyFunctional.tv: How did you get into functional programming?

Daniel Friedman: In the Fall of 1965, my extraordinary professor, Elliot Organick, handed out to the class, a mimeographed book, called The Lisp 1.5 Programmer's Manual. I was in seventh heaven. I knew I was holding in my hands one of the most interesting documents I had ever seen. Reading it was nearly impossible, but so what. The programs in the book were beautiful to behold and some day, who knew how far into the future, I would completely understand this book.

Every language I was aware of back then was imperative. I had had my fill of effects (It is a terrible way to program, unless all the effects are derived.) and I was now open to mathematical reasoning. I started teaching these ideas when I got to graduate school in Fall of 1967 and have quite literally never stopped teaching them except for a few other courses where it did not seem appropriate, like "Fortran for Freshman", etc. But, whether I am programming in Lisp, Scheme, or Racket, it is all functional programming to me. Whether I have functions as values, it is all Lisp to me. Lisp is programming in a functional fashion, where you can think about Natural Recursion, to convince yourself that you are writing your programs so that recursions on finite structures will always terminate. It does not matter whether the finite structures are lists, numbers, trees, etc.

Lisp was a wonderful invention and recursion was a fantastic way of reasoning. When I joined the faculty of The LBJ School of Public Affairs in the Summer of 1971 (I gave the first lecture at the new school to only faculty and it was in Lisp.), I was asked to teach their soon to be arriving first graduate students Lisp, among other programming languages and among other mathematical subjects. I had watched students repeatedly be able to do what others thought was really hard or impossible. It had really impressed me that programming without state could be so easy and so much fun.

PF.tv: Very briefly, what is your talk about?

DF: microKanren and its implementation and why you might care. microKanren is a tiny language with a very small implementation (under 50 lines) for doing relational (logic) programming that is so simple, that re-implementing it in your favorite language is quite an easy exercise and has been done many times. This allows relational programming to snugly fit into you favorite language. Jason Hemann (my current doctoral student) and I will be showing you how to do it and we will be talking about what makes it even easier to extend microKanren to miniKanren. This will lead to shorter programs that do the same thing that can be done in microKanren. So, it is worthwhile to invest a few more minutes to give the full feel of miniKanren.

PF.tv: What concepts do you recommend people be familiar with to maximize their experience with the talk?

DF: Comfort with at least one functional language, say the functional subset of Scheme that appears in The Little Schemer. The syntax for defining functions in Racket or MIT Scheme:

(define (((foo x y s) a b) c) ...) is the same as

(define foo
  (lambda (x y s)
    (lambda (a b)
      (lambda (c) ...))))

PF.tv: What is the weirdest language someone has implemented microKanren in?

DF: I don't know, perhaps microKanren in microKanren with constraints, but I do know that there is a reasonable chance you'll find it at miniKanren.org.

PF.tv: What is the most interesting application of relational programming in industry or academia?

DF: I think the work that my former student Will Byrd is doing with synthesis is quite fascinating. Start with a miniKanren interpreter for Scheme and then use that interpreter to process Scheme programs. This will yield Scheme programs with the familiar relational properties. Once that is done, Will is able to drop variables into the code a little at a time and have his system infer what is missing, even in skeletons of recursive programs. Take a look at Barliman, which clarifies how synthesis via relational interpreters are interesting and useful.

PF.tv: What resources are available for people who want to study up before the talk?

DF: miniKanren.org (lots of videos and pointers to implementations).

PF.tv: Where can people follow you online?

DF: I have a twitter account, but rarely have time to pursue it.

PF.tv: Are there any projects you'd like people to be aware of? How can people help out?

DF: My current project is to finish a second edition of The Reasoned Schemer, We have learned a lot in the last decade, some of which painstakingly describes the microKanren implementation in the tradition of "Little" books. People can help out by letting one of my co-authors of the book: Will Byrd, Oleg Kiselyov, and Jason Hemann know about their willingness to be a reader.

PF.tv: Where do you see the state of functional programming in 10 years?

DF: With the advent of security as a major field of computer science, I expect functional programming and theorem proving using proof assistants (writing theorems as types and proofs of the theorems as programs of the types) will soon be standard fare as background of a Bachelor's Degree in Computer Science. See Aaron Stump's Verified Functional Programming in Agda, which he uses to teach undergraduates.

I would like to think that with the passage of another 10 years, there will be no computer programmer who is not fluent in multiple functional programming languages (both typed and untyped) for various tasks. Back when I became enamored of functional programming, I thought this would happen overnight once people truly understood what they were missing, but apparently I was just a bit too optimistic. And in my wildest dreams for the next decade, I would hope that all programming would be done with a proof of the program's correctness.

PF.tv: If functional programming were a superhero, what superpower would it have?

DF: "Lambda the Elephant"'s ability to never forget. (The elephant's name in The Little Schemer is "Lambda".)

Thanks for the interview!

You are welcome,

Dan Friedman