1.3 The World of Programming Languages

1.3.1 Fundamental Questions

This text is about programming language concepts. In preparation for a study of language concepts, we must examine some fundamental questions:

• What is a language (not necessarily a programming language)? A language is simply a medium of communication (e.g., a whale’s song).

• What is a program? A program is a set of instructions that a computer understands and follows.

• What is a programming language? A programming language is a system of data-manipulation rules for describing computation.

• What is a programming language concept? It is best defined by example. Perhaps the language concept that resonates most keenly with readers at this point in their formal study of computer science is that of parameter passing. Some languages implement parameter passing with pass-by-value, while others use pass-by-reference, and still other languages implement both mechanisms. In a general sense, a language concept is typically a universal principle of languages, for which individual languages differ in their implementation approach to that principle. The way a concept is implemented in a particular language helps define the semantics of the language. In this text, we will demonstrate a variety of language concepts and implement some of them.

• What influences language design? How did programming languages evolve and why? Which factors form the basis for programming languages’ evolution: industrial/commercial problems, hardware capabilities/limitations, or the abilities of programmers?

Since a programming language is a system for describing computation, a natural question arises: What exactly is the computation that a programming language describes? While this question is studied formally in a course on computability theory, some brief remarks will be helpful here. The notion of mechanical computation (or an algorithm) is formally defined by the abstract mathematical model of a computer called a Turing machine. A Turing machine is a universal computing model that establishes the notion of what is computable. A programming language is referred to as Turing-complete if it can describe any computational process that can be described by a Turing machine. The notion of Turing-completeness is a way to establish the power of a programming language in describing computation: If the language can describe all of the computations that a Turing machine can carry out, then the language is Turing-complete. Support for sequential execution of both variable assignment and conditional-branching statements (e.g., if and while, and if and goto) is sufficient to describe computation that a Turing machine can perform. Thus, a programming language with those facilities is considered Turing-complete.

Most, but not all, programming languages are Turing-complete. In consequence, the more interesting and relevant question as it relates to this course of study is not what is or is not formally computable through use of a particular language, but rather which types of programming abstractions are or are not available in the language for describing computation in a more practical sense. Larry Wall, who developed Perl, said:

“Languages are abstractions: ways of seeing or organizing the world according to certain patterns, so that a task becomes easier to carry out. . . . [For instance, a] loop is an abstraction: a reusable pattern” (Krishnamurthi 2003, p. 315). Furthermore, programming languages affect (or should affect) the way we think about describing ideas about computation. Alan Perlis (1982) said: “A language that doesn’t affect the way you think about programming, is not worth knowing” (Epigraph 19, p. 8). In psychology, it is widely believed that one’s capacity to think is limited by the language through which one communicates one’s thoughts. This belief is known as the Sapir–Whorf hypothesis. George Boole (1854) said: “Language is an instrument of human reason, and not merely a medium for the expression of thought[; it] is a truth generally admitted” (p. 24). As we will see, some programming idioms cannot be expressed as easily or at all in certain languages as they can in others.

A universal lexicon has been established for discussing the concepts of languages and we must understand some of these fundamental/universal terms for engaging in this course of study. We encounter these terms throughout this chapter.

1.3.2 Bindings: Static and Dynamic

Bindings are central to the study of programming languages. Bindings refer to the association of one aspect of a program or programming language with another. For instance, in C the reserved word int is a mnemonic bound to mean “integer” by the language designer. A programmer who declares x to be of type int in a program (i.e., int x;) binds the identifier x to be of type integer. A program containing the statement ; binds the value 1 to the variable represented by the identifier x, and 1 is referred to as the denotation of x. Bindings happen at particular times, called binding times. Six progressive binding times are identified in the study of programming languages:

1. Language definition time (e.g., the keyword int bound to the meaning of integer)

2. Language implementation time (e.g., int data type bound to a storage size such as four bytes)

3. Compile time (e.g., identifier x bound to an integer variable)

4. Link time (e.g., printf is bound to a definition from a library of routines)

5. Load time (e.g., variable x bound to memory cell at address 0x7cd7—can happen at run-time as well; consider a variable local to a function)

   

6. Run-time (e.g., x bound to value 1)

Language definition time involves defining the syntax (i.e., form) and semantics (i.e., meaning) of a programming language. (Language definition and description methods are the primary topic of Chapter 2.) Language implementation time is the time at which a compiler or interpreter for the language is built. (Building language interpreters is the focus of Chapters 10–12.) At this time some of the semantics of the implemented language are bound/defined as well. The examples given in the preceding list are not always performed at the particular time in which they are classified. For instance, binding the variable x to the memory cell at address 0x7cd7 can also happen at run-time in cases where x is a variable local to a function or block.

The aforementioned bindings are often broadly categorized as either static or dynamic (Table 1.1). A static binding happens before run-time (usually at compile time) and often remains unchangeable during run-time. A dynamic binding happens at run-time and can be changed at run-time. Dynamic binding is also referred to as late binding. It is helpful to think of an analogy to human beings. Our date of birth is bound statically at birth and cannot change throughout our life. Our height, in contrast, is (re-)bound dynamically—it changes throughout our life. Earlier times imply safety, reliability, predictability (i.e., no surprises at runtime), and efficiency. Later times imply flexibility. In interpreted languages, such as Scheme, most bindings are dynamic. Conversely, most bindings are static in compiled languages such as C, C++, and Fortran. Given the central role of bindings in the study of programming languages, we examine both the types of bindings (i.e., what is being bound to what) as well as the binding times involved in the language concepts we encounter in our progression through this text, particularly in Chapter 6.

Table 1.1 Static Vis-à-Vis Dynamic Bindings

1.3.3 Programming Language Concepts

Let us demonstrate some language concepts by example, and observe that they often involve options. You may recognize some of the following language concepts (though you may not have thought of them as language concepts) from your study of computing:

• language implementation (e.g., interpreted or compiled)

• parameter passing (e.g., by-value or by-reference)

• abstraction (e.g., procedural or data)

• typing (e.g., static or dynamic)

• scope (e.g., static or dynamic)

We can draw an analogy between language concepts and automobile concepts. Automobile concepts include make (e.g., Honda or Toyota), model (e.g., Accord or Camry), engine type (e.g., gasoline, diesel, hybrid, or electric), transmission type (e.g., manual or automatic), “drivetrain (e.g., front wheel, rear wheel, or all wheel), and options (e.g., rear camera, sensors, Bluetooth, satellite radio, and GPS navigation). With certain concepts of languages, their options are so ingrained into the fiber of computing that we rarely ever consider alternative options. For instance, most languages provide facilities for procedural and data abstraction. However, most languages do not provide (sophisticated) facilities for control abstraction (i.e., developing new control structures). The traditional if, while, and for are not the only control constructs for programming. Although some languages, including Go and C++, provide a goto statement for transfer of control, a goto statement is not sufficiently powerful to design new control structures. (Control abstraction is the topic of Chapter 13.)

The options for language concepts are rarely binary or discretely defined. For instance, multiple types of parameter passing are possible. The options available and the granularity of those options often vary from language to language and depend on factors such as the application domain targeted by the language and the particular problem to be solved. Some concepts, including control abstraction, are omitted in certain languages.

Beyond these fundamental/universal language concepts, an exploration of a variety of programming styles and language support for these styles leads to a host of other important principles of programming languages and language constructs/abstractions (e.g., closures, higher-order functions, currying, and first-class continuations).