31

In a pure functional programming language, there is no real notion of time at all. So, saying that a variable x has value a at one point and then b later simply doesn't make any sense – it's like asking a character in a painting why she always stares in the same direction. The advantage of having no time is that you never† need to worry about the order in ...


10

The simplest kind of state is the configuration of memory. In C this memory is accessed through variables (and arrays and pointers, but let us ignore those), so the state is the values of variables. For example, suppose we have variables x and y whose values are 23 and 42 respectively (and no other variables). Then we could write the state as $$[x \mapsto ...


10

I don't know Brainfuck so you'll have to do some translation from my pseudocode. But, assuming that Brainfuck behaves sensibly (ha!), everything below should apply. do-while is equivalent to while-do. do X while Y is equivalent to X; while Y do X and, assuming you have conditionals, while Y do X is equivalent to if Y then (do X while Y). Life is a bit ...


10

If we peel off the syntactic sugar on the front and the code generation on the back and compare what happens in between when converting source to running code for imperative languages, such as C or Java with functional languages such as ML or OCaml we will generally find the following differences in what, why, and how. Mutable vs. immutable With functional ...


10

I can only share my perspective. The way I think of it is that mainstream functional languages typically combine two themes: (1) support for higher-order functions, and (2) a preference for pure computation (referential transparency, no side effects, no mutation). In principle those two could potentially be separable, but they often go together in many ...


9

A functional programming language is notable for what it prohibits. It prohibits modifying an existing variable or data structure. You can program in a "functional style" in some imperative programming languages, but the language won't protect you from accidentally modifying an existing variable or data structure. For example, here is a recursive, ...


8

Performance is not a property of language, it is a property of specific programs within a language. Some languages might be very fast at some things and slow at others. For example, Chez-Scheme can sometimes find performance comparable to C, not because the language is more efficient, but because defensive practices that programmers often use in C are less ...


8

If we want to be very precise with our words, we should say that in functional programming you don't assign a value to a variable, because assignment is a thing that you "do", and if you are telling the computer what to "do" then you are doing imperative programming instead of functional programming. In a functional programming language, ...


7

I think what you want is essentially conversion to static single assignment (SSA) form, followed by closure conversion, followed by conversion to continuation passing style. Static single assignment form guarantees that each variable is written exactly once in the program text. That this is the key step in converting imperative to functional programs is ...


7

Your example of "functional programming" is a pretty poor one. For starters, it is not functional because it uses state (it stores something in words and behind the scenes set(words) is doing stateful stuff as well). To actually learn what functional programming is about, you should look outside an imperative language such as Python. Python often uses ...


6

There are several reasons, but they boil down to three main points: It's easier to reason about correctness, especially in the context of complex semantics (e.g. existential types, lazy evaluation) and security. It allows for optimisations that are not possible if data can change underneath. It allows for a transparent models of multi-threading, since read-...


6

In functional programming, great pains are taken to be able to know exactly what a computation depends on. The way in which you make variables be mutable, there can be cascading effects on the rest of the language. If you just make them mutable, in that they are reference cells, then what you are effectively doing is wrapping the entire language in a state ...


5

Since the question does not fully describe the language, I assume the simpler case when the $\texttt{++}$ operator applies only to variables given by an identifier, for example: $\texttt{foo++}$. Short of having more examples of the way you write denotational semantic, I have to improvise a bit. In particular, I avoid lambda notation since I do not know ...


4

So, it's possible, but there are certainly some barriers: What kinds of expressions are allowed in types? What does it mean for a type to have a side-effect? Can typrchecking my program perform IO? Just because dependent types are in the system doesn't mean they provide a type safe language. It may be possible to produce proofs of False if the underlying ...


4

The real answer is that the designers of those languages chose not to include it. It's certainly technically possible. As has been said in the comments, Rust does, Java does, C# does, etc. However, there are some difficulties. The first is in the choice of impelemtation strategy. Polymorphism is easy if you're working with Lambda Calculi and looking only ...


4

What would it be like to have variable reassignment in functional programming? First i is 0, then you do something and change i to 1 ... But that is "do this, then that". Imperative programming; not functional. Functional programming is declarative. You write a whole bunch of functions and the computer takes care of calling them as needed. If you ...


3

At a high enough level and when contrasted with functional programming, sure. Turing machine models and imperative programs have in common that they start from an input and take a series of steps that change a state stored in memory, ending with some output. This contrasts with lambda calculus and functional programming which generally and loosely do not ...


3

The state monad allows us to translate any stateful (you call it "mutable") program to a pure one. The changes required to the program are "local" in the sense that you only need to make superficial changes to the syntax, assuming you use Haskell-style do notation. For example, the following is the Haskell translation of your program into a pure program: do ...


3

Yes. There are problems where we can prove there is a $\Omega(\lg \lg n)$ factor slowdown. We also know that the slowdown is at most $O(\lg n)$ in all cases. See What classes of data structures can be made persistent?.


3

Your understanding is not correct. There are two major programming paradigms: imperative programming and declarative programming. In imperative programming you basically tell your computer what to do to solve a certain problem by providing an algorithm which might be implemented as a composition of different functions and/or methods. Often one distinguishes ...


3

Functional programming is great for parallel programming that is not concurrent. The example problem you gave is inherently concurrent, but we can make it non-concurrent by "batching" the work that needs to be performed. The batch form of the problem you suggested is like this. Input: length of desired array, and collection of indices to increment. ...


3

The triple $\{Q\}C\{X\}$ states that if $Q$ holds, then after executing $C$, the condition $X$ holds. Now suppose that $\{Q\}C\{X\}$ and that $P \Longrightarrow Q$. We will prove that $\{P\}C\{X\}$. Indeed, suppose that $P$ holds. Since $P \Longrightarrow Q$, also $Q$ holds. Hence if we execute $C$, then $X$ will hold. Altogether, we see that $\{P\}C\{X\}$ ...


3

Not that I know of, but "stateful function" is reasonably descriptive. In informal conversation, that's what I'd use, as long as I suspect the audience will understand what I mean. In formal writing, I might still use the same phrase but also provide a careful definition of what I meant by that phrase. Really, that's a large part of what "formal" writing ...


2

There isn't a single loop invariant: any property that remains true during the execution of the loop is a loop invariant. For example, “I am not the Pope” is an invariant of this loop, but it is not a useful one. A useful loop invariant is one that helps in proving some property of the program. Here, presumably, the ultimate point of the exercise is to ...


2

I recommend that you translate while(c) b to def myWhile() = if (c) then (b ; myWhile()) myWhile() With this translation, the precondition of myWhile is the loop invariant of the original while loop. So, this becomes the question of how to find the loop invariant of a loop. In general, that requires manual annotation. If you do a search, you should be ...


2

There are two related concepts called "idempotence" in programming. One is the mathematical one that quicksort and Raphael talk about. Namely, given a mathematical function $f$, $f$ is idempotent if $f(f(x))=f(x)$. Or more algebraically, $f\circ f = f$. The other notion that's common in practice and particularly for distributed computations is if an ...


2

I'm not sure functional programming does make parallel programming any easier, when taken in the round. If you program in a "functional style" (including all so-called good practices), then converting certain steps of a serial program to parallel execution (and getting results that are equivalent to the serial execution) may not usually involve ...


2

The grammatical classification of the sentence types you're asking about isn't well-defined for programming languages because they refer to common ways humans respond to being talked to, which don't apply closely to computers. The declarative, interrogative, imperative and exclamative grammatical forms are so named because those are the purposes to which ...


2

Optimizers in C++ turn traditional C++ code into static single assignment when it can. You can think of traditional imperative programming as chaining together functional steps. struct state { int sum; int i; }; auto numsum1 = [](int n){ return fpipe{} | []{ return state{0, 1}; } | while_loop( [n](state s){ return s.i<=n; } )( [](...


2

Disallowing assignment is part of the definition of "functional programming" and "functional language". On one level, you're simply asking why the definition of "functional language" is correctly being applied, so that languages which allow mutation of local variables are not eligible. Why is variable mutation excluded from the ...


Only top voted, non community-wiki answers of a minimum length are eligible