3 HN users recommended this talk2 months2017–2024score 2.5
Years with an HN recommendation, 2007–2026
HN people point to it as an amazing demonstration of relational programming and program synthesis that still looks exciting after LLM code generation.
A Clojure/conj 2016 talk demoing Barliman, a prototype smart editor that does program synthesis. Given a partial program and tests, it completes the program using a relational interpreter written in miniKanren.
“I work on miniKanren, which is a logic programming language with a complete search that doesn't hit the nontermination issues you mention.” (HN, 2017)
For anyone who finds this topic interesting, you might be interested in the following resources: [link] The second edition of `The Reasoned Schemer` (MIT Press, 2018): [link] The Clojure/conj 2016 talk Greg Rosenblatt and I gave on Barliman: [this video] `A Unified Approach to Solving Seven Programming Problems (Functional Pearl)`, William E. Byrd, Michael Ballantyne, Gregory Rosenblatt, Matthew Might (ICFP 2017) (Open Access): [link] and the related talk: [link] and Nada Amin's interactive version of the paper: [link] Cheers, --Will
Have you checked out any of the minikanren logic programming environments people have implemented in scheme? The Reasoned Schemer is an accessible introduction to that space if you’re not put off by the socratic-themed dialogue. & the Barliman demo is still pretty exciting even after LLM codegen. [this video]
Other search algorithms can take up lots of memory to store progress they've made down different paths. Having only one active state also lets you map unification down to efficient low level cpu operations. If you have multiple states, you either have to copy lots of data when you fork the state or you use a persistent data structure but can't use side effects, so everything is a bit slower. It's a tradeoff though. I work on miniKanren, which is a logic programming language with a complete search that doesn't hit the nontermination issues you mention. The complete search lets us do some pretty cool stuff with program synthesis (though we're not about to put any programmers out of business just yet): [this video] Note that you can implement iterative deepening depth first search on top of prolog if you want a complete search there. Iterative deepening takes a little more time but avoids the memory problems with breath-first. SWI has tools built in to help there: [link] And I believe Ciao implements its iterative deepening library with a meta-interpreter: [link]
Program synthesis with miniKanren's complete search
Video list and Hacker News comment labels from HackerTube (prompted by @karpathy), released under ODC-By 1.0, built on the open-index/hacker-news archive. Hacker News data is provided by Y Combinator; comments remain the work of their authors. Video titles, channel names and thumbnails belong to their creators and are shown via YouTube. HackerTube Watch is an unofficial edition. Data export of 2026-10-31.
Plays via YouTube's privacy-enhanced embed
4 Hacker News comments
From the HN archive; up to 20 kept per video, favoring different commenters. Recommendations first.
Citations, criticism and jokes
Read more