Re: [racket-users] Re: Listing All Programs

2019-09-05 Thread Hendrik Boom 
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 > 
> > wrote:
> >
> >
> > What is the shortest program listing the largest list of programs that can 
> > be listed without looping?
> >
> > On Thursday, 5 September 2019 11:10:59 UTC-4, dvanhorn wrote:
> >>
> >> 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 #x10)] 
> >>  #: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  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...@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.
> >>  
> >>
> >>
> > -- 
> > 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 .
> > To view this discussion on the web visit 
> > https://groups.google.com/d/msgid/racket-users/beea9305-6945-45fd-91b2-59e6162b6b1e%40googlegroups.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-users+unsubscr...@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.

-- 
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 
https://groups.google.com/d/msgid/racket-users/20190905213728.6u5voccrebxisalg%40topoi.pooq.com.

Re: [racket-users] Re: Listing All Programs

2019-09-05 Thread Sage Gerard 
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 
On Sep 5, 2019, 3:45 PM, Laurent wrote:

> 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:
> http://people.idsia.ch/~juergen/mljssalevin/node4.html
> http://www.scholarpedia.org/article/Universal_search#Universal_search
>
> 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.
>
> On Thu, Sep 5, 2019 at 7:13 PM Sage Gerard  wrote:
>
>> 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 ‐‐‐
>> On Thursday, September 5, 2019 2:09 PM, Sage Gerard  
>> wrote:
>>
>>> It almost sounds like you want a cleaner interface for defining a neural 
>>> net.
>>>
>>> ~slg
>>>
>>> ‐‐‐ Original Message ‐‐‐
>>> On Thursday, September 5, 2019 2:07 PM, Adam Golding 
>>>  wrote:
>>>
 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...

 On Thursday, 5 September 2019 13:53:29 UTC-4, Sage Gerard wrote:

> 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 ‐‐‐
> On Thursday, September 5, 2019 1:48 PM, Adam Golding  
> wrote:
>
>> 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.
>>
>> On Thursday, 5 September 2019 13:46:54 UTC-4, 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
>>>
>>> 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> wrote:

> What is the shortest program listing the largest list of programs 
> that can be listed without looping?
>
> On Thursday, 5 September 2019 11:10:59 UTC-4, dvanhorn wrote:
>
>> 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

Re: [racket-users] Re: Listing All Programs

2019-09-05 Thread Laurent 
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:
http://people.idsia.ch/~juergen/mljssalevin/node4.html
http://www.scholarpedia.org/article/Universal_search#Universal_search

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.


On Thu, Sep 5, 2019 at 7:13 PM Sage Gerard  wrote:

> 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 ‐‐‐
> On Thursday, September 5, 2019 2:09 PM, Sage Gerard 
> wrote:
>
> It almost sounds like you want a cleaner interface for defining a neural
> net.
>
> *~slg*
>
>
> ‐‐‐ Original Message ‐‐‐
> On Thursday, September 5, 2019 2:07 PM, Adam Golding <
> adamgold...@gmail.com> wrote:
>
> 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...
>
> On Thursday, 5 September 2019 13:53:29 UTC-4, Sage Gerard wrote:
>
>> 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 ‐‐‐
>> On Thursday, September 5, 2019 1:48 PM, Adam Golding 
>> wrote:
>>
>> 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.
>>
>> On Thursday, 5 September 2019 13:46:54 UTC-4, 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
>>>
>>> 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> wrote:


 What is the shortest program listing the largest list of programs that
 can be listed without looping?

 On Thursday, 5 September 2019 11:10:59 UTC-4, dvanhorn wrote:

> 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 #x10)]
>  #: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))
>

Re: [racket-users] Re: Listing All Programs

2019-09-05 Thread Sage Gerard 
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 ‐‐‐
On Thursday, September 5, 2019 2:09 PM, Sage Gerard  wrote:

> It almost sounds like you want a cleaner interface for defining a neural net.
>
> ~slg
>
> ‐‐‐ Original Message ‐‐‐
> On Thursday, September 5, 2019 2:07 PM, Adam Golding  
> wrote:
>
>> 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...
>>
>> On Thursday, 5 September 2019 13:53:29 UTC-4, Sage Gerard wrote:
>>
>>> 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 ‐‐‐
>>> On Thursday, September 5, 2019 1:48 PM, Adam Golding  
>>> wrote:
>>>
 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.

 On Thursday, 5 September 2019 13:46:54 UTC-4, 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
