Carry the list as an immutable accumulator instead of storing it in a reference:
fun snackerPure m =
    let
      fun collect (Snack x, acc) = x :: acc
        | collect (Lunch (a, b), acc) =
            collect (b, collect (a, acc))
        | collect (Feast (a, b, c), acc) =
            collect (c, collect (b, collect (a, acc)))
    in
      collect (m, [])
    end;
For any initial accumulator acc, structural induction shows that collect(m,acc) equals the final reference content obtained by traversing m left to right and prepending each snack to a reference initially containing acc. At Lunch and Feast, the accumulator passed to each child is the result of all earlier children, exactly matching the imperative sequencing. Thus the result is the reverse of the left-to-right list of snack labels, just as for the original snacker; returning the ordinary left-to-right list would be incorrect. The code uses no mutable cells and is polymorphic, with type 'a meal -> 'a list.
An ML reference type 'a ref describes a mutable cell holding a value of type 'a. The operations are ref : 'a -> 'a ref for allocation, ! : 'a ref -> 'a for dereferencing and := : 'a ref * 'a -> unit for assignment. An immutable variable binding can name a mutable cell; assigning to the cell does not change what the binding denotes. Two names may alias the same cell, so an update through either is visible through the other.
val counter = ref 0;
val alias = counter;
counter := !counter + 1;
Both dereferences now give one. A reference's stored type remains fixed; the value restriction prevents allocating one unrestricted polymorphic cell and then using incompatible instantiations.
Imperative programming uses sequencing (e1; e2; ...; en) to perform effects left to right, with the final expression supplying the result. Conditional expressions choose one branch. while condition do body repeatedly checks a Boolean condition and performs a unit-valued body, returning () on termination. Standard ML has no required primitive for loop, but recursion or a reference with while supplies one. For example:
fun sumTo n =
    let val i = ref 1
        val total = ref 0
    in
        while !i <= n do
          (total := !total + !i; i := !i + 1);
        !total
    end;
References provide mutable state; sequencing, conditionals and loops control its updates.
If f : 'a -> 'b, then the success constructor applied to f x has type 'b result, and the exception alternative has that same type. Therefore
what : ('a -> 'b) -> 'a -> 'b result
The zero comparison fixes the labels to type int, and tony with this predicate accepts an int tree and normally produces a Boolean. The requested expression consequently has type
int tree -> bool result
so the wrapper maps an integer tree to a packaged Boolean result or exception packet.
For ta, the packet Ian true means that a normal successful search occurred: ta has at least one root-to-Lf path all of whose branch labels are nonzero. It can be Lf; if nonempty, its root must be nonzero, but labels away from the successful path need not be. For example, Br(1,Lf,Br(0,Lf,Lf)) succeeds despite containing a zero.
For tb, Cherie Blair means that the search raised the designated exception. Every root-to-Lf path has a zero-labeled branch somewhere. Thus tb is nonempty, but its root need not be zero: Br(1,Br(0,Lf,Lf),Br(0,Lf,Lf)) fails. With the supplied total comparison predicate, tony can return only true or raise Blair, never return false. ta admits an all-nonzero path; tb admits none.
The ML exception type exn contains exception packets and is an extensible datatype: an exception declaration introduces a fresh constructor, optionally with an argument. For example:
exception Empty;
exception BadIndex of int;
Empty has type exn, and BadIndex has type int -> exn. These packets are ordinary values which can be passed, returned or stored. raise propagates a packet; the resulting expression can have whatever result type its surrounding context requires, because normal evaluation does not return from the raise.
In exception handling, expression handle pattern => recovery evaluates the recovery for a matching exception packet and otherwise propagates the packet outward. The normal expression and recovery must have the same result type. Handlers are dynamically nested, and exceptions raised in the recovery are not handled again by that same handler. A variable pattern catches every packet, whereas a constructor pattern selects a particular exception. Separate fresh exception declarations create distinct identities even if their printed names coincide; exception rebinding instead aliases an existing constructor. exn packages exceptional information; raise and handle determine its control-flow effect.
The inference is false in both directions. Although String is a subtype of Object, generic type invariance means that neither Vector<String> nor Vector<Object> is a subtype of the other. If a string vector could be used as an object vector, an arbitrary object could be inserted into storage promised to contain strings. Conversely, an object vector may already contain an Integer, so it cannot satisfy the contract of a string vector.
Both parameterizations are subtypes of the ordinary class Object, but this does not create a subtype relation between their element parameterizations. For a view accepting vectors with different element types, Vector<?> is appropriate; a Vector<? extends Object> similarly allows retrieval as Object without arbitrary non-null insertion. A Vector<? super String> accepts insertion of strings but does not promise that retrieved elements are strings. The stated subclass relationship does not hold: mutable generic vectors are invariant.
Replace type parameters by their erasures, normally Object or the first declared bound, and insert checked casts where an erased result is used as its former specific type. A simple generics in Java example becomes:
// Generic version
Vector<String> names = new Vector<String>();
names.add("Ada");
String s = names.get(0);

