Questions tagged [imperative-programming]
The imperative-programming tag has no usage guidance.
2
votes
2answers
51 views
Is purely functional programming in some situations less efficient than imperative programming?
I am used to implementing algorithms in imperative languages. Many of the algorithms I have implemented use hash maps, hash sets, mutable arrays, heaps, doubly linked lists, etc. I understand that ...
2
votes
0answers
16 views
Formal semantics of a mutable/imperative stack
When introducing formal semantics for data structures, immutable stacks are a nice simple example :
$\mathit{is\_empty}(\mathit{create()})=\mathrm{True}$
$\mathit{is\_empty}(\mathit{push}(e, s))=\...
3
votes
1answer
32 views
“Immediate” method of translating arbitrary mutable program to equivalent unmutable program?
Consider the following program in "mutable style":
x=1
x=f(x);
x=f(x);
We can rewrite this in "immutable style" without changing the higher-level structure of ...
3
votes
2answers
254 views
The idea behind the state of Imperative languages
I was reading about programming paradigms and I have a question about the state when speaking about Imperative languages. What does it mean to change the program's state? Is it just an abstract idea? ...
5
votes
1answer
137 views
Best way to translate while loops to functions for software verification
I have a verification engine where while loops are translated into functional code, like this:
...
0
votes
2answers
178 views
Definition of “idempotence” of a function?
Currently there are two things that may change between invocations of a function: the return value, and the external states. I understand that if the external states changes, the function is not ...
2
votes
1answer
143 views
Can we add dependent type into an existing imperative programming language?
As we know, dependent type allows programmers to write bugless programs.
But as I know there's only very few languages support dependent type, like Haskell with extensions, Idris, Agda, F*, etc.
...
5
votes
2answers
350 views
Why don't imperative languages like C or Go support Haskell-like parametric polymorphism?
Why don't imperative languages support parametric polymorphism as powerful as whats in Haskell and OCaml?
More specifically if I call a function foo(x) that ...
2
votes
1answer
312 views
An imperative program is analogous to how a Turing machine works?
Since Turing machines has great influence on typical hardware architecture (Von Neumann) and both uses concept of state, is correct to say that an imperative program is analogous to how a Turing ...
0
votes
0answers
36 views
What is the origin of state concept?
On a Turing machine, the state changes during the execution of the program. Von Neumann architecture implements this machine theory and typical computer hardware uses Von Neumann architecture.
...
2
votes
0answers
556 views
What is the difference between a loop and a natural loop?
Is there a difference between a loop and a natural loop? Natural loops are defined as having a back edge to a head block that dominates it. If you have a natural loop nested inside of another ...
3
votes
0answers
55 views
Definition of imperative semantic in a HDL context
I've been studying from this book the topic of "Synthesis and optimization of digital circuit". In chapter 3 some theory about programming languages is exposed. I was wondering what's the meaning of ...
21
votes
1answer
1k 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
324 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
40 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
196 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
334 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:
...
3
votes
1answer
508 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
304 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.
...
7
votes
2answers
1k 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
550 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
19k 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
285 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$ ...
5
votes
1answer
595 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 ();
(...
