Editing Declarative programming (section)

==Examples==

===Lisp===
[[Lisp (programming language) |Lisp]] is a family of programming languages loosely inspired by mathematical notation and [[Alonzo Church]]'s [[lambda calculus]]. Some dialects, such as [[Common Lisp]], are primarily imperative but support functional programming. Others, such as [[Scheme (programming language)|Scheme]], are designed for functional programming.

In Scheme, the [[factorial]] function can be defined as follows:

<syntaxhighlight lang=scheme>
(define (factorial n)
    (if (= n 0)                     
        1                             ;;; 0! = 1
        (* n (factorial (- n 1)))))   ;;; n! = n*(n-1)!
</syntaxhighlight>

This defines the factorial function using its recursive definition. In contrast, it is more typical to define a procedure for an imperative language.

In lisps and lambda calculus, functions are generally [[first-class citizen]]s. Loosely, this means that functions can be inputs and outputs for other functions. This can simplify the definition of some functions.

For example, writing a function to output the first n [[square number]]s in [[Racket (programming language)|Racket]] can be done accordingly:

<syntaxhighlight lang=scheme>
(define (first-n-squares n)
    (map (lambda (x) (* x x))          ;;; A function mapping x -> x^2
         (iota n)))                    ;;; Lists the first n naturals
</syntaxhighlight>

The [[Map (higher-order function) |map]] function accepts a function and a list; the output is a list of results of the input function on each element of the input list.

===ML===
[[ML (programming language)|ML]] (1973)<ref name="Gordon1996">{{cite web
 | last = Gordon
 | first = Michael J. C.
 | author-link = Michael J. C. Gordon
 | year = 1996
 | title = From LCF to HOL: a short history
 | url = http://www.cl.cam.ac.uk/~mjcg/papers/HolHistory.html
 | access-date = 2021-10-30
 | archive-date = 2016-09-05
 | archive-url = https://web.archive.org/web/20160905201847/http://www.cl.cam.ac.uk/~mjcg/papers/HolHistory.html
 | url-status = live
 }}</ref> stands for "Meta Language." ML is statically typed, and function arguments and return types may be annotated.<ref name="cpl_3rd-ch9-233">{{cite book
  | last = Wilson
  | first = Leslie B.
  | title = Comparative Programming Languages, Third Edition
  | publisher = Addison-Wesley
  | year = 2001
  | page = 233
  | isbn = 0-201-71012-9
}}</ref> 

{{sxhl|2=sml|1=fun times_10(n : int) : int = 10 * n;}}

''ML'' is not as bracket-centric as ''Lisp'', and instead uses a wider variety of syntax to codify the relationship between code elements, rather than appealing to list ordering and nesting to express everything. The following is an application of <code>times_10</code>:

 times_10 2

It returns "20 : int", that is, <code>20</code>, a value of type <code>int</code>. 

Like ''Lisp'', ''ML'' is tailored to process lists, though all elements of a list must be the same type.<ref name="cpl_3rd-ch9-235">{{cite book
  | last = Wilson
  | first = Leslie B.
  | title = Comparative Programming Languages, Third Edition
  | publisher = Addison-Wesley
  | year = 2001
  | page = 235
  | isbn = 0-201-71012-9
}}</ref>


