Overview of Programming Language Concepts

The Main Topics

Perhaps none of us will agree on the set of main topics in the study of programming languages, but I’ll take a shot. Here I’ve organized the field into eight topic areas:

① Names, Binding, and Scope (Declarations)

How do we give names to entities? And when we encounter a name, how do we know which entity it refers to?

② Evaluation (Expressions)

How do we express computations, using values and operators?

③ Control Flow (Statements)

How to we organize computation in time? What actions or effects can we produce?

④ Classification (Types)

How do we classify values so that they may behave in certain, predictable ways?

⑤ Functional Abstraction (Subroutines and Coroutines)

How can we abstract computations into chunks so that we can invoke them whenever we need them?

⑥ Data Abstraction (Objects and Modules)

How do we make little bundles of data together with behavior?

⑦ Concurrency, Parallelism, and Distribution

How do we arrange to do different computations at the “same” time (safely)?

⑧ Metaprogramming

How can our programs know about themselves? How can we answer questions about the code itself?

Are there others?

What about things like performance? Readability? Maintainability? Security? Not quite! These are higher-level, qualitative concepts, more pragmatic concerns.

Let’s look a little deeper into each of these areas. But not that deep. Our concern here is only to list topics and subtopics. Detailed notes for each of the topics are elsewhere.

Names

We have to be able to name things. Naming is indispensable in human languages. So too in programming languages. This topic area is concerned with:

• Binding: associating names with entities
• Scope: the region of text in which a binding is active
• Visibility: sometimes you can see a name, sometimes you can’t
• Extent: the lifetime of a binding
• Storage class: “Where” are certain named (entities) stored?
• Linkage: How, if at all, are names accessible from the outside?
• Defining vs. referencing occurrences
• Overloading and aliasing
• Polymorphism (static/dynamic)
• Bound vs. free names
• Shallow vs. deep binding
• Static vs. dynamic scope

Expression Evaluation

An expression is either a value, or one or more expressions joined by operators. Expressions are evaluated to produce a value. This is a rich topic, covering:

• Operators (Precedence, associativity, fixity, arity)
• Evaluation order (defined, undefined, short-circuit)
• Side effects
  • Lvalues vs. Rvalues
  • Initialization vs. Assignment
  • Assignables?
• Eager vs. Lazy Evaluation
• Macros

Control Flow

Computations often are required to occur in time. Some constructs produce actions, or effects. Some are triggered by events. Many languages feature statements (a.k.a. commands) that are executed. Control flow refers to how these actions are grouped within lines of execution. There are a few ways to do this:

• Sequencing (semicolon, comma)
• Selection (if, switch, case)
• Iteration (for, while, forEach, takeWhile)
• Recursion
• Non-determinism
• Disruption (call, return, break, continue, throw)

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. This is one of the largest and most technical fields in programming language theory, encompassing many topics, including:

• Fixed set of types or can you create new ones?
• Are types extra-lingual or are they values you can manipulate (first-class types)?
• Types vs. Classes vs. Typeclasses
• Type Expressions
• Equivalence, compatibility, checking, coercion
• Inference
• Spectra: static vs. dynamic, strong vs. weak, manifest vs. inferential
• Parameterized types (generics), covariance, contravariance, invariance
• Dependent types
• Boolean, numeric, string, ...
• Collections (arrays, lists, set, dictionaries)
• Sum and product types
• Optionals
• Regular Expressions and other pattern types

Functions

Functions may just be the most important building block of good code. They are the most basic kind of code abstraction. After all, The Lambda Calculus shows us that mathematics itself can rest on a foundation of functions. In programming languages, a study of functions is are concerned with:

• Procedures (abstractions for commands)
• Functions (abstractions for expressions)
• 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, value-result, reference, name
• Higher-order functions
• Closures

Modules

Humans deal with complexity by chunking things. In a software system, one of the biggest chunks is the module. Modules are a way to divide a system into parts that can be developed, tested, and reasoned about independently. They are also a way to control the visibility and accessibility of names and entities.

The study of modules includes:

• Modules, packages, namespaces, classes, units, etc.
• Import and export
• Open vs. Closed
• Object orientation
• Separate compilation (the physical organization of a system)

Concurrency

In the real world, things don’t happen in a single sequence. Things can happen at anytime. Different things can happen at the same time. What is time, anyway? This field is so rich that thousands of books and hundreds of college-level courses focus entirely on concurrency (and its cousins parallelism and distribution). Topics here include:

• Concurrency vs. parallelism vs. distribution
• Threads vs. processes
• Events
• Single-threaded event queue vs. preemptive threading
• Shared resources and synchronization
• Scheduling
• Asynchronicity: callbacks, promises, async/await
• Coroutines (yield)
• Channels vs. Processes
• Buffered vs. Unbuffered communication

Metaprogramming

User-facing applications are writting to help their users answer questions like “What is the average salary of employees in the marketing department?” But can you also ask it ”How many local variables are you made up of, and what are their types?” Metaprogramming is writing programs that manipulate programs (including themselves).

• Introspection
• Reflection
• Eval
• Decorators
• Metaclasses

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. Name at least five conceptual 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.
2. What is a declaration?
   An entity that introduces a name.
3. What is the difference between an expression and a statement?
   An expression is evaluated to produce a value. A statement is executed to produce an effect.
4. What is control flow concerned with?
   How computations are organized in time, in a single line of execution.
5. What do we call the study of computations organized in multiple lines of execution?
   Concurrency.
6. Types impose constraints on ________________.
   what we can and cannot say.
7. What are modules?
   Modules are a way to divide a system into parts that can be developed, tested, and reasoned about independently. They are also a way to control the visibility and accessibility of names and entities.
8. What is metaprogramming?
   Metaprogramming is writing programs that manipulate programs (including themselves).

Summary