PL Lecture 1

add pages 25-27 to these cue cards

GCC compiler

• GCC = GNU Compiler Collection

• GNU = GNU’s Not Unix

• Developed w/ GPL (General Public License)

  • Therefore it’s free to use & has an openly available source code

  • GPL is sometimes called '“copyleft software”, but it’s more commonly known as open-source

• GCC is available on all platforms commonly used in this day & age (e.g. Linux, Windows, Mac, etc.)

T or F: Clang and GCC are both powerful C & C++ compilers.

True

GCC v.s. Clang

GCC = GNU Compiler Collection

Clang:

• Usually offers faster compilation times

• More modular design

• Follows the C standard very closely

GCC:

• Mature codebase

• Wider support for languages & architectures

What is a language?

A medium of communication.

What is a program?

A set of instructions which a computer understands and follows.

What is a programming language?

A notational system used to describe computation in both human-readable and machine-readable form.

T or F: Machine data carries no type of information.

***KEY MATERIAL***

True.

Machine data is a just a sequence of bits.

The sequence of bits represents data.

Every program uses _____, either explicitly or implicitly, to arrive at a ______.

Every program uses data, either explicitly or implicitly, to arrive at a result. D

Data in its most primitive form is simply ________________.

Data in its most primitive form is simply a collection of bits.

***KEY MATERIAL***

(a) What is a data type?

(b) Why do we need it?

***KEY MATERIAL***

(a) What is a data type?

• A data type defines what kind of data a variable can hold (like numbers, text, etc.)

(b) Why do we need it?

It allows programming languages understand how to store & work with data.

Data types are like labels that tell the computer what kind of value it's dealing with. They're the foundation for handling and organizing data in any program.

T or F: The data type long is the same as the data type long int.

***KEY MATERIAL***

True

Name each of the primitive data types in C (LP64) and its typical size.

(Hint: “Curious Unicorns Swim In Underwater Lakes Until Finding Dazzling Lost Valuables”)

***KEY MATERIAL***

Letter	Data Type	Size (bytes)	Mnemonic Word

C

char

1

Curious

U

unsigned char

1

Unicorns

S

short int

2

Swim

I

int

4

In

U

unsigned int

4

Underwater

L

long int

8

Lakes

U

unsigned long int

8

Until

F

float

4

Finding

D

double

8

Dazzling

L

long double

16

Lost

V

void

0 (the typeless type)

Valuables

T or F: The size (in byes) of a data type can vary depending on the machine CPU. For instance, the size of a float value could be 5 bytes on one computer type and 4 bytes on another computer type.

True

(a) Which data model are we using in this course?

(b) In this model, what are the sizes (in bytes) of each of the following:

• unsigned int

• int

• long int

• unsigned long int

***KEY MATERIAL***

(a) LP64 data model

(b) unsigned int — 4 bytes

int — 4 bytes

long int — 8 bytes

unsigned long int — 8 bytes

The long int type can vary in size depending on the C programming data model being used.

However, as defined in the C standard, a long int is guaranteed to be at least ______ in size.

The long int type can vary in size depending on the C programming data model being used.

However, as defined in the C standard, a long int is guaranteed to be at least 32 bits in size.

In code, the long int type is declared as simply ____.

In code, the long int type is declared as simply long.

How would you declare a variable called “x” that is a long int data type with a value of 1?

long x = 1

(you wouldn’t write long int x = 1)

In our course we use the C programming ____ data model.

In our course we use the C programming LP64 data model.

T or F: In mathematics, the integer set is infinite.

True

T or F: In computer hardware, there is always largest and smallest integer.

True

T or F: In C programming, the numeric data types are finite in size.

True

In a C program, the sum of a + b (where a & b are numeric types) may ________ the finite range.

In a C program, the sum of a + b (where a & b are numeric types) may overflow the finite range.

T or F: The following mathematical expression is possible in C programming…

a + (b - c) ≠ (a + b) - c

True

Before high-level programming languages were created — all program code on computers were done in ____________ or ______________.

Before high-level programming languages were created — all program code on computers were done in machine code or assembly language.

