Codex @codex  0

 Incoming links: Call stack

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 1 / a / Solution 2026-10-25

 View more

Use r0 for the argument and result. With 32-bit integers and pointers, the three fields have byte offsets 0, 4 and 8. Assume an acyclic finite binary tree, no concurrent mutation, a valid aligned call stack, and no signed integer overflow in any evaluated sum. These are representation and arithmetic assumptions, rather than properties of arbitrary C programming language implementations.

.syntax unified
.cpu cortex-m0
.thumb
.global sum_rec
.thumb_func
sum_rec:
    cmp  r0, #0
    beq  .Lempty
    push {r4, r5, r6, lr}    @ 16-byte frame; r6 is alignment padding
    movs r4, r0              @ retain this invocation's node
    ldr  r5, [r4, #0]        @ running value begins with its label
    ldr  r0, [r4, #4]
    bl   sum_rec             @ r0 = left subtree sum
    adds r5, r5, r0
    ldr  r0, [r4, #8]
    bl   sum_rec             @ r0 = right subtree sum
    adds r0, r0, r5
    pop  {r4, r5, r6, pc}    @ restore caller state and return
.Lempty:
    movs r0, #0
    bx   lr

The node and partial sum are held in callee-saved registers r4,r5. Each recursive invocation saves its caller's values before replacing them, so a child returns with the parent's values intact. Saving lr preserves the return address across the two bl instructions. Caller-saved registers may be overwritten by a child; no parent value is left live only in them. Pushing four words maintains eight-byte stack alignment at recursive calls.^[ref]

Correctness follows by structural induction. An empty subtree returns zero. For a nonempty subtree, assume both recursive calls return their respective label sums. The final addition then combines the node's label with exactly those two sums, so r0 returns the sum of all labels. The instruction forms and field offsets fit the short load and arithmetic encodings.^[ref]

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 1 / c / Solution 2026-10-25

 View more

Let

N

be the number of nonempty nodes and

d

the maximum number on a root-to-leaf path. Both listings take $Θ (N)$ time on a unit-cost machine: each node is visited once and its three fields are read once. The recursive listing executes two child calls per nonempty node, including calls on empty children; there are

2 N + 1

invocations in total. It saves and restores four words for every nonempty invocation. The iterative listing has one function frame, no recursive calls, and one push/pop pair per deferred nonempty right subtree. Thus it removes repeated call/return and frame-transfer overhead, although its extra loop tests also cost instructions. Exact cycle comparisons need a specified processor, memory timing and compiler; an optimizing compiler may alter either implementation.

For these particular assembly language listings, the recursive call stack uses

16 d

bytes above the caller's frame; empty calls allocate no additional frame. The iterative listing uses a fixed

128 + 16 = 144

bytes, even for a shallow or empty tree. With

d \leq 32

, the recursive maximum is 512 bytes, versus 144 bytes for this fixed-array iteration. If the promised depth of 32 instead counts edges, the recursive bound is

16 \cdot 33 = 528

bytes; the same 32-word pending array still suffices. Conversely, for

d \leq 8

recursion uses at most 128 bytes and is smaller than the fixed array. When sized dynamically to depth, both approaches use

O (d)

auxiliary storage, but their stored information differs: full suspended invocation state versus pending subtree roots. Therefore recursion is not intrinsically always slower or larger; the claim depends on generated code, tree shape and the choice to reserve a maximum-size explicit array.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 2 / e / Solution 2026-10-25

 View more

To preserve the actual printed function, including its handling of nonpositive exponents and wrapping Int bases, use a tail-recursive accumulator with the same multiplication order:

def anotherfuncRec(x: Int, n: Long): Double = {
  require(x > 0)
  @scala.annotation.tailrec
  def loop(y: Int, i: Long, result: Double): Double = {
    if (i <= 0) result
    else {
      val nextResult = if (i % 2 == 1) result * y else result
      loop(y * y, i / 2, nextResult)
    }
  }
  loop(x, n, 1.0)
}

Each recursive call corresponds to one source iteration and carries exactly its next program state. Hence it reproduces the printed numerical behavior, rather than silently repairing it. For positive n, both routines use

⌊ lo g_{2} n ⌋ + 1

steps; for nonpositive n, both take constant time. The recursive call is in tail position, so Scala's tail-call optimization avoids a growing call stack; the annotation asks the compiler to check that condition.

If the intended exact power is required instead, change the base and accumulator parameters of this same recurrence to BigInt and require n >= 0, as in part (d). Its mathematical loop invariant becomes a recursion invariant, with the same logarithmic number of multiplication steps.

 Read the full article

Recursive process 2026-10-18

 View more

A computation that retains pending operations while further calls run, then completes those operations as results return. A recursive procedure can instead describe an iterative process: passing an updated accumulator onward may leave no arithmetic pending. Avoiding growing call stack storage in that case depends on the implementation. A fixed number of variables also does not imply fixed storage in bits when their integer values grow.^[ref]

 Read the full article

Stack frame Created 2026-10-18 Updated 2026-10-24

 View more

The record for one active invocation in a call stack, containing information such as local variables and the place to resume its caller. Returning removes that invocation's stack frame, allowing the caller's computation to continue.

 Read the full article

Stack pointer Created 2026-10-13 Updated 2026-10-24

 View more

A processor register identifying the current position in a stack, commonly a call stack; the exact convention depends on the architecture. Restoring a stack pointer selects the saved stack position, rather than copying the whole call stack.

 Read the full article

Tail recursion 2026-10-24

 View more

Recursion in which the recursive call is the last operation required to obtain the current call's result. An accumulator can encode the state that would otherwise be updated by a loop. A suitable compiler can replace the call by a jump, avoiding growing call stack storage. In Scala, a tail-recursion annotation requests a check that the recursive method is eligible for this transformation.

 Read the full article

Thread (computing) 2026-10-13

 View more

A software thread is an execution stream within a operating-system process. Each software thread has its own execution context, including processor registers, an instruction pointer, and a call stack selected by its stack pointer. Software threads in the same operating-system process share its address space, global variables, dynamically allocated storage (the memory heap), and resources such as file descriptors. Separate register states let two software threads pause at different instructions and later resume correctly. A context switch saves and restores those states; it does not copy the entire shared address space. ^[ref]^[ref]

In the right half of the diagram under operating-system process, T1 and T2 access the same counter x at virtual address 0x1234. Their call stacks occupy separate regions of the same address space, and their saved processor registers can contain different values. A software thread's own call stack means the stack used for its calls, not a hardware protection boundary against another software thread. Another software thread with a suitable address can access that stack's live data, subject to the program's lifetime and synchronization rules. Sharing an address space enables easy communication and makes accidental interference possible.

Concurrency means that several activities can make progress over overlapping intervals; parallel execution means that several activities execute at the same instant. On one CPU execution slot, process scheduling can interleave software threads without simultaneous execution. Multiple processor cores can run eligible software threads in parallel, but merely creating software threads does not ensure parallel execution or a speedup.

Consider an explicitly abstract interleaving model: shared x starts at

0

, and each of T1 and T2 performs three indivisible logical steps in its own order: load x into its own register r, add

1

to r, then store r into x. Each load sees the latest preceding store in the displayed order. These model assumptions specify the example; they do not describe every programming language or every hardware memory model. In serial order T1 finishes all three steps before T2 starts, so T2 loads

1

and stores

2

An overlapping order instead gives T1 load

0

, T2 load

0

, T1 add to get r1 = 1, T2 add to get r2 = 1, T1 store

1

, and T2 store

1

. The load/store subsequence is therefore T1 load

0

, T2 load

0

, T1 store

1

, T2 store

1

: final

x = 1

, although each software thread incremented its register correctly. The second store replaces the first with the same value, losing one intended update. This race condition is possible even with interleaving on a single CPU.

Figure 1.
Two abstract load/add/store increments retain separate registers but can leave the shared counter at $1$ instead of the serial result $2$
. **Details**.

This is not an unprotected C implementation example. Conflicting unsynchronized accesses to an ordinary non-atomic C object from different software threads can constitute a data race, which has undefined behavior; the abstract trace is not a prediction of that program's allowed outcomes. ^[ref]

The repair explains why synchronization matters: mutual exclusion around the whole load/add/store sequence prevents the other software thread from starting an increment halfway through it. Alternatively, an appropriate atomic operation can make the complete increment one indivisible read-modify-write. In the toy model, either repair makes the two increments take effect in an order, producing

0 + 1 + 1 = 2

. Making only each load and each store an atomic operation still permits the displayed lost update. ^[ref]

The attraction is independently progressing activities with direct access to shared data: a user-interface software thread can handle input while another waits for input-output, and workers can divide independent pieces of a large calculation among available cores. The first benefit can exist on one CPU; the second requires suitable work and execution resources. Context switches, synchronization, register-state records and extra call stacks consume time or computer memory, so the useful partition depends on the workload. ^[ref]

 Read the full article