6.9 Revision of three languages

Abstract Data Types

An Abstract Data Type is a description of values and operations on those values, without defining the technical details on how those values are represented and how the operations work on those representations

Representation Invariant

Assume we have an abstract function, then every abstract value must have at least one concrete value

For example, we have abstract value \(\{1,2\}\), then we have \([1,2]\) or \([2,1]\) concrete value

Error example of linked list

They are incorrect

Thus to ensure the concrete value of abstract value are valid, we use repOk to filter valid concrete values

Genericity

The ability of defining programs whose manipulated data are of types to be defined (instantiated) when used.
Genericity allows us to avoid duplicating code.
Genericity is strongly related to abstraction (by parameterization), as it enables us to collapse different pieces of code by abstracting away the type of the manipulated data.

Advantages of using abstract datatypes.

Single ADT implementation and definition vs Multiple implementations and definitions.
Flexible reuse techniques vs Copy and Paste.
Simple namespace vs Repeating names with different tags related to different types.
Bugs occur in one implementation vs Bugs get replicated.
Only one implementation and definition to keep track vs multiple versions.
Focus on the how, and not the what (How you manipulate an abstract data type, and not on what that abstract data type has inside).

Abstraction by parameterization

What about parameterized behavior?
passing a function as a parameter to control the behavior of another function.

List filter(List list, ? accept) {
    List result = create_list();
    for (int i = 0; i < list_size(list); i++) {
        if (accept(elem_at(list, i))) {
            insert_elem(result, list_size(result), elem_at(list, i));
        }
    }
    return result;
}

Creates a new list from list, with only the values for which accept returns TRUE.

Expressions and types

A \(\textbf{type}\) defines a set of values and what operations can be performed and how. On a technical level, it determines the size of related values (how many bytes it will take to store a value), and how to store and interpret a value in memory (as bytes).

Every expression will have a type, how this types are checked and determined will depend on the language.

Functions/Methods

A function/method is a set of statements that, when called, perform a specific task.

How arguments are passed to a function will depend on the language, we will see this later.
All locally defined variables inside a function/method, will only live (be available) while the function/method is being executed. This can also be applied to classes. Although depending on the language, the values associated to these variables might still live but remain unreachable.

For example: The data in heap without deleting

Functions/Methods

A function is applied on a list of arguments, the only side effect a function can have is over global variables.

A method is applied to an object, and side effects can only affect the object's state, or static-variables that are reachable from the definition of the function.

Scopes: They define the reachability and lifecycle of symbols

We cannot use definition of D since it's out of scope

Java

Object Oriented Programming

In Java we have both primitive types (non-objects) and non-primitive types (objects). This distinction is ingrained in many Java features:

In Java anything must be part of a class, even if we only have static members.
In any class there is an implied variable this that mention the object in which a method in being invoked.
Primitive type values don't have member functions int x = 42; x.to_string(); ❌ ERROR! But they do have associated operators that can be applied to them.
Operators cannot be redefined or overloaded.
Genericity can only be used with Classes, i.e.: No List of int.

List<int> ints = new ArrayList<>();    // ❌ compile‐time error
List<Integer> ints = new ArrayList<>(); // ✅ OK

* Generic Arrays can only be created from specific types, no generic array creation is allowed.

private T[] items = new T[10];  // ❌ compile‐time error

* There is method overloading and overriding, the capacity to override a method is enabled by default.

In Java we can have at most one top level class per file, you can define internal classes. The top level class must have exactly the same name as the java file.

Functions cannot be passed as arguments, objects can, and one can use lambda functions as arguments, but underneath they are objects.

Universal Bytecode, specific Java Virtual Machines

In Java we compile Java code into Bytecode, this can be interpreted on any system, as long as there is a Java Virtual Machine (JVM) implemented for that system.

Java offers a Just In Time Compiler (JIT Compiler), that will compile some Bytecode into native code (not run by the interpreter) if some instructions are executed several times in the same fashion.

So java is interpreted language

Type checking

Java uses static type checking, this means that types will be verified during compilation time (when generating Bytecode). But there is still support for runtime type checking when, for example, making casts.