===Prolog===
[[Prolog]] (1972) stands for "PROgramming in LOGic." It was developed for natural language [[question answering]],<ref name="PrologHistory">{{cite web
  | url = http://alain.colmerauer.free.fr/alcol/ArchivesPublications/PrologHistory/19november92.pdf
  | title = Birth of Prolog
  | date = November 1992
  | access-date = 2022-05-25
  | archive-date = 2015-04-02
  | archive-url = https://web.archive.org/web/20150402111123/http://alain.colmerauer.free.fr/alcol/ArchivesPublications/PrologHistory/19november92.pdf
  | url-status = live
  }}</ref> using SL resolution<ref>{{cite journal |author1=Robert Kowalski |author2=Donald Kuehner |url=http://www.doc.ic.ac.uk/~rak/papers/sl.pdf |title=Linear Resolution with Selection Function |journal=Artificial Intelligence |issn=0004-3702 |volume=2 |issue=3–4 |date=Winter 1971 |pages=227–260 |doi=10.1016/0004-3702(71)90012-9 |access-date=2023-08-13 |archive-date=2015-09-23 |archive-url=https://web.archive.org/web/20150923215814/http://www.doc.ic.ac.uk/~rak/papers/sl.pdf |url-status=live }}</ref> both to deduce answers to queries and to parse and generate natural language sentences.

The building blocks of a Prolog program are ''facts'' and ''rules''. Here is a simple example:
<syntaxhighlight lang=prolog>
cat(tom).                        % tom is a cat
mouse(jerry).                    % jerry is a mouse

animal(X) :- cat(X).             % each cat is an animal
animal(X) :- mouse(X).           % each mouse is an animal

big(X)   :- cat(X).              % each cat is big
small(X) :- mouse(X).            % each mouse is small

eat(X,Y) :- mouse(X), cheese(Y). % each mouse eats each cheese
eat(X,Y) :- big(X),   small(Y).  % each big being eats each small being
</syntaxhighlight>

Given this program, the query <syntaxhighlight inline lang=prolog>eat(tom,jerry)</syntaxhighlight> succeeds, while <syntaxhighlight inline lang=prolog>eat(jerry,tom)</syntaxhighlight> fails. Moreover, the query <syntaxhighlight inline lang=prolog>eat(X,jerry)</syntaxhighlight> succeeds with the answer substitution <syntaxhighlight inline lang=prolog>X=tom</syntaxhighlight>.

Prolog executes programs top-down, using [[SLD resolution]] to [[backward chaining |reason backwards]], reducing goals to subgoals. In this example, it uses the last rule of the program to reduce the goal of answering the query <syntaxhighlight inline lang=prolog>eat(X,jerry)</syntaxhighlight> to the subgoals of first finding an X such that <syntaxhighlight inline lang=prolog>big(X)</syntaxhighlight> holds and then of showing that <syntaxhighlight inline lang=prolog>small(jerry)</syntaxhighlight> holds. It repeatedly uses rules to further reduce subgoals to other subgoals, until it eventually succeeds in [[Unification (computer science)#Application: unification in logic programming |unifying]] all subgoals with facts in the program. This backward reasoning, goal-reduction strategy treats rules in logic programs as procedures, and makes Prolog both a declarative and [[procedural programming#Logic programming |procedural programming]] language.<ref>Robert Kowalski [http://www.doc.ic.ac.uk/~rak/papers/IFIP%2074.pdf Predicate Logic as a Programming Language] {{Webarchive|url=https://web.archive.org/web/20160207012437/http://www.doc.ic.ac.uk/~rak/papers/IFIP%2074.pdf |date=2016-02-07 }} Memo 70, Department of Artificial Intelligence, University of Edinburgh.  1973. Also in Proceedings IFIP Congress, Stockholm, North Holland Publishing Co., 1974, pp. 569-574.</ref>

The broad range of Prolog applications is highlighted in the Year of Prolog Book,<ref name="Prolog Book">{{cite book |last1=Warren |first1=D.S. |editor-last1=Warren |editor-first1=D.S. |editor-last2=Dahl |editor-first2=V. |editor-last3=Eiter |editor-first3=T. |editor-last4=Hermenegildo |editor-first4=M.V. |editor-last5=Kowalski |editor-first5=R. |editor-last6=Rossi |editor-first6=F. |chapter=Introduction to Prolog |title=Prolog: The Next 50 Years |series=Lecture Notes in Computer Science() |date=2023 |volume=13900 |publisher=Springer, Cham. |doi=10.1007/978-3-031-35254-6_1 |pages=3–19|isbn=978-3-031-35253-9 }}</ref> celebrating the 50 year anniversary of Prolog.

===Datalog===
The [[Datalog#History |origins of Datalog]] date back to the beginning of logic programming, but it was identified as a separate area around 1977. [[Syntax and semantics of logic programming |Syntactically and semantically]], it is a subset of Prolog. But because it does not have [[Prolog#Data types |compound terms]], it is not [[Turing completeness|Turing-complete]].

Most Datalog systems execute programs bottom-up, using rules to [[forward chaining |reason forwards]], deriving new facts from existing facts, and terminating when there are no new facts that can be derived, or when the derived facts unify with the query. In the above example, a typical Datalog system would first derive the new facts:
<syntaxhighlight lang="prolog">
animal(tom).
animal(jerry).
big(tom).
small(jerry).
</syntaxhighlight>

Using these facts, it would then derive the additional fact:
<syntaxhighlight lang="prolog">
eats(tom, jerry).
</syntaxhighlight>

It would then terminate, both because no new, additional facts can be derived, and because the newly derived fact unifies with the query <syntaxhighlight lang="prolog">
eats(X, jerry).</syntaxhighlight>

Datalog has been applied to such problems as [[data integration]], [[information extraction]], [[Computer network|networking]], [[security]], [[cloud computing]] and [[machine learning]].<ref>{{cite conference | url = http://www.cs.ucdavis.edu/~green/papers/sigmod906t-huang.pdf | conference = SIGMOD 2011 | title = Datalog and Emerging applications | last1 = Huang | first1 = Shan Shan | last2 = Green | first2 = Todd J. | last3 = Loo | first3 = Boon Thau | publisher = Association for Computing Machinery | date = June 12–16, 2011 | location = Athens, Greece | isbn = 978-1-4503-0661-4 | access-date = 2023-08-13 | archive-date = 2020-10-22 | archive-url = https://web.archive.org/web/20201022234145/https://www.cs.ucdavis.edu/~green/papers/sigmod906t-huang.pdf | url-status = live }}</ref><ref>{{Cite conference|title=Neural Datalog Through Time: Informed Temporal Modeling via Logical Specification|book-title=Proceedings of ICML 2020|last1=Mei |first1=Hongyuan |last2=Qin |first2=Guanghui |last3=Xu |first3=Minjie |last4=Eisner |first4=Jason |year=2020 |arxiv=2006.16723 }}</ref>

=== Answer Set Programming===
[[Answer set programming]] (ASP) evolved in the late 1990s, based on the [[stable model semantics|stable model]] (answer set) semantics of logic programming. Like Datalog, it is a subset of Prolog; and, because it does not have compound terms, it is not Turing-complete.

Most implementations of ASP execute a program by first "grounding" the program, replacing all variables in rules by constants in all possible ways, and then using a propositional SAT solver, such as the [[DPLL algorithm]] to generate one or more models of the program.

Its applications are oriented towards solving difficult [[search algorithm|search problems]] and [[knowledge representation]].<ref>{{cite book |first=Chitta |last=Baral |title=Knowledge Representation, Reasoning and Declarative Problem Solving |url=https://archive.org/details/knowledgereprese00bara |url-access=registration |year=2003 |publisher=Cambridge University Press |isbn=978-0-521-81802-5}}</ref><ref>{{cite book |first=Michael |last=Gelfond |chapter=Answer sets |editor1-first=Frank |editor1-last=van Harmelen |editor2-first=Vladimir |editor2-last=Lifschitz |editor3-first=Bruce |editor3-last=Porter |title=Handbook of Knowledge Representation |chapter-url=https://books.google.com/books?id=xwBDylHhJhYC&pg=PA285 |year=2008 |publisher=Elsevier |isbn=978-0-08-055702-1 |pages=285–316 }} [http://www.depts.ttu.edu/cs/research/krlab/pdfs/papers/gel07b.pdf as PDF] {{Webarchive|url=https://web.archive.org/web/20160303231241/http://www.depts.ttu.edu/cs/research/krlab/pdfs/papers/gel07b.pdf |date=2016-03-03 }}</ref>