// Non-generic version
Vector names = new Vector();
names.add("Ada");
String s = (String) names.get(0);
The two fragments are alternatives, not consecutive declarations in one scope. For a user-defined Box<T>, replace fields, parameters and returns of type T by Object, and cast the retrieved result. Bounded parameters instead erase to their bound. A full translation must also preserve method dispatch where erasure changes overridden signatures, using suitable forwarding methods; this is the principle of type erasure, not simply deleting every pair of angle brackets.
The raw collection permits accidental insertion of an unrelated object, which may fail much later at a cast. The generic collection rejects such insertion during compilation, documents its contract at the declaration, and eliminates repetitive casts at use sites. The generic version catches more errors earlier and expresses the programmer's intended element type directly. Generic types are largely erased at runtime, so their advantage is static checking rather than a new runtime vector representation. The translation mechanism is specified by the Java language specification.
A generic class, interface or method in Java is parameterized by one or more types. Generics in Java allow one implementation of a collection or algorithm to be reused with different reference types while checking the allowed values and results statically. For example:
Vector<String> names = new Vector<String>();
names.add("Ada");
String first = names.get(0);

class Box<T> {
    private T value;
    public void put(T x) { value = x; }
    public T get() { return value; }
}
The type parameter is declared inside angle brackets, as in Box<T>, and supplied as a type argument, as in Box<String>. A generic method places its parameter list before its return type, for example static <T> T identity(T x). Bounds such as <T extends Number> restrict type arguments, and wildcards such as ? extends Number or ? super Integer describe restricted views. Primitive values require wrapper types such as Integer rather than a type argument int. Generics provide reusable code with compile-time checking of element types.
Set-user-ID execution of a suitable executable makes its effective user identity that of the owner. When that owner is root, running it can give root privileges even to an otherwise unprivileged caller. World-write permission destroys the trust boundary: any user can alter the privileged executable, potentially substituting code which performs arbitrary privileged operations. World-execute permission then makes the compromised program available to everyone.
World-read access can reveal implementation details or embedded secrets, but reading alone is not the decisive privilege-escalation flaw; properly designed public set-user-ID utilities need not keep their code secret. Some Unix kernels clear the set-user-ID bit after an unprivileged modification. That is a mitigation, not a reason to maintain a world-writable privileged program: if the bit persists or is restored without validating the changed code, the privilege escalation remains. Root-owned privileged executables must not be writable by untrusted users.
First, suppressing kernel preemption simplifies protection of shared kernel data on a uniprocessor: another ordinary kernel execution cannot be scheduled in the middle of a short update which temporarily breaks an invariant. Fewer paths require preemption-specific locking and reentrancy handling, making the operating-system kernel easier to implement correctly.
Second, it avoids involuntary kernel context switches and their scheduler, register-save and cache-disruption costs, and can make the execution of short kernel operations more predictable. The tradeoff is greater scheduling latency if a kernel operation runs too long. Simpler synchronization and lower switching overhead are the two reasons. Non-preemptive kernel code can still receive interrupts or block voluntarily, and multiprocessor execution still requires synchronization; non-preemption is not a substitute for all locking.
Both kinds of context switch save and restore registers, a program counter, stack pointer and scheduler state. Switching between operating-system processes additionally changes the address-space and protection context, including the page-table root. Cached translations must be invalidated or distinguished by address-space identifiers, and the new process may have a different memory and cache locality.
Software threads of one process share its address space and most resources, so a thread switch normally preserves the page-table root and valid cached translations; only the execution context, stack and thread-specific state need change. Thus a process switch requires address-space management which a same-process thread switch usually avoids. Tagged translation caches can reduce the extra cost, so a complete translation lookaside buffer flush is not an inevitable feature of every process switch.
The working set is the set of virtual pages referenced by an operating-system process within a recent window of execution time or memory references. Its size estimates the number of frames needed for the process's current locality of execution. It is a set of recently used pages, not the entirety of the process's address space.
An operating system can estimate it from reference bits or fault history and try to keep those pages resident. Process scheduling and admission control should avoid simultaneously running processes whose combined working sets exceed physical memory; suspending some processes or reducing multiprogramming then allows the rest to make useful progress. If too many active pages compete for too few frames, repeated page faults produce memory thrashing. Working sets connect memory allocation to the choice of processes allowed to run.
The Fermat-Euler theorem states that for integers and with ,
where Euler's totient function counts the residue classes coprime to . The case is trivial. For , list a reduced residue system . Multiplication by permutes these classes: each is coprime to , and implies since has a multiplicative inverse modulo . Multiplying the permuted residues gives
The product is itself coprime to and can be cancelled using its inverse, proving the theorem.
The integer 359 is prime: none of the primes , all the primes not exceeding , divides it. Therefore and 60 is coprime to 359. Using the supplied congruence and the Fermat-Euler theorem,
Now express the decimal expansion by long division. Put and for define
Thus , and none of these remainders is zero. The congruence implies ; since both are the unique representatives between zero and 358, they are equal. A digit is determined by the preceding remainder, namely , so
This proves the required pure periodicity from the first digit. In fact its least period is 179: the multiplicative order of 10 modulo 359 divides the prime 179 and is not one, since . The connection between the remainder recurrence and the period is the decimal period from multiplicative order.
Suppose is a prime number, and . Since the only positive divisors of are one and , the greatest common divisor of and is one. By Bézout's identity, integers exist with . Multiplying by gives . Both terms on the left are divisible by , so . Thus Euclid lemma gives
The fundamental theorem of arithmetic says that every positive integer greater than one is a product of prime numbers, uniquely up to their order. Existence follows by strong mathematical induction: if is prime it already has a factorization; otherwise with , and the factorizations of combine to factor .
For uniqueness, suppose are two prime factorizations. Repeated application of Euclid lemma makes divide one of the , so primality forces . Reorder that factor to the front, cancel it and repeat. Neither side can retain extra primes when the other has become one, since every prime exceeds one. The two multisets are therefore identical. For a negative integer there is additionally the uniquely determined sign; one has the empty positive factorization, and zero is excluded. The prime-product divisibility lemma is the step which makes factorization unique.
Add a public override of toString in each concrete subclass. In TypeVar:
public String toString() {
    return "t" + id.toString();
}
In Arrow:
public String toString() {
    return "(" + from.toString() + " -> " + to.toString() + ")";
}
Inherited dynamic dispatch selects the proper method at every node of the abstract syntax tree. Full parentheses distinguish the domain and codomain nesting without relying on a reader's precedence convention. Repeated occurrences of one type variable use the same identifier, and distinct factory variables have distinct identifiers. For example, with the first three factory variables, the type from part (b) prints as ((t1 -> t2) -> (t2 -> t3)). The recursive textual form preserves both arrow structure and variable identity.
Introduce a checked exception class, for example in its own source file:
public final class ItDoesDependOn extends Exception {
    private final MLType.TypeVar variable;
    public ItDoesDependOn(MLType.TypeVar variable) {
        this.variable = variable;
    }
    public MLType.TypeVar getVariable() { return variable; }
}
Declare the required abstract method in MLType:
public abstract void mustNotDependOn(TypeVar a)
    throws ItDoesDependOn;
