Science Loves Declarative Style [1]
… so why are you still coding in imperative style?
It is the first chapter of Science Loves Declarative Style, and you can navigate to the next chapter clicking here.
Imperative programming has been the most popular paradigm for a century.
Most of the technological breakthroughs are achieved using imperative programming languages such as Java, C/C++, JavaScript, Go.
We cannot really imagine how to program a simple for loop program without a for loop.
Recursion is — generally speaking — less intuitive and human-understandable than iteration.
Perhaps that’s why declarative programming is nowadays an uncommon paradigm that only a few of us know.
It is not difficult, but unintuitive, and we are not programmed to program recursively. In case you don’t know those programming paradigms:
Declarative programming is known as a superset of functional programming and logical programming, but it is sometimes interchangeably referred as functional programming due to its high popularity.
Logical programming is built on relations and predicates, and the variable assignment is achieved under unifications and resolutions ( = a depth-first search algorithm for finding any solution which suits well to the condition).
We will see more on functional programming in the next sections.
Key Features of Functional Programming
In general, Functional Programming has the following key features:
First-class functions: Everything is a function.
- Variables and constants are also functions which don’t take any arguments.
- So a function results always to a function when called.
- With this in mind, a function can be also partial — intermediate states of a function are also functions.
- For example: “=” with 2 arguments, checks whether both numbers are equal.
- “=5” with one argument, checks whether a number is equal to 5.
- “5=5” is a variable ( = a function with no argument), which results to true.
No modification: Functions are immutable.
- Variables and data structures are constant, because they are functions.
- If a variable X is assigned 5, it cannot be changed to 6.
- Neither the list Y = [3, 7, 5] nor its elements can be modified, since lists are also recursive data structures.
No loop: No iteration, just recursion.
- Since there are also no variable modifications, it is not allowed to define a counter.
- Instead of for-loops and while-loops, iterating over a list or other recursive data structures is the way to do.
Lazy Evaluation: No CPU overload.
- Functional programming takes advantage of the power of recursion.
- Even if the recursion doesn’t end, the number of calculated results depends on how many results are taken.
- Let’s assume we calculate the first n numbers of a set with an open interval such as ones, zeros or natural numbers {0, 1, …}.
- If we ‘take’ the first n = 30.000 numbers, more results will be cached compared to n = 30.
Higher-order functions: We will see more details in the next sections.
Key Mathematical Concepts Related to Relations
Did you know that functional programming shares too many similarities with math language, logic and SQL?
The reason behind the similarity is that all of them are built on relations, but we will get later into it.
This article is strongly linked to my other article: Logic is Built On Relations.
I wrote about the fact that relational databases, programs in object oriented style and logical structures have something in common, along with a gentle introduction to Boolean Logic and First-Order Logic.
If you are not a math person, check this out: Sets & Tuples, which makes a brief introduction to overview of features, similarities and operations on sets and tuples.
Relations & Functions
Universal Set: The set of all values.
- Since we make a closed world assumption ( = all we know is all it exists in the universe), universal set contains all ‘existing’ elements and nothing more.
- It is generally used to show the all possible combinations, for example when we define a relation.
- Keyword: dictionary, capacity of information.
Relation: A subset of universal set.
- Assuming A is the universal set, a n-ary relation R is a subset of A × … × A = A^n, so it is basically a set of tuples.
- Notation: R : (A_1, …, A_n)
- Each tuple in set holds a unique information and there are a set of such information.
- It holds the information that we make use of in our closed world assumption.
- The information is binary, since we can only check, whether a relation contains an element.
- Keyword: actual information, attribute.
Function: A special type of relation.
- Functions are relations which basically map each domain value to a co-domain value (domain set is the set of all inputs, co-domain is the set of all outputs).
- Currying f: (A, B) to f: A → B makes a function out of relation. Uncurrying f: A → B to f: (A, B) makes a relation out of function.
- In general, if a relation f : (A_1, …, A_n, B_1, …, B_m) meets the conditions of being a function, it can be curried as f : (A_1, …, A_n) → (B_1, …, B_m)
- (A_1, …, A_n) is the domain and (B_1, …, B_m) the codomain.
- Notice that domain and co-domain can be a cross product of multiple sets.
- If (a_1, …, a_n, b_1, …, b_m) ∈ f, then f((a_1, …, a_n)) = (b_1, …, b_m).
Currying and Partial Functions
Mostly in functional programming and math universe, the functions are curried, which is why partial functions are allowed.
Let’s assume that f is an uncurried function f : (A_1, …, A_n).
It doesn’t have a intermediate state. It returns an output as a constant function, if and only if every value (a_1, …, a_n) is successfully passed as an argument.
Let’s assume i ∈ {0, …, n-1} is a number.
f : (A_1, …, A_i) → A_{i+1} → … → A_n is a function which returns a function if every value (a_1, …, a_i) is successfully passed.
If i = 0, every A_i is joined by → and the tuple on the left side is empty.
Now the function looks like this: f : () → A_{1} → … → A_{n} or simply f : A_1 → … → A_n.
It is a function which always returns:
- a partial function with the missing arguments
- or an output value if all arguments are passed
In functional programming languages such as Haskell, the function looks like f : A_1 → … → A_n, because of the first rule: everything is a function.
Functional Programming: Functionals
Now that we have a grasp of basic concepts, it’s time to refresh what we know about functional programming:
Map: A function f : A → B which mappes each value a_i to f(a_i) = b_i.
- If we would allow B to be a multi-set or bag where duplicates are allowed, B would still have the equal number of elements.
- However mathematically, we will simply assume B is a set too, so if there are at least two values a_i ≠ a_j with f(a_i) = f(a_j), the number of elements on both sides will be different: |A| > |B|.
- In OCL, it is referred as →collect(x : Real | f(x)) where you need to define the mapping function f.
- It is also very similar to π (projection operator in Relational Algebra) and SELECT (projection keyword in SQL).
Filter: A relation R ⊆ (A_1, …, A_m) which contains a subset of all possible values.
- It is possible to identify the values (a_1, …, a_m) contained in R using (a_1, …, a_m) ∈ R.
- Alternatively, we can define a characteristics function p: (A_1, …, A_m) → {0, 1} with p((a_1, …, a_m)) = 1 if (a_1, …, a_m) ∈ R and else 0.
- With this function in mind, we can define a filter function f: (A_1, …, A_m) → R where f((a_1, …, a_m)) = (a_1, …, a_m) if p((a_1, …, a_m)) = 1 and else ⊥ (undefined).
- In OCL, it is referred as →select(x : Real | p(x)) where you need to define the predicate function p.
- It is also very similar to σ (selection operator in Relational Algebra) and WHERE (selection keyword in SQL)
Reduce: A function f : (A_1, …, A_m) → B which reduces the input to a summary value.
- It can be a sum or multiply function, cosine similarity function, mean — mode — median function, where each b = f((a_1, …, a_m)) is a scalar value.
- It is the most representative function among those 3 functions, because reducing function can be a structure-holding function.
- For example: it can be a pass function or a mapping function where b is defined as (b_1, …, b_m).
- In OCL, it is referred as →iterate(x : Real, acc : Real = <acc>| f(x, acc)) where you need to define the function f and accumulator value acc.
- Relational Algebra: Such operations can be done using Ɣ, groupby-aggregate operator. It takes two kinds of input: columns to be grouped by and columns to be summarized.
- SQL: Likewise GROUP BY, groupby-aggregate-keyword.
[BONUS] Zip: A function f which compresses the sets A, B with n elements to a set of pairs.
- Definition: f({a_i | 1 ≤ i ≤ n}, {b_i | 1 ≤ i ≤ n}) = {(a_i, b_i) | 1 ≤ i ≤ n}, n = |A| = |B|.
- It can be rewritten using reduce function which uses a structure-holding function internally.
- Unzip function is the inverse function of zip, which maps both elements in the pair a_i, b_i to their original set.
Next Chapter
It is the first chapter of Science Loves Declarative Style, and you can navigate to the next chapter clicking here.