Here is a very simple example.

public class SimpleTypeCheck {
    public static void main(String[] args) {

        // We create an Object variable, but the actual thing inside is an Integer.
        Object myObject = 123; // 123 is an Integer

        // 1. The Planner (Compile-Time Check)
        // We tell the compiler: "Trust me, this object is a String."
        // The compiler looks at the variable's type, which is `Object`.
        // It thinks: "Well, an Object *could* be a String, so your plan is plausible."
        // The compiler approves the plan.
        // THIS LINE COMPILES WITHOUT ANY ERRORS.

        System.out.println("Code has compiled. The bouncer (JVM) is now checking...");

        // 2. The Bouncer (Runtime Check)
        // The program runs. The bouncer looks at the *actual* object.
        // The actual object's ID says "I am an Integer".
        // The bouncer says: "Whoa, you're not a String. You can't come in."
        // The program crashes here.
        String myString = (String) myObject; // <-- RUNTIME ERROR!

        // This line is never reached.
        System.out.println("Success! The string is: " + myString);
    }
}

What Happens When You Run It

The code compiles perfectly fine. But when you run it, you get an error like this:

Code has compiled. The bouncer (JVM) is now checking...
Exception in thread "main" java.lang.ClassCastException: class java.lang.Integer cannot be cast to class java.lang.String
        at SimpleTypeCheck.main(SimpleTypeCheck.java:21)

Summary

Static Check (Success): The compiler allowed (String) myObject because it was possible for an Object to hold a String.
Runtime Check (Failure): The JVM checked the actual object, found it was an Integer, and threw an error because an Integer can never be a String.

Python

Multiparadigm

In Python we have features associated with different programming paradigms, i.e.: procedural, object oriented, functional, etc. But in Python everything is an object with associated functions/methods. Even functions, classes, and modules are considered as objects, with fields and methods.

Dynamic type checking

In Python we do not specify the types for variables, arguments, and return types. The type of an expression is determined during runtime. Without using external libraries or frameworks, we have no type checking during compilation. During runtime type errors only occur if we try to apply a function or operator with a type that does not support those.

try:
    add_things(5, " world")
except TypeError as e:
    print(f"Something went wrong!")
    print(f"Error: {e}")

Error: unsupported operand type(s) for +: 'int' and 'str'

Dynamic type checking

Is not possible to add type restrictions

Since there is no Static Typing, there is no way to define type restrictions:

We cannot make a proper generic class, i.e.: a List of E and only E.
We cannot determine what type of values a function will take, or return.
Class fields cannot be restricted to specific types.

Prints “Hello World”, no state change occurs.

Uses bar, and foo definitions, prints the result foo(1, bar(2, 3)); the state is not modified

C++

Multiparadigm

In C++ we have features associated with different programming paradigms, i.e.: procedural, object oriented, functional, etc.

In C++ we don't only have function overloading and overriding, we can also override and overload operators.

Static type checking, and generics

In C++ types are checked during compilation time. Generics are provided by using templates, these create copies of a templated class, structure, variable, function, type, etc.

When a template is instantiated with a particular type, or types, a copy of that member is created by replacing the each typename in the template with the instantiated types.

template<typename T>
T add(int size, T neutral, T[] values) {
    T result = neutral;
    for (int i = 0; i < size; i++) {
        result = result + values[i];
    }
    return result;
}

int values[] = {1, 2, 3, 4, 5, 7, 8, 9};
int res = add<int>(10, 0, values);

int add(int size, int neutral, int[] values) {
    int result = neutral;
    for (int i = 0; i < size; i++) {
        result = result + values[i];
    }
    return result;
}

Templates do not offer restrictions by themselves

A template by themself do not offer any restriction on the type it is used to replace it. In this case it must be replaced with a type that allows the usage of the '+' operators.

template<typename T>
T add(int size, T neutral, T[] values) {
    T result = neutral;
    for (int i = 0; i < size; i++) {
        result = result + values[i];
    }
    return result;
}

We have seen three options:

