CMS 710 · Principles of Programming Languages

Three perspectives on a programming language

1. Communication perspective · a medium between the programmer and the computer
2. Problem-solving perspective · tools and constructs for solving computational problems
3. Formal system perspective · a mathematically defined system governed by precise syntactic and semantic rules

Evolution · the four generations

Syntax vs semantics · the classic pair

SYNTAX  · is it legally written?
   Correct:    x = 10
   Incorrect:  = x 10        ← violates the rules

SEMANTICS · what does it mean?
   x = 10 + 20
   Syntax says: correctly written.
   Semantics says: add 10 and 20, store in x.

The five goals of language design

The three principles of language definition

1. Formal rules govern every language. Languages are not arbitrary collections of symbols; without precisely defined rules for syntax, semantics and execution, compilers and interpreters could not process programs consistently.
2. Simplicity versus expressiveness. Simple languages give easier learning and better readability but limited abstraction; expressive languages give powerful constructs and less code but increased complexity.
3. Efficiency versus safety. C++ emphasizes performance; Python emphasizes productivity and safety. This trade-off drives adoption in different domains.

BNF · the notation to reproduce

Meaning: an assignment statement consists of an identifier, an assignment operator and an expression. The statement x = y + z satisfies this rule.

PYTHON
age = 20

if age >= 18:
    print("Adult")

JAVASCRIPT
let age = 20;

if (age >= 18) {
    console.log("Adult");
}

C++
#include <iostream>
using namespace std;

int main() {
    int age = 20;
    if (age >= 18) {
        cout << "Adult";
    }
    return 0;
}

What a data type specifies · four things

1. The kind of values that can be stored
2. The operations that can be performed on them
3. The amount of memory required for storage
4. The interpretation of the stored data

Formally, a data type defines a set of values and a set of permissible operations.

Importance of data types · four points

1. Improve program correctness · they prevent invalid operations
2. Improve reliability · type checking detects errors before execution
3. Improve efficiency · the compiler can optimize memory allocation when types are known
4. Enhance readability · proper use makes programs easier to understand

The three categories of data type

USER-DEFINED TYPES IN THREE LANGUAGES

C++       struct Student {
              string name;
              int    age;
          };

Python    class Student:
              def __init__(self, name, age):
                  self.name = name
                  self.age  = age

JavaScript class Student {
               constructor(name, age) {
                   this.name = name;
                   this.age  = age;
               }
           }

Static vs dynamic typing LIKELY QUESTION

C++    int x = 10;
       x = "CMS710";     ← COMPILATION ERROR

Python x = 10
       x = "CMS710"      ← perfectly legal

Strong vs weak typing · a different axis

Data abstraction

Definition: hiding implementation details while exposing only essential features, so programmers focus on what an object does rather than how it is implemented.

The car analogy from the notes: a driver uses the steering wheel, accelerator and brake without needing to understand the internal engine mechanisms. Similarly, programmers interact with data structures through well-defined interfaces.

Four benefits: simplicity (reduces complexity) · reusability (abstract components can be reused) · maintainability (changes to implementation do not affect users) · security (internal details remain hidden).

The three principles of data structures

1. Efficient organization of data · searching an unsorted array may require scanning every element, while a binary search tree may require far fewer comparisons.
2. Abstraction of complexity · a programmer may use a stack without understanding its internal memory allocation.
3. Trade-off between time and space · improving speed often requires more memory; reducing memory may increase processing time.

Abstract Data Types

An ADT specifies the data it stores and the operations that can be performed, without specifying implementation. The Stack ADT declares Push(), Pop(), Peek() and IsEmpty() · and does not specify whether the stack is built from arrays, linked lists or dynamic memory.

Four advantages of ADTs: abstraction (reduces complexity) · reusability (can be implemented in multiple ways) · maintainability (implementation can change without affecting users) · modularity (encourages separation of concerns).

The four linear structures

Arrays: fast access and simple implementation, but fixed size and costly insertion/deletion. Lists: dynamic and flexible, but extra memory overhead and slower than arrays for some operations.

Each structure in three languages

ARRAY / LIST
Python      scores = [70, 80, 90, 85, 95]
JavaScript  let scores = [70, 80, 90, 85, 95];
C++         int scores[5] = {70, 80, 90, 85, 95};
            vector<string> students;    // dynamic

STACK
Python      stack = []
            stack.append(10); stack.pop()
JavaScript  let stack = [];
            stack.push(10); stack.pop();
C++         #include <stack>
            stack<int> s;
            s.push(10); s.pop();

QUEUE
Python      from collections import deque
            queue = deque()
            queue.append(10); queue.popleft()
JavaScript  let queue = [];
            queue.push(10); queue.shift();
C++         #include <queue>
            queue<int> q;
            q.push(10); q.pop();

BINARY TREE NODE
Python      class Node:
                def __init__(self, value):
                    self.value = value
                    self.left  = None
                    self.right = None
            root = Node(50)

C++         class Node {
            public:
                int   value;
                Node* left;
                Node* right;
                Node(int v) { value = v;
                              left = nullptr;
                              right = nullptr; }
            };
            Node* root = new Node(50);

A tree is a hierarchical structure of nodes connected by edges · root, parent, child, leaf. A binary tree has at most two children per node. Applications: searching, sorting, expression evaluation, database indexing.

