Talk:Declarative programming
From Wikipedia, the free encyclopedia
A lot of this material was taken from old versions of the Combinatorial_search node. I think I have permission to do this as this and the Combinatorial_search node are actually part of a homework assignment. maxomai
I thought C++ and Java are OOP languages.
- Yes, C++ and Java are OOP languages. But OOP languages are imperative languages. So C++ and Java are also imperative languages. -- Derek Ross
Aren't there any object oriented declarative languages? And if so, what's the reason?
Wouldn't CSS and XSLT qualify as good examples of declarative languages, too? — Brianiac 18:05, 15 Nov 2004 (UTC)
Yes, XML is also declarative.
If you classify OO as imperative, you will have to classify all programming paradigm that runs in an Imperative architecture as Imperative. --Lssilva 12:50, 3 Jan 2005 (UTC)
Just put a header on the applications section, and added Enterprise Programming as an example application. --harburg 22:04, 6 Jan 2005 (UTC)
It doesn't seem to be entirely clear what Declarative programming is. Why do some consider the distinction Functional vs. Imperative, and not Declarative vs. Imperative (for instance: http://www.haskell.org/complex/why_does_haskell_matter.html and imperative programming comparison)? Is functional programming really a form of declarative programming (I have my doubts, but perhaps the definitions for functional programming, I've come across are also mistaken).
Perhaps it needs to be made clear where exactly the boundaries of imperative and declarative programming are. Makefiles, for instance, seem to be declarative (I stand under correction though), but can easily be extended (or, rather, hooked onto) with any number of approaches. I assume that imperative languages could also be extended with declarative languages too (regular expressions within certain imperative languages, may be a case in point).
See also the discussion on Declarative Programming Languages.
The reason why people don't consider the distiction is that functional languages are not declarative. That is in error on this page. I thought I should post discussion before changing that. In Concepts of Programming Lanuages, Robert Sebesta constrasts declarative programming from procedural, and indicates functional languages are primarily procedural. This article and the procedural article seem to include very little on the two ideas, and give the wrong impression of the concepts because editors have written on things they are more familiar with like OO or what a procedure is. ProLog is probably the best example of a declarative lanuage. It does not use procedures to calculate things, it simply indicates what it expects (there is no details on "how"). -has
[edit] declarative program is not Turing-complete
I'm willing to stand corrected, since I don't know most of the languages listed in the examples. But if you do revert my new paragraph, you should explain how SQL (not a programming language but a "data sublanguage", in the words of C. J. Date) and XML (even more specialized -- what I would call a "data storage sublanguage") and XSLT (yet more specialized -- a conversion utility for XML) and Prolog (according to Wikipedia, "In Prolog you supply a database of facts and rules; you can then perform queries on the database") got into the list of examples (well, XML is not in the list in the Article but it is categorized as a declarative language in Talk) without any mention of the fact that they are not UTMs.
TH 01:11, 13 December 2005 (UTC)
- First of all, programs or stylistic ambitions are not Turing-complete, computational models can be, and most languages are. Turing-completeness isn't about what's practical, it's about what's possible. As an example, you can turn any C program into an XML representation and apply some XSLT to it to produce the output of the C program, if XSLT is Turing-complete (it probably is). We aren't interested in the ways of IO etc. at all, only computation. Another example, C++ is Turing-complete, but so is the compile-time template language in it!
- Now, to give programming languages that are definitely Turing-complete: Lisp, Prolog, Haskell. They are usually regarded as declarative programming languages and it is easy to write programs in them in the declarative style. I tried to rewrite the section to my best knowledge. --TuukkaH 20:53, 17 December 2005 (UTC)
I had to take this whole paragraph out:
" Many of the dialects being created based on the XML format can be described as declarative due largely to the increasing popularity of the declarative programming paradigm. "
because:
1. XML is a language, not a format (and not a programming language).
2. All extensions of XML are no more and no less declarative than XML.
3. I see no evidence that declarative programming is becoming more popular in comparison with imperative languages. Cite. Writing XML files is not programming; it's equivalent to writing DML in SQL. Writing DTDs is not programming; challenging it may be, but it's equivalent to writing DDL in SQL.
4. Popularity would be no reason that XML dialects could be described as declarative.
TH 01:29, 13 December 2005 (UTC)
[edit] Makefiles: imperative
Someone asked about makefiles above -- so:
Although the dependency lines of a makefile are declarative, the block of command lines that follow each dependency line are procedural (imperative), because in effect they constitute a shell script.
Just as the data declarations of a Java program, however elaborate, do not make the Java program declarative, the dependency lines of a makefile do not make the makefile declarative.
In short, makefiles are imperative.
TH 03:21, 13 December 2005 (UTC)
I disagree. Makefiles are both declarative (the rules) and imperative (the actions). I don't think it's reasonable to say that anything that is even the slightest bit imperative is therefore imperative without qualification. That would be like saying HTML is imperative because it can embed javascript, or SQL is imperative because the database might have triggers.
Kimbly 19:30, 31 December 2005 (UTC)
[edit] Limitations of declarative languages (with citations)
I reverted recent changes to "Disadvantages", pending (a) someone citing a demonstration that some language among the examples given is Turing-complete, and providing a frank discussion of why so many of them are not Turing-complete; or (b) someone providing a frank discussion of the non-Turing-completeness of imperative languages, which restricts them to solving a tiny fraction of the infinity of problems that are solvable by Turing-complete languages. Note Wikipedia policy on Cite. When I say "a tiny fraction", I mean "a tiny fraction, however large in magnitude" -- I do not mean declarative languages are unimpressive or are toys or are useless or not clean or beautiful.
I removed the phrase "how widely applicable" because I don't see that it addresses the issue that imperative languages are highly restricted (not UTMs). That is a big deal, not a minor flaw. Similarly, I saw the phrase "the interpreter" but I didn't see any discussion addressing the point that this interpreter is otherwise known as "the semi-special-purpose program that you buy or download for free" (MySQL, msql, JESS, etc.).
Here's how it works -- correct me if I'm wrong -- cite if you correct me -- I will cite. With a declarative (general-purpose or Turing-complete) language, you buy a compiler (possibly free; Java, Perl, C++, Delphi, assembler, etc.), and write a special-purpose program to solve your special problem. With an imperative language, you buy a sort-of-special-purpose program (possibly free; see list below). Along with the sort-of-special-purpose program, you get a system for feeding your special data to the program; that system is called a "declarative language". Then the sort-of-special-purpose program chews on your special data to solve your special problem. I cite: MySQL FAQ page; msql FAQ page; any book on XML or SQL; JESS FAQ page; any SQL FAQ page; any expert system or AI system FAQ page. I cite C. J. Date's statement that SQL is not really a language but is instead "a data sub-languages". I believe that declarative languages are confined to solving these types of problems: formal logic queries; data storage (XML in all its varieties), data access (SQL, Quel, etc.); optimization; rule systems (given the rules I put in, is X allowed?). I probably missed one or two -- I would appreciate help completing the list of problem types solvable by the current crop of declarative languages. It's market-driven, so the list is ever changing.
Singapore's airport gate and baggage-machine scheduler is run by an optimization engine (I have forgotten the brand) that balances a tremendous number of factors. For all I know, it saves them a billion dollars a year. It's extremely powerful. Singapore would never want to pay anyone to write the equivalent logic in a UTM. But it's not a Turing machine. It can't balance your checkbook.
(Don't you just love how, if you try to arrow down past the last line of your editing and the last line is not blank, Wikipedia appends a blank line and puts your cursor on it -- a nice touch that Microsoft Word for well over ten years now has still not figured out?)
TH 00:44, 19 December 2005 (UTC)
[edit] Realistic UTMs (spreadsheets -- not); this page bifurcated at best
Maybe we need to concentrate on the concept of a Realistic Universal Turing Machine (RUTM).
A real UTM (infinite paper tape, bi-directional motor, etc.) is not an RUTM -- too clumsy. Nobody discusses UTML, the language of a real (unrealistic) UTM.
A spreadsheet is a UTM, but not an RUTM, because although it's a UTM, it's too specialized (not general-purpose-realistic enough) for anyone to use it as a general-purpose computing language. Therefore no one write graphics drivers for a spreadsheet, so we can't draw little pictures inside the cells; similarly, no one writes regular expression evaluators for spreadsheets, nor all the other libraries that an RUTM tends to accumulate.
So . . . is Haskell an RUTM?
Yes, it absolutely is. For practice, look at http://www.haskell.org/libraries/. For theory, look into Monads, Concurrent Haskell, Software Transactional Memory, etc. Kimbly 19:39, 31 December 2005 (UTC)
And who outside the ivory tower cares about non-R-UTMs, unless they're going to bust out and change the landscape of real-world programming forever?
I believe it's easy to find examples of non-UTM (declarative) languages: Every XML language is non-UTM. Regular expressions are non-UTM. The language of Windows (or KBE, etc.) is a powerful but awkward and nontextual and non-UTM langauge whose lexicals are click, double-click, drop-down, type "ABC", choose menu item, right-drag, mouse-wheel-down, Page Up, etc. Any data entry system that slaps your hand or corrects you when you type something wrong is probably a non-UTM language. Usually they're so simple that we don't call them languages, but that choice is arbitrary. Your telephone dial has a language -- 55512345 is identical to 5551234 in that language; 555123 is syntactically invalid; years ago, 16795551212 was invalid (when the middle digit of an area code was constrained to 0 or 1). There's no meaningful line to draw between these non-UTM languages and Singapore's expert systems rule "Baggage conveyor type 103B223Q cannot unload Boeing 767s".
At best, I think the Declarative Programming page as it stood last week was seriously bifurcated. Bifurcated between the semi-special-purpose engines that I listed a few inches up and *_possibly_* the near-R-UTM languages that some still claim exist; e.g. perhaps Haskell. The crack should either be repaired seamlessly (smooth continuum from your phone-pad's language (lexicals: [0-9*#], Hangup, etc.) to XML to Haskell), or explicated thoroughly (Declarative Languages type S and Declarative Languages type G?).
TH 03:58, 19 December 2005 (UTC)
[edit] O(n**2)? or cite?
I reverted but also clarified my original by giving the time to solution as O(n**2).
Coastalpedia (or anyone else) -- if you feel that the order of the problem is less than n squared, please put your reasoning in and provide a citation. I think Wikipedia needs something more solid than "But that belief is simply wrong" -- the unobvious needs to be substantiated. Has the "belief" been mathematically proven to be wrong? Or is that an empiricaly result, widely confirmed? What exactly is the time to solution? Is it (my guess) that for a lucky client (with a fairly simple problem) the order is slightly over n, and for an unlucky client, the folks who optimized the solution engine haven't gotten it much below n squared.
TH 20:48, 23 December 2005 (UTC)
How can I explain this when you are willing to make assumptions about O(n**2) (or any other order)? No system (other than perhaps naive student projects) does a full search space enumeration to perform constraint satisfaction. Even back in the mid 80s, Prolog systems knew about trimming search spaces. The cite for ALS provides one example of something quite finely tuned well past the point of any "inconvenience". Frankly, it's fundamentally wrong to assume that declarative systems require an interpreter. A constraint satisfaction system? Sure. Interpreter? No.
For that matter, this article contains a number of errors, especially in the conflation of terms, such as the conflation of functional and declarative. This article desperately needs to go back to basics, get the terms defined orthogonally, and build it back up on a solid foundation.
Coastalpedia 07:57, 24 December 2005 (UTC)
[edit] Heavy re-org
I thank Coastalpedia for the example of ASL. I agree on the need for a basic rewrite, so I took a stab at it. I hope I have treated ASL fairly in the rewrite.
I leaned toward the term "conditions", which I found in the first paragraph, but I kept the names of the constituents (data, functions, rules, term-rewriting) that I found in the article. In particular, "functional" is now a secondary concept. But I think there is still some article in in Wikipedia that claims that "functional" and "declarative" are opposites.
I leaned toward the term "engine", but I left the synonyms (interpreter, executor, compiler) in for at least one mention each.
I removed the word "pure", which seemed more confusing than helpful (why pure functional? why not pure logic? why not a mix?).
TH 01:37, 30 December 2005 (UTC)
[edit] References, See also, External links
This article is highly controversial, judging by the edit history. References are a good tool to show we have facts and are discussing notable points of view. If you disagree, you don't need to remove references, you can add to them ones that support your view! I don't know many good references but I like the clear albeit strict definitions in FOLDOC even though they only have "declarative language" instead of "declarative programming".
Another concern of mine is the article's wrong relation of the topic to some close ones. I don't understand why we want to make false claims about domain-specific languages, turing completeness, language classification here. If you want to claim no DSL is turing complete, why not say it on the page on DSLs and get reverted? If you want to claim HTML can be used for programming, why not say it on the page on programming languages and get reverted? I hope the sections See also and External links can help give the article a distinguished scope between all the other topics.
Of course everybody disagrees what the scope should be :-) Declarative programming is a way to programming, a programming paradigm? Declarative programming is computer programming? Declarative programming is the opposite of imperative programming in the sense that the first lacks the concentration on the program state of execution? Declarative programming is also the opposite of procedural programming (or sequential programming more generally) in the sense that the first lacks the step-after-step instructions of program execution? This all is what I read from the FOLDOC articles, what about you people? --TuukkaH 21:01, 1 January 2006 (UTC)
[edit] Declarative UI
I think it could be relevant to add a section about Declarative UIs (like XUL, XAML, etc..), and maybe add a link to User interface markup language article. - Hervegirod 09:58, 14 May 2006 (UTC)
[edit] not Turing-complete = drawback ?
From the article: "One drawback of DSLs is that they are often not Turing-complete." This suggests that Turing-completeness should be mandatory for programming languages. IMHO it is no drawback, if a language is not Turing-complete; unless, you want to use the language to solve problems that require Turing-completeness.
But DSLs a restricted to a certain domain and usually the Turing-completeness is not required. Would you say the drawback of an electric drill is that you cannot cut paper with it? No. Sometimes the it is a drawback if the language IS Turing-complete, because certain things (source code analysis,etc.) are undecidable over Turing-complete languages (Halting problem) while there might be feasible for 'incomplete' DSLs.
--Riedel 09:44, 22 July 2006 (UTC)
[edit] HTML is not presentational anymore...
The W3C made this pretty clear. Most presentational elements have been deprecated as of HTML 4.01 Strict (Transitional is called Transitional for a reason) and those that are still in are on their way out.
The HTML example is currently as follows:
- For example, HTML web pages are declarative because they describe what the page should look like — title, font, text, images — but not how to actually display the page on a computer screen.
This is thus fundamentally wrong. HTML doesn't describe what the page looks like, that's the job of stylesheets (CSS, XSLT, etc), it describes what the page consists of. It structures the content of the website and denotes relations (hence "Hypertext") between the document and other files or entities.
According to the second definition, HTML is definitely not a declarative programming language. Another snippet says:
- In a declarative program you write (declare) a data structure that is processed by a standard algorithm (for that language) to produce the desired result. When you write a web page for example, you declare what the page should look like in HTML, and the browser's procedural algorithm translates this into the pixels on the display.
When you write a web page, you declare its structure and content (i.e. semantics) in HTML. CSS describes the styling.
Also, unlike someone stated earlier on this Talk page, XML is not a declarative programming language in any sense, because it is only a syntax. XML dialects can be declarative, but XML itself does not have any semantics beyond the XML headers. In that sense, XML is merely a standardised format for markup languages, not a markup language of that format itself. It's not much more of a language than ASCII or comma-separated values.
Further, the first definition of declarative languages is a bit vague. It could be used to label any data format that is not an imperative programming language a declarative programming language. This clashes with the definition of a "programming language".
Calling semantic HTML (granted, prior to HTML 4.01 it did have a lot of presentation mixed into it) a programming language is misleading at best. To quote the article "programming language":
- Non-computational languages, such as markup languages like HTML or formal grammars like BNF, are usually not considered programming languages; however, informal usage sometimes includes them.
As an aside: SGML has "processing instructions", but I wouldn't rate them as anything but a more generic form of the modifier glyphs found in Unicode.
Apparently the first definition in this article rates anything with even a hint of embedded meta-data as a declarative programming language. This use is not only vague, but I would say that it is heavily disputed and non-standard. I've removed the passages about HTML from this article and Declarative programming language (a bit of redundant an article, IMO). Feel free to put them back in, but only if you can find a less authorative wording. — Ashmodai (talk · contribs) 10:45, 27 August 2006 (UTC)
