Programming Languages Theory¶

This guide breaks down how we talk to computers and why some problems are impossible even for the smartest machines.

What is a Programming Language?¶

Think of a Programming Language as a bridge between how humans think and how computers “think.”

Humans use complex languages like English or Spanish, filled with slang and emotions. Computers, however, are basically just billions of tiny light switches that are either On (1) or Off (0). A programming language allows you to write instructions that look like human words, which the computer then translates into those 1s and 0s.

Key Concepts¶

Syntax: These are the “grammar rules.” If you forget a semicolon (;) or a bracket, the computer gets confused and throws an error.
Abstraction: This is a fancy way of saying “making things simpler.” Instead of telling the computer exactly which electrical switch to flip, you just type print("Hello").

The “Halting Problem”¶

Imagine you have a super-smart app called The Checker. Its only job is to look at any program you write and predict one of two things:

“It will finish” (The program runs, does its job, and stops).
“It will run forever” (The program gets stuck in an infinite loop and never stops).

It is mathematically impossible to build a version of “The Checker” that works perfectly every single time. This is known as the Halting Problem.

Why can’t we build it?¶

It leads to a “Logic Paradox.” Imagine we programmed a new app that does the opposite of whatever “The Checker” says:

If The Checker says a program will stop, our new app is programmed to run forever.
If The Checker says a program will run forever, our new app is programmed to stop.

Now, what happens if we ask The Checker to analyze this new app?

If The Checker says it stops, the app is forced to run forever (making The Checker wrong).
If The Checker says it runs forever, the app is forced to stop (making The Checker wrong again).

Note

Because of this paradox, there are some things in math and logic that a computer simply cannot solve, no matter how powerful it is.

Quiz¶

Which concept refers to “hiding complex technical details behind simpler commands”?
- 1. Syntax
- 1. Binary Mapping
- 1. Abstraction
Why is the “Halting Problem” significant in computer science?
- 1. It shows there are logical limits to what can be computed
- 1. It proves that computers will eventually crash
- 1. It defines the speed of modern processors.
True or False: High-level languages interact directly with electrical switches without any translation.
- ( ) True
- ( ) False

Answer Key & Explanations¶

1: C (Abstraction)
- Explanation: Abstraction allows programmers to use high-level commands (like print) without knowing the physics of the CPU’s transistors.
2: A (Logical limits)
- Explanation: The Halting Problem is the foundation of computability theory; it proves that some mathematical truths cannot be reached by an algorithm.
3: False
- Explanation: High-level languages must be “compiled” or “interpreted” into machine code (binary) before a computer can execute them.

Formalisms for Computability¶

Abstract¶

Computability theory is the branch of computer science that deals with what can be calculated using an algorithmic process. This guide explores the mathematical formalisms that define the limits of computation and the Church-Turing Thesis.

The Turing Machine (TM)¶

Proposed by Alan Turing in 1936, the Turing Machine remains the standard formalism for defining an “algorithm.”

The Mathematical Components¶

A Turing Machine is formally defined as a 7-tuple containing a finite set of states, a tape alphabet, a transition function, and designated start and halt states.

The Infinite Tape: Represents unlimited memory, divided into discrete cells.
The Read/Write Head: Can move left or right, reading symbols and writing new ones based on its current state.
Deterministic vs. Non-Deterministic: While Non-Deterministic TMs (NTMs) can explore multiple computational paths simultaneously, they do not compute any functions that a standard Deterministic TM cannot.

Church’s Lambda Calculus¶