***KEY MATERIAL***

(a) Define: “Data Structure”

(b) Give examples of a data structure.

(a) Define: “Data Structure”

• Particular way of storing & organizing data in a computer so that it can be used efficiently

(b) Give examples of a data structure.

• Array

• Stack

• Queue

• Linked List

• Tree

***KEY MATERIAL***

Classification of Data Structures

Data structures are classified into various types.

Two Major Classifications

1. Primitive Data Structures

2. Non-Primitive Data Structures

Primitive Data Structures

1. Character

2. Integer

3. Float

4. Pointer

Non-Primitive Data Structures

1. Linear Data Structures

   • Arrays

   • Linked List

   • Stacks

   • Queues

2. Non-Linear Data Structures

   • Graphs

   • Trees

***KEY MATERIAL***

Primitive Data Structures v.s. Non-Primitive Data Structures

Primitive Data Structures

Fundamental data structures supported by a programming language.

• E.g: Integer, short, long, float, char, etc.

Non-Primitive Data Structures

Data structures created using primitive data structures.

• E.g: Arrays, linked lists, stacks, graphs, trees, etc.

Linear Data Structure v.s. Non-Linear Data Structure

***KEY MATERIAL***

Linear Data Structure

Data elements are stored in a sequential (linear) order in consecutive memory locations.

• Includes: Linked Lists, Arrays, Stacks, Queues

Non-Linear Data Structure

Data elements are not stored in sequential (linear) order in consecutive memory locations. Instead data elements are represented by a hierarchical order.

• Includes: Graphs & Trees

Abstract Data Type (ADT)

• What is it?

• Why is it significant?

  • Name one example.

***KEY MATERIAL***

Concept that defines:

• What kind of data you're working with (e.g., a list, a stack, a queue).

• What operations you can perform on that data (e.g., add, remove, search).

• What rules or behaviours those operations should follow (e.g., in a stack: LIFO – Last In, First Out)

BUT:
It does NOT care how those operations are implemented in code.

Important:

• can have multiple different implementations

  • Diff implementations can have varying levels of efficiency, inner logic, and resource needs

Examples of ADTs:

• List w/ operations insert and delete

• Stack w/ operations push and pop

____________ types are similar to interfaces.

Abstract data types are similar to interfaces.

Data Structure

Specific organization of data and family of algorithms for implementing an ADT.

***KEY MATERIAL***

T or F: Many ADTs (Abstract Data Types) can be implemented as the same data structure. (aka — ADT can have multiple different implementations)

***KEY MATERIAL***

True

For example:

• A stack (ADT) can be implemented using an array or a linked list

T or F: Even though stacks and queues have different rules for adding & removing elements (LIFO v.s. FIFO), they can both be implemented as the same data structure.

True

ADT: Array

• Operations in C?

• Implementation in C?

***KEY MATERIAL***

ADT: Array

Operations —> Accessed by index [i]

Implementation in C —> Array data structure

ADT: Stack

• Operations in C?

• Implementation in C?

***KEY MATERIAL***

ADT: Stack

Operations —> push() & pop()

• You can push a plate on top of a stack

• You can pop the top plate off a stack

Implementation in C —> Linked list or array

What trade-offs must be considered when choosing a data structure?

*the following are generalizations/what typically happens, but not always

1. Time v.s. Space

   • Faster operations —> Use more memory

   • Saving memory space —> Slows things down

2. Operation Efficiency

   • Optimizing one operation (e.g. insert) may make another operation (e.g. search) less efficient

3. Generality v.s. Simplicity v.s. Performance

   • General structure —> More flexible, many use cases, but slower to run

   • Simple structure —> Less flexible, but faster to run

***KEY MATERIAL***

What key questions should you ask when choosing a data structure type?

***KEY MATERIAL***

• Does it support the operations I need efficiently?

• Is it easy to use, implement and debug?

• What assumptions am I making about how my software will be used by users (usage pattern)? (e.g. more lookups v.s. more inserts)

In the context of usage patterns (how users use a program), what do the following terms mean?

Lookups

• Searching for or accessing data

• e.g. “Find the value for this key.”

