Will Crichton

Good Ideas For Free

Here are some ideas that I worked on a bit, but haven't had time to keep exploring. If any of them are exciting to you, please reach out and I would love to chat!

1. It should be possible to build a garbage-collected programming language on top of a non-GC language, and get the standard library for free! For instance, there should be a version of OCaml built on Rust that doesn't need to reimplement Vec or HashMap. See: Gradual Programming, Rust: The New LLVM and willcrichton/lia.
2. When a CS teacher gets 100 solutions from students to a new assignment, the teacher should have tools that help them explore the commonalities and differences between solutions. I worked on this a bit [4]. See also "Generative Grading: Neural Approximate Parsing for Automated Student Feedback" for another cool concept in this space.
3. Trait-based languages like Rust have a Turing-complete logic-programming-esque computation model embedded into their type system. I built Tyrade to show that it's possible to translate a sensible functional language into traits. But the translation is limited and I never formally proved the kind of relationship between these languages.
4. Probabilistic programming languages offer an unprecedented new capability to model problems involving uncertainty. But most PPL texts focus on teaching the mechanics of the language rather than how to map a domain task into a probabilistic program. Can we systematically describe a translation from uncertain tasks to probabilistic programs? See: Compiling Knowledge into Probabilistic Programs.
5. Programmers often intuit that a particular API has a more direct mapping to a domain than another API, such as how many Python libraries are marketed as for humans. How can we quantify the concept of direct mapping? For example, I created the Expressiveness Benchmark as a first pass on this question for tabular data processing APIs. Here's a really cool idea: imagine if you (1) embedded a bunch of APIs into a theorem prover, (2) implemented the same task in each API, and (3) wrote a proof of correctness for each implementation. Does the smallest proof corresponds to the most direct mapping?
6. Intro to discrete math and intro to probability courses share the same problem: students get caught up in the syntax, and then fail to understand the underlying concepts. (Example: what is the type of the $P$ operator in probability?) Is it possible to improve students' learning experience with the introduction of a theorem prover or probabilistic programming language, respectively? For example, see Logic and Proof, a logic textbook written using Lean, and the Let's Chance project from MIT Media Lab.
7. When programmers have questions about an API, they only use documentation and StackOverflow, rarely looking at the source code. That's not unreasonable: production-grade libraries have multiple layers of abstraction that make it hard to explore code. What if we equipped programmers with spelunking tools that could break through these abstractions? For example, I worked on Inliner, a tool that uses source-to-source compiler optimizations to show how a library works in the context of an example. See also: Partial evaluation as an aid to the comprehension of Fortran programs and Amorphous program slicing.
8. Scientists learning to program in R have to deal with the language's god-awful ergonomics and error messages. How can tooling provide contextual assistance to help learners better understand how the langauge works? I built a prototype Auto TA for RStudio which learners seemed to really enjoy.
9. System designers have a vocabulary of common system components that recur across domains: state machines, event registries, access control, so on. I've always thought that design patterns should be articulated in terms of these kinds of components, not stuff like a visitor. For example, I wrote a mini-book Type-Driven API Design in Rust that shows how to idiomatically express system components in Rust, and what mistakes you can catch at compile-time with careful design. But I think a more systematic enumeration of these kinds of system idioms would be really interesting. See also: domain-driven design.
10. For sufficiently well-defined and low-level programming tasks, it should be possible to build a probabilistic cognitive model that could accurately predict a person's behavior in solving the task. For example, after publishing The Role of Working Memory in Program Tracing [3], I explored the idea of modeling a person as a lossy interpreter, and whether you could tune the lossiness parameters to explain the range of observed human traces. The models actually worked, although I never figured out what a useful application of such a cognitive model would be. Maybe you can!