What is a procedure?

Question

Non-computer scientist here, trying to understand what SICP (Structure and Interpretation of Computer Programs) means by a procedure, whether it matches the dictionary definition, and also how a procedure relates to an algorithm (so maybe I should ask separate questions).

First, SICP defines a process:

We are about to study the idea of a computational process. Computational processes are abstract beings that inhabit computers. As they evolve, processes manipulate other abstract things called data. The evolution of a process is directed by a pattern of rules called a program. People create programs to direct processes. In effect, we conjure the spirits of the computer with our spells.

This seems clear to me (although I did struggle with it in the past). It mentions processes run by e.g. a modern operating system, (ultimately) on a computer. They are evolving manipulations of data directed by a pattern of rules which is a computer program inserted in memory and made up by instructions. I've taken my share of the From Nand To Tetris pt. I course to understand what this means.

Later on, it goes:

The most significant of these features is the fact that Lisp descriptions of processes, called procedures, can themselves be represented and manipulated as Lisp data.

I'm trying to conciliate this with the dictionary definition of procedure. I've bumped into the mention in SICP of a procedure receiving a name and being callable (or something like that; I couldn't find it again when I looked it up), so I suspect that both of them refer to the same concept. Also I'm aware that a process in the OS executes algorithmic instructions (i.e. instructions described by an algorithm), so this seems like a safe assumption to make.

Definition of algorithm

(...)

: a procedure for solving a mathematical problem (as of finding the greatest common divisor) in a finite number of steps that frequently involves repetition of an operation

broadly : a step-by-step procedure for solving a problem or accomplishing some end

Definition of procedure

(...)

2a (presumably related to 2b below) : a series of steps followed in a regular definite order

// legal procedure

// a surgical procedure

2b : a set of instructions for a computer that has a name by which it can be called into action

Definition of operation

(...)

8 : a single step performed by a computer in the execution of a program (see program entry 1 sense 6a)

Definition of program (Entry 1 of 2)

(...)

6a : a sequence of coded instructions that can be inserted into a mechanism (such as a computer)

I must admit that I struggle with definitions sometimes.

So, the 2b definition of procedure simply says a procedure is a set of instructions for a computer (should it have said a sequence of instructions I'd say it refers to the binary machine code in a program) that has a name (or, for that effect, any usable reference) by which it can be called into action. Despite it not being a sequence, it still sounds like it refers to a callable function.

So is the SICP definition the same as a function that can be called from its address (thinking of assembly, following a certain convention for passing arguments and returning a value)?

I've taken a look into the JavaScript edition of SICP and from what I recall it replaces procedures with functions in the text.

I'm aware that the Pascal programming language differentiates a procedure from a function. Based on my suspicion, it seems that all these definitions match (a Pascal procedure is the same as a SICP or dictionary procedure; and also simply a function that returns no value).

So do both definitions match? Or is a procedure something trickier than it seems?

Bonus question, which definition of a procedure can I use to define an algorithm?

Further dissecting the dictionary definitions, it seems to be that a) coded instructions are not the same as instructions (although both can be referred by the same name); b) an operation is the execution of a coded instruction by a processor, not the instruction itself; c) a procedure is defined as a set of instructions, possibly because a callable function in assembly is made up of multiple parts (i.e. the calling part which sets it up and the callee); d) in the definition of algorithm, I don't know what it means by repetition of an operation -- repetition of operations would make more sense to me.

P.S.: The question tags are a mess, but I'm not sure which ones to add.

Answer 1

A lot of this comes down to specific semantics. There are some core ideas that are switched around depending mostly on the language, I'll share the version that I'm used to and how they're different in different languages.

• A program is a complete list of instructions detailing receiving input, processing it, and producing output. It describes a sequence of operations, the smallest unit of action that a language can express, such as addition or control flow operations. Sometimes this is called a computation.
• A function is a named list of instructions that acts on some input, a sort-of shorthand for doing some nontrivial operation.
• An expression is anything which returns a value. This includes trivial operations like a + b, functions that return values, and other stuff. In essence, you can insert an expression into an equation of some sort. Usually these do not mutate the state of the input, but they may.
• A procedure is a function that does not return a value. Or in other words, functions that are not expressions. Usually these involve mutating the given state.
• An algorithm is a function that solves a specific provided problem (given as input) and eventually terminates.