PARSE TREE for the expression  a + b * c

            +
           / \
          a   *
             / \
            b   c

The parse tree shows that MULTIPLICATION
is evaluated BEFORE addition.

ABSTRACT SYNTAX TREE

        Assignment
        ├── Variable(a)
        └── Addition
            ├── b
            └── c

A parse tree represents the grammatical structure of a program according to the language grammar and is generated during syntax analysis. An AST is a simplified parse tree that removes unnecessary grammar details while preserving meaning. ASTs are used in compilers, interpreters, static analysis tools, code optimization systems and modern AI code assistants.

Where trees sit in the translation pipeline

The conclusion the module draws: trees are central to compiler and interpreter design. If a question asks why trees matter in a programming languages course rather than a data structures one, this table is the answer.

Control flow · the definition to memorise

Control flow refers to the order in which statements, instructions or function calls are executed in a program. It determines:

• Which instruction executes next
• Under what conditions execution changes direction
• How repetition occurs
• How data moves through program components

It is commonly represented using flowcharts, control-flow graphs or execution traces. Control structures are the mechanisms that govern it, and their design significantly influences program readability, software reliability, maintainability and execution efficiency.

The three principles of control structures

1. Program behaviour is determined by control structures · the same data and operations may produce different results depending on the sequence and conditions under which they execute.
2. Simplicity improves readability · Python emphasizes readability through simplified control constructs.
3. Abstraction reduces complexity · higher-level abstractions hide low-level control details: foreach loops, iterators, generators, recursive functions.

The four kinds of control flow

Selection has three types: single (execute a statement if a condition is true) · double (choose between two alternatives) · multiple (choose among several · the switch).
Advantages of selection: supports decision making · improves flexibility · enhances program intelligence.
Advantages of iteration: reduces code duplication · improves efficiency · simplifies repetitive tasks.

Sequence vs iteration TEST Q1

SEQUENCE              ITERATION
x = 10                for i in range(5):
y = 20                    print(i)
z = x + y
print(z)              prints 0 1 2 3 4
                      · one statement, five executions
Executes 4 statements,
each exactly once.

The three loops

Python      for i in range(5):
                print(i)

JavaScript  for (let i = 0; i < 5; i++) {
                console.log(i);
            }

C++         for (int i = 0; i < 5; i++) {
                cout << i;
            }

Python      count = 1
            while count <= 5:
                print(count)
                count += 1

Recursion is a control mechanism in which a function calls itself to solve a problem. A recursive solution consists of a base case, which terminates the recursion, and a recursive case, which calls itself with a smaller problem.

Python      def factorial(n):
                if n == 1:
                    return 1
                return n * factorial(n - 1)

JavaScript  function factorial(n) {
                if (n === 1) { return 1; }
                return n * factorial(n - 1);
            }

C++         int factorial(int n) {
                if (n == 1) return 1;
                return n * factorial(n - 1);
            }

Scope determines where a variable can be accessed within a program. It is fundamental because it controls variable visibility and lifetime.

Importance of scope · four points: prevents naming conflicts · enhances security · improves maintainability · supports modular design.

Variable lifetime refers to the period during which a variable exists in memory. A variable's lifetime depends on scope, storage allocation method and program execution state.

• Global variables typically exist throughout execution.
• Local variables exist only while their function executes.

C++ pass-by-value        C++ pass-by-reference
void increment(int x) {  void increment(int &x) {
    x++;                     x++;
}                        }
original unchanged       original modified

Python pass-by-object-reference
def modify(lst):
    lst.append(100)      ← the original list IS modified

Data flow

Data flow refers to how information moves through a program · between variables, functions, modules and program components. Most programs follow the Input → Processing → Output model:

number = int(input())
square = number * number
print(square)

    User Input
        ↓
     Variable
        ↓
    Processing
        ↓
      Output

Imperative vs functional control flow

Advantages of the functional approach: simpler code · improved abstraction · reduced side effects.

Structured programming, in this module's words, emphasizes sequence, selection and iteration while avoiding uncontrolled jumps such as excessive use of GOTO. Its benefits: improved readability (programs easier to understand) · improved reliability (errors easier to identify) · easier maintenance (modifications simpler).

1. Defining syntax and semantics with the same words. Syntax = structure, semantics = meaning.
2. Confusing the two typing axes. Static/dynamic = when checked; strong/weak = how strictly enforced. Python is dynamic and strong.
3. Saying a parse tree and an AST are the same. The AST is the simplified one, with grammar details removed.
4. Calling C++ interpreted or Python compiled. C++ is compiled, Python interpreted, JavaScript JIT/interpreted.
5. Giving stacks FIFO or queues LIFO. Stack = LIFO, queue = FIFO.
6. Describing a data type as only "a kind of value" · it is a set of values and a set of permissible operations.

7. Answering "differentiate" in prose. This examiner's questions all say compare or differentiate · use a table.
8. Omitting the example when the question says "with an example". Q2 and Q4 both demand one.
9. Treating scope and lifetime as the same thing. Scope is spatial (where), lifetime is temporal (when).
10. Saying recursion is always better. It is elegant but costs memory, risks stack overflow and is often slower.
11. Forgetting that a recursive function needs a base case · without it, infinite recursion.
12. Writing only C++. The course compares Python, JavaScript and C++ throughout; a comparison answer that names all three scores higher.