Inserts

• Adding new data to a structure

• e.g. “Add a new record”

Define “Algorithm”

Step-by-step, finite, effective procedure made up of precise instructions that solves a problem or performs a calculation.

***KEY MATERIAL***

Algorithms can be expressed in pseudocode through flowcharts or program code.

Algorithms can be expressed in pseudocode through flowcharts or program code.

In an algorithm, represented as a flowchart:

(a) What do branches represent?

(b) What do loops represent?

(a) What do branches represent?

• Conditional blocks

(b) What do loops represent?

• Repeated logic

Why are algorithms so important?

• Bc algorithms (alongside data structures) are the foundation of computer programming=

• “Algorithmic thinking” — i.e. problem-solving, and data structures are vital areas of knowledge for software engineers

***KEY MATERIAL***

_____________ and __________ are the foundation of computer programming.

Data structures and algorithms are the foundation of computer programming.

Algorithmic Complexity (aka Computational Complexity)

INCOMPLETE

Way of describing/measuring how efficient an algorithm is in terms of:

(1) Time Complexity

• How long to run program using said algorithm (AKA program running time)

• Dependent upon input size

(2) Space Complexity

• How much memory required to run program using said algorithm

• Also dependent upon input size

Important for algorithm design & efficient programming.

***KEY MATERIAL***

Computational complexity is important to consider in _________ design.

Computational complexity is important to consider in algorithm design.

Performance of an Algorithm

Performance of an algorithm = The algorithm’s time & space requirements (i.e. time & space complexity)

How are competing algorithms compared?

• performance of each algorithm is assessed by measuring their algorithmic complexity

• algorithmic complexity is approximated using asymptotic notations (e.g. Big-O notation) & ignoring the implementation dependent notations

• then the “values” of algorithmic complexity for each algorithm is compared

Fill in the Blanks:

“ In this course, we will write efficient code by focusing on two goals:

1. ______________

2. ______________ “

“ In this course, we will write efficient code by focusing on two goals:

1. Minimizing memory use

2. Reducing the number of instructions computer must execute “

Describe a few ways you can minimize memory use (to ensure you are writing efficient code).

To minimize memory use, avoid using…

• unnecessary variables

• function calls (which increases stack memory)

• large data structures

Describe a few ways you can reduce the number of instructions a computer must execute to run your code (to ensure you are writing efficient code).

To minimize number of instructions in your code that a computer must execute, avoid…

• extra work inside loops

• redundant calculations

• limiting nested loops

Define “Pseudocode”

• Simplified, English-like version of code

• Describes an algorithm’s logic

• Helps programmers plan & communicate ideas clearly w/o worrying about syntax

Define “Algorithm Complexity”

• A measure of the amount of time & space and algorithm needs to solve a problem

• Expressed using Big O notation

Define “Program”

• Final implementation of an algorithm

• Written as a specific programming language

• Translating pseudocode or flow chart into exact instructions a computer can execute

How many programming languages exist?

Fill in the blanks: There are ____________ of programming languages.

There are thousands of programming languages.

Why study various programming languages?

INCOMPLETE

Each language has its own strengths, paradigms, and design goals.

Studying various PLs helps you:

• Choose the best language for a specific task

• Understand different paradigms (procedural, OOP, functional, etc.)

• Write more efficient & appropriate code

• Leverage language-specific tools & libraries

1. Makes it easier to learn new PLs

   • some PLs are similar

2. Helps you make better use of any language by understanding implementation costs

Systems Programming

(a) Which 2 PLs are commonly used for this?

(b) Why may you choose one over the other?

C vs. C++ → Systems programming (C is low-level; C++ adds OOP)

Data Manipulation

(a) Which 2 PLs are commonly used for this?

(b) Why may you choose one over the other?

Python vs. R → Data manipulation (R is statistical; Python is general-purpose)

Network Programming

(a) Which 2 PLs are commonly used for this?

(b) Why may you choose one over the other?

Java vs. C++ → Network programming (Java has built-in support; C++ is faster)

Web Development

(a) Which 2 PLs are commonly used for this?

(b) Why may you choose one over the other?

