title: Elementary proof that Bool is a Set

text:
# Question
Title: Elementary proof that Bool is a Set
The type `Bool`, as in the datatype with just two point constructors `true false : Bool` and no higher-dimensional constructors, has decidable equality which is easy to prove directly, e.g. via a type family that maps `true` to `Unit` and `false` to `Void`. Then we can apply Hedberg's theorem to show that `Bool` is a Set.

**What is a direct, elementary proof of `IsSet Bool` that doesn't go via Hedberg's theorem?**

# Answer
Here is the encode-decode method that L. Garde suggests (in cubical Agda):

```
{-# OPTIONS --cubical --safe --postfix-projections #-}

module Hmm where

open import Cubical.Core.Everything

open import Cubical.Foundations.Prelude
open import Cubical.Foundations.Isomorphism

open import Cubical.Data.Empty
open import Cubical.Data.Unit

data ℕ₂ : Type₀ where
  0₂ 1₂ : ℕ₂

Code : ℕ₂ → ℕ₂ → Type₀
Code 0₂ 0₂ = Unit
Code 1₂ 1₂ = Unit
Code m  n  = ⊥

Crefl : ∀{m} → Code m m
Crefl {0₂} = tt
Crefl {1₂} = tt

decode : ∀ m n → Code m n → m ≡ n
decode 0₂ 0₂ c = refl
decode 1₂ 1₂ c = refl

encode : ∀ m n → m ≡ n → Code m n
encode m n p = transport (λ i → Code m (p i)) Crefl

decode-encode : ∀ m n p → decode m n (encode m n p) ≡ p
decode-encode m n p
  = J (λ z q → decode m z (encode m z q) ≡ q) (lemma m) p
  where
  lemma : ∀ m → decode m m (encode m m refl) ≡ refl
  lemma 0₂ = refl
  lemma 1₂ = refl

encode-decode : ∀ m n c → encode m n (decode m n c) ≡ c
encode-decode 0₂ 0₂ c = refl
encode-decode 1₂ 1₂ c = refl

Cprop : ∀ m n → isProp (Code m n)
Cprop 0₂ 0₂ = isPropUnit
Cprop 1₂ 1₂ = isPropUnit

ℕ₂set : isSet ℕ₂
ℕ₂set m n = transport (λ i → isProp (p i)) (Cprop m n)
  where
  p : Code m n ≡ (m ≡ n)
  p = isoToPath (iso (decode m n) (encode m n)
                   (decode-encode m n) (encode-decode m n))

```
> 1 votes

---
Tags: homotopy-type-theory
---