Within the nested TypeVar class implement it by an identity check:
public void mustNotDependOn(TypeVar a) throws ItDoesDependOn {
    if (this == a) throw new ItDoesDependOn(a);
}
Within the nested Arrow class implement it recursively:
public void mustNotDependOn(TypeVar a) throws ItDoesDependOn {
    from.mustNotDependOn(a);
    to.mustNotDependOn(a);
}
The parameter denotes an actual non-null type variable returned by the factory; checking object identity distinguishes different variables without confusing their printed names. Structural induction on the abstract syntax tree proves the occurs check: a variable node contains the queried variable exactly when the identities match, and an arrow contains it exactly when either component does. The first detected occurrence throws and propagates the checked exception; normal return proves absence. Both subclass methods must declare the exception, and callers must catch or declare it.
For , either recursive branch detects each of , whereas a distinct is absent and the call returns. A recursive identity-based occurs check throws exactly when the queried variable occurs.
Represent the two constructors of the type grammar by subclasses of MLType: a TypeVar node and an Arrow node containing two types. Use immutable fields so a completed type expression cannot acquire cycles through later mutation. The static factory allocates a fresh object and gives it a fresh identifier shared across the whole hierarchy:
import java.math.BigInteger;

public abstract class MLType {
    private MLType() { }
    private static BigInteger next = BigInteger.ONE;

