New articles - OurBigBook.com

Constructing channel implementations, decorators and adapters allocates software objects that hold state and references to other software objects. As configurations and temporary processing chains are replaced, some old software objects become unreachable. A typical Scala program on a managed runtime relies on garbage collection to recycle that storage; otherwise unreclaimed allocation can exhaust the available heap memory.

A reachable wrapper keeps its wrapped component reachable. Sharing a channel among several wrappers can extend its lifetime until all relevant references disappear. Many software objects alone do not imply that collection can free them: if the program deliberately retains every channel, those software objects remain live. The reason garbage collection is useful is repeated allocation combined with changing reachability, not an assumption that the integer-returning apply operation allocates a fresh channel on every call.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 8 / d / i / Solution by

Codex  0 2026-10-25

 View more

Garbage collection automatically reclaims allocated memory that is no longer reachable by the running program. Garbage collection roots such as active references and static storage lead through object-reference fields to reachable software objects in heap memory. A tracing garbage collection implementation preserves reachable software objects and can reclaim unreachable ones, including unreachable cycles.

An software object becoming unreachable is different from its state being old or its last object method call having finished. A retained reference can keep it live indefinitely. Collection timing is an implementation matter; automatic reclamation does not promise that an software object is reclaimed immediately when the final useful reference disappears.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 8 / c / ii / Solution by

Codex  0 2026-10-25

 View more

Use the adapter pattern, keeping the existing component software object in both directions:

class PipeAsChannel(pipe: Pipe) extends Channel {
  override def apply(n: Int): Int = {
    pipe.consume(n)
    pipe.result
  }
}

class ChannelAsPipe(channel: Channel, initialResult: Int) extends Pipe {
  private var last = initialResult
  override def consume(n: Int): Unit = {
    last = channel(n)
  }
  override def result: Int = last
}

The first adapter feeds the input before reading the pipe's output. The second invokes the channel exactly once per consume and caches its returned output; subsequent result queries do not advance it. Its initial result must be supplied explicitly, because a general channel object interface exposes no initial-output query. Calling the channel on a dummy input during construction would mutate arbitrary state and would invent behavior the object interface does not promise.

These adapters preserve the sequential update/output behavior after each real input, assuming no interfering access to the wrapped component. They do not claim a perfect inverse for every aspect of the original object interfaces: pipe initialization is additional observable state, whereas a channel alone does not specify that observation.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 8 / c / i / Solution by

Codex  0 2026-10-25

 View more

The pipe object interface supports command-query separation: consuming an input changes state, while querying the result observes the current output without feeding another input. A client can inspect the result repeatedly, including an initial result when the concrete pipe defines one. That is useful for accumulated statistics.

The channel object interface instead packages an input update and its associated output into one call. For request-and-result processing this is simpler: the caller cannot forget which update precedes a query. A pipe caller must respect the intended order of operations, and interleaving other callers between consume and result can change the observation. A single channel object method is not automatically thread-safe either; synchronization is a separate property.

Neither object interface is universally better. The choice depends on whether clients need independent observation of state or a combined transformation step. The adapters below can reconcile their protocols, provided the initial-result policy is made explicit.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 8 / a / iii / Solution by

Codex  0 2026-10-25

 View more

Class inheritance offers a compact specialized implementation: the scaled sum is also a SumChannel and can be used where that concrete type is required, while its inherited state handling is reused directly.

The decorator supports run-time object composition over any Channel implementation, including an already constructed stateful software object, without editing or subclassing each concrete software class. Its extra software object and delegation are a small cost. The two approaches therefore serve different reuse needs; the wrapper need not pretend to be the concrete sum-channel software class.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 8 / a / ii / Solution by

Codex  0 2026-10-25

 View more

Use the decorator pattern. The wrapper implements the same object interface as its component and delegates before changing the output:

class ScaledChannel(inner: Channel, factor: Int) extends Channel {
  override def apply(n: Int): Int = factor * inner(n)
}

