#Programming_paradigms : #Array_programming (also vector or multidimensional)
Generalizes operations on scalars to apply transparently to vectors, matrices, and higher-dimensional arrays.
Is used in scientific and engineering settings.
e.g. APL, J, Fortran, #Ada, #MATLAB, #Perl Data Language (PDL) and the NumPy extension to #Python.
Vectorized operation
Operations applied at once to an entire set of values like arrays; regardless of whether it is executed on a vector processor or not.
Function rank
Analogous to tensor rank in mathematics
Functions that operate on data may be classified by the number of dimensions they act on.
• Ordinary multiplication, for example, is a scalar ranked function because it operates on zero-dimensional data (individual numbers).
• The cross product operation is an example of a vector rank function because it operates on vectors, not scalars.
• Matrix multiplication is an example of a 2-rank function, because it operates on 2-dimensional objects (matrices).
Collapse operators reduce the dimensionality of an input data array by one or more dimensions. For example, summing over elements collapses the input array by 1 dimension.
Generalizes operations on scalars to apply transparently to vectors, matrices, and higher-dimensional arrays.
Is used in scientific and engineering settings.
e.g. APL, J, Fortran, #Ada, #MATLAB, #Perl Data Language (PDL) and the NumPy extension to #Python.
Vectorized operation
Operations applied at once to an entire set of values like arrays; regardless of whether it is executed on a vector processor or not.
Function rank
Analogous to tensor rank in mathematics
Functions that operate on data may be classified by the number of dimensions they act on.
• Ordinary multiplication, for example, is a scalar ranked function because it operates on zero-dimensional data (individual numbers).
• The cross product operation is an example of a vector rank function because it operates on vectors, not scalars.
• Matrix multiplication is an example of a 2-rank function, because it operates on 2-dimensional objects (matrices).
Collapse operators reduce the dimensionality of an input data array by one or more dimensions. For example, summing over elements collapses the input array by 1 dimension.
GoTo
- is a statement that performs a one-way transfer of control to another point of code; in contrast to a function call which returns control.
Its use has declined significantly since the advent of structured programming in the 1960s. Structured programming languages like #Pascal introduced control structures such as: subroutines, loops and multiway branch for clarity and efficiency. These replace equivalent flows written using gotos and ifs.
Language support:
• #C
• #CSharp: also makes
• #Perl
• #PHP there was no native support for goto until version 5.3
• #Java:
• #Python: does not support it but there are several joke modules that provide it.
The structured program theorem proves that
- is a statement that performs a one-way transfer of control to another point of code; in contrast to a function call which returns control.
Its use has declined significantly since the advent of structured programming in the 1960s. Structured programming languages like #Pascal introduced control structures such as: subroutines, loops and multiway branch for clarity and efficiency. These replace equivalent flows written using gotos and ifs.
Language support:
• #C
• #CSharp: also makes
case and default statements labels, whose scope is the enclosing switch statement; goto case or goto default is often used to replace explicit "fall-through", which C# disallows.• #Perl
• #PHP there was no native support for goto until version 5.3
• #Java:
goto is a reserved word, but is unusable.• #Python: does not support it but there are several joke modules that provide it.
The structured program theorem proves that
goto is not necessary to write programs.The diamond problem
- is an ambiguity that arises when two classes B and C inherit from A, and class D inherits from both B and C. If there is a method in A that B and C have overridden, and D does not override it, then which version of the method does D inherit: that of B, or that of C?
For example, in the context of GUI software development, a class Button may inherit from both classes Rectangle (for appearance) and Clickable (for functionality/input handling), and classes Rectangle and Clickable both inherit from the Object class. Now if the equals method is called for a Button object and there is no such method in the Button class but there is an overridden equals method in Rectangle or Clickable (or both), which method should be eventually called?
How different languages deal with it:
• Common #Lisp: by order "...in the order in which parent classes are named in the subclass definition"
• Curl: "and the secondary constructor will be invoked for all other subclasses."
• Eiffel: "Eiffel will automatically join features together, if they have the same name and implementation."
• Go: compile-time error
• #Java: compile-time error
• #OCaml: by order "...are inherited in the same order, with each newly inherited method overriding any existing methods."
• #Perl: by order "...from as an ordered list. The compiler uses the first method it finds..."
• #Python: by order
• #Ruby: by order "...as rightmost depth first resolution."
• #Scala: by order "allows multiple instantiation of traits, which allows for multiple inheritance by adding a distinction between the class hierarchy and the trait hierarchy. A class can only inherit from a single class, but can mix-in as many traits as desired." This approach is the most similar to #Nile's; traits being qualifications.
• Tcl: by order "the order of specification in the class declaration affects the name resolution for members..."
Languages that allow only single inheritance, where a class can only derive from one base class, do not have the diamond problem.
Moreover, languages such as #Ada, Objective-C, #CSharp, #Delphi/Free #Pascal, Java, #Swift and PHP allow multiple-inheritance of interfaces (called protocols in Objective-C and Swift). Interfaces are like abstract base classes that specify method signatures without implementing any behavior.
When several interfaces declare the same method signature, as soon as that method is implemented (defined) anywhere in the inheritance chain, it overrides any implementation of that method in the chain above it (in its superclasses). Hence, at any given level in the inheritance chain, there can be at most one implementation of any method. Thus, single-inheritance method implementation does not exhibit the Diamond Problem even with multiple-inheritance of interfaces.
- is an ambiguity that arises when two classes B and C inherit from A, and class D inherits from both B and C. If there is a method in A that B and C have overridden, and D does not override it, then which version of the method does D inherit: that of B, or that of C?
For example, in the context of GUI software development, a class Button may inherit from both classes Rectangle (for appearance) and Clickable (for functionality/input handling), and classes Rectangle and Clickable both inherit from the Object class. Now if the equals method is called for a Button object and there is no such method in the Button class but there is an overridden equals method in Rectangle or Clickable (or both), which method should be eventually called?
How different languages deal with it:
• Common #Lisp: by order "...in the order in which parent classes are named in the subclass definition"
• Curl: "and the secondary constructor will be invoked for all other subclasses."
• Eiffel: "Eiffel will automatically join features together, if they have the same name and implementation."
• Go: compile-time error
• #Java: compile-time error
• #OCaml: by order "...are inherited in the same order, with each newly inherited method overriding any existing methods."
• #Perl: by order "...from as an ordered list. The compiler uses the first method it finds..."
• #Python: by order
• #Ruby: by order "...as rightmost depth first resolution."
• #Scala: by order "allows multiple instantiation of traits, which allows for multiple inheritance by adding a distinction between the class hierarchy and the trait hierarchy. A class can only inherit from a single class, but can mix-in as many traits as desired." This approach is the most similar to #Nile's; traits being qualifications.
• Tcl: by order "the order of specification in the class declaration affects the name resolution for members..."
Languages that allow only single inheritance, where a class can only derive from one base class, do not have the diamond problem.
Moreover, languages such as #Ada, Objective-C, #CSharp, #Delphi/Free #Pascal, Java, #Swift and PHP allow multiple-inheritance of interfaces (called protocols in Objective-C and Swift). Interfaces are like abstract base classes that specify method signatures without implementing any behavior.
When several interfaces declare the same method signature, as soon as that method is implemented (defined) anywhere in the inheritance chain, it overrides any implementation of that method in the chain above it (in its superclasses). Hence, at any given level in the inheritance chain, there can be at most one implementation of any method. Thus, single-inheritance method implementation does not exhibit the Diamond Problem even with multiple-inheritance of interfaces.
Blocks
- are lexical structures that allow many statements to be treated as one. A language that allows blocks and nested blocks, is called block-structured. Blocks are fundamental to #structured programming.
As scopes
Depending on the language, certain distinguished blocks may be treated as lexical scopes; otherwise, identifiers assigned in outer blocks are visible inside inner blocks, unless shadowed.
Syntax
• Free-form
Whitespace only delimits tokens and has no other significance
•
•
•
• Off-side rule
Indentation groups blocks of code
e.g. #Python, #Haskell, #Cobra, #CoffeeScript
Limitations
In some languages blocks do not fully support all declarations; for instance many C-derived languages do not permit nested functions.
- are lexical structures that allow many statements to be treated as one. A language that allows blocks and nested blocks, is called block-structured. Blocks are fundamental to #structured programming.
As scopes
Depending on the language, certain distinguished blocks may be treated as lexical scopes; otherwise, identifiers assigned in outer blocks are visible inside inner blocks, unless shadowed.
Syntax
• Free-form
Whitespace only delimits tokens and has no other significance
•
begin ... end: #ALGOL, #Pascal•
{ ... }: #C, #Perl, #JS, #Nile•
( keyword ... ): #Lisp• Off-side rule
Indentation groups blocks of code
e.g. #Python, #Haskell, #Cobra, #CoffeeScript
Limitations
In some languages blocks do not fully support all declarations; for instance many C-derived languages do not permit nested functions.
Data layout
- is how multidimensional arrays are stored in a linear storage such as RAM. It is critical for:
• correctly passing arrays between programs written in different programming languages
• performance when traversing an array because modern CPUs, due to caching, process sequential data more efficiently than non-sequential data
• contiguous access makes it possible to use SIMD instructions that operate on vectors of data
Row-major versus column-major order
The difference between the orders lies in which elements of an array are contiguous in memory. In a row-major order, the consecutive elements of a row reside next to each other, whereas the same holds true for consecutive elements of a column in a column-major order. While the terms allude to the rows and columns of a two-dimensional array, the orders can be generalized to arrays of any dimension.
Transposition
As exchanging the indices of an array is the essence of array transposition, an array stored as row-major but read as column-major (or vice versa) will appear transposed. As actually performing this rearrangement in memory is typically an expensive operation, some systems provide options to specify individual matrices as being stored transposed.
Languages support
• Row-major: #C/C++/Objective-C (for C-style arrays), PL/I, #Pascal, Speakeasy, SAS, and Rasdaman
• Column-major: #Fortran, #MATLAB, GNU Octave, S-Plus, #R, #Julia, and Scilab.
• Neither (for less dense arrays):
• Iliffe vectors: #Java, #Scala, #Swift. #Ruby, #Perl, #PHP, #JavaScript, Visual Basic .NET
• Lists of lists: #Python, Wolfram Language of Wolfram Mathematica
• Tables of tables: #Lua
- is how multidimensional arrays are stored in a linear storage such as RAM. It is critical for:
• correctly passing arrays between programs written in different programming languages
• performance when traversing an array because modern CPUs, due to caching, process sequential data more efficiently than non-sequential data
• contiguous access makes it possible to use SIMD instructions that operate on vectors of data
Row-major versus column-major order
The difference between the orders lies in which elements of an array are contiguous in memory. In a row-major order, the consecutive elements of a row reside next to each other, whereas the same holds true for consecutive elements of a column in a column-major order. While the terms allude to the rows and columns of a two-dimensional array, the orders can be generalized to arrays of any dimension.
Transposition
As exchanging the indices of an array is the essence of array transposition, an array stored as row-major but read as column-major (or vice versa) will appear transposed. As actually performing this rearrangement in memory is typically an expensive operation, some systems provide options to specify individual matrices as being stored transposed.
Languages support
• Row-major: #C/C++/Objective-C (for C-style arrays), PL/I, #Pascal, Speakeasy, SAS, and Rasdaman
• Column-major: #Fortran, #MATLAB, GNU Octave, S-Plus, #R, #Julia, and Scilab.
• Neither (for less dense arrays):
• Iliffe vectors: #Java, #Scala, #Swift. #Ruby, #Perl, #PHP, #JavaScript, Visual Basic .NET
• Lists of lists: #Python, Wolfram Language of Wolfram Mathematica
• Tables of tables: #Lua
#regex
Regex Cheatsheet
All the rules apply to all of the three languages: #Python, #Perl (PCRE) and #JavaScript, unless stated otherwise.
Source: debuggex.com
Basics
Quantifiers
⚠️ Default is greedy. Append ? for reluctant.
Groups
Python and PCRE:
PCRE only:
Character Classes
Assertions
Python and PCRE:
PCRE:
Flags
Python and PCRE:
JavaScript only:
Special Characters
JavaScript and PCRE:
Hexadecimal character YY (
Replacement
Python only:
JavaScript only:
Escapes
PCRE only:
POSIX Classes
PCRE only:
Regex Cheatsheet
All the rules apply to all of the three languages: #Python, #Perl (PCRE) and #JavaScript, unless stated otherwise.
Source: debuggex.com
Basics
.: Any character except newlinea: The character aab: The string aba|b: a or ba*: 0 or more a's\: Escapes a special characterQuantifiers
*: 0 or more+: 1 or more?: 0 or 1{2}: Exactly 2{2, 5}: Between 2 and 5{2,}: 2 or more(,5}: Up to 5 (Python only)⚠️ Default is greedy. Append ? for reluctant.
Groups
(...): Capturing group(?:...): Non-capturing group\Y: Match the Y'th captured groupPython and PCRE:
(?P<Y>...): Capturing group named Y(?P=Y): Match the named group Y(?#...): CommentPCRE only:
(?>...): Atomic group(?|...): Duplicate group numbers(?R): Recurse into entire pattern(?Y): Recurse into numbered group Y(?&Y): Recurse into named group Y\g{Y}: Match the named or numbered group Y\g<Y>: Recurse into named or numbered group YCharacter Classes
[ab-d]: One character of: a, b, c, d[^ab-d]: One character except: a, b, c, d[\b]: Backspace character\d: One digit\D: One non-digit\s: One whitespace\S: One non-whitespace\w: One word character\W: One non-word characterAssertions
^: Start of string$: End of string\b: Word boundary\B: Non-word boundary(?=...): Positive lookahead(?!...): Negative lookaheadPython and PCRE:
\A: Start of string, ignores m flag\Z: End of string, ignores m flag(?<=...): Positive lookbehind(?<!...): Negative lookbehind(?()|): ConditionalPCRE:
\G: Start of matchFlags
i: Ignore casem: ^ and $ match start and end of linePython and PCRE:
s: . matches newline as wellx: Allow spaces and commentsL: Locale character classesu: Unicode character classes(?iLmsux): Set flags within regexJavaScript only:
g: Global MatchSpecial Characters
\n: Newline\r: Carriage return\t: Tab\YYY: Octal character YYY\xYY: Hexadecimal character YYJavaScript and PCRE:
\0: Null character\cY: Control character YHexadecimal character YY (
\uYY for JavaScript and \x{YY} for PCRE)Replacement
Python only:
\g<0>: Insert entire match\g<Y>: Insert match Y (name or number)\Y: Insert group numbered YJavaScript only:
$$: Inserts $$&: Insert entire match$`: Insert preceding string$': Insert following string$Y: Insert Y'th captured groupEscapes
PCRE only:
\Q..\E: Remove special meaningPOSIX Classes
PCRE only:
[:alnum:]: Letters and digits[:alpha:]: Letters[:ascii:]: Ascii codes 0 - 127[:blank:]: Space or tab only[:cntrl:]: Control characters[:digit:]: Decimal digits[:graph:]: Visible characters, except space[:lower:]: Lowercase letters[:print:]: Visible characters[:punct:]: Visible punctuation characters[:space:]: Whitespace[:upper:]: Uppercase letters[:word:]: Word characters[:xdigit:]: Hexadecimal digitsOpenCL (Open Computing Language)
- is a parallelism framework for writing programs that execute across heterogeneous platforms consisting of one host CPU and any number of compute devices. These devices include GPUs, CPUs with SIMD instructions, FPGAs, Movidius Myriad 2, Adapteva epiphany and DSPs.
A compute device is broken down to several compute units, which themselves are broken down to multiple PEs (processing elements). A single function execution can run on any number of PEs in parallel. How a compute device is subdivided into compute units and PEs is up to the vendor.
It defines an API for programs running on the host to launch functions on compute devices and manage device memory. This API is defined for C and C++, as well as third-parties such as #Python, #Java, #Perl, #DotNET, etc. A more recent, higher-level model is SYCL; which is purely based on C++11. Programs in OpenCL are compiled at run-time therefore its applications are portable between various host devices.
A four-level memory hierarchy is defined for the compute device:
• global: shared by all PEs, high access latency
OpenCL C
- is the programming language used to write compute kernels. Though based on C99, it is adapted to fit the device model.
A memory buffer resides in a specific level and its pointer is annotated with a region qualifier:
• There is no
• There are no function pointers, bit fields or variable-length arrays
• Recursion is forbidden
• stdlib is replaced by a custom set of standard functions, geared toward math programming
• Scalar types such as
Features:
• Vector types available in fixed-lengths of 2, 3, 4, 8 and 16; and for various base types e.g.
• Operations for vector types
• Synchronization facilities
• Functions to work with work-items and work-groups
• More specialized types incl. 2D and 3D image types
#OpenCL #OpenCL_C
- is a parallelism framework for writing programs that execute across heterogeneous platforms consisting of one host CPU and any number of compute devices. These devices include GPUs, CPUs with SIMD instructions, FPGAs, Movidius Myriad 2, Adapteva epiphany and DSPs.
A compute device is broken down to several compute units, which themselves are broken down to multiple PEs (processing elements). A single function execution can run on any number of PEs in parallel. How a compute device is subdivided into compute units and PEs is up to the vendor.
It defines an API for programs running on the host to launch functions on compute devices and manage device memory. This API is defined for C and C++, as well as third-parties such as #Python, #Java, #Perl, #DotNET, etc. A more recent, higher-level model is SYCL; which is purely based on C++11. Programs in OpenCL are compiled at run-time therefore its applications are portable between various host devices.
A four-level memory hierarchy is defined for the compute device:
• global: shared by all PEs, high access latency
__global
• read-only: smaller, low latency, writable only by the host __constant
• local: shared by a group of PEs __local
• per-element private memory: device registers; __private
Not every device needs to implement each level of this hierarchy in hardware. Consistency between the various levels in the hierarchy is relaxed, and only enforced by explicit synchronization constructs, notably barriers. The host provides handles on device memory buffers and functions to transfer data back and forth.OpenCL C
- is the programming language used to write compute kernels. Though based on C99, it is adapted to fit the device model.
A memory buffer resides in a specific level and its pointer is annotated with a region qualifier:
__global, __local, __constant, and __private
Comparison with #C:• There is no
main; functions are marked __kernel to signal that they are entry points, and are to be called from programs running on the host• There are no function pointers, bit fields or variable-length arrays
• Recursion is forbidden
• stdlib is replaced by a custom set of standard functions, geared toward math programming
• Scalar types such as
float and double behave similarly to those of CFeatures:
• Vector types available in fixed-lengths of 2, 3, 4, 8 and 16; and for various base types e.g.
float4 (4-vector of single-precision floats)• Operations for vector types
• Synchronization facilities
• Functions to work with work-items and work-groups
• More specialized types incl. 2D and 3D image types
#OpenCL #OpenCL_C