“First-class functions” usually means that functions can be passed around, used as arguments, returned, etc. That’s a big step up compared to languages where you can’t. It unlocks higher-order functions and a whole new way of modeling the world. But does that really make them first-class citizens?

A fresh look at “first-class functions”

If functions are genuinely first-class citizens, we can have nice things

If you’re familiar with intensionality (with an “s”), consider skipping this post. It argues that intensionality bridges the gap between the usual definition of “first-class functions” and a world where functions truly are first-class.

Functional programming rocks! I remember how blown away I was when I first watched Erik Meijer’s Functional Programming Fundamentals video series in my youth, eagerly awaiting each new episode. (Little did I know that I would meet Erik at a conference nine years later and join his awesome team at Meta soon after. Thank you, Erik, for having such a profoundly positive impact on my life, time and again!)

“First-class functions”

I’m thrilled that functional programming has found its way into the mainstream over the decades. Today, functional languages are being used at scale, and many other languages have received a functional infusion. One core principle is to treat functions like other data types — numbers, strings, arrays, and so on — making them “first-class citizens” of the language. What does that mean in practice? You can pass functions around, use them as arguments or return them, declare variables or fields with a function type, and more.

First-class functions

Here’s what else we can do with numbers, strings and arrays: We can send them over the network or store them to and load them from a file (serialization). We can look at their value or structure, e.g. check if a number is zero, extract elements from an array, or pattern match on a tuple. Of course we can!

And yet, in many programming languages (or the λ-calculus), the only thing we can do with functions is call them. Functions are opaque; most facts about them are fundamentally inaccessible. We’re stuck with an extensional view, with little ability to reflect on internal structure. Imagine if numbers were just as mysterious — say, a program could only ask whether an int is divisible by another int, but can’t directly observe its actual value. For primitive values we take an intensional view for granted — the ability to inspect and introspect them — so much so that it feels silly to point out. Surely, if functions are first-class citizens, they deserve the same treatment!

Intensionality! So what? Why would I look inside functions?

Developers are used to functions being opaque. But what if they weren’t? Here is a glimpse into that world:

• Serialization: Functions can be stored and sent around. Why would you want that? Ask users of cloudpickle. Many DSLs exist to communicate functionality long after a program has been compiled or deployed. First-class support for this would be better than forcing developers to invent DSLs or rely on unsafe libraries. Note that an intensional language also allows us to inspect a function from an untrusted source in terms of safety. We could ban side-effects or only allow very specific APIs to be used. We’d get the safety of a DSL, but inside the host language — which likely has much better tools (editing, debugging, etc).
• Automatic differentiation: Machine learning has driven the creation of frameworks and even specialized programming languages specialized in computing derivatives of functions. In an intensional language we can just write a higher-order function differentiate that recursively decomposes its argument (a function) while composing a derivative.
• Type checker as a function: We’re usually stuck with the type system that ships with a language — sometimes too restrictive, sometimes too weak. If you’re working on machine learning models, have you ever lost hours or days because of some tensor shape mismatch crashing the training? We could save a lot of electricity (and grey hair) by opting into a stronger type system. An intensional language lets anyone contribute a type-checker as a higher-order function and ship it as a library, for anyone to use. (Side-note: If type checking is just a function call, then static vs dynamic becomes a matter of when you call it relative to other code. Neat.)
• Program optimization as a function: Type checking is just one kind of program analysis. Optimizations are another — typically baked into a compiler. Developers control them by picking an optimization level, providing hints or relying on arcane knowledge to tailor code to improve cache locality or enable tail recursion. But in an intensional language, regular functions can look at, analyze and transform functions!
• Compiler as a function: If type checkers and optimizers are just functions, why not entire compilers? Imagine a server/client app. Instead of two separate codebases, you write one app with server_main and client_main, sharing data structures and logic. Then you call to_arm64 server_main and to_wasm client_main to produce deployable artifacts. This tier splitting idea isn’t new, but intensionality puts it in your hands—no declarative magic required. Notably, the Wolfram Language supports compiling functions from within the language!
• Almost any developer tool as a function. The pattern is probably clear by now: Metaprogramming is traditionally reserved for dev tools that operate on source code, ASTs or some intermediate representation. With intensionality, the “guts” of functions become accessible to ordinary higher-order functions, at runtime. Think of what Roslyn did for C#: turning the compiler into an open platform. An intensional language is implicitly this open, and not just at compile time.
• All-powerful REPLs/notebooks: Interactive development environments like Jupyter are thriving! They excel at researching and prototyping ideas. Turning developer tools into functions supercharges this. Imagine you have trained a machine learning app and now have a function make_theme_music, which turns keywords into theme music. You would like to turn it into an app or an online service. Usually, that means leaving your notebook, replicating the core of make_theme_music in a “proper” project with build pipeline and deployment scripts. Instead, just add another notebook cell that imports a compiler for whatever target platform and passes make_theme_music to it — then another cell to authenticate with your app store or cloud provider and upload the artifacts we just compiled. The full life cycle can happen in one place.