These terms shuffle around depending on context, and even within one context. For instance, in Python, sorting can be a procedure list.sort() or an expression sorted(list). Python calls both of these methods, which in turn means something more specific in Java. In Rust, everything is an expression, and there is basically no such thing as a procedure. in SQL, functions are what I call named expressions, and procedures are what I call procedures. I'm not sure about Lisp specifically as I haven't worked with it much, but it seems to be like SQL with named expressions being their functions, and procedures being their procedures. The main point is that a lot of this is semantics and highly depends on context.

However, as SICP states, in their context understanding procedures is important. In SICP, the significance of a procedure is described in the quote you provide: it can be manipulated as data. This idea is a little tricky to define, but the book itself goes into a lot more detail on this further on (In my copy of 2nd ed. it's in section 2.1.3). In essence, it means you can use conditions on procedures to validate behavior.

Surprisingly, this idea is very difficult to formulate rigorously. There are two approaches to giving such a formulation... Both methods are surveyed in the paper by Liskov and Zilles (1975).

Answer 2

Almost every programming language has a way to specify sequences of instructions that can be reused (or used once). But programming languages don't agree on what these are called. Sometimes they are called procedures, or functions, or routines, or subroutines. I'm not aware of any languages which call them algorithms.

Apparently, in Lisp they are called "procedures" even though the keyword used to define them is defun.

It's best to treat these words as interchangeable, unless there is a specific context in which they have different meanings. You can see from the dictionary definitions you quoted that the words "algorithm", "procedure", "program" have at least one similar meaning - a sequence of steps to accomplish some task.

Visual Basic distinguishes between functions (which return values) and subroutines (which do not). Haskell distinguishes between functions (pure computations) and I/O operations. You wouldn't expect to find these distinctions in an English dictionary, but you would learn them when learning about these respective programming languages.

Dictionaries written for general audiences are not expected to have precise definitions of jargon - don't get caught up in the minutiae, like the fact your dictionary says a procedure has a name and an algorithm doesn't. These dictionary entries could have been written by different people at different times, and one thought of procedure names and one didn't. As you learn programming you will learn what each word means in the context in which you need to use it (such as a specific programming language) and the commonalities across different contexts.

It seems the author of SICP has chosen to use the word "process" to refer to the sequence of instructions, and "procedure" to refer to the way it is written in Lisp. I daresay that most programmers don't even make this distinction.

You might notice something similar in mathematical papers, too - authors will define precisely what they mean by certain words, and each paper may use a slightly different definition, while still conforming to the same general idea. For example, some papers will say that 0 is a natural number, and some will say it's not, but it doesn't matter because the set of integers greater than or equal to 1 by any other name smells just as sweet.

Answer 3

Disregarding the context of programming languages, a procedure is an unambiguous decomposition of a task in elementary operations, such that it can be performed mechanically. It is implicit that the "operator" knows how to perform the elementary operations.

E.g. the procedure to solve the Hanoi Towers problem is a sequence of disk moves from one stick to another.

The procedure can be described by a textual "program", but not necessarily.

An algorithm is a procedure, with the special characteristic that it solves a problem of general interest.

E.g. a sorting algorithm is a generic procedure that applies in a wide variety of situations.

Answer 4

Outside computing, a procedure is a way of doing things. It usually has specific steps in a specific order, possibly to be executed by different parties.

In computing, an algorithm is a way of performing a certain computational task. For instance, quicksort is an algorithm for inline sorting. In the case of distributed or concurrent algorithms, different parties may be involved. For instance, we may discuss algorithms to solve the dining philosophers problem.

In computing, and more specifically, software development, a procedure is an executable piece of code, written in a programming language, usually with a name and, optionally, arguments, that can be called from other code. When executing the procedure, the computer will do whatever the code specifies. For instance, a procedure may specify sorting an array of items using quicksort.

So in computing, a procedure is code; an algorithm is not. A procedure may implement an algorithm; it cannot be an algorithm. Algorithms are often described using pieces of code; either pseudo-code or code in an actual programming language. Such code is not the algorithm; it illustrates or implements the algorithm. The algorithm is the method being used by the code.

(As explained in other answers, terms used to describe programming languages tend to be specific to the language; for instance,

• in Algol, we have procedures;
• in C, we call them functions;
• in Fortran, we call them functions or subroutines, depending on whether they return a value or not;
• in Pascal, we call them functions or procedures, depending on whether they return a value or not;

and these are just four of the tens of thousands of languages out there.

So it's a challenge for textbook authors to find and use generic terminology when discussing these things.)