The Study of Programming Languages

Welcome

Hello • Manahuu • Olá • Hallo • こんにちは • Sawubona • 안녕하세요 • नमस्ते • Bonjour • مرحبًا • Merhaba • Aloha • Cześć • Mabuhay • سلام • Aaniin • Привет • ᎣᏏᏲ • 你好 • Dia duit!

Do you find it interesting that humans have so many different ways to express themselves? Even a single thought can be communicated in a multitude of ways.

This holds not only for human greetings but also for computations.

How many ways can you express the computation of summing the squares of the even numbers in a list? Let’s look at a few ways. One approach is to explicitly iterate through the list, checking each element to see if it is even, and if so, squaring it and accumulating the square into the final answer. This is the approach we need to take in Go:

func sumOfEvenSquares(a []int) int {
    total := 0
    for _, x := range a {
        if x % 2 == 0 {
            total += x * x
        }
    }
    return total
}

And in Lua:

function sumofevensquares(a)
  local total = 0
  for _, x in ipairs(a) do
    if x % 2 == 0 then
      total = total + x * x
    end
  end
  return total
end

And in Zig, it’s the most idiomatic way:

fn sumOfEvenSquares(a: []const i32) i32 {
  var total: i32 = 0;
  for (a) |x| {
    if (@mod(x, 2) == 0) {
      total += x * x;
    }
  }
  return total;
}

Another approach is to first filter (a.k.a. ”select”) the even numbers, then map the squaring operation over each of them, and finally reduce (a.k.a. “fold”) the plus operation over the filtered-and-squared values to produce the result. For example:

• Input List: [3, -2, 9, 51, 20, 8, 0, -31, 10]
• After filtering by (keeping) evens: [-2, 20, 8, 0, 10]
• After mapping the square function: [4, 400, 64, 0, 100]
• After reducing the sum function: 568

Most major programming languages have these operations built-in.

function sumOfEvenSquares(a) {
  return a.filter(x => x % 2 === 0).map(x => x**2).reduce((x, y) => x + y, 0)
}

function sumOfEvenSquares(a: number[]): number {
  return a.filter(x => x % 2 === 0).map(x => x ** 2).reduce((x, y) => x + y, 0)
}

def sum_of_even_squares(a)
  a.select{|x| x % 2 == 0}.map{|x| x * x}.reduce(0, :+)
end

func sumOfEvenSquares(_ a: [Int]) -> Int {
    return a.filter{$0 % 2 == 0}.map{$0 * $0}.reduce(0, +)
}

