In SICP, the authors state (Section 1.1) that there are three basic "mechanisms" of programming languages:

  • primitive expressions, which represent the simplest entities the language is concerned with

  • means of combination, by which compound elements are built from simpler ones

  • means of abstraction, by which compound elements can be named and manipulated as units

How can I analyze a mainstream programming language (Java, for example) in terms of these elements or mechanisms?

migrated from stackoverflow.com Nov 8 '11 at 18:11

This question came from our site for professional and enthusiast programmers.

  • Have you looked in Extended Backus-Naur Form, EBNF or Backus-Naur Form, BNF before? It can break down a grammar similar to these three concepts, though I'm not really sure what your intentions are so I don't know if it will help or not. – Jetti Nov 10 '11 at 21:29
  • @Jetti -- yes, I have, and no, it's not what I'm interested in. I'm really looking to analyze the semantics (question: is that actually the word I'm looking for?) of programming languages, not their written forms (i.e. syntax). – user39685 Nov 10 '11 at 21:46

The distinction between primitive expressions, means of combination and means of abstraction is a useful one when modelling programming languages. Note that this is not an intrinsic property of the language: you can't point at any language definition and say “this feature is unambiguously a primitive expression, that feature is unambiguously a means of combination”. The distinction is a property of the model, and complex models can resist classification.

A textbook example of these three concepts is the lambda calculus, which has exactly one of each:

  • Variables x, y, … are the only primitive expressions.
  • Function application M N is the one means of combination.
  • Lambda abstraction λx.M is the one means of abstraction.

When you get to languages with more features, the modeling can become more ambiguous. Generally speaking, a primitive expression is one that you can't or won't break down into primitive components. But it's like the atom: it's primitive until science marches on. For example, there is a variant of the lambda-calculus in which variables use numbers rather than names (de Bruijn indices), which is particularly convenient when modeling lambda-terms for computer proofs; and in computer proofs, integers are broken down into constituent parts. So in these models, variables aren't primitive expressions after all.

In (a typical model of) Java, primitive expressions are primarily constants and variables. Means of combinations include the numerous operators; more precisely, “additive expression” is a means of combination with two slots (the left-hand side and the right-hand side), or with three slots (the two sides plus the operator) if you include both A + B and A - B under that name (in which case the operators + and - would be primitive constructs in their own right). Other means of combination include sequences of instruction I ; J, loop constructs while (…) {…}, and so on. Then you have constructs like variable declarations, function definitions, class definitions and so on which are both means of combinations (they combine parameter names and types, bodies, initializers, …) and means of abstraction (because they define names for reuse). It is in fact quite common that means of abstraction are also means of combination: they combine a name with its definition.

  • Nice answer; you got at the problems that I was struggling with -- the ambiguous distinction between primitives, combinations, etc. – user39685 Nov 21 '11 at 13:19
  • What do you mean by "variable" exactly? Can't those be described as means of abstraction because they have a name? – morbidCode Jul 30 '17 at 14:21
  • @morbidCode The concept of variable is a complicated one, and the word has a different but related meaning in the lambda calculus and in Java. A variable can be considered an “abstraction” since it refers to an unspecified value. However, it is not a means of abstraction: it doesn't create the reference, it's merely a way to use the existing abstraction. A lambda abstraction creates a way to use a block of code as an object which can be manipulated. – Gilles Jul 31 '17 at 0:50

Rough stab:

Expressions are just that; what constitutes an expression in Java. I don't know if that would expand to include statements or not.

Combinations would include compound expressions, (variables?,) statements, methods, the class mechanism, and packages. Modules, too, once they're in the language.

In Java, the simplest means of abstraction is a class: nothing may exist outside of a class. There are, perhaps, "layers" of abstraction: a static method is arguably simpler than an instance method, because it doesn't require an instance.

