Could any existing ML technique be used, for example, to solve the problem of building a lazy Sieve of Eratosthenes in Haskell? By that, I mean a program that, given a specification (a dependent type inhabited by infinite, ordered lists of prime numbers), builds a program of that type, with the same complexity of the known, manually designed algorithm?

  • $\begingroup$ Please edit your question to clarify what you are asking. What precisely do you mean by "solve the problem of building a lazy Sieve of Eratosthenes"? Do you mean, come up with the code of a Haskell program that implements this sieve? Do you mean, outputs the same sequence of integers that this sieve outputs? Do you mean something else? Given what input (or what training set)? Have you read the literature on "program synthesis"? $\endgroup$ – D.W. Oct 6 '16 at 21:51
  • 1
    $\begingroup$ @D.W. done. I've not read a lot on the literature on "program synthesis" but thanks for the recommendation. $\endgroup$ – MaiaVictor Oct 6 '16 at 23:58
  • $\begingroup$ What kind of specification language do you have in mind? I imagine "output primes" is just one example of a task you'd want to be able to synthesize programs for. Then the expressiveness and nature of the specification language becomes a key parameter that will influence how easy/hard the problem is and what approaches one might consider. Anyway, I encourage you to spend some quality time reading the research literature on "program synthesis" -- this is exactly the sort of problem that it's aimed at addressing. I suspect achieving the same asymptotic running time may be hard. $\endgroup$ – D.W. Oct 7 '16 at 0:23
  • $\begingroup$ Actually, I probably, yes, have spent some time reading about program synthesis a while ago, if I recall correctly, and I'm almost positive nothing I read propose any technique that could even hope writing a Sieve of Eratosthenes as clean as that one, regardless of the specification language (that is why I used that particular example). I'm under the impression those techniques aren't suited to generate clean/elegant programs. Nether less, I need to spend some time reading it and refreshing my memory before being able to be sure of that (and, consequently, ask richer questions). Thank you! $\endgroup$ – MaiaVictor Oct 7 '16 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.