* Declarative Programming Techniques
Describe what is to be done, without explaining how.
Definition: *Referential Transparency*: Any expression can be replaced
by its value without changing the semantics of the program. No
external state used.
--------------------------------------------------
* Iterative Programming
fun {Append_ X Y}
case X
of nil then Y
[] H|T then
case Y
of nil then X
else H|{Append_ T Y}
end
end
end
How do we convert this into an iterative program?
Accumulators.
When is iterative programming useful?
--------------------------------------------------------
* Grammar-driven Programming
(Gary T. Leavens)
---------------------------------------------------------
* Difference Lists
Is a way of representing a list as the difference of a pair of lists.
(Recall that a pair in Oz is a tuple that has 2 features. A tuple, in
turn, is a record where all feature labels are numbers.
e.g. of a pair: #(1:Key 2:Value) == Key#Value
)
Syntax
------
::= #
L1#L2 is the list of elements in L1 but not in L2.
L2 is always the tail of L1.
e.g. [1 2 3]#[2 3] is a difflist representation of [1].
[1 2 3]#[2] is not a valid difflist.
(1|2|X)#X is (1|2|nil) - why?
Observation:
Difflists of the form
(a|b|X)#X
can be appended to other lists in constant time:
e.g. To append (a|b|X)#X and (c|d|Y)#Y
bind X to (c|d|Y) and then collate the lists to get
(a|b|c|d|Y)#Y
---------------------------------------------------------
* Skipped - Performance : Time and Space Efficiency
---------------------------------------------------------
* Higher-Order Programming
Order of a procedure:
Basic Types like integers, strings etc are of order 0.
Order of a function = 1 + maximum order of its arguments.
e.g.
-------------------
fun {Sort Array GT}
...
end
fun {GT X Y}
X > Y
end
------------------
Here, GT compares two basic data instances. GT is of order 1 since X
and Y are of order 0. Sort is a second order function, since one of
its arguments, GT, is of order 1.
Higher-order programming involves passing procedures of /any/ order as
arguments, and ability to return them as values.
How is this different from function pointers in C?
------------------------------------------------------------------
** Procedural Abstraction
Making a statement into a procedure.
--------------
An interesting discussion: Why does C and Pascal not support full
procedural abstraction? What is missing?
C - no nested functions
Pascal - "packaging" disallowed.
Consequence of stack deallocation of local variables.
------------
-------------------------------------------------------------------
** Genericity
Making a procedure an argument.
-------------------------------------------------------------------
*** Abstraction For iteration
--------------
fun {For Low High Step Proc}
fun {LoopUp I}
if I < High
then
{Proc I}
{LoopUp I+1}
end
end
in
if Step > 0 then {LoopUp Low} end
end
--------------
is an abstraction of a for loop.
e.g.
--------------
{For 1 10 1 proc {$ X} {Browse X*X} end}
--------------
would display a list of the first 10 squares of numbers in the
browser.
*** Abstraction for lists
*** Abstraction for trees
What is different between a for loop in an imperative language and in
a declarative language?
- Each iteration creates a new variable.
- No destructive assignment to the loop variable
- Can be concurrently executed!
--------------------------------------------------------------------
** Instantiation
A cool higher order programming technique to ``return'' functions. Can
be used to implement ``factory'' patterns.
For example, suppose we have two XML reading libraries - one fast, but
requiring a lot of memory, the other slow, but memory-efficient. We
can decide which to use as a file manipulation library based on the
file size.
----Template Pseudo Code----------
fun {Walker F}
if {Size F} > 10^8 % > approx 100 MB
then
fun {SAXWalker}
...
end
else
fun {DOMWalker}
...
end
end
end
------------------------------------
*** Currying
An important concept in this regard : *Currying*. Named in honour of
Haskell B. Curry, who also discovered Y-combinator. [Curry had
attributed the discovery of Currying to Schonfinkel.]
What currying is:
Simulating multi-argument functions through a cascade of simple
argument functions.
----------- ---------------------
fun {Add X Y} fun {Add X}
X + Y vs. fun {AddX Y}
end X+Y
----------- end
end
---------------------
The left hand side is a function that takes two arguments and returns
their sum. The right side is a function that takes one argument X, and
returns a function. The returned function has X ``hardwired'' into its
code. It takes one parameter, Y, and returns X + Y.
The left function can be called as
{Browse {Add 2 3}}
The right function can be called as
local P in
P = {Add 2}
{Browse {P 3}}
end
This should remind us of
(l x y. xy) == (l x. (l y. xy))
in the untyped lambda calculus.
(You can also go in the reverse direction - given a curried form, you
can formulate an equivalent procedure which operates on multiple
arguments. This is sometimes called ``Uncurrying''.)
----------------------------------------------------------------------
** Embedding
Functions can be embedded inside data structures. Supports partial
construction of data.
----------------------------------------------------------------------
* Components