>
> 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> wrote:
>>
>>> What is the shortest program listing the largest list of programs that 
>>> can be listed without looping?
>>>
>>> On Thursday, 5 September 2019 11:10:59 UTC-4, dvanhorn wrote:
>>>
 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 #x10)]
  #: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  
 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...@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.
>>>
>>> --
>>> You received this message because you are

Re: [racket-users] Re: Listing All Programs

2019-09-05 Thread Sage Gerard 
It almost sounds like you want a cleaner interface for defining a neural net.

~slg

‐‐‐ Original Message ‐‐‐
On Thursday, September 5, 2019 2:07 PM, Adam Golding  
wrote:

> 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...
>
> On Thursday, 5 September 2019 13:53:29 UTC-4, Sage Gerard wrote:
>
>> 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 ‐‐‐
>> On Thursday, September 5, 2019 1:48 PM, Adam Golding  
>> wrote:
>>
>>> 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.
>>>
>>> On Thursday, 5 September 2019 13:46:54 UTC-4, 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

 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> wrote:
>
>> What is the shortest program listing the largest list of programs that 
>> can be listed without looping?
>>
>> On Thursday, 5 September 2019 11:10:59 UTC-4, dvanhorn wrote:
>>
>>> 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 #x10)]
>>>  #: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  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...@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.
>>
>> --
>> 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.
>> 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_source=footer).
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups 
>>>

Re: [racket-users] Re: Listing All Programs

2019-09-05 Thread Adam Golding 
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...

On Thursday, 5 September 2019 13:53:29 UTC-4, Sage Gerard wrote:
>
> 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 ‐‐‐
> On Thursday, September 5, 2019 1:48 PM, Adam Golding  > wrote:
>
> 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.
>
> On Thursday, 5 September 2019 13:46:54 UTC-4, 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
>>
>> 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> wrote:
>>>
>>>
>>> What is the shortest program listing the largest list of programs that 
>>> can be listed without looping?
>>>
>>> On Thursday, 5 September 2019 11:10:59 UTC-4, dvanhorn wrote:
>>>
 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 #x10)] 
  #: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  
 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...@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.
  


>>>
>>> --
>>> 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.
>>> To view this discussion on the web visit 
>>> https://groups.google.com/d/msgid/racket-users/beea9305-6945-45fd-91b2-59e6162b6b1e%40googlegroups.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 .
> To view this discussion on the web visit 
> https://groups.google.com/d/msgid/racket-users/a0ee9cdb-c46d-4f3a-a9c3-4a9c700cec71%40googlegroups.com
>  
>

Re: [racket-users] Re: Listing All Programs

2019-09-05 Thread Sage Gerard 
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 ‐‐‐
On Thursday, September 5, 2019 1:48 PM, Adam Golding  
wrote:

> 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.
>
> On Thursday, 5 September 2019 13:46:54 UTC-4, 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
>>
>> 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> wrote:
>>>
 What is the shortest program listing the largest list of programs that can 
 be listed without looping?

 On Thursday, 5 September 2019 11:10:59 UTC-4, dvanhorn wrote:

> 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 #x10)]
>  #: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  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...@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.

 --
 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.
 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_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+unsubscr...@googlegroups.com.
