Listing All Programs

55 views
Skip to first unread message

Adam Golding

unread,
Sep 5, 2019, 9:05:48 AM9/5/19
to Racket Users
What is the shortest/smallest racket program (ithat enumerates all and only valid racket programs?

Adam Golding

unread,
Sep 5, 2019, 9:06:30 AM9/5/19
to Racket Users
*that

David Van Horn

unread,
Sep 5, 2019, 9:31:06 AM9/5/19
to Adam Golding, Racket-Users List
What do you mean by valid?

On Thu, Sep 5, 2019, 9:05 AM Adam Golding <adamg...@gmail.com> wrote:
What is the shortest/smallest racket program (ithat enumerates all and only valid racket programs?

--
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...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/0b83b7d7-ea3e-434a-b6c4-f394a97fe4fd%40googlegroups.com.

Laurent

unread,
Sep 5, 2019, 9:45:32 AM9/5/19
to David Van Horn, Adam Golding, Racket-Users List
Probably only those that output Chaitin's constant ;)

But otherwise I would guess "syntactically valid", in which case it would be easier to consider only lambdas with only one argument.

Though if you want to also use all of Racket's primitives (that is, including I/O), then good luck. My closest guess would be:
(for/list ([i (in-naturals)])
  (mflatt i))

David Van Horn

unread,
Sep 5, 2019, 9:56:48 AM9/5/19
to Laurent, Adam Golding, Racket-Users List
But whether a program is syntactically valid is not an easy thing to decide in a language like racket... 

Laurent

unread,
Sep 5, 2019, 10:07:42 AM9/5/19
to David Van Horn, Adam Golding, Racket-Users List
Although it's not about checking, but generating, which *may* be easier.
(Though if one can generate all syntactically valid programs in program size order, then checking is just a matter of checking for membership in the list of all programs of size less than the program. This list can be huge however.)

At least it's very simple to generate all 'syntactically' valid Turing machines ;)

Jérôme Martin

unread,
Sep 5, 2019, 10:11:50 AM9/5/19
to Racket Users
On Thursday, September 5, 2019 at 3:05:48 PM UTC+2, Adam Golding wrote:
> What is the shortest/smallest racket program (ithat enumerates all and only valid racket programs?

Given that "valid" means "a Racket program that compiles correctly".
As the Racket compiler is Turing Complete and can be changed by the compiled program itself.
Then there would be no way to know if the compiler will finish executing or get stuck into an infinite loop.
Which means it would resume to the https://en.wikipedia.org/wiki/Halting_problem

Right?

Sorawee Porncharoenwase

unread,
Sep 5, 2019, 10:13:45 AM9/5/19
to Laurent, David Van Horn, Adam Golding, Racket-Users List

Oh, this is easy. The grammar of Racket is

#lang <id> <whatever>*

which, as I showed above, is expressible as regular expression. Regular languages are easily decidable :)




Adam Golding

unread,
Sep 5, 2019, 10:57:33 AM9/5/19
to Racket Users
if it executes?


On Thursday, 5 September 2019 09:56:48 UTC-4, dvanhorn wrote:
But whether a program is syntactically valid is not an easy thing to decide in a language like racket... 

On Thu, Sep 5, 2019, 9:45 AM Laurent <lauren...@gmail.com> wrote:
Probably only those that output Chaitin's constant ;)

But otherwise I would guess "syntactically valid", in which case it would be easier to consider only lambdas with only one argument.

Though if you want to also use all of Racket's primitives (that is, including I/O), then good luck. My closest guess would be:
(for/list ([i (in-naturals)])
  (mflatt i))

On Thu, Sep 5, 2019 at 2:31 PM David Van Horn <dvan...@cs.umd.edu> wrote:
What do you mean by valid?

On Thu, Sep 5, 2019, 9:05 AM Adam Golding <adamg...@gmail.com> wrote:
What is the shortest/smallest racket program (ithat enumerates all and only valid racket programs?

--
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...@googlegroups.com.

--
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...@googlegroups.com.

Adam Golding

unread,
Sep 5, 2019, 10:58:39 AM9/5/19
to Racket Users
It's okay if the program never halts.

David Van Horn

unread,
Sep 5, 2019, 11:10:59 AM9/5/19
to Adam Golding, Racket Users
How about this: a stream of strings which can be be parsed and
compiled. (Note that this will loop when it gets to the first program
that makes the compiler loop; luckily it's inefficient enough that
you'll never actually get there.)

#lang racket
(define valid-progs
(for/stream ([p strings]
#:when (valid p))
p))

(define strings
(stream-cons ""
(for*/stream ([s strings]
[i (in-range 0 #x10FFFF)]
#:when (not (<= #xD800 i #xDFFF)))
(string-append (string (integer->char i)) s))))

(define (valid x)
(with-handlers ([exn:fail? (λ _ #f)])
(compile (with-input-from-string x
(λ () (begin0 (read)
(unless (eof-object? (read))
(error "fail"))))))
x))

On Thu, Sep 5, 2019 at 10:58 AM Adam Golding <adamg...@gmail.com> wrote:
>
> It's okay if the program never halts.
>
> --
> 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...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/70d0b081-eef8-44a6-b2e3-5a72eba7ff5a%40googlegroups.com.

David Van Horn

unread,
Sep 5, 2019, 11:46:13 AM9/5/19
to Adam Golding, Racket Users
This program works in 7.3, but not 7.4, which complains about the use
of strings before it's definition. Swapping the order of valid-progs
and strings fixes that, but the program then loops, although I don't
understand why.

Adam Golding

unread,
Sep 5, 2019, 1:13:58 PM9/5/19
to Racket Users
What is the shortest program listing the largest list of programs that can be listed without looping?
> To unsubscribe from this group and stop receiving emails from it, send an email to racket...@googlegroups.com.

Sage Gerard

unread,
Sep 5, 2019, 1:17:32 PM9/5/19
to adamg...@gmail.com, racket...@googlegroups.com
This question can be read a couple of different ways too. What are you trying to do once you have the answer you are looking for?



-------- Original Message --------
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/beea9305-6945-45fd-91b2-59e6162b6b1e%40googlegroups.com.

Adam Golding

unread,
Sep 5, 2019, 1:46:54 PM9/5/19
to Racket Users
I want to try automating programming as search where I have various methods to enumerate the set of all programs in different orders (fastest to halt first?  shortest source code first? etc.) and filter out certain programs almost like evolutionary programming.  I don't have a specific application in mind really, I wanted to have various enumerators to experiment with, not unlike the opening of "New Kind of Science", where Wolfram generates all possible CA programs and then categorizes them according to their behavior.

The idea also came up recently in this context: https://www.facebook.com/adamgolding/posts/10106973704058242

Adam Golding

unread,
Sep 5, 2019, 1:48:54 PM9/5/19
to Racket Users
Basically I want to enumerate programs with as few assumptions as possible aka enumerate the largest set of programs I can--I want to be able to enumerate them in a variety of different orders to compare search strategies.

Adam Golding

unread,
Sep 5, 2019, 1:51:05 PM9/5/19
to Racket Users
The relevant part of the fb thread is where I remark "Suppose every voter is a program--then we can randomly sample programs and voting methods on objective questions and see which methods the epistemic argument for democracy is likely to be correct for" -- the word 'randomly' can probably be removed--there are different orders you can sample programs in, I would like a variety of them.


On Thursday, 5 September 2019 13:46:54 UTC-4, Adam Golding wrote:

Sage Gerard

unread,
Sep 5, 2019, 1:53:29 PM9/5/19
to Adam Golding, Racket Users
Thanks, that helps.

In the way I read this, it sounds like you want a program that computes the most efficient search algorithm regardless of the context in which said algorithm is used.

Is that accurate?

~slg


‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.

Adam Golding

unread,
Sep 5, 2019, 2:07:32 PM9/5/19
to Racket Users
At this point I don't need the search (through the space of all programs) to be efficient I just need it to be 'total' in that every program would be reached given a countable infinity of time.  Then I could alter this search to search the same space in a different order (still total) and compare empirically which is 'more efficient' (depends what programs you're searching for).  For example, enumerating possible racket programs from shortest to longest source would be one order, and enumerating them from shortest to longest runtime would be another...

Sage Gerard

unread,
Sep 5, 2019, 2:10:09 PM9/5/19
to Adam Golding, Racket Users
It almost sounds like you want a cleaner interface for defining a neural net.

~slg


‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users...@googlegroups.com.

Sage Gerard

unread,
Sep 5, 2019, 2:13:31 PM9/5/19
to Adam Golding, Racket Users
In all honesty, I think you are asking for something so broad that it would be more practical if you ran experiments and simulations against the specific space you are curious about. Once you do that enough times you'll be able to pick out the patterns. I'm not convinced there is an off-shelf design for what you want without a patent attached to it.

~slg


‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐

Laurent

unread,
Sep 5, 2019, 3:45:45 PM9/5/19
to Sage Gerard, Adam Golding, Racket Users
Adam,

I strongly recommend you take a look at Levin Search (aka Universal Search), which enumerates and runs programs by dovetailing in a smart way:

This avoids the halting problem including the running time in the complexity: If a program q solves the problem in time Tq, then Levin Search solves the problem in time Tq / wq, where wq = 2^-l(q) with l(q) being the size in bits of program q. In other words, Levin Search solves all search problems at least as fast as the fastest program within a constant factor that depends on the inverse of the prior of the program.

IMO, Levin Search is one of the most important algorithms ever.


Sage Gerard

unread,
Sep 5, 2019, 3:52:31 PM9/5/19
to laurent...@gmail.com, adamg...@gmail.com, racket...@googlegroups.com
It's as they say: if you want an answer on the internet, just say the wrong thing and wait for someone to correct you. :)



-------- Original Message --------

Josh Rubin

unread,
Sep 5, 2019, 5:27:03 PM9/5/19
to Adam Golding, Racket Users

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.

http://minikanren.org/

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:

(and
  (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
jlr...@gmail.com


Sage Gerard

unread,
Sep 5, 2019, 5:34:30 PM9/5/19
to jlr...@gmail.com, adamg...@gmail.com, racket...@googlegroups.com
With a Racket section to boot. Thanks so much for sharing this! I had no idea about this kind of application.



-------- Original Message --------

--


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...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/b7389311-cc35-a725-dbaa-6ffc7153781b%40gmail.com.

Hendrik Boom

unread,
Sep 5, 2019, 5:37:31 PM9/5/19
to Racket Users
On Thu, Sep 05, 2019 at 10:46:54AM -0700, Adam Golding wrote:
> I want to try automating programming as search where I have various methods
> to enumerate the set of all programs in different orders (fastest to halt
> first? shortest source code first? etc.) and filter out certain programs
> almost like evolutionary programming. I don't have a specific application
> in mind really, I wanted to have various enumerators to experiment with,
> not unlike the opening of "New Kind of Science", where Wolfram generates
> all possible CA programs and then categorizes them according to their
> behavior.
>
> The idea also came up recently in this context:
> https://www.facebook.com/adamgolding/posts/10106973704058242
>

I once wrote a program to enumerate typed lambda calculus expressions
equivalent to church numerals. It didn't find any interesting ones in
feasible time. But machines were slower and more expensive back in the
70's.

This was in context of finding the shortest lambda-expression that could
represent eash integer, and trying to find the size-restricted
lambda-expression that could represent the largest integer.

-- hendrik

> On Thursday, 5 September 2019 13:17:32 UTC-4, Sage Gerard wrote:
> >
> > This question can be read a couple of different ways too. What are you
> > trying to do once you have the answer you are looking for?
> >
> >
> >
> > -------- Original Message --------
> > On Sep 5, 2019, 1:13 PM, Adam Golding < adamg...@gmail.com <javascript:>>
> > email to racket...@googlegroups.com <javascript:>.
> > To view this discussion on the web visit
> > https://groups.google.com/d/msgid/racket-users/beea9305-6945-45fd-91b2-59e6162b6b1e%40googlegroups.com
> > <https://groups.google.com/d/msgid/racket-users/beea9305-6945-45fd-91b2-59e6162b6b1e%40googlegroups.com?utm_medium=email&utm_source=footer>
> > .
> >
> >
>
> --
> 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...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/66cee60f-b75c-4c9c-a2b8-a90dfabdfc1e%40googlegroups.com.

Jens Axel Søgaard

unread,
Sep 5, 2019, 6:04:27 PM9/5/19
to Josh Rubin, Adam Golding, Racket Users
Den tor. 5. sep. 2019 kl. 23.27 skrev Josh Rubin <jlr...@gmail.com>:

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.


Apropos,  Friedman and Byrd shows how one can use an 
interpreter written in Kanren to generate Scheme programs.

https://www.youtube.com/watch?v=5vtC7WEN76w

/Jens Axel 
Reply all
Reply to author
Forward
0 new messages