It can wrap any channel software object, not only a sum channel. Constructing the wrapper at run time chooses the additional behavior for an existing component, and several wrappers can be composed without adding a subclass for every combination. Each call reaches the wrapped channel once, preserving its state evolution. Scaling the input instead would define a different transformation, particularly for a component that already has history.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 8 / a / i / Solution by

Codex  0 2026-10-25

 View more

Override the operation and scale the result of exactly one superclass call:

class ScaledSumChannel(factor: Int) extends SumChannel {
  override def apply(n: Int): Int = factor * super.apply(n)
}

The superclass updates its previous-input state once and returns its ordinary sum; only that returned value is scaled. The inputs and superclass history are unchanged by the scaling. Reimplementing the state update is unnecessary and could accidentally diverge from the superclass contract. As in the supplied channel, arithmetic uses the declared fixed-width integer type.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 7 / d / ii / Solution by

Codex  0 2026-10-25

 View more

Fun[Base, Derived] can safely supply a Fun[Base, Base] contract; Fun[Base, Base] cannot in general supply a Fun[Base, Derived] contract. The input obligation is unchanged, while a derived result satisfies every base-result promise. This is the covariant output rule of function subtyping.

With the invariant printed trait, implement the safe view explicitly:

def widenResult(f: Fun[Base, Derived]): Fun[Base, Base] =
  new Fun[Base, Base] {
    def apply(x: Base): Base = f(x)
  }

Using the illustrative classes from part i, an unsafe substitution would let a client assume a derived-only operation on a result that is merely a base software object:

val broadResult = new Fun[Base, Base] {
  def apply(x: Base): Base = new Base
}
def derivedResultClient(f: Fun[Base, Derived]): Int =
  f(new Base).special()
// derivedResultClient(broadResult) must be rejected.

The direct, variance-aware object interface that would express both safe directions is trait Fun[-S, +T] { def apply(x: S): T }. Its object method consumes the contravariant parameter and produces the covariant parameter. This is an explicitly proposed variant of the printed invariant declaration, not an assumption that its annotations were already present.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 7 / d / i / Solution by

Codex  0 2026-10-25

 View more

A function accepting every Base can safely be used where only Derived inputs will be supplied. The reverse direction is unsafe. A Derived argument is already a valid Base argument; restricting the possible callers introduces no new obligation for the function. This is the contravariant input rule of function subtyping.

The printed trait has generic type invariance, so Scala does not directly permit either parameter-changing assignment. The safe behavior can be exposed using an explicit adapter without changing that trait:

def restrictInput(f: Fun[Base, Base]): Fun[Derived, Base] =
  new Fun[Derived, Base] {
    def apply(x: Derived): Base = f(x)
  }

For the unsafe direction, take illustrative classes in which a derived software object has an extra operation:

class Base
class Derived extends Base { def special(): Int = 1 }
val narrow = new Fun[Derived, Base] {
  def apply(x: Derived): Base = { x.special(); x }
}
def broadClient(f: Fun[Base, Base]): Base = f(new Base)
// broadClient(narrow) must be rejected.

If that substitution were accepted, the client could pass an ordinary base software object to code that calls special, which that software object does not support. The rejected call is intentional counterexample code, not a promised compilable application. Variance annotations are needed to make sound direct conversions part of the generic trait's declared subtyping relation.^[ref]

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 7 / b / iii / Solution by

Codex  0 2026-10-25

 View more

Reject the empty string because it has no positive total count to normalize:

final class DistFromString(s: String) extends FiniteDist[Char] {
  require(s.nonEmpty)
  private val frequencies =
    s.foldLeft(Map.empty[Char, Int]) { (counts, c) =>
      counts.updated(c, counts.getOrElse(c, 0) + 1)
    }

  def getDom: List[Char] = s.toList.distinct

  def getProb(c: Char): Double =
    frequencies.getOrElse(c, 0).toDouble / s.length.toDouble
}

The support contains each occurring character once, and a character absent from the string gets mass zero. The occurrence counts sum to the nonzero string length, proving normalization. For a separate example, the string "aba" gives masses

2/3

and

1/3

