User:Tobias Bergemann/Scratch

From Wikipedia, the free encyclopedia

< User:Tobias Bergemann

1 History of Scheme
- 1.1 Older standards
- 1.2 History of call/cc
2 Shannon entropy: characterization

[edit] History of Scheme

[edit] Older standards

RRS ("The Revised Report on Scheme", G.L. Steele et al, AI Memo 452, MIT, Jan 1978)
R²RS ("The Revised Revised Report on the Algorithmic Language Scheme", Clinger, AI Memo 848, MIT Aug 1985)
R³RS ("Dedicated to the Memory of ALGOL 60", Revised(3) Report on the Algorithmic Language Scheme)
R⁴RS (Revised(4) Report on the Algorithmic Language Scheme)

R⁵RS and R⁶RS are already referenced from Scheme (programming language).

[edit] History of `call/cc`

interaction with dynamic-wind (R5RS call/cc & dynamic-wind in terms of r4rs, faking dynamic-wind, dynamic-wind, A new specification for dynamic-wind, call/wc, and call/nwc, implementing dynamic-wind)
interaction with values and call-with-values

[edit] Shannon entropy: characterization

Information entropy is characterised by these desiderata:

(Define $p_i=\Pr(X=x_i)$ and $H_n(p_1,\ldots,p_n)=H(X)$ )

The measure should be continuous and symmetric — i.e., changing the value of one of the probabilities by a very small amount should only change the entropy by a small amount, and the measure should be unchanged if the outcomes x_i are re-ordered:

$H_n\left(p_1, p_2, \ldots \right) = H_n\left(p_2, p_1, \ldots \right)$ etc.

The measure should be maximal for uniformly distributed events (uncertainty is highest when all possible events are equiprobable):

$H_n(p_1,\ldots,p_n) \le H_n\left(\frac{1}{n}, \ldots, \frac{1}{n}\right)$

For equiprobable events the entropy should increase with the number of outcomes:

$H_n\bigg(\underbrace{\frac{1}{n}, \ldots, \frac{1}{n}}_{n}\bigg) < H_{n+1}\bigg(\underbrace{\frac{1}{n+1}, \ldots, \frac{1}{n+1}}_{n+1}\bigg).$

The amount of entropy should be independent of how the process is regarded as being divided into parts.

This last functional relationship characterizes the entropy of a system with sub-systems. It demands that the entropy of a system can be calculated from the entropy of its sub-systems if we know how the sub-systems interact with each other.

Given an ensemble of n uniformly distributed elements which are arbitrarily divided into $k$ boxes (sub-systems) with $b_1, b_2, \ldots, b_k$ elements respectively, the entropy of the whole ensemble should be equal to the sum of the entropy of the system of boxes and the individual entropies of the boxes, each weighted with the probability of finding oneself in that particular box.

For positive integers $b i$ where $b_1 + \ldots + b_k = n$ ,

$H_n\left(\frac{1}{n}, \ldots, \frac{1}{n}\right) = H_k\left(\frac{b_1}{n}, \ldots, \frac{b_k}{n}\right) + \sum_{i=1}^k \frac{b_i}{n} \, H_{b_i}\left(\frac{1}{b_i}, \ldots, \frac{1}{b_i}\right).$

Choosing the sub-ensembles to be of equal size, i.e. $b_1 = \ldots = b_k = l$ with $n = k \cdot l$ , the additivity assumption implies that the total entropy is given by the sum of the uncertainty of choosing one of the k boxes and the uncertainty of choosing a specific event within the chosen box:

$H_n\left(\frac{1}{n}, \ldots, \frac{1}{n}\right) = H_k\left(\frac{1}{k}, \ldots, \frac{1}{k}\right) + H_{l}\left(\frac{1}{l}, \ldots, \frac{1}{l}\right).$