An evolving glossary of terms used in functional programming, mathematics and computing in general.
An understanding of many mathematical terms is fundamental to get an understanding of many of the principles embodied in functional programming.
A few other glossaries that may come in handy:-
Reactive Manifesto
Programming in Scala
In alphabetical order.
Abstract-Syntax Trees
Syntax
AST - wiki
Abstract Syntax Trees are a way of representing the syntax of something as a tree structure. Their purpose is that they capture the relationships between syntactical elements in a way that is easier to work with programmatically.
A simple syntax example is an expression with a binary operator with two operands a + b. If code like this were stored just as a sequence of tokens (a whitespace + whitespace b) then for a compiler (for example) to understand them, it would have to read all 5 of these characters, and (importantly) read them in sequence. This is a simple example, but imagine a complex block of code being stored as a long sequence of tokens that must all be read in sequence for that block to be understood - this would get very cumbersome.
If however, we store the syntax as a tree structure, with a binary operator node with a value of +, which has two child nodes a and b
+
/ \
a bWe are now storing the syntax of the expression as a tree, which is:-
- abstract - because it is no longer a concrete representation of the syntax (we have lost the whitespace for example).
Abstract syntax trees are data structures widely used in compilers to represent the structure of program code. An AST is usually the result of the syntax analysis phase of a compiler. It often serves as an intermediate representation of the program through several stages of compilation.
The stages of compilation are (broadly):-
-
Lexical analysis (aka lexing or tokenization) - breaks the source code text into a sequence of small pieces (lexical tokens). Common token categories include: identifiers, keywords, separators, operators, literals, comments ...
-
Syntax analysis (aka _parsing) - involves parsing the token sequence to identify the syntactic structure of the program. -> Concrete Syntax tree -> Abstract Syntax tree -> Semantic checks -> ...).
This represents how far a number is from zero. eg. -5 is 5 from zero, so, in practice, it means to remove any negative sign in front of a number.
The arity of a function (or operation) is the number of arguments or operands that the function takes. In programming, there is a syntactial distinction between operators and functions since operators will usually have arity 0 (nullary), 1 (unary), 2 (binary), 3 (ternary), whereas functions can usually take more arguments - Scala allows up to 22 at the time of writing.
Unary (1 operand) operators include increment, decrement, logical Not.
Binary operators (2 operands) are the most prevalent in programming and include multiplication, addition, division.
Ternary operators (3 operands) include the conditional operator ?:.
n-ary - a function with n arguments. They can always be considered as a function of a single argument however ie. taking some composite type like tuple, or in languages that have higher-order functions, by currying.
TODO - expand in relation to complexity/performance. How do we use this term in the context of Big O.
https://www.mathsisfun.com/algebra/asymptote.html
https://www.mathsisfun.com/algebra/rational-expression.html
...
From wikipedia:-
An assignment statement sets and/or re-sets the value stored in the storage location(s) denoted by a variable name; in other words, it copies a value into the variable. In most imperative programming languages, the assignment statement (or expression) is a fundamental construct.
Assignments typically allow a variable to hold different values at different times during its life-span and scope. Purely functional languages do not allow assignment in order to enforce referential transparency, i.e. functions that do not depend on the state of some variable(s), but produce the same results for a given set of parametric inputs at any point in time.
Any assignment that changes an existing value (e.g. x := x + 1) is disallowed in purely functional languages. In functional programming, assignment is discouraged in favor of single assignment, also called initialization. Single assignment is an example of name binding and differs from assignment in general in that it can only be done once, usually when the variable is created; no subsequent reassignment is allowed.
The evaluation of an expression does not have a side effect if it does not change an observable state of the system, and produces same values for the same inputs. Imperative assignment can introduce side effects while destroying and making the old value unavailable while substituting it with a new one, and is referred to as destructive assignment for that reason in LISP and functional programming, similar to destructive updating.
Single assignment is the only form of assignment available in purely functional languages, such as Haskell. Purely functional languages can provide an opportunity for computation to be performed in parallel, avoiding the von Neumann bottleneck of sequential one step at time execution, since values are independent of each other.
The associative law states that it does not matter in what order we evaluate mutliple operations - or rather how we group (associate) operations - the result will always be the same.
Multiplication and addition are associative whereas division and subtraction are not.
(a + b) + c = a + (b + c)
(3 + 4) + 5 = 3 + (4 + 5)
(a x b) x c = a x (b x c)
(3 x 4) x 5 = 3 x (4 x 5)
(a - b) - c ≠ a - (b - c)
(3 - 4) - 5 ≠ 3 - (4 - 5)
(a / b) / c ≠ a / (b / c)
(3 / 4) / 5 ≠ 3 / (4 / 5)Associativity (also called fixity) allows a calculation containing multiple operations to be reorganized in any order. One way in which this is useful is that it allows us to break the calculation up and run each part in parallel - map/reduce.
The definition of atomic (in computing) is that an operation (or sequence of operations) appears to the rest of the system as occuring instantaneously eg. a read-write-read sequence of operations (increment/decrement operators in imperative languages do this) carried out in 1 thread cannot be interrupted part-way through by other threads.
In concurrent systems, different processes and threads can access the same objects in memory at the same time. This can cause problems eg. two threads both need to increment an integer 1 - both threads read the same value 1, one thread updates it, then the other thread updates it, but because they both read and updated the same value 1 the final result of both increments is 2 whereas it should have been 3 - the system's state is now incorrect. By ensuring that operations are atomic, systems can ensure that state is managed how it is expected to be ie. threads cannot read-increment-write the value (one example) until other such operations have completed.
Atomicity is often enforced by mutual exclusion, whether at the hardware level building on a cache coherency protocol, or the software level using semaphores or locks. Thus, an atomic operation does not necessarily actually occur instantaneously. The benefit comes from the appearance: the system behaves as if each operation occurred instantly, separated by pauses. This makes the system consistent.
All single operations (read or write) are atomic - the only exceptions (I believe) are where you have some operation on a 64 bit structure on a 32 bit system eg. a Long in Java is 64 bits so on a 32 bit machine it needs to be read and written in 2 operations - each of 32 bits.
Implementations of atomic operations in computing languages generally delegate to low-level native instructions of the underlying host eg. compare-and-swap
In order to ensure that the result of a sequence operations are visible at once to the rest of the system, an implicit requirement of an atomic operation is that a sequence of operations either all occur successfully or none at all in order that the state of the system is inconsistent.
From Latin bīnārius (meaning “consisting of two”), binary is the simplest numbering system, as digits are limited to only two possible symbols, (0 & 1).
A binary digit is given a special name - a bit - which is a portmanteau (combination of multiple words and their sounds to form a new word) of binary digit
One bit can represent two values - 0 and 1. Quantities greater than one, are written using two or more bits.
1 - represents the decimal 1. 10 - equivalent to the decimal 2. 100 - equivalent to the decimal 4.
Like decimal the bits have different weightings, but in binary the weightings increase by a factor of 2 (rather than a factor of 10), moving from right to left.
In mathematics (and computing), this term is sometimes called a bivariate function (function of two variables) and is simply a function that takes two inputs.
It is simply a function which maps between the cartesian product of two sets X, Y to a set Z.
X x Y to Z
f: X x Y -> ZIt may be used interchangeably with the term binary operation however.
A binary operation is a calculation that combines two elements (operands) of a set to produce another element of the same set. The arity is two, and the two domains (from which the operands are drawn) and one codomain (in which the result exists) are all subsets of the same set.
The term is commonly used in programming for any binary function, which is simply a function that takes two inputs. In mathematics, it is defined as ƒ: X x Y -> Z. Where X x Y is the Cartesian product of X and Y
Slightly more clearly, we can say that a binary operation f on a set S is a map which sends elements of the Cartesian product S × S to S.
f: S X S -> SBecause the result of performing the operation on a pair of elements of S is again an element of S, the operation is called a closed binary operation on S (or sometimes expressed as having the property of closure). If f is not a function, but is instead a partial function, it is called a partial binary operation. For instance, division of real numbers is a partial binary operation, because one can't divide by zero: a/0 is not defined for any real a.
Sometimes, especially in computer science, the term is used for any binary function.
Binary operations are the keystone of algebraic structures studied in abstract algebra: they are essential in the definitions of groups, monoids, semigroups, rings, and more. Most generally, a magma is a set together with some binary operation defined on it.
A block refers to one or more declarations and statements grouped togethor. As well as being used to control the scope of variables, procedures and functions declared in the block, they also serve the purpose of being able to treat a group of statements as if they were one statement.
At a high level, blocking essentially means that some process will wait until some resource is returned to it before it will do anything else ie. it is blocked from progressing until it gets what it needs. By contrast, non-blocking means that the process does not wait around.
There are several contexts within which you may here it's use, but usually it is either:- in the context of multi-threading, or some API that accesses resources that don't necessarily require CPU core attention ie. web service calls or I/O.
Blocking will cause a process to give up it's turn on the CPU core - by going into a blocked state, which will cause it to be context switched off of a core. The OS will awaken the process by delivering the resource (I/O data or whatever) and it will go into a state of Waiting and then Running when it is allocated some CPU core time.
It can be said that applications that implement blocking I/O, for example, are better able to cooperate on multitasking systems.
In computing, an application executes in a process (or task). Within each process, an application will usually have multiple threads of execution (a thread being the smallest unit of instructions that can be managed independently by a scheduler which switches between process, and their threads, so that each application running concurrently can have a slice of CPU core processing time to progress their work).
For the purposes of discussing what blocking we will use the term process to refer to both processes and threads.
A process can only ever be in one of several possible states. These states are just useful abstractions for us to understand process states ie. they may not be exactly recognised as such by different OS kernels.
Running - A process is in running mode when it has been scheduled for execution on a CPU core.
Ready / Waiting - A ready (or waiting) process is loaded into main memory and is waiting to be context switched onto a CPU core for execution.
Blocked - A process changes to blocked state when it cannot progress without external input ie. it is waiting on data being returned from an I/O request or user input. The process must move to a ready/waiting state before it can complete it's execution on a CPU core.
Blocking (ie. putting a process into a blocked state) is part of the strategy for managing a multitasking environment ie. most modern OSs. Since a CPU core can only execute one thread at a time, if there are more threads than there are cores available then some threads need to be kept in a waiting state until there is a core available for them to execute on. In addition to this, many other shared resources (in addition to CPU) on a system (disk, network etc) are limited in how many tasks can access them at any one time. Furthermore, some resources (memory addresses, files, global application state) should only be accessed by a single process at any one time otherwise we may get undesirable results due to interleaving concurrent processes (corrupt data etc). Therefore, threads that are waiting on a resource to be free will be put into a blocked state since they are not ready to run until the resource becomes available to them.
OSs employ techniques such as mutual exclusion to implement blocking in order to prevent concurrent access to protected resources such as critical sections of code (eg. mutable global application state).
It is most commonly used in the context of APIs that access some resources that do not generally require any CPU time eg. I/O. A blocking read from a socket, a web service call for example, is where the thread that initiated the read waits until the socket has something to return (or perhaps times out). A non-blocking read is where the thread does not wait until the socket returns data.
We say that HTTP is a blocking protocol because the HTTP server blocks the client from doing anything until it has received a response to it's request (or the connection times out).
In contrast to blocking, a non-blocking process does not wait around for the resource it has requested. There are two approaches:-
1.) "Get me this data, I'm going to go do something else. Interrupt me when the data is ready."
2.) "Get me this data, I'm going to go do something else. I'll ask you later if you have it yet."
The term generally used to describe the situation in which a process frequently polls to determine if it has access to a synchronized (protected) resource and it's frequent polling robs processing time from other processes.
This is an operation that returns a set (also known as product set or simply product) from multiple sets.
So, for sets A and B, the product A x B is the set of all ordered pairs (a, b).
A deck of 52 cards provides a nice example.
The standard playing card ranks {A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2} form a 13-element set. The card suits {♠, ♥, ♦, ♣} form a four-element set. The Cartesian product of these sets returns a 52-element set consisting of 52 ordered pairs, which correspond to all 52 possible playing cards.
Ranks × Suits returns a set containing 52 elements of the form:-
{(A, ♠), (A, ♥), (A, ♦), (A, ♣), (K, ♠), ..., (3, ♣), (2, ♠), (2, ♥), (2, ♦), (2, ♣)}.
Suits × Ranks returns a set containing 52 elements of the form:-
{(♠, A), (♠, K), (♠, Q), (♠, J), (♠, 10), ..., (♣, 6), (♣, 5), (♣, 4), (♣, 3), (♣, 2)}.
An algebraic structure that comprises objects that are linked by arrows. It is a very general concept in that the objects and arrows may be abstract entities of any kind ie. the arrow does not necessarily represent a mapping from one object to another.
It has two basic properties:-
-
The ability to compose the arrows associatively - ie. whatever the arrow represents, we should be able to compose them associatively eg. if the addition operation represents the arrow in a category whose objects represent the set of integers, then this is an example of this property since we know we can compose the addition operation associatively on those objects. This demonstrates that monoids can be thought of as a special sort of category.
-
The existence of an identity arrow for each object - ie. an arrow which returns the object itself.
An example is the category of sets, whose objects are sets and whose arrows are functions.
A set has closure under an operation if execution of that operation on members of the set always produces a member of the same set. We also say that the set is closed under the operation.
For example, the set of positive integers are closed under addition (+), but not under subtraction (-) because 1-2 (for example) is not a positive integer even though both 1 and 2 are positive integers.
A set is said to be closed under a collection of operations if it is closed under each of the operations individually.
More simply, we can say that if an operation on two values from the same set (eg. two positive integers) gives you back another value from the same set ie. another positive integer, then the set is closed under that operation. Mathematicians call this the closure requirement (of an operation).
In maths, a coefficient is a multiplicative factor in some term. It is usually a number but can be an expression.
In the following:-
7x - 3xy7 and -3 are coefficients.
In this example:-
ax - bxyThe a and b are considered parameters and x and y are variables.
Also, see binomial coefficient.
Combinators are programming constructs that allow you to, in effect, join (combine) different pieces of logic togethor to form larger constructs.
SEE this
For example,
// TODOA common application of combinators is in parsing. As a combinator provides a way to combine two functions to produce another, so a parser combinator combines two parsers to form another larger parser.
Function composition is about chaining functions, eg. Scala's compose and andThen functions combine other functions and then apply them in sequence.
// `compose` combines two functions to form another which applies f() to the result of applying g()
f compose g = f(g())
// `andthen` combines two functions to form another which applies g() to the result of applying f()
f andThen g = g(f())Combinators are a different and larger concept than composition. Composition operators are one example of a combinator.
As the following REPL session for compose demonstrates, the composition functions care about the terms they operate on ie. the type of the functions they combine. Since f and g both return an Int they can be composed because the type returned by f is a valid argument type for g, and vice versa. However, f and h cannot be composed because h returns a String which is not a valid argument for f, and vice versa.
scala> def f(x: Int) = x; def g(x: Int) = x; def h(s: String) = s
f: (x: Int)Int
g: (x: Int)Int
h: (s: String)String
scala> f _ compose g _
res10: Int => Int = scala.Function1$$Lambda$1301/1820750521@6fbfd28b
scala> f _ compose h _
<console>:15: error: type mismatch;
found : String
required: Int
f _ compose h _
^The relevance of the above is that, unlike composition functions, combinators, in general, act upon their terms (the functions passed to them) but they are generalized to not care what the type of the terms are. In other words, whereas composition functions can only be used on particular combinations of terms (ie. functions of a similar type), combinators are more powerful since they can deal with whatever terms are passed to them so are at a higher level of abstraction.
For combinators to be useful, you have to appreciate when fully generalized functions are worth creating. Parsers are a good, and therefore common, example, because they generally have to deal with a large number of possible inputs, therefore the ability to generalize the handling of their inputs comes in very handy.
Combinatorics is a branch of maths which is (in a general sense) concerned with how we go about counting how many of something exists. Examples include:-
- counting how many structures of a given kind and size exist (enumerative combinatorics)
- deciding when certain criteria can be met and constructing and analyzing objects meeting the criteria (combinatorial design)
- finding the largets, smallest, or optimal objects (extremal combinatorics)
- applying algebraic techniques to combinatorial problems (algebraic combinatorics)
There are many sub-fields of combinatorics.
Combinatorics is used frequently in computer science to obtain formulas and estimates in the analysis of algorithms.
Catalan numbers are a sequence of natural numbers that occur in various counting problems, commonly involving recursively-defined objects. They provide the solution for many counting problems in combinatorics and are named after a Belgian mathematician Eugene Catalan.
Combinatory logic was originally used in mathematics as a notation that eliminates the need for quantified variables. It is used in computer science as a theoretical model of computation and also as a basis for the design of functional programming languages. It is based on combinators. A combinator is a higher-order function that uses only function application and earlier defined combinators to define a result from its arguments.
Despite its simplicity, combinatory logic captures many essential features of computation.
Combinatory logic can be viewed as a variant of the lambda calculus, in which lambda expressions (representing functional abstraction) are replaced by a limited set of combinators, primitive functions from which bound variables are absent. It is easy to transform lambda expressions into combinator expressions, and combinator reduction is much simpler than lambda reduction. Hence combinatory logic has been used to model some non-strict functional programming languages and hardware.
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it.
Multiplication and addition are commutative whereas division and subtraction are not (we say the latter are noncommutative operations).
a + b = b + a
3 + 4 = 4 + 3
a x b = b x a
3 x 4 = 4 x 3
a - b ≠ b - a
3 − 4 ≠ 4 − 3
a / b ≠ b / a
3 / 4 ≠ 4 / 3In logic and mathematics, AND is the truth-functional operator of logical conjunction. The AND of a set of operands (conjuncts) is true if, and only if, all of its operands are true.
"A and B" is true only if A is true and B is true.
An operand of a conjunction is a conjunct.
The situation in which multiple prcoesses are waiting for a shared resource which is being held by some other process. The processes just keep waiting and execute no further.
From the Latin decem (meaning "ten"), the Decimal numbering system is the most familiar to humans. We say that a number is made up of digits, where each single digit is represented by one of ten possible symbols. ( 0, 1, 2, 3, 4, 5, 6, 7, 8 & 9 ).
Quantities greater than nine are written using two or more digits. e.g. 10, 11, 1200 ...
The weightings of each position in a decimal number, increase by a factor of 10, as we move from right to left.
In logic and mathematics, OR is the truth-functional operator of (inclusive) disjunction, also known as alternation. The OR of a set of operands (disjuncts) is true if and only if one or more of its operands is true.
"A or B" is true if A is true, or if B is true, or if both A and B are true.
An operand of a disjunction is called a disjunct.
We say that a function f relates values from a domain X to a codomain Y.
f: X -> YIn set theory, the domain of a function is the set of input (or argument) values for which the function is defined.
The set of output values is usually called the range, or image, of the function. In general, the range is usually smaller (a subset) of the codomain. If the range is the whole codomain then we say that f is a surjective function.
Also, see function.
A positive infinitesimal quantity, particularly used in calculus to denote an arbitrary small positive quantity.
existentials as they are sometimes called, are a way of squashing a group of types into one, single type.
An operation - written as bn - where b is the base, and n the exponent.
When n is a positive integer, the exponentiation corresponds to the repeated multiplication of the base eg.
43 == 4 x 4 x 4
When n is a negative integer, and b is not zero, then the exponentiation corresponds to 1 over the repeated multiplication of the base eg.
2-2 == 1 / 2-2 == 1 / (2 x 2) == 0.25
TODO . formula
A formula that contains at least one free variable
The definition of a function in mathematics can be quite broad as discussed here. They have been around for a long time and hence there are a many different names and ways of expessing them.
The common notation for a function is:-
f: X -> YWhere X is a set that we commonly call the domain of f and Y is the codomain of f. Another way to say it is that f takes elements of set X and gives back elements of set Y.
We say that individual things in a set are called members, or elements.
The following illustrates the idea of a function f which relates values from a domain X to a codomain Y.
f: X -> Y
Domain X Codomain Y
+---------+ +---------+----+
| | | | |
| ■ -------------------> ■ | |
| | | | |
| ■ -------------------> ■ | |
| | | | |
| ■ -------------------> ■ | |
| | | | |
| X | | f(x) | |
+---------+ +---------+ |
| Y |
+--------------+ The set of output values is usually called the range, or image, of the function. In general, the range is usually smaller (a subset) of the codomain. If the range is the whole codomain then we say that f is a surjective function.
Here is an example of a function.
f(x) = x * xIt is common in notation to refer to the name of the function as f but it could be called whatever we wish. x is just a placeholder for the value that gets passed into f. The right-hand side is the implementation of the function ie. what comes out of it.
The above function takes x, squares it and returns the squared value.
Here is a function with no name.
y = x * xThere is still an input x and an output y, and the relationship between the input and output, which in this case is the squaring.
Saying f(4) = 16 is like saying 4 is somehow related to 16. Or 4 -> 16.
We can saying that the height of a tree is related to it's age using function h.
h(age) = age x 20Where a tree grows 20 units every year.
Functions have special rules which are that:-
-
They must work for every possible input value ie. a function which takes a string as an input must be able to work on all strings
-
They only have one relationship for each input value. In other words, for a given input, the function must always output the same value
So, a function relates each element of a set with exactly one element of another set - possibly the same set but it does not have to be.
The two important things to note:-
-
Each element in
Xis related to some element inY. We say that the function covers X (relates every element of it). But some elements ofYmight not be related at all - which is where not every element of the domain relates to an element in the codomain ie. the range is smaller than the codomain. -
Exactly one means that a function is single valued ie. it will not give back more than 1 result for the same input. Many-to-one is allowed ie. two different elements of the domain can relate to the same element (value) in the codomain - in other words, it is allowed for 2 different input values to give you back the same element (value) in the codomain. But one-to-many is not allowed ie. an input value cannot give you back more than one output value.
Another way to think about functions is to write them as an ordered pair. They are called ordered because the input always comes first, and the output second (input, output).
The following means that the function takes a 4 and outputs 16.
(4, 16)A function can then be defined as a set of ordered pairs.
The following example states that "2 is related to 4", 3 is related to 5, 7 is related to 3".
{ (2,4), (3,5), (7,3) }The domain is {2,3,7} (the input values).
The range is {4,5,3} (the output values).
Since a function has to be single valued (an input must always give back the same output) then we can say that if a function contains the ordered pairs (a, b) and (a, c), then b must equal c. Since a cannot produce two different results it means that b and c must be the same output element.
The following is not a function because {2,4} and {2,5} means that 2 could be related to 4 or 5 which is not allowed.
{ (2,4), (2,5), (7,3) }We can also graph ordered pairs because they act as coordinates. So a set of coordinates also define a function - as long as they follow the rules.
In category theory, this is a type of mapping between categories. They can be thought of as homomorphisms between categories.
A functor that maps a category to itself eg. if the category is the set of positive integers, then any mapping which - given a positive integer - always returns a positive integer, is an example of an endofunctor eg. integer addition on the set of positive integers is an endofunctor since it always returns a positive integer ie. maps the category of positive integers to itself.
In maths, graph theory studies the structures (graphs) used to model pairwise relations between objects. It's a pretty large subject if this glossary of terms is anything to go by.
The following example shows a graph with 6 vertices and 9 edges.
⃞-----⃞
/ \ / \
/ \ / \
⃞-----⃞----⃞ -------- a vertex (aka node or point)
\ /
\ / ------ an edge (aka arc or line)
⃞Each edge has two or more vertices to which it is attached, called it's endpoints. If the graph has edges which are attached to more than two vertices then it is called a hypergraph.
There are many variations in the fundamental structure of graphs, but here are few key terms.
⃞ ----▶ ⃞
▲ |
| |
| ▼
⃞ ◀---- ⃞A Directed graph (or digraph) is a graph in which edges have orientations (directions between two vertices). It is written as an ordered pair of sets G = (V, A) (sometimes also written G = (V, E)) where:-
Vis a set which elements are called vertices, nodes or points.Ais a set of ordered pairs of vertices, called arrows, directed edges (sometimes simply referred to as edges with the corresponding set namedEinstead ofA) or directed arcs, or directed lines.
So, (V, A) is a pair of a set of Vertices and a set of Arrows.
x -> yAn Arrow (x, y) is an ordered pair of vertices x and y and is considered to be directed from x to y (x -> y).
⃞ ----- ⃞
| |
| |
| |
⃞ ----- ⃞In this graph type, the edges have no orientation. The edge (x, y) is identical to edge (y, x) ie. they are not ordered pairs, but sets of vertices.
A heap is a tree-based data structure that satisfies the heap property. It is an implementation of a priority queue whereby the largest element will be at the top of the tree and the smallest element will be somewhere at the bottom of the tree.
The heap property states that: if P is a parent node of C, then the key (the value) of P is greater than the key of node C. This defines a "max heap", but a heap may also be in reverse, called a "min heap". In a min heap, the keys of the parent nodes are less than or equal to those of the children and the lowest key is in the root node (at the top of the tree).
There are different types of [heap](https://en.wikipedia.org/wiki/Heap_(data_structure), but common operations are:-
max(orfind-max) which finds the maximum element (aka _peek)min(orfind-min) which finds the minimum elementmerge(union) joins two heaps to form a new heap and preserves the original heapsmeldjoins two heaps and destroys the original heaps
In mathematics, an identity element or neutral element is a special type of element of a set with respect to a binary operation on that set, which leaves other elements unchanged when combined with them. This concept is used in algebraic structures such as groups. The term identity element is often shortened to identity (as will be done in this article) when there is no possibility of confusion.
Let (S, ∗) be a set S with a binary operation ∗ on it. Then an element e of S is called a left identity if e ∗ a = a for all a in S, and a right identity if a ∗ e = a for all a in S. If e is both a left identity and a right identity, then it is called a two-sided identity, or simply an identity.
An identity with respect to addition is called an additive identity (often denoted as 0) and an identity with respect to multiplication is called a multiplicative identity (often denoted as 1). The distinction is used most often for sets that support both binary operations, such as rings. The multiplicative identity is often called the unit in the latter context.
Example:-
If you consider that String represents the set S (of all strings) which has a binary operation + which operates on 2 strings from the set, then we can show that an empty string "" represents the identity element (both left and right) of the set - since no matter what string we take from the set, if we use an empty string "" on the left or right of the operation then it has no effect:-
"" + "yo" = "yo" // left identity
"yo" + "" = "yo" // right identityNearly all computer hardware is designed to execute machine code written in imperative style.
TODO...
In mathematics, and computing, this means the opposite of something.
Examples:-
An inverse function is a function that "reverses" another function: if the function f applied to an input x gives a result of y, then applying its inverse function g to y gives the result x, and vice versa.
The additive inverse of a number a is the number that, when added to a, yields zero. This number is also known as the opposite (number), sign change, and negation. For a real number, it reverses its sign: the opposite to a positive number is negative, and the opposite to a negative number is positive. Zero is the additive inverse of itself.
The additive inverse of a is denoted by unary minus: −a. For example, the additive inverse of 7 is −7, because 7 + (−7) = 0
Also written as λ-calculus is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any single-taped Turing machine.
This is the inverse operation to exponentiation.
The third power (or cube) of 2 is 8, because 8 is the product of three factors of 2.
23 = 2 x 2 x 2 = 8
The logarithm of 8 - with respect to the base 2 - is 3, ie.
log2 8 = 3
The logarithm is denoted logb(x) (pronounced as "the logarithm of x to base b" or "the base-b logarithm of x"). In the equation y = logb(x), the value y is the answer to the question "To what power must b be raised, in order to yield x?".
Logarithms can also be negative.
In computer science, a macro (from the Greek "macroinstruction") is a rule which specifies how an input sequence should be mapped into a replacement output sequence. The process of producing the output sequence (from the input sequence) is known as macro expansion. The use of the term expansion is because the usefulness of macros is usually based on them mapping a sequence of programming instructions into a larger sequence of programming instructions
Their general purpose is to enable code reuse, and also facilitate other more specific uses such as designing domain-specific languages (DSLs).
See What are Macros good for.
See Macros - official Scala documentation.
See A good Macro tutorial.
A good appreciation of macros involves also having an understanding Abstract-Syntax Trees and Quasiquotes. See also, Understanding Trees.
The positive fractional part of a floating point number. eg. for the number 3.14159, the mantissa is 0.14159
In maths, the term mapping (usually shortened to map) is generally used to refer to a general function or a function with special properties. In category theory it is often used more generally as a synonym for morphism, or arrow.
In Scala, it is generally used to name a function that ranges over some container and applies a provided function to each element in the container. It preserves the structure by returning the same type of container, which contains the results of the applying the provided function to each element.
If we wish to apply a function to an Int value, but it is inside a List, then I guess we could write some code ourselves that explicitly gets the item out and then applies the function. But what if there are a 1000 or more values in the list, this wouldn't be a very efficient way to work. So we define functions, like map, on these containers, that applies the function to each element for us, and return the results - a new container with the results of the function application. If we apply a function to a 1000 values in a List then the most useful way to get the result is in another List containing the results of applying the function to each element.
A programming model for parallel and distributed processing. Consisting of a map method which perfoms filtering and sorting, and a reduce method that performs the summary operation.
Metaprogramming is a programming technique in which computer programs have the ability to treat programs as their data. It means that a program can be designed to read, generate, analyse or transform other programs, and even modify itself while running.
Macros are an example of metaprogramming since they map a sequence of programming instructions into another (usually larger) sequence of programming instructions.
So macros are basically code which works on other code, not data.
Aka replication
... TBC ...
A monomorphic function is one which only operates on one type of data eg. a function that only takes an Int and returns an Int and cannot work with other types. This contrasts with polymorphic functions which can operate on a range, or even any, data type.
To give another example, the following is a higher-order function (HOF) that is fixed to only operate on functions
that take arguments of type Int and return a resukt of type String
def op(f: Int => String): String = { ... } In maths, a morphism is a structure-preserving map (function) from one mathematical structure to another.
A structure-preserving map between two algebraic structures.
In category theory, a natural transformation provides a way of transforming one functor into another while respecting the internal structure of the categories involved. Hence, a natural transformation can be considered to be a "morphism of functors".
A monad (for example) is an endofunctor that has two natural transformations flatMap (or bind), and unit.
A whole number (not a fractional number) that can be positive, negative, or zero.
The set of whole, non-negative numbers used for counting. The set of natural numbers, denoted N, is defined as:
N = {0, 1, 2, 3, ...}Some consider that the natural numbers correspond to the set of non-negative integers - ie. they include zero {0, 1, 2, ...}
Some consider that the set corresponds to the positive integers - ie. excluding zero {1, 2, 3, ...}
A number defined by the ratio of some integer p and some nonzero natural number q. The set of rational numbers is denoted Q, and represents the set of all possible integer-to-natural-number ratios p/q.
1/10, 200/40, 2/3, 4/5 are all rational numbers.
An irrational number is a real number that cannot be reduced to any ratio between an integer p and a natural number q. The union of the set of irrational numbers and the set of rational numbers forms the set of real numbers.
Examples of irrational numbers are 21/2 (the square root of 2), 3 1/3 (the cube root of 3), the circular ratio pi, and the natural logarithm base e . The quantities 2 1/2 and 3 1/3 are examples of algebraic numbers. Pi and e are examples of special irrationals known as a transcendental numbers.
The real numbers include all the rational numbers, such as the integer −5 and the fraction 4/3, and all the irrational numbers, such as √2 (1.41421356…, the square root of 2, an irrational algebraic number).
A calculation from zero or more input values (operands) to an output value.
The elementary arithmetic operations are + plus (addition), - minus (subtraction), x times (multiplication), ÷ obelus (division).
The two most common types of operations are unary and binary.
Unary operations involve just 1 value and negation is an example.
Binary operations take two values - addition, subtraction, multiplication, division, exponentiation.
There are also logcial operations such as and, or, not.
Operations on sets include binary operations union and intersection, and the unary operation complementation.
Operations on functions include composition and convolution.
The values for which an operation is defined form a set called it's domain. Operations may not be defined for every possible value - for example, in the set of real numbers you cannot divide by zero, so for the division operation, the domain set would not include zero. The set which contains the values produced is called the codomain.
The set of actual values produced by an operation is called it's range. For example, in the set of real numbers, the squaring operation only produces non-negative numbers; so the codomain is the set of real numbers but the range is the non-negative numbers. So the codomain for the squaring operation includes all real numbers, but since it only produces non-negative numbers, the negative numbers in the codomain are not included in the range.
In general computing, the general usage of orthogonal is where two things vary from each other independently. One thing can be used without considering its after effects towards other.
From "The Art of Unix Programming":- "Orthogonality is one of the most important properties that can help make even complex designs compact. In a purely orthogonal design, operations do not have side effects; each action (whether it's an API call, a macro invocation, or a language operation) changes just one thing without affecting others. There is one and only one way to change each property of whatever system you are controlling."
If we say that two concepts are orthogonal then we mean that they work well togethor. For example, sharding (the partitioning of data) and replication (the mirroring) - which are approaches at improving performance and availability - are different things but they are orthogonal so they work well togethor. In a key-value-store such as Redis, sharding is used to scale Writes (it improves performance by spreading the write load across different nodes), and replication is used to scale Reads (since the data is duplicated across several nodes it doesnt matter which node you hit for a read so you can spread the load across them). We can combine these two concepts by replicating shards.
In terms of programming languages, orthogonality means that a relatively small set of primitive constructs can be combined in a relatively small number of ways to build the control and data structures of the language. This is an important characteristic since the more orthogonal a language is, the fewer constructs there are to combine and their combination always provides a consistent result. This makes it easier to learn, read and write programs in that programming language.
From "Programming Language Pragmatics":- "Orthogonality means that features can be used in any combination, that the combinations all make sense, and that the meaning of a given feature is consistent, regardless of the other features with which it is combined."
In Java, for example, the keywords public and static can be said to be orthogonal since they can be combined (in a method signature) and the effect is always the same - they do not interfere with each others purpose (no side effects) and the result that they each produce does not vary depending on how or where they are applied. Note: Im not sure whether Java can be considered an orthogonal language in it's entirety however.
Something involving two values (a pair) - usually used in the conetext of an operation performed on two values eg. a binary operation is a pairwise operation (this is a particular type of pairwise operation that works on two values from the same set and produces a single value from that set).
Aka sharding
... TBC ...
Pointfree is a style of writing functions. It is very common for functional programmers to write functions as a composition of other functions, never mentioning the actual arguments they will be applied to.
In the following declaration we define the function f in terms of its action on an arbitrary point (aka value) x
f x = x + 1Contrast this with the points-free version:
f = (+ 1)where there is no mention of the value x on which the function f is acting.
A common misconception is that the term 'point' of the pointfree style refers to the (.) operator. This is incorrect though, it refers to the values that the functions are being applied to. The term originated in topology, a branch of mathematics which works with spaces composed of points (ie. values), and functions between those spaces. So a 'points-free' definition of a function is one which does not explicitly mention the points (values) of the space on which the function acts.
! I don't really get this at the time of writing - hopefully it will become clearer later.
From wiki:-
In mathematics, the qualifier pointwise is used to indicate that a certain property is defined by considering each value f(x) of some function f. An important class of pointwise concepts are the pointwise operations — operations defined on functions by applying the operations to function values separately for each point in the domain of definition.
A polymorphic function is one which is designed to be able to work on a range of, or even any, type.
Here is an example from here which takes an Array and a function as arguments. The details are unimportant - what is important is that the function can take an Array of any type and a function which maps any type to a Boolean.
def findFirst[A](as: Array[A], p: A => Boolean): Int = { ...In OO languages like Java the term polymorphism usually implies some form of subtyping or inheritance relationship. There are no interfaces or subtyping here in this form of polymorphism. The kind of polymorphism we are referring to here is generally referred to as parametric polymorphism.
See type-system/polymorphic-functions.
An expression consisting of:-
- variables (indeterminites)
- coefficients
- the operators - addition, subtraction, multiplication
- non-negative integer exponents
An example of a polynomial of a single indeterminate x is:
x2 − 4x + 7
Where:-
x is a variable
2 is a exponent
4 & 7 are coefficients
- + are operators
The following are all examples of polynomials in algebra (poly means many and nomial mean term - so many terms).
3xy // monomial (1 term)
3xy - 5x // binomial (2 terms)
3xy - 5x + 3 // trinomial (3 terms)
...A product is the result of multiplying. For instance, 6 is the product of 2 and 3 (the result of multiplication), and x · (2+x) is the product of x and (2+x) (indicating that the two factors should be multiplied together).
Here are some common definitions for this term: -
- Primitive is the simplest type of programming language item. It may also refer to the smallest processing unit accessible by a programmer.
- Primitive types are basic programming language building blocks.
- A programmer combines primitives to create more complex operations.
- Primitive types are also known as built-in types or basic types.
- Primitives are used to create more complex pieces of code.
Quantification is a construct that specifies the quantity of things in a range of quantification that satisfy an open formula eg. the set of natural numbers is an example of such a range.
In arithmetic, it allows the expression of statements such as every natural number has a successor. A language element which generates a quantification (such as "every") is called a quantifier. The resulting expression is a quantified expression, it is said to be quantified over the predicate (such as "the natural number x has a successor") whose free variable is bound by the quantifier.
The range of quantification specifies the set of values that the variable can have eg. the set of natural numbers. Specification of the range of quantification allows us to express the difference between, asserting that a predicate holds for some natural number or for some real number.
Note that the range may not be finite eg. the set of natural numbers is infinite, but it is bounded by the fact that the set can only contain whole non-negative integers.
The two most common quantifiers are the universal quantifier and the existential quantifier. The traditional symbol for the universal quantifier is "∀", a rotated letter "A", which stands for "for all" or "all". The corresponding symbol for the existential quantifier is "∃", a rotated letter "E", which stands for "there exists" or "exists".
The answer after you divide one number by another dividend / divisor = quotient
A priority queue is an implementation of a queue in which each element has a priority associated with it. The elements are ordered such that the element with the highest priority is at the head of the queue and is the first to be dequeued. The element with the lowest priority is at the back of the queue. Elements with the same priority are positioned according to their order in the queue.
Common implementations of a priority queue are a heap but a priority queue is a more abstract concept and may be implemented in different ways.
A queue is an abstract data type which has a linear structure. It may also be described as a sequential collection. The entities it contains are kept in order, whereby new values are always added (enqueue) to the end (back) of the queue and values are always removed (dequeue) from the head (front) position - this makes a queue a First-In-First-Out (FIFO) structure. Queues often provide another operation, usually called peek, which returns the entity in head position without dequeuing it. Common implementations of queues are priority queues (eg. heaps), buffers and linked lists.
This is the result in a division operation. For example, when dividing twenty-one (the dividend) by three (the divisor), the quotient is seven.
Aka mirroring
... TBC ...
Scientific notation is a special way of writing very large or very small numbers (also sometimes called standard form).
The following are all equivalent:
3200
3.2 x 10 x 10 x 10
3.2 × 103
3.2e+3
-45000
-4.5 x 10 x 10 x 10 x 10
-4.5 × 104
-4.5e+4
0.00024
2.4 / 10 / 10 / 10 / 10
2.4 × 10-4
2.4e-4
-0.00003
-3 / 10 / 10 / 10 / 10 / 10
-3 × 10-5
-3e-5
A fundamental cornerstone of maths, they are collections of elements that share some property P - the characteristic property of a set. The following is a common notation for a set:-
{ x: P(x) }Which reads:- the set of all x that have the property P.
Aka partitioning
... TBC ...
When a process is waiting to gain access to some synchronized (protected) resource other processes monopolize access to the resource preventing the initial process from ever obtaining access and thus is forced to wait indefinately.
TODO ...
Also, see asynchronous.
The definition of the word synchronous (from Greek, "syn" meaning "with" and "chronous" meaning "time") describes the fact that processes or events are coordinated in time.
In computing, this term can be used to refer to two different but related concepts:-
-
Data Synchronization - which concerns itself with keeping multiple copies of a dataset in coherence with one another. Data Integrity is a broad term which covers the accuracy and consistency of data over it's lifetime and which encompases the process of data synchronization.
-
Process Synchronization - an abstract description is the idea that multiple processes must join up at some point in order to commit to a certain sequence of events.
Here are some examples:-
-
Multiple threads in a concurrent system must be synchronized so that they cannot simultaneously execute the same piece of code or access shared (global) data otherwise they may interleave causing unpredictable (non-deterministic) results. The synchronization here is that the threads wait on each other to take their turn and signal to each other when they are done so that others may take their turn. There are multiple ways in which this concurrent orchestration can be achieved and implemented.
-
In program-to-program communication, a synchronous transaction is one where each end of the transmission must process only one transmission at a time. The sender must wait until the reciever has responded (either with success or fail/try again). Each successive transmission of data requires a response to the previous transmission before a new one can be initiated.
HTTP is one example of a synchronous
The syntax of a computer programming language can also be described as it's grammer or alphabet. It is the set of rules that generally defines two things:-
- What constitutes a token - the smallest units of a programming language.
- How these tokens can be legally combined.
In the following expression we have 4 tokens.
val exp = 5You will notice that it can be represented as a tree structure - hence the term syntax tree.
val exp = 5
// \__ __/ \__ __/ \__ __/ \__ __/
// \/ \/ \/ \/
// keyword identifier operator number
// \ / /
// \ / /
// \ / /
// left hand side right hand side
// \ /
// \ /
// \ /
// \ /
// variable declarationcombinations of symbols that are considered to be a correctly structured document or fragment in that language. The syntactic analysis - the process of checking that a document is well formed - is done during compilation. Any parts of the document that are not considered well formed (by the compiler) will generate syntaxt errors - preventing the compiler from making any further progress until corrected.
Language syntax breaks down into 3 general levels:-
- Words – the lexical level, determining how characters form tokens.
- Phrases – the grammar level, narrowly speaking, determining how tokens form phrases.
- Context – determining what objects or variables names refer to, if types are valid, etc.
Example - Consider the following Scala expression.
val exp = 5The Scala language syntax describes what are valid:-
- Words -
Phrases
keywords (eg.
lazy,val), where they can legally be placed in an expression
When compiling a block of code, the compiler will first perform syntactic (syntax) anaysis. Syntax analysis (also known as parsing) involves parsing the token sequence to identify the syntactic structure of the program. This phase typically builds a parse tree, which replaces the linear sequence of tokens with a tree structure built according to the rules of a lexical grammar which define the language's syntax.
to check that the code complies with the language's rules for words, phrases and context (the compiler front-end).
The semantics of a computer programming language are the rules which describe what the code means ie. what should happen when a block of code is executed.
Semantic analysis will include things like type checking, making sure variables are declared before use etc etc.
In mathematics, terms are discrete components of a formula. As an analogy (to natural language), where a noun phrase (such as "green chair") refers to an object, and a whole sentence refers to a fact (such as "there was a green chair in the room"), in mathematical logic, a term is a mathematical object and a formula is a mathematical fact.
In the formula 7 + 3x - 2x, the 7, 3x and 2x are all terms.
Also, see polynomial.
In computing, a tree is a commonly used abstract data type (ADT) that simulates a hierarchical tree structure, with a root value (or root _node), and subtrees of children, represented as a set of linked nodes.
Here a few fundamental features:-
- like a graph, a tree is made up of nodes (or vertices) and edges.
- in theory, you can have a tree with no nodes (empty or null).
- a non-empty tree consists of a 1 root node nd potentially many levels of subtrees (nodes that form a hierarchy).
- unlike a graph, the structure cannot be cyclic ie. a node cannot have more than 1 parent. (see this for a digram).
- all parts of the tree must be connected, that is, all nodes must be connected in some way (via the hierarchy of the tree) to the root node.
- a rooted tree is a tree in which one vertex has been designated the root. The edges of a rooted tree can be assigned a natural orientation, either away from or towards the root, in which case the structure becomes a directed rooted tree.
- an ordered tree (or plane tree) is a rooted tree in which an ordering is specified for the children of each vertex.
More terminology.
TODO... this definition is a bit too abstract I think to be of much value - and I think it refers mostly to the theory that came from Haskell. RRQUIRES CLEANUP.
Often confusing to newcomers with an OO background, Type Classes are not the same thing as a class you might define in Java.
A type class C defines some behaviour in the form of operations that must be supported by a type T for it to be a member of type class C. Whether the type T is a member of the type class C is not inherent in the type. Rather, any developer can declare that a type is a member of a type class simply by providing implementations of the operations the type must support. Now, once T is made a member of the type class C, functions that have constrained one or more of their parameters to be members of C can be called with arguments of type T.
As such, type classes allow ad-hoc and retroactive polymorphism. Code that relies on type classes is open to extension without the need to create adapter objects.
Explanation of Type classes Type class - Neophytes Guide
TODO ...
A bound variable is a variable that was previously free, but has been bound to a specific value or set of values. For example, the variable x becomes a bound variable when we write:
For all x, (x + 1)2 = x2 + 2x + 1
// or
There exists x such that x2 = 2.In either of these above propositions, it does not matter logically whether we use x or some other letter. However, it could be confusing to use the same letter again elsewhere in some compound proposition. That is, free variables become bound, and then in a sense retire from being available as stand-in values for other values in the creation of formulae.
In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation that specifies places in an expression where substitution may take place. The idea is related to a placeholder (a symbol that will later be replaced by some literal string), or a wildcard character that stands for an unspecified symbol.
In computer programming, the term free variable refers to variables used in a function that are neither local variables nor parameters of that function.
In mathematics (specifically graph theory), a vertex (also called a node or point) is the
Imperative languages like Java and C# have a volatile keyword which is designed to address the visibility problem - how do you make a change to a variable's value visible to all CPUs/cores (and therefore all threads)? ie. how to you communicate an update made to a value in one cache line to all other cache lines on them same machine?
The volatile feature ensures this by requiring that volatile variables are always read/written to/from main memory rather than local cache, meaning that a core can never work with a stale value from local cache.
Some further resources for understanding mathmatical terms/notation:-
http://www.cut-the-knot.org/do_you_know/few_words.shtml