declarative programming

Declarative Programming is a style of programming that concentrates on what to do, rather than how to do it. Contrast with imperative programming.

See Also

Demand-driven computation
Resource Usage Tracker ,by DKF
whose XML generation is an example of declarative programming.

Description

Some examples of declarative programming languages:

  • Functional programming languages, like Haskell, ML, etc. (Should this be refined to say pure functional programming languages?) (NEM: Not unless we want to remove Prolog too...)
  • Logic programming languages, like Prolog.
  • Dataflow programming languages, like Lucid.
  • Various rule-based languages, such as CLIPS are primarily declarative, but are often used in a stateful manner.
  • Various procedural markup languages, such as runoff and compose (Multics) and the Unix *roff family (troff, nroff, etc.), are imperative.
  • Various descriptive markup languages, such as HTML and SGML (from which XML was derived) are declarative (ish -- again, this is often not the case in practice).

XSLT could indeed be called an XML-based, declarative and functional programming language.

  • The most ubiquitous and most forgotten declarative programming language is that of the make utility.

To illustrate what declarative programming looks like in SML, here's a simple function that counts the number of items in a list:

fun llength []      = 0
  | llength _::tail = 1 + (llength tail)

The first line says that llength of an empty list (which is what [] represents) returns zero, and the second line says that llength of a non-empty list (:: is the infix list constructor) returns one more than the llength of the tail of the list. Clear and easy.

In Tcl you can have that as well (though it's the most impractical thing to do):

proc length list {
    expr {
        $list eq []? 0: 
        1 + [length [lrange $list 1 end]]
    }
}

SS Maybe the following is a bit more familar Tcl version:

proc rest list {lrange $list 1 end}
proc listlen list {
    if {$list eq {}} {
        expr 0
    } else {
        expr 1 + [listlen [rest $list]]
    }
}

it's worth to note that the program is exactly as complex as the SML version, but in SML there is enough syntax sugar for lists that it looks much simpler.

SYSTems A Tcl version that more match the SML idioms will tool like this

proc tail {lst} {
    lrange $lst 1 end 
}
 
# It would be kinda silly but maybe Tcl should add standard head and tail procedures
# proc head {lst} {lindex $lst 0} 
 
proc lslen {lst} {
    switch $lst {
        "" {expr 0}
        default { expr 1 + [lslen [tail $lst]]}
    }
}

# or something tail recursive

proc listlen {lst {count 0}} {
    switch $lst {
        "" {expr $count}
        default {listlen [tail $lst] [expr {$count+1}]}
    }
}

SYStems I am a bit familiar (and in love) with ocaml, sml is another language from the same familly. ocaml have a feature called pattern matching. The above sml syntax won't work in ocaml thought. But you can have the exact same thing with slightly different syntax

let rec length = function [] -> 0 | head::tail -> 1 + (lenth tail) ;;
(* 
  The above is possible for many reasons, ocaml does type inference, this function will only match
  possible list value, of which [] and head::tail are two, length will produce and error if it receives
  anything but a list
*)

But again, why would we call this declarative programming. You are just using builting pattern matching and type inference features of the language.

NEM: Because you can reason about it statically: nothing in the description depends upon an effect which occurs at runtime.


SYStems: I really don't know why no one ranted about this before, but when I tell tcl to compute

puts stdout "Hello World!" 

I dont care how it does it, this is what How to Think Like A Computer Scientist books call leap of faith, and this is why, I don't know why people speak as if only declaritive programming hold any particularity in this!

The way I see it, declarative language are almost always domain specific Sql and XSLT, being domain specific, they can also be viewed as higher level programming languages, i.e. they have highly crafter syntax/construct to support their domain specific operation, which make em easier to use when performing these operation, but highly crippled outside their domain, if at all usuable.

A nice thing about Tcls' idiom every script line is a command, is that you can have highly crafted syntax without losing the general purposiveness of the language! All Tcl control structure facilities are regular commands.

NEM: Sure, you always rely on a computer to interpret the instructions you give it, and declarative languages are also giving the computer instructions. For instance, to illustrate, here is a declarative program which describes a book:

book {
  title "Godel, Escher, Bach: an eternal golden braid"
  author "Douglas Hofstadter"
  isbn "0-14-028920-8"
  publisher "Penguin"
  year 1979
}

You can view that fragment of my new Book programming language in one of two ways:

  • As a description of a book -- the declarative view;
  • As a set of instructions that, when executed, build up a graphical user interface to edit the book's details -- an imperative view.

To illustrate the second view, here is a little interpreter for my Book language, which does exactly that:

proc book details {
    toplevel .book
    foreach {name value} $details {
        grid [label .book.$name -text [string totitle $name]: -anchor e]\
            [entry .book.v_$name -textvariable ::book($name)] -sticky ew
        set ::book($name) $value
    }
    grid [button .book.ok -text "OK" -width 8 \
        -command { parray ::book; destroy .book }] \
        [button .book.can -text "Cancel" -width 8 \
        -command { destroy .book }] -sticky e
    grid columnconfigure .book 1 -weight 1
}

When you run it, you get a window with fields for editing data about a book. Note that my little book interpreter proc is very imperative in style -- it's all about actions that have effects. It's certainly useful to be able to program imperatively, but a good style of programming (IMO), is to move as much towards writing a little descriptive language that describes your problem domain, and then writing code to interpret that (declarative) description. This is really saying nothing much more than that separating interface and implementation is a good thing, and that Tcl has some pretty powerful facilities for making abstract interfaces that concisely describe your problem.


A special case of declarative programming was described on NAND, where a function is defined by its results for all possible inputs (truth table):

proc booleanFunction {table a b} {lindex $table [expr {!!$a+!!$a+!!$b}]}
proc declareBooleanFunction {name |-> args} {interp alias {} $name {} booleanFunction $args}
declareBooleanFunction and  |-> 0 0 0 1
declareBooleanFunction or   |-> 0 1 1 1
declareBooleanFunction nand |-> 1 1 1 0
declareBooleanFunction nor  |-> 1 0 0 0
declareBooleanFunction xor  |-> 0 1 1 0