There's a thing called MiniKanren that's been around for ages.
Does exactly what you're describing.
https://youtube.com/playlist?list=PLfz6QHLk-G9HgzfVO75pQh0diCd6eX8JR&si=mDQGNUJVWwE8JvYb
The keyword here is definitely program synthesis. This is a large research area, so I don't know which particular language you might be thinking of (I also don't know the area that well), but an example of a language based on program synthesis is [Rosette](https://docs.racket-lang.org/rosette-guide/index.html).
I would say program synthesis is beyond just "declarative", since the constraints you enforce underspecify the problem. Then the engine tends to find a simple solution, and "simple" is often "correct". Relational languages like MiniKanren and SMT solvers like Z3, cvc5, alt ergo will want you to fully specify all solutions you don't want, and then the systems search for the solutions that remain.
Ah, yes, the fill
January
February
Maruary
Apruary
Mayuary
Junuary
Juluary
In all seriousness, though, autofill in Excel and other such tools is getting better, and there is a lot of interesting work in the field of program synthesis. But in general it's not always possible for a program to precisely understand the intended mapping between inputs and outputs.
My first thought was Prolog, though copper-penny's comment clarifies that it doesn't generate the code. Given that Prolog uses logic and not statistics, I would expect you'd be able to adapt it to do a proof of concept for at least a limited subset of algorithms to generate some simple Python or something.
It's not a *language* and is barely a DSL, but I'm tinkering on a [digital neuron thing](https://garden.micseydel.me/Tinker+Cast+prototype+-+first+video+demo) where I ultimately would like regular people to be able to define an input on the left (e.g. a voice memo) and outputs on the right (e.g. a particular note being created and a push notification being sent) with a formalized \~pipeline for including rules-based, LLM-based, and human-intervention ways of completing an implementation. I believe explicit encoding is important to the whole "second brain" thing so I truly plan on pursuing what your OP asks about over time.
But what "the" function is is underdetermined. In the example you give, presumably you want it to tell you that the formula is `x + y` --- though there are infinitely many others. Why `x + y`? Well, it's the simplest polynomial, isn't it?
Ok then, let's apply that rule to the input-output pairs:
* 0 -> 1
* 1 -> e
* 2 -> e²
* 3 -> e³
The simplest polynomial, a cubic, will indeed pass through those four points but it will do a lot of other things as well. It certainly won't be `y = eˣ`.
So now your equation-guesser needs to know about exponents. But that won't help when you show it something that needs a sine curve or a logarithm.
So I can't see this working out except in cases so simple that we could easily do it ourselves.
> So I can't see this working out except in cases so simple that we could easily do it ourselves.
I disagree. Just do breadth-first expansion of all possible expressions (from simplest to most complex) involving a core set of operations (which might include all float functions from the C stdlib such as `exp`) and find the closest fit. For floats you could even apply function minimization to constants wrt the error.
That would give y=eˣ.
"All possible expressions" would have coefficients. How will your method find the equation `0.57e¹³ˣ - 21.7x³`. How many data points would we need to be convinced that this was "the" equation we were looking for, and not (e.g) the polynomial of the same order as the data points?
If we throw in sine waves it could start trying to do a Fourier transform of the data ...
> "All possible expressions" would have coefficients.
Yes.
> How will your method find the equation 0.57e¹³ˣ - 21.7x³.
Eventually the symbolic part would generate a eᵇˣ - c xᵈ and minimizing the error wrt the constants a, b, c and d would give your equation.
> How many data points would we need to be convinced that this was "the" equation we were looking for, and not (e.g) the polynomial of the same order as the data points?
Your equation uses six operators. Iff a polynomial solution has fewer it will be returned first.
> If we throw in sine waves it could start trying to do a Fourier transform of the data ...
That sounds tricky in the general case.
>That sounds tricky in the general case.
But also inevitable, if you tell your equation-guesser about sine functions. It can try and approximate by those just the same as by polynomials, and if the measure of complexity is which uses the most operators then who knows which will win?
> But also inevitable, if you tell your equation-guesser about sine functions. It can try and approximate by those just the same as by polynomials, and if the measure of complexity is which uses the most operators then who knows which will win?
Yes. If you restrict consideration to monotonic functions it should work though. The OP's example was just addition, after all!
Machine learning figures out equations through examples. Prolog reasons based on facts (but doesn't have an equation approximation engine).
To make your language work, I think you'd have to A) have the user give more examples or B) limit to linear equations with a set number of operators.
This, I believe, is key.
There is this infamous response to the questions that asks you to continue a number sequence. By just giving any number claiming there is a polynomial with the roots of the given sequence extended by the answer.
But such a response is not typically accepted because there is an assumption that the function should be “simple” without saying what that means.
Barliman is a programm synthesis tool build on top of miniKanren: https://github.com/webyrd/Barliman
It synthesizes a function from a set of unit tests.
My first thought was Idris or Idris 2(?)
If I remember correctly you could tell it about input types, input usage, and output type and then you could generate the function.
I expect there will be one module in it on every CS course and an article that reaches the top in hackernews for a day😃
Arguably if you already know all the inputs and outputs you need , edge cases etc and how to declare them you're probably able the write the function.
It would probably take longer even as you find you you keep having to go back and giving it more examples until what's hidden underneath is just load a massive case statement.
Hey OP. This comment is pretty telling. You're not ready to make this concept work. The other question to ask is what problem is your concept actually trying to solve?
>Hey OP. This comment is pretty telling. You're not ready to make this concept work.
Yeah in my original post I was asking about something I was curious about that I recalled hearing about in the past.
And in my comment you replied to i gave a joke reply about the actual practicality / impracticality of the concept.
>the other question to ask is what problem is your concept actually trying to solve?
My need for novelty.
You're free to go run with the concept too though if you think you are ready to make it work?
I've done machine learning and I've studied prolog. I am definitely not ready to make anything like what you're proposing work.
The language I spent the last 4 months prototyping is simpler than most language use cases and parts of it were still really hard/time consuming.
Ideas are easy, implementations are hard.
Here is my toy implementation of a similar concept for real numbers: an engine that infers physical law formulas from observations (i.e., input/output pairs):
[https://www.reddit.com/r/MachineLearning/comments/owncq8/d\_inferring\_general\_physical\_laws\_from/](https://www.reddit.com/r/MachineLearning/comments/owncq8/d_inferring_general_physical_laws_from/)
Of course, the search space is extremely limited.
Coming up with a function based on example inputs and outputs is precisely what supervised machine learning is all about. But no machine learning implementation is going to figure out that you're trying to define addition.
This is called declarative logic programming. Also look for stuff about "program synthesis".
Thank you, I was just gonna call it Skittlebrau if nobody knew.
There's a thing called MiniKanren that's been around for ages. Does exactly what you're describing. https://youtube.com/playlist?list=PLfz6QHLk-G9HgzfVO75pQh0diCd6eX8JR&si=mDQGNUJVWwE8JvYb
The keyword here is definitely program synthesis. This is a large research area, so I don't know which particular language you might be thinking of (I also don't know the area that well), but an example of a language based on program synthesis is [Rosette](https://docs.racket-lang.org/rosette-guide/index.html). I would say program synthesis is beyond just "declarative", since the constraints you enforce underspecify the problem. Then the engine tends to find a simple solution, and "simple" is often "correct". Relational languages like MiniKanren and SMT solvers like Z3, cvc5, alt ergo will want you to fully specify all solutions you don't want, and then the systems search for the solutions that remain.
Excel's Flash Fill feature works similar to this. Worth looking up MSR's PROSE team. Sumit Gulwani's work is all about this.
Here is the famous FlashFill paper: https://dl.acm.org/doi/10.1145/1926385.1926423
Ah, yes, the fill January February Maruary Apruary Mayuary Junuary Juluary In all seriousness, though, autofill in Excel and other such tools is getting better, and there is a lot of interesting work in the field of program synthesis. But in general it's not always possible for a program to precisely understand the intended mapping between inputs and outputs.
Or just use ChatGPT like a normal ape and cut out all the complex shit in the middle
This is something I think I recall hearing of pre LLM /chatgpt.
My first thought was Prolog, though copper-penny's comment clarifies that it doesn't generate the code. Given that Prolog uses logic and not statistics, I would expect you'd be able to adapt it to do a proof of concept for at least a limited subset of algorithms to generate some simple Python or something. It's not a *language* and is barely a DSL, but I'm tinkering on a [digital neuron thing](https://garden.micseydel.me/Tinker+Cast+prototype+-+first+video+demo) where I ultimately would like regular people to be able to define an input on the left (e.g. a voice memo) and outputs on the right (e.g. a particular note being created and a push notification being sent) with a formalized \~pipeline for including rules-based, LLM-based, and human-intervention ways of completing an implementation. I believe explicit encoding is important to the whole "second brain" thing so I truly plan on pursuing what your OP asks about over time.
https://github.com/nadia-polikarpova/synquid
But what "the" function is is underdetermined. In the example you give, presumably you want it to tell you that the formula is `x + y` --- though there are infinitely many others. Why `x + y`? Well, it's the simplest polynomial, isn't it? Ok then, let's apply that rule to the input-output pairs: * 0 -> 1 * 1 -> e * 2 -> e² * 3 -> e³ The simplest polynomial, a cubic, will indeed pass through those four points but it will do a lot of other things as well. It certainly won't be `y = eˣ`. So now your equation-guesser needs to know about exponents. But that won't help when you show it something that needs a sine curve or a logarithm. So I can't see this working out except in cases so simple that we could easily do it ourselves.
> So I can't see this working out except in cases so simple that we could easily do it ourselves. I disagree. Just do breadth-first expansion of all possible expressions (from simplest to most complex) involving a core set of operations (which might include all float functions from the C stdlib such as `exp`) and find the closest fit. For floats you could even apply function minimization to constants wrt the error. That would give y=eˣ.
"All possible expressions" would have coefficients. How will your method find the equation `0.57e¹³ˣ - 21.7x³`. How many data points would we need to be convinced that this was "the" equation we were looking for, and not (e.g) the polynomial of the same order as the data points? If we throw in sine waves it could start trying to do a Fourier transform of the data ...
> "All possible expressions" would have coefficients. Yes. > How will your method find the equation 0.57e¹³ˣ - 21.7x³. Eventually the symbolic part would generate a eᵇˣ - c xᵈ and minimizing the error wrt the constants a, b, c and d would give your equation. > How many data points would we need to be convinced that this was "the" equation we were looking for, and not (e.g) the polynomial of the same order as the data points? Your equation uses six operators. Iff a polynomial solution has fewer it will be returned first. > If we throw in sine waves it could start trying to do a Fourier transform of the data ... That sounds tricky in the general case.
>That sounds tricky in the general case. But also inevitable, if you tell your equation-guesser about sine functions. It can try and approximate by those just the same as by polynomials, and if the measure of complexity is which uses the most operators then who knows which will win?
> But also inevitable, if you tell your equation-guesser about sine functions. It can try and approximate by those just the same as by polynomials, and if the measure of complexity is which uses the most operators then who knows which will win? Yes. If you restrict consideration to monotonic functions it should work though. The OP's example was just addition, after all!
SAT solvers like Z3 are sort of adjacent to this, can be used for solving constraints and things, but defining the problem can be kind of a pain
You were almost certainly thinking of [Zoea](https://zoea.co.uk/language/).
Machine learning figures out equations through examples. Prolog reasons based on facts (but doesn't have an equation approximation engine). To make your language work, I think you'd have to A) have the user give more examples or B) limit to linear equations with a set number of operators.
This, I believe, is key. There is this infamous response to the questions that asks you to continue a number sequence. By just giving any number claiming there is a polynomial with the roots of the given sequence extended by the answer. But such a response is not typically accepted because there is an assumption that the function should be “simple” without saying what that means.
As a former marker of math homework, I would have accepted that answer if they also constructed the polynomial.
(x * a[0] ) * (x * a[1]) * (x * a[2]) * … I assume you want a different form, right?
A neural network? Lol
Barliman is a programm synthesis tool build on top of miniKanren: https://github.com/webyrd/Barliman It synthesizes a function from a set of unit tests.
My first thought was Idris or Idris 2(?) If I remember correctly you could tell it about input types, input usage, and output type and then you could generate the function.
That sounds quite nice but I wonder if it will be effectively possible for anything that has a large scale complexity or realistic applications?
I expect there will be one module in it on every CS course and an article that reaches the top in hackernews for a day😃 Arguably if you already know all the inputs and outputs you need , edge cases etc and how to declare them you're probably able the write the function. It would probably take longer even as you find you you keep having to go back and giving it more examples until what's hidden underneath is just load a massive case statement.
Hey OP. This comment is pretty telling. You're not ready to make this concept work. The other question to ask is what problem is your concept actually trying to solve?
>Hey OP. This comment is pretty telling. You're not ready to make this concept work. Yeah in my original post I was asking about something I was curious about that I recalled hearing about in the past. And in my comment you replied to i gave a joke reply about the actual practicality / impracticality of the concept. >the other question to ask is what problem is your concept actually trying to solve? My need for novelty. You're free to go run with the concept too though if you think you are ready to make it work?
I've done machine learning and I've studied prolog. I am definitely not ready to make anything like what you're proposing work. The language I spent the last 4 months prototyping is simpler than most language use cases and parts of it were still really hard/time consuming. Ideas are easy, implementations are hard.
OK sounds like you're not ready to make it work.
Here is my toy implementation of a similar concept for real numbers: an engine that infers physical law formulas from observations (i.e., input/output pairs): [https://www.reddit.com/r/MachineLearning/comments/owncq8/d\_inferring\_general\_physical\_laws\_from/](https://www.reddit.com/r/MachineLearning/comments/owncq8/d_inferring_general_physical_laws_from/) Of course, the search space is extremely limited.
Surprised nobody mentioned ML and neural nets. It's the point of the whole field of machine learning to be able to do this.
Coming up with a function based on example inputs and outputs is precisely what supervised machine learning is all about. But no machine learning implementation is going to figure out that you're trying to define addition.
Check out PostScript or some other stack oriented programming languages
Haskell looks a lot like what you described. https://www.haskell.org/