Topics include: Advanced memory management features of C and C++; the differences between imperative and object-oriented paradigms; the functional paradigm (using LISP) and concurrent programming (using C and C++); brief survey of other modern languages such as Python, Objective C, and C#. Prerequisites: Programming and problem solving at the Programming Abstractions level. Prospective students should know a reasonable amount of C++. You should be comfortable with arrays, pointers, references, classes, methods, dynamic memory allocation, recursion, linked lists, binary search trees, hashing, iterators, and function pointers. You should be able to write well-decomposed, easy-to-understand code, and understand the value that comes with good variable names, short function and method implementations, and thoughtful, articulate comments.
Administrative Details, Exams - Time limit, Conflicts, Course Grade Breakdown, Assignment Details - Submission, Grading, Late Days, Course Email, Newsgroup, Facebook/Twitter, Mailing List, Course Prerequisites, Languages and Paradigms Taught - C++ vs. Pure C, Procedural Paradigm vs. Object-Oriented Paradigm, Assembly, Concurrent Programming Overview, Example of Data Sharing Issues with Concurrent Programming, Scheme, Functional Paradigm Overview, Python Overview, Benefits and Common Uses
C/C++ Data Types - Interpretations, Sizes, Bits- How Bytes are Broken Up into Bits, Breaking Up a Character's Decimal Value into its Underlying Bit Structure, Shorts - Interpreting Data that Consists of More Than One Byte, Representations of Negative Numbers, The Sign Bit, Two's Complement Addition, Converting Between Chars and Shorts, How the Bit Representation is Transferred, Converting Between ints and shorts, Sign Extending During Conversion, Floats, Converting Between Integers and Floats
Converting Between Types of Different Sizes and Bit Representations Using Pointers, Little Endian vs. Big Endian, Structs: How the Data of a Struct is Stored, Accessing the Data of a Struct, Arrays, Pointer Arithmetic on Arrays, Result of Casting Arrays to Different Types, Layout in Memory of Structs, Dynamically Allocated Strings in C vs. Arrays of Characters, Modifying Internal Data of Structs Using strcpy, Character Arrays and cout, Generic Functions in C Using Memory and Pointers
Creating a Generic Swap Function for Data Types of Arbitrary Size, Void* Type for Generic Pointers, Implementation of Swap Function Using memcpy, Client Interface to Generic Swap Function, Pros and Cons of C Generics vs. C++ Generics, Errors Resulting from Improper Use of C Generic Swap Function that Compile, Swapping Pointers, Pitfalls when Swapping Pointers Using Generics, Implementing a Generic Linear Search, Implementing a Generic Linear Search, Using Casts and Pointer Arithmetic, Comparing Memory Blocks Using memcmp or a Comparison Function
Generic Lsearch - Prototype, Comparison Function, Implementation, Casting Void*S to Char*S to Compute Byte Offsets, Client Use of Generic Lsearch, Example of a Comparison Function for Integers, More Complicated Data Types and Lsearch- Example Using C-Strings, Comparison Function for Two C-Strings, With Arguments that Represent Char**S, Comparison Functions Where the Key is a Different Type than the Second Argument, Using a Pointer to a Struct as a Key in Order to Access Additional Data in a Comparison Function, Functions Vs. Methods, C Data Structures - Implementing a Non-Generic Stack of Integers, C Stack Interface, Implementation, Preallocating Memory, Client Use of C Stack, State of Internal Memory of the Stack, Growth of Memory when Stack Becomes Too Large, Implementation of Stacknew, Asserts
Integer Stack Implementation - Constructor and Destructor, Stackpush Implementation, Reallocation of Memory when Stack Grows Too Big Using Realloc, How Memory is Copied Using Realloc, Stackpop Implementation, Reimplementing the Stack Interface as a Generic Data Structure, Generic Implementation of StackNew, Generic Implentation of Stackpush Using Memcpy, Stackgrow Implementation, Static (Internal) Functions, Generic Stackpop Implementation Using Memcpy, Where it is the Responsibility of the Caller to Allocate the Memory Where the Popped Element is Stored.
Problems with Ownership of Memory, How Default Implementation of Stackdispose Does Not Free Dynamically Allocated Data, Adding a Free Function to the Stack Implementation, Rewriting Stackdispose to Incorporate It, Writing a Free Function for a Stack of C-Strings, Pitfalls When Writing Such Functions, C Library Functions for Assignment 3 - Memmove (Memcpy That Can Copy Using Two Regions That Overlap), Example of Rotate Function, C Qsort Function, Global Layout of Memory - Stack Segment, Heap Segment, How the Heap Manager Allocates And Frees Memory on the Heap, Underlying Linked List of Free Node Information
Heap Management - How Information about Allocations are Stored in the Heap, Result of Freeing Memory Improperly, Actual Sizes of Heap Allocations - Nearest Power of 2, Management of Free Blocks on the Heap by Storing Addresses in the Blocks of Free Memory, Algorithms for Choosing Which Free Block to Allocate, How the Heap's Free List Can Be Updated When Memory is Freed, How Adjacent Free Blocks Are Combined To Avoid Fragmentation, Compacting the Heap By Using Handles, Stack Segment Layout, Allocation of Local Variables on the Stack by Decrementing the Stack Pointer, Activation Records and State of the Stack Pointer During Nested Function Calls, Assembly Code and the Code Segment, RAM, Registers, and the ALU, Example That Demonstrates How an Arithmetic Expression is Translated Into Register Operations
How a Code Snippet is Translated into Assembly Instructions, Store, Load, and ALU Operations, Assembly Optimizations for 4-Byte Addresses, Context-Insensitive Code Translation, Overriding the 4-Byte Default in Assembly Instructions, Translating a For Loop into Assembly, Using Branch Instructions and the PC Register, Pointer/Array Arithmetic in Assembly, Unconditional Branch Instructions (Jumps), How a 4-Byte Assembly Instruction is Encoded in Memory
More Detail about Activation Records - Layout of Memory During a Function Call, How the Return Address of a Function is Stored on the Stack, Example Showing How an Activation Record is Constructed on the Stack, Setting Up Function Parameters on the Stack, Using the Call Instruction to Jump to the Function, Cleaning Up at the End of a Function and Using the RET Instruction and the Saved Return Address to Return to the Original Function, General Layout of an Activation Record, Who Sets Up Each Part of the Activation Record, Assembly Code Translation of the Factorial Function, How Recursion Translates into Assembly, Why Registers Need to be Reloaded After Other Functions Are Called, Animation Demonstrating the Assembly Execution for the Factorial Function
Moving from C Code Generation to C++ Code Generation: Basic Swap Example, Code Generation for the Pointer Swap Function, Code Generation for the C++ Version Of Swap Using References, Which Are Treated as Automatically Dereferenced Pointers, Local Variables Declared as References, Difference Between References and Pointers, Effect Of Declaring a Class on Memory in the Stack, Class Methods, Which Take a "This" Pointer as An invisible First Parameter, Effect Of the "This" Pointer on the Activation Record for a Class Method, Static Class Methods (Standalone Functions), Which Don't Contain a "This" Pointer, Compilation and Linking - #Define and the Preprocessor
Preprocessing Commands - #Define as a Glorified Find and Replace, Preprocessing Macros - Preprocessor Commands With Arguments, Example of Macro Usage in the Vector assignment to Calculate the Address of the Nth Element, Assert Macro Implementation, How Asserts are Stripped Out for the Final Product Using #Ifdef and #Define, C Macro Drawbacks When Given More Complex Arguments, #Include as a Search and Replace Operation, < > Vs. " ", Output to the Compiler After Preprocessing, How to View the Output of the Preprocessor Using Gcc, How to Avoid Circular #Include Loops Using #Ifndef, #Define, and #Endif, Visual Representation of the Result of Preprocessing (The Translation Unit) that Is Passed to the Compiler to Create a .O File, An Example Illustrating the Preprocessing and Compilation of a Simple Program
Review of Compilation Process of a Simple Program Into a .O File, Effect of Commenting Out a C Standard Library .H File on the Resulting Translation Unit, How Gcc Infers a Prototype When None Is Found and the .O File Remains the Same, How the Gcc Linker Is Able to Link Standard Library Files Without a #Include, The (Similar) Result When the .H File with Malloc's Prototype Is Not Included, How Commenting Out Assert.H Creates Different Results, Failing In the Linker Since Assert Is a Macro, As Opposed to a Function In the Standard Libraries, Effect of Calling Strlen with the Wrong Number of Arguments on the Compilation/Linking Process, Effect of Calling Memcmp with too Few Arguments on the Compilation/Linking Process, How C++ Disambiguates Between Different Function Prototypes to Avoid the Problems Posed By the Previous Two Examples, Debugging Information - Seg Faults (Usually Dereferencing a Bad Pointer) Vs. Bus Errors (Dereferencing Data that Isn't Correctly Aligned), Debugging Example Where Overflowing an Integer Array Leads to an Infinite Loop, Similar Example with a Short Array that Works Differently on Big-Endian Systems Vs. Little-Endian Systems, Example Where an Array Overflow Overwrites the Saved PC and Leads to an Infinite Loop
Example in Which Writing Past the End of Array Causes the Return Address of the Function to be Overwritten, Leading to An Infinite Loop, Example in Which Data Is Incorrectly Shared between Two Different Functions, But Can Still be Printed Out Due to the Structure of the Activation Record (Channelling), How Printf's Prototype Uses "...", Which Allows It to Take A Variable Number of Arguments, Why Parameters Are Pushed Onto the Stack From Right to Left, in the Context of Printf Crawling Up the Stack And Functions With A Variable Number of Arguments, Justification For Structs' Fields being Laid Out Sequentially in Memory, in Terms of Casting between Different Structs With Similar Internal Structures, Sequential Programming Vs. Concurrent Programming, Example of Many Different Processes Running in Separate Virtual Address Spaces, Each Mapped to Physical Addresses by A Central Memory Management Unit, How Concurrent Programming (Multiprocessing) Allows Mutiple Processes to Seemingly Run At the Same Time, How Multithreading Allows Multiple Functions in Run 'Simultaneously' Within One Process (E.G. the office Assistant in Microsoft office Or Downloading Songs in Itunes), Real-World Situation that Can be Modeled Using Threads (10 Ticket Agents Simultaneously Selling 150 Tickets)
Transitioning from Sequential Programming to Concurrent Programming in the Ticket Sale Example, Problems with the Sequential Model, Threading Interface, Rewriting the Ticket Example to Use It, Adding a Randomized Threadsleep Call to the Threads to Make the Time Slices Used by the Different Threads Less Uniform, Sample Output of Our Ticket Threads, How a Thread Can be Interrupted in the Middle of a Nonatomic Operation, How Multithreading Can Drastically Speed Up the RSS News Reader by Allowing Some Feeds to be Loaded While the Other Feeds Are Blocked, Allowing Each of the Ticket Threads to Access A Global Pool of Tickets, Rather than Allocating 15 Tickets to Each Agent, How This Can Lead to Problems When Threads Attempt to Access the Shared Data Simultaneously, How We Can Prevent This from Happening By Enclosing the Critical Region within A Semaphore, the Semaphorewait And Semaphoresignal Functions, Modifying the Selltickets Function to Use the Semaphore to Protect the Shared Data, How Changing the initial Value of the Semaphore Can Create Deadlock or Allow Too Many Threads to Access the Shared Data At Once
Review of Semaphore Syntax, Semaphoresignal and Semaphorewait, Semaphore Usage in the Multithreaded Selltickets Function (Protecting a Critical Region), Example of a Race Conditions Where Two Ticket agents Sell the Same Ticket, How the Stack and Various Registers are Saved When the Currently Running Thread Is Swapped, Another Example Using Semaphores that Models the internet, Implementations of a Reader and Writer Thread, Potential Dangers When the Two Threads Run Without Protection, Using a Fullbuffer Semaphore and an Emptybuffer Semaphore To Ensure that Neither Thread Outpaces the Other, Different Semaphore Patterns - Binary Lock Vs. Rendezvous, Effect of Changing the Starting Values of the Emptybuffers and Fullbuffers Semaphore, How To Detect Deadlock, Changes in the Thread Synchornization When Using Multiple Readers and Writers, Dining Philosopher Problem - Modeling Each Philosopher as a Thread, How Deadlock Can Result, How the Deadlock Can be Eliminated by Limiting the Number of Philosophers that Can Eat at Once
Review of the Dining Philosopher Problem, Modeling Each Philosopher as a Thread, How Deadlock Can Result, How Deadlock Can be Eliminated By Limiting the Number of Philosophers That Can Eat at Once Using a Semaphore, Using a Global Variable and a Binary Lock to Track a Resource Vs. Using a Semaphore, Another Threading Example Involving FTP Downloads of Multiple Files at Once, Where Each File Is Assigned to a Thread and the Total Number of Bytes Is Returned, Implementing a Downloadhelper Function That Downloads a File and then Uses a Binary Lock to Safely Update the Total Number of Bytes Downloaded, Ensuring that the Downloadallfiles Function Does Not Return Before All the Files Have Been Downloaded by the Threads Which It Spawns by Using a Childrendone Semaphore, Ensuring that the Downloadallfiles Function Does Not Return Before All the Files Have Been Downloaded by the Threads Which It Spawns by Using a Childrendone Semaphore, How the Childrendone Semaphore Ensures that the Function Returns at the Correct Time, No Matter How the Various Threads Are Interleaved, Setting Up the Ice Cream Store Concurrency Example for Next Week
Guest Lecturer, Setup of the Ice Cream Store Problem, with Customer, Cashier, Clerk, and Manager Threads, The Different Constraints on the Various Types of Threads, Writing the Main Function, Spawning the Various Threads, Handling the Manager-Clerk Interaction Using the Inspection Struct, Which Uses a Semaphore to Signal to the Manager That the Clerk Is Ready for Inspection, As Well as a Semaphore that Ensures that the Clerk Will Wait for the Inspection to Finish, Writing the Manager Function, Which Performs Each of the Inspections and Signals When Each one Is Finished, Writing the Clerk Function, Which Makes Cones Until the Manager Inspects and Approves One; Why an Additional Semaphore Must Be Added That Protects the Manager Function, Why Each of the Semaphores Introduced So Far Is Needed, Writing the Customer Thread's Function, Which Spawns Clerk Threads to Deliver its Ice Cream Cones and Then Waits Until They Are All Finished, Creating and Protecting the Line Struct, Which Is Used to Keep Track of the Customers Waiting for the Cashier in Order, Writing the Cashier Thread's Function, Which Checks Out Each Person Waiting in Line in Order, Waiting if Needed
Imperative/Procedural Paradigms (C) and Object-Oriented Paradigm(C++), Introduction to the Functional Paradigm (Scheme), Which Is Based on Synthesizing the Return Values of Functions, Example of a Scheme Function Definition that Converts Celsius to Fahrenheit, Scheme Environment (Kawa) Details, Scheme Primitives, Scheme Lists, Expressing Functions and Function Calls as Lists, Function Examples: <, >, and, Scheme List Operations: Car and Cdr, Distinguishing Between Lists and Functions with ', Origin of the Names "Car" and "Cdr", The Cons Function, Which Constructs a New List by Prepending the First Argument to the Second Element (Which Must Be a List), The Append Function, Which Concatenates Two Or More Lists, Defining Our Own Add Function, "Define" as an Operation in Scheme with Side Effects, Run-Time Error Checking in Scheme, Writing a Recursive Function that Sums All of the Numbers in a List
Car-Cdr Recursion Problem that Returns the Sum of Every Element in a List of Integers, How Scheme Checks Type During Run-Time Rather than Compilation, Recursive Implementation of the Fibonacci Function in Scheme, Example that Illustrates Runtime Error/Type Checking Vs. Compile-Time Error/Type Checking, Writing a Recursive Flatten Function that Removes All the Intervening Parentheses from a List, Using a Cond Structure to Branch Over the Various Recursive Cases in the Flatten Function, Using the Else Statement to Make Sure that Cond Always Returns Something, Writing the Sorted? Function for a List of Integers, Using the Or Function to Handle the Base Case Logic And Cadr As Shorthand for the Second Element, Using < And <= With Multiple Arguments in Scheme, Function Pointers in Scheme, How Function Data Is Stored Like a Linked List in Scheme And Function Names Are Linked to Code in a Symbol Table, Generalizing the Sorted? Function By Passing in a Comparison Function as the Second Parameter
Introduction to the Kawa Development Environment: Evaluation of Expressions, Loading Function Definitions From a .Scm File, Mapping Arbitrary Unary Functions Over Lists in Scheme Using the Map Operation, Mapping List Functions (Car, Cdr) Over Lists of Lists, Using Mapping Functions with More than One Input by Passing Multiple Lists into Map, Implementing the Unary Version of Map Using Recursion, Apply, Which Allows You to Specify a Function to Be Prepended to a List of Arguments and Be Evaluated, and Eval, Which Evaluates a List as Though it Were Typed into the Commandline, Using Apply to Implement an Average Function Wihtout Recursion, How Eval Can Be Used to Apply Non-Functions Like 'And' and 'Define' to a List, or to Evaluate a Complicated Expression Created While the Program Is Running, Revisiting Flatten Using Map and Apply, Writing a Flatten Implementation That Maps Itself Over Each of its Elements and Appends Each of the Results Together Using Apply, Implementing a Translate Function, Which Shifts Each Point in a List of Points by a Certain Delta, How a Typical Mapping Function Is Not Usable Because of its Need for Client Data, Using the Lambda Function to Define a Nameless Function On the Fly, Which Can Access the Delta Value Since it Is Constructed within the Translate Function, Defining Functions within Functions as an Alternative to Using Lambda, How the Define Keyword Implicitly Uses the Lambda Keyword to Associate a Name with a Function
Writing a Recursive Power Set Function in Scheme, Using a Lambda Mapping Function that Cons-Es the Car to Every Element in the Power-Set of the Cdr to Make the Recursive Step in the Power-Set Function, Using a Let Binding to Cause Power-Set to Only Make One Recursive Call Rather than Two, Structure of a Let Binding, How Expressions Within a Let Binding Cannot Depend On Each Other Unless the Let* Keyword Is Used, How a Let Binding Is Compiled to the Evaluation of a Lambda Expression, Writing a Permute Function, Which Prints Out a List of All Permutations of a Given List, Writing a Permute Function, Which Prints Out a List of All Permutations of a Given List, Writing the Overall Algorithm For the Permutation Function, Which Maps a Function Over Each Element in the List that Produces Each Permutation Starting With that Element, then Appends the Results Together, Writing the Mapping Function For the Permute Function, Which Maps Another Function (That Simply Conses the Current Element) to Each Permutation of the List of Elements when the Current Element Is Removed, Coding Without Side Effects and Immutability of Lists in Scheme, Memory Allocation in Scheme and the Read-Eval-Print Loop, How Integers, Strings, and Lists Are Laid Out in Memory when They Are Typed into the Scheme Command Line
Scheme Memory Model - How Scheme Instructions Synthesize Linked Lists Behind the Scenes and Perform Operations on Them, Two Different Ways of Laying Out A List In Memory, One With Memory Aliasing and One Without, The Scheme Equivalent of "..." (Functions With Multiple Arguments), Writing A Generic Map Function, Modifying the Unary-Map Function to Handle Multiple Arguments By Adding A . to the List of Arguments, Extending Unary-Map to An N-Ary Map Implementation Using ., Sample Trace of the N-Ary Map Function, Garbage Collection In Scheme, How Care Must Be Taken When Reclaiming Global Variables to Ensure That They Won't Be Needed Later, High-Level Mechanics of Garbage Collection: Reference Counts, or Sweeping Through the Data and Marking All Reachable Data, Then Freeing the Rest, Other Functional Languages: Scheme, ML, Haskell, Erlang
Overarching Features of Python: Scripting Language, Imperative, Object-Oriented, Functional, More Python Overview - Dynamic Typing, Use of Whitespace and Tabs, Python Environment, Execution of Basic Statements, Calling Methods Using Objects (And Anonymous Objects Like String Literals), Evaluating Assignments, Python Strings, String Methods, and Lists/Sublists (Including Index Wrapping), Strings as Lists of Characters in Python, Replacing Characters Within a List, Mutable Lists Vs. Immutable Lists, Writing the Gatherdivisors Function, Which Lists All the Divisors of the inputted Numbers: Function/Line Syntax (Incl. Tabs), for Loop Syntax and Iterables, Using and Importing Python Modules, Python Dictionaries, Adding and Retrieving Data from Dictionaries, How Heterogeneous Data Is Allowed inside Dictionaries, Look Ahead: Python Libraries, More About Dictionaries
Rewriting RSG to Illustrate all Three Paradigms and Lambdas in Python, How Objects Are Implemented in Python, Python Dictionary Implementation, Writing an RSG Grammar in Python Using A Dictionary and Lists, Expanding the Start Terminal Using all Three Paradigms at Once, Changing the Expand Function to A Binary Function, Modifying the Map to Use A Python Lambda Function As A Result, Python Object Model From A Memory Standpoint, How Objects Are Passed By Reference and How Lists Are Copied, How to Make A Deeper Copy of an Object in Python Using Copy or Deepcopy, Objects and Classes in Python, How They Are Stored As Dictionaries, Example of A Class Constructor and How it Creates Initializes the Class's Data, Rest of the Python Lexicon Implementation, Python Object Interface, Accessing the Underlying Dictionay of an Object, Inserting New Values into an Object's Underlying Dictionary
XML Processing and Python - Two Different XML Processing Models, Example XML Fragment, How an XML Parser Uses Tag Handlers to Break Up an XML Stream, How Python Can Parse XML Streams Using Urlopen, Make_Parser, and Contenthandler, Defining a Listfeedtitles Function that Takes in a URL and Parses it Using a Parser and an Rsshandler, Contenthandler Interface, Implementing The Rsshandler Class, Which Subclasses Contenthandler, to Fit The Specific Goals of The RSS Feed Reader, Implements The Rsshandler So that it Only Prints Data that Lies Within a Title Tag, Looking at an Actual RSS Feed in Firefox and Through Telnet, Looking at an XML Document with a Tree-Based XML Renderer Rather Than a Stream-Based Parser, Advantages of this Approach
Guest Lecturer: Sasha Rush, Haskell History, Safeguards in Haskell that Avoid Runtime Errors, Expressive Functions in Haskell, Speed of Haskell, Haskell Fibonacci Sequence in One Line Using Lazy Evaluation, How Lazy Evaluation Allows if Statements, Haskell Types, User-defined Data Types, Representing the Null Type in Haskell, List Types, Strings as Lists and Recursive Type Definitions, List Functions and Pattern Matching, Type Variables and Functions, Recursive Map Function, Reasons for the Lack of Object-oriented Code in Haskell, How to Get a Job Using Haskell, Three Functions that are Easier to Write in Haskell