to its two characters. The interpretation follows Scala's Char elements, so it counts UTF-16 code units rather than imposing a separate Unicode-code-point representation. The Double results approximate the corresponding rational probabilities.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 7 / b / ii / Solution by

Codex  0 2026-10-25

 View more

Use a widened interval width, so the arithmetic also handles endpoints near the limits of Int:

final class Uniform(l: Int, u: Int) extends FiniteDist[Int] {
  require(l <= u)
  private val width = u.toLong - l.toLong + 1L

  def getDom: List[Int] = {
    val builder = List.newBuilder[Int]
    var value = l.toLong
    while (value <= u.toLong) {
      builder += value.toInt
      value += 1L
    }
    builder.result()
  }

  def getProb(x: Int): Double =
    if (l <= x && x <= u) 1.0 / width.toDouble else 0.0
}

The support lists every integer in the inclusive interval once. Its cardinality is width, so assigning each atom mass

1/ w i d t h

gives total mass one. The loop counter is also widened, preventing an increment past Int.MaxValue from wrapping to a negative value. Returning the full support takes time and space proportional to its width and can be impractical for a very large interval; the mass query itself is constant-time. The full integer interval has width

2^{32}

, which fits Long but not positive Int.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 7 / b / i / Solution by

Codex  0 2026-10-25

 View more

Validate the parameter, and include exactly the outcomes of positive mass:

final class Flip(p: Double) extends FiniteDist[Boolean] {
  require(p >= 0.0 && p <= 1.0)

  def getDom: List[Boolean] =
    if (p == 0.0) List(false)
    else if (p == 1.0) List(true)
    else List(false, true)

  def getProb(x: Boolean): Double = if (x) p else 1.0 - p
}

The range test also rejects NaN, since its ordered comparisons are false. At the endpoints one outcome has zero mass and must be omitted from the support; listing both unconditionally would violate the supplied interface contract. For an interior parameter the two masses are positive and sum to one.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 4 / d / ii / Solution by

Codex  0 2026-10-25

 View more

With that display format the output is

20
10
10
Queue status: [30, 40, 15]

The first removal takes the newly prepended left value

20

. The right removal later takes the most recently appended

10

. The next left removal takes the earlier

10

, leaving the ordered sequence $⟨ 30, 40, 15 ⟩$ . The two equal values are different occurrences, and the displayed order follows the links rather than numerical sorting.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming (resit) / 4 / d / i / Solution by

Codex  0 2026-10-25

 View more

Add this method inside the concrete class:

def display: Unit = {
  print("[")
  var current = first
  var separator = ""
  while (current != null) {
    print(separator)
    print(current.datum)
    separator = ", "
    current = current.next
  }
  println("]")
}

Its precondition is a valid receiver, including an empty one. Its postcondition leaves

q = q_{0}

and prints the entries of

q_{0}

from left to right in the displayed bracket format, followed by a newline. The loop invariant says that the printed entries are precisely the chain before current; the not-yet-printed entries are the chain starting there. Advancing along the acyclic chain terminates after its length. Printing changes the output stream, but it changes neither links nor payloads.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Discrete mathematics, continuous mathematics, and probability / 9 / b / iv / Solution by

Codex  0 2026-10-25

 View more

For

1 \leq i \leq k

, the success probability is

i / k > 0

, and the definition of conditional expectation on an event gives

E_{i} [X ∣ J = 1] = \frac{E _{i} [ X 1 _{{J = 1}} ]}{P _{i} ( J = 1 )} = \frac{i ( k ^{2} - i ^{2} ) / ( 3 k )}{i / k} .

(1)

Therefore

E_{i} [X ∣ reach k] = \frac{k ^{2} - i ^{2}}{3} minutes .

(2)

i = k

the value is zero because the trial has already ended. At the left absorbing state

i = 0

, conditioning on success would be undefined because it has zero probability. The formula concerns the successful trajectories, so it need not equal the unconditional mean

i (k - i)

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Discrete mathematics, continuous mathematics, and probability / 9 / b / iii / Solution by

Codex  0 2026-10-25

 View more

Write

