# Tag Info

24

There are many reasons why the lambda calculus is so important. A very important reason is the lambda calculus allows us to have a model of computation in which computable functions are first-class citizens. One cannot express higher-order functions in the language of middle school algebra. Take as example the lambda expression $$\lambda f. \lambda g. \... 19 When you work with immutable data objects, functions have the property that every time you call them with the same inputs, they produce the same outputs. This makes it easier to conceptualize computations and get them right. It also makes them easier to test. That is just a start. Since mathematics has long worked with functions, there are plenty of ... 15 It is easier to correctly work with persistent data structures than it is to work with mutable data structures. This, I would say, is the main advantage. Of course, theoretically speaking, anything we do with persistent data structures we can also do with mutable ones, and vice versa. In many cases persitent data structures incure extra costs, usually ... 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 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 ...

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, ...

9

In a procedural language you can't necessarily express restrictions that are required to prove that the caller is using a module in a supported fashion. In the absence of a compiler checkable restriction, you have to write documentation and hope that it is followed, and use unit tests to demonstrate intended uses. Declaring Types is the most obvious ...

8

Procedural/functional programming is in no way weaker than OOP, even without going into Turing arguments (my language has Turing power and can do anything another will do), which do not mean much. Actually, object oriented techniques were first experimented in languages that did not have them built-in. In this sense OO programming is only a specific style ...

8

A bit of history is in order, I think. The era from the mid-1960s to the mid-1970s is known today as the "software crisis". I can't put it better than Dijkstra in his Turing award lecture from 1972: The major cause of the software crisis is that the machines have become several orders of magnitude more powerful! To put it quite bluntly: as long as ...

8

The key with functional programming is not that there is no state, it's that there is explicit state. What this means is, that your state is passed around as a parameter to your functions. It's an actual value, that you can get your hands on, look at, and pass to other functions. For example, let's look at the Dynamic Programming method of calculating the ...

7

This field has been invented many times, and goes under many names, such as: Online algorithms. Streaming algorithms, stream queries, continuous queries. Dynamic data structures. Self-adjusting computation (as per Andrej). (And possibly more.) Those are not the same, but related. Paraphrasing Cai et al (1): There are two core ways of implementing online ...

7

I wanna point out how they are different from a practical point of view: 1) actors send messages to other actors, this message passing is described explicitly and imperatively. For example: send msg to Actor137. 2) in FRP the data flow is described declaratively: For example: Cell134=Cell185+Cell42. The message passing is handled by the FRP framework ...

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

That of course depends on how exactly we define structured programming. We can look to the research papers that coined the phrase, such as the 1966 Structured Programming Theorem. Structured programming, as defined in these papers, would not permit partial execution of a loop body, and therefore neither a break, continue, return or throw statement (nor any ...

6

None, really. OOP doesn't really solve a problem, strictly speaking; there's nothing you can do with an object-oriented system that you couldn't do with a non object-oriented system- indeed, there's nothing you can do with either that couldn't be done with a Turing machine. It all turns into machine code eventually, and ASM is certainly not object-oriented. ...

6

When functions are first described to youngsters, they are essentially identified with graphs (plots), or perhaps with formulas; this is the way functions were understood historically before the advent of formalist trends in mathematics. Nowadays functions, as taught in first year calculus, are real functions, that is, functions from $\mathbb{R}$ to $\mathbb{... 5 A programming model is implied by the system architecture. If your system architecture is a register machine, your programming model will consist of machine code operations on registers. If your architecture is a stack machine, your programming model will consist of stack operations. A Von Neumann architecture and a Harvard architecture will have other ... 5 Let us go over your paradigms one by one: Local search: In this paradigm, we start with some solution and try to improve it by local changes. Local search can be applied to Sudoku in at least two ways: Start with a non-legal solution (either not satisfying the Sudoku constraints or not conforming to the filled cells), and try to make local changes (say, ... 4 Do not be too obsessed with it. It is often only buzzwords covering a fuzzy trend (from structured to object oriented) towards better organization of programs, with somewhat different realizations in different languages. It can appear in any programming paradigm, whether imperative or declarative. They are intended to improve readability of programs, good ... 4 I convinced myself that this is not possible, I was indeed mixing up the selection structure with conditional jumps; but they're not equally expressive. The conditional jump is as powerful as both selection and iteration together; this is what compilers use to rewrite both choice statements and loop statements. As a counterexample for rewriting any loop ... 4 There is no exact answer to your question. The terms "programming model" and "programming paradigm" are not exact technical terms that have fixed definitions. Depending on a context, some authors might define "programming model" in some specific way, but that will usually turn out to cover only some aspects of what people ... 4 I'll say up front I'm not an expert on this topic, but I did just spend a bit of time studying it and one of the most fascinating things to me in any topic is the history behind it. So to me understanding a bit of the history behind lambda calculus helps explain why it is useful. The short summary is that in the early 1900s after set theory started to take ... 4 Going from the point-free version to the lambda version is mechanical. Remember that composition is defined by (f . g) = (.) f g = \x. f (g x), so (f . g) x = f (g x). Remember also that (f . g) is syntactic sugar for (.) f g and f x y is shorthand for (f x) y. It's easier to follow what's going on if you apply one argument at a time. p = ((.) f) . g p x = (... 3 As Yuval pointed out in the comments Haskell is based on the$\lambda\$-calculus. Another reason why lambda calculus is so important is the Church-Rosser Theorem, which justifies the existence of lazy evaluation. (Which is one of Haskell's many cool features)

3

Having written embedded C for a few years managing things like devices, serial ports, and communications packets between the serial ports, network ports, and servers; I found myself, a trained electrical engineer with limited procedural programming experience, concocting my own abstractions from the hardware which ended up manifesting in what I later ...

3

Lambda calculus wasn't designed to be a programming language. Indeed, it was created in the 1930s, decades before we even had programmable computers. Rather, it was created as a formal model for studying computation, itself. If you're disappointed in how easily it expresses code, or mathematical functions, that's because that's not what it's for.

3

Object-oriented programming languages are designed to support programming. Whether they "properly" model the real world is beside the point and not the primary goal. So, when you ask "why haven't [these requirements] been included?", it's likely because those weren't considered relevant or necessary to the goal of supporting programming....

2

I want to understand at a low level what would happen if the data structure is not persistent? Let's look at a pseudorandom number generator with a huge state space (like "Mersenne twister" with a state of 2450 bytes) as a data structure. We don't really want to use any random number more than once, so there seems to be little reason to implement this as an ...

2

Adding to others' answers, and reinforcing a mathematical approach, functional programming also has a nice synergy with Relational Algebra, and Galois Connections. This is extremely useful in the area of Formal Methods. For instance: Formal proofs in program verification are simplified with Extended Static Checking; A number of properties from Relational ...

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