Research | Selected Publications | Upcoming Talks | Recent Talks | Interviews | Teaching

Research Interests

Programming Languages and Program Synthesis

For over ten years I have been working on miniKanren, an embedded domain-specific language for constraint logic programming. I am especially interested in using miniKanren to write programs as relations, without distinguishing between input and output arguments. Over the past decade my colleagues and I have developed relational interpreters, term reducers, type inferencers, and theorem provers, all of which are capable of program synthesis, or of otherwise running "backwards." miniKanren is described in The Reasoned Schemer (MIT Press, 2005).

To explore how relational programming can be used for program synthesis we have created a prototype interactive editor, Barliman, that can synthesize higher-order, recursive Scheme functions from example inputs and outputs. In addition to investigating software engineering applications of Barliman, I am working with Molly Feldman and others in Erik Andersen's lab at Cornell on adapting Barliman for educational uses, including automated tutoring.

In addition to relational programming, I am very interested in functional programming, especially in Scheme, Racket, Clojure, and other Lisps. I'm a member of the Scheme and Functional Programming Workshop steering committee, organized the 2013 Scheme and Functional Programming Workshop, and have served on the program committees for the International Conference on Functional Programming (2015), the Scheme and Functional Programming Workshop (2013 and 2014), the International Workshop on Functional and (Constraint) Logic Programming (2014), and the International Lisp Conference (2014). I have given invited talks and tutorials at a variety of functional programming conferences and workshops.

Biology and Medicine

Recently I have become extremely interested in biology, especially synthetic biology. I took a intense two-week wet-lab synthetic biology course at Cold Spring Harbor Laboratory in the summer of 2015. Since then I have been helping the Bertozzi lab at Stanford and the Woo lab at Harvard on improving their IsoStamp software for glycoprotein analysis using tandem mass spectrometry. I have begun helping the Bild lab at Utah with low-cost wet-lab automation, and have been helping the Myers lab at Utah with their work on the Synthetic Biology Open Language (SBOL) and their libSBOLj library. Most recently I have begun working with the Institute for Genomic Medicine at Columbia University's College of Physicians and Surgeons, exploring how to scale genome analytics to tens of thousands of human genomes.

I suspect there are applications of our program synthesis technology to biology and medicine, as has been demonstrated by other researchers in the synthesis community. Finding important problems that might benefit from our approach to synthesis will require collaboration with scientists in these domains.

I have also become interested in the possibilities of using CRISPR/Cas to perform computation inside of living cells, as well as using cell signaling to perform "object-oriented" programming within living tissue. (Indeed, object-oriented programming was originally inspired by cell signaling!)

I am interested in applications of scanning probe microscopy to molecular biology and nanotechnology, including direct imaging and manipulation of biomolecules. To better understand the principles involved, I am building a scanning tunneling microscope capable of atomic resolution with my father and several friends, based on a low-cost open-source design by Dan Berard.

I am looking for collaborators who are interested in these—or related—problems.

Selected Publications

Theses

William E. Byrd
Relational Programming in miniKanren: Techniques, Applications, and Implementations.
Indiana University, Bloomington, IN,
September 30, 2009.
[Full Dissertation (PDF file)]
[Easier to read, single-spaced, re-typeset version (PDF file), released under Creative Commons Attribution 4.0 International (CC BY 4.0) license.]

Books

Daniel P. Friedman, William E. Byrd and Oleg Kiselyov
The Reasoned Schemer.
The MIT Press, Cambridge, MA, 2005.
[Complete source code from the book--R5RS Scheme (GitHub)]

Refereed conference and workshop papers

William E. Byrd, Daniel P. Friedman, Ramana Kumar, and Joseph P. Near.
A Shallow Scheme Embedding of Bottom-Avoiding Streams.
To appear in a special issue of Higher-Order and Symbolic Computation, in honor of Mitchell Wand's 60th birthday.
[Preprint (PDF file)]

William E. Byrd, Michael Ballantyne, Greg Rosenblatt, Matthew Might.
Functional Pearl: A Unified Approach to Solving Seven Programming Problems.
In Proceedings of the 22nd ACM SIGPLAN International Conference on Functional Programming (ICFP 2017), Oxford, 2017.
[Paper (ACM Digital Library, Open Access)]
[Talk]
[Reusable Artifact]
[Interactive version of paper, courtesy of Nada Amin]