(defn sum-of-even-squares [a]
  (->> a (filter even?) (map #(* % %)) (reduce +)))

int sumOfEvenSquares(int[] a) {
    return IntStream.of(a).filter(x -> x % 2 == 0).map(x -> x * x).sum();
}

int SumOfEvenSquares(int[] a) {
  return a.Where(x => x % 2 == 0).Select(x => x * x).Sum();
}

fun sumOfEvenSquares(a: Array<Int>): Int {
    return a.filter { it % 2 == 0 }.map { it * it }.sum()
}

def sumOfEvenSquares(a: Seq[Int]): Int =
  a.collect { case x if x % 2 == 0 => x * x }.sum

function sumOfEvenSquares(a)
  sum(x -> x^2, filter(x -> x % 2 == 0, a), init = 0)
end

sumOfEvenSquares := method(a,
  a select(isEven) map(x, x**2) reduce(x, y, x + y) ifNil(return 0))

fn sum_of_even_squares(a: &[i32]) -> i32 {
    a.iter()
        .filter(|&&x| x % 2 == 0)
        .map(|&x| x * x)
        .sum()
}

sub sum_of_even_squares {
    sum0 map { $_**2 } grep { $_ % 2 == 0 } @_;
}

let sum_of_even_squares a =
    a
    |> List.filter (fun x -> x % 2 = 0)
    |> List.sumBy (fun x -> x * x)

Sometimes you can specify the filtering, mapping, and reducing functions without parameters:

sumOfEvenSquares :: [Int] -> Int
sumOfEvenSquares = sum . map (^ 2) . filter even

: sum-of-even-squares ( seq -- n )
    [ even? ] filter [ sq ] map sum ;

Sometimes the filtering and mapping can be expressed in a single construct known as a comprehension (which makes a new list at each step), or as a generator expression (which generates the list elements lazily):

def sum_of_even_squares(a):
    return sum(x**2 for x in a if x % 2 == 0)

def sumOfEvenSquares(a: Seq[Int]): Int =
  (for
    x <- a
    if x % 2 == 0
  yield x * x).sum

proc sum_of_even_squares(a) {
  return + reduce ([x in a] if x % 2 == 0 then x*x else 0);
}

function Sum_Of_Even_Squares (A : Integer_Array) return Integer is
begin
   return [for X of A when X mod 2 = 0 => X * X]'Reduce ("+", 0);
end Sum_Of_Even_Squares;

Some languages have really, really powerful operators for processing arrays:

sumOfEvenSquares ← {+/((2|⍵)=0)×⍵*2}

sumofevensquares: {+/x[&~x!2]^2}

function sum_of_even_squares(a) result(total)
  integer, intent(in) :: a(:)
  integer :: total
  total = sum((a**2) * merge(1, 0, mod(a, 2) == 0))
end function

function sumOfEvenSquares(a)
  sum((a[a .% 2 .== 0]).^2)
end

The examples above all express the operation using high-level programming languages. If you were working at a very low-level, say assembly language, the procedure might be a little harder to figure out. The parameters have to come from somewhere. And at a low-level, what even is an array? It’s actually a contiguous block of memory identified by two things: (1) the address of the block and (2) the number of elements! Here’s the function using ARM 64 Assembly, where the first parameter (the address) has been passed in register x0 and the array length in x1:

_sum_of_even_squares:               ; x0 = start of array, x1 = length
        mov     x3, x0              ; x3 = iterator, initialized to start
        add     x1, x0, x1, lsl 2   ; x1 = x0 + (x1 * sizeof(int)), end of array
        mov     w0, 0               ; w0 = total
        cmp     x3, x1              ; check if iterator already hit the end
        bhs     .done               ; if so, done
.again:
        ldr     w2, [x3], 4         ; w2 = next element, x3 += 4 (point to next)
        tst     w2, 1               ; test if it is even
        madd    w4, w2, w2, w0      ; w4 = w2 * w2 + total
        csel    w0, w4, w0, eq      ; if even, update total
        cmp     x3, x1              ; check if x3 reached end of array
        blo     .again              ; if not, continue loop
.done:
        ret

The programming language C is slightly more abstract than assembly language. We can specify parameters directly, and use variables rather than registers. But we still treat the array as an address, pass its length as a second parameter, and be explicit about memory addressing:

int sum_of_even_squares(int* a, size_t length) {
    int total = 0;
    for (int *p = a; p < a + length; p++) {
        if (*p % 2 == 0) {
            total += (*p) * (*p);
        }
    }
    return total;
}

The fact that there are a seemingly infinite number of approaches for even this simple problem make the study of languages interesting!

Why

Well that was sure a lot of languages. You are now either excited or overwhelmed. But if you have patience and perseverance and take on a study of programming languages, you will reap many benefits—professional, social, and academic.

Professional Benefits

Studying programming languages will help you in many ways! For instance, you will:

Express yourself better

Expertly wielding language allows you to communicate ideas powerfully. Programming is a form of written expression just like novels, short stories, technical manuals, wikis, screenplays, essays, dialogues, articles, and poetry. Just as knowledge of rhetoric can improve your prose, verse, and arguments, knowledge of programming languages improves your ability to express computations elegantly and precisely. Studying not only how-to-program, but the mathematical formalisms underlying language syntax and semantics, leads to expertise in writing precise and unambiguous specifications and implementations of information structures and processes.

Become a better technical decision-maker

Understanding a variety of languages and language paradigms enables you to make informed choices when selecting the most appropriate language for a given task, as some languages do a great job expressing some kinds of tasks and do a terrible job at others. Your study will enable you to describe design tradeoffs (garbage collection or not, compile-time type safety or not) and be able to articulate how exactly languages like Rust, Swift, and Zig compete against C and C++.

Learn new languages more easily

Thinking in terms of language independent concepts (e.g. types, sequencing, iteration, selection, recursion, concurrency, subroutines, parameterization, naming, scope, abstraction, inheritance, composition, binding, method dispatch, and so on), rather than in one particular language’s syntactic constructs (e.g., “if statement,” “while statement,” “virtual function”), enables you to adapt to any programming environment. A time will surely come when you will author programs in a language you never even heard about.

... Mastering more than one language is often a watershed in the career of a professional programmer. Once a programmer realizes that programming principles transcend the syntax of any specific language, the doors swing open to knowledge that truly makes a difference in quality and productivity. — Steve McConnell

Become more productive

If you know how and why a language was designed, you can:

• use a language’s features effectively, for the purposes they were designed
• choose the best and most efficient feature for the task at hand
• utilize some of its non-obvious powerful features
• simulate useful (and powerful) features from other languages that your language lacks
• understand obscure features
• understand weird error messages
• understand and diagnose unexpected behavior
• understand the performance implications of doing things a certain way
• have deep and effective conversations with AI code assistants and agents
• know when to and when not to trust the suggestions of AI code assistants and agents
• use a debugger effectively

Design (and implement!) your own language

There are many good reasons for creating new languages to solve problems (see this essay by Tom Van Cutsem). Even if you never create a “full programming language,” you might need to write your own little language as part of a larger application, for example:

• A query language for database access
• A query language for a search engine
• A calculator
• A console interface to an adventure game

Expand your mind

You cannot grow when your thinking about programming is fixed. Study programming languages to encounter fascinating ways of programming you might never have even imagined before, achieving enlightenment as you deeply understand pattern matching, type inference, closures, prototypes, introspection, instrumentation, just-in-time compilation, annotations, decorators, memoization, traits, streams, monads, actors, mailboxes, comprehensions, continuations, wildcards, regular expressions, proxies, and transactional memory.

Exercise: What is a monad? What is a continuation?

Your study will lead you to embrace languages, and programming environments, that may be different than you’ve ever imagined. You do know about eToys, right?

Prepare yourself to build some stunning things

Imagine formally-verified compilers, formally-verified hardware, formally-verified programs, the world’s smartest and fastest IDE, code generators from specifications, block-programming environments that actually work, and so on. To build programs that manipulate and build other programs, you need the deep understanding of what programs are, and this comes from studying the field of Programming Languages.

So basically, you will become happier and make more money.

Social Benefits

Studying programming languages may even enable you to:

• Participate in exciting academic and professional discussions at meetups and conferences, making new friends.
• Socialize with researchers in linguistics, psychologists, neuroscientists, and people interested in communication, making even more new friends.

  Key discoveries have been made by archaeologists when digging in the ground, psychologists listening to children, computer scientists simulating language change, ethnologists watching apes, and linguists taking language apart. The pile of new puzzle pieces from their work has been added to by geneticists decoding human genomes and neuroscientists peering inside the brain. — Steven Mithin, The Language Puzzle

• Make a difference in the world, with a programming language you design yourself, gaining followers and subscribers.
• Impress your friends with esoteric, geeky, fun, and sometimes arcane knowledge, gaining admirers.

  

Academic Benefits

Programming Language Study is one of the 17 knowledge areas of computer science as defined by the ACM, IEEE-CS, and AAAI their 2023 Computer Science Curriculum.

Browse the knowledge area list now, and take a peek at the full document for the Foundations of Programming Languages knowledge area. You might find the study of language, especially some of the theoretical aspects, to be even more fundamental than the favorite of job interviewers—Data Structures and Algorithms. Language theory directly deals with how information itself is expressed, organized, and manipulated. Without a way to represent data or computation, we really wouldn’t have computer science. And the part of computer science that language theory studies is really fun: it’s about people expressing themselves in all kinds of fascinating ways.

Programming Languages is not Programming

Let’s face it: agents do most of the turning specifications into code. Humans engineer software systems. Getting the agents to write the right code is your job. Understanding what they write is your job. Adding your own code is your job. You need to know the deep foundations of multiple languages to be effective at your job.

But maybe you are reading these notes not because you want a job engineering software, but because you like learning. That’s wonderful too! There is a great deal that studying programming languages can tell us about human language. And knowledge is fun. And empowering.

And finally, it is only with deep theoretical knowledge that you can be positioned to create what comes next. There is always a “next” that comes beyond the current state of the art.

How

Self-check time! Make sure you know what a programming language is.

Yes, that link was to a Wikipedia article. Did you read the article? No? Read it. Now? Okay, let’s lay out a study plan.

An effective study of programming languages has these five dimensions:

The rest of these introductory notes provide a whirlwind introduction to each of these five items, in this order:

1. History
2. Learning (Specific) Languages
3. Learning (Language-independent) Concepts
4. (Mathematical and Logical) Foundational Theories
5. Pragmatics

History

Your study of programming languages is enhanced when done in a historical and human context. There have been many books and articles written on the History of Programming Languages (HOPL). It’s really fascinating! And super important, too. Perhaps you’ll find it exciting too.

We can’t cover the entire field here, but we can provide just enough of the highlights to give you a sense of where the languages of today came from:

Antiquity to the 1700s

Early computing recipes were written in prose.

1700s-1940s

In 1804 Jacquard patents the Jacquard Machine and in the 1850s Ada Lovelace publishes her Bernoulli numbers program for the Analytical Engine. Plankalkül is designed in the early 1940s but never gets popular. It’s a high-level language, yes, but mostly symbolic.

1950s-1960s Rise of natural language-like languages

Grace Hopper leads the COBOL effort (business computing), John McCarthy leads Lisp (AI), and John Backus leads Fortran (scientific computing). Early Algol becomes popular and eventually we get behemoth multi-purpose languages like Algol 68 and PL/1.

1970s The structured programming revolution begins

Languages providing information hiding, such as Modula, CLU, Simula, Mesa, and Euclid attempt to address the “software crisis.” Structured and modular features are bolted on to earlier languages.

1980s Object-orientation takes over the world

Though begun in the 1960s with Simula and refined in the 1970s at Xerox PARC with Smalltalk, OO—or approximations to it—explodes in the 1980s with C with Classes (since renamed C++), Objective-C, Eiffel, and Self. Earlier languages such as Lisp and Pascal gain OO features, becoming Common Lisp and Object Pascal, respectively.

1990s The World Wide Web appears

Perl becomes popular. Java, JavaScript, and PHP are created with web applications in mind.

2000s: Interest in established dynamic languages such as Ruby takes off

Scala shows that static languages can feel dynamic. Clojure arrives as a dynamic, modern Lisp, leveraging Java’s virtual machine.

2010s: Old things become new again

Multicore processors and “Big Data” revive interest in functional programming. Older languages such as Python and R, and the newer Julia language, find use in data science. Net-centric computing and performance concerns make static typing popular again as Go, Rust, Swift, and Zig challenge C and C++ for native applications.

2020s: People are talking about AI again

Mojo is created with direct support for AI, and particularly machine learning, applications, allowing programmers to not have to employ a variety of external packages to get their work done.

Overviews are nice, but you’ll need to go much deeper. These sources will get you started:

• Wikipedia’s article on the History of Programming Languages
• List of recommended reads from a Hacker News question

Many people don’t realize what incredible work happened in the 1960s and 1970s. Learn about this era in this informative and entertaining look into what this work could have turned into, so much sooner than it did, if only people had carried out the visions:

Follow up with your own web searches for “History of Programming Languages” or “Evolution of Programming Languages.”

Language Diversity

Your study of programming languages is also enhanced by becoming a polyglot—writing a lot of programs in a lot of languages, and learning each of those languages deeply. By doing so, some of the important linguistic concepts will naturally emerge. But which languages should you learn, and what should you learn about them? A good place to start is to note:

• Whether a language is significant or not. A significant language is one that has had a major impact on the design of future languages, or happened to, regardless of any merits of its own, come into widespread use.
• The context in which the language was designed. Perhaps it was designed to solve a particular problem or address a particular problem domain. You might even track the evolution of the language over time, as intended application areas may change over the life of the language.

Understanding a language’s motivation for existence is essential. It is unfair to criticize a language for doing a bad job in an area which it was never intended to be used for.

Some Significant Languages

Here are a few languages that for some reason or another rate as significant. The reasons why they are grouped the way they are shown here will be discussed in class:

• Fortran (I, II, IV, 66, 77, 90, 95, 2003, 2008, 2018, 2023)
• Lisp, Scheme, Common Lisp, Clojure
• COBOL (60, 68, 74, 85, 2002, 2014, 2023)
• Algol (58, 60, W, 68), Pascal, Modula (2, 3), Oberon
• PL/I
• APL, J, K, Q
• BASIC
• Clu, Alphard, Euclid, Mesa, Cedar, Turing, Ada (83, 95, 2005, 2012, 2022)
• Forth, Factor
• BCPL, B, C (K&R, 90, 99, 11, 17, 23), C++ (98, 11, 14, 17, 20, 23, 26), D, Rust, Zig, Odin
• Java, C#, Scala, Kotlin
• Perl, PHP, Hack, Tcl, Python, Ruby, Groovy, Lua
• Simula, Smalltalk (72, 74, 76, 80), Object Pascal, Eiffel
• Concurrent Pascal, Occam, Linda, SR, Erlang, Elixir, Go, Chapel, Gleam
• Objective C, Swift
• Self, JavaScript, ActionScript, CoffeeScript, TypeScript
• Standard ML (90, 97), CAML, Ocaml, F#
• Miranda, Haskell, PureScript, Elm
• Gallina, Agda, Lean, Idris
• Prolog, Mercury
• Snobol, Icon
• Id, Val, Sisal
• SQL
• Postscript
• Verse
• Mojo
• MATLAB, R, Julia
• Intercal, Unlambda, LOLCODE, ArnoldC, Brainfuck, Malbolge, Befunge, Piet, Whitespace
• GolfScript, Pyth, CJam, Jelly, 05AB1E, Vyxal

Motivation

Here are some languages and their motivations for being created. In some cases, the language found a niche outside the purpose for which it was designed. But the point is that some problem was seen as significant enough to warrant a new language.

• Fortran — Numeric computation
• LISP — Symbolic computation, artificial intelligence
• COBOL — Business computation
• Algol 60 — Algorithmic description
• APL — Array processing with a concise mathematical notation
• Algol 68 — Kitchen sink of programming language features
• Pascal — Teaching structured programming
• Modula — Modular programming
• C — Systems programming
• SQL — Database applications
• Scheme — To simplify Lisp
• Prolog — Expert systems; Natural language processing
• Smalltalk — Workstation GUI programming
• MATLAB — Numeric computation without having to use Fortran
• Ada — Megaprogramming; Embedded systems
• C++ — Simulation
• ML — Theorem proving
• Perl — Scripts, with a focus on text processing
• Erlang — Massively scalable, reliable, soft realtime systems
• Python — To be an extensible scripting language
• Ruby — To be the language Matz wanted (and better than Perl)
• Lua — General-purpose scripting
• K — Ultra high-performance numerical (typically financial) analysis
• R — Statistical and graphical Computing
• Java — Compact downloadable executable components
• C# — To be the Java of the Microsoft (.NET) world
• JavaScript — Client-side scripting for web applications
• PHP — Server-side scripting for web applications
• Postscript — Formatting of printed documents
• Haskell — Unifying the best of existing functional languages
• Io — Dynamic language experimentation
• Scratch — Creating and sharing interactive stories, games, music, and art
• Scala — Supporting both object-oriented and functional programming
• F# — Solving complex problems simply
• Clojure — To be a modern Lisp-dialect for the JVM
• Nim — Expressivity in a systems programming language
• CoffeeScript — To be a better JavaScript
• Dart — To be a better language for modern (web) apps
• Go — To build large distributed, interconnected systems
• ParaSail — Safe, secure, highly parallel applications
• Chapel — Parallel programming at scale
• Rust — Large, safe, network clients and servers
• TypeScript — Large-scale JavaScript applications
• Quipper — Functional programming for Quantum computers
• Hack — To do PHP-compatible things while keeping your sanity
• Elm — To be a “delightful language for reliable webapps”
• Elixir — Modernizing and extending Erlang
• Kotlin — Fixing and improving Java
• Julia — Scientific computing in a dynamic language with near compiled-language speed
• Crystal — High expressiveness together with speed and safety
• Swift — Because it was time to make something more fun than Objective-C for iOS apps
• Zig — Safety, efficiency, and reusability
• Gleam — Type-safe systems that scale
• Ballerina — To compose network services for cloud computing
• Grain — Support for web applications in a modern language
• Verse — Metaverse applications
• Mojo — AI and machine learning applications

Where to Learn More

Language lists, comparisons, and taxonomies:

• Wikipedia’s Programming Languages Article
• Wikipedia’s Programming Language Lists
• A site I am making (with help from students—you can contribute, too!)
• PLangs! a curated resource for exploring programming languages and tools, kept up-to-date
• Hyperpolyglot
• Learn X in Y Minutes
• Pixel’s Language Study with links to two great diagrams of language evolution and a great chart of syntax across languages
• Another Diagram of Language Evolution (seems to have stalled at 2020)
• A Timeline of Programming Languages (stalled at 2015 last I checked)
• The Programming Languages Category Page at RosettaCode

Concepts

An important part of language study is a deep understanding of language-independent concepts. The vocabulary around programming languages is massive, so how can you organize all this knowledge you will be gaining?

The Big Picture

Let’s begin with some critically important terminology that underlies the study of programming languages. It is time for a vocabulary fire hose. You can handle it.

A language is a structured system of communication.

A programming language is a language for expressing computation.

A computation is a determination of new information from existing information by formal, logical, mathematical, mechanical means, carried out by a sequence of steps, each of which takes a finite amount of time and resources.

The expression of a particular computation in a programming language is called a program.

Code

You can call a program, or a collection of programs making up a system, the “code.” But please don’t call a program “the codes.”

Information is that which informs.

Usable information is representable as strings of characters over some alphabet. Today, virtually every information system uses the Unicode alphabet. Here are some example strings that give evidence that Unicode is sufficient for anything of interest to us:

91332.3e-81
⚠️ Stay BEHIND the yellow line! ⚠️
<ul><li>你好</li><li>ᎣᏏᏲ</li><li>ᐊᐃᓐᖓᐃ</li></ul>
/Pecs/Los Angeles/Berlin/Madrid//1 2/3 0/2 2/2 0/3 2///
(* (+ 88 3) (- 9 57))
int average(int x, int y) {return (x + y) / 2;}
{"type": "dog", "id": "30025", "name": "Lisichka", "age": 13}
∀α β. α⊥β ⇔ (α•β = 0)
1. f3 e5 2. g4 ♛h4++

Each character in Unicode can be encoded into bits. The most widely used encoding for characters today is UTF‑8. Information in the form of character strings is good for humans; information reduced to (encoded) bit strings is better for processing and transmission by machines. Example: The character CHEROKEE LETTER O, written as Ꭳ, is encoded in UTF-8 as 111000011000111010100011.

Information is chunked into meaningful units called values. Values can be characters, numbers (e.g., 389.221E-25), or atoms (e.g., true, false, null, north, south, blue), as well as composite values such as tuples, records, lists, sets, dictionaries, references, functions, and more. Values inhabit types which classify values by their shared behavior.

Programs are built from entities such as declarations, expressions, statements, literals, variables, functions, procedures, coroutines, threads, processes, modules, and packages. Entities refer to, store, or manipulate values.

Values vs. entities

It is sometimes easy to get confused between values, literals, and variables. This should help: values are pure information that exist outside of a program. Entities are program constructs that live inside the program: entities are the components from which programs are constructed. Literals and variables (both of which are entities) stand for and contain values, respectively.

Statics and Dynamics

The statics of a language defines how to construct programs out of entities, and specifies what we can know about a program before running it.

A language’s statics is generally defined in two parts: the syntax describes how the entities are arranged, structurally, to form a valid program, and a set of contextual rules that determine which valid arrangements are meaningful and which are not.

The dynamics of the language describes the computational effects of programs during execution.

Here’s the key idea: A running program is made up of one or more lines of execution. Each line of execution is a sequence of statements that are executed one after the other. Within each line, computation proceeds according to various types of control flow. The study of the communication and coordination between lines of execution is known as concurrency.

We’ll be studying control flow in more detail here, and concurrency here. As a teaser, we’ll be exploring the following types of control flow:

and the following paradigms for concurrent programming:

The Big Questions

Now, before we can begin to organize all this knowledge, we’ll want to ask some pretty deep, philosophical questions, that will help to motivate an ontology, or at least the beginnings of one.

• What kinds of information units do we wish to store and process, and what are their behavioral capabilities? Typing
• How do we denote, or encode, these values? Representation
• How do we name the constructs that store and manipulate values? Binding
• How do we chunk information and computational procedures into larger units to better manage large systems? Abstraction
• How can we build entities that are customizable in some way? Parameterization
• How do entities emit and respond to events? Communication
• How do we synchronize various sub-computations? When do we require sequential execution and when do we allow true parallel execution? Coordination
• How can computations know about themselves? Metaprogramming
• How can we know our programs always do what they should? Correctness
• How do we know they never do what they should not? Security

Ontologies

When we start examining the little things, it’s nice to organize concepts into an ontology. There are many possible ontologies. Here’s a very rough one with eight top-level study areas. Don’t worry if most of these terms are completely unfamiliar.

• Naming. As in natural language, we often give names to entities to be able to refer to them. When we encounter a name, we need to know what it refers to.

  Binding (associating names with entities), scope (the region in space or time in which a binding is active), visibility, extent (the lifetime of a binding), storage class (“where” named entities are stored), linkage (how are names accessible from the outside), defining vs. referencing occurrences, overloading and aliasing, polymorphism (static vs. dynamic), bound vs. free names, shallow vs. deep binding, static vs. dynamic scope.

• Evaluation. Certain computations, known as expressions, produce values. Expressions are constructed from values and operators.

  Operators, precedence, associativity, fixity, arity, evaluation order (defined, undefined, short-circuit), side effects (lvalues vs. rvalues, initialization vs. assignment, assignables), eager vs. lazy evaluation, errors as values, types as values, macros.

• Control Flow. Certain computations, known as statements, produce effects. Statements organize computation in time into lines of execution, How can we organize the actions within lines so they occur when we want them to?

  Sequencing (comma, semicolon), selection (if, switch, match), iteration (for, while, forEach, takeWhile), recursion, procedural abstraction, functional abstraction, non-determinism, disruption (call, return, break, continue, throw, panic).

• Types. A value’s type constrains the way it may be used in a program. Types impose constraints on what we can and cannot say. How can we classify values so that they behave in certain, predictable ways?

  Type systems (fixed or extensible, extra-lingual vs values, first-class or not), basic, sum, and product types, types vs. classes vs. typeclasses, type expressions, type checking, type inference, type coercion, type equivalence, type compatibility, static vs. dynamic typing, strong vs. weak typing, manifest vs. inferential typing, nominal vs. structural typing, parameterized types (generics), covariance, contravariance, invariance, dependent types, higher-kinded types, universes.

• Functional Abstraction. Functions may just be the most important building block of good code. They abstract executable code into (often named) chunks so we can invoke them when needed. They can be parameterized, too!

  Procedures (abstractions for statements) vs. functions (abstractions for expressions), first-class functions, higher-order functions, closures, currying, partial application, function composition, lambda expressions, anonymous functions, function signatures (names, modes, types, patterns, defaults, rest parameters), parameters and arguments (exactly one parameter? Or zero to many? Exactly one return value? Or zero to many?), parameter association (positional vs. named, value vs. reference vs. name), recursion (direct vs. indirect), tail recursion.

• Modularity. Just like we can chunk code into procedures, we can chunk data as well. But not just data. When we bundle data and code together, we get something qualitatively more powerful. Modules divide a system into parts that can be developed, tested, and reasoned about independently, and often control the visibility and accessiblity of names and entities.

  Modules, packages, units, namespaces, classes, object orientation, import and export, open vs. closed, encapsulation, separate compilation.

  “Bob Barton, the main designer of the B5000 and a professor at Utah had said in one of his talks a few days earlier: "The basic principle of recursive design is to make the parts have the same power as the whole." For the first time I thought of the whole as the entire computer and wondered why anyone would want to divide it up into weaker things called data structures and procedures. Why not divide it up into little computers, as time sharing was starting to? But not in dozens. Why not thousands of them, each simulating a useful structure?” — Alan Kay

• Concurrency. In the real world, things don’t happen in a single line of execution. Events can occur at any time. Multiple things can happen at the same time. Many languages have features that enable us to express these situations clearly and coordinate these concurrent activities.

  Ontology of topics in concurrency.

• Metaprogramming. Generally, programs are written for some purpose or application area to answer questions for a user. For example, an application for a human resources professional might answer questions like “What is the average salary of employees in the marketing department?” But if the program can also answer ”How many local variables does this program contain, and what are their types?” then you are doing metaprogramming.Metaprogramming is writing programs that can answer questions about, and manipulate, programs (including themselves).

  Introspection, reflection, eval, decorators, metaclasses.

Theoretical Foundations

A study of just about anything can be enhanced with mathematical and logical precision. For programming languages, we want a way to specify, unambiguously, exactly what are the legal programs in a language, and what exactly they mean. Natural language is open to interpretation and fuzziness and ambiguity, so we would like to bring in some mathematical machinery as expressed in the study of logic and various mathematical and computational theories.

• Logic. Logic is the study of reasoning. It is used in programming languages to specify and reason about the behavior of programs.
• Type Theory. Type Theory is a theory used provide a rigorous foundation of mathematics, and of programming languages! It is a superior alternative to Set Theory as a foundation of mathematics, at least for computer science.
• Lambda Calculus. The λ-Calculus is a formal system for defining computation. It is based entirely around the notion of the function, which is why languages like Python and Java speak of certain functions as lambdas. The λ-Calculus is the theoretical foundation for Type Theory, and a massive influence on functional programming.
• Theories of Computation. Theories are an indispensable tool for doing science or any kind of exploration. A good theory organizes knowledge and provides us with explanatory and predictive powers. Language Theory is the study of how computations are expressed. Automata Theory is the study of abstract machines for carrying out computations. Computability Theory is the study of what can and cannot be computed. Complexity Theory is the study of quantifying resources (such as time and space) required for certain computations.
• Syntax. A programming language gives us a way structure our thoughts. A program’s structure is determined by the syntax of the language. The syntax defines which strings of characters are valid programs, and if valid, how the characters are grouped into words (called tokens) and how the words are grouped into phrases (such as declarations, expressions, statements, modules, and more). Syntactic formalisms are well understood in computer science and fluency with at least one formalism is an expectation of undergraduate computer science students and professional programers. Among those you will encounter in your study of programming languages are: BNF, EBNF, ABNF, plain old Context-Free Grammars, Syntax Diagrams, and (my favorite) Parsing Expression Grammars.
• Semantics. The semantics of a language gives meaning to its programs. We need to be able to precisely and unambiguously define the meaning (or effect) of every program. This requires a fair amount of mathematical machinery. Unlike syntax, for which formalisms are straightforward, mathematical approaches to semantics are generally undertaken only in graduate computer science courses. See the Wikipedia articles on Semantics and Semantics in Computer Science.

Pragmatics

Syntax and semantics are part of the formal specification of a programming language. But there’s another dimension that is equally important.

Pragmatic concerns must guide your design of a programming language, that is, if you want it to be easy to read, easy to write, and able to be implemented efficiently (all of which you do). Pragmatics encompasses:

• What the language values
• Who the language is for?
• Which applications the language is best suited for
• Its advantages and disadvantages relative to other languages
• Expressiveness and performance characteristics
• Common programming idioms (the good, the bad, and the ugly ways of doing things)
• An implied execution model, e.g., assignment-based, stack, combinator, data-flow, etc.
• Its standard library or libraries
• The ecosystem that evolved around the language, encompassing both programming environments such as IDEs, REPLs, workspaces, or playgrounds; and package management systems such as NPM for JavaScript, Pip for Python, Gems for Ruby, Rocks for Lua, Maven for Java, Cargo for Rust, Alire for Ada, and many more.

Vision and Values

We can think of a language’s value system as what it is that the language wants to be. The values stem from the vision of the designers and ultimately play a role in making a language learnable, usable, and maybe even successful. To get a sense of what this all means, see Ashley Williams’ amazing talk subtitled “How language values shape the features we build and the journeys we take to design them.” It focuses on JavaScript and Rust, but the ideas are universally applicable:

Evaluation Criteria

Reasonable people know that all languages have their pros and cons. But why are some things pros and other things cons? Under what criteria can we evaluate programming languages?

Technical Criteria

There are certain technical criteria. For example, is the language:

• Easy to read? Because:
  • Over 90% of programmer time is reading and modifying existing code
  • Labor costs dwarf hardware costs
  • If someone can’t understand existing code, it will get thrown away
• Easy to write? Because:
  • If the learning curve is too high, who would bother to use it?
• Highly Expressive? That would help reading and writing. Does the language have:
  • Operators like A = B + C which adds whole arrays in Fortran 90?
  • Abstract data types (with encapsulation)?
  • Module and package structures to aid programming-in-the-large?
  • A rich operator set, as in languages like APL and Perl?
  • Rich type/object structures supporting inheritance, composition and aggregation?
  • Polymorphism, overloading, aliasing?
  • Higher order functions?
  • Pattern matching?
  • Built-in control flow (e.g. unification, backtracking)?
  • Facilities for symbolic computation?
  • Support for asynchronous, concurrent, and distributed programming?
• Designed to make it impossible to making (some) stupid mistakes? Some languages do! For example you might see:
  • A requirement to declare variables and types detects spelling errors early
  • Simple iteration over collections vs. crazy-flexible for loops
  • Robust switches with pattern-match exhaustiveness vs. the abomination which is the C switch
  • Safe discriminated sum types vs. unsafe C unions
  • Languages without insecure features, such as user-specified pointer deallocation, pointer arithmetic, automatic coercions
  • Whitespace significance to prevent the classic Fortran 77 example

             DO 10 I = 1 . 5
               PRINT * "Hello"
          10 CONTINUE
    

• Designed to allow quick and incremental compilation? Because breaking a programmer’s flow by constantly hitting that compile button or having to run linkers, or such things get annoying.
  • If compilation is as fast as you can type, development time and cost can be greatly reduced.
  • If compilation can be incremental, there’s no need to recompile after making small changes.
  • If compilation can be quick, some compilation can be done at runtime to adapt to changing conditions.
• Amenable to efficient target code generation?
  • Languages with static scope and type checking keep the runtime system free from tons of work, e.g. no runtime variable lookup: all variable references have already been resolved to machine addresses.
  • Languages with no first-class functions allow for stack-allocation of frames.
  • Some languages are strongly influenced by hardware.
• Genuinely portable? Yes, we want our creations to spread!
  • Many languages have too many implementation dependencies.

Also see Wikipedia’s Programming Language Comparison article.

Non-Technical Criteria

There are non-technical, subjective criteria, too. Good and successful are not the same! Success comes from:

• Being the only language suitable for a specific problem
• Personal preference (no accounting for taste)
• Good development environments
• Fast compilers (not necessarily a language issue!)
• A massive ecosystem (like NPM or Maven or Pip or Gems)
• Patronage (support from a government or big company)
• “Everyone else is using it”
• “The boss made me use it”
• Economics and Inertia — “we already invested too much in this to change”
• Laziness — “I’m too tired to learn a new language”

Expressiveness

Expressiveness is a pragmatic concern, too, influencing how a language can be wielded to say what needs to be said. Some languages want to be verbose, low-level, or “close to the machine” and others want to be terse or expressive. At the beginning of these notes, we saw a function to return the sum of the squares of even numbers in a list in a bunch of different languages. Revisit those examples now with an eye toward what you think the designers of each language want you to be able to, or not be able to, express. What constraints are they placing on you?

Related to expressiveness is the idea of code as art, or art as code. Here’s a discussion of what this actually means:

Popularity

There are countless numbers of ways to measure popularity! You really can’t make popularity statements without stating your measure. Then people will argue whether your measure is even valid. 🤷‍♀️ Nevertheless, it’s fun to look at this stuff from time to time.

RedMonk has a language ranking scheme that combines pull requests on GitHub and questions on StackOverflow. (One could argue that this measures how confusing a language is too...maybe most of the StackOverflow questions are language complaints?) Here is the ranking from March, 2024:

RedMonk gives these rankings:

1. JavaScript
2. Python
3. Java
4. PHP
5. C#
6. TypeScript
6. CSS
8. C++
9. Ruby
10. C
11. Swift
12. Go
12. R
14. Shell
14. Objective-C
16. Scala
17. Kotlin
18. PowerShell
19. Rust
20. Dart

Another ranking system, by Tiobe, ends up with a radically different top 20. They say: “The ratings are based on the number of skilled engineers world-wide, courses and third party vendors. Popular search engines such as Google, Bing, Yahoo!, Wikipedia, Amazon, YouTube and Baidu are used to calculate the ratings.”

The YouTube channel Context-Free has a video on language popularity (covering the Languish app):

Interesting how Tiobe ranks Ada as #9 but Languish places it at #161. Go figure.

But what makes a language popular? MPJ has thoughts:

Tradeoffs

You can’t have everything, it seems:

• The expressive power of dynamic typing, polymorphic type systems, functions as first-class values, higher-order functions, and closures can sometimes impact performance.
• Automatic garbage collection saves billions of dollars in programmer time, but isn’t always a good idea in embedded, life-critical, real-time systems.
• A language may be wonderful and amazing and increase developer productivity, but if no talented people are out there that know the language, how will you hire the best team?
• Languages that are intentionally designed to be horrible (Brainfuck, Java2K, Malbolge, etc.) have some intellectual and educational value (and offer amusement).

No Competition!

Don’t make the mistake of thinking programming languages are like sports teams—they don’t compete against each other. Don’t root for one to “win.”

Realize that languages serve different purposes and are often used together to build systems.

Recall Practice

Here are some questions useful for your spaced repetition learning. Many of the answers are not found on this page. Some will have popped up in lecture. Others will require you to do your own research.

1. What Java expression will sum the squares of even numbers in an array?
   IntStream.of(a).filter(x -> x%2==0).map(x -> x*x).sum()
2. What is the generator expression to sum the squares of even numbers in Python?
   sum(x**2 for x in a if x % 2 == 0)
3. Which are the languages with these logos?
   
   
   Fortran, Kotlin, Lisp, Python.
4. What professional benefits can you gain from studying programming languages?
   • Better expressive capacity
   • Better technical decision making
   • Ability to learn new languages more easily
   • Better productivity
   • Ability to create new languages
   • New ways of thinking
   • Ability to create tools to manipulate language and knowledge
5. Programs are a form of ________________ just like novels, short stories, technical manuals, wikis, screenplays, essays, dialogues, articles, and poetry.
   Literature, writing, or written expression.
6. “If statements” are a form of ________________ and “while statements” are a form of ________________.
   conditional execution; iteration.
7. What programming language did Alan Kay demo in his 2013 Video Programming Languages and Programming?
   I’m not telling you. Watch the video. It is worth your time. If you watched the video, you know.
8. What are five dimensions of an effective study of programming languages?
   1. Learning specific languages
   2. Learning language-independent concepts
   3. Learning mathematical formalisms for the description of languages
   4. Programming Language History
   5. Programming Language Pragmatics
9. What are three of the most popular programming languages created in the 1950s? What was the primary domain of each?
   Fortran for scientific computation, Lisp for artificial intelligence, and COBOL for business.
10. What “revolution” in programming characterized the 1970s?
    Structured Programming.
11. What programming paradigm started taking over the world in the 1980s?
    Object orientation.
12. What “movements” brought back interest in functional programming in the early 21st century?
    (1) The rise of multicore processors, and (2) the rise of big data.
13. In Bret Victor’s The Future of Programming, what are the four “predictions” his 1973 persona predicted for 2013 that did not actually take over to the degree one might have wished?
    I really don’t want to share the answer because the video is so important that you need to watch the whole thing yourself. But you know, it’s good to be able to check your recall abilities, so here they are:

    • Direct manipulation of data over writing lines of code
    • Goals (what you want) over procedures (how to get what you want)
    • Spatial representation of data over text representations
    • Parallel execution over sequential execution
14. When studying individual languages what we must always keep in mind?
    The reason why the language was designed, which is often a particular problem domain for which it was intended to operate in.
15. Which language was the successor to Objective-C?
    Swift.
16. Verse was designed for ________________ and Mojo was designed for ________________.
    Metaverse applications; AI and Machine Learning applications.
17. What is a language?
    A structured system of communication.
18. What is a programming language?
    A language for expressing computation.
19. What do we mean by computation?
    A determination of new information from existing information by formal, logical, mathematical, mechanical means, carried out by a sequence of steps, each of which takes a finite amount of time and resources.
20. Information can be represented as sequences of ________________ drawn from an ________________.
    characters, alphabet
21. All usable information can be represented as strings of characters. For most computation today, what alphabet are characters drawn from?
    Unicode.
22. Humans don’t think in terms of characters but rather in terms of ________________.
    Values.
23. What are the three basic information units that can be encoded into bits?
    Characters, numbers, and atoms.
24. Information is chunked into ________________.
    Values.
25. Values are classified into ________________.
    Types.
26. What are entities? Name some.
    Entities are constructs within programs that refer to, store, or manipulate values. Examples include: literals, variables, functions, declarations, expressions, statements, coroutines, threads, processes, modules, and packages.
27. What is meant by the statics of a language?
    How programs are constructed.
28. What is meant by the dynamics of a language?
    Computational effects of programs in execution.
29. Name at least five “top-level” ontological areas in the study of programming languages.
    Possible answers include: Naming, Evaluation, Control Flow, Typing, Functional Abstraction, Modularity, Concurrency, and Metaprogramming. There may be others.
30. What are some areas of philosophy and mathematics that are important in the study of programming languages?
    Logic, Type Theory, Lambda Calculus, Theories of Computation, Syntax, and Semantics.
31. Syntax deals with ________________ and semantics deals with ________________.
    structure; meaning.
32. Is it for syntax or for semantics that formal methods are much easier and universally applied?
    Syntax.
33. What are some concerns of “pragmatics” in programming languages? Name at least five.
    Here are some to choose from; there may be others:

    • Suitability for a given application domain
    • Comparison to other languages
    • Expressiveness
    • Performance capabilities
    • Idioms
    • Environments
    • Implied execution model
    • Standard library
    • Ecosystem
34. Name at least five technical criteria on which to evaluate programming languages.
    Here are some to choose from; there may be others:

    • Ease of reading
    • Ease of writing
    • Expressiveness
    • Linguistic prevention of mistakes
    • Possibility of quick and incremental computation
    • Possibility of efficient target code generation
    • Portability
35. Name at least three non-technical criteria on which to evaluate programming languages.
    Here are some to choose from; there may be others:

    • Being the only language suitable for a specific problem
    • Personal preference
    • Good development environments
    • Fast compilers
    • A massive ecosystem
    • Patronage
    • “Everyone else is using it”
    • “The boss made me use it”
    • Economics and Inertia
    • Laziness
36. What must accompany any claim of language popularity?
    The measure used to determine popularity.
37. What is the tradeoff surrounding automatic garbage collection?
    It saves billions of dollars in programmer time, but isn’t always a good idea in embedded, life-critical, real-time systems (because it kicks in at unpredictable times).

Summary