    public static synchronized TypeVar createNewTypeVar() {
        TypeVar answer = new TypeVar(next);
        next = next.add(BigInteger.ONE);
        return answer;
    }
    public static final class TypeVar extends MLType {
        private final BigInteger id;
        private TypeVar(BigInteger id) { this.id = id; }
    }
    public static final class Arrow extends MLType {
        private final MLType from, to;
        public Arrow(MLType from, MLType to) {
            if (from == null || to == null)
                throw new IllegalArgumentException();
            this.from = from; this.to = to;
        }
    }
}
The nested classes are public for use by clients, while their fields are private; TypeVar can be created only through the factory. Client code uses MLType.TypeVar and MLType.Arrow. A type variable is identified by its unique node, and a function type by its domain and codomain nodes; repeated occurrences of one logical variable share the same TypeVar object.
The monotonically increasing BigInteger identifier avoids fixed-width counter overflow, and synchronization prevents two simultaneous calls from receiving the same identifier. Actual allocation remains subject to available memory. This is an abstract syntax tree representation, possibly sharing subexpressions. Fresh variable nodes and recursive arrow nodes represent every type in the given grammar.
Assume head comparison and construction of one list cell take constant time. In the merge algorithm, every comparison removes one head from the recursive inputs, and evaluation stops as soon as either is empty. For lengths , at most comparisons and the same number of newly constructed cells are required; the untouched suffix is shared. Inputs which keep both lists nonempty until the last comparison attain this bound. Thus
An initially empty input makes this particular implementation constant-time; not every pair requires linear work.
The balanced merge sort spends time per call on list length, splitting and merging. Hence its time complexity satisfies
At each recursion level the lengths of its disjoint subproblems sum to , so the work per level is , and balanced splitting gives levels. Consequently
The length and splitting traversals change the constant factor, not this asymptotic order; repeatedly inserting elements into a sorted list would not give the same complexity.
Split the list into two contiguous halves, sort each recursively, and use the merge algorithm from part (a):
fun mergesort [] = []
  | mergesort [x] = [x]
  | mergesort xs =
      let
        val k = List.length xs div 2
        val left = List.take (xs, k)
        val right = List.drop (xs, k)
      in
        merge (mergesort left, mergesort right)
      end;
List.length counts elements, List.take(xs,k) returns the first elements and List.drop(xs,k) returns the remaining suffix. Since when , both recursive inputs are smaller and differ in length by at most one. Mathematical induction on length proves that each half is sorted without losing elements, and the correctness of the merge algorithm proves the same for the combined result. Contiguous splitting and left-biased equal-key merging preserve the original relative order of equal keys. This is a stable top-down merge sort.

There are unlisted articles, also show them or only show them.