Reputation: 9641

Programming languages that define the problem instead of the solution?

Are there any programming languages designed to define the solution to a given problem instead of defining instructions to solve it? So, one would define what the solution or end result should look like and the language interpreter would determine how to arrive at that result. Looking at the list of programming languages, I'm not sure how to even begin to research this.

The best examples I can currently think of to help illustrate what I'm trying to ask are SQL and MapReduce, although those are both sort of mini-languages designed to retrieve data. But, when writing SQL or MapReduce statements, you're defining the end result, and the DB decides the best course of action to arrive at the end result set.

I could see these types of languages, if they exist, being used in crunching a lot of data or finding solutions to a set of equations. The dream language would be one that could interpret the defined problem, identify which parts are parallelizable, and execute the solution across multiple processes/cores/boxes.

Upvotes: 26

Answers (15)

Andrew Salinas

Reputation: 54

Google created something called FunSearch that does something similar to what you’re asking.

Upvotes: 0

hellodanylo

Reputation: 400

Meta Discussion

What constitutes a problem or a solution is not absolute and depends on the level of abstraction that you are taking as a reference point.

Let's compare the following 3 languages: SQL, C++, and CPU instructions.

C++ vs CPU instructions

If you choose array manipulation as the desired level of abstraction, then C++ allows you to "define the problem" instead of the solution:

array[i * 2 + 3] = 5;
array[t] = array[k - m] - 1;

Note what this C++ snippet does not state: how the memory is laid out, how many bits are used by each array element, which CPU registers hold the data, and even in which order the arithmetic operations will be performed (as long as the result is the same).

The C++ compiler, however, will translate this code to lower-level CPU instructions that will contain all of these details.

At the abstraction level of array manipulation, C++ is declarative, and CPU instructions are imperative.

SQL vs C++

If you choose a sorting algorithm as the desired level of abstraction, then SQL allows you to "define the problem" instead of the solution:

select *
from table
order by key

This snippet of code is declarative with respect to the sorting algorithm's level of abstraction because it declares that the output is sorted without using lower-level concepts (like array manipulation).

If you had to sort an array in C++ (without using a library), the program would be expressed in terms of array manipulation steps of a particular sorting algorithm.

void sort(int *array, int size) {
   int key, j;
   for(int i = 1; i < size; i++) {
      key = array[i];
      j = i;
      while(j > 0 && array[j-1] > key) {
         array[j] = array[j-1];
         j--;
      }
      array[j] = key;
   }
}

This snippet is not declarative with respect to the sorting algorithm's level of abstraction because it uses concepts (such as array manipulation) that are constituents of the sorting algorithm.

Summary

To summarize, whether a language defines problems or solutions depends on what problems and solutions you are referring to.

Many answers here have brought up examples: SQL, LINQ, Prolog, Lisp, OCaml. I am sure there are many useful levels of abstractions with respect to which these languages are declarative.

However, do not forget that you can build a language with an even higher level of abstraction on top of them.

Upvotes: 1

peroumal1

Reputation: 266

I would say Objective Caml (OCaml) too...

Upvotes: 2

Meredith L. Patterson

Reputation: 4911

This sounds like a description of a declarative language (specifically a logic programming language), the most well-known example of which is Prolog. I have no idea whether Prolog is parallelizable, though.

In my experience, Prolog is great for solving constraint-satisfaction problems (ones where there's a set of conditions that must be satisfied) -- you define your input set, define the constraints (e.g., an ordering that must be imposed on the previously unordered inputs) -- but pathological cases are possible, and sometimes the logical deduction process takes a very long time to complete.

If you can define your problem in terms of a Boolean formula you could throw a SAT solver at it, but note that the 3SAT problem (Boolean variable assignment over three-variable clauses) is NP-complete, and its first-order-logic big brother, the Quantified Boolean formula problem (which uses the existential quantifier as well as the universal quantifier), is PSPACE-complete.

There are some very good theorem provers written in OCaml and other FP languages; here are a whole bunch of them.

And of course there's always linear programming via the simplex method.

Upvotes: 12

outis

Reputation: 77400

While mathematical proofs don't constitute a programming language, they do form a formal language where you simply define solutions (as long as you allow nonconstructive proofs). Of course, it's not algorithmic, so "math" might not be an acceptable answer.

Upvotes: 0

David Plumpton

Reputation: 1927

Lisp. There are so many Lisp systems out there defined in terms of rules not imperative commands. Google ahoy...

Upvotes: 1

Jon Smock

Reputation: 9641

LINQ could also be considered another declarative DSL (aschewing the argument that it's too similar to SQL). Again, you declare what your solution looks like, and LINQ decides how to find it.

The beauty of these kinds of languages is that projects like PLINQ (which I just found) can spring up around them. Check out this video with the PLINQ developers (WMV direct link) on how they parallelize solution finding without modifying the LINQ language (much).

Upvotes: 0

Gordon Potter

Reputation: 5862

This may seem flippant but in a sense that is what stackoverflow is. You declare a problem and or intended result and the community provides the solution, usually in code.

It seems immensely difficult to model dynamic open systems down to a finite number of solutions. I think there is a reason most programming languages are imperative. Not to mention there are massive P = NP problems lurking in the dark that would make such a system difficult to engineer.

Although what would be interesting is if there was a formal framework that could leverage human input to "crunch the numbers" and provide a solution, perhaps imperative code generation. The internet and google search engines are kind of that tool but very primitive.

Large problems and software are basically just a collection of smaller problems solved in code. So any system that generated code would require fairly delimited problem sets that can be mapped to more or less atomic solutions.

Upvotes: 1

Savvas Dalkitsis

Reputation: 11592

The closest you can get to something like this is with a logic language such as Prolog. In these languages you model the problem's logic but again it's not magic.

Upvotes: 14

quillbreaker

Reputation: 6225

I remember reading something about computation using DNA back when I was in college. You would put segments of DNA in a solution that represented segments of the problem, and define it in such a way that if the DNA fits together, it's a valid solution. Then you let the properties of chemicals solve the problem for you and look for finished strands that represent a solution. It sounds sort of like what you are refering to.

I don't recall if it was theoretical or had been done, though.

Upvotes: 0

Ray

Reputation: 1585

A lot of languages define more problems than solutions (don't take this one seriously).

On a serious note: one more vote for Prolog and different kinds of DSLs designed to be declarative.

Upvotes: 0

tinyd

Reputation: 952

There are various Java-based rules engines which allow declarative programming - Drools is one that I've played with and it seems pretty interesting.

Upvotes: 0

Ionuț G. Stan

Reputation: 179119

These languages are commonly referred to as 5th generation programming languages. There are a few examples on the Wikipedia entry I have linked to.

Upvotes: 5

Karl Voigtland

Reputation: 7705

What about Declarative Programming? Excerpt from wikipedia article (emphasis added):

In computer science, declarative programming is a programming paradigm that expresses the logic of a computation without describing its control flow. Many languages applying this style attempt to minimize or eliminate side effects by describing what the program should accomplish, rather than describing how to go about accomplishing it. This is in contrast with imperative programming, which requires an explicitly provided algorithm.

Upvotes: 31

nightingale2k1

Reputation: 10315

Let me try to answer ... may be Prolog could answer your needs.

Upvotes: 4

Programming languages that define the problem instead of the solution?

Answers (15)

Meta Discussion

C++ vs CPU instructions

SQL vs C++

Summary

Related Questions