> To view this discussion on the web visit 
> [https://groups.google.com/d/msgid/racket-users/a0ee9cdb-c46d-4f3a-a9c3-4a9c700cec71%40googlegroups.com](https://groups.google.com/d/msgid/racket-users/a0ee9cdb-c46d-4f3a-a9c3-4a9c700cec71%40googlegroups.com?utm_medium=email_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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/racket-users/GQkLv3Jr-HmHQc3o0Psl1mS7eDEuxSgaFJsV06mTk-Drum9H9ddmDIgSqUEqzUGC-brt20RCfNGOdw0uwW0wIqWF_wcQYUv21vnjMtxxChA%3D%40sagegerard.com.

Re: [racket-users] Re: Listing All Programs

2019-09-05 Thread Adam Golding 
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:
>
> 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
>
> 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> wrote:
>>
>>
>> What is the shortest program listing the largest list of programs that 
>> can be listed without looping?
>>
>> On Thursday, 5 September 2019 11:10:59 UTC-4, dvanhorn wrote:
>>>
>>> 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 #x10)] 
>>>  #: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  
>>> 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...@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.
>>>  
>>>
>>>
>> -- 
>> 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.
>> To view this discussion on the web visit 
>> https://groups.google.com/d/msgid/racket-users/beea9305-6945-45fd-91b2-59e6162b6b1e%40googlegroups.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-users+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/racket-users/20ae2b58-0e33-4d9c-b6b8-8ab6d87b944c%40googlegroups.com.

Re: [racket-users] Re: Listing All Programs

2019-09-05 Thread Adam Golding 
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.

On Thursday, 5 September 2019 13:46:54 UTC-4, 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
>
> 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> wrote:
>>
>>
>> What is the shortest program listing the largest list of programs that 
>> can be listed without looping?
>>
>> On Thursday, 5 September 2019 11:10:59 UTC-4, dvanhorn wrote:
>>>
>>> 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 #x10)] 
>>>  #: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  
>>> 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...@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.
>>>  
>>>
>>>
>> -- 
>> 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.
>> To view this discussion on the web visit 
>> https://groups.google.com/d/msgid/racket-users/beea9305-6945-45fd-91b2-59e6162b6b1e%40googlegroups.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-users+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/racket-users/a0ee9cdb-c46d-4f3a-a9c3-4a9c700cec71%40googlegroups.com.

Re: [racket-users] Re: Listing All Programs

2019-09-05 Thread Adam Golding 
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

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 > 
> wrote:
>
>
> What is the shortest program listing the largest list of programs that can 
> be listed without looping?
>
> On Thursday, 5 September 2019 11:10:59 UTC-4, dvanhorn wrote:
>>
>> 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 #x10)] 
>>  #: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  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...@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.
>>  
>>
>>
> -- 
> 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 .
> To view this discussion on the web visit 
> https://groups.google.com/d/msgid/racket-users/beea9305-6945-45fd-91b2-59e6162b6b1e%40googlegroups.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-users+unsubscr...@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.

Re: [racket-users] Re: Listing All Programs

2019-09-05 Thread Sage Gerard 
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 wrote:

> What is the shortest program listing the largest list of programs that can be 
> listed without looping?
>
> On Thursday, 5 September 2019 11:10:59 UTC-4, dvanhorn wrote:
>
>> 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 #x10)]
>>  #: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](javascript:)> 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...@googlegroups.com](javascript:).
>>> To view this discussion on the web visit 
>>> https://groups.google.com/d/msgid/racket-users/70d0b081-eef8-44a6-b2e3-5a72eba7ff5a%40googlegroups.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-users+unsubscr...@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](https://groups.google.com/d/msgid/racket-users/beea9305-6945-45fd-91b2-59e6162b6b1e%40googlegroups.com?utm_medium=email_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+unsubscr...@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/racket-users/ii7sMy_fxElYY2CIt16vQ6Zy1JLL5EJLRtKveAkTNHfR4rhN9VjpcSC0A8gzfiFRd5BDr_GQRehZAR7JBcAP3W7GXu2MS_Bd8mRWeMNbE-M%3D%40sagegerard.com.

Re: [racket-users] Re: Listing All Programs

2019-09-05 Thread Adam Golding 
What is the shortest program listing the largest list of programs that can 
be listed without looping?

On Thursday, 5 September 2019 11:10:59 UTC-4, dvanhorn wrote:
>
> 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 #x10)] 
>  #: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  > 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...@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.
>  
>
>

-- 
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 
https://groups.google.com/d/msgid/racket-users/beea9305-6945-45fd-91b2-59e6162b6b1e%40googlegroups.com.

Re: [racket-users] Re: Listing All Programs

2019-09-05 Thread David Van Horn 
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.

On Thu, Sep 5, 2019 at 11:10 AM David Van Horn  wrote:
>
> 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 #x10)]
>  #: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  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+unsubscr...@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.

-- 
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 
https://groups.google.com/d/msgid/racket-users/CAFJHQkGnh-hUB4Rbg9jQNrOtjSXFyP2_w4ci1w0WcKuMe58MyQ%40mail.gmail.com.

Re: [racket-users] Re: Listing All Programs

2019-09-05 Thread David Van Horn 
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 #x10)]
 #: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  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+unsubscr...@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.

-- 
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 
https://groups.google.com/d/msgid/racket-users/CAFJHQkH1pM0mE3qSacCD8Cn9T%2B%2BLw%3DJs0XF-oeb-TPD%2BQuhuAA%40mail.gmail.com.