Chapter 4: Linguistic Realization of Algorithms: Low-Level Programming Languages

abstract model

technique that derives simpler high-level conceptual models for a computer while exploring the science of what new algorithms can or cannot do

allocated memory

memory region set aside to hold a value

archive file

.a file that contains a static library

Arduino

hardware platform intended for creating simple, low-cost hardware for educational or hobbyist purposes

assembler

program that translates assembly language source code into machine code

assembly language

low-level language in which every statement corresponds directly to a machine instruction

BASIC

early high-level programming language

binary code

program in the native format that is understood by a CPU, which is a long series of 0s and 1s

C

middle-level language that has been in wide use since the 1970s

C++

middle-level object-oriented language based upon C

central processing unit (CPU)

computer chip capable of executing machine code programs

child thread

thread that is started by the parent thread, and only runs for a limited period in a parallel section

Church-Turing Thesis

scientific theory stating that an algorithm can be converted from any reasonable computational model to another

Clang

open-source C compiler developed by the LLVM project

code relocation

merges separate code and data sections into single sections (one for code and one for data)

compiler

(also: interpreter) program that translates source code from a middle-level or high-level language into something a computer can read

computational model

system for defining what an algorithm does and how to run it

concurrent programming

situation where multiple programs or tasks are running at the same time, regardless of whether they are using multiple processors or sharing one processor

core

individual processor built into a CPU chip

declarative programming

paradigm in which code dictates a desired outcome without specifying how that outcome is achieved

device driver

piece of code that is responsible for connecting to a hardware component such as a video card or keyboard

distributed computing

specific form of parallel programming where processors are working together in parallel, but the processors are in multiple connected computers, not a single computer

executable and linkable format (ELF)

standard binary format for object code

external reference

symbol that is used in a module, but not defined in that module, so is expected to be defined in some other module

firmware

very low-level code that communicates directly with hardware, providing a convenient interface for other software

freed memory

memory that is given back to be reused when a value is no longer needed

functional programming

paradigm in which algorithms are written as mathematical functions

GCC

open-source C compiler developed by the GNU Project

Git

widely-used version control system

GitHub

website that allows free storage of public git repositories

GOTO

non-structured operation that instructs a computer to jump to an entirely different part of the program

graphics processing unit (GPU)

massively-parallel processor that supplements a CPU; GPUs were originally designed for rendering real-time graphics in video games

hardware model

design for a how a specific physical computer executes algorithms

high-level programming language

programming language that operates at a high level of abstraction, meaning that low-level details such as the management of memory are automated

imperative programming

paradigm in which the programmer writes a series of steps that must be followed in order

instruction set architecture (ISA)

type of hardware model that defines a list of operations that a CPU can execute

integrated development environment (IDE)

program with a graphical user interface that includes a text editor, compiler, and other tools, all in one application

interpreter

(also: compiler) program that translates source code from a middle-level or high-level language into something a computer can read

invalid pointer

pointer that does not hold a valid location

kernel

core part of an operating system that is responsible for managing and interfacing with hardware components

Lambda calculus

abstract computational model defined by Alonzo Church that inspired the functional programming paradigm

level of abstraction

degree to which a computational model, programming language, or piece of software relates to computer hardware

library

file that contains object code for functions and global variables that are intended to be reused

linker

program that performs linking

linking

process of collecting and combining various pieces of object code into a single program file that can be loaded into memory and executed

Linux

open-source operating system kernel that is Unix-compatible

load time linking

when dynamic linking happens at the same time a program executable is first run

low-level programming language

programming language that operates at a low level of abstraction, meaning that code is similar to machine code

machine code

sequence of binary digits (bits) that can be understood and executed directly by a computer

memory leak

occurs when some memory is allocated but never freed

memory management

process of allocating and freeing memory

message passing

parallel programming approach where separate processes communicate only by sending messages, not sharing memory

Message Passing Interface (MPI)

message-passing interface that was first developed in the 1990s

middle-level programming language

programming language that is somewhat abstracted above low-level, but not as much as a high-level programming language; allows direct hardware access

modularity

property of code that allows it to be divided into a small, reusable piece

multicore

CPU chip that contains more than one core

object

a program value that has both data, or variables, and procedures that work together to represent a specific human concept

object-oriented programming

paradigm in which code is organized into objects, where each object has both data and procedures

OpenMP

library for parallel programming in the SMP model

operating system

software that provides a platform for applications and manages hardware components

operator

fundamental programming operation that combines values

parallel computer

multiple-processor system that supports parallel programming

parallel computing

practice of making productive use of parallel computers

parallel programming

computer programming technique that provides for executing code in parallel on multiple processors

parent thread

thread that runs from the program beginning through the end, and starts and manages child threads

pointer

variable that holds the memory address of another variable and points to that variable

procedural programming

paradigm in which code is organized into procedures

procedure

function in the context of programming

programming language paradigm

philosophy and approach for organizing code

programming model

design for humans to read and write

Random Access Machine

abstract computational model used to analyze the efficiency of algorithms

repository

container for files and related information stored in a version control tool

runtime linking

when linking occurs after a program has already started running

Rust

a relatively new middle-level programming language created by the Mozilla Foundation in the 2010s

segmentation fault

occurs if the subscript is very far out of range

semantic error

when code compiles and runs, but does not behave as it should

shared library

library file that can be shared by multiple programs at the same time

shared memory

programming model in which processes/tasks share a common address space, which they read and write to asynchronously

socket

Internet connection between two computers

source code

text of a program written in a programming language

static library

simple kind of library that that copies the contents of object files into a single file called an “archive”

structured programming

paradigm in which control flow is always controlled with conditionals (“if”) or loops (“while”) and never GOTO

symbol

identifier for a function or global variable

symbol resolution

during the symbol resolution step, the linker associates each symbol reference with exactly one symbol definition

symbol table

array of structures in which each entry includes name, size, and location of symbol

symmetric multiprocessor (SMP)

model in which there are multiple parallel processors that are practically identical

systems software

programs that provide infrastructure and platforms that other programs rely upon

thread

light-weight parallel execution path that shares memory with other threads

Unix

operating system that has been used widely, primarily in servers and software development since the 1970s

version control

tools that are used to store and improve multiple versions of project files and support team collaboration, and the ability to revert to an earlier versions

Visual C++

proprietary-license C and C++ compiler developed by Microsoft