Wikipedia has a pretty good definition of “declarative language”. It goes something like this:
[A declarative language] describes what the program must accomplish in terms of the problem domain, rather than describe how to accomplish it as a sequence of the programming language primitives (the how being left up to the language’s implementation).
If you take this definition seriously, then a declarative language is not a programming language. A declarative language has no concept of control flow or evaluation order or sequential evaluation of language primitives. If you have to execute a program in your head, as an ordered sequence of steps, using a mental model of an abstract machine, in order to understand what it means, then the program is not declarative.
If a language is implemented on a computer, then the implementation will contain an abstract machine that executes a series of operations in some order. If the language contains features that expose the order of operations executed by the abstract machine, then the language is not declarative.
According to this definition, “declarative programming language” is a contradiction in terms. A language is either declarative, or it is a programming language, but not both. I think this conflict between being declarative and being a programming language is at the heart of the confusion over what the term “declarative programming language” could possibly mean.
Robert Harper has some good observations on the confusion inherent in the term “declarative programming language”:
Probably not many people in the programming language community would be happy with my definition of a declarative language.
Partly that’s because, as Harper observers, “declarative language” is used as an expression of approval, so language developers will claim this term and apply it to their language to improve the language’s status. This tendency is on display in a recent Lobsters post, Why does nobody seem to know what imperative and declarative actually mean?, where the author, an employee of Palumi, argues that Palumi is declarative, and not imperative, as many people are claiming.
And partly it’s because programmers, being programmers, want the languages they use to be as expressive as programming languages. Any declarative language used by programmers is likely to be extended until it is no longer declarative. This happened with regular expressions, which originated in mathematics, but which were extended by various programming communities until they had captures, back references, recursion, greedy and non-greedy matches, etc. Now these regexes are no longer “regular” in the original mathematical sense, they have an order of evaluation, and they are no longer declarative. JSON is declarative, but it isn’t a programming language, so now we have Jsonette and Dhall, which are “programmable configuration languages”. I’m happy that the creators of Dhall chose not to describe their language as a “declarative programming language”.
My list of declarative languages would include:
regular expressions, as originally defined in mathematics
context free grammars, in the original sense (without “operational” and order dependent extensions)
JSON
In these examples,
A regular expression (in the original sense) denotes a set of strings.
A context free grammar (in the original, unextended sense) denotes a set of token sequences.
A JSON program denotes a hierarchical data structure.
The denotational semantics are simple, compositional and direct. State threading is not required to model state transitions in some underlying abstract machine.
The linked article includes Prolog. But Prolog is a programming language, and it isn’t declarative even by more liberal definitions of “declarative”, as Robert Harper points out: “Prolog has imperative features, such as assert and retract, that have imperative meaning”.
I think that the author of the linked article may be saying the same thing as I just said above using more formal and mathematical language. His criterion “has a semantics which relies on some existential quantifiers which it is not immediately obvious how to discharge” and “the semantics is not well moded” appears to mean the same thing as my “doesn’t have an order of evaluation”. I’m not certain, because he includes regular expressions with backreferences, and prolog with cuts, as declarative languages, even while noting that these features “expose the operational model”. Maybe the author’s definition of declarative is more like “doesn’t have a total order of evaluation”? Not sure.
I think you haven’t supplied your definition of a programming language. Is the untyped lambda calculus not a programming language? Or is it somehow not declarative?
Good point, so here’s another attempt, based on the “denotational semantics” post elsewhere in this page.
a level 0 language (Pure Declarative) has a direct denotational semantics that maps expressions directly onto denotations that part of the high level domain or purpose of the language. Examples include original regular expressions, original context free grammars, JSON, the calculator language, and the combinator calculus. The meaning of a term is independent of its lexical and dynamic context.
a level 1 language (Lexically Scoped Declarative) has a denotational semantics where the denotations are functions from a lexical environment to a denotation in the domain. The meaning of a term depends on the lexical context (which is static). Examples include the lambda calculus.
a level 2 language (Imperative) has a denotational semantics where the denotations are functions that take a state as an argument and return a modified state as one of the results. The meaning of a term depends on the runtime state (which is dynamic).
I’m using the numbers 0, 1 and 2 because the names are debatable. Everyone wants words to have the meaning which makes most sense in their personal context.
A programming language is a language that is “Turing complete” in the usual programming sense, I guess. Although that would exclude Dhall. The definition of “programming language” shouldn’t be part of the definition of “declarative”.
This is a very interesting question. I don’t know how to construe Wang tiles as a declarative language, but it might be worth finding a way to do this. It might shed some light on visual programming languages, especially 2D VPLs with no hierarchical structure. Here are some issues:
In computability theory, a “language” is a set of strings over some alphabet. (The definition of language is purely syntactic.) A string is an ordered sequence of symbols (from some alphabet). An alphabet is a finite set of symbols.
To give a mathematical meaning to “declarative language”, we need to consider languages which have been augmented with a meaning. My preferred technique for doing this is denotational semantics.
Wang tiles are a class of formal systems. A Wang tile system has something like an alphabet (a set of tiles), although the tiles aren’t arbitrary symbols, they have internal structure. The tiles are not arranged in strings, so the system doesn’t meet the definition of a language.
A denotational semantics is normally given by associating a denotation function with each production in a context free BNF grammar. I don’t see how to do this with Wang tiles, even though the rules for joining tiles do feel like syntax rules.
This definition is pleasing because it includes search as an essential primitive. Given some declared problem, there might exist a solution, but we must search for that solution.
JSON has no semantics; JSON text is trivially acceptable. (Whether text is JSON text is non-trivial, of course.) Neel isn’t talking about syntax.
Edit: Let me use more words; I’m not just trying to contradict you. For Neel, a regular expression doesn’t just denote a set of strings, but a partial function from strings to proofs of membership; for each member, there exists a proof which destructures the string into components and assigns each component to a subexpression. Similarly, a context-free grammar assigns a parse forest to each member, denoting the zero-or-more parse trees in the forest, and a parser asserts that there exists at least one tree in the forest.
So what about JSON? In your view, JSON is a declarative language for specifying trees using strings, and since it has a context-free grammar, I think that this is fair. But also, in my view, JSON is not a programming language and thus not eligible for consideration when it comes to programming paradigms; rather, JSON is a textual format for encoding simply-typed trees, and JSON is wholly syntactic.
I only have minor disagreements with what you say. I think that connecting the idea of search with the semantics of declarative DSLs is a fruitful insight. I don’t think it’s essential to all declarative languages, and anyway animatronic says you didn’t claim that.
I agree that JSON isn’t a programming language. I don’t agree that it is wholly syntactic, it’s just mostly syntactic.
You can write a denotational semantics for JSON: it would map JSON syntax onto idealized mathematical objects. JSON text is not trivially acceptable: the semantics of strings is non-trivial and is specified by the standard. An implementation which accepts all JSON syntax would conflict with the standard. Although json.org only specifies a syntax for JSON on the front page, it contains a link to ECMA-404, which specifies a semantic interpretation of the syntax. Here are some semantics from ECMA-404:
A JSON string denotes a string of Unicode code points. This means that unpaired surrogates, while possible in the syntax, are semantically illegal, because they don’t map to a code point. Also, it is stated that the following JSON strings have the same denotation: “\u002F”, “\u002f”, “/”, “/”.
When ECMA-404 was created, it standardized some semantic constraints on the syntax (which weren’t previously specified, just assumed by many people) and this made a better, more useful standard. So it’s useful to think about the semantics of a language such as JSON, good things can result.
As for whether JSON is eligible for consideration when it comes to programming paradigms: well, for me it is. One of the languages I designed and implemented started as JSON extended with function literals, function calls, and let expressions. It was a pure functional expression language with the data model being pure JSON. I was trying to learn something about programming paradigms, and about how simple a programming language could be and still be useful for real work. The paradigm I was exploring has no user defined types and no data abstraction mechanisms. Jsonette and Dhall are related languages, although they were created for different purposes than mine.
We can pick multiple denotational semantics for JSON, so it’s not clear why we should insist that JSON is non-syntactic. Denoting Unicode strings is not that tricky, and we can structure e.g. unpaired surrogates wholly as a parser issue. I can make three assignments of semantics:
JSON denotes a subset of plain old data in languages like Python, ECMAScript, or E
JSON non-trivially denotes expressions in SK combinator calculus, like ["s", "k", "k"] for SKK
JSON non-trivially denotes expressions in my current pet project Cammy; like ["pr", "t", "not"] for (pr t not)
Reduction of SK calculus is Turing-complete, but reduction of Cammy expressions is total.
I understand why you chose JSON as a building block. JSON was originally distilled from E, as a way to capture E expressions which denoted plain old data.
My (provocative) question would rather be: What are imperative languages?
In none of the so-called imperative languages you really do give concrete orders. You just declare the kind of result that you would like to be see at the end and the “interpreter” does it for you:
I would like to find in variable x the sum of y and z: x = y + z.
In a high-level language like Ruby the interpreter would subserviently do all the dirty work that is needed for this to happen. Making sure that all variable are compatible, finding the right kind of sum to apply, converting from int to float, dealing with overflow, changing to a Bignum if the result gets too big. I haven’t given any of these commands, I only expressed my desire for a result and the interpreter has provided me with a correct solution.
Actually, I have no idea if the interpreter did any of this. Maybe it had a lookup table. Or it run a backtracking search algorithm to find the right solution. Maybe it’s Prolog all the way down.
Why wouldn’t that fit pretty much any definition of declarative programming?
The same thing can also be said of C code or, even, of assembly code. In MIPS assembly
addiu $t0, $s3, 1
is a declaration of the fact that I want to associate the name $t0 to the incremented value of what is currently referred as $s3. There is no connection between this and what the hardware actually does. The hardware (or the emulator) is free to do whatever they want and to transform this code however they like (making use of the modern intricate web of renamed registers, out-of-order operations, microcoding…), as long as the result is correct.
In my view declarative and imperative are relative terms. A piece of code can be more declarative than another piece of code that produces the same output because it, for instance, focuses more on describing the intended result rather than spelling out all intermediate steps.
I’m working on the idea that the class of declarative languages and the class of imperative languages can be defined in terms of what you need to do in order to write a denotational semantics for the language.
In a denotational semantics, you define a denotation function that maps a program (an abstract parse tree) onto its denotation or meaning. My idea is that the form of these denotation objects indicates the class of the language.
Consider a simple calculator language with numerals, arithmetic operators (+, -, *, /) and parentheses, nothing else. Programs denote numbers. The denotational semantics for the calculator maps each syntactically valid expression onto either a number, or an error (to model division by zero). This direct mapping onto numbers (which are the domain of this DSL) indicates a declarative language.
In an imperative language, there is a global state that can be changed by assignment statements, function calls, etc. In the denotational semantics for an imperative language, the denotation function maps expressions and statements onto functions that take a state S (plus other arguments) and which also return the modified state. (This is what I meant by “state threading” in another comment.)
It’s possible for an imperative language to have a declarative subset. You could write a separate denotational semantics for this declarative subset. Programs written in this declarative subset would themselves be declarative.
An imperative language is one where the primary denotation is state transition functions.
A declarative language’s primary denotation is the semantic domain that the language was created for. (And to retain common usage, that semantic domain shouldn’t be state transitions)
To expand on your arithmetic example:
Imperative
[[_]] : Map String Int -> Map String Int
[[ x; y ]](s) = [[ y ]]([[ x ]](s))
[[ %r = int n ]](s) = Map.insert r n
[[ %r = add %x %y ]](s) = Map.insert r (Map.get x s + Map.get y s)
[[ %r = mul %x %y ]](s) = Map.insert r (Map.get x s * Map.get y s)
This program represents (22 + 33) * 11:
%0 = int 22;
%1 = int 33;
%2 = add %0 %1;
%3 = int 11;
%result = mul %2 %3
Declarative
[[_]] : Int
[[ int n ]] = n
[[ add x y ]] = [[ x ]] + [[ y ]]
[[ mul x y ]] = [[ x ]] * [[ y ]]
Wikipedia has a pretty good definition of “declarative language”. It goes something like this:
If you take this definition seriously, then a declarative language is not a programming language. A declarative language has no concept of control flow or evaluation order or sequential evaluation of language primitives. If you have to execute a program in your head, as an ordered sequence of steps, using a mental model of an abstract machine, in order to understand what it means, then the program is not declarative.
If a language is implemented on a computer, then the implementation will contain an abstract machine that executes a series of operations in some order. If the language contains features that expose the order of operations executed by the abstract machine, then the language is not declarative.
According to this definition, “declarative programming language” is a contradiction in terms. A language is either declarative, or it is a programming language, but not both. I think this conflict between being declarative and being a programming language is at the heart of the confusion over what the term “declarative programming language” could possibly mean.
Robert Harper has some good observations on the confusion inherent in the term “declarative programming language”:
Probably not many people in the programming language community would be happy with my definition of a declarative language.
My list of declarative languages would include:
In these examples,
The denotational semantics are simple, compositional and direct. State threading is not required to model state transitions in some underlying abstract machine.
The linked article includes Prolog. But Prolog is a programming language, and it isn’t declarative even by more liberal definitions of “declarative”, as Robert Harper points out: “Prolog has imperative features, such as assert and retract, that have imperative meaning”.
I think that the author of the linked article may be saying the same thing as I just said above using more formal and mathematical language. His criterion “has a semantics which relies on some existential quantifiers which it is not immediately obvious how to discharge” and “the semantics is not well moded” appears to mean the same thing as my “doesn’t have an order of evaluation”. I’m not certain, because he includes regular expressions with backreferences, and prolog with cuts, as declarative languages, even while noting that these features “expose the operational model”. Maybe the author’s definition of declarative is more like “doesn’t have a total order of evaluation”? Not sure.
I think you haven’t supplied your definition of a programming language. Is the untyped lambda calculus not a programming language? Or is it somehow not declarative?
Good point, so here’s another attempt, based on the “denotational semantics” post elsewhere in this page.
I’m using the numbers 0, 1 and 2 because the names are debatable. Everyone wants words to have the meaning which makes most sense in their personal context.
A programming language is a language that is “Turing complete” in the usual programming sense, I guess. Although that would exclude Dhall. The definition of “programming language” shouldn’t be part of the definition of “declarative”.
Are Wang tiles a declarative language?
This is a very interesting question. I don’t know how to construe Wang tiles as a declarative language, but it might be worth finding a way to do this. It might shed some light on visual programming languages, especially 2D VPLs with no hierarchical structure. Here are some issues:
This definition is pleasing because it includes search as an essential primitive. Given some declared problem, there might exist a solution, but we must search for that solution.
I consider JSON to be a declarative language, and there’s no search involved. See my other post in this thread.
JSON has no semantics; JSON text is trivially acceptable. (Whether text is JSON text is non-trivial, of course.) Neel isn’t talking about syntax.
Edit: Let me use more words; I’m not just trying to contradict you. For Neel, a regular expression doesn’t just denote a set of strings, but a partial function from strings to proofs of membership; for each member, there exists a proof which destructures the string into components and assigns each component to a subexpression. Similarly, a context-free grammar assigns a parse forest to each member, denoting the zero-or-more parse trees in the forest, and a parser asserts that there exists at least one tree in the forest.
So what about JSON? In your view, JSON is a declarative language for specifying trees using strings, and since it has a context-free grammar, I think that this is fair. But also, in my view, JSON is not a programming language and thus not eligible for consideration when it comes to programming paradigms; rather, JSON is a textual format for encoding simply-typed trees, and JSON is wholly syntactic.
I only have minor disagreements with what you say. I think that connecting the idea of search with the semantics of declarative DSLs is a fruitful insight. I don’t think it’s essential to all declarative languages, and anyway animatronic says you didn’t claim that.
I agree that JSON isn’t a programming language. I don’t agree that it is wholly syntactic, it’s just mostly syntactic. You can write a denotational semantics for JSON: it would map JSON syntax onto idealized mathematical objects. JSON text is not trivially acceptable: the semantics of strings is non-trivial and is specified by the standard. An implementation which accepts all JSON syntax would conflict with the standard. Although
json.orgonly specifies a syntax for JSON on the front page, it contains a link to ECMA-404, which specifies a semantic interpretation of the syntax. Here are some semantics from ECMA-404:When ECMA-404 was created, it standardized some semantic constraints on the syntax (which weren’t previously specified, just assumed by many people) and this made a better, more useful standard. So it’s useful to think about the semantics of a language such as JSON, good things can result.
As for whether JSON is eligible for consideration when it comes to programming paradigms: well, for me it is. One of the languages I designed and implemented started as JSON extended with function literals, function calls, and
letexpressions. It was a pure functional expression language with the data model being pure JSON. I was trying to learn something about programming paradigms, and about how simple a programming language could be and still be useful for real work. The paradigm I was exploring has no user defined types and no data abstraction mechanisms. Jsonette and Dhall are related languages, although they were created for different purposes than mine.We can pick multiple denotational semantics for JSON, so it’s not clear why we should insist that JSON is non-syntactic. Denoting Unicode strings is not that tricky, and we can structure e.g. unpaired surrogates wholly as a parser issue. I can make three assignments of semantics:
["s", "k", "k"]forSKK["pr", "t", "not"]for(pr t not)Reduction of SK calculus is Turing-complete, but reduction of Cammy expressions is total.
I understand why you chose JSON as a building block. JSON was originally distilled from E, as a way to capture E expressions which denoted plain old data.
a implies b doesn’t mean b implies a. Search can be a declarative way to implement a language.
My (provocative) question would rather be: What are imperative languages?
In none of the so-called imperative languages you really do give concrete orders. You just declare the kind of result that you would like to be see at the end and the “interpreter” does it for you:
In a high-level language like Ruby the interpreter would subserviently do all the dirty work that is needed for this to happen. Making sure that all variable are compatible, finding the right kind of sum to apply, converting from int to float, dealing with overflow, changing to a Bignum if the result gets too big. I haven’t given any of these commands, I only expressed my desire for a result and the interpreter has provided me with a correct solution.
Actually, I have no idea if the interpreter did any of this. Maybe it had a lookup table. Or it run a backtracking search algorithm to find the right solution. Maybe it’s Prolog all the way down.
Why wouldn’t that fit pretty much any definition of declarative programming?
The same thing can also be said of C code or, even, of assembly code. In MIPS assembly
is a declaration of the fact that I want to associate the name $t0 to the incremented value of what is currently referred as $s3. There is no connection between this and what the hardware actually does. The hardware (or the emulator) is free to do whatever they want and to transform this code however they like (making use of the modern intricate web of renamed registers, out-of-order operations, microcoding…), as long as the result is correct.
In my view declarative and imperative are relative terms. A piece of code can be more declarative than another piece of code that produces the same output because it, for instance, focuses more on describing the intended result rather than spelling out all intermediate steps.
I’m working on the idea that the class of declarative languages and the class of imperative languages can be defined in terms of what you need to do in order to write a denotational semantics for the language.
In a denotational semantics, you define a denotation function that maps a program (an abstract parse tree) onto its denotation or meaning. My idea is that the form of these denotation objects indicates the class of the language.
Consider a simple calculator language with numerals, arithmetic operators (+, -, *, /) and parentheses, nothing else. Programs denote numbers. The denotational semantics for the calculator maps each syntactically valid expression onto either a number, or an error (to model division by zero). This direct mapping onto numbers (which are the domain of this DSL) indicates a declarative language.
In an imperative language, there is a global state that can be changed by assignment statements, function calls, etc. In the denotational semantics for an imperative language, the denotation function maps expressions and statements onto functions that take a state S (plus other arguments) and which also return the modified state. (This is what I meant by “state threading” in another comment.)
It’s possible for an imperative language to have a declarative subset. You could write a separate denotational semantics for this declarative subset. Programs written in this declarative subset would themselves be declarative.
This was my conclusion after thinking about this thread: https://lobste.rs/s/aedphq/why_does_nobody_seem_know_what_imperative.
An imperative language is one where the primary denotation is state transition functions.
A declarative language’s primary denotation is the semantic domain that the language was created for. (And to retain common usage, that semantic domain shouldn’t be state transitions)
To expand on your arithmetic example:
ImperativeThis program represents
Declarative(22 + 33) * 11:This program also represents
(22 + 33) * 11: