Final Exam Key Facts

C++ Concepts

Memory Management

• Static Memory: Allocated when the program is compiled. Used for global and static variables. There is only one copy, and it persists for the entire program duration.
• Stack Memory: Used for local variables inside functions. Memory is automatically allocated and deallocated as functions are called and return (Last-In, First-Out).
• Heap Memory: Used for dynamic memory allocation with the new keyword or functions like malloc. This memory must be manually deallocated using delete or free to prevent memory leaks. The golden rule is: every new must have a matching delete.

Classes, Constructors, and Destructors

• A Class is a blueprint for creating objects, defining both state (member variables) and behavior (member functions).
• Access Specifiers: public (accessible anywhere), protected (accessible within the class and derived classes), and private (accessible only within the class). These enforce encapsulation.
• Member functions can be defined inside the class (for short, convenient functions) or outside using the scope resolution operator (::) to keep class definitions cleaner.
• A Constructor is a special function called automatically when an object is created to initialize it.
• A Destructor is called automatically when an object is destroyed. Its primary purpose is to clean up resources, especially deallocating heap memory allocated by the object to prevent memory leaks and dangling references.

Inheritance and Polymorphism

• Inheritance allows a new class (derived/child class) to be built from an existing class (base/parent class), promoting code reuse.
• The "is-a" relationship signifies inheritance (e.g., a Student is a Person).
• The "has-a" relationship signifies containment or composition (e.g., a Car has a Wheel).
• Polymorphism ("many forms") allows a single interface to represent different underlying forms (data types). In C++, this is achieved with virtual functions.
• A virtual function in a base class can be overridden by a derived class. When called through a base class pointer, the version in the derived class is executed, enabling dynamic behavior based on the actual object type.
• Function Overloading means having multiple functions with the same name but different parameters (number or type of arguments). The return type alone is not sufficient to overload a function.

Scheme Concepts

Syntax and Core Ideas

• Scheme uses prefix notation, where the operator comes first, followed by operands, all enclosed in parentheses. Example: (+ 3 2).
• Everything in parentheses is a "form" that gets evaluated.
• Names are bound to values using define. Procedures (functions) can be created with a named form or an anonymous lambda. Both forms are equivalent.
• Scheme blurs the line between code and data. A symbol is a value that represents code without executing it, allowing programs to manipulate other programs. Source code itself is just a data structure (a list of symbols).

Data Structures and Control Flow

• Pairs are the fundamental building block of lists, containing two slots: the car (the first element) and the cdr (the rest of the list).
• A proper list is a series of nested pairs ending with an empty list '().
• Control constructs include if for binary choices and cond for multiple branching conditions (a cascade of cases).
• Scope is managed through environments. define adds to the global environment, while let creates a temporary, local environment for its body, keeping temporary names tidy.
• A let expression is just syntactic sugar for a lambda call. They are interchangeable and understanding this conversion helps clarify scope.

Recursion and Higher-Order Functions

• Recursion is a primary method for iteration. A common pattern involves identifying a base case (stopping condition) and a recursive step that solves a smaller version of the problem (e.g., operating on the cdr of a list).
• The Ackermann function is a classic example of a deeply recursive function that grows extremely fast.
• Higher-Order Functions are functions that take other functions as arguments or return them as results.
• Key higher-order functions include: map (applies a function to every element in a list, returning a new list), reduce (collapses a list into a single value), and filter (selects elements from a list that satisfy a condition).

Prolog Concepts

Facts, Rules, and Queries

• Prolog programs are built from facts (things that are true), rules (general relationships), and queries (questions about the facts and rules).
• Constants start with a lowercase letter, while variables start with an uppercase letter. The underscore _ is an anonymous variable (a "don't care" placeholder).
• A fact is a rule with no body. A rule has a head and a body, where the head is true if the body is true. Example: head :- body.
• The comma , means "and", the semicolon ; means "or", and the period . ends a statement.

Unification and Execution

• Prolog's reasoning engine is based on unification, which is a process of pattern matching goals with facts or rule heads.
• Unification succeeds if the predicates have the same name, the same number of arguments (arity), and all corresponding arguments can be made equal.
• Prolog explores solutions systematically through search and backtracking. When a path fails, it automatically backtracks to the last choice point to try an alternative.

Lists and Recursion

• Lists are written with square brackets. The structure [H | T] is used to unify the head of the list with H and the tail (the rest of the list) with T.
• Recursion is fundamental to processing lists, using the base case of an empty list [] and a recursive step that processes the head and recurses on the tail.
• The cut (!) is an optimization tool that prunes the search space by committing to the choices made so far and preventing backtracking past that point.
• The "negation as failure" rule (often implemented with not) states that something is false if Prolog fails to prove that it is true. The cut is used internally to implement this efficiently.

Glossary of Terms