Leave the compiler with the task of checking if we instantiate a template with the wrong type; or reading through the code to see what functions/methods/operators are required.

Exam Question Example:

What restriction do you want to add?

Ans: Two arguments of the same type, and this operation, method, or operator works on two variables and returns the same type.

For every operation or function a function/structure/class needs, we can add a concept for those restrictions.

template<typename T>
concept Addition = requires(T a, T b) {
    {a + b} -> std::same_as<T>;
};

template<Addition T>
T add(int size, T neutral, T[] values) {
    T result = neutral;
    for (int i = 0; i < size; i++) {
        result = result + values[i];
    }
    return result;
}

For every operation a function/structure/class needs, we can add a generic function.

template<typename T>
using t_add = T (*) (T, T);

template<typename T>
T add(int size, T neutral, T[] values, t_add<T> add_f) {
    T result = neutral;
    for (int i = 0; i < size; i++) {
        result = add_f(result, values[i]);
    }
    return result;
}

Metaprogramming

Templates not only allow us for generic classes, functions, and structures.

We can program using templates:

Templates are not the same as preprocessor directives.
Templates are resolved by the compiler, not the preprocessor#define ...
Templates are instances during compilation time depending on the arguments.
Once the executable is compiled, instances are already available without any extra steps.
All instances generated are also accessible.

#include <iostream>

template<unsigned int x>
struct Counter {
    static const int counter = 1 + (Counter<x - 1>::counter);
};

template<>
struct Counter<0> {
    static const int counter = 0;
};

int main() {
    std::cout << Counter<42>::counter << std::endl;
    return 0;
}

Difference

Interpreted vs Compiled language

Compiler: You then run a special program called a Compiler. The compiler's job is to:

Check for errors (like syntax mistakes or type mismatches).
Translate the entire program into a new file containing machine code.

Manual memory management vs Garbage collector

Manual:

We need to allocate and deallocate dynamic memory (heap) ourselves.
We can have memory leaks if we fail to correctly deallocate all memory.
Data Types (data + operations) MUST have some function to deallocate an instance.

Garbage collector:

Memory allocation is usually fully automatic.
We cannot have memory leaks, although we can have the garbage collector working overtime.
Data Types (data + operations) can have a function to release resources like opened files or connections.

Static vs Dynamic Typing

unsigned char is_prime(const unsigned int value) {
    int divisors = 1;
    for (int divisor = 2; divisor <= value; divisor++) {
        if (value % divisor == 0) {
            divisors++;
        }
    }
    return divisors == 2;
}

def is_prime(value):
    divisors = 0
    divisor = 1
    while divisor <= value:
        if value % divisor == 0:
            divisors += 1
        divisor += 1
    return divisors == 2

Definition before usage; Declaration before mention

Left Column:

This will run in Python, fail to compile in Java, fail to compile in C++

function foo(a : int) : int {
  if (a > 50) {
    return bar()
  }
  return 42
}

call foo with 1

Right Column:

This will run in Python, fail to compile in Java, compile but fail to link in C++

function bar() : int;
function foo(a : int) : int {
  if (a > 50) {
    return bar()
  }
  return 42
}

call foo with 1

The key difference between the two examples is:

Left column: Uses bar() without any prior declaration
Right column: Declares bar() with function bar() : int; before using it

Python Both examples run successfully because:

Python resolves function names at runtime, not compile time
Since foo(1) means a = 1, the condition a > 50 is false
The bar() call is never executed, so Python never needs to find the function
Python allows forward references and doesn't require explicit declarations

Java

Left column fails to compile: bar() is used without being declared anywhere
Right column also fails to compile: While bar() is declared, Java requires both declaration AND implementation. A declaration without implementation causes a compile error, not a link error

C++