# Question
Title: Whether the given language is a CFL or not?
Let $L$ be a language defined over $\Sigma = \left \\{ a, b \right \\}$ such that $L = \left \\{ x\\#y \mid x,y \in \Sigma^\*, \\# \text { is a constant and } x \neq y \right \\}$ State whether the language L is a CFL or not? Give valid reasons for the same.

---

Now, I think that the given language is not a CFL. I have used the pumping lemma test for showing that L is not CFL. Specifically, I have done the following-

Consider a string $w = abb\\#aab$. Obviously, $w \in L$.

Let, $u = \epsilon \\ v = a \\ w = bb\\#aa \\ x = b \\ y = \epsilon$

Here, $|vx| \geq 1$

But, $uv^2wx^2y = aabb\\#aabb \notin L$ Therefore, pumping lemma test result is negative. Therefore, we can conclude that the given language is not a CFL.

Now, I have a doubt regarding the above method- I know that given a CFL, if we want to perform the pumping lemma test for the CFL, we must always use strings which are of length greater than or equal to the minimum pumping length. In fact, this also confirms to the condition that the length of the string $w$ used for the pumping lemma test (denoted by $|w|$) must be greater than or equal to n.

Therefore, when I use $w = abb\\#aab$ for doing the pumping lemma test, I implicitly make the assumption that 7 is greater than or equal to the minimum pumping length (if $L$ were to be a CFL). ***Am I correct or incorrect in doing so?***

# Answer
> 0 votes
The language is context-free.

The statemant of the pumping lemma claims "there exists a $uvwxy$-division", so in order to show a language non-context-free, you have to check that *every* possible division leads to a pumping contradiction. Your mistake is that you only checked one division.

---
Tags: context-free, pumping-lemma
---


# Question
Title: Analysis of a LALR shift-reduce conflict
I have created an extremely simple byacc grammar (ok, it's not really that simple but I simplified purposefully to be a minimal complete verifiable example):

```
%token NEWLINE SPECIFIER
%token EQUALS STRING VAR

%start st

%%

st: toplevel;

toplevel:
| toplevel VAR EQUALS STRING NEWLINE
| toplevel list NEWLINE
;

list:
  maybe_specifier VAR
| list maybe_specifier VAR
;

maybe_specifier:
| SPECIFIER
;

```

However, it is warning about a shift-reduce conflict. If I remove `maybe_specifier` from the grammar entirely (so that variables cannot be prefixed by a specifier in a list), the conflict disappears. Similarly, if I remove the variable assignment from the grammar entirely, the conflict disappears too.

My questions are:

* Where does this shift-reduce conflict come from? Is it an artifact of LALR? Or would it be there even with an LR(1) parser generator?
* Does this shift-reduce conflict matter? Or is it always doing the right thing anyway by using shift instead of reduce?
* Is there any way to modify the grammar to accept the same language without having the shift-reduce conflict, other than by prefixing `VAR` in assignment line by `maybe_specifier` and then checking whether the `SPECIFIER` was there in a semantic action, and failing if the `SPECIFIER` was present?

My current approach is to modify the assignment rule to initially accept a `SPECIFIER` in the form of `maybe_specifier` but then terminate with a parse error if the `SPECIFIER` was there. I'm wondering if there's a cleaner approach that would allow me to do the same without adding a semantic action.

# Answer
> 1 votes
This conflict arises because when the parser is at the beginning of a line and the lookahead is `VAR`, it can't tell whether or not to reduce an empty `maybe_specifier`. In this simple grammar, that decision could be resolved with one more lookahead token, making the grammar LR(2), but that might not be true in the original unsimplified version.

So the conflict is not an artefact of the LALR algorithm, and it is important to fix. (The yacc default resolution "choise shift over reduce" will make it impossible to parse `list`s which don't start with a `SPECIFIER`.)

A simple fix is to defer the parsing decision for the first entry in a `list`:

```
list:
  VAR
| SPECIFIER VAR
| list maybe_specifier VAR
;

```

Again, that might or might not be useful in the context of your full grammar.

---
Tags: parsers, lr-k
---


title: Help with Big-O homework

text:
# Question
Title: Help with Big-O homework
"er" is the Danish equivalent of "is" in English. I need some help with the square root one. Additionally, it would be nice to know if the other ones are correct.

# Answer
> 0 votes
You can use this fact that $\log(n) = O(n^k)$ for any constant $k \> 0$ and $k \in \mathbb{R}$. $k$ in your case is $\frac{1}{2}$. Hence, $\sqrt{n}$ **is not** $O(2\log(n))$.

---
Tags: asymptotics, big-o-notation
---


title: Asymptotic Relationship from Limit

text:
# Question
Title: Asymptotic Relationship from Limit
F(n) = n-100 G(n) = n-200

I am trying to show the asymptotic relationship between these two functions using limits.

I take the limit n-\>∞ f(n) / g(n) and I get the result 1 which is constant c.

**From the Big O theorem,**

**From the Big Omege theorem,**

My question is: How I supposed to determine whether they are **f = O(g(n)) or f = Ω(g(n))**

In general, what is a good way to find the relationship between given two functions?

# Answer
The theorems you quote are unfortunately wrong. As an example, $2 + \sin n = \Theta(1)$ although the limit $\lim\_{n\to\infty} \frac{2+\sin n}{1}$ doesn't exist.

Here are some theorems which do hold.

**Theorem 1.** Let $f,g$ be two functions such that $f(n),g(n)$ are eventually positive. If the limit $c := \lim\_{n\to\infty} f(n)/g(n)$ exists then

1. $f(n) = O(g(n))$ iff $0 \leq c \< \infty$.
2. $f(n) = \Omega(g(n))$ iff $0 \< c \leq \infty$.
3. $f(n) = \Theta(g(n))$ iff $0 \< c \< \infty$.
4. $f(n) = o(g(n))$ iff $c = 0$.
5. $f(n) = \omega(g(n))$ iff $c = \infty$.

**Theorem 2.** If $f,g$ are two polynomials which are eventually positive, then the limit $\lim\_{n\to\infty} f(n)/g(n)$ exists.

**Theorem 3.** Let $f,g$ be two functions such that $f(n),g(n)$ are eventually positive. Then

1. $f(n) = O(g(n))$ iff $\lim\sup\_{n\to\infty} \frac{f(n)}{g(n)} \< \infty$.
2. $f(n) = \Omega(g(n))$ iff $\lim\inf\_{n\to\infty} \frac{f(n)}{g(n)} \> 0$.
3. $f(n) = o(g(n))$ iff $\lim\_{n\to\infty} \frac{f(n)}{g(n)} = 0$.
4. $f(n) = \omega(g(n))$ iff $\lim\_{n\to\infty} \frac{f(n)}{g(n)} = \infty$.
> 2 votes

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Need help regarding random password generator: Urgent
I had generated a random password from a website which unfortunately has put me into trouble.

The password contains 26 characters which includes alphabets, numbers and special characters. My trouble started when it was found that among the 26 characters there was a 4 letter Malayalam word (spelled in English) which is interpreted to be abusive, followed by an exclamation mark and then again followed by 3 alphabets which unfortunately consists of the initials of the person to whom I had sent the password.

How can I make others believe that this can be auto generated using a random password/string generator algorithm?

I request those people who are acquainted with such algorithms to please help me in this regard. Those who can help me may please reply at the earliest.

# Answer
> 2 votes
There's really no way to do this. First, the website generating the password would need to be open source, or at least publish what algorithm they use. Supposing they do that, then we would need to know the "inputs" to the algorithm. That would depend on their source of randomness: it might be the microsecond that your query was submitted, or it might be random mouse movements, or it might be random atmospheric data. It's also possible that the website uses some "secret salt" in addition to the randomness source, so that their results can't be replicated from the randomness alone.

Really, we have two situations. Either the password can't be recovered/explained, because the website is using proper security to make sure that your password is secret. Or, you can fully recreate the inputs to the algorithm, in which case someone else could, meaning that your password isn't very secure.

There is a third possibility, which is that this website isn't legitimate, and it's deliberately returning things with Malay profanity. I'd try generating another password to see. But in all likelihood you're just terribly unlucky.

---
Tags: algorithms, randomness
---


# Question
Title: Do determinacy of one-step evaluation and uniqueness of normal forms apply to all (or most) languages in TAPL?
In *Types and Programming Languages* by Pierce, when talking about untyped arithmetic expressions in Chapter 3, there are two theorems:

$-→$ is single-step evaluation relation:

> 3.5.4 Theorem \[Determinacy of one-step evaluation\]: If $t -→ t'$ and $t -→ t''$ , then $t' = t''$ .

$-→ ∗$ is multi-step evaluation relation:

> 3.5.11 Theorem \[Uniqueness of normal forms\]: If $t -→ ∗ u$ and $t -→ ∗ u'$ , where $u$ and $u'$ are both normal forms, then $u = u'$.

Do the two theorems also apply to all (or most) the other languages/systems in the book, or only to the untyped arithmetic expressions?

From my limited experiences in a few programming languages, it seems that an expression is always evaluated in exactly one deterministic process, so I wonder if both theorems apply to all the languages.

Thanks.

# Answer
> 1 votes
1. Uniqueness of normal forms definitely applies. This is still a theorem you have to prove, but if it doesn't hold, what you have isn't really a normal form. The whole point of normal forms is that there's a unique form for each value, that's what makes it "normal".
2. For determinancy, I think it holds for most languages in the book. Usually when you're defining a small step semantics, you try to do it in such a way that it's deterministic. However, there are notable exceptions to this. First, if you have a general rewrite system, like the untyped lambda calculus, then it's totally valid to have non deterministic reductions. This is what lets us talk about Church Rosser and the diamond property. Secondly, if you have a language with any sort of concurrency, then you probably want to have non deterministic rules, to model the different possible orders of evaluation, so that you can show your language is well behaved regardless of which interleaving is taken.

That said, I want to be clear that these things do not come for free. They hold for the Languages in the book because Pierce has been very careful to ensure they hold. It is easy to accidentally definite a language where these do not hold.

---
Tags: programming-languages, type-theory, types-and-programming-languages
---


# Question
Title: Does a term being normalizable mean the same as the term has a normal form?
From Types and Programming Languages by Pierce

> A term $t$ is in normal form if no evaluation rule applies to it— i.e., if there is no $t'$ such that $t -→ t'$.

and

> A term $t$ is typable (or well typed) if there is some $T$ such that $t : T$.

In the pure simple typed lambda calculus:

> we consider another fundamental theoretical property of the pure simply typed lambda-calculus: the fact that the evaluation of a well- typed program is guaranteed to halt in a ﬁnite number of steps—i.e., every well-typed term is normalizable.

Does a term being normalizable mean the same as the term has a normal form?

Here is a term which has no normal form in the untyped lambda calculus:

> Recall that a term that cannot take a step under the evaluation relation is called a normal form. Interestingly, some terms cannot be evaluated to a nor- mal form. For example, the divergent combinator
>
> $$omega = (λx. x x) (λx. x x);$$
>
> contains just one redex, and reducing this redex yields exactly omega again! Terms with no normal form are said to diverge.

In the pure simple typed lambda calculus,

* is $omega$ typable (i.e. well-typed)?
* is $omega$ normalizable?
* does $omega$ have a normal form?

# Answer
> 1 votes
Yes, a term is normalizable if, and only if, it has a normal form.

It is well known that $\omega = (\lambda x . x x) (\lambda x . x x)$ is not typeable, nor is it normalizable. It is not normalizable because it has an evaluation step ($\beta$-reduction) which evaluates it to itself, so we get $\omega \mapsto \omega \mapsto \omega \cdots$.

To see that it is not typeable, observe that already its subexpression $\lambda x . x x$ is not typeable. For if $x$ has type $T$ then in order for $x x$ to have a type, $T$ must be of the form $T \equiv T \to S$ (because $x$ is applied to something, therefore by the typing rules it must have a function type). But there is no type $T$ such that $T \equiv T \to S$, because the type on the right-hand side is larger (as a syntactic expression) than the type on the left-hand side.

---
Tags: programming-languages, type-theory, types-and-programming-languages
---


# Question
Title: Do the following concepts belong to syntax or semantics?
I am not very sure about the difference between syntax and semantics.

Does each of the following concepts belong to syntax or semantics?

* terms
* values: terms that are possible ﬁnal results of evaluation.
* types
* (typing) context
* evaluation (rules)
* typing (relation)?

Here are two examples from *Types and Programming Languages* by Pierce.

For example, I thought evaluation (rules) belongs to operational semantics, so values should also belong to operational semantics, by the definition of values. Why does the book list "values" under "Syntax"?

# Answer
> 3 votes
It's not really a good idea to try to divide everything in PL into "syntax" and "semantics". Often we mix things. Nevertheless, as for your question, we normally divide things up like this:

* terms, values and types are syntactic entities, as each of them is described by grammatical rules, so these are syntax
* a typing context is syntax in simple cases, when we can describe contexts using grammatical rules
* the typing relation is considered to be part of *static semantics*, i.e., the typing relation is determined by the structure of the terms (as opposed to their operational behavior),
* the evaluation relation is part of *dynamic semantics*, i.e., the evaluation rules explain the operational (dynamic) behavior of terms.

You did not mention *denotational semantics*, which gives *mathematical* meaning to terms and types. It is considered to be a separate thing of its own.

---
Tags: programming-languages, type-theory, semantics, syntax, types-and-programming-languages
---


title: Why an error probability of 1/3 in BPP?

text:
# Question
Title: Why an error probability of 1/3 in BPP?
BPP is defined as the class of polynomial-time random algorithms which have an error probability of at most 1/3.

But why was 1/3 chosen? If we have an algorithm with some error probability less than 1/2, then we can run it several times, taking the most common result, to obtain an error probability of less than 1/3 while still staying in the same complexity class.

So why isn't BPP instead defined as the algorithms which have an error probability of less than 1/2? Is there something special about 1/3?

# Answer
> 1 votes
The constant $1/3$ is completely arbitrary. Let's say that $\mathsf{BPP}\_p$ is the class of problems solvable in polytime with error at most $p$. Then $\mathsf{BPP}\_p = \mathsf{BPP}\_q$ for any $0 \< p,q \< 1/2$. The simple proof can be found in any decent textbook or lectures notes on complexity theory, and is also a nice exercise. The idea is that you can boost the success probability by running the algorithm several times and take a majority vote (details left to you).

Why do we like $1/3$, then? It's the "simplest" rational number in $(0,1/2)$: for example, it is the rational number in $(0,1/2)$ with the minimal possible denominator, and with the minimal sum of numerator and denominator.

---
Tags: probabilistic-algorithms
---


# Question
Title: Approximately counting the number of marked elements in a list of n numbers
Assume that we have n sealed boxes. There are k boxes with a ball inside. The goal is to approximate k by an additive error epsilon, using the minimum number of box probing. I know that this is possible using O(n/k. 1/epsilon^2) box probing but I don't know the algorithm and its analysis.

# Answer
You calculate the average number of balls in a box (k / n), and the variance. From this you calculate the estimated number of balls and the variance when probing m random boxes. Convert variance to standard deviation. The number of balls will be normal distributed, and there is a simple formula for diverging by more than k standard deviations.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Is the graph symbol used in dask a general notation?
Dask is a flexible library for parallel computing in Python.

This piece of code define some simple functions.

```
def inc(x):
    return x + 1

def double(x):
    return x + 2

def add(x, y):
    return x + y

data = [1, 2, 3, 4, 5]

output = []
for x in data:
    a = inc(x)
    b = double(x)
    c = add(a, b)
    output.append(c)

total = sum(output)

```

this piece of code wraps the functions above, and defer their execution.

```
x = dask.delayed(inc)(1)
y = dask.delayed(inc)(2)
z = dask.delayed(add)(x, y)
z.visualize()

```

and this task graph

# question

is the symbol here a general graph notation? is this a kind of graph language, like UML for visualizing the design of a system, used to visualize the computation task?

# Answer
It's... a visualization. Don't read too much into it. Graphs in computer science are formalized, but unless specifically mentioned a visualization of a graph doesn't have a formal underpinning. They're generally self-explanatory, there are objects (nodes) and arrows (edges).

UML is more of the exception than the rule, being a graphical language with a formal interpretation. Most visualizations in computer science aren't that strict in meaning.

Here it seems that the round nodes are functions, the square nodes are (temporary) variables, and the arrows indicate data flow.
> 4 votes

---
Tags: graphs, computation-models
---


# Question
Title: Simple generator of pseudo-random permutations of variable length short sequence
The problem in front of me is to write a function (from scratch) to permute n elements, where n is an argument. I decided to break it down to applying Knuth's shuffles algorithm, therefore I needed to write a pseudorandom number generator.

So now my task is to write a simple function `F(seed,n)` that will help me generate indices for the pseudorandom permutations of n elements. However, the function has to be extremely simple: My constraint is that I can only use the following operators: +,-,\*,/,%, specifically, no address access, binary encoding, bits selection etc. - only arithmetic on numbers. That is fine, I went for linear congruental generators and implemented a `(a*x+c)%m` procedure.

As I started testing `F(seed,2)` it immediately went apparent that the results oscilate between zero and one with a period of two.

My problem is: how can I adjust `F` to avoid that behavior? Maybe I should generate the n-permutations in a different manner?

In practice, I am only interested in n=\<32

# Answer
The low bits of a linear congruential generator are notoriously weak. Try to use only the higher order bits. Normally this is done by bit operations, but you can discard the bottom $b$ bits by dividing by $2^b$ and rounding down.
> 3 votes

---
Tags: randomness, number-theory, pseudo-random-generators, modular-arithmetic, random-number-generator
---


title: Find pair with maximum Appeal value

text:
# Question
Title: Find pair with maximum Appeal value
**Find pair with maximum Appeal value.**

* Input: Array
* Output: index {i, j} ( i = j allowed) with maximum Appeal
* Appeal = A\[i\] +A\[j\] + abs(i-j)

**Example 1:**

* Input: \[1, 3, -1\]
* Output: \[1, 1\]
* Explanation: Appeal = A\[1\] + A\[1\] + abs(0) = 3 + 3 + 0 = 6

**Example 2:**

* Input: \[1, 6, 1, 1, 1, 1, 7\]
* Output: \[1, 6\]
* Explanation 6 + 7 + abs(1 - 6) = 18

**Example 3:**

* Input: \[6, 2, 7, 4, 4, 1, 6\]
* Output: \[0, 6\]
* Explanation: 6 + 6 + abs(0 - 6) = 18

I'm not sure how to approach this problem. I've tried the 2 pointer approach as below and it seems to work for some cases but I'm missing some fundamental intuition about it.

```
public static int[] maximumAppeal(int[] A) {
    int left = 0;
    int right = A.length - 1;
    int max = 0;
    int[] r = {-1,-1};
    while (left <= right) {
        int sum = A[left] + A[right] + Math.abs(left - right);
        if (A[left] <= A[right]) {
            if (sum > max) {
                max =sum;
                r[0] = left;
                r[1] = right;
            }
            left++;
        } else {
            if (sum > max) {
                max = sum;
                r[0] = left;
                r[1] = right;
            }
            right--;
        }
    }
    return r;
}

```

Edited: Here's the link, its an Amazon question https://leetcode.com/discuss/interview-question/355698

# Answer
Let $B\[i\] = A\[i\] + i$ and let $C\[j\] = A\[j\] - j$. You are looking for $$ \max\_{i \geq j} B\[i\] + C\[j\] = \max\_j (C\[j\] + \max\_{i \geq j} B\[i\]). $$

This gives a linear time in-place algorithm for your problem:

* maxB = A\[n\] + n
* maxSum = A\[n\] - n + maxB
* for j=n-1 downto 1:
    1. maxB = max(maxB, A\[j\] + j)
    2. candidate = A\[j\] - j + maxB
    3. maxSum = max(candidate, maxSum)
* return maxSum
> 1 votes

---
Tags: arrays
---


# Question
Title: Wrapping the complexities of alternative algorithms: What is the proper "term" for it?
Suppose that we have two algorithms for the same task (e.g. search):

* AlgC: has bounded worst-case complexity, e.g. O(n.logn)
* AlgH: is a heuristic algorithm that is experimentally faster than AlgC, but there is no tight complexity bound for AlgH.

If we want to have an algorithm that is **FAST** but also has a guaranteed **computational complexity**, we can use some simple tricks. For example:

* We can run AlgC and AlgH simultaneously in an interleaved fashion (or in parallel), and once any of them finishes the task, we stop the other one. This ensures that AlgC binds the complexity, while the execution is as fast as AlgH.
* We can also run AlgH for a limited time (e.g. a factor of $n.\log n$) and if it hasn't finished, we run AlgC.

**What are such techniques called in Algorithm's community?** There should be a proper term for that, right?

# Answer
> 1 votes
Hybrid algorithms.

In sorting algorithms it's rather common, Start with quicksort and if the size of the array is small enough switch to insertion sort (much faster for small $n$). Additionally when the recursion depth becomes too large (threatens to become $O(n^2)$) fall back to heapsort (guaranteed $O(n\log n)$).

---
Tags: algorithms, complexity-theory, time-complexity, real-time
---


# Question
Title: Minimal hitting set with respect to set inclusion from a book "Parameterized Complexity Theory"
In the first chapter of "Parameterized Complexity Theory" by Flum and Grohe, an example is presented to find a hitting set of minimal cardinality.

In Fig. 1.3, the author says a black colored leaf is the minimal with respect to set inclusion and a hitting set consists of the vertices labeling the edges on the path from the root to the leaf. However, both grey and black colored hitting set consists of 3 vertices. Why grey colored leaf is not minimal in this case?

Related question: Given a set of sets, find the smallest set(s) containing at least one element from each set

# Answer
> 3 votes
It seems you are confusing the terms minimal and minimum. The Hitting set problem is to find a hitting set of *minimum* cardinality, not a minimal set.

A set $S$ is called *minimal* with respect to some property (in this case, being a hitting set) if there exists no strict subset $T$ of $S$ (i.e. $T\subsetneq S$) that also satisfies that property.

On the other hand, a set $S$ is said to have *minimum* size or cardinality with respect to some property if there exists no set $T$ of strictly smaller size (i.e. $|T|\< |S|$) that also satisfies this property.

A minimum size set must be minimal (why?), but a minimal set need not be of minimum size (why?).

In the example in the book, the set $\\{b,c,d\\}$ is not a minimal hitting set, because its strict subset $\\{c,d\\}$ is also a hitting set. The subset $\\{b,d,f\\}$ is a minimal hitting set, because it has no strict subset that is a hitting set. It is not a minimum hitting set, because there is a hitting set of size $2$ ($\\{c,d\\}$).

---
Tags: algorithms, graphs, optimization, np-hard, set-cover
---


title: Is $A$ regular if $A^{2}$ is regular?

text:
# Question
Title: Is $A$ regular if $A^{2}$ is regular?
If $A^2$ is regular, does it follow that $A$ is regular?

My attempt on a proof:

> Yes, for contradiction assume that $A$ is not regular. Then $A^2 = A \cdot A$.
>
> Since concatenation of two non-regular language is not regular $A^2$ cannot be regular. This contradicts our assumption. So $A$ is regular. So if $A^2$ is regular then $A$ is regular.

Is the proof correct?

Can we generalize this to $A^3$, $A^4$, etc...? And also if $A^\*$ is regular then $A$ need not be regular?

Example: $A=\lbrace 1^{2^i} \mid i \geq 0\rbrace$ is not regular but $A^\*$ is regular.

# Answer
Consider Lagrange's four square theorem. It states that if $B = \\{1^{n^2}| n \geq 0\\}$ then $B^4 = \\{1^n | n \geq 0\\}$. If $B^2$ is regular, take $A = B$ else take $A = B^2$. Either way, this proves the existence of irregular $A$ such that $A^2$ is regular.
> 28 votes

# Answer
Here is an example of a non-computable language $A$ such that $A^2 = \Sigma^\*$. Take any non-computable $K$ (represented as a set of numbers, e.g. the codes of Turing machines that halt), and define $$ A = \\{ w \in \Sigma^\* : |w| \neq 4^k \text{ for all } k \in K \\}. $$ So $A$ contains all words other than ones of length $4^k$ for some $k \in K$. If $A$ were computable then you could compute $K$: given $k$, determine whether $0^{4^k}$ (that is, $4^k$ zeroes) is in $A$ or not. Since we assumed $K$ is not computable, $A$ must also be non-computable.

Claim: $A^2 = \Sigma^\*$. Let $w$ be any word of length $n$. If $n$ is not a power of $4$, then $w \in A$ and the empty word is in $A$, so $w \in A^2$. If $n$ is a power of $4$ then $n/2$ is not a power of $4$. Write $w = xy$, where $|x| = |y| = n/2$. Both $x,y \in A$ so $w = xy \in A^2$.
> 8 votes

# Answer
Your proof still makes a huge jump (arguing that concatenation of non-regular languages is non-regular).

If the Goldbach conjecture is true, then the answer to the question is no: Consider the non-regular language $A=\\{1^p: p\text{ is a prime}\\}$. Then by the Goldbach conjecture, $A^2=\\{1^{2k}: k\>1\\}$, which is regular.

This doesn't solve the question entirely, but it gives strong evidence that the answer is no (otherwise the Goldbach conjecture is false). However, the answer may be very hard to prove, if this is the only known example.
> 2 votes

# Answer
The claim is wrong.

Let $D$ be non-regular language which is "sparse": if $x \in D$ then any other $y\in D$ satisfies $|y| \> 4|x|$ (or $|x|\>4|y|$)$\dagger$. It's not too difficult to see that many non-regular languages can be sparse.

Now define $A = \Sigma^\* \setminus D$. From closure properties (complementation), $A$ must be non-regular.

However, $A^2 = \Sigma^\*$ $\ \ \ $ (can you see why?)

$\dagger$ I think $|y|\>2|x|$ is enough, but may cause some nasty edge cases. $|y|\>2|x|+2$ should be enough though, so let's take $|y|\>4|x|$ to be on the safe side.
> 2 votes

# Answer
Take any nonregular $X \subseteq {1}^\ast$ and define $A=\\{1\\} \cup \\{1^{2x}:x \in \mathbb N\\} \cup \\{1^{2x+1}:1^x \in X\\}$.

It is easy to see $A$ is nonregular, while $A^2=1^{\ast}$.
> 2 votes

# Answer
Let $U\subseteq \mathbb{N}$ be any undecidable set, let $I = \\{2u+1\mid u\in U\\}\cup\\{0,2,4,\dots\\}$ and let $L = \\{a^i\mid i\in I\\}$. $L$ is undecidable so it certainly isn't regular. But $L^2 = \\{a^{2n}\mid n\in \mathbb{N}\\} \cup \\{a^n\mid n\geq \min\\,I\\}$, which is regular because its complement is finite.
> 2 votes

# Answer
Another example, from a question that was marked as a duplicate of this, is to consider the non-regular language $\\{a^k\mid m\text{ is composite}\\}$. Any even number $n\geq 8$ is the sum of $n-4$ and $4$, which are both composite; any odd number $n\geq 13$ is the sum of $n-9$ and $9$, which are both composite ($n-9=2m$ for some $m\geq 2$). Therefore, $A^2 = \\{a^8,a^{10}\\}\cup\\{a^k\mid k\geq 12\\}$, which is regular because it's co-finite (it's the complement of $\\{\epsilon,a,aa,\dots,a^6,a^7,a^9,a^{11}\\}$).
> 0 votes

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: Red-Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root
I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest, et al.), and have been studying the deletion algorithm for red-black trees. However, I am confounded at the moment while I am trying to delete a node from the tree.

The algorithm could be found at Page No. 324, third edition, Introduction to Algorithms,(CLRS).

Suppose I have a red-black tree as follows:

This RB TRee was constructed by inserting the number 1 to 7 in non-decreasing order (i.e. 1,2,3,4,5,6,7).

Suppose we wish to delete the root of the tree, node 2.

Then as per the delete algorithm, on page-324,

```
1. y = z (i.e. y = ROOT of the tree)
2. y-original-color = BLACK
3. z.left exists, skip lines 4-5
6. z.right exists, skip lines 7-8
9. Now y = tree-minimum(z-right), i.e. y is a pointer to 3
10. y-original color = BLACK
11. x = y.right (i.e. T.NIL only)
12. y's parent = pointer to 4, which is not z (i.e. ROOT), skip line 13
14. Else transplant y with y.right, i.e. left of '4' is T.NIL now
15. Lines 15-16 fix the new parent issue for the transplanting node
17. Line 17 transplants z (i.e. the ROOT) with the pointer y, i.e. 3 is the root now
18. Lines 18-21 fix the parent and left child issue for the new ROOT
21. as y-original-color is BLACK, call the RB-DELETE-FIXUP function for x

```

As x is T.NIL, this is passed as an argument for the RB-DELETE-FIXUP function. However, there is an issue.

1. How can we claim the parent of this x, i.e. the T.NIL, for the purpose of finding its sibling?
2. Even if we claim that 4 be the parent of this x, and 6 be the sibling (as per the diagram), then the deletion falls under none of the categories mentioned in the book since 6 is a BLACK parent and both of its children are RED.

I have been following the algorithm and have been quite confounded by this case. Maybe there is a misinterpretation on my end regarding following the algorithm. Any help in this regard would be appreciated.

# Answer
> 1 votes
This is case 4, because w's right child is red. the left child (of z) could have any color red/black.

---
Tags: trees, binary-trees, balanced-search-trees, red-black-trees
---


# Question
Title: Why are struct and class essentially the same in C++?
`struct` and `class` in C++ are nearly identical (as covered for example here).

But why is this so? What did happen when C++ was developed and eventually standardized, that `struct` was allowed to define a full OOP class, yet `class` keyword was *also* added? There must be a historical reason for this, but I did not find an answer by searching.

In contrast, for example C# uses these keywords too, but there they have different and distinct meaning. I would say this is quite a valuable feature in that language.

In hindsight, it would have for example made sense to keep C++ `struct` be always compatible with similar C `struct` in memory layout, and only those class features that are compatible with that would have been supported (so no "virtual" stuff, value always copyable by `memcpy`, maybe even some kind of C interoperability for `struct` methods). Or something else perhaps; point is, the distinction could have meant something and added to the language, instead of being a (small) source of confusion it is now.

So I am looking for some historical record, quote or story, which would explain this.

# Answer
Bjarne Stroustrup writes in his The Design and Evolution of C++ book (item 3.5.1):

> At this point, the object model becomes real in the sense that an object is more than the simple aggregation of the data members of a class. An object of a C++ class with a virtual function is a fundamentally different beast from a simple C `struct`. Then why did I not at this point choose to make structs and classes different notions?
>
> My intent was to have a single concept: a single set of layout rules, a single set of lookup rules, a single set of resolution rules, etc. Maybe we could have lived with two sets of rules, but a single concept provides a smoother integration of features and simpler implementations. I was convinced that if `struct` came to mean "C and compatibility" to users and `class` to mean "C++ and advanced features" the community would fall into two distinct camps that would soon stop communicating. Being able to use as many or as few language features as needed when designing a class was an important idea to me. Only a single concept would support my ideas of a smooth and gradual transition from "traditional C-style programming," through data abstraction, to object-oriented programming. Only a single concept would support the notion of "you only pay for what you use" ideal.
>
> In retrospect, I think these notions have been very important for C++'s success as a practical tool. Over the years, just about everybody has had some kind of expensive idea that could be implemented "for classes only," leaving low overhead and low features to `struct`s. I think the idea of keeping `struct` and `class` the same concept saved us from classes supporting an expensive, diverse, and rather different set of features than we have now. In other words, the "a `struct` is a `class`" notion is what has stopped C++ from drifting into becoming a much higher-level language with a disconnected low-level subset. Some would have preferred that to happen.
> 9 votes

---
Tags: history, language-design, c++
---


# Question
Title: How to propose a method to construct an automaton?
Given $0 \leq m \< k$ and $p \geq 2$ it's defined $$A\_{k,m,p} = \\{ \alpha \in \\{0,1,\dots,p-1\\}^\* | \alpha \text{ is a p-ary representation of } x \backepsilon x \text{ mod } k = m \\}$$

It is needed to give a general method to construct an automaton which accepts this language. I'm trutly lost about the procedure in this. Any hint would be helpful.

Some observations about this: The automaton is not specified (i.e. could be NFA or DFA) and the numbers are static.

# Answer
Your automaton will have $k$ states, one for each possible value of $m$, i.e., one for each of the congruence $(\text{mod } k)$ classes. Exactly one of these states will be marked as the final state, because that will be the one that accepts ocurrences of $\alpha$ that are compatible with $x ( \text{mod } k) =m$.

The transition function will connect states representing congruence classes for $m=a$ and $m=b$ by an arrow labeled with a symbol denoting $c$, if and only if $(a.p +c)\text{ mod } k = b$.

The initial state will be the one corresponding to $m = 0$, assuming leading zeros are allowed.
> 1 votes

---
Tags: formal-languages, automata
---


# Question
Title: Proof that complement of HAMPATH is not in NP
The Sipser book says, Complement of HAMPATH is not in NP.

I tried to find the solution for this, actually, a rigid proof like HAMPATH, which can state Complement of HAMPATH is in/not in NP, but I could not come up with any.

This is what I think, We are given a path from s to t(which can be a certificate for the problem, or not?), and check if it is not a HAMPATH. But this is easy, we can check this in P time right--Just list down the path, see that if any vertex is repeating in it, or if it is missing any vertex of the graph.

How come we are saying this problem is not in NP

I am very new to P and NP, Please correct my mistakes, and apologies if my question sounds like a silly one.

# Answer
The complement of HAMPATH is the following problem:

> Given an undirected graph, determine whether it *doesn't* contain a Hamiltonian path.

A YES instance for the complement of HAMPATH is a graph which doesn't contain a Hamiltonian path. It is not clear what a witness for this property would be. Contrast that with HAMPATH itself, in which the witness for having a Hamiltonian path is simply a Hamiltonian path.

---

It is not known whether the complement of HAMPATH is in NP, or equivalently, whether HAMPATH is in coNP.

However, it is considered unlikely that HAMPATH is in coNP, since this would imply that NP=coNP, which is considered unlikely by most researchers in the area.
> 4 votes

---
Tags: complexity-theory
---


# Question
Title: What Is the Complexity Class of Deciding Whether a Problem Is in NP? Is It Decidable?
Title says it all, but to clarify:

Define a problem, called $IsInNP$, as follows:

> Given a Turing Machine $M$ that always halts, $IsInNP$ is the problem of deciding if the problem that $M$ recognizes is in $NP$.

**What is the complexity class of $IsInNP$? Is it even decidable? Is the answer the same for any other complexity class, like $NP$-hard?** And are those questions even sensible to ask?

By the way, I am aware that the class $NP$ is not enumerable, but since I do not quite understand enumerability and it seems that recursively enumerable problems can be decidable, I do not know if that means that deciding whether a problem is in $NP$, or any other complexity class, is decidable.

Also, I am aware of Rice's Theorem, and I believe it can be interpreted as saying that deciding whether a problem is in $NP$ is undecidable, but I am not certain.

**Bonus question if the above questions are sensible**: given a property $S$ that only $NP$ problems possess, does the above also mean that deciding whether a problem decided by a Turing Machine $M\_2$ has property $S$ is in the same complexity class as $IsInNP$?

# Answer
> 4 votes
Here are several interpretations of your question:

> $L\_1$ consists of all descriptions of Turing machines which are deciders (always halt) and the language that they decide is in NP.

This is undecidable, by reduction from the halting problem. Given a Turing machine $T$, construct a new Turing machine $M$ which erased its input and transfers control to $T$. Then $\langle M \rangle \in L\_1$ iff $T$ halts on the empty input.

Indeed, if $T$ halts then $L(M) = \Sigma^\*$, while if $T$ doesn't halt, then $M$ is not a decider.

> $L\_2$ consists of all descriptions of Turing machines which are either not deciders, or the language that they decide is in NP.

This is undecidable, by reduction from the halting problem. Given a Turing machine $T$, construct a new Turing machine $M$ which simulates $T$ on the empty tape, and if $T$ halts, solves some NEXP-complete problem on the original input. Then $\langle M \rangle \in L\_2$ iff $T$ doesn't halt on the empty input.

Indeed, if $T$ halts on the empty input then $M$ decides an NEXP-complete problem, which by the nondeterministic time hierarchy theorem doesn't belong to NP. In contrast, if $T$ doesn't halt on the empty input, then $M$ is not a decider.

> $L\_3$ is the promise problem in which the input is a description of a Turing machine which is promised to be a decider, and the goal is to determine whether the language it decides is in NP.

Alternatively, you can ask whether there exists any decidable language $L\_4$ such that

1. The description of any machine deciding a language in NP belongs to $L\_4$.
2. The description of any machine deciding a language not in NP doesn't belong to $L\_4$.

This is undecidable, in the sense that there is no Turing machine that halts and answers YES on all YES instances, and halts and answers NO on all NO instances.

Given a Turing machine $T$, construct a new Turing machine $M$ with two inputs $n,x$. The Turing machine simulates $T$ for $n$ steps. If $T$ halts within these $n$ steps, then it solves some NEXP-complete problem on $x$. Otherwise, it simply returns YES. The new machine $M$ is a YES instance of $L\_3$ iff $T$ doesn't halt on the empty input.

Indeed, if $T$ halts on the empty input then there exists an NEXP-complete language $L$ and an integer $n$ such that $(n,x) \in L(M)$ iff $x \in L$, and so $L(M) \notin \mathsf{NP}$. In contrast, if $T$ doesn't halt on the empty input then $L(M)$ consists of all pairs $(n,x)$, and so $L(M) \in \mathsf{NP}$.

---
Tags: complexity-theory, computability
---


title: evaluating time complexity of a code

text:
# Question
Title: evaluating time complexity of a code
I'm trying to evaluate the time complexity of the following :

```
foo (n)
    if n ≤ 1
        return 1
    if n is odd
        for i=1 to n
            print i
        return foo(n-1) + 1
    if n is even
        i=n
        while i>2
            j=1
            while j<i
                j=j*2
            i=i/3
        return 2 * foo(n-1)

```

my attempt was to produce a recurrence relation broken into cases:

if $n \leq 1$ then :

$T(n)=\theta(1)$

if $n $ is odd then the for loop is executed $n$ times and we return a problem of size $n-1$ so :

$T(n)= T(n-1) + \theta(n)$

if $n$ is even then the inner while loop is executed $\theta(log\_6(n))$ times and the outer while loop is executed $O(log\_3(n)) $ times so totally that would be $O(log\_3(n))= O(log(n))$ , and we return a problem of size $n-1$ twice so:

$T(n) = 2T(n-1) + O(log(n))$

ultimately :

$T(n) = T(n-1)+n $ if $n$ is odd

$T(n) = 2T(n-1)+log(n) $ if $n$ is even

$T(n) = 1 $ if $n = 1$

since whenever $n$ is odd , $n-1 $ is even , $n-2 $ is odd and so on.. that had me confused. Any ideas of how to solve this?

# Answer
> 0 votes
Your recurrence is $$ T(n) = \begin{cases} T(n-1) + n & \text{if $n\>1$ is odd}, \\ 2T(n-1) + \log n & \text{if $n$ is even}, \\ 1 & \text{if $n=1$}. \end{cases} $$ We can convert it to a more amenable pair of recurrences. If $n \> 1$ is odd then $$ T(n) = T(n-1) + n = 2T(n-2) + n + \log(n-1). $$ If $n \> 2$ is even then $$ T(n) = 2T(n-1) + \log n = 2T(n-2) + 2(n-1) + \log n. $$ Finally, $$ T(2) = 2T(1) + \log 2 = 2 + \log 2. $$

We obtain the two recurrences $$ T(2m+1) = \begin{cases} 2T(2(m-1)+1) + (2m+1) + \log (2m) & \text{if $m \> 0$}, \\ 1 & \text{if $m = 0$}. \end{cases} \\ T(2m) = \begin{cases} 2T(2(m-1)) + 2(2m-1) + \log(2m) & \text{if $m \> 1$}, \\ 2 + \log 2 & \text{if $m = 1$}. \end{cases} $$ Both recurrences are of the form $S(m) = 2S(m-1) + \Theta(m)$. The simplest way of solving this is considering $R(m) = S(m)/2^m$, which satisfies the recurrence $R(m) = R(m-1) + \Theta(m/2^m)$. Since $\sum\_{m=0}^\infty m/2^m$ converges, we see that $R(m) = \Theta(1)$ and so $S(m) = \Theta(2^m)$. This implies that $T(2m+b) = \Theta(2^m)$ (for $b=0,1$), and so $T(n) = \Theta(2^{n/2})$.

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: Create automata from non regular grammar
I have two grammars:

```
 L → ε | aLcLc
 L → ε | aLcLc | LL

```

This two grammars are equals but the first one is regular, so it produces a regular language and a Finite State Automata. Instead, the second one is non regular but it might produces a regular language.
To prove it, I want to create two differentes automata: the first one should be a correct automata and if the second one can't be create then the language is not regular. Are all this statments correct?
If so, can someone help me build these two automata? Thank you!

# Answer
> 1 votes
Your first language isn't regular. Here is a simple way of showing this. Consider all words in your language of the form $a^\*c^\*$; if your language were regular, then so would be that language. However, the new language is generated by the grammar $L \to \epsilon \mid aLcc$ (this requires an argument), and so is $\\{a^n (cc)^n : n \geq 0\\}$, which is classically known to be irregular.

With more effort, you can show that your language consists of all words $w$ in which every proper prefix $x$ satisfies $\\#\_a(x) \> 2\\#\_c(x)$, and furthermore $\\#\_a(w) = 2\\#\_c(w)$.

An identical argument works for your second language. With more effort, you can show that the language consists of all words $w$ in which every prefix $x$ satisfies $\\#\_a(x) \geq 2\\#\_c(x)$, and furthermore $\\#\_a(w) = 2\\#\_c(w)$.

Summarizing, both of your languages are irregular, and this can be shown by intersecting them with $a^\*c^\*$.

---
Tags: automata, regular-languages, finite-automata, formal-grammars, regular-expressions
---


# Question
Title: Conversion from octal numerical system to binary numerical system
I know that in order to convert a numeral in base-8 to a numeral in base-2 I can write each octal digit as a binary word of 3 bits.

I know that 2^3 = 8 that is exactly the dimension of the base of the octal system.

I just cannot understand the fundamental reason why it works. Is it just a coincidence?

# Answer
Its not a coincidence. It is a general result for any number represented in a positive base $b$, its representation in base $b^k$ for some positive integer $k$, is simply grouping $k$ digits in its base $b$ representation starting from the least significant digit to the most significant digit.

Take base $10$ for example.

$427428$ in base $10$ is $(4,2,7,4,2,8)$.
$427428$ in base $10^2$ is $(42,74,28)$.
$427428$ in base $10^3$ is $(427,428)$.

You can now find an analogy to your problem.

**Edit:** Proof for the above claim

Let a number $n$ be represented in base $b$ positional system as

$n = (a\_{m-1},a\_{m-2},\space...\space,a\_1,a\_0)$ such that $0 \le a\_i \lt b \space \forall i\in\\{0,1,\space...\space,m-1\\}$

where $m$ represents the number of digits $n$ has in the base $b$ representation. We wish to represent $n$ in base $B = b^k$ for some positive integer $k$.

For the sake of simplicity of the argument, let $m$ be a multiple of $k$, i.e. $m = c k$ for some integer $c$. (If $m$ is not a multiple of $k$, the representation of $n$ in base $b$ can be prefixed by $0$'s untill the number of digits are a multiple of $k$)

From the representation in base $b$, we can write $n$ as follows

$n = a\_{m-1} b^{m-1} + a\_{m-2} b^{m-2} + \space ... \space + a\_2 b^2 + a\_1 b + a\_0$

$\space\space= a\_{ck-1} b^{ck-1} + a\_{ck-2} b^{ck-2} + \space ... \space + a\_2 b^2 + a\_1 b + a\_0$

$\space\space = a\_{ck-1}b^{ck-1} + a\_{ck-2}b^{ck-2} + \space ... \space + a\_{(c-1)k+1} b^{(c-1)k+1} + a\_{(c-1)k} b^{(c-1)k}$

$\space\space\space + a\_{(c-1)k-1}b^{(c-1)k-1} + a\_{(c-1)k-2}b^{(c-1)k-2} + \space ... \space + a\_{(c-2)k+1} b^{(c-2)k+1} + a\_{(c-2)k} b^{(c-2)k}$

$\space\space\space\vdots$

$\space\space\space + a\_{2k-1}b^{2k-1} + a\_{2k-2}b^{2k-2} + \space ... \space + a\_{k+1} b^{k+1} + a\_k b^k$

$\space\space\space + a\_{k-1}b^{k-1} + a\_{k-2}b^{k-2} + \space ... \space + a\_1 b + a\_0$

We can rearrange the last expression by taking out powers of $b^k$ from each sequence of $k$ terms as follows

$\space\space\space + \\{\space a\_{ck-1}b^{k-1} + a\_{ck-2}b^{k-2} + \space ... \space + a\_{(c-1)k+1} b + a\_{(c-1)k} \space\\}.b^{(c-1)k}$

$\space\space\space + \\{\space a\_{(c-1)k-1}b^{k-1} + a\_{(c-1)k-2}b^{k-2} + \space ... \space + a\_{(c-2)k+1} b + a\_{(c-2)k} \space\\}.b^{(c-2)k}$

$\space\space\space\vdots$

$\space\space\space + \\{\space a\_{2k-1}b^{k-1} + a\_{2k-2}b^{k-2} + \space ... \space + a\_{k+1} b + a\_k b \space\\} . b^k$

$\space\space\space + \\{\space a\_{k-1}b^{k-1} + a\_{k-2}b^{k-2} + \space ... \space + a\_1 b + a\_0 \space\\}$

$\space\space = p\_{c-1} B^{c-1} + p\_{c-2} B^{c-2} + \space ... \space + p\_1 B + p\_0$

Where, $p\_i = a\_{(i+1)k-1} b^{k-1} + a\_{(i+1)k-2} b^{k-2} \space ... \space + a\_{ik+1} b + a\_{ik} \space$ $\space\space\forall i \in \\{0,1,\space ...\space ,c-1\\}$

We can see that this is a representation of $n$ in base $B$ i.e. base $b^k$, with $c$ digits.

$n = (p\_{c-1},p\_{c-2},\space ... \space, p\_1,p\_0)$.

For the above to a valid representation in base $B$, $\forall i:\space0 \le p\_i \lt B$

We can verify this by finding the maximum value of any of the group of terms in the above expressions.

Since, $\forall i:\space 0 \le a\_i \lt b$, maximum value of $a\_i$ is $b-1$.

Now we get for any $i$,

$a\_{(i+1)k-1}b^{k-1} + a\_{(i+1)k-2}b^{k-2} + \space ... \space + a\_{i+1} b + a\_i$

$= (b-1)b^{k-1} + (b-1)b^{k-2} + \space ... \space + (b-1)b + b$

$= (b-1)(b^{k-1}+b^{k-2}+\space...\space+b+1)$

$= (b-1)\frac{b^k-1}{b-1}$

$= b^k - 1 $

which is strictly less than $b^k$ or $B$.

Hence, we prove the claim.
> 2 votes

---
Tags: binary, base-conversion, numeral-representations
---


title: Converting physical address to logical

text:
# Question
Title: Converting physical address to logical
In 8-bit address space there are 16 pages and the page table stores:

*68792EA51BD3CF04* (hex)

The physical address is *39h*, what is the corresponding logical address?

---

I have literally no idea what to do, tried to look on different sites and work with formulas but nothing seems to work. I don't think it was ever covered on the lectures but it might show up at the exam.

I'd appreciate any form of help, thank you and sorry for taking your time.

# Answer
You need to provide a linking **page table** which links the page number (logical address) to the frame number (physical address) and vice versa.
> 0 votes

---
Tags: operating-systems, memory-management, paging, memory-allocation
---


# Question
Title: Given a specific computer system, is it possible to estimate the actual precise run time of a piece of Assembly code
this is a piece of Assembly code

```
section .text
    global _start       ;must be declared for using gcc
_start:                     ;tell linker entry point
    mov edx, len    ;message length
    mov ecx, msg    ;message to write
    mov ebx, 1      ;file descriptor (stdout)
    mov eax, 4      ;system call number (sys_write)
    int 0x80        ;call kernel
    mov eax, 1      ;system call number (sys_exit)
    int 0x80        ;call kernel

section .data

msg db  'Hello, world!',0xa ;our dear string
len equ $ - msg         ;length of our dear string

```

Given a specific computer system, is it possible to predict precisely the actual run time of a piece of Assembly code.

# Answer
I can only quote from the manual of a rather primitive CPU, a 68020 processor from around 1986: "Calculating the exact runtime of a sequence of instructions is difficult, even if you have precise knowledge of the processor implementation". Which we don't have. And compared to a modern processor, that CPU was *primitive*.

I can't predict the runtime of that code, and neither can you. But you can't even *define* what "runtime" of a piece of code is, when a processor has massive caches, and massive out-of-order capabilities. A typical modern processor can have 200 instructions "in flight", that is in various stages of execution. So the time from trying to read the first instruction byte, to retiring the last instruction, can be quite long. But the actual delay to all other work that the processor needs doing may be (and typically is) a lot less.

Of course doing two calls to the operating system makes this completely unpredictable. You don't know what "writing to stdout" actually does, so you can't predict the time.

And you can't know the clock speed of the computer at the precise moment you run the code. It may be in some power saving mode, the computer may have reduced clock speed because it got hot, so even the same number of clock cycles can take different amounts of time.

All in all: Totally unpredictable.
> 47 votes

# Answer
You cannot do this in general, but in some senses, you very much can, and there have been a few historical cases in which you indeed *had* to.

The Atari 2600 (or Atari Video Computer System) was one of the earliest home video game systems and was first released in 1978. Unlike later systems of the era, Atari could not afford to give the device a frame buffer, meaning that the CPU had to run code at every scanline to determine what to produce - if this code took over 17.08 microseconds to run (the HBlank interval), the graphics would not be properly set before the scanline began drawing them. Worse, if the programmer wanted to draw more complex content than what the Atari normally allowed, they had to measure exact times for instructions and change the graphics registers as the beam was being drawn, with a span of 57.29 microseconds for the whole scan line.

However, the Atari 2600, like many other systems based on the 6502, had a very important feature that enabled the careful time management required for this scenario: the CPU, the RAM, and the TV signal all ran off clocks based on the same master clock. The TV signal ran off a 3.98 MHz clock, portioning the times above into an integer number of "color clocks" that managed the TV signal, and a cycle of the CPU and RAM clocks was exactly three color clocks, allowing the CPU's clock to be an accurate measure of time relative to the current progress TV signal. (For more information on this, check out the Stella Programmer's Guide, written for the Stella Atari 2600 emulator).

This operating environment, in addition, meant that every CPU instruction had a defined amount of cycles it would take in every case, and many 6502 developers published this information in reference tables. For instance, consider this entry for the `CMP` (Compare Memory with accumulator) instruction, taken from this table:

```
CMP  Compare Memory with Accumulator

     A - M                            N Z C I D V
                                    + + + - - -

     addressing    assembler    opc  bytes  cycles
     --------------------------------------------
     immediate     CMP #oper     C9    2     2
     zeropage      CMP oper      C5    2     3
     zeropage,X    CMP oper,X    D5    2     4
     absolute      CMP oper      CD    3     4
     absolute,X    CMP oper,X    DD    3     4*
     absolute,Y    CMP oper,Y    D9    3     4*
     (indirect,X)  CMP (oper,X)  C1    2     6
     (indirect),Y  CMP (oper),Y  D1    2     5*

*  add 1 to cycles if page boundary is crossed

```

Using all of this information, Atari 2600 (and other 6502 developers) were able to determine exactly how long their code was taking to execute, and construct routines that did what they needed and still complied with the Atari's TV signal timing requirements. And because this timing was so exact (especially for time-wasting instructions like NOP), they were even able to use it to modify the graphics as they were being drawn.

---

Of course, the Atari's 6502 is a very specific case, and all of this is possible only because the system had all of the following:

* A master clock that ran everything, including RAM. Modern systems have independent clocks for the CPU and the RAM, with the RAM clock often being slower and the two not necessarily being in sync.
* No caching of any kind - the 6502 always accessed DRAM directly. Modern systems have SRAM caches that make it more difficult to predict the state - while it is perhaps still possible to predict the behavior of a system with a cache, it is definitely more difficult.
* No other programs running simultaneously - the program on the cartridge had complete control of the system. Modern systems run multiple programs at once using non-deterministic scheduling algorithms.
* A clock speed slow enough that signals could travel across the system in time. On a modern system with clock speeds of 4 GHz (for example), it takes a photon of light *6.67 clock cycles* to travel the length of a half-meter motherboard - you could never expect a modern processor to interact with something else on the board in just one cycle, since it takes more than one cycle for a signal on the board to even reach the device.
* A well defined clock speed that rarely changes (1.19 MHz in the case of the Atari) - the CPU speeds of modern systems change all the time, while an Atari could not do this without also affecting the TV signal.
* Published cycle timings - the x86 does not define how long any of its instructions take.

All of these things came together to create a system where it was possible to craft sets of instructions that took an exact amount of time - and for this application, that's exactly what was demanded. Most systems do not have this degree of precision simply because there is no need for it - calculations either get done when they get done, or if an exact amount of time is needed, an independent clock can be queried. But if the need is right (such as on some embedded systems), it can still appear, and you will be able to accurately determine how long your code takes to run in these environments.

---

And I should also add the big massive disclaimer that all of this only applies to *constructing* a set of assembly instructions that will take an exact amount of time. If what you want to do is take some arbitrary piece of assembly, even in these environments, and ask "How long does this take to execute?", you categorically cannot do that - that is the Halting Problem, which has been proven unsolvable.

---

**EDIT 1:** In a previous version of this answer, I stated that the Atari 2600 had no way of informing the processor of where it was in the TV signal, which forced it to keep the entire program counted and synchronized from the very beginning. As pointed out to me in the comments, this is true of some systems like the ZX Spectrum, but is not true of the Atari 2600, since it contains a hardware register that halts the CPU until the next horizontal blanking interval occurs, as well as a function to begin the vertical blanking interval at will. Hence, the problem of counting cycles is limited to each scanline, and only becomes exact if the developer wishes to change content as the scanline is being drawn.
> 30 votes

# Answer
There are two aspects at play here

As @gnasher729 points out, if we know the exact instructions to execute, it's still difficult to estimate the exact runtime because of things like caching, branch prediction, scaling, etc.

However, the situation is even worse. Given a chunk of assembly, it's impossible to know which instructions will run, or even to know how many instructions will run. This is because of Rice's theorem: if we could determine that precisely, then we could use that information to solve the Halting Problem, which is impossible.

Assembly code can contain jumps and branches, which are enough to make the full trace of a program possibly infinite. There has been work on *conservative approximations* of execution time, that gives upper bounds on execution, through things like cost semantics or annotated type systems. I'm not familiar with anything for assembly specifically but I wouldn't be surprised if something like that existed.
> 15 votes

# Answer
Back in the era of 8-bit computers, some games did something like that. Programmers would use the exact amount of time it took to execute instructions, based on the amount of time they took and the known clock speed of the CPU, to synchronize with the exact timings of the video and audio hardware. Back in those days, the display was a cathode-ray-tube monitor that would cycle through each line of screen at a fixed rate and paint that row of pixels by turning on and off the cathode ray to activate or deactivate the phosphors. Because programmers needed to tell the video hardware what to display right before the beam reached that part of the screen, and fit the rest of the code into whatever time was left over, they called that “racing the beam.”

It absolutely would not work on any modern computer, or for code like your example.

Why not? Here are some things that would mess up the simple, predictable timing:

CPU speed and memory fetches are both bottlenecks on execution time. It’s a waste of money to run a CPU faster than it can fetch instructions to execute, or to install memory that can deliver bytes faster than the CPU can accept them. Because of this, old computers ran both off the same clock. Modern CPUs run much faster than main memory. They manage that by having instruction and data caches. The CPU will still stall if it ever needs to wait for bytes that aren’t in the cache. The same instructions will therefore run much faster if they’re already in the cache than if they’re not.

Furthermore, modern CPUs have long pipelines. They keep up their high throughput by having another part of the chip do preliminary work on the next several instructions in the pipeline. This will fail if the CPU doesn’t know what the next instruction will be, which can happen if there’s a branch. Therefore, CPUs try to predict conditional jumps. (You don’t have any in this code snippet, but perhaps there was a mispredicted conditional jump to it that clogged the pipeline. Besides, good excuse to link that legendary answer.) Similarly, the systems that call `int 80` to trap into kernel mode actually are using a complicated CPU feature, an interrupt gate, that introduces unpredictable delay.

If your OS uses preemptive multitasking, the thread running this code could lose its timeslice at any moment.

Racing the beam also only worked because the program was running on the bare metal and banged directly on the hardware. Here, you’re calling `int 80` to make a system call. That passes control over to the operating system, which gives you no timing guarantee. You then tell it do I/O on an arbitrary stream, which might have been redirected to any device. It’s much too abstract for you to say how much time the I/O takes, but it will surely dominate the time spent executing instructions.

If you want exact timing on a modern system, you need to introduce a delay loop. You have to make the faster iterations run at the speed of the slowest, the reverse not being possible. One reason people do so in the real world is to prevent leaking cryptographic information to an attacker who can time which requests take longer than others.
> 2 votes

# Answer
Would the choice of "computer system" happen to include microcontrollers? Some microcontrollers have very predictable execution times, for example the 8 bit PIC series have four clock cycles per instruction unless the instruction branches to a different address, reads from flash or is a special two-word instruction.

Interrupts will obvously disrupt this kind of timimg but it is possible to do a lot without an interrupt handler in a "bare metal" configuration.

Using assembly and a special coding style it is possible to write code that will always take the same time to execute. It isn't so common now that most PIC variants have multiple timers, but it is possible.
> 2 votes

# Answer
This is somewhat tangential but the space shuttle had 4 redundant computers that depended on being accurately synced, i.e. their run-time matching exactly.

The very first launch attempt of the space shuttle was scrubbed when the Backup Flight Software (BFS) computer refused to synchronize with the four Primary Avionics Software System (PASS) computers. Details in "The Bug Heard Round the World" here. Fascinating read about how the software was developed to match cycle for cycle and might give you interesting background.
> 1 votes

# Answer
I think we're mixing two different issues here. (And yes, I know this has been said by others, but I hope I can express it more clearly.)

First we need to get from the source code to the sequence of instructions that is actually executed (which needs knowledge of the input data as well as the code - how many times do you go round a loop? which branch is taken after a test?). Because of the halting problem, the sequence of instructions may be infinite (non-termination) and you can't always determine that statically, even with knowledge of the input data.

Having established the sequence of instructions to be executed, you then want to determine the execution time. That can certainly be estimated with some knowledge of the system architecture. But the problem is that on many modern machines, the execution time depends heavily on caching of memory fetches, which means it depends as much on the input data as on the instructions executed. It also depends on correct guessing of conditional branch destinations, which again is data dependent. So it's only going to be an estimate, it's not going to be exact.
> 0 votes

---
Tags: assembly
---


# Question
Title: What is the purpose of erasing a type application to a term-application in parametric polymorphism?
From *Types and Programming Languages* by Pierce

> **23 Polymorphism**
>
> **23.7 Erasure and Evaluation Order**
>
> in a full-blown programming language, which may include side- eﬀecting features such as mutable reference cells or exceptions, the type- erasure function needs to be deﬁned a little more delicately than the full era- sure function in §23.6. For example, if we extend System F with an exception- raising primitive error (§14.1), then the term
>
> ```
> let f = (λX.error) in 0;
>
> ```
>
> evaluates to 0 because λX.error is a syntactic value and the error in its body is never evaluated, while its erasure
>
> ```
> let f = error in 0;
>
> ```
>
> raises an exception when evaluated.
>
> What this shows is that type abstractions do play a signiﬁcant semantic role, since they stop evaluation under a call-by-value evaluation strategy and hence can postpone or prevent the evaluation of side-eﬀecting primitives. We can repair this discrepancy by introducing a new form of erasure appropriate for call-by-value evaluation, in which we **erase a type abstraction to a term-abstraction**
>
> ```
> erasev (x) = x
> erasev (λx:T 1 . t 2 ) = λx. erasev (t 2 )
> erasev (t 1 t 2 ) = erasev (t 1 ) erasev (t 2 )
> erasev (λX. t 2 ) = λ_. erasev (t 2 )
> erasev (t 1 [T 2 ]) = erasev (t 1 ) dummyv
>
> ```
>
> where **`dummyv` is some arbitrary untyped value, such as `unit`**.

* Is the purpose of "erase a type abstraction to a term-abstraction" to prevent the body of a type abstraction from being evaluated?
* What is the purpose of erasing a type application to a term-application by adding `dummyv`?
* What is the evaluation rule for an application when the argument is `unit`? (I can't find it in the section for type `Unit`.)

Thanks.

# Answer
> 1 votes
### Q1

* Is the purpose of "erase a type abstraction to a term-abstraction" to prevent the body of a type abstraction from being evaluated?

Yes.

> We can repair this discrepancy by introducing a new form of erasure appropriate for call-by-value evaluation, in which we erase a type abstraction to a term-abstraction

### Q2

* What is the purpose of erasing a type application to a term-application by adding `dummyv`?

The erasure introduces a term-abstraction into a type-abstraction:

```
eraseᵥ(λX. t₂) = λ_. eraseᵥ(t₂)

```

So the erasure needs a term-application instead of a type-application. An argument of the term-application can be any untyped value because it will be discarded, so for example `unit`.

### Q3

* What is the evaluation rule for an application when the argument is `unit`? (I can't find it in the section for type `Unit`.)

The unit value `unit` is a value. Therefore we can use (E-APPABS) for an application.

```
(λx:T₁₁. t₁₂) v₂ ⟶ [x ↦ v₂] t₁₂    (E-APPABS)

```

---
Tags: programming-languages, type-theory, types-and-programming-languages, polymorphisms
---


# Question
Title: Weaknesses arising from using same key in both channel directions
I came across the following question:
Which of the following risk may arise, when same key is used to encrypt both directions of a communication channel, that are not present if using different keys in both direction?
The answer to the question was reflection attack. The other options provided were denial of service, eavesdropping and none of the above.
I presume it could be eavesdropping. Eg: When a Diffie-Hellman key exchange is performed, a man-in-the-middle attack (type of eavesdropping attack) could occur.
So is the answer reflection attack or eavesdropping or something else entirely and why ? I tried looking up resources to justify and figure out the right answer but this is what I could conclude with.

# Answer
> 0 votes
Suppose that the keys used in both directions are the same. You listen to something sent from A to B:

```
kjhsdfiugdsa8ltr634o87qy5843jlgrwjklfjgsfds

```

You then listen to something sent from B to A:

```
jh35i798fdgkjh53jkh87gfhkjsfhtjk35h1o8798ug

```

Does it matter that the key is the same? Can you understand any of the messages?

If the answer to these questions is negative, then eavesdropping can be ruled out.

In contrast, suppose that you sent the following message from B to A:

```
kjhsdfiugdsa8ltr634o87qy5843jlgrwjklfjgsfds

```

You don't necessarily have any idea what this means, but it is identical to a message sent from A to B.

Because the key is the same, whatever meaning the original message had, so does this one.

This kind of attack (which is easy to thwart even if the keys are the same) is known as *replay*.

---
Tags: cryptography, security, encryption
---


# Question
Title: How to test implementation details when there are multiple ways of implementing the algorithm, without reading the code?
I want to make sure that the code that the written code is precisely doing what it is expected to do.

For example, if I want to search in an array particularly using linear search, I don't want binary search to pass the test. Unit test to test the method "search" would pass irrespective of the implementation which is not what I want. (I understand that binary search won't work if the data is unsorted, but lets say the data is sorted and I still want to make sure that it is a linear search and not the binary. In this case, I know that for sufficiently large input, BS would be way quicker than LS, but I want a generic answer where there might not be considerable difference in performance.)

Is there a way to achieve this?

An idea comes to my mind - Divide the method in extremely small submethods and make sure that all the submethods are implemented correctly and are used in main method. However this is not desirable, this might not be feasible always.

# Answer
> 1 votes
To find out if it is e.g. doing binary search (or using hashing, or whatever) inside, you have to look at what it is doing. No way around it.

Why would you insist on a particular algorithm? The whole point of *modularity* (and thus of much of modern programming languages and techniques) is to be able to hide such irrelevant details, and have users depend only on observable behaviour (so you can go back tomorrow and replace a simple, inefficient algorithm by a complex, efficient one, and noone is the wiser).

---
Tags: software-testing, testing
---


# Question
Title: How does a computer remember the address of a data variable in a program, in the main memory?
Suppose I write a program as below:

```
int main()
{
int a = 3;
int b = 4;
return 0;
}

```

Suppose the computer stores the address of 'a' as 0x00104. How does it associate 'a' with 0x00104?

# Answer
> 2 votes
> Suppose the computer stores the address of 'a' as 0x00104.

No, 'computer'(?) nowhere stores the address of 'a'. Compiler or assembler converts source code into object modules. Those object modules have instructions and data. 'a' is symbolic address which is bound by compiler to relocatable address. The linkage editor or loader in turn bind the relocatable address to absolute address. So, there is no storage but binding. Note that the absolute binding can be done at either compile time, load time or execution time where relocatable address binding will be done in any case by the compiler.

# Answer
> 0 votes
"a" may never make it into memory the way you are thinking.

At compile time what you know as "a" will cease to exist.

The line "int a = 3" will be replaced with an assembly instruction likely to look something like this:

```
LOAD R1 3

```

R1 is a register inside the CPU (could be R2, R3, etc). This assembly instruction tells the CPU to put the value 3 in R1. The compiler generates a list of assembly instructions which comprises your program executable. When you execute that program "LOAD R1 3" will appear somewhere in your computer memory, waiting to be loaded into your CPU instruction register (A register which tells the CPU what to do next, different from the R1 register). Its difficult to say what memory address that will end up in -- however i suspect that you are referring to the address of the variable in the same sense that you would get if you created a pointer to that variable.

As written in your program the value of "a" will never make it into any memory address. The compiler could write "a" to memory but would have no need to do so here.

There are two ways for the value of "a" to make it to memory in your program. One is by loading it onto the stack:

```
int main() {
int a = 3;
int b = 4;
someFunctionCall();
b = a + 1;
return 0;
}

```

If the compiler is simple it will issue an assembly instruction like this:

```
SW SP R1

```

This means store word (SW) at the memory address of the stack pointer (SP, another CPU register which stores a special memory address) and the value to store is in R1. The address R1 gets loaded in will vary and changes each time something new gets stored.

The second way for "a" to make it into memory would be on the heap. If you did something like:

```
int main() {
int [] a;
a = new(1);
A[0] = 3;
int b = 4;
return 0;
}

```

Not 100% sure on the syntax here -- my C is rusty. The heap is controlled by the operating system and therefore new() can be complicated. The OS will return a memory address, R1 will be loaded with a 3, then sent to memory using a similar instruction as the SW above. The address that the OS returns can be quite random.

# Answer
> 0 votes
The compiler analyses your program, and lays out space for whatever variables it really needs in memory. If the compiler is smart, here it will see that neither `a`nor `b` are ever used, and just don't assign space to them. For another program, the compiler may notice that `a` is always some fixed value, and use that one throughout, again not giving `a` an address. Yet another program uses `a` and `b` alternatively, the compiler is then allowed to place them at the same address. Or the value of `a` is short-lived, it is computed into a register, used and discarded. No address assigned. If you only ever use e.g. `5 * a + 3`, the compiler could invent it's own variable to hold that value and never even store `a`'s value.

The compiler's job is to write an assembly program that behaves as if it is doing as you wrote, but hopefully more efficient. As a programmer, you can't "see" where the compiler places your variables (if at all), it is free to juggle with them if worthwhile.

---
Tags: memory-allocation
---


# Question
Title: Doubt regarding Chomsky Hierarchy, CFG and CSG
I was following a discussion on a website, where a fellow scholar claims that this grammar

> S→ aAa | bAb | ϵ
>
> A→aA | bA |ϵ

is not CSG, so it should also NOT be a CFG. But this grammar properly satisfies the rules of CFG according me, on the other hand it fails to satisfy the conditions of CSG, which states that--

> In addition, a rule of the form
>
> ```
> S → λ
>
> ```
>
> where λ represents the empty string and S does not appear on the right-hand side of any rule is permitted

So the given grammar is definitely not in CSG. But According to chomsky hierarchy

A CFG should be contained in CSG, so why this rule is NOT being satisfied for this case?

# Answer
Note that the Chomsky Hierarchy is nowsadays considered as a hierarchy of language families. For each of the levels we both have suitable grammars and automata to generate and accept the languages in the family. Usually there is a relation between the devices for the different levels, but in some cases we have to be careful about the details.

You are right. The given grammar is context-free, but it is not context-sensitive. The reason is that with CSG we have to restrict the possibility for variables to generate the empty string. Technically the reason for this is that the context-sensitive languages are not closed uner erasing (deleting some letters).

So, any CFG that does not have $\varepsilon$-rules is also a CSG. Usually a CSG is not allowed to have $\epsilon$-rules. Of course that would mean that CSL do not contain the empty string. Well, the empty string can be handles separately if we need it. The same is true for, say, CFG in Chomsky normal form. Strict ChNF does not allow the empty string, but that is not a real restriction. Either we deal with the language without $\varepsilon$, or we have some complicated formulation that will allow generating $\varepsilon$ only in the first step of the derivation.
> 1 votes

# Answer
A CFG (in the strict sense) can't have a right hand side $\epsilon$ in a production. Neither can a CSG. So your example is neither, it is an unrestricted grammar.

You *can* allow "CFGs" with $\epsilon$ on right hand side of productions, because they can be modified automatically to eliminate those right hand sides. It is allowed in e.g. parser generators and in programming language descriptions, as it provides a very useful (and easily understandable!) shorthand. So, in C you can say "a function body is declarations, definitions, and statements in braces", and each of the above can be empty. If not, you'd have to lay out the full eight alternatives with missing pieces. Not at all nice.
> 0 votes

---
Tags: context-free, context-sensitive, chomsky-hierarchy
---


# Question
Title: Can we always transform a set of lines to a function?
If I have `n` lines in a programming language like Python (globally or inside a function):

```
..
..
# from here
..
..
..
..
# to here
..
..

```

or

```
def example():
    ...
    ...
    # from here
    ...
    ...
    ...
    ...
    # to here
    ...
    ...

```

can I always transform it to a function of the form `s1, s2, s3 … = function(s1, s2, s3 ...)`, where:

1. `s1`, `s2`, and `s3` etc are the local/global variables created/updated after the n lines gets executed.
2. `function` is almost the same code as the `n` lines above except it collects them and returns them?

As an example, in the below function:

```
def example():
    ...
    ...
    # from here
    ...
    ...
    a = 'c'
    b = 'd'
    ...
    ...
    # to here
    ...
    ...

```

I know I can do this:

```
def example():
    ...
    ...
    a, b = transform('a', 'b')
    ...
    ...

```

But my question is if I can extend this idea to any arbitrary `n` lines of code, abstracting them as an input-output block?

According to me, the only thing that happens after any `n` lines is executed, is a state change (as far as the program is concerned) - which can always be represented as a function with an input and output.

Am I missing something? Can someone please clarify?

# Answer
The short answer is yes. The longer answer is no.

The short answer is yes: that's a fundamental computation operation and it's pretty much the definition of a function. The equivalence between

```
def f(x):
    do something with x
f(foo)

```

and

```
do something with foo

```

is in fact the definition of a function, or more precisely of function application. This is so fundamental that it's the basis of the lambda calculus. In the lambda calculus, there are just three syntactic constructs:

* variables ($x$, $y$, …);
* applying a function to an argument ($F X$ where $F$ is a function and $X$ is the argument);
* lambda abstraction $\lambda x. M$ where $x$ is the parameter name and $M$ is the function body.

The lambda calculus gets its name from that $\lambda$ notation, and it's where Python got `lambda`. In the lambda calculus, there is a single computation rule, called **beta conversion** (beta reduction when done from left to right, beta expansion from right to left): $$ (\lambda x. M) N \equiv M\[x \leftarrow N\] $$ where $M\[x \leftarrow N\]$ means to replace $x$ by $N$ in $M$. (Details omitted because it would take a book chapter or two.) That single rule is enough to express all possible computations, in the sense that the lambda calculus is Turing-complete.

Beta conversion can be done in any language that has something that can reasonably called a function. But you need to take care of the details, and there are some language features that require additional effort or make it impossible in certain cases. Pretty much any language that isn't purely functional has restrictions on when beta expansion is correct.

In any language, the lines that you move to the new function must form a syntactic block. For example, if you have lines that are part of a multi-line construct like

```
while condition():
    instruction1()
    instruction2()

```

then you can move the loop out as a whole, but you can't move out `while condition(): instruction1()` and keep `instruction2()` in place.

One superficial but easily understood feature where beta conversion changes the behavior is **introspection features**. For example, if the language exposes a way to identify the current function or the function call stack trace, such as `traceback.extract_stack()` in Python, beta conversion changes that trace. If you put a call to `traceback.extract_stack` in a new auxiliary function, it's going to return something different. To make a beta-expansion that preserves the behavior, you'd need to modify calls to `traceback.extract_stack` to remove the new function from the trace. Note that this includes calls that may be deeply nested (if a function called inside the moved code calls a function that calls a function that … that calls `traceback.extract_stack`), so doing a fully behavior-preserving beta expansion turns into a global program transformation.

Another introspection feature of Python that breaks beta conversion is that it exposes local variables through `locals()`: `locals()['x']` evaluates to the same value as `x`. If the code that you move calls `locals()`, you also need to pass the variables accessed through `locals()` as arguments to the new function and return their new values. So it isn't a purely syntactic transformation anymore.

A more interesting interaction is with flow control features. If the instructions that you put in the new function have self-contained flow, meaning that they're executed by starting at the top and either finishing at the bottom or raising an exception, then beta expansion or beta conversion doesn't change anything. It's ok if the code has loops and function calls inside it. But if the block of code that you move contains a **non-local exit**, i.e. an instruction that makes the execution jump outside that block of code such as `return` or `break`, you can't just move it. Likewise if the block contains a jump target (in imperative languages that have `goto`). It's possible to get around this with a local transformation: make the auxiliary function take one more argument which indicates the entry point (if there's a way to jump into the middle of the code), and one more return value which indicates where to exit to (if there's a way to jump out to a place other than the end of the code block). For example:

```
def outer_function(x):
    if x == 1: return 2       #
    else: x = x - 1           #
    return x

```

If you want to extract the two lines marked with `#` on the right into a function, you need to remember whether to return the `2` or continue on to `return x`.

```
def new_auxiliary_function(x):
    if x == 1: return "RETURN", 2
    else: x = x - 1
    return "FALLTHROUGH", x
def new_outer_function(x):
    tmp = new_auxiliary_function(x)          #
    if tmp[0] == "RETURN": return tmp[1]     #
    x = tmp[1]                               #
    return x

```

Your transformation also changes exactly when variables are modified. This can become an issue due to **aliasing**. Aliasing is not normally an issue in Python since there's no way for a variable to designate another variable, as opposed to designating the same object as another variable. I wouldn't swear that it's never an issue, but I can't think of a way to do it. So instead I'll give an example in C, where aliasing is common due to pointers.

```
int x = 3;
int *p = &x;
*p = 2;                    //
printf("%d\n", x);         //

```

This code prints `2`, since the pointer `p` points to `x` and the line `*p = 2` therefore sets `x` to 2. Now let's create an auxiliary function for the part marked with `//`. Since C can't create compound values on the fly, we need to define a structure type for the return values, but that's just a cosmetic change compared with Python.

```
typedef struct {
    int x;
    int *p;
} values;
values new_function(int x, int *p) {
    *p = 2;
    printf("%d\n", x);
}
…

int x = 3;
int *p = &x;
values tmp = new_function(x, p);
x = tmp.x;
p = tmp.p;

```

The line `*p = 2` in `new_function` sets the *outer* variable `x` to 2, since that's where `p` points to. It does not change the variable `x` that is inside `new_function`. Therefore this program prints `3`.

When a compiler performs a beta reduction, it's called inlining. This is a common optimization, which typically makes the program run faster at the expense of larger code size. Compilers much more rarely do beta expansions. It's a worthwhile optimization when the same block of code (or more generally similar-enough blocks) appears more than once and code size is more important than execution speed, but it's difficult to detect worthwhile cases. Both transformations have limitations as to exactly when they're correct.
> 4 votes

# Answer
Maybe one issue is how to handle the early return.

Example:

```
# A function which returns a sum of 0, 1, ..., n.
def sum(n):
    # from here
    if n < 0:
        return 0
    answer = 0
    # to here
    for i in range(n+1):
        answer += i
    return answer

```

We want to transform the above three lines into one line:

```
answer = some_function(n)

```

But we can't directly return from `sum()` function just by calling `some_function()`.
> 2 votes

---
Tags: programming-languages, functional-programming
---


# Question
Title: What does it mean that a let-binding can be treated polymorphically, only if its right-hand side is a syntactic value?
*Types and Programming Languages* by Pierce says:

> **22.7 Let polymorphism**
>
> A ﬁnal point worth mentioning is that, in designing full-blown programming languages with let-polymorphism, we need to be a bit careful of the interaction of polymorphism and side-eﬀecting features such as mutable storage cells. A simple example illustrates the danger:
>
> ```
> let r = ref (λx. x) in
> (r:=(λx:Nat. succ x); (!r)true);
>
> ```
>
> ...
>
> It is better to change the typing rule to match the evaluation rule. Fortunately, this is easy: we just impose the restriction (often called the value re striction) that **a let-binding can be treated polymorphically—i.e., its free type variables can be generalized—only if its right-hand side is a syntactic value**. This means that, in the dangerous example, the type assigned to r when we add it to the context will be X→X, not ∀X.X→X. The constraints imposed by the second line will force X to be Nat, and this will cause the typechecking of the third line to fail, since Nat cannot be uniﬁed with Bool.

I am trying to understand the above sentence in bold.

* In the example, is the let binding not treated polymorphically, because `ref (λx. x)` is not a syntactic value?
* Could you give an example, where the let binding can be treated polymorphically?

Is the above sentence related to the following three sentences in bold? Or are they talking about several different things?

> **23.8 Fragments of System F**
>
> The most popular of these is the let-polymorphism of ML (§22.7), which is sometimes called prenex polymorphism because it can be viewed as a fragment of System F in which **type variables range only over quantiﬁer-free types (monotypes)** and in which **quantiﬁed types (polytypes, or type schemes) are not allowed to appear on the left-hand sides of arrows**. The special role of let in ML makes the correspondence slightly tricky to state precisely; see Jim (1995) for details.
>
> **23.2 Varieties of Polymorphism**
>
> More common in practice is the form known as ML-style or let-polymorphism, which restricts polymorphism to top-level let-bindings, **disallowing functions that take polymorphic values as arguments**, and obtains in return a convenient and natural form of automatic type reconstruction (Chapter 22).

Thanks.

# Answer
> 5 votes
You seem to have been confounded by many related and similar but crucially different concepts! Let me attempt to explain them one at a time.

**Parametric polymorphism** is the ability to write types that quantify universally over type variables using the $\forall$ quantifier. It is similar to template polymorphism in C++, or generics in Java. For example, the type $\forall \alpha . \alpha \rightarrow \alpha$ means "for each and every type $\alpha$, given an expression of type $\alpha$, this function returns an expression of type $\alpha$. This is (almost) equivalent to writing the Java method signature `public <T> T foo(T bar)`.

Parametric polymorphism is parametric in that *for each and every possible type $\alpha$, the function behaves in the same way*. This gives us powerful free theorems about the behavior of a function, e.g., a function with type $\forall \alpha . \alpha \rightarrow \alpha$ could only be the identity function, as you were given something of an unknown type, the only thing that you could do with it is to return it unchanged (unless you cheat by non-termination).

**Hindley-Milner** is a special and restricted form of parametric polymorphism, in that it only allows $\forall$ to appear at the beginning of a type. That is, you cannot have types like $\forall \alpha . (\forall \beta . \beta \rightarrow \beta) \rightarrow \alpha$. The reason why people love Hindley-Milner is that **type reconstruction (or type inference)**, or reconstructing the type of an expression without type annotations, is always deciable and *principal* (meaning that the type reconstructed is always the most general type possible).

The **value restriction** is a restriction in programming languges with both Hindley-Milner type systems and mutable storage. With the value restriction, a polymorphic type would only be inferred for a definition if the right-hand side of the definition is a syntactic value. The idea is to prevent problems with mutable store:

Consider the following ML program:

```
let r = ref []
r := [3]; r
let l = List.map (function true -> 1 | false -> 2) !r

```

Without the value restriction, the type `'a list ref` would be inferred for `r`. However, the second line makes the contents of `r` have the type `int list`, nevertheless `r` still keeps the (incorrectly) polymorphic type `'a list ref` and the third line would result in an uncaught type error!

The value restriction prohibits definitions whose right-hand side is not a syntactic value from being inferred a polymorphic type. In the program above, `r` would no longer have a polymorphic type since `ref []` is not a syntactic value. The second line will fix the type to `r` to `int list ref`, causing the third line to correctly report a type error.

For more about value restriction, the first and second part of Jacques Garrigue's paper *Relaxing the Value Restriction* explains it rather concisely. There is also Andrew Wright and Matthias Felleisen's paper *A Syntactic Approach to Type Soundness* in which the value restriction was first invented.

---
Tags: programming-languages, polymorphisms
---