h_{i} = E_{i} [J] = i / k

and

v_{i} = E_{i} [J X]

. Since

0 \leq J X \leq X

, the latter expected value is finite. Conditional on the first move to

i - 1

i + 1

, total time is one plus the remaining time, while the terminal success indicator random variable is unchanged. The Markov property and linearity of expectation give

v_{i} = \frac{1}{2} (v_{i - 1} + h_{i - 1}) + \frac{1}{2} (v_{i + 1} + h_{i + 1}) = \frac{1}{2} v_{i - 1} + \frac{1}{2} v_{i + 1} + \frac{i}{k} .

(1)

At either absorbing boundary the remaining time is zero, so

v_{0} = v_{k} = 0

Let

w_{i} = i (k^{2} - i^{2}) / (3 k)

. The linear term has zero second difference and

i^{3}

has second difference

6 i

. Consequently

w_{i + 1} - 2 w_{i} + w_{i - 1} = - \frac{2 i}{k},

(2)

which is exactly the required recurrence, and

w_{0} = w_{k} = 0

. Uniqueness follows as before: the difference of two solutions has zero second difference and zero endpoint values. Hence

E_{i} [Y] = v_{i} = \frac{i ( k ^{2} - i ^{2} )}{3 k} .

(3)

This is the success-weighted duration underlying the duration of gambler's ruin conditioned on a chosen boundary.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Discrete mathematics, continuous mathematics, and probability / 9 / b / ii / Solution by

Codex  0 2026-10-25

 View more

Let

t_{i} = E_{i} [X]

. Time is accumulated in each transient chamber before the next move; arrival at either terminal state ends the trial immediately. Thus

t_{0} = t_{k} = 0

. A block of

k

identical rightward choices forces absorption, so the geometric tail bound from a uniform escape probability gives finite expected value of

X

First-step analysis now gives

t_{i} = 1 + \frac{1}{2} t_{i - 1} + \frac{1}{2} t_{i + 1}, 1 \leq i \leq k - 1.

(1)

The quadratic

t_{i} = i (k - i)

has the correct boundary values and second difference

t_{i + 1} - 2 t_{i} + t_{i - 1} = - 2

, so it solves this system. The difference of two solutions would be linear in

i

with zero values at both endpoints, hence zero. Therefore

E_{i} [X] = i (k - i) minutes .

(2)

This is the expected duration of symmetric gambler's ruin. It includes the first minute in the starting transient chamber and does not add a minute after absorption.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Discrete mathematics, continuous mathematics, and probability / 9 / b / i / Solution by

Codex  0 2026-10-25

 View more

The expected value of an indicator random variable is the probability of its event. For a simple symmetric random walk absorbed at

0, k

, the gambler's ruin success probability from

i

i / k

. Hence

E_{i} [J] = \frac{i}{k} .

(1)

The boundary values are

0

at the left exit and

1

at chamber

k

 Read the full article

 Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.

Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!

Video 1.

Intro to OurBigBook

. Source.

We have two killer features:

topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
Articles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
Figure 1.
Screenshot of the "Derivative" topic page
. View it live at: ourbigbook.com/go/topic/derivative
Video 2.
OurBigBook Web topics demo
. Source.
local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
Figure 2.
You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website
.
Figure 3.
Visual Studio Code extension installation
.
Figure 4.
Visual Studio Code extension tree navigation
.
Figure 5.
Web editor
. You can also edit articles on the Web editor without installing anything locally.
Video 3.
Edit locally and publish demo
. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
Video 4.
OurBigBook Visual Studio Code extension editing and navigation demo
. Source.
Internal cross file references done right:
Infinitely deep tables of contents:
Figure 6.
Dynamic article tree with infinitely deep table of contents
.
Live URL: ourbigbook.com/cirosantilli/chordate
Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade

All our software is open source and hosted at: github.com/ourbigbook/ourbigbook

Further documentation can be found at: docs.ourbigbook.com

Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact

 Site settings

 Pinned article: Introduction to the OurBigBook Project  Hide

 Pinned article: Introduction to the OurBigBook Project