4
$\begingroup$

Starting with a representation of a item of computation as an object which includes a method says how to perform the next step of its computation.

// a statement, expression etc. class ExecutableThing { executeStep(C:Context ); }

Where context here is the execution environment including all the variables in scope.

Now consider a block which is an ordered collection of things to execute following the composite pattern, pseudo code below:

// a statement, expression etc. class ExecutableThing { X executeStep(C:Context ); } class Block implements ExecutableThing { vector<ExecutableThing> statements; X executeStep(C:Context); };

Where X represents an output that indicates what to execute next.

Is that definition sufficient to make it correct to call X a continuation?

There are different ways to think of this. Taking a very low-level view the vector of statements could be like machine code instructions. The block could be a linear representation of the entire program. X could be a token meaning increment the program counter. It could be the program counter itself (for implementing a jump instruction)

For a low-level model where X literally is the program counter would it still be correct to call that program counter a continuation?

Taking a higher level view where X exists in code (rather than being something happening inside a CPU) its a pointer to the next thing to step into. For the 'block' that pointer is (or includes) an iterator into the vector of statements. But is still essentially acting as a program counter.

In my mind a continuation normally includes a reference to the execution context. For example, at the very least, a pointer to an activation record in a stack. So calling X a continuation feels wrong.

Depending on your implementation the 'program counter' could literally be a variable in the context. Such that X means:

context.PC += 1 // for a normal 'statement' context.PC = address // for a jump statement.

Does that make the context its own continuation?

Are there rigorous definitions of the following terms that distinguish them from and relate them to each other?

  • Program Counter
  • Continuation
  • Context
  • Environment
  • Scope
  • Activation Record

I think its fair to start by saying that a program counter and an activation record are low level implementation details of one or more of the higher level concepts.

I've added environment and scope there as alternative words for context, though I personally think of scope as "set set of variables visible from a given execution context".

Here's what I have so far please fill in holes as appropriate

  • Program Counter

    • a low-level variable points to the next instruction to be executed.
    • typically a control flow register in a CPU

  • Continuation

    • an object which can be passed to something to indicate where control flow should proceed once its execution has completed.

  • Context

    • the environment in which something executes
    • includes variables in scope
    • may also includes some structures relating to control flow (for example pointers to parent contexts)

  • Environment

    • an alternative word for context

  • Scope

    • the set of variables visible from a given execution context This is more a logical concept than something you implement. For example in some implementations the variables in scope might be those from the
      current context and any of its parents

  • Activation Record

    • The implementation of a context as a stack frame
    • composing activation records produces a call stack
$\endgroup$

1 Answer 1

Reset to default
8
$\begingroup$

Some of the terms are ambiguous without additional context. However, here is generally how I would define them:

  • The program counter is a register of a machine (physical or abstract) that keeps track of the point of execution in a linear stream of instructions. In stored-program computers with addressable program memory, it usually corresponds to a memory address.

  • The continuation refers to “the remainder of the program” at any given point of evaluation. This can be represented in many different forms. In physical computers and CEK-style abstract machines, the continuation corresponds to the program counter and call stack. In reduction semantics, the continuation corresponds to the portion of the expression that is not the redex, which is the minimal subexpression currently being reduced.

    • A first-class continuation is a value in a programming language obtained by reifying (or capturing) the continuation at some point of execution. The continuation can then be applied or restored to either extend or replace the current continuation with the captured continuation.

    • A delimited continuation is a slice of the continuation delimited by some delimiting operator, like try ... catch. A first-class, delimited continuation is a delimited continuation reified as a value in the programming language.

    • All of this stuff can be very confusing without examples and diagrams. Fortunately, I gave a talk that goes into great detail just a few weeks ago, which has both.

  • A context can be any number of things, depending on… context. Sometimes it refers to an environment. Sometimes it refers to a continuation, particularly when called an evaluation context. But it is a very overloaded term.

  • An environment refers to a mapping from variables to types or values. An interpreter maintains an environment that keeps track of the values of variables that are in scope. A compiler maintains a type environment that keeps track of the types of variables within a particular expression.

    A common aspect of an environment is that it is extended within certain subexpressions in a program. For example, a lambda expression extends the environment within its body. So an environment can be thought of as a flattened mapping that captures a cascade of nested scopes.

  • The scope of a variable binding refers to all of the places where it is bound, i.e. places it can be referenced from.

    • Lexical scope refers to a scoping scheme where the scope of a variable is determined by the relative positions of expressions within the source code.

    • Dynamic scope refers to a scoping scheme where the scope of a variable is determined by the continuation (which is a dynamic property of program control flow).

    • Most modern languages use lexical scope, but dynamic scope is still common in the form of environment variables or (in most shells) shell variables.

  • An activation record is a stack frame that is pushed by the invocation of a procedure and is used to store the return address of its caller and any local variables. In many languages, especially imperative ones, the phrase “activation record” is effectively synonymous with “stack frame”, though some languages may also have other types of stack frames.

Going into great detail about each and every one of these terms would be far too broad for a single answer. Consider asking more specific followup questions if you want to learn more.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.