What is the mathematics foundation for first/second/third class values in programming languages?

Just found two related questions

https://math.stackexchange.com/q/1759680/1281

https://stackoverflow.com/a/2582804/156458

In programming languages, from Michael Scott's Programming Language Pragmatics

In general, a value in a programming language is said to have ﬁrst-class status if it can be passed as a parameter, returned from a subroutine, or assigned into a variable. Simple types such as integers and characters are ﬁrst-class values in most programming languages. By contrast, a “second-class” value can be passed as a parameter, but not returned from a subroutine or assigned into a variable, and a “third-class” value cannot even be passed as a parameter.

Labels are third-class values in most programming languages, but second-class values in Algol. Subroutines display the most variation. They are ﬁrst-class values in all functional programming languages and most scripting languages. They are also ﬁrst-class values in C# and, with some restrictions, in several other imperative languages, including Fortran, Modula-2 and -3, Ada 95, C, and C++. 11 They are second-class values in most other imperative languages, and third-class values in Ada 83.

1. What is the mathematics foundation for first/second/third class values in programming languages?

The terminology reminds me of first/second order logic, but are they related?

2. It seems to me that the difference between them is which specific case a value can be used

• passed as a parameter,
• returned from a subroutine, or
• assigned into a variable.

Why are the specific cases important, while not other cases not mentioned?

Thanks.

• Classifying values into first/second-class is as fruitless as classifying languages into paradigms. All you'll end up with are vague generalizations that muddle the picture. This is not the right approach to understanding programming languages. What's important are understanding the language's syntax, statics, and dynamics, but that's much too large to go into in a comment Sep 27, 2016 at 1:30
• Aside: PL/I would be an example of labels as first-class. In PL/I you can declare variables typed to label, assign them code locations, and the goto them. You can also pass them as parameters, and even create arrays of them. Sep 27, 2016 at 3:54
• @Theraot: Perhaps I'm dating myself, but am I the only one who ever had to deal with assigned and computed GOTOs in FORTRAN? And no, I didn't write the @\$%! code, I was stuck re-engineering it. Sep 27, 2016 at 5:26
• @jamesqf I'm aware of assigning to labels in FORTRAN and COBOL, no, I haven't used that. I'm unsure of how to classify labels there. Yet for what I read (I have the manuals) PL/I goes beyond that, and I'm convinced that labels are first-class there. Sep 27, 2016 at 6:08
• Sep 27, 2016 at 12:48

There isn't any, and it's pretty arbitrary.

The only useful distinction is between first class, and all others. Every case that's in the "other" bracket has its own distinct set of rules in each case and lumping them all together just isn't very helpful. "First class" means "You don't have to look up the rules", essentially, and "other" is "You have to learn the rules".

For instance in C++ individual functions are first class values, as long as they're stateless. Overload sets are not but lambdas are. In C# functions are generally first-class values but there's some awkward cases that arise when dealing with type inference that prevent them from being in all cases.

