Lecture Identity

File/lecture name: sep_comp.pdf (Separate Compilation) Main theme: Understanding the C/C++ compilation pipeline, managing declarations vs. definitions, and implementing modular programming using header files and separate compilation. Prereqs assumed by slides: Basic C syntax (variables, functions, structs), familiarity with gcc command line usage, understanding of memory (stack vs. heap). What this lecture enables you to do:

• Resolve "undefined reference" linker errors by understanding the compilation pipeline.
• Write modular C/C++ programs using separate compilation (.c and .o files).
• Create header files (.h) that provide interfaces without exposing implementation details.
• Use preprocessor directives (#define, #ifdef) to control code inclusion.
• Manage incomplete types to enforce encapsulation in Abstract Data Types (ADTs).

Big Picture Map (High-Level)

1. Declarations vs. Definitions: Distinguishing between promising an entity exists (declaration) and allocating space for it (definition).
2. Forward Declarations: Using declarations to allow function calls before the function definition is seen.
3. Compilation Pipeline: The four steps: Preprocessor -> Compiler -> Assembler -> Linker.
4. Preprocessor Directives: Using #include, #define, and #ifdef to manipulate source text before compilation.
5. Separate Compilation: Compiling individual files into object files (.o) using the -c flag.
6. Linking: Combining object files into a final executable using the linker.
7. Header Files: Creating .h files to declare interfaces for modules.
8. Incomplete Types: Understanding when the compiler needs the full struct definition vs. just a pointer.
9. Encapsulation: Using incomplete types to hide implementation details (e.g., struct List internals) from the client.
10. Stack vs. Heap: How incomplete types prevent stack allocation of complex ADTs.

Key Concepts & Definitions

1. Declaration vs. Definition

• Definition: The full details of an entity (e.g., variable type, function body, struct layout). Space is allocated. Can only be defined once.
• Declaration: Asserts that an entity of a given type and name exists. Does not allocate space. Can be declared multiple times.
• Why it matters: The compiler needs a definition to allocate memory (stack/heap), but only needs a declaration to check types and generate jump instructions.
• Common confusion: Thinking void foo(int x); is a definition. It is a declaration.
• Tiny example:

  // Declaration
  void foo(int x); 
  
  // Definition
  void foo(int x) { printf("%d", x); }
  

2. Forward Declaration

• Definition: A declaration of a function or type that appears before its definition in the code.
• Why it matters: Allows the compiler to generate placeholder code for function calls before the function body is encountered.
• Common confusion: Believing a forward declaration provides the function's implementation.
• Tiny example:

  void bar(int x); // Forward declaration
  void foo(int x) { bar(x); } // foo can call bar
  void bar(int x) { ... } // Definition comes later
  

3. Object File (.o)

• Definition: A binary file containing machine code generated by the assembler, but not yet linked into an executable.
• Why it matters: Allows separate compilation of modules. The linker combines these later.
• Common confusion: Thinking gcc file.c produces an executable immediately (it does, but it also links).
• Tiny example: gcc -c file.c produces file.o.

4. Preprocessor Directives

• Definition: Lines starting with # processed before compilation. They manipulate the source text (copy, paste, define, conditionally include).
• Why it matters: Enables #include for libraries, #define for constants, and #ifdef for build configurations.
• Common confusion: Thinking #define creates a variable. It creates a text replacement token.
• Tiny example:

  #define MAX 100
  int x = MAX; // x becomes 100
  

5. Incomplete Type

• Definition: A type (usually a struct) that has been declared but not defined (compiler doesn't know its size).
• Why it matters: Allows pointers to the type to exist on the stack without knowing the struct's internal layout.
• Common confusion: Trying to declare a variable of an incomplete type on the stack (e.g., struct List l;).
• Tiny example:

  struct List; // Declaration only (Incomplete)
  struct List *l; // Valid pointer
  struct List l;  // Error: storage size not known
  

6. Encapsulation

• Definition: Hiding the internal details of a module (like an ADT) so clients can only interact via a defined interface.
• Why it matters: Prevents clients from breaking invariants (e.g., modifying next pointers directly).
• Common confusion: Believing header files must contain all struct definitions.
• Tiny example:

  // Header only declares struct List
  struct List; 
  // Client cannot access l->len directly
  

Core Mechanics / How-To

How to Compile a Single File into an Executable

1. Write main.c containing main().
2. Run gcc main.c.
3. Result: gcc runs all 4 steps (preprocess, compile, assemble, link).
4. Warning: If main is missing, the linker will fail with "undefined reference to _start".

How to Compile into an Object File (Separate Compilation)

1. Write module.c (no main).
2. Run gcc -c module.c.
3. Result: Produces module.o.
4. Why: Allows you to compile this module independently of main.

How to Link Object Files

1. Ensure you have object files (e.g., main.o, module.o).
2. Run gcc main.o module.o -o executable_name.
3. Result: Linker combines object files into a final executable.
4. Note: gcc assumes .o files are object files and skips compilation steps.

How to Write a Header File (.h)

1. Create module.h.
2. Include only declarations (function prototypes, incomplete struct types).
3. Do not include full struct definitions or implementation details.
4. Use #include "module.h" in client files.
5. Why: Provides the interface without exposing the implementation.

How to Use Preprocessor Conditionals

1. Define a flag: #define DEBUG.
2. Wrap code:

   #ifdef DEBUG
   printf("Debug info\n");
   #endif
   

3. Compile with flag: gcc -DDEBUG file.c.
4. Result: Code inside #ifdef is included only if the flag is passed.

How to Handle Incomplete Types Safely

1. Declare the struct in the header: struct List;.
2. In client code, only use pointers: struct List *l = createList();.
3. Never try to allocate the struct on the stack: struct List l; (Error).
4. Reason: The compiler doesn't know the size of struct List in the header.

Code Patterns & Idioms

Pattern: Forward Declaration

• When to use: When a function calls another function defined later in the file or in another file.
• Correct minimal example:

  void bar(int x); // Forward declaration
  void foo(int x) { bar(x); }
  void bar(int x) { ... }
  

• Common bug: Forgetting the forward declaration, causing "implicit declaration" warnings or errors.

Pattern: Header File Interface

• When to use: When creating a library or module to be reused.
• Correct minimal example:

  // List.h
  struct List; // Incomplete type
  void printList(struct List *);
  struct List *createList();
  

• Common bug: Including the full struct definition in the header, breaking encapsulation.

Pattern: #include Syntax

• When to use: #include <...> for standard libraries, #include "..." for custom headers.
• Correct minimal example:

  #include <stdio.h>   // Standard library
  #include "mylib.h"   // Custom header
  

• Common bug: Using < > for custom headers (compiler looks in system paths, not current directory).

Pitfalls, Edge Cases, and Debugging

• Symptom: undefined reference to 'main'
  • Likely cause: Compiled a file without main as an executable entry point.
  • Fix: Ensure main.c contains main, or link against a library that provides it.
• Symptom: implicit declaration of function 'foo'
  • Likely cause: Used a function before declaring it.
  • Fix: Add a forward declaration before usage.
• Symptom: storage size of 'l' isn't known
  • Likely cause: Trying to declare a struct variable on the stack using an incomplete type.
  • Fix: Use a pointer (struct List *l) or include the full definition in the header.
• Symptom: ld returned 1 exit status
  • Likely cause: Linker error (missing symbols).
  • Fix: Ensure all object files are linked, or use gcc to link automatically.
• Symptom: PREX is not undeclared
  • Likely cause: Using a preprocessor constant without defining it.
  • Fix: Use #define PREX 5 or gcc -DPREX=5.
• Symptom: #include not finding custom header
  • Likely cause: Using < > instead of " ".
  • Fix: Use #include "header.h" for local files.
• Symptom: Client modifies struct fields directly (e.g., l->len = 10).
  • Likely cause: Header included full struct definition.
  • Fix: Use incomplete type (struct List;) in header to hide fields.
• Symptom: gcc produces executable but crashes on deleteList.
  • Likely cause: Client stored pointers to heap nodes on the stack.
  • Fix: Ensure all pointers to ADT internals are managed via the API.
• Symptom: #ifdef code not compiling.
  • Likely cause: Flag not passed during compilation.
  • Fix: Add -DDEBUG to gcc command.
• Symptom: gcc complains about #define inside string.
  • Likely cause: #define does not replace text inside quotes.
  • Fix: Accept this behavior; #define is for code, not strings.
• Symptom: gcc treats .o file as source.
  • Likely cause: Forgetting -c flag or passing .o to gcc without -o.
  • Fix: Use gcc -c file.c for object files, or gcc file.o -o exe for linking.
• Symptom: gcc produces warning about implicit-function-declaration.
  • Likely cause: Missing header or forward declaration.
  • Fix: Add void printArray(int *, size_t); before usage.

Exam-Style Questions (with answers)

1. Q: What is the difference between void foo(int x); and void foo(int x) { ... }? A: The first is a declaration (promise of existence), the second is a definition (implementation + space allocation).
2. Q: Why does gcc file.c produce a linker error if main is missing? A: The linker needs an entry point (main) to build an executable. Without it, it fails.
3. Q: What does the -c flag do in gcc? A: It compiles the source file into an object file (.o) without linking.
4. Q: Can you declare a variable of an incomplete type on the stack? A: No. The compiler doesn't know the size, so it cannot allocate space.
5. Q: What is the purpose of #include "file.h" vs #include <file.h>? A: Double quotes look in the current directory; angle brackets look in system paths.
6. Q: What happens if you use #define FLAG without a value? A: It defines the identifier FLAG as an empty token (true/false check).
7. Q: Why is struct List; called an incomplete type? A: It declares the name but not the members/size, so the compiler doesn't know how much space to allocate.
8. Q: How do you fix "undefined reference to bar"? A: Add a forward declaration void bar(int x); before foo calls it.
9. Q: What is the role of the linker? A: It combines object files (.o) into a single executable, resolving references between them.
10. Q: Why can't a client modify struct List fields directly if the header only declares struct List;? A: The compiler doesn't know the fields exist, so it rejects direct access (encapsulation).
11. Q: What is the output of gcc -DDEBUG file.c? A: The preprocessor includes code inside #ifdef DEBUG blocks.
12. Q: Can you define a preprocessor constant in the command line? A: Yes, using -DNAME=value (e.g., gcc -DPREX=5 file.c).

Quick Reference / Cheat Sheet

• Compilation Steps: Preprocessor -> Compiler -> Assembler -> Linker.
• Object File: gcc -c file.c -> file.o.
• Linking: gcc file.o -o exe or gcc file.c -o exe (auto-links).
• Preprocessor:
  • #include <stdio.h> (System)
  • #include "file.h" (Local)
  • #define MAX 100 (Constant)
  • #ifdef FLAG (Conditional)
• Declaration: void foo(int x); (No space allocated).
• Definition: void foo(int x) { ... } (Space allocated).
• Incomplete Type: struct List; (Pointer only, no stack allocation).
• Linker Error: "undefined reference" -> Missing definition or main.
• Compiler Warning: "implicit declaration" -> Missing forward declaration.

Mini Glossary

1. Declaration: Asserts an entity exists (type + name).
2. Definition: Full details of an entity; space is allocated.
3. Forward Declaration: Declaration of a function/type before its definition.
4. Object File: Binary machine code (.o) ready for linking.
5. Linker: Combines object files into an executable.
6. Preprocessor: Tool that processes # directives before compilation.
7. Header File: File containing declarations for a module (.h).
8. Incomplete Type: Type declared but not defined (unknown size).
9. Encapsulation: Hiding implementation details from the client.
10. Invariant: A property that must always hold true for the code to work.
11. Stack Allocation: Placing variables in memory with known size.
12. Heap Allocation: Placing variables in memory with dynamic size.
13. #define: Macro definition for text replacement.
14. #ifdef: Conditional compilation based on defined flags.
15. -c Flag: Compile only, do not link.
16. -D Flag: Define a preprocessor constant.
17. -o Flag: Specify output filename.
18. _start: Entry point symbol for the linker.
19. printf: Standard output function (from stdio.h).
20. scanf: Standard input function (from stdio.h).

What This Lecture Does NOT Cover (Boundary)

• C++ Classes: While the course is C++, these slides focus on C structs and pointers. C++ classes (inheritance, polymorphism) are not covered here.
• Dynamic Memory Management: malloc/free are not explicitly detailed, though createList implies heap usage.
• Graph Algorithms: Shortest paths or divide-and-conquer are mentioned in the course description but not in these slides.
• Client-Server Computing: Mentioned in course description, not in these slides.
• Recursion: Mentioned in course description, not in these slides.
• C++ Specifics: std:: namespace, templates, or class keyword are not used in these slides.

Slide Anchors (Traceability)

• Declarations vs. Definitions: Slide 2 ("Declarations and Definitions") - "A declaration only asserts that an entity... exists."
• Forward Declarations: Slide 3 ("Forward declarations, a necessity") - "Declarations allow us to make a promise to the compiler..."
• Compilation Steps: Slide 6 ("The four steps of C/C++ compilation") - "The C preprocessor... The compiler... The assembler... The linker..."
• Preprocessor Directives: Slide 8 ("Preprocessor directives") - "Preprocessor directives are the lines of our code that begin with a #."
• Defining Constants: Slide 10 ("Defining preprocessor constants") - "We can also define preprocessor constants with compiler flags."
• Conditional Compilation: Slide 12 ("ifdef and ifndef") - "We can also write simple conditionals that check if a preprocessor flag has been defined."
• Separate Compilation: Slide 17 ("Compiling printArray.c") - "This is not a compilation error. This is a linker error."
• Object Files: Slide 18 ("Compiling without linking") - "A C file that has been compiled into machine code without linking it into a final executable is called an object file."
• Header Files: Slide 24 ("Header files") - "Header files are files that include the declarations of entities our module provides."
• Incomplete Types: Slide 31 ("Incomplete types") - "At the point of compiling stackList.c the type struct List is known as an incomplete type."
• Encapsulation: Slide 33 ("Encapsulation") - "The concept of encapsulation is that our ADTs should be black boxes..."
• Stack vs. Heap: Slide 32 ("Incomplete types | How to use them") - "Our code for printLargest.c works because while we use struct List as a type, we never ask the compiler to allocate one!"