2023 Exam A

QUESTION 1

In the following pseudo-codes, explain for each one what the behavior would be for each of the following contexts:

• In a compiled language like \(Java\) where we need to compile and execute the code.

• In an interpreted language like \(Python\) when we just run the code with the interpreter.

• Pseudo-code A

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

call foo with 1

1. Pseudo-code B

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

call foo with 63

1. Pseudo-code C

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

call foo with 1

Pseudo-code A

In a Compiled Language (like C++)

Result: Compilation Error

• The compiler performs static analysis of the entire code before execution
• It will detect that bar() is referenced but never declared/defined
• Error occurs at compile time, preventing the program from being built
• The program never gets to run, even though the execution path wouldn't actually call bar()​

In an Interpreted Language (like Python)

Result: Successful Execution, returns 42

• The interpreter only checks for function existence when the function is actually called
• Since foo(1) evaluates the condition 1 > 50 as false, the bar() call is never reached
• The function successfully returns 42
• No error occurs because the undefined function is never invoked

Pseudo-code B

In a Compiled Language (like C++)

Result: Linker Error

• The compiler accepts the forward declaration of bar()​
• Compilation succeeds because bar() is properly declared
• However, during the linking phase, the linker cannot find the implementation of bar()​
• Error occurs at link time: "undefined reference to bar()"
• The program fails to build

In an Interpreted Language (like Python)

Result: Runtime Error

• The code starts executing successfully
• ​foo(63) is called, and since 63 > 50 is true, it attempts to call bar()​
• Runtime error occurs: "NameError: name 'bar' is not defined" (Python) or similar
• The program crashes at the point where bar() is called

Pseudo-code C

In a Compiled Language (like C++)

Result: Compilation Error

• The compiler performs static analysis and detects that bar() is referenced in the function body
• The line function bar() : int; appears to be a declaration attempt, but the syntax is unclear/invalid
• Error occurs at compile time due to undefined reference to bar()​
• The program fails to compile, even though bar() would never be called with argument 1

In an Interpreted Language (like Python)

Result: Successful Execution, returns 42

• The interpreter only evaluates function calls when they are executed
• Since foo(1) evaluates the condition 1 > 50 as false, the bar() call is never reached
• The function successfully returns 42
• No error occurs because the undefined function is never invoked

Summary

Pseudo-code	Compiled Language	Interpreted Language
A	❌ Compile-time error	✅ Runs successfully (returns 42)
B	❌ Link-time error	❌ Runtime error
C	❌ Compile-time error	✅ Runs successfully (returns 42)

The key difference is when the error detection occurs:

• Compiled languages catch undefined references early (compile/link time)
• Interpreted languages only catch errors when the problematic code is actually executed

QUESTION 2

25pts. Implement a function \(\text{index\_of}\) in JAVA, Python, and C++ with the following restrictions:

1. Function \(\text{index\_of}\) takes an array or a list, you can choose a different collection for each language, and an element to search.

2. The collection and element on which \(\text{index\_of}\) operates can be empty but it cannot be NULL or None.

3. The function must be generic, it must work with any type for the collection's values and element.

4. You can add arguments to the function if you need them, e.g.: a \(\text{size}\) argument if you are using an array in either C or C++.

5. Function \(\text{index\_of}\) must return the first index \(\text{i}\) such that \(\text{collection[i]}\) is equal to the \(\text{searched element}\); or -1 if the searched value does not exist in the collection; this makes comparing addresses and invalid solution.

For each implementation you need to explain advantages and disadvantages.

Java

public class IndexOf {

