On 9/5/2019 9:05 AM, Adam Golding wrote:
What is the shortest/smallest racket program (ithat enumerates all and only valid racket programs?

You might be interested in the logic-programming/constraint-solving language named miniKanren.


miniKanren can solve puzzles like these:
generate ( all ! ) programs that print "I love you"
generate ( all ! ) programs that reproduce themselves
generate ( all ! ) pairs of programs (A,B) where A prints B and B prints A
generate programs from examples of what they are supposed to do.

One trick solves all these puzzles.
Given the source code of an interpreter named eval, miniKanren can solve equations like this:

  (equal? (eval '(<program-with-missing-part> example1)) 'desired-result1)
  (equal? (eval '(<program-with-missing-part> example2)) 'desired-result2)
... )

The search strategy is complete. It will eventually check everything in the search tree. It will not get stuck.

Josh Rubin

You received this message because you are subscribed to the Google Groups "Racket 
Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to racket-users+unsubscr...@googlegroups.com.
To view this discussion on the web visit 

Reply via email to