Developed by Alonzo Church, Lambda Calculus ($lambda$-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application.

Core Concepts¶

Abstraction: Building a function (e.g., $lambda x. M$).
Application: Applying a function to an argument (e.g., $M N$).
Beta Reduction: The process of calculating a result by replacing variables with their assigned values.

Lambda Calculus is the theoretical foundation of functional programming languages like Haskell and Lisp. It proved that computation could be represented entirely through functions without needing an explicit “tape” or “state.”

The Church-Turing Thesis¶

The Church-Turing Thesis states that a function is “effectively calculable” if and only if it can be computed by a Turing Machine or expressed in $lambda$-calculus.

Equivalence of Formalisms¶

Despite their radical differences in design—Turing Machines being mechanistic and Lambda Calculus being functional—it was proven that they are computationally equivalent. Any problem solvable by one is solvable by the other. This led to the concept of Turing Completeness.

The Halting Problem and Decidability¶

Not all functions are computable. The most famous example is the Halting Problem, which asks: “Given a description of an arbitrary computer program and an input, can we determine if the program will eventually stop or run forever?”

The Proof by Contradiction¶

Turing proved that a general algorithm to solve the Halting Problem for all possible program-input pairs cannot exist. This established that there are fundamental limits to what computers can ever achieve, regardless of processing power.

Quiz¶

Question 1: Turing Machine Mechanics¶

In a standard Turing Machine, what determines the next action (write a symbol, move the head, or change state)?

A. The current state of the machine and the symbol currently being read on the tape.

A random number generator within the tape.
The total length of the tape.
The speed of the processor.

Question 2: Turing Completeness¶

What does it mean for a programming language to be “Turing Complete”?

It can run on any operating system.
It has reached its final version and no longer needs updates.
It is written in binary code.

D. It is capable of simulating any Turing Machine, meaning it can compute any function that is algorithmically possible.

Question 3: The Halting Problem¶

Which of the following best describes the significance of the Halting Problem?

It proved that computers will eventually become smarter than humans.

B. It established that there are certain well-defined problems that no computer program can solve.

It provided a way to fix infinite loops in modern software.
It defined the maximum amount of RAM a computer can use.

Question 4: Lambda Calculus Foundations¶

Which programming paradigm is most directly derived from the formalisms of Lambda Calculus?

Imperative Programming (e.g., C, Assembly)
Object-Oriented Programming (e.g., Java, C++)
Functional Programming (e.g., Haskell, Lisp)
Database Query Languages (e.g., SQL)

Answer Key and Technical Explanations¶

Answer to Question 1¶

Correct Answer: A

Explanation: The transition function ($delta$) takes the current state and the current symbol as input to decide the machine’s next move. This is the core of deterministic computation.

Answer to Question 2¶

Correct Answer: D

Explanation: A language is Turing Complete if it can compute anything a Turing Machine can. Most modern languages (Python, C++, etc.) are Turing Complete, provided they have access to enough memory.

Answer to Question 3¶

Correct Answer: B

Explanation: The Halting Problem is not able to be proved or disproved. Logic itself has limits. We cannot build a program that perfectly predicts the behavior of all other programs.

Answer to Question 4¶

Correct Answer: C

Explanation: Functional programming treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data, mirroring the structure of $lambda$-calculus.

Coding Styles¶

Difference between coding styles¶

Overview¶

Programming languages are very important for software development, and each was created for a certain use cases. Python, JavaScript, and C++ are some of the most frequently used languages today; all three have different characteristics that make them more or less desirable for a certain use. This document compares these three languages in many ways:

Typing discipline
Syntax style
Memory management
Use case focus
Naming conventions
Error handling

Typing Discipline¶

Typing defines how a language handles variable types:

Python and JavaScript: Dynamically typed; variables can change types at runtime. This contributes to rapid development but can result in runtime errors if not properly restricted.
C++: Statically typed; the type of every expression is known at compile time. This improves performance and safety, making C++ a preferred language for systems programming.

Syntax Style¶

Python: Uses indentation-based syntax. Whitespace is essential for readability and structure.
JavaScript and C++: Use braces and semicolons to define code blocks and statements. This allows more freedom but can lead to unclean code if not formatted correctly.

Programming Paradigms¶

All three languages support multiple paradigms:

Procedural
Object-oriented
Functional

These options allow developers to choose the most appropriate style for their problem domain.

Memory Management¶

Python and JavaScript: Use automatic garbage collection to manage memory allocation and deallocation.
C++: Uses manual memory management, offering more control over system resources. This is ideal for performance-critical applications but can be error-prone.

Use Case Focus¶

Python: Excellent for scripting, data science, and machine learning due to its simplicity and rich ecosystem.
JavaScript: Ideal for web development, enabling dynamic client-side interactions and server-side programming.
C++: Preferred for systems programming, game development, and high-performance applications.

Naming Conventions¶

Python: Uses snake_case for variables and function names.
JavaScript: Uses camelCase, following web development conventions.
C++: Uses both PascalCase and camelCase, depending on context and coding standards.

Error Handling¶

Python and C++: Use exceptions to catch and handle errors.
JavaScript: Supports try/catch blocks and promises for flexible error handling.

Conclusion¶

Python, JavaScript, and C++ each bring unique strengths to software development:

Python: Readability and ease of use for rapid development and data analysis.
JavaScript: Versatility in web environments, both front-end and back-end.
C++: High performance and control for system-level programming.

Understanding these differences helps developers choose the right language for their projects, balancing productivity, performance, and maintainability.

Feature	Python	JavaScript	C++
Typing	Dynamic	Dynamic	Static
Syntax Style	Indentation-based	Braces and semicolons	Braces and semicolons
Paradigm	Multi-paradigm	Multi-paradigm	Multi-paradigm
Memory Management	Automatic (GC)	Automatic (GC)	Manual
Use Case Focus	Scripting, data science	Web development	Systems, performance apps
Common Naming Style	snake_case	camelCase	PascalCase / camelCase
Error Handling	Exceptions	Try/catch, promises	Exceptions

Python vs. Prolog: The Quest for Logic¶

“How” vs. “What”¶

As a Python developer, you are a Chef. You write a recipe: “First chop this, then sauté that, if it smells burnt, lower the heat.” This is Imperative Programming. You manage the state of the kitchen every step of the way.

In Declarative Programming (like Prolog), you are a Travel Agent. You describe the desired outcome: “I want a vacation that is tropical, under $2,000, and has a gym.” You don’t tell the agent which flight paths to take; you describe the constraints, and the system finds a solution that fits.

The Building Blocks¶

While Python relies on functions that return values, Prolog relies on a Knowledge Base built of three things:

Facts (The Data) Facts are “atoms” of truth. They don’t need logic to be true; they just are.
- Prolog: is_wizard(gandalf).
- Python equivalent: A value in a dictionary or a row in a database.
Rules (The Logic) Rules use the “implication” operator :-, which translates to “is true if”.
- can_cast_spell(X) :- is_wizard(X), has_staff(X).
- Translation: “X can cast a spell if X is a wizard and X has a staff.”
Unification (The Matching Engine) In Python, = is assignment (putting a value in a box). In Prolog, it is Unification. It asks: “Can I make these two things look the same?” If you ask Prolog wizard(X) = wizard(gandalf), it concludes that $X = gandalf$ to make the statement true.

Comparing the Logic: The “Quest Party” Example¶

Let’s build a system to determine who is in a “party” together based on their current location.

The Python Way (Imperative)¶

In Python, we have to manually iterate and filter. We are responsible for the “search” logic.

# The Data
locations = {
    "Frodo": "Shire",
    "Samwise": "Shire",
    "Merry": "Shire",
    "Aragorn": "Rivendell",
}

def get_party_members(location_name):
    party = []
    for person, loc in locations.items():
        if loc == location_name:
            party.append(person)
    return party

# Usage:
print(f"People in the Shire: {get_party_members('Shire')}")

The Prolog Way (Declarative)¶

In Prolog, we define the relationships. The “search” is built into the language engine itself via Backtracking.

% Facts
at_location(frodo, shire).
at_location(samwise, shire).
at_location(merry, shire).
at_location(aragorn, rivendell).

% The Rule: X and Y are in a party if they are at the same place P
% and X is not the same person as Y.
in_party(X, Y) :-
    at_location(X, P),
    at_location(Y, P),
    X \= Y.

Backtracking and Reversibility¶

This is where the magic happens. In Python, your get_party_members function is a one-way street: it takes a location and returns people.

In Prolog, the exact same code works in any direction:

Who is in Frodo’s party? Query: ?- in_party(frodo, X). Result: X = samwise, X = merry.
Find every possible pair in any party: Query: ?- in_party(X, Y). Result: (Prolog lists every valid combination it can find by “Backtracking”).
Is there anyone in a party at the Shire? Query: ?- in_party(X, Y), at_location(X, shire).

Prolog uses Backtracking: if it picks a person who has no party members, it “rewinds” its decision, goes back to the last successful step, and tries a different path automatically.

Summary Comparison¶

Feature	Python (Imperative)	Prolog (Declarative)
Primary Tool	Functions & Objects	Facts & Rules
Execution	Line-by-line (Step-by-step)	Resolution & Backtracking
Variables	Can change (Mutable)	Once bound, they stay (Immutable)
Success/Failure	Returns a value or Error	Finds a solution or returns `false`

Note

Python is a “General Purpose” powerhouse—best for web servers, apps, and data science. Prolog is a specialist—best for scheduling, AI logic puzzles, and complex constraint-solving.