Generics offer an additional layer of abstraction (and frustration).

  • @MattFenwick An expression may consist of a single primitive, combinations of primitives and other entities makes a compound expression (still an expression, but not a statement). – Dave Newton Nov 8 '11 at 18:02
  • @MattFenwick I'm not, I'm not saying an expression is a primitive, I'm saying an expression may consist of only a single primitive. There's no way a String is a primitive just because the language provides syntactic sugar for it, unless you want to differentiate between an immediate string and the reference it creates. I'd say + is, because it cannot be acted upon in any way. – Dave Newton Nov 8 '11 at 18:20
  • Regarding your aside: Is there a problem with Java's implementation of generics? – Steven Evers Nov 8 '11 at 19:31

Here is my basic categorization. I'm trying to draw a paralel with LISP.

Primitive expressions

  • All primitive values, things you can represent using literals (numbers, booleans, ...)

Parallel in LISP: atoms, numbers and lists.

Means of Combination (Ways you can build compound data-structures)

  • Arrays
  • Objects / structs.

Parallel in LISP: Cons cells, lists

Means of Abstraction

  • All control flow syntax (if, while for)
  • All builtin operators (+, -, *, /, ...)
  • All functions (in this category we include classes and methods)

Parallel in LISP: Functions, syntactic sugar like let, define

  • Nice answer! I was thinking maybe some of the control-flow constructs would fit under means of combination, though. Nice parallels with LISP, that helps a lot. – user39685 Nov 10 '11 at 19:07
  • Not quite. Arrays and objects play at a different level, they're part of the data representation, not of the language itself. Array initializers are part of the language, and they're a means of combination. Operators and control flow constructs are not means of abstraction, because they do not “store away” anything for reuse. Means of abstraction usually give a name to an entity for future reuse under that name. – Gilles Nov 20 '11 at 21:29

A programming language is generally defined by its syntax and its semantics. Both of these will be defined in the standards for the language.

The syntax outlines how to write a valid program and the semantics defines what that valid program means.

In your cases, the syntax will tell you what your primitives are, how you combine them, and how you abstract them. The semantics will tell you what the combinations and abstractions mean.

For example, the syntax will tell you how to write a valid for loop. The semantics will tell you what the for loop does.

If you really want to start to analyze a programming language, grab a copy of the standard and see what is in there. I would really start off with a simple language, like C, before delving into Java. I would also read the rest of the book. Learning why programming langauges work the way they do has made me a better programmer, even though I don't implement compilers.

  • 1
    Wait, what? "Simple like C before delving into Java." You lost me at "Simple like C". – corsiKa Nov 8 '11 at 19:23
  • Matt, I guess I don't really understand what you are doing then. The book you quoted from talks about both of these things whether the authors explicitly call them syntax and semantics or not. – mpdonadio Nov 8 '11 at 19:27
  • In fact, "syntax" describes precisely the "simplest" things in the languages, the atoms from which is is composed. – Ira Baxter Nov 10 '11 at 18:04
  • The syntax does not fully capture what a valid program is, far from that. For example a syntactically correct program might fail type checking. A C program that executes the statement x = ++x; is not valid even if a typical compiler would accept it. – Gilles Nov 20 '11 at 21:27

I don't know if it is correct, but the way I understand the division is as follows:

primitive expressions, These would be, things such as >>,+,*,/,int,boolean,variables,methods etc.

means of combination, This can be debatable, either its things like + and concact, or its talking about more advanced ideas like inheritance vs composition and the methods to do that. Injection, the new operator, extending etc.

means of abstraction, This would be the syntax used to name variables, and methods, as well as means of creating interfaces, classes, static classes, overloading methods etc.

However, its possible you need to give us more info from the book so we know exactly what is meant there.

  • The book is free online; a link is given in the OP. I kind of felt the same way about means of combination -- that it's tough to figure out what exactly belongs there. Nice answer, though. – user39685 Nov 10 '11 at 19:09
  • Do you know which other chapters he talks about combinations and abstractions though? – Bob Nov 10 '11 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy