Barliman: trying the halting problem backwards, blindfolded - William Byrd, Greg Rosenblatt
ClojureTV3 HN recommenders · recommended in 2 months, 2017–2024
talk · intermediate · evergreen · 2017–2024 on HN
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.
HN people point to it as an amazing demonstration of relational programming and program synthesis that still looks exciting after LLM code generation.
Up next
18 mo on HNRuby Conf 12 - Y Not- Adventures in Functional Programming by Jim Weirich
Confreaks
17 HN recommender · 2013–2026
14 mo on HNThe Soul of Erlang and Elixir • Sasa Juric • GOTO 2019
GOTO Conferences
16 HN recommender · 2019–2024
14 mo on HN"Simple Made Easy" - Rich Hickey (2011)
Strange Loop Conference
14 HN recommender · 2022–2026
13 mo on HN"Making Impossible States Impossible" by Richard Feldman
elm-conf
9 HN recommender · 2017–2026
12 mo on HNWilliam Byrd on "The Most Beautiful Program Ever Written" [PWL NYC]
PapersWeLove
11 HN recommender · 2017–2026
11 mo on HNThe Value of Values with Rich Hickey
InfoQ
10 HN recommender · 2014–2023
12 mo on HNWhy Isn't Functional Programming the Norm? – Richard Feldman
Metosin
12 HN recommender · 2019–2025
11 mo on HNMaybe Not - Rich Hickey
ClojureTV
14 HN recommender · 2018–2025
11 mo on HNSolving Problems the Clojure Way - Rafal Dittwald
Clojure/north
10 HN recommender · 2019–2025
10 mo on HNLecture 1A: Overview and Introduction to Lisp
MIT OpenCourseWare
10 HN recommender · 2019–2026
10 mo on HNConway's Game Of Life in APL
Dyalog
11 HN recommender · 2010–2024
9 mo on HNLecture 1A | MIT 6.001 Structure and Interpretation, 1986
MIT OpenCourseWare
11 HN recommender · 2012–2024
4 comments from Hacker News
You might enjoy this amazing talk. I've linked to a part when the next 20 seconds of explanation turns the amazing up to 11. ▶ this video
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
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
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