    // Generic method that works with any type T
    public static <T> int indexOf(T[] values, T element) {
        // Check for null array (requirement: cannot be NULL)
        if (values == null) {
            throw new IllegalArgumentException("Array cannot be null");
        }

        for (int i = 0; i < values.length; i++) {
            // Handle null elements properly
            if (values[i] == null && element == null) {
                return i;
            }
            if (values[i] != null && values[i].equals(element)) {
                return i;
            }
        }
        return -1;
    }

Python

def index_of(values, value):
    i = 0
    for current_value in values:
        if current_value == value:
            return i
        i = i + 1
    return -1

if __name__ == "__main__":
    values = [0, 1, 2, 3, 4, 5, 6, 7]
    value = 3
    print("The index of {} in {} is {}".format(value, values, index_of(values, value)))

C++

#include <iostream>
#include <concepts>

template <typename T>
concept Comparable = requires(T a, T b) {
    { a.compares_to(b) } -> std::same_as<int>;
};

class Integer {
private:
    int value;
public:
    Integer() : value(0) {} 
    Integer(int value): value(value) {}
    int compares_to(Integer other) {
        return value - other.value;
    }
};

template<Comparable T>
int comparing(T a, T b) {
    return a.compares_to(b);
}

template <Comparable T>
int index_of(const int size, T values[], T elem) {
    for (int i = 0; i < size; i++) {
        if (values[i].compares_to(elem) == 0) {
            return i;
        }
    }
    return -1;
}

int main() {
    int size = 10;
    Integer pvalues[size];
    for (int i = 0; i < size; i++) {
        pvalues[i] = Integer(i);
    }
    Integer value_to_search = Integer(7);
    std::cout << "Index of Integer 7 is : " << index_of(size, pvalues, value_to_search) << std::endl;

    return 0;
}

Analysis of Advantages and Disadvantages

Java

Advantages:

• Type Safety: Generics provide compile-time type checking, preventing ClassCastException at runtime
• Automatic Boxing/Unboxing: Works seamlessly with both primitive wrapper types and objects
• Object-oriented: Uses .equals() method which allows custom equality logic for complex objects
• Memory Management: Automatic garbage collection handles memory cleanup
• Null Safety: Explicit null handling prevents NullPointerException
• Collections Framework: Can easily work with various collection types (Array, List, Set, etc.)

Disadvantages:

• Performance Overhead: Generics use type erasure, which can cause some runtime overhead
• Verbosity: More verbose syntax compared to other languages
• Wrapper Objects: Autoboxing creates wrapper objects for primitives, adding memory overhead
• JVM Dependency: Requires Java Virtual Machine to run

Python

Advantages:

• Simplicity: Clean, readable syntax with minimal boilerplate
• Dynamic Typing: Works with any type without explicit type declarations
• Flexibility: Can handle any iterable (lists, tuples, strings, etc.)
• Duck Typing: Uses == operator which works with any objects that implement __eq__​
• No Memory Management: Automatic garbage collection
• Interactive Development: Great for rapid prototyping and testing

Disadvantages:

• No Type Safety: No compile-time type checking, errors only discovered at runtime
• Performance: Slower execution due to interpreted nature and dynamic typing
• Runtime Errors: Type-related errors only surface when the code is executed
• Memory Usage: Objects have more overhead compared to statically typed languages

C++

Advantages:

• Performance: Compiled to native machine code, very fast execution
• Memory Control: Direct memory management and stack allocation possible
• Template System: Powerful template metaprogramming capabilities
• Concepts (C++20) : Provides compile-time constraints on template parameters
• Zero-cost Abstractions: Generics/templates have no runtime overhead
• Type Safety: Strong compile-time type checking

Disadvantages:

• Complexity: More complex syntax, especially with templates and concepts
• Manual Memory Management: Need to manage memory explicitly (though not required here)
• Compilation Time: Template instantiation can slow down compilation
• Custom Comparison: Requires custom compares_to method instead of standard operators
• Concept Constraint: The current implementation is overly restrictive - requires a specific compares_to method rather than using standard equality operators
• Learning Curve: Harder to learn and master compared to Java or Python

QUESTION 4

\(10pts\). Considering java, python, C++

1. Provide an input that will break the preprocessor.

2. Provide an input of syntactically and grammatically correct code that breaks the compilation step. This means that you can't use an input that is just gibberish.

3. Provide an input that breaks the linking step but do not break any previous step.

Explain in every case why the error occurs.

1. Breaking the Preprocessor

This primarily applies to C++ (Java and Python don't have traditional preprocessors):

// File: main.cpp
#include "header1.h"

int main() {
    return 0;
}

// File: header1.h
#ifndef HEADER1_H
#define HEADER1_H
#include "header2.h"
#endif

// File: header2.h
#ifndef HEADER2_H
#define HEADER2_H
#include "header1.h"  // Circular dependency
#endif

Why this breaks the preprocessor:
The preprocessor gets stuck in an infinite loop trying to resolve circular includes. Even though the include guards prevent infinite text expansion, the preprocessor still needs to process the dependencies and can fail if the circular dependency creates unresolvable symbol requirements.

Alternative preprocessor-breaking example:

#define MACRO(x) MACRO(x)  // Infinite macro expansion
int main() {
    MACRO(5);
    return 0;
}

2. Breaking the Compilation Step (Syntactically/Grammatically Correct but Semantically Wrong)

C++:

#include <iostream>

class MyClass {
private:
    int value;
public:
    MyClass(int v) : value(v) {}
};

int main() {
    MyClass obj;  // Error: no default constructor
    return 0;
}

Why this breaks compilation:
The code is syntactically correct - all brackets match, semicolons are in place, keywords are used properly. However, it's semantically incorrect because MyClass only has a parameterized constructor, but we're trying to create an object without providing arguments.

Java:

public class CompilationError {
    public static void main(String[] args) {
        final int x;
        System.out.println(x);  // Error: variable x might not have been initialized
    }
}

Why this breaks compilation:
The syntax is perfect, but Java's definite assignment analysis determines that the final variable x is used before being definitely assigned a value.

Python:

def my_function():
    return x  # Error: local variable 'x' referenced before assignment

def another_function():
    print(x)
    x = 5  # This makes x local, but it's used before assignment

my_function()

Why this breaks compilation/interpretation:
Python's parser and compiler can detect that x is assigned later in the function, making it a local variable, but it's referenced before assignment. This is caught during the compilation phase to bytecode.

3. Breaking the Linking Step

C++:

// File: main.cpp
#include <iostream>

// Function declaration (prototype) - this is syntactically correct
int calculate(int a, int b);

int main() {
    std::cout << calculate(5, 3) << std::endl;
    return 0;
}

// No definition provided for calculate() function
// This will compile but fail at linking stage

Why this breaks linking:
The code compiles successfully because the function is properly declared. However, during linking, the linker cannot find the actual implementation/definition of the calculate function, resulting in an "undefined reference" error.

Java:

// File: Main.java
public class Main {
    public static void main(String[] args) {
        MissingClass obj = new MissingClass();  // References a class that doesn't exist
        obj.doSomething();
    }
}

Why this breaks at runtime (Java's equivalent of linking):
The code might compile if MissingClass was available during compilation but then the .class file was deleted. At runtime, when the JVM tries to load the class, it will throw a ClassNotFoundException or NoClassDefFoundError.

Better Java linking example:

// File: Main.java - compiles successfully
public class Main {
    public static void main(String[] args) {
        Helper.missingMethod();  // Method exists during compilation
    }
}

// File: Helper.java - compiled with this method, then method is removed and recompiled
public class Helper {
    // Method was: public static void missingMethod() { }
    // But now it's removed and Helper.class is recompiled without Main.class
}

Python:

# File: main.py
import missing_module  # Module doesn't exist

def main():
    missing_module.some_function()

if __name__ == "__main__":
    main()

Why this breaks at runtime (Python's equivalent of linking):
Python will fail when it tries to import the missing module, throwing a ModuleNotFoundError. This happens at runtime when the import statement is executed.

Summary of Why Each Error Occurs:

1. Preprocessor errors occur when the text processing phase cannot resolve includes, macros, or conditional compilation directives.

2. Compilation errors occur when the code follows correct syntax rules but violates semantic rules of the language (type checking, scope rules, initialization requirements).

3. Linking errors occur when all individual compilation units are syntactically and semantically correct, but the linker/runtime cannot find the actual implementations of referenced symbols, classes, or modules.

QUESTION 6 \(10pts\). In C++, when declaring an Abstract Data Type in a header file like \(list.h\), which way to declare the \(list\) type would be the correct one and why:

1. Option A

struct s_list;
typedef struct s_list list;

1. Option B

struct s_list;
typedef struct s_list * list;

Looking at this question about Abstract Data Type (ADT) declaration in C++, I can explain which option is correct and why.

Option B is the correct choice:

struct s_list;
typedef struct s_list * list;

Key Principles of Abstract Data Types

1. Information Hiding: The internal structure should be hidden from client code

2. Encapsulation: Clients should only interact with the ADT through defined functions

3. Opaque Types: The actual implementation details are not visible to users

Why Option B Works

With Option B:

• ​list is a pointer type (specifically struct s_list *)
• Client code can declare and use list variables without knowing the size or internal structure of struct s_list​
• The actual definition of struct s_list stays in the implementation file (.cpp)
• This creates an opaque pointer or handle - a classic ADT pattern

Example usage:

// In client code - this works fine
list my_list;
my_list = list_create();  // Function returns a pointer
list_add(my_list, item);  // Pass the pointer to functions

Why Option A Doesn't Work

With Option A:

• ​list would be the actual struct s_list type (not a pointer)

• Client code would need to know the complete definition of struct s_list to:

• Declare variables of type list​

• Know how much memory to allocate
• Determine the struct's size
• Since we only have a forward declaration, compilation would fail:

// This would cause compilation errors
list my_list;  // Error: incomplete type 'struct s_list'

‍

‍

LinkedList.hpp

#include <cassert>

template <typename T>
class list {

    public:
        list() {
            this->head = nullptr; // nullptr is equivalent to NULL
            this->size = 0;
        }

        ~list() {
            while(size() > 0) {
                remove_at(0);
            }
        }

        T remove_at(int pos) {
            assert(pos >= 0);
            assert(pos < list_size);
            node<T> * to_delete; 
            if (pos == 0) {
                to_delete = this->head;
                this->head->set_next(this->head->get_next());
            } else {
                node<T> * current = this->head;
                //we want to go to the previous node of the one we need to delete
                for (int i = 0; i < pos - 1; i++) {
                    current = current->get_next();
                }
                to_delete = current->get_next();
                current->set_next(current->get_next());
            }
            T value = to_delete->get_value();
            delete to_delete;
            this->size--;
            return value;
        }

        T at(int pos) {
            assert(pos >= 0);
            assert(pos < list_size);
            node<T> * current = head;
            int i = 0;
            while (i < pos) {
                current = current->get_next();
                i++;
            }
            return current->get_value();
        }

        int size() {
            return list_size;
        }

        bool is_empty() {
            return list_size == 0;
        }

    private:
        template <typename E>
        class node {
            public:
                node(E value) {
                    this->value = value;
                    this->next = nullptr;
                }

                node(node<E> &other) : value(other.value), next(other.next) {}

                ~node() {}

                void set_next(node<E> *next) {
                    this->next = next;
                }

                node<E> *get_next() {
                    return next;
                }

                void set_value(E value) {
                    this->value = value;
                }

                E get_value() {
                    return value;
                }

            private:
                E value;
                node<E> *next;
        };
        node<T> * head;
        int list_size;
};