• +1, though in the context of a book like Programming Language Pragmatics that compares a large number of constructs in a large number of languages, and analyzes the similarities and differences and implications in depth, I think this sort of shorthand can be useful. (Just don't go around expecting other people to understand "second-hand" and "third-hand" as meaning specific things.) Sep 27, 2016 at 5:54
• (Uh, where by "second-hand" and "third-hand" I of course mean "second-class" and "third-class". :-P ) Sep 28, 2016 at 2:31
• If you want to trade with second-hand functions, you had better do it in a language where functions are first-class citizens. ^^ Sep 28, 2016 at 3:02
• @5gon12eder: "second-hand functions" would be those you call from 3rd-party libraries, no? Sep 28, 2016 at 18:09

I agree with DeadMG, the important distinction is between first-class and "everything else." However, there is a more familiar way to classify the difference.

First-class values are data, the others are code. (roughly speaking: I am sure there are exceptions. But this is a really good approximation that holds for real-world languages.)

In some languages you can treat code as data. Functional languages are famous for this: some of them let you change the code of the program as it is running (the foundation of genetic programming).

Languages such as C and C++ allow you to take the address of functions: while you cannot modify them, you can pass functions as parameters to other functions. C++ also has the syntactic sugar of functors. The idea there is to create a whole object that, on the surface, appears to behave like a function and can be passed around as if it were data. What is otherwise a lower-class of value can be treated as a first-class value.

Mathematically, I think the best way is to think of a program's AST. Typically, each token has a specific type that may or may not be compatible with other types. Think l-value, r-value, and the other whole mess of value types in C++. Then add in the keywords, symbols that are functions, etc. Some of these may be first, second, or third class values depending on the language.

I am not sure knowing the "class" of value is all that important, except maybe in an academic environment. In the real-world, the important thing to know is how you can pass code around, treating it like data: functors, lambdas/closures, function pointers, etc.

• An example of a non-code non-first-class value: Lua has a special `...` "variable" used to denote vararg function parameters. You can use it in many expressions as if it were a value list (such as `print(...)` or `local args = {...}`) but there are some things you cannot do with it, such as refer to it in a closure (`function(...) return function() return ... end end`). Sep 27, 2016 at 12:59

Denotational Semantics provides a mathematic bases for describing how values and variables works in a programming language. It was explained so well in my Computer Sci Degree that I got a top mark in the Denotational Semantics exam, then forgot most of it and have never had a need to use it in a 20 year life as a programmer.

You can choose to use a well defined mathematically foundation, or you can use informal terminology like “ﬁrst-class status”. I would have learned at lot more if the course was based Scott's Programming Language Pragmatics, however the formal maths is needed for someone that is going to do a PHd in programming language design.

If you read the specification for most programming language, you will notice a dissident lack of Denotational Semantics, however most well designed languages had someone on the team that is an expert in programming language design, hence understands Denotational Semantics well.

So Michearl Scott uses informal terminology that has some relationship to formal mathematics, while presenting the subject in a way that most programmers can benefit from. His terminology is not used by other people, so it not useful for communicating, but it does gives you a good foundation on the questions you should ask when seeing a new programming language for the first time.

Note that Michael L. Scott is a leading researcher in Computer Sci, so will understand and be very happy using the formal maths, but like the best researchers he is skill in explaining the application of the research to the rest of us.

• Thanks. Which books were used in your class? Which books do you recommend now? I am a self learner
– Tim
Sep 27, 2016 at 11:44
• @Tim, I did my class over 20 years ago! I expect that Michearl Scott's book is one of the best and will cover more then you need unless you are going to do PHd level research.
– Ian
Sep 27, 2016 at 13:11

No, the word "first" in "first-class" and in "first-order" mean different things.

But yes, the concepts of "first-class" and "first-order" are related. They are both about classifying which concepts that a language can describe the language can also abstract over.

A concept is first-class if the usual abstraction mechanisms of a language can abstract over that concept.

For example, the Java programming language can describe integers, and all the usual mechanisms for abstracting over integers (accepting them as method parameters, returning them as function results, storing them in data structures, ...) work for integers.

A concept is first-order if it cannot be used to abstract over itself.

For example, again in Java, we can use methods to abstract over certain things. But we cannot use methods to abstract over methods, because a method name cannot be passed as method parameter. This is different in JavaScript, where you can use bracket notation to access a property of an object by its name as a string, and you can abstract over strings.

A concept is second-order if it can be used to abstract over first-order uses of itself, but not over second-order uses.

For example, in Java, you can use Generics to abstract over types (as in `class Foo<T> { public List<T> content; }`). However, you cannot use generics to abstract over Generics (as in `class Bar<T> { public T<Int> content; }`). This is different in Scala.

A concept is third-order if it can be used to abstract over first-order and second-order uses of itself, but not over second-order uses.

And so on.

Finally, a concept is higher-order if it can be used to abstract over arbitrary uses of itself.

Summary: If an abstraction feature is first-class, it is also higher-order. And if an abstraction feature is first-order, it cannot be first-class.

• You can do `List<List>` in Java, though. Maybe you can clarify what you mean with that part? Sep 27, 2016 at 14:24
• Good point. I mean: `class Foo<A> { A<Int> ... }`. That is, I mean to use a generic type parameter as a generic class. Then, `Foo<List>` would instantiate the `A<Int>` to `List<Int>`. In Java, that is not possible. I'll try to edit this in to the answer later. Sep 27, 2016 at 14:26
• Indeed, thats not possible. Sep 27, 2016 at 15:13
• I now replaced the misleading `List<List>` example. Thanks for pointing out the issue, @Polygnome. Sep 27, 2016 at 15:29
• @Toxaris I think this is just idiosyncratic terminology you've made up yourself. A 'concept' is not first-order or second-order, a logical quantifier is. Sep 28, 2016 at 4:25

What is the mathematics foundation for first/second/third class values in programming languages?

None that I am aware of.

The terminology reminds me of first/second order logic, but are they related?

Not really.

The "class" of a programming language element is just a shorthand way of thinking about the question what things does the user of my language wish to manipulate programmatically? For example, C# gives you a rich set of operations to manipulate values, a less rich set of ways to manipulate types, and no operations that manipulate labels.

However your intuition that there is a connection here is not entirely misplaced. There is an analogy to be made from first order logic to procedural programming, and from higher-order logic to functional programming. First order logic is about logical manipulation of values; procedural programming is about programmatic manipulation of values. Higher order logic is about logical manipulation of statements of logic, functional programming is about programmatic manipulation of functions.

Why are the specific cases important, while not other cases not mentioned?

You'd have to ask the author for a definitive answer.

I would not get too hung up on this notion of "class". It's not a formally define thing. It's a shorthand that language designers use to talk about what sorts of things can be manipulated programmatically.

“First-class value”, in this context, is standard terminology in programming language theory. A first-class value is something that can be manipulated as normal values in the language, something that can be computed at runtime. Of course, that's a tautological definition until you've defined a semantics for the language, and then a value is whatever the semantics defines to be a value. The point of the concept is to identify what can be manipulated directly, as opposed to only accessed indirectly.

For example, in almost every programming language, machine integers of a bounded size (e.g. 8-bit integers, or 32-bit integers, or 64-bit integers, etc.) are first-class values. You can store them in variables, pass them and return them to functions, etc. In most languages but not low-level languages such as assembly and C, strings are first-class values — but in C, they aren't, you only get pointers to strings. In C, strings and arrays are not first-class values: for example you can't pass an array to a function, you can't assign an array to an array variable, etc. In C, functions are not first-class values either: you can't store a function in a variable, only a pointer to a function. In contrast, strings and functions are first-class values in most high-level programming languages: you can store them in a string, etc.

An example of a concept that is not first-class in many programming languages designed to be compiled is types. In a language like C or Java, types live at compile time, you can't manipulate them using language constructs. (Java also has a dynamic type system based on classes; classes are first-class values through reflection.) In contrast, a language like Python has a `type` function that returns a value that represents the type of its argument.

The negation of “first-class value” in standard terminology is “not a first-class value”. The term “second-class value” is not commonly used, and “third-class value” even less. Don't expect to see them outside of this book. There is absolutely no basis for defining “second” as “can be passed as a parameter” and “third” as “can't be passed as a parameter”, there's no scale of things that could be meaningfully numbered. Very few languages make a difference between values that can be passed as a parameter to functions and values that can be assigned to variables, so it isn't useful to define a name for this concept.