Jason Hemann, Dan Friedman, William E. Byrd, Matt Might.
A Small Embedding of Logic Programming with a Simple Complete Search.
In Proceedings of the Dynamic Languages Symposium 2016 (DLS '16), Amsterdam, 2016.
[Paper (ACM Digital Library)]

Dakota Fisher, Matthew Hammer, William E. Byrd, Matthew Might.
miniAdapton: A Minimal Implementation of Incremental Computation in Scheme.
In Proceedings of the 2016 Workshop on Scheme and Functional Programming, Nara, Japan, 2016.
[Full paper (PDF file)]
[Complete source code--R6RS Scheme (GitHub)]

Steven Lyde, William E. Byrd, Matthew Might.
Control-Flow of Dynamic Languages via Pointer Analysis.
In the 11th Dynamic Languages Symposium (DLS) at SPLASH 2015, October 27th, 2015.

William E. Byrd, Eric Holk, and Daniel P. Friedman.
miniKanren, Live and Untagged: Quine Generation via Relational Interpreters (Programming Pearl).
In the Proceedings of the 2012 Workshop on Scheme and Functional Programming, Copenhagen, Denmark, 2012.
[Full paper (PDF file)]
[Complete source code--R6RS Scheme (GitHub)]

Claire E. Alvis, Jeremiah J. Willcock, Kyle M. Carter, William E. Byrd, and Daniel P. Friedman.
cKanren: miniKanren with Constraints.
In Proceedings of the 2011 Workshop on Scheme and Functional Programming (Scheme '11), Portland, OR, 2011.
[Full paper (PDF file)]
[Complete source code--R6RS Scheme (GitHub)]

Eric Holk, William E. Byrd, Nilesh Mahajan, Jeremiah Willcock, Arun Chauhan, and Andrew Lumsdaine.
Declarative Parallel Programming for GPUs.
In Proceedings of the International Conference on Parallel Computing (ParCo), Ghent, Belgium, 2011.
[Complete source code--R6RS Scheme (GitHub)]
[Full paper (PDF file)]

Eric Holk, William E. Byrd, Jeremiah Willcock, Torsten Hoefler, Arun Chauhan, and Andrew Lumsdaine.
Kanor: A Declarative Language for Explicit Communication.
In Proceedings of the Thirteenth International Symposium on the Practical Aspects of Declarative Languages (PADL),
Austin, TX, pp. 190-204, 2011.
[Full paper (PDF file)]

Andrew W. Keep, Michael D. Adams, Lindsey Kuper, William E. Byrd, and Daniel P. Friedman.
A Pattern-matcher for miniKanren -or- How to Get into Trouble with CPS Macros
In Proceedings of the 2009 Workshop on Scheme and Functional Programming,
Cal Poly Technical Report CPSLO-CSC-09-03, pp. 37-45, 2009.
[Full proceedings (PDF file)]

Joseph P. Near, William E. Byrd and Daniel P. Friedman.
alphaleanTAP: A Declarative Theorem Prover for First-Order Classical Logic
In Proceedings of the 24th International Conference on Logic Programming (ICLP 2008),
LNCS vol. 5366, Springer-Verlag, Heidelberg, pp. 238-252, 2008.
[Full paper (PDF file)]
[Complete source code--R6RS Scheme and Prolog (.zip file)]

Oleg Kiselyov, William E. Byrd, Daniel P. Friedman and Chung-chieh Shan
Pure, declarative, and constructive arithmetic relations (declarative pearl)
In Proceedings of the 9th international symposium on functional and logic programming,
ed. Jacques Garrigue and Manuel Hermenegildo, pp. 64-80.
LNCS vol. 4989, Springer, 2008.
[Full paper (PDF file)]

William E. Byrd and Daniel P. Friedman
alphaKanren: A Fresh Name in Nominal Logic Programming
Proceedings of the 2007 Workshop on Scheme and Functional Programming,
Universite Laval Technical Report DIUL-RT-0701, pp. 79-90.
[Full paper (PDF file)]
[Author's revised version (recommended) (PDF file)]
[Revised R5RS-compliant source code (.scm file)]

William E. Byrd and Daniel P. Friedman
From Variadic Functions to Variadic Relations: A miniKanren Perspective.
Proceedings of the 2006 Scheme and Functional Programming Workshop,
University of Chicago Technical Report TR-2006-06, 2006, pp. 105-117.
[Full paper (PDF file)]

Upcoming Talks

Recent Talks, Tutorials, and Summer Schools

The Most Beautiful Program Ever Written
Papers We Love, New York, NY, April 12, 2017.

Synthesis of Lisp Programs
LispNYC, New York, NY, April 11, 2017.

Relational programming
KatsConf 2, Dublin, February 18, 2017.

Thinking About Recursion (with Nada Amin)
KatsConf 2, Dublin, February 18, 2017.

Barliman: Trying the Halting Problem Backwards, Blindfolded (with Greg Rosenblatt)
Clojure/conj, Austin, TX, December 3, 2016.

New Tools and Practices for Online Collaboration in Teaching, Learning, and Research of Programming Languages
Off-the-Beaten Track (co-located with POPL 2016), St. Petersburg, FL, January 23, 2016.

The Promise of Relational Programming
Partial Evaluation and Semantic-Based Program Manipulation (PEPM 2016), San Diego, CA, January 18, 2016.

miniKanren, a Language for Relational Programming} (CS242 guest lecture)
Stanford University, Stanford, CA, November 30, 2015.

A Vision for Relational Programming in miniKanren
Code Mesh 2015, London, England, November 4, 2015.

Concatenative Programming (with Rob Martin)
Code Mesh 2015, London, England, November 2, 2015.

Interpreting Scheme procedures as logic programs using miniKanren (with Michael Ballantyne)
Scheme and Functional Programming Workshop, Vancouver, Canada, September 4, 2015.

Summer School on Relational Programming (sponsored by JetBrains, courtesy of Dmitri Boulytchev)
St. Petersburg, Russia, August 24--28, 2015.

The Promise of Relational Programming
PolyConf, Poznan, Poland, July, 2015.

Write a Relational Scheme Interpreter in miniKanren
PolyConf, Poznan, Poland, July 2, 2015.

Concatenative Programming (with Rob Martin)
Lambda Lounge Utah, Sandy, UT, May 12, 2015.

Program Synthesis Using miniKanren (with Daniel P. Friedman)
Strange Loop, St. Louis, MO, September 17, 2014.

miniKanren Summer School (with Daniel P. Friedman and Jason Hemann)
University of Utah, Salt Lake City, UT, May 27 and 29, 2014

Logic Night
Lambda Lounge Utah, Sandy, UT, May 13, 2014

We Need Real Tools for Generating Type Inferencers (with Nada Amin)
Off-the-Beaten Track (co-located with POPL 2014), San Diego, CA, January 25, 2014.

miniKanren Tutorial (with Daniel P. Friedman)
Practical Aspects of Declarative Languages (PADL), San Diego, January 23, 2014.

Relational Programming in miniKanren
The Computer Laboratory, University of Cambridge, Cambridge, England, December 6, 2013.

Meta-Programming in Logic Programming (with Nada Amin)
Code Mesh 2013, London, England, December 5, 2013.

From Greek to Clojure! (with Nada Amin)
Clojure/conj, Alexandria, VA, November 14, 2013.

A Relational Exploration of the Chomsky Hierarchy (with Daniel P. Friedman)
Strange Loop, St. Louis, MO, September 18--20, 2013.

Program Transformations (with Nada Amin)
Lambda Jam, Chicago, IL, July 9, 2013.

Fun with Relational Interpreters in miniKanren (with Daniel P. Friedman)
flatMap, Oslo, Norway, May 14, 2013.

The Unreasonable Schemers (guest of honor, with Daniel P. Friedman)
miniKanren Confo (associated with Clojure/West), Portland, OR, March 19, 2013.

miniKanren Philosophy (with Daniel P. Friedman)
Clojure/conj, Raleigh, NC, November 16, 2012.

Relational Programming in miniKanren (with Daniel P. Friedman)
Strange Loop, St. Louis, MO, September 24, 2012.

miniKanren, Live and Untagged: Quine Generation via Relational Interpreters
Scheme and Functional Programming Workshop, Copenhagen, Denmark, September 9, 2012.

Declarative Parallel Programming
Computer Science Department, Colorado State University, Ft. Collins, CO, February 29, 2012.

3D Printing, Open Hardware, and the DIY Revolution
CATALYST, Informatics and Computing Student Association, Indiana University, Bloomington, IN, February 18, 2012.

Generating Quines Using a Relational Interpreter
Indiana University Logic Seminar, Bloomington, IN, February 15, 2012.

3D Printing, Open Hardware, and the DIY Revolution
Technology Management Club, Kelley School of Business, Indiana University, Bloomington, IN, February 7, 2012.

miniKanren ("Untalk", with Daniel P. Friedman)
Clojure/conj, Raleigh, NC, November 10, 2011.

3D Printing, Open Hardware, and the DIY Revolution
Mechanical Engineering Technology (MET) Department, Purdue University, West Lafayette, IN, October 12, 2011.

Animatronic Kittehs, 3D Printers, and Rogue Game Studios --or-- Why Computer Science Education Should be Just-in-Time, not Just-in-Case, and Why (Epic) Failure Should Always be an Option
Indiana University Programming Languages Group, Bloomington, IN, April 15, 2011.

Interviews

Mostly Erlang Episode 050 -- miniKanren With William Byrd
Recorded by Zachary Kessin, Thursday, November 13, 2014.

Functional Geekery Episode 9 -- William E. Byrd
Recorded by Proctor, Monday, April 21, 2014

William Byrd on Logic and Relational Programming, miniKanren
Recorded by InfoQ at Code Mesh 2013, London, England, December, 2013

Teaching

C211 Introduction to Computer Science (undergraduate)
Course Instructor, Fall 2011 (Honors Section), Fall 2010 (Honors Section), Summer 2005
Associate Instructor, Honors Section, Fall 2003

C311 Programming Languages (undergraduate)
Associate Instructor, Spring 2009, Fall 2008, Spring 2008, Fall 2007, Spring 2007, Fall 2006, Spring 2006, Fall 2005, Spring 2005, Fall 2004, Spring 2004

B521 Programming Languages (graduate)
Associate Instructor, Fall 2008, Fall 2007, Fall 2006, Fall 2005, Fall 2004

A290 Tools for Computing: Arduino Development
Course Instructor, Spring 2012

Stanford Talk resources (November 2015)

St. Petersburg relational programming course resources (summer 2015)