Re: [racket-users] Listing All Programs

[Jens Axel Søgaard]

Den tor. 5. sep. 2019 kl. 23.27 skrev Josh Rubin :

>
> 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

-- 
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/CABefVgzYc0sMhobXpW9Ucbkpiex-45of6mAHSV_di4wiTc%2B_Gg%40mail.gmail.com.

Re: [racket-users] Listing All Programs

[Sage Gerard]

With a Racket section to boot. Thanks so much for sharing this! I had no idea 
about this kind of application.

 Original Message 
On Sep 5, 2019, 5:26 PM, Josh Rubin wrote:

> 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 '( example1)) 'desired-result1)
>   (equal? (eval '( example2)) 'desired-result2)
> ... )
>
> The search strategy is complete. It will eventually check everything in
> the search tree. It will not get stuck.
>
> --
> Josh Rubin
> jlru...@gmail.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/b7389311-cc35-a725-dbaa-6ffc7153781b%40gmail.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/hGOkV_lLRfIvpOcB6BfbiPsHl7cTQCC7P4tGxCROxYjM1Gyr588-aG4Y6EefSwESXaKjo8Myvyg1v-0uD3vG4SW85eGiTGL8aOZ4aASiaBg%3D%40sagegerard.com.

Re: [racket-users] Listing All Programs

[Josh Rubin]

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 '( example1)) 'desired-result1)
  (equal? (eval '( example2)) 'desired-result2)
... )

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


--
Josh Rubin
jlru...@gmail.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/b7389311-cc35-a725-dbaa-6ffc7153781b%40gmail.com.

Re: [racket-users] Listing All Programs

[Adam Golding]

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 > 
> 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 > > wrote:
>>
>>> What do you mean by valid?
>>>
>>> On Thu, Sep 5, 2019, 9:05 AM Adam Golding >> > 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 .
 To view this discussion on the web visit 
 https://groups.google.com/d/msgid/racket-users/0b83b7d7-ea3e-434a-b6c4-f394a97fe4fd%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/CAFJHQkGS_%3DM9G%3DGaLXZgctO6UC_cR9VpqjXt5q211UOeOq2dFw%40mail.gmail.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/f8d75da4-5355-4744-a582-77ba4adc8e70%40googlegroups.com.

Re: [racket-users] Listing All Programs

[Sorawee Porncharoenwase]

Oh, this is easy. The grammar of Racket is

#lang  *

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



On Thu, Sep 5, 2019 at 9:07 PM Laurent  wrote:

> 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 ;)
>
> On Thu, Sep 5, 2019 at 2:56 PM David Van Horn  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  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 
>>> wrote:
>>>
 What do you mean by valid?

 On Thu, Sep 5, 2019, 9:05 AM Adam Golding 
 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+unsubscr...@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
> 
> .
>
 --
 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/CAFJHQkGS_%3DM9G%3DGaLXZgctO6UC_cR9VpqjXt5q211UOeOq2dFw%40mail.gmail.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/CABNTSaGqXagO98Ttx1-rjmqSrdNyHn4m_UUd5_xazF-xiW2O_Q%40mail.gmail.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/CADcuegs4t0dwKdF%2BbnFJ2w_k6_E7reHqVkEn_1wyv0HgcQr-Rw%40mail.gmail.com.

Re: [racket-users] Listing All Programs

[Laurent]

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 ;)

On Thu, Sep 5, 2019 at 2:56 PM David Van Horn  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  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 
>> wrote:
>>
>>> What do you mean by valid?
>>>
>>> On Thu, Sep 5, 2019, 9:05 AM Adam Golding  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+unsubscr...@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
 
 .

>>> --
>>> 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/CAFJHQkGS_%3DM9G%3DGaLXZgctO6UC_cR9VpqjXt5q211UOeOq2dFw%40mail.gmail.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/CABNTSaGqXagO98Ttx1-rjmqSrdNyHn4m_UUd5_xazF-xiW2O_Q%40mail.gmail.com.

Re: [racket-users] Listing All Programs

[David Van Horn]

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  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  wrote:
>
>> What do you mean by valid?
>>
>> On Thu, Sep 5, 2019, 9:05 AM Adam Golding  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+unsubscr...@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
>>> 
>>> .
>>>
>> --
>> 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/CAFJHQkGS_%3DM9G%3DGaLXZgctO6UC_cR9VpqjXt5q211UOeOq2dFw%40mail.gmail.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/CAFJHQkHG4wEpekEEfHf2NmHyPsQSZ%2BOpEx%3D1uNXQ5q6wJKG_1w%40mail.gmail.com.

Re: [racket-users] Listing All Programs

[Laurent]

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  wrote:

> What do you mean by valid?
>
> On Thu, Sep 5, 2019, 9:05 AM Adam Golding  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+unsubscr...@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
>> 
>> .
>>
> --
> 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/CAFJHQkGS_%3DM9G%3DGaLXZgctO6UC_cR9VpqjXt5q211UOeOq2dFw%40mail.gmail.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/CABNTSaFts7ZaLTW3%3DzM-OSW%3D-OMiZwTyxvgAWVk0pDaq0yKazg%40mail.gmail.com.

Re: [racket-users] Listing All Programs

[David Van Horn]

What do you mean by valid?

On Thu, Sep 5, 2019, 9:05 AM Adam Golding  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+unsubscr...@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
> 
> .
>

-- 
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/CAFJHQkGS_%3DM9G%3DGaLXZgctO6UC_cR9VpqjXt5q211UOeOq2dFw%40mail.gmail.com.

[racket-users] Listing All Programs

[Adam Golding]

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+unsubscr...@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.