Python vs. PHP → Web development (PHP is web-focused; Python is more flexible)

Numerical Computing

(a) Which 2 PLs are commonly used for this?

(b) Why may you choose one over the other?

C vs. Fortran → Numerical computing (Fortran excels in math-heavy tasks)

Functional Programming

(a) Which 2 PLs are commonly used for this?

(b) Why may you choose one over the other?

F# vs. Haskell → Functional programming (different ecosystems/syntax)

Logic Programming

(a) Which 2 PLs are commonly used for this?

(b) Why may you choose one over the other?

Prolog vs. Python → Logic programming (Prolog is built for it; Python can imitate)

Embedded Systems

(a) Which 2 PLs are commonly used for this?

(b) Why may you choose one over the other?

Python vs. C → Embedded systems (C is fast and memory-efficient)

Programming languages use the following 5 concepts:

• Parameter passing (by-value, by-reference)

• Typing (static or dynamic)

• Support for abstraction (procedural, data)

  • Scope (static or dynamic)

• Implementation (interpreted or compiled)

***KEY MATERIAL***

Which 4 criteria are used to evaluated programming languages?

1. Readability

   • How easy is it to understand the code?

2. Writability

   • How easy is it to create new programs?

3. Reliability

   • Safety

4. Cost / Efficiency

   • Cost/efficiency of execution and/or development

***KEY MATERIAL***

(a) Programming languages have 4 main properties…

(b) Fill in the blank: For any programming language, its designers must ________ these properties and its programmers must _______ these properties.

***KEY MATERIAL***

(a) Programming languages have 4 main properties…

• Syntax

• Names

• Types

• Semantics

(b) Fill in the blank: For any programming language, its designers must define these properties and its programmers must master these properties.

Fill in the Blank:

“Different ADT implementations have different ___(i)___, ___(ii)___ , and ___(iii)___ .”

***KEY MATERIAL***

“Different ADT implementations have different efficiency, inner logic , and resource needs .”

Syntax of Human Language v.s. Syntax of Programming Languages

***KEY MATERIAL***

Syntax of Human Language

• Arrangement of words in sentences, clauses, or phrases

Syntax of Programming Language

• Precise description of all its grammatically correct programs.

Examples of entities in a program.

• Variables

• Data Types

• Functions

• Parameters

• Classes

• Objects

Named entities are bound in a running program to…

***KEY MATERIAL***

Named entities are bound in a running program to…

• Scope

• Visibility

• Type

• Lifetime

(a) Define “Type”

(b) Simple/Primitive Types (define + examples)

(c) Structured Types (define + examples)

(a) Define “Type”

A type defines the kind of data a variable can hold & what operations can be performed on it.

