Video Summary - CS 4337- Ch 1- Part 2

Main ideas & concepts

1) Categories of programming languages (4 major categories)

The lecturer states that programming languages can be categorized into four major types:

Imperative programming languages
Functional programming languages
Logical programming languages
Markup programming languages (not treated as “programming languages” in the lecture’s framing)

Imperative programming languages

Key characteristics/requirements

Programs use variables.
Programs use assignment statements.
Programs include iteration constructs.

Order of execution

To write a program, you must specify the order of execution.

Default execution order is sequential
It can be changed using control structures such as:
- if/else
- for loops
- while loops
- (and similar constructs)

Program state

The program has a state, defined as:

The collection of variables and their values at a specific time.

This state changes during execution.

Illustrative state-change example

Example begins with assignments like:

x = 0
y = 5 (the lecture implies initial value changes over time)

Over time:

At time 0, state s0 includes variables and their initial values (x known; y undefined at that moment per the explanation).
After executing an instruction, state becomes s1 (y becomes 5).
At time 2, after executing a computation like x = x + y, state becomes s2 (x becomes 5; y remains 5).

Main lesson for imperative languages

Execution involves both:

an explicit control flow/order of execution
and changing state (variable values evolve step-by-step)

Functional programming languages

Core concept: based on mathematical functions

Computation is modeled using mathematical functions.

A function maps:

an element from a domain set
to an element in a range set

Example described

A “cube” function:

cube(x) = x * x * x

Applying it:

input 2 maps to output 8

How functions are written (as described)

Define a function with:

a function name
a parameter
a function definition/body using the operator expression (e.g., x * x * x)

Variables, assignment, and state

The lecturer emphasizes:

no variable assignment statements
no variables in the imperative/state sense

Because of this:

the value of x does not change
x is treated as a constant
there is no changing program state

Main lesson for functional languages

Programs are built from function evaluation, not mutable state.

Logical programming languages

Core concept: based on facts and rules

Programs are made of:

facts
rules

How queries work

The program receives a query (e.g., something like man x).

It consults the facts and rules and returns all values that satisfy the query.

Illustrative example

Facts like:

“Ali is a man”
“Jake is a man”

Query: “man x”

Output:

x = Ali
x = Jake (all matching values)

Main lesson for logical languages

Computation is answering queries via logical inference from facts/rules, rather than step-by-step execution.

Markup languages

Role

Markup languages are used to:

specify webpage content
design webpage structure

Example given:

HTML

The lecturer’s framing:

markup languages are not programming languages.

Implementation methods (how code becomes machine-executable)

The lecturer shifts to “implementation method” and reviews basic architecture concepts before explaining translation/execution approaches.

Terminology reviewed

Memory stores:
- data
- instructions
Processor provides primitive operations, referred to as macro instructions
High-level programs (e.g., Java) require translation because:
- the machine cannot directly understand high-level language

Translation to machine language + OS support

Stages/needs described:

Convert high-level program → machine language (0s and 1s) using compiler, interpreter, or a hybrid approach.
Use operating system services for:
- file management
- input/output operations
Perform linking and loading:
- link OS-provided components/program units with the program
- produce an executable image / load image
Execute the executable image.

Conversion/execution approaches (with structure differences)

1) Compilation

A compiler converts the whole high-level program to machine language first.
Then the machine code is executed afterward.

Pros noted:

better execution time because compilation and execution are separated

2) Pure interpretation

An interpreter processes the program statement-by-statement:
- read first statement
- translate to machine language
- execute it
- repeat for the next statement

Cons noted:

longer execution time because translation and execution happen together repeatedly

3) Hybrid implementation system (compromise)

Combines compiler-like and interpreter-like behavior.
The interpreter works on intermediate code (instead of the original source code):
- intermediate code improves performance vs pure interpretation

Detailed step-by-step: compilation process (as listed in the lecture)

Compilation stages

Lexical analysis
- converts characters in the source code into lexical units
- lexical units include:
  - identifiers
  - keywords
  - operators
  - punctuation/symbols
Syntax analysis
- transforms lexical units into a parse tree
- if there’s a syntax error:
  - parse tree cannot be built
  - syntax problem occurs
Semantic analysis
- uses the parse tree to generate intermediate code
- intermediate code is described as being similar to assembly
Code generation
- converts intermediate code to machine language (0s and 1s)
- the computer executes the machine language

Additional supporting elements

Symbol table
- stores information such as:
  - types of variables
  - keywords
Optimization
- aims to make the compiler output smaller and faster

Flow of interpretation (as described)

Interpretation flow (conceptual steps)

Interpreter reads the source code
For each statement:
- converts the statement to machine code
- executes it
- proceeds to the next statement and repeats

Performance note:

translation and execution occur together → longer execution time vs compilation

Flow of hybrid system (as described)

Hybrid flow (conceptual steps)

Compiler front-end components produce intermediate code:
- lexical analysis → lexical units
- syntax analysis → parse tree
- intermediate code generator → intermediate/assembly-like code
Interpreter then:
- reads intermediate code (instead of source)
- converts each intermediate/assembly instruction to machine code
- executes instruction-by-instruction