The tag has no usage guidance.

learn more… | top users | synonyms

15
votes
1answer
346 views

Does a do-while loop suffice for Turing-completeness?

I know that, in imperative programming languages, a while-do loop is sufficient as a control flow construct to make the language Turing-complete (as far as control flow goes - of course we also need ...
2
votes
1answer
50 views

Why precondition strengtening is sound in Hoare logic

I have problem with understanding why precondition strengthening is sound rule in Hoare logic. The rule is: $$ {P \implies Q, \{Q\} C \{X\} } \over {\{P\} C \{X\}} $$ I really do not understand why ...
3
votes
2answers
27 views

Is there a formal term for functions that have static state across executions?

Two examples, one in PHP: function adder($i){ static $a = 0; $a += $i; return $a; } A similar effect can be achieved with closures in javascript: ...
6
votes
2answers
147 views

Eliminate non-local references from closure

For a code similarity detection framework I need to eliminate references to non-local variables, for example having the following closure: ...
2
votes
1answer
111 views

Do functional algorithms require more memory than imperative algorithms? [closed]

Let's suppose we are counting words in string. We split it so what we have is an array of strings. I'll use Python as an example. The imperative approach would as follows: ...
2
votes
1answer
132 views

Denotational semantics of expressions with side effects

I'm doing revision for a module on programming language semantics and I'm having trouble understanding the introduction of side-effects in expressions. We assume a standard syntax for arithmetic ...
1
vote
1answer
89 views

Loop invariant: decreasing a variable and swapping it

As an example exercise, we were asked to find the loop invariant for this bit of code. ...
4
votes
2answers
302 views

Isn't Functional Programming just Imperative Programming in disguise?

A YouTube video I was watching explained the differences between Imperative and Functional programming by demonstrating how the numbers from 1 to ...
1
vote
1answer
468 views

Asymptotic time complexity of a two-loop program

I have two pieces of code in a function which I'm trying to calculate the asymptotic running time for: ...
7
votes
2answers
13k views

Is it possible to find the nth term of a Fibonacci sequence using a definitive for loop?

I'm using the book Introduction to Computer Science by John Zelle and at the end of Chapter 3 (Computing with numbers), I'm asked to find the nth term of a Fibonacci sequence presumably using a ...
5
votes
1answer
225 views

termination of two concurrent threads with shared variables

We're in a shared memory concurrency model where all reads and writes to integer variables are atomic. do: $S_1$ ...
3
votes
1answer
336 views

Double-nested loop with bitwise operation

I have this little exercise: for ( i = 0; i < 2 * n; i += 2 ) for ( j = 1; j <= n; j <<= 1 ) if ( j & i ) foo (); (...