13

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?

3
  • 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, 2011 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, 2011 at 21:46
  • Sounds like atoms, bonds, and molecules. These authors are just recasting the most general and trite philosophy - that the entire world consists of things, their relations, and combinations of the previous two treated as a unit for convenience - in the jargon of computer programming.
    – Steve
    Nov 27, 2021 at 9:01

5 Answers 5

3

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.

3
  • Nice answer; you got at the problems that I was struggling with -- the ambiguous distinction between primitives, combinations, etc.
    – user39685
    Nov 21, 2011 at 13:19
  • What do you mean by "variable" exactly? Can't those be described as means of abstraction because they have a name? Jul 30, 2017 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. Jul 31, 2017 at 0:50
5

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).

3
  • @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). Nov 8, 2011 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. Nov 8, 2011 at 18:20
  • Regarding your aside: Is there a problem with Java's implementation of generics? Nov 8, 2011 at 19:31
3

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

2
  • 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, 2011 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. Nov 20, 2011 at 21:29
1

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.

2
  • 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, 2011 at 19:09
  • Do you know which other chapters he talks about combinations and abstractions though?
    – Bob
    Nov 10, 2011 at 19:37
0

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.

4
  • 1
    Wait, what? "Simple like C before delving into Java." You lost me at "Simple like C".
    – corsiKa
    Nov 8, 2011 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, 2011 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, 2011 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. Nov 20, 2011 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.