Functional Programming Languages

The functional programming paradigm represents a fundamental shift in software design. While imperative languages abstract the manipulation of a machine’s state through changing variable values, functional languages are based on mathematical functions that map a domain to a range. By mimicking mathematics, these languages eliminate side effects, making programs more predictable and easier to test.

Functional Programming Languages

Core Characteristics of Pure Functionalism

A purely functional language does not support the concept of “state” as we know it in C++ or Java. This leads to several defining traits:

• Referential Transparency: Given the same parameters, a function is guaranteed to produce the same result every time.
• No Side Effects: Evaluation of an expression does not change the value of any variable or affect the environment outside the function.
• No Variables: By disallowing the concept of assignment, programmers avoid unintended state changes.
• Recursion over Loops: Because there are no counters or state variables, repetition is achieved through recursion rather than iterative loops.

Mathematical Foundations

In functional design, unnamed function definitions are represented as lambda expressions (e.g., (λ(x) x · x · x)(2)). Higher-order functions, or functional forms, allow functions to take other functions as parameters or yield them as results.

• Function Composition: Combining two functions such that the output of one becomes the input of another (h ≡ f ∘ g).
• Apply-to-all: Applying a specific function to every element in a list

The LISP & Scheme Landscape

Developed by John McCarthy at MIT in 1959, LISP (List Processor) is the oldest and most widely used functional language. Scheme, a dialect developed in the mid-’70s, is a smaller, statically scoped version of LISP frequently used in education.

Data Structures: Atoms and Lists

LISP recognizes two primary categories of data objects:

1. Atoms: Numeric values (e.g., 10) or symbolic values (e.g., a).
2. Lists: Stored as linked structures, these can be simple (containing only atoms) or nested (containing other lists).

Cambridge Polish Notation

Functions in Scheme use a specific list notation where the function name appears first, followed by its parameters.

Six rows covering everything fundamental — the four operators, how nesting replaces precedence rules, and how to define a function.

Control and Logic in Scheme

Scheme provides standard relational functions (=, <, >, ≤, ≥) and Boolean operations (not, or, and). For non-numeric data, it uses eq? or equal? to check for identity.

Conditional Statements

• If Statement: A 1 or 2-way branch used for simple logic.
• Cond Statement: A multi-way branching structure used for more complex conditions, similar to a “switch” or “if-else-if” ladder

Essential List Functions

The power of Scheme lies in its ability to manipulate lists using a small set of primitives.

• quote or ': Prevents the interpreter from evaluating a list as a function call.
• car: Returns the first element (the Head) of a list.
• cdr: Returns the remainder of the list (the Tail) after the first element.
• cons: Joins an atom or list to the front of another list.
• append: Merges two lists into one

Evaluation Models: Strict vs. Lazy

A key design difference between functional languages is how they evaluate parameters.

• Strict Evaluation: Every parameter is evaluated before the function is called. The scheme uses this model.
• Lazy Evaluation: Sub-expressions are only evaluated when their values are actually needed. This allows for the creation of “infinite lists,” where values are generated on demand.

Intuition Summary

• The Paradigm → Logic through mapping, not sequence.
• State → There is no state; only input and output.
• LISP/Scheme → Every operation is a list processing task.
• Immutable Objects → Once a value is defined, it cannot be changed.

For those interested in hands-on practice, Racket is a popular modern implementation of Scheme. You can experiment with the code in the Dr. Racket environment or use online sandboxes like wescheme.org

🔙 Back to all notes
𝕏 Let’s Connect

Get Prajun Trital’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Backlinks:
Principles of Programming Languages