Concepts and Semantics of Programming Languages 1

A Semantical Approach with OCaml and Python

Therese Hardin,Mathieu Jaume,Francois Pessaux,Veronique Viguie Donzeau-Gouge

• Publisher: Wiley-ISTE
• Year: 2021
• ISBN:
  9781119824091
• Edition: 1
• Topic: Ciencia de la computación
• Subtopic: Ingeniería computacional

This book – the first of two volumes – explores the syntactical constructs of the most common programming languages, and sheds a mathematical light on their semantics, while also providing an accurate presentation of the material aspects that interfere with coding.

Concepts and Semantics of Programming Languages 1 is dedicated to functional and imperative features. Included is the formal study of the semantics of typing and execution; their acquisition is facilitated by implementation into OCaml and Python, as well as by worked examples. Data representation is considered in detail: endianness, pointers, memory management, union types and pattern-matching, etc., with examples in OCaml, C and C++. The second volume introduces a specific model for studying modular and object features and uses this model to present Ada and OCaml modules, and subsequently Java, C++, OCaml and Python classes and objects.

This book is intended not only for computer science students and teachers but also seasoned programmers, who will find a guide to reading reference manuals and the foundations of program verification.

1
From Hardware to Software

This first chapter provides a brief overview of the components found in all computers, from mainframes to the processing chips in tablets, smartphones and smart objects via desktop or laptop computers. Building on this hardware-centric presentation, we shall then give a more abstract description of the actions carried out by computers, leading to a uniform definition of the terms “program” and “execution”, above and beyond the various characteristics of so-called electronic devices.

1.1. Computers: a low-level view

Computer science is the science of rational processing of information by computers. Computers have the capacity to carry out a variety of processes, depending on the instructions given to them. Each item of information is an element of knowledge that may be transmitted using a signal and encoded using a sequence of symbols in conjunction with a set of rules used to decode them, i.e. to reconstruct the signal from the sequence of symbols. Computers use binary encoding, involving two symbols; these may be referred to as “true”/”false”, “0”/”1” or “high”/”low”; these terms are interchangeable, and all represent the two stable states of the electrical potential of digital electronic circuits.

1.1.1. Information processing

Schematically, a computer is made up of three families of components as follows:

• – memories: store data (information) and executable code (the so-called von Neumann architecture);
• – one or more microprocessors, known as CPUs (central processing units), which process information by applying elementary operations;
• – peripherals: these enable information to be exchanged between the CPU/memory couple and the outside.

Information processing by a computer – in other terms, the execution of a program – can be summarized as a sequence of three steps: fetching data, computing the results and returning them. Each elementary processing operation corresponds to a configuration of the logical circuits of the CPU, known as a logic function. If the result of this function is solely dependent on input, and if no notion of “time” is involved in the computations, then the function is said to be combinatorial; otherwise, it is said to be sequential.

For example, a binary half-adder, as shown in Figure 1.1, is a circuit that computes the sum of two binary digits (input), along with the possible carry value. It thus implements a combinatorial logic function.

Figure 1.1. Binary half-adder

The essential character of a combinatorial function is that, for the same input, the function always produces the same output, no matter what the circumstances. This is not true of sequential logic functions.

For example, a logic function that counts the number of times its input changes relies on a notion of “time” (changes take place in time), and a persistent state between two inputs is required in order to record the previous value of the counter. This state is saved in a memory. For sequential functions, a same input value can result in different output values, as every output depends not only on the input, but also on the state of the memory at the moment of reading the new input.

1.1.2. Memories

Computers use memory to save programs and data. There are several different technologies used in memory components, and a simplified presentation is as follows:

• – RAM (Random Access Memory): RAM memory is both readable and writeable. RAM components are generally fast, but also volatile: if electric power falls down, their content is lost;
• – ROM (Read Only Memory): information stored in a ROM is written at the time of manufacturing, and it is read-only. ROM is slower than RAM, but is non-volatile, like, for example, a burned DVD;
• – EPROM (Erasable Programmable Read Only Memory): this memory is non-volatile, but can be written using a specific device, through exposure to ultra- violet light, or by modifying the power voltage, etc. It is slower than RAM, for both reading and writing. EPROM may be considered equivalent to a rewritable DVD.

Computers use the memory components of several technologies. Storage size diminishes as access speed increases, as fast-access memory is more costly. A distinction is generally made between four different types of memory:

• – mass storage is measured in terabytes and is made either of mechanical disks (with an access time of ~ 10 ms) or – increasingly – of solid-state drive (SSD) blocks. These blocks use an EEPROM variant (electrically erasable) with an access time of ~ 0.1 – 0.3 ms, known as flash memory. Mass storage is non-volatile and is principally used for the file system;
• – RAM, which is external to the microprocessor. Recent home computers and smartphones generally possess large RAM capacities (measured in gigabytes). Embedded systems or consumer development electronic boards may have a much lower RAM capacity. The access time is around 40–50 ηs;
• – the cache is generally included in the CPU of modern machines. This is a small RAM memory of a few kilobytes (or megabytes), with an access time of around 5 – 10 ηs. There are often multiple levels of cache, and access time decreases with size. The cache is used to save frequently used and/or consecutive data and/or instructions, reducing the need to access slower RAM by retaining information locally. Cache management is complex: it is important to ensure consistency between the data in the main memory and the cache, between different CPUs or different cores (full, independent processing units within the same CPU) and to decide which data to discard to free up space, etc.;
• – registers are the fastest memory units and are located in the center of the microprocessor itself. The microprocessor contains a limited number (a few dozen) of these storage zones, used directly by CPU instructions. Access time is around one processor cycle, i.e. around 1 ns.

1.1.3. CPUs

The CPU, as its name suggests, is the unit responsible for processing information, via the execution of elementary instructions, which can be roughly grouped into five categories:

• – data transfer instructions (copy between registers or between memory and registers);
• – arithmetic instructions (addition of two integer values contained in two registers, multiplication by a constant, etc.);
• – logical instructions (bit-wise and/or/not, shift, rotate, etc.);
• – branching operations (conditional, non-conditional, to subroutines, etc.);
• – other instructions (halt the processor, reset, interrupt requests, test-and-set, compare-and-swap, etc.).

Instructions are coded by binary words in a format specific to each microprocessor. A program of a few lines in a high-level programming language is translated into tens or even hundreds of elementary instructions, which would be difficult, error prone and time consuming to ...