Left column fails to compile: C++ requires functions to be declared before use (the "declaration before mention" principle)
Right column compiles but fails to link:
The declaration function bar() : int; satisfies the compiler's requirement
However, since bar() is never actually defined/implemented, the linker fails when trying to resolve the symbol (even though it's never called at runtime)

The Principle Explained

"Declaration before mention" means you must declare a function's signature before you can reference it in your code. This allows the compiler to:

Verify the function exists
Check parameter types and return types
Generate appropriate call code

"Definition before usage" would require the complete implementation to be available, which is more restrictive than just requiring a declaration.

The C++ approach (allowing declarations without definitions to compile) enables techniques like:

Header files with function prototypes
Separate compilation units
Forward declarations for mutually recursive functions

If a python file is named math.py, the module is called math.

If a python file is named math.py, the module is called math. And every definition d inside will be referred to as math.d

In Java, every Java file must have a root class, with the same name as the file

Memory management

Manual memory management

Garbage collection

Java vs Python vs C++

Java	Python	C++
Object Oriented	Multiparadigm	Multiparadigm
Automatic Memory Management (Garbage Collector)	Automatic Memory Management (Garbage Collector)	Semi-manual: objects created without new, will get deleted where their scope is left or the object holding a reference to those values gets destroyed.
Static Typing	Dynamic Typing	Static Typing
Genericity with generic classes	Duck Typing: "If an object has the methods and properties I need (if it 'quacks' and 'walks'), I don't care about its actual class or type. I'll treat it as if it were the type I expect."	Genericity via Templates
Declarations required before mention; Definitions required before usage.	Definitions required before usage	Declarations required before mention; Definitions required before usage.
Interpreted (using a compiled Bytecode)	Interpreted	Compiled

Comparison of Unique Features

C++ Unique Features

Compiled language
Your .cpp is turned directly into native machine code ahead of time
Manual Memory Management & Deterministic Destructors (RAII)
C++ relies on Resource Acquisition Is Initialization (RAII) rather than a garbage collector. Objects free their resources as soon as they go out of scope, giving developers precise, predictable control over resource cleanup.
(Neither Java nor Python expose direct RAII or deterministic destructors.)
Template Metaprogramming & Compile‑Time Polymorphism
C++ templates allow you to write code that generates code at compile time—performing computations and type resolutions before runtime. This results in zero‑overhead abstractions: generic containers, algorithms, or even domain‑specific compile‑time logic with no runtime cost.
(Java’s Generics are erased at runtime, and Python relies on dynamic typing.)
Multiple Inheritance
A single C++ class can inherit directly from multiple base classes. This provides fine‑grained composition of functionality (mixing several class hierarchies) without requiring interfaces or traits.
(Java forbids multiple implementation inheritance (interfaces only), and Python’s multiple inheritance is based on its dynamic type system rather than compile‑time class hierarchies.)
Operator Overloading
In C++, you can redefine how built‑in operators (e.g., +, -, *, ==) behave for your own types, making user‑defined types work “as if” they were built‑in.
(Java does not allow operator overloading at all; Python has operator overloading via special methods like __add__ , but it occurs at runtime.)
Direct Memory & Hardware Access
C++ lets you manipulate raw pointers, perform pointer arithmetic, and even access hardware registers or specific memory layouts. This makes it the go‑to choice for low‑level systems programming, embedded development, or performance‑critical code.
(Both Java and Python strictly abstract away raw memory access.)
Standard Template Library (STL)
While Java and Python have extensive standard libraries, C++’s STL is unique in that it’s built entirely on templates, offering container classes (e.g., std::vector, std::map) and algorithms (e.g., std::sort, std::binary_search) that are guaranteed to compile down to minimal, inlined code.
(Java’s collections and Python’s built‑ins are not zero‑cost abstractions nor resolved at compile time.)

Java Unique Features

Interpreted language

In Java we compile Java code into Bytecode, this can be interpreted on any system, as long as there is a Java Virtual Machine (JVM) implemented for that system.

Java offers a Just In Time Compiler (JIT Compiler), that will compile some Bytecode into native code (not run by the interpreter) if some instructions are executed several times in the same fashion. * Write Once, Run Anywhere (Bytecode Portability)
Java source compiles into platform‑neutral bytecode (.class files) that run on any device equipped with a Java Virtual Machine (JVM). You don’t need to recompile for different operating systems.
(C++ produces machine‑specific binaries; Python is interpreted but doesn’t produce JVM bytecode.) * Just‑In‑Time (JIT) Compiler
The JVM’s JIT dynamically translates Java bytecode into optimized machine code at runtime. This allows Java programs to approach native performance while preserving portability.
(C++ is natively compiled ahead of time; Python’s standard interpreter (CPython) does not use a JIT.) * Built‑In Multithreading Model
Java provides a mature, baked‑in threading API (java.lang.Thread, java.util.concurrent) with high‑level constructs (executors, thread pools, locks, atomic variables), plus a well-defined memory model.
(Python has the GIL (Global Interpreter Lock) which limits true parallel CPU–bound threads; C++ leaves threading entirely to libraries or OS APIs.) * Checked Exceptions & Robust Exception Handling
Java enforces compile‑time checks for certain exceptions (checked exceptions), requiring you to declare or handle them. Its try‑catch‑finally mechanism is more rigorous than Python’s or C++’s exception systems.
(C++ exceptions are unchecked; Python has exceptions but no compile‑time enforcement.) * Dynamic Class Loading & Reflection API
Java can load classes on demand at runtime (Class.forName(...)), inspect methods/fields, and even modify them via reflection. This underpins many frameworks (e.g., Spring).
(Python supports runtime introspection but via its own dynamic typing; C++ has no built‑in reflection at runtime.) * Built‑In Distributed Computing Support
Java natively supports RMI (Remote Method Invocation), CORBA, and Web Services APIs, making it straightforward to build distributed applications without third‑party libraries.
(Neither C++ nor Python include a standardized, language‑level distributed‑object system.) * Security through Omission of Pointers
By design, Java disallows raw pointers. All memory access goes through managed references, preventing buffer‑overflows or arbitrary pointer arithmetic. Its strong type system, sandboxing, and security manager add layers of protection.
(C++ exposes raw pointers; Python delegates memory safety to its interpreter but allows certain C extensions that can be unsafe.)

Python Unique Features

Interpreted, Interactive Shell (REPL)
Python code is executed line by line without an explicit compilation step. Its built‑in REPL lets you experiment, test snippets, and debug on the fly.

“Interpreted” (in practice CPython compiles your .py to bytecode, then a VM interprets that bytecode)
(C++ always requires compilation; Java’s REPL (jshell ) is more recent and less universally used.) * Indentation‑Based Syntax & Emphasis on Readability
Python uses whitespace (indentation) to denote code blocks instead of braces or keywords. This enforces a clean, uniform style that many find easier to read and maintain.
(Neither C++ nor Java enforce indentation; both rely on braces.) * Dynamic Typing & Duck Typing
You don’t declare variable types explicitly in Python. Types are determined at runtime, and an object is used based on its behavior (“if it quacks like a duck, it’s a duck”).
(C++ is statically typed; Java has compile‑time type checking with generics. Neither supports Python’s level of duck typing.) * First‑Class Multi‑Paradigm Support
Although C++ and Java allow procedural or object‑oriented code, Python’s syntax and built‑in functions directly support functional programming (e.g., map, filter, lambdas), procedural scripts, and OOP without ceremony.
(Java only more recently added lambdas; C++ supports functional constructs via the STL and lambdas, but Python’s approach is more idiomatic and pervasive.) * Rapid Prototyping via Extensive Standard Library (Batteries Included)
Python’s “batteries included” philosophy means there are built‑in modules for everything from web servers (http.server) and file I/O to unit testing and data serialization (json, csv, sqlite3), allowing developers to build prototypes extremely quickly.
(Java’s standard library is large but more verbose; C++’s STL focuses on containers/algorithms rather than high‑level services.) * Easy Integration with C/C++/Java (Extension Modules & Wrappers)
Python can embed or extend C/C++ modules (via CPython extensions) or call Java code (via Jython), letting you accelerate performance‑critical sections in native code while leaving the rest in Python.
(Java interoperates with native code via JNI, but not as seamlessly as Python’s C extensions; C++ can call C libraries but not Python natively.)

‍