My Computer Science Vocabulary Page

Introduction
Too often I have “problems” with computer science vocabulary. In addition, there is always something new I learn along my readings/viewings on the Web. So, I decided to start this page.
Usually Googling helps a lot to get an “answer” at the speed of light. On the other hand, working on this page, adding words, taking the time to read, copy/paste, write, summarize what I understood help me a lot.
How does it works?
- This is mostly for me
- This is done mostly in a C++ context
- There is no goal of completeness (how could it be?)
- Entries are in alphabetical order
- Whenever possible I add the sources, links and references
- Some entries are and remains empty. This act as a reminder. Feel free to help, sharing a source of information in the comments
Table of Contents
- Algorithm
- Arguments and Parameters
- Amdahl’s law
- Concurrency
- Dependency Injection Framework
- DRY
- Expressions
- Fiber
- Function, Method, Procedure
- Framework
- Heuristic
- Initialization vs copy vs assignments
- Introspection
- Invariant
- KISS
- Literals
- Parallelism
- Parameters and Arguments
- POD (Plain Old Data)
- Pointer dereferencing
- Predicates
- Programming idioms
- Reflexion
- Semantic
- Serialisation (object serialization)
- SFINAE
- SOLID
- Statement
- Strength reduction
- Syntax (difference between syntax and semantic)
- Tasks
- Threads
Algorithm
[Knuth,1968] A finite set of rules which gives a sequence of operations for solving a specific set of problems [and] has five important features:
- Finiteness
- Definiteness
- Input
- Output
- Effectiveness
In the context of the C++ standard library, an algorithm is a function template operating on sequences of elements.
Arguments and Parameters
void MyFunction(int i, double d){
// ...
}
void main(){
int MyInt = 1;
MyFunction(MyInt, 42.0);
}
i
andd
are parameters. They are part of the definition of the function. They are part of the function signature.MyInt
and42
are arguments. Let’s keep in mind that : “The arguments are given”
Moyen mnémotechnique en Français :
- Arguments, Appel de la fonction
- Paramètres, Prototype de la fonction
Mnemoni in English
- Arguments are Actuals
- Parameters are Placeholders
Amdahl’s law
The speedup of a program using multiple processors in parallel computing is limited by the time needed for the sequential fraction of the program.
For example, if a program needs 20 hours using a single processor core, and a particular portion of the program which takes one hour to execute cannot be parallelized, while the remaining 19 hours (95%) of execution time can be parallelized, then regardless of how many processors are devoted to a parallelized execution of this program, the minimum execution time cannot be less than that critical one hour. Hence the speedup is limited to at most 20×.
http://en.m.wikipedia.org/wiki/Amdahl’s_law
Concurrency
When tasks start, run and complete in overlapping time periods.
Task can be seen as a function. I can have concurrency even if I have a sigle thread of execution (this can be achieve with time slicing the thread, cooperative threading model or breaking up tasks and requeuing the tasks)
Concurrency is the basic building block that allow to get to parallelism. Also improve interactivity.
See : Parallelism, Tasks
See : https://www.youtube.com/watch?v=QIHy8pXbneI at 6:30
Dependency Injection Framework
See : https://stackoverflow.com/questions/130794/what-is-dependency-injection
In French
Design principle qui consiste à fournir à un objet ses dépendances plutôt que de les créer lui-même. Au lieu qu’une classe crée les objets dont elle a besoin, on les lui injecte de l’extérieur. Ça permet :
- de réduire le couplage entre les classes,
- de faciliter les tests (ex : en injectant des mocks),
- de favoriser la réutilisation et la maintenance du code.
# This is the service that fetches data
class DataFetcher:
def fetch(self) -> str:
# In a real app, this could fetch data from an API or database
return "some important data"
# This class depends on DataFetcher
class ReportGenerator:
def __init__(self, fetcher: DataFetcher):
# The dependency is injected via the constructor
self.fetcher = fetcher
def generate(self) -> str:
# Uses the injected dependency
data = self.fetcher.fetch()
return f"Report based on: {data}"
# We create the dependency manually and inject it
data_fetcher = DataFetcher()
report_generator = ReportGenerator(data_fetcher)
# Use the class with the injected dependency
print(report_generator.generate())
Exemple, par exemple en test, de remplacement de la “vraie” dépendance par une version simulée (mock).
# A fake DataFetcher for testing
class FakeDataFetcher:
def fetch(self) -> str:
return "test data"
# Inject the fake fetcher
test_fetcher = FakeDataFetcher()
test_generator = ReportGenerator(test_fetcher)
assert test_generator.generate() == "Report based on: test data"
DRY
Don’t repeat yourself
Expressions
- If an instruction or a set of instructions evaluate to a single value this is an expression otherwise it is a statement
- Are made up of Operators and Operands.
- Are made of Operators and Values (literals or variable)
In French
- Une expression est évaluée pour retourner un résultat
- Une expression est une combinaison de valeurs, de variables, d’opérateurs et de fonctions qui produit une valeur
- L’ensemble des expressions est inclus dans l’ensemble des instructions (statements)
US | FR | Note |
---|---|---|
Statement | Instruction | exécute une action sans renvoyer nécessairement une valeur |
Expression | Expression | évaluée pour donner une valeur |
Fiber
Function, Method, Procedure
Function : Reusable block of code that returns a value.
Method : Function associated with an object (or class). It is called via an instance or the class. Acts on the object’s internal data or interacts with its attributes.
Precedure : Reusable block of code that returns no value (or implicitly returns void or None). Performs an action (e.g. display a message, modify a file, etc.).
// Rust sample code
// Function: returns the square of a number
fn square(x: i32) -> i32 {
x * x
}
// Struct: simple representation of a rectangle
struct Rectangle {
width: u32,
height: u32,
}
// Method: defined on Rectangle, calculates its area
impl Rectangle {
fn area(&self) -> u32 {
self.width * self.height
}
}
// Procedure: prints a greeting message (no return value)
fn greet(name: &str) {
println!("Hello, {}!", name);
}
fn main() {
// Using the function
let val = 5;
let sq = square(val);
println!("The square of {} is {}", val, sq);
// Using the method
let rect = Rectangle { width: 10, height: 5 };
println!("The area of the rectangle is {}", rect.area());
// Using the procedure
greet("Philippe");
}
Framework
Frameworks are distinct from libs :
- Inversion of control : With lib the application use the lib functions. The flow goes from the app code to the lib. With framework this is the opposite. The overall program’s flow of control is dictated by the framework (not the app).
- Users can extend frameworks not libs
- Users can extend frameworks but should not modify their core.
Heuristic
Example : I used to use reserve()
to try to improve performance, but that turned out to be a waste of effort: The heuristic used by vector is better than my guesses, so now I only use reserve()
to avoid reallocation of elements when I want to use pointers to elements.
Wikipedia : refers to experience-based techniques for problem solving, learning, and discovery that find a solution which is not guaranteed to be optimal, but good enough for a given set of goals. More precisely, heuristics are strategies using readily accessible, though loosely applicable, information to control problem solving in human beings and machines.
Initialization vs copy vs assignments
Concept | Quand est-ce utilisé ? | Fonction appelée | Signature typique |
---|---|---|---|
Initialisation | Lors de la création d’une nouvelle variable. Create and initialize simultaneously. | Constructeur | MyClass(int val) ou MyClass() |
Copie (initialisation) | Lors de la création d’un objet à partir d’un autre objet existant. | Constructeur de copie | MyClass(const MyClass &other) |
Affectation | Lorsqu’un objet existant reçoit une nouvelle valeur d’un autre objet existant. | Opérateur d’affectation | MyClass& operator=(const MyClass &other) |
#include <iostream>
#include <string>
#include <vector>
void demo_initialization(void){
// Default Initialization
int x; // x is not initialized
std::cout << x << std::endl;
int y{}; // y is initialized to 0
// Direct Initialization
int a(10); // a is initialized to 10
std::string s("Hello"); // s is initialized to "Hello"
// Copy Initialization
int b = 20; // b is initialized to 20
std::string t = "World"; // t is initialized to "World"
// List Initialization, Uniform Initialization
// To be preferred avoid implicit conversions
int c{30}; // c is initialized to 30
std::vector<int> vec{1, 2, 3}; // vec is initialized to {1, 2, 3}
}
// Copy Constructor
// Happen when an object is created based on another object of the same class
void demo_copy(void){
class MyClass {
public:
int x;
MyClass(int val) : x(val) {} // default constructor
MyClass(const MyClass &other) : x(other.x) {} // copy constructor
};
MyClass obj1(10);
MyClass obj2(obj1); // use the copy constructor
MyClass obj3 = obj1; // implicit call to the copy constructor
}
// Affectation in french
void demo_assignment(void){
class MyClass {
public:
int x;
MyClass(int val) : x(val) {}
MyClass& operator=(const MyClass &other) {
if (this != &other) { // avoid self-assignment
x = other.x;
}
return *this;
}
};
MyClass obj1(10);
MyClass obj2(20);
obj2 = obj1; // use the assignment (=) operator
}
int main() {
demo_initialization();
demo_copy();
demo_assignment();
}
Introspection
Usage?
Invariant
Something that remains constant during the execution of an algorithm, a loop, or in the state of an object.
It is a logical property or condition that :
- is true before a block of code is executed,
- is always true during execution,
- remains true afterwards.
Use assert
to check the invariants. See also Boost.Contract (C++) and icontract
in Python (never used).
Invariant helps:
- Checking for correctness : to prove that an algorithm or class works as expected.
- Reasoning tools : to understand the code, especially in complex algorithms.
- Debugging and validation : use assertions to check invariants.
- Safe refactoring : we can modify the code while ensuring that it still complies with the operating rules (invariant remains the same)
- Simpler tests : a test can be limited to checking that invariants are respected. This reduces the number of error cases.
Loop invariant
This is a property that is true before each iteration of a loop. It allows to
- reason about the correctness of an algorithm,
- demonstrate that a loop does what it is supposed to do.
Sample code where at each iteration, max_val
contains the maximum already observed. This invariant helps to understand that the algorithm is correct.
# Goal: Find the maximum value in a list
def find_max(lst):
assert len(lst) > 0
max_val = lst[0]
for i in range(1, len(lst)):
# Invariant: max_val is the maximum of lst[0:i]
if lst[i] > max_val:
max_val = lst[i]
return max_val
Class or structure invariant
This is a condition that is always true for a valid object after its construction and after each public method.
Sample code where the invariant is that width
and height
are always strictly positive. This contract guarantees that all methods can function assuming the dimensions are valid.
class Rectangle {
private:
int width;
int height;
public:
Rectangle(int w, int h) : width(w), height(h) {
assert(w > 0 && h > 0); // Class invariant: dimensions must be positive
}
int area() const {
return width * height;
}
};
KISS
Keep it simple stupid. Ne complique pas les choses.
Literals
- A string literal is a sequence of characters surrounded by double quotes.
- A literal is a constant: string literals, numeric literals etc.
- A literal is a notation for representing a fixed value in source code (https://en.wikipedia.org/wiki/Literal_(computer_programming))
Parallelism
- When two or more tasks execute simultaneously
- See: Concurrency https://youtu.be/QIHy8pXbneI?t=385
Parameters and Arguments
POD (Plain Old Data)
POD type is a scalar or a POD class with
- no user defined constructors or destructor,
- no user defined copy assignment operator,
- no base classes or virtual functions,
- no private or protected non-static data
- no static data that is non-POD types)
Pointer dereferencing
- A variable (such as number) directly references a value,
- whereas a pointer indirectly references a value through the memory address it stores
- Referencing a value indirectly via a pointer (*ptr) is called indirection or dereferencing.
Predicates
A function that returns true or false Read this page.
Programming idioms
- Simple Factory
- RAII
- PIMPL
Reflexion
The ability of some programming languages to inspect type and code information at runtime and modify it. Could be another type of metaprogramming.
Semantic
- Example : What is common for all iterators is their semantics and the naming of their operations. However, when you really need the semantics of pointers, unique_ptr is a very lightweight mechanism with no space or time overhead compared to correct use of a built-in pointer.
- http://web.archive.org/ : It’s the meaning of the language elements in terms of what they formally mean in terms of computation. This means that it expresses what a term of your language effectively does assuming an underlying kind of model that depends on which semantic we are talking about.
- Semantics is concerned with the interpretation or understanding of programs and how to predict the outcome of program execution. The semantics of a programming language describe the relation between the syntax and the model of computation. Semantics can be thought of as a function which maps syntactical constructs to the computational model. (http://web.archive.org/web/20040410154109/cs.wwc.edu/~aabyan/PLBook/HTML/Semantics.html)
Serialisation (object serialization)
See Python Pickle
SFINAE
- Substitution failure is not an error
A C++ compiler rule that applies when resolving templates. It allows to exclude certain function overloads or template specializations if type substitution fails, without generating a compiler error.
When one write a function or a template class, the compiler tries to substitute the types passed as parameters. If this substitution fails, instead of crashing with an error, the compiler ignores this version and tries the others (if any). It is this mechanism that enables conditional overloading based on types.
#include <iostream>
#include <type_traits>
// Version activée si T est un entier
template<typename T>
typename std::enable_if<std::is_integral<T>::value>::type
print_type(T val) {
std::cout << "Integer: " << val << std::endl;
}
// Version activée si T est un flottant
template<typename T>
typename std::enable_if<std::is_floating_point<T>::value>::type
print_type(T val) {
std::cout << "Floating-point: " << val << std::endl;
}
print_type(42); // Integer: 42
print_type(3.14); // Floating-point: 3.14
std::enable_if
is used to enable or disable a template function according to type. If the condition is false
, the substitution fails, but this is not an error thanks to SFINAE.
See : std::enable_if
, std::is_same
, std::is_integral
, std::is_floating_point
, decltype(...)
etc.
Here below the code detects at compile time whether a t
object has a foo()
method (useful for template introspection).
template<typename T>
auto has_foo(T t) -> decltype(t.foo(), std::true_type{}) {
return std::true_type{};
}
std::false_type has_foo(...) {
return std::false_type{};
}
Since C++20 use concepts instead
#include <iostream>
#include <vector>
#include <list>
#include <type_traits> // For std::size_t
// Define a concept that checks if a type T has a size() method returning something convertible to std::size_t
template<typename T>
concept HasSize = requires(T t) {
{ t.size() } -> std::convertible_to<std::size_t>;
};
// Only accepts types satisfying the HasSize concept
template<HasSize T>
void print_size(const T& t) {
std::cout << "Size: " << t.size() << std::endl;
}
// A class with size() method
class MyContainer {
public:
std::size_t size() const { return 42; }
};
// A class without size() method
class NoSizeClass {
public:
void dummy() {}
};
int main() {
std::vector<int> v{1, 2, 3};
std::list<std::string> l{"a", "b", "c"};
MyContainer c;
print_size(v); // OK: std::vector has size()
print_size(l); // OK: std::list has size()
print_size(c); // OK: MyContainer has size()
// NoSizeClass n;
// print_size(n); // ❌ Compilation error: NoSizeClass does not satisfy HasSize
return 0;
}
- https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error
- http://en.cppreference.com/w/cpp/language/sfinae
SOLID
https://en.wikipedia.org/wiki/SOLID_(object-oriented_design)
- S ingle responsibility : Classes should have only one responsibility.
- O pen–closed : Software compoenent should be open for extension, but closed for modification. New features can be added without modifying existing code.
- L iskov substitution : Polymorphism. Functions using objects of base classes must be able to use objects of derived classes without knowing it
- I nterface segregation : Decoupling, reduces dependencies between classes (modular & maintenable code). Clients should not be forced to depend upon interfaces that they do not use
- D ependency inversion : Depend on abstractions, not concretes implementations. Enables changes to implementations without affecting clients
Statement
- Statements are made up of expressions
- If an instruction or a set of instructions evaluate to a single value this is an expression otherwise it is a statement
- Example :
In C++, in the if statement, the braces ['{', '}'] are not mandatory, but parentheses ['(', ')'] around the expression being tested are
. Belowbob > 3
is an expression and the are twoif
statements.
#include <iostream>
int main(){
auto bob = 42;
if (bob > 1) {
std::cout << "bob larger than 4\n";
}
if (bob > 3) std::cout << "bob larger than 3\n";
}
In French
- Une instruction est une ligne de code qui exécute une action, mais qui ne renvoie pas nécessairement une valeur.
- Elles sont formées d’une combinaison de littéraux, d’identifiants et d’opérateurs.
- Caractéristique principale : fait quelque chose, mais ne renvoie pas directement de valeur.
- Contrairement aux expressions, les instructions ne renvoient pas directement de valeur. Elles modifient l’état du programme (par exemple, en affectant une variable, en imprimant du texte, ou en contrôlant le flux d’exécution).
- Contrairement à d’autres langages (comme JavaScript ou C), en Python l’affectation est une instruction et non une expression, donc elle ne retourne pas de valeur.
x = 5 # Instruction d'affectation, ne retourne rien
y = (x = 5) # ❌ Erreur : l'affectation n'est pas une expression en Python !
US | FR | Note |
---|---|---|
Statement | Instruction | exécute une action sans renvoyer nécessairement une valeur |
Expression | Expression | évaluée pour donner une valeur |
Strength reduction
- See From Mathematics to Generic Programming p 26
- ISBN-10: 0321942043
- Code optimization
- In loop, replace complex multiplications with “lite” additions
- Need to evaluate the \(\delta\) between 2 loops
Example 1 :
Replace
for i in range(10):
x = i * 8 # Multiplication at each iteration
print(x)
with
x = 0
for i in range(10):
print(x)
x += 8 # Lite addition
Example 2 :
Replace this code full of multiplications
i += 1
factor = i+i+3
index_square = 2 * i * (i + 3) + 3
With this code with additions
i += 1
index_square += factor # index_square = factor(i)
factor += 2 # factor(i+1) = factor(i) + 2
index_square += factor # index_square = factor(i) + factor(i+1)
Because in the case above one can easily demonstrate that :
factor(i+1) = factor (i) + 2
index_square(i+1) = factor (i) + factor(i+1)
Syntax (difference between syntax and semantic)
Syntax is about the structure or the grammar of the language. It answers the question: how do I construct a valid sentence? All languages, even English and other human (aka “natural”) languages have grammars, that is, rules that define whether or not the sentence is properly constructed.
Here are some C language syntax rules:
- separate statements with a semi-colon
- enclose the conditional expression of an IF statement inside parentheses
- group multiple statements into a single statement by enclosing in curly braces
- data types and variables must be declared before the first executable statement (this feature has been dropped in C99. C99 and latter allow mixed type declarations.)
Semantics is about the meaning of the sentence. It answers the questions: is this sentence valid? If so, what does the sentence mean? For example:
x++; // increment
foo(xyz, --b, &qrs); // call foo
Are syntactically valid C statements. But what do they mean? Is it even valid to attempt to transform these statements into an executable sequence of instructions? These questions are at the heart of semantics.
Consider the ++ operator in the first statement. First of all, is it even valid to attempt this?
- If x is a float data type, this statement has no meaning (according to the C language rules) and thus it is an error even though the statement is syntactically correct.
- If x is a pointer to some data type, the meaning of the statement is to “add sizeof(some data type) to the value at address x and store the result into the location at address x”.
- If x is a scalar, the meaning of the statement is “add one to the value at address x and store the result into the location at address x”.
Finally, note that some semantics cannot be determined at compile-time and must therefore must be evaluated at run-time. In the ++ operator example, if x is already at the maximum value for its data type, what happens when you try to add 1 to it? Another example: what happens if your program attempts to dereference a pointer whose value is NULL?
In summary, syntax is the concept that concerns itself only whether or not the sentence is valid for the grammar of the language . Semantics is about whether or not the sentence has a valid meaning.
Tasks
A unit of work, often a function, to be executed on a thread.
See : https://www.youtube.com/watch?v=QIHy8pXbneI at 18:15
We call a computation that can potentially be executed concurrently with other computations a task.
Threads
Execution environment consisting of a stack and processor state running in parallel to other threads.
See : https://www.youtube.com/watch?v=QIHy8pXbneI at 18:15
A thread is the system-level representation of a task in a program.
Threads of a program share a single address space. In this, threads differ from processes, which generally do not directly share data. Since threads share an address space, they can communicate through shared objects (§13.5). Such communication is typically controlled by locks or other mechanisms to prevent data races (uncontrolled concurrent access to a variable).
We call a computation that can potentially be executed concurrently with other computations a task. A thread is the system-level representation of a task in a program. A task to be executed concurrently with other tasks is launched by constructing a std::thread (found in