One common problem we deal with in programming goes like this: I have certain inputs. I desire a certain output. What function (or combination of functions) will give me the desired output?
Since a relation makes no distinction between "inputs" and "outputs", relational programming is one way we can approach this problem. All we need is a relation that relates a program, its input(s), and its output. Then, by fixing the inputs and output, we can generate programs that produce the desired output. We could use such a tool as an aid to guide us in writing programs. I.e., we can basically write queries to find core functions (and combinations thereof) that produce the desired output. But we can take this even further. In general, we can write specifications for functions. From this specification, we can generate programs that conform to the specification. But we don't have to stop there. Instead of specifying (either entirely or in part) the inputs and output, we can fix and leave free any components of the relation to any degree. For example, we might (partially) specify a program and its output. We can then generate inputs that result in the given output. So, at least in theory, a relational lisp interpreter would give us (in many respects) the "ultimate" development tool. If we leave everything free (i.e., no restrictions on the programs, its inputs, or the output), then we can generate every possible lisp program. This isn't very useful per se. But by partially specifying one or more components of the relation, we provide a priori knowledge to help guild the process. Even if it is not enough to produce the desired result immediately, we might be able to gain further insight into the specific problem we are trying to solve. From this, we can refine the specification. We can iterate this process until we arrive at an acceptable solution. This gives us a development process where human and machine "collaborate" to derive a program. Unfortunately, the power of relational programming comes at a cost. That cost is divergence (non-termination of the search algorithm). It is extremely tricky to write relations in a way that guarantee (when there are a fininte number of solutions) that (a) all soutions will be found in a finite amout of time, and (b) if there are no (more) solutions, the search terminates in a finite amount of time. This largely boils down to limiting the search space to a finite domain (while ensuring no valid results are excluded). This seems simple, but is far from trivial in practice (see, for instance, the chapter on relational arithmetic in Byrd's thesis). The possibility of infinite results sets presents its own problems, such as how to output such an infinite set. core.logic uses Clojure's lazy seqs for this. Minikanren's original implementation in Scheme requires limiting the number of results rendered from an inifinite result set. Furthermore, whether the solution set is inifinite or finite, it can be difficult to separate "interesting" solutions from "mundane" solutions. Minikanren's interleaving search can help with this (especially when the solution set is infinite), but is not a panacea. In the case of generating programs, it would also be desirable that the *generated* programs are guaranteed to terminate. However, is has been shown that there algorithm that is capable of determining (for all possible programs) if a given program always terminates for any input. So it would appear that we must choose between the possibility of non-terminating programs and limiting the range of generated programs to those which (the generative system) can prove to be terminating. Different situations may call for different choices. Hopefully this helps highlight some of the (theoretical) use-cases of a relational lisp interpreter, as well as provide some insight into the difficulties in implementing such an interpreter. > > On Wednesday, June 22, 2016 at 9:22:35 PM UTC-5, Ashish Negi wrote: One usecase of a "relational" lisp interpretter > > > > I am reading joy of clojure. In the "forward to second edition" William E > Byrd and Daniel P Firedman says : > > > > *As with recursion, the art of defining little languages encourages—and > rewards—wishful thinking. You might think to yourself, “If only I had a > language for expressing the rules for legal passwords for my login system.” > A more involved example—a story, really—started several years ago, when we > thought to ourselves, “If only we had the right relational language, we > could write a Lisp interpreter that runs backward.”[2] > <http://www-legacy.manning.com/fogus2/excerpt_foreword2ed.html#footnote-2> > What does this mean? * > > > *An interpreter can be thought of as a function that maps an input > expression, such as (+ 5 1), onto a value—in this case, 6. We wanted to > write an interpreter in the style of a relational database, in which either > the expression being interpreted or the value of that expression, or both, > can be treated as unknown variables. We can run the interpreter forward > using the query (interpret ‘(+ 5 1) x), which associates the query variable > x with the value 6. Better yet, we can run the interpreter backward with > the query (interpret x 6), which associates x with an infinite stream of > expressions that evaluate to 6, including (+ 5 1) and ((lambda (n) (* n 2)) > 3). (Brainteaser: determine the behavior of the query (interpret x x).)* > > Although the writer gave an example of `*(interpret x 6)*` i could not > imagine the use case of `*lisp interpreter running backwards*` ? > I am not even sure what he meant exactly. > > Thinking on it, i could only relate this to *theorem prover*s where you > run backwards from the result. > Can somebody explain this ? > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