I do think it’s important for a language ecosystem to provide a solid type system, reasonable optimizations, and so on. But intensionality gives developers control when they need it. For example, choosing an intensional language or calculus for smart contracts could increase transparency and provide greater flexibility in verification strategies.

Pseudo-intensionality in mainstream languages

Not all languages treat functions strictly extensionally. JavaScript and Python, for instance, let you retrieve a function’s source code as a string — but with limitations. In JavaScript: (a => b => a + b)(42).toString() returns b => a + b with no mention of 42. The fact that a is bound to 42 is inaccessible. Python’s magic __closure__ attribute on the other hand allows accessing this, which is great. I believe cloudpickle leverages this and other metadata to serialize functions.

Lisp is often hailed as a shining example of metaprogramming, thanks to its homoiconicity: functions are data. But given (defun f (a) (lambda (b) (+ a b))), can (f 42) actually be turned back into data? My understanding is that closures are opaque in this case. (Please leave a comment if that’s wrong.)

Python’s dis package and .NET languages allow retrieving bytecode (reflection). However, the exact intermediate representation depends on the compiler (and settings) used, so it’s not deterministic. That’s suboptimal.

Pointers in low-level languages typically point to the first machine-code instruction of the function. Even worse than bytecode, what you find there is platform-dependent — and where a function ends can be far from obvious.

Good examples

The above examples suggest intensionality, but are mostly workarounds around an opaque core. On the other hand, the following examples are intensional by construction:

• Wolfram Language. Everything is represented as symbolic expressions. Use FullForm to uncover this structure. Stellar.
• Intensional calculi such as Barry Jay’s tree calculi. While λ-calculus is fundamentally extensional, tree calculi are not — despite being even simpler than λ-calculus. Check out our website for a quick overview and interactive demos, or Barry’s book for a rigorous deep dive.

As this demo shows, an intensional language let’s you write things like to_source (mul 4) and get back "double ○ double". Note how this is not some closure-voodoo on top of compile-time metadata of mul, as Python would be able to produce. Instead, mul 4 returns a proper self-contained function that seems to double its argument twice, and we’re able to observe that!

Takeaways & Challenges

The functional programming paradigm brought first-class functions and higher-order functions into the mainstream. Intensionality takes this further, unlocking truly first-class functions and making higher-order functions far more powerful. It “democratizes” developer tools and metaprogramming, enabling programming language ecosystems to remain lightweight while letting anyone contribute their own tools — as ordinary libraries. I hope to illustrate this with demos and posts on tree calculus.

Here are some potential challenges:

• Typing intensional programs. How can we reason safely about programs that reflect on other programs? Rather than wrangling source code (strings) or some opaque AST type, tree calculus works directly on values. (Notice that you can write my_func 42 and optimize my_func in the same stroke — no quoting or encoding of my_func required.) Barry’s paper Typed Program Analysis without Encodings presents a first type system that is capable of reasoning about intensional programs. This remains an active area of research.
• Performance. Isn’t it expensive to have the “guts” of functions readily available? Doesn’t that prevent all sorts of optimizations? Potentially. However:
  (1) It’s trivial to write a program analysis is_reflective (a higher-order function, of course) that detects whether a function uses intensionality. So is_reflective is_reflective = true while is_reflective add = false. Compilers could use this to elide intensionality where it’s not needed.
  (2) Real world applications are usually a mix of perf-critical code and plenty of glue or “business logic.” Nothing prevents compiling the perf-critical parts to a lower-level language — heck, in most mainstream languages, critical algorithms aren’t implemented in the language itself. Python isn’t powering the hot loops of machine learning.
  (3) Note that at the machine code level, the “guts” of functions are typically available anyway — just in a platform-dependent form. Much like how extra debug information/“symbols” let us interactively step through running programs, I see no fundamental reason why a fully integrated intensional language should incur significantly more overhead.

There’s probably more, but I’m excited to figure it out.