(b) Simple/Primitive Types (

Def: Represent single, indivisible values

Examples:

• int —> integer

• char —> character

• float, double —> decimal numbers

• bool —> true or false

(c) Structured Types

Def: Types made by combining multiple values (of the same type or of different types)

Examples:

• Arrays —> a list of elements (same type)

• Structs —> a group of variables (can be diff types)

• Strings —> a sequence of characters

• Lists —> an ordered collection of elements (can be diff types)

• Classes/Objects —> combine data & methods

• Tuples/Records —> fixed collection of values

(a) Define “Type System”

(b) Significance?

(a) Define “Type System”

• A type system is a collection of rules used to assign types to various entities in a programming language, such as:

  • Variables

  • Expressions

  • Functions

  • Parameters

(b) Significance

A type system is important because it helps:

1. Organize data clearly

2. Check code correctness before runtime

3. Determine legal operations for each type

4. Detect type errors (e.g., using a string like a number)

Define “Type Safety of a Language”

Type safety of a PL is the extent to which its Type System prevents or discourages relevant type errors.

Define “Semantics”

Semantics refers to the meaning of a program — what the program does when it runs.

Semantics v.s. Syntax

• Include an example using code.

Semantics

• About behaviour

• What does the program do? How does it work?

Syntax

• About structure of code

• How does the program look?

Example:

• Syntax: x = x + 1; ← this is syntactically correct

• Semantics: this line means “increase the value of x by 1”

Good programmers wrote code that ________ can understand.

Good programmers wrote code that humans can understand.

A programmer should be able to ________________________ before actually running a program.

A programmer should be able to anticipate what will happen before actually running a program.

What kinds of questions do we ask when studying semantics in programming languages?

1. What happens to the values of variables during execution?

2. What does each statement actually mean at runtime?

3. What model governs runtime behaviour (e.g., function calls, memory management)?

4. How are objects allocated in memory at runtime?

(a) Define “Paradigm”

(b) Define “Programming Language Paradigm”

(a) Define “Paradigm”

• A system of assumptions, concepts, or patterns.

  • e.g: Theory of evolution

(b) Define “Programming Language Paradigm”

• Pattern/style that defines how programming problems are approached and solved in a language.

Many researchers classify programming languages into ___ categories and ____ paradigms.

Many researchers classify programming languages into 2 categories and 4 paradigms.

Describe the 2 categories of programming languages and the 5 programming paradigms that fall under each.

(1) IMPERATIVE — Programmer instructs the computer step-by-step on how to change its state.

This category includes the following PL paradigms:

• Imperative: Basic step-by-step instructions

• Procedural: Instructions are group into procedures or functions

• OOP: Instructions are grouped with the data (state) they operate on, using objects

(2) DECLARATIVE — Programmer merely declares what they want as the result, w/o specifying how to compute it.

This category includes the following PL paradigms:

• Functional: The result is described using function applications.

• Logic: The result is a logical answer to a query about a system of facts and rules.

Name the 4 main programming paradigms.

1. Imperative

2. obejct-oriented (OO)

3. functional

4. logical (declarative)

Programming ___________ are a way to classify programming languages based on their _________.

Programming paradigms are a way to classify programming languages based on their features.

T or F: Programming languages can be classified into multiple paradigms.

True

What is John von Neumann’s contribution to modern computer architecture?

• In 1944, John von Neumann proposed the idea of storing programs as sequences of numbers (binary) in memory — alongside the data they use.

  • This led to the concept of the stored-program computer

  • Programs and data are both stored in memory as binary

  • This design is the foundation of modern computers today

• Known as the von Neumann architecture

CPU stands for…

Central Processing Unit

The von Neumann — Eckert Model

Fill in the labels in the diagram above.

Fill in the labels in the diagram above.

1- Input

2 - Program

3 - Variables

4 - Memory

5 - Output

6 - Control

7 - Arithmetic/Logic

NTS: Once you get really good at labelling the diagram, change the question so that it simply requires you to draw & label the entire Eckert Model from scratch.

What is the role of the following in the Eckert Model:

• Memory

• Processing Unit

• Control Unit

• Memory —> Contains instructions & data

• Processing Unit —> performs arithmetics & logical operations

• Control Unit —> interprets instructions

INCOMPLETE —> PAGES 54-60 (I SKIPPED THESE PAGES, SO THERE HAVEN’T BEEN ANY CUE CARDS MADE ON THEM YET!!)

Define each of the following type systems of programming languages in one sentence:

(a) Static

(b) Nominative

(c) Manifest

Define each of the following type systems of programming languages in one sentence:

(a) Static —> Types are checked at compile time

(b) Nominative —> Type compatibility is based on name, not structure

(c) Manifest —> Types must be explicitly declared

Java

(a) Developer?

(b) Paradigm(s) it follows?

(c) Type system?

(d) What is Java’s approach to compatibility?

(e) What is 1 disadvantage of using Java?

(f) Where is Java widely used?

(a) What company developed Java?

Oracle Corporation

(b) What programming paradigms does Java follow?

Imperative & object-oriented (OO).

(c ) How does Java handle type systems?

• Static

• Nominative

• Manifest

(d) What is Java’s approach to compatibility?

Write once, Run anywhere (via JVM)

(e) What languages also use the Java Script

• Scala

• Jython

• Clojure

• Groovy

(f) What is one disadvantage of Java?

It’s verbose — meaning it requires more code to accomplish tasks compared to languages like Python.

(g) Where is Java widely used?

Large-scale enterprise software.

C/C++


(a) Developer?

(b) What paradigm does C follow? What about C++?

(c) Type system?

(d) Where are C & C++ commonly used?

(e) How does C/C++ compare to Java?

(f) Disadvantages

(a) Developer?

The International Organization for Standardization (ISO).

(b) What paradigm does C follow? What about C++?

• C: Imperative, procedural

• C++: Imperative, procedural, object-oriented

(c) Type system?

• Static

• Nominative

• Manifest

• C++ also has type interference

(d) Where are C/C++ commonly used?

• Operating systems

• Graphics processing

• Game development

• Compilers

• Applications needing predictable resource use

(e) How does C/C++ compare to Java?

• C and C++ are "closer to the hardware" than Java.

  • C and C++ let you directly control things like memory and system resources (e.g., using pointers).

  • Java runs on the Java Virtual Machine (JVM), which acts like a middleman, so you don’t interact with the hardware as directly.

(f) What are some of the disadvantages of using C/C++ ?

• Manual memory management

• Less protection from memory errors

• Compiler errors can be difficult to understand

• Generally easier to make mistakes

C#

(a) Developer?

(b) Paradigm(s) it follows?

(c) Type system?

(d) What framework does C# run on? What major advantage does it provide?

(e) How does C# allow system function access?

(f) How does C# compare to Java & C++ ?

(g) Primary use?

(a) Who developed it?

Microsoft

(b) What programming paradigms does it follow?

• Imperative

• Object-oriented

• Functional

(c) How does C# handle its type system?

• Static

• Nominative

• Partially inferred (optionally dynamic)

(d) What framework does C# run on? What major advantages does this framework provide?

• C# runs on the .NET Framework

  • Allows cross-platform development

  • Performs garbage collection (similar to the JVM)

(e) How does C# allow system function access?

• using the unsafe keyword

(f) How does C# compare to Java & C++ ?

• less verbose than Java

• safer than C++

(g) Primary use?

Writing Windows applications

Python

(a) Developer?

(b) Paradigm(s)?

(c) Type system?

(d) What is Python classified as? Why?

(e) What is Python's Read-Eval-Print-Loop (REPL) used for?

(f) How does Python handle variable types?

(g) What is unique about Python’s use of whitespace?

(f) Disadvantages?

(a) Developer?

Python Software Foundation

(b) Paradigm(s)?

• Imperative

• Object-oriented (OO)

• Functional

• Procedural

(c) Type system?

Dynamic

(d) What is Python classified as? Why?

A scripting language

(e) What is Python's Read-Eval-Print-Loop (REPL) used for?

REPL is useful for experimenting or one-off tasks

(f) How does Python handle variable types?

Variables don’t have types, only values have types

(g) What is unique about Python’s use of whitespace?

Whitespace has semantic meaning

(f) Disadvantages?

Lack of variable types and compile-time checks mean more may be required of documentation and testing.

JavaScript

(a) Developer?

(b) Paradigm(s)?

(c) Type system?

(d) What is JS classified as? Why?

(e) What is JS primarily used for?

(f) How does JS handle errors compared to how other PLs do?

(g) What are some challenges of using JS in large-scale development?

(a) Developer?

Mozilla Foundation

(b) Paradigm(s)?

• Imperative

• Object-oriented

• Functional

• Procedural

(c) Type system?

Dynamic

d) What is JS classified as? Why?

A scripting language

(e) What is JS primarily used for?

JavaScript is the primary client-side language of the web

(f) How does JS handle errors compared to how other PLs do?

JavaScript takes a "continue at any cost" approach, meaning errors often fail silently rather than stopping execution

(g) What are some challenges of using JS in large-scale development?

• JS is great for simple tasks

• JS is horrible for large & complex software development due to its error-handling approach

Haskell

(a) Developer?

(b) Paradigm(s)?

(c) Type system?

(e)

(f) Advantages of using Haskell over imperative languages?

Functional Programming v.s. Imperative Programming

SQL

Prolog

Church-Turing Thesis

For any computable (solvable) problem —> There is a turing machine (computer) that can compute it.