William E. Byrd

email

Research and Teaching Interests: Programming Languages and Program Synthesis, Biology and Medicine

Education:

  • BS, College of Charleston, Special Education
  • BS, University of Maryland, Computer Science
  • PhD, Indiana University, Computer Science

William Byrd.For over 10 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).

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.

Download CV (pdf)

  • CS 211: Introduction to Computer Science
  • CS 311: Programming Languages (undergraduate)

Programming Languages and Program Synthesis

For over 10 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.

  • Daniel P. Friedman, William E. Byrd and Oleg Kiselyov, The Reasoned Schemer (Cambridge, MA, 2005).
  • William E. Byrd, Daniel P. Friedman, Ramana Kumar, and Joseph P. Near. A Shallow Scheme Embedding of Bottom-Avoiding Streams. Forthcoming, to appear in a special issue of Higher-Order and Symbolic Computation
  • William E. Byrd, Michael Ballantyne, Greg Rosenblatt, Matthew Might. Functional Pearl: A Unified Approach to Solving Seven Programming Problems. Proceedings of the 22nd ACM SIGPLAN International Conference on Functional Programming (ICFP 2017), Oxford, 2017.
  • Jason Hemann, Dan Friedman, William E. Byrd, Matt Might. A Small Embedding of Logic Programming with a Simple Complete Search. Proceedings of the Dynamic Languages Symposium 2016 (DLS '16), Amsterdam, 2016.
  • Dakota Fisher, Matthew Hammer, William E. Byrd, Matthew Might. miniAdapton: A Minimal Implementation of Incremental Computation in Scheme. Proceedings of the 2016 Workshop on Scheme and Functional Programming, Nara, Japan, 2016.
  • 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). Proceedings of the 2012 Workshop on Scheme and Functional Programming, Copenhagen, Denmark, 2012.
  • Claire E. Alvis, Jeremiah J. Willcock, Kyle M. Carter, William E. Byrd, and Daniel P. Friedman. Kanren: miniKanren with Constraints. Proceedings of the 2011 Workshop on Scheme and Functional Programming (Scheme '11), Portland, OR, 2011.
  • 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.