2

Let's consider an example: I want to turn on/off a light bulb. In C, I could just write:

struct lightbulb { int is_turned_on; /* from 1 to 10 */ int light_intensity; };

Whenever I want to turn the light bulb on or off, I change is_turned_on to 1 and how bright it is by setting light_intensity from 1 (dimmest) to 10 (brightest).

How can I do the same in functional programming? I guess I will have to create a list to hold these values, create a function ON and OFF to "turn" the light bulb on/off, and a function to return the light intensity of the light bulb. Every time the function is called, a new lightbulb is returned:

(defun turn-on() '(1 0)) (defun turn-off() '(0 0)) (defun light-intensity (x) `(0 ,(eval x)))

I can see that function like light-intensity is a continuous function similar to a linear function. It will evaluate to the same result no matter how many times we pass the same argument x, for every x. The result of each function is a new light bulb with different state.

The problem is, how can I persist states? Obviously, I have to store it in somewhere in my memory through variable.

UPDATE: I found answer to above question through c2 Wiki - Functional Programming

How do data items persist?

On the stack. In a sequential, batch program, data is initialized and transformed in a top-level function. In a long-lived program like a server, a top level looping function is called recursively, passing global state from one call to the next.

I also have to create a new object (list) every time the function is called, how can I destroy the previous old object?

Isn't it more efficient and simpler to just mutate the variables through defparameter and setf? Imagine if it's not a light bulb, but a more complicated object with much more information? How can I model this as a function?

Improve this question
4
  • 2
    Both your C code and your Common Lisp code are incorrect. In C you cannot assign fields in a struct declaration. In Lisp you cannot apply 0. And I don't understand what you are asking.... Mutable data is not really functional programming. Commented Nov 1, 2012 at 9:06
  • Oh I forgot. I intended to write a main function, but somehow decided to not write and mixed up with struct declaration. I will fixed. But about the Lisp code, that's what I understand. I studied Common Lisp for a while, not Scheme. Commented Nov 1, 2012 at 9:12
  • I am asking how to handle states efficiently with pure functional programming, without having another copy just to make it "referential transparency"? By reading the paper "Why functional programming matters", the paper suggests that not having assignment is NOT an advantage of FP. Commented Nov 1, 2012 at 9:18
  • Btw Lisp code is correctly executed in CLISP interpreter. Commented Nov 1, 2012 at 9:20

3 Answers 3

Reset to default
2

The problem is, how can I persist states? Obviously, I have to store it in somewhere in my memory through variable.

I think you are looking at functional programming from an imperative viewpoint, which happens a lot and can be confusing. In functional programming rather than representing a program as a series of steps that modify state (by setting variables, for instance) it's represented as a set of interdependent math-style functions which each contain just one expression. Because the only reason to include multiple lines in a function would be to modify state, in purely functional programming, all functions are one-liners; this means code runs as a cascading series of function calls. Programs tend to be viewed more like descriptions of problems than step-by-step instructions.

I also have to create a new object (list) every time the function is called, how can I destroy the previous old object?

I think all functional programming languages use garbage collection. Fewer side effects and memory aliasing mean that it's simpler to work out when memory isn't being used anymore.

Isn't it more efficient and simpler to just mutate the variables through defparameter and setf? Imagine if it's not a light bulb, but a more complicated object with much more information? How can I model this as a function?

I am not sure what you are asking here.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

The last question means by simply change the value of a variable rather than going through all steps of evaluation, we can still have what we want. Imagine I have an object with a heavy structure (i.e. trees), I can't afford to copy the whole thing just to modify a value.
@Amumu You don't copy the whole thing, because in pure functional style it's always safe to share data. For example, if you need a new tree with a different value somewhere down in the left branch, you can directly use a reference to the right branch in your new tree. Trying to do that in an imperative setting risks confusing bugs when you later modify part of the tree in place while somebody else was still using the original value (see every second SO question in the Python tag with "list" in the title).
Ah I see. So we can reuse existing data without fear of destructing. But, having to create a branch is still heavy weight. For example, I delete a node in my binary tree. In C, I would just rewire the parent's pointer to the children of the deleted node. From what you suggest, it seems I have to update a whole branch starting from the deleted node, because I can't update the parent's pointer.
I experienced frustrating bugs with excessively use of mutable data structure though. I used to implement Karger's min cut algorithm in C, and let every node in node linked list refer to the elements in that exact list through pointer. As a result, when it came to node merging, I got all kinds of bugs that I had to maintain a list of head nodes for each node in the graph to reduce the complexity with operating on the same list. However, I never think of the polar opposite such as immutable data structure.
To add to Ben: this is also why compilers are so important in functional programming such as Haskell. As Ben said, to ensure that things such as "null-point exceptions" cannot occur in functional programming, it is not possible to "point" to data, but you can only copy it. The compiler will try to figure out as much as possible when data actually does not need to be copied, which is a much safer way than letting the user figure it out themselves. So in a way, the responsibility of copying and manipulating data safely is shifted from the user to the compiler.
|
1

I am asking how to handle states efficiently with pure functional programming, without having another copy just to make it "referential transparency"?

One can handle state efficiently in functional programming, provided that the language supports linear types. Namely, each mutable cell is given a linear type, and a typechecker sees to it that any variable of linear type is neither discarded nor duplicated at programmer's will. For instance, this is not allowed:

val x = make_reference (5) // [x] is a mutable cell val y = x val res = !x + !y // the syntax [!x] is for reading a value of a cell

It isn't allowed because [x] has a linear type, and values of linear types can't be duplicated (which is essentially what we are doing on the next line, when binding [y] to [x]). This kind of duplication is also called "aliasing" (or "sharing"), and in turn, aliasing is what makes state-manipulating programs harder to reason about (for instance, by breaking referential transparency). So, linear types restrict aliasing and that is an aid in reasoning about programs. Most of the time a program with linear types is referentially transparent, and retains some similarity to a purely functional program.

Here is an example in ATS that uses linear types in order to deal with (mutable) state.

typedef lightbulb (b: bool) = @{is_turned_on= bool b, light_intensity= intBtw (1, 10)} fn lightbulb_make {b:bool} (state: bool b, intensity: intBtw (1, 10)) :<> lightbulb b = @{is_turned_on= state, light_intensity= intensity} // The [&T1 >> T2] notation means that function expects to be given // a term of type T1, and then on exit, the type of the term will // change to T2. // In our case, the function expects a lightbulb either turned on or off, // but on exit, the lightbulb will be turned off. fn lightbulb_turn_on {b:bool} (x: &lightbulb b >> lightbulb true) :<> void = x.is_turned_on := true fn lightbulb_change_intensity {b:bool} (x: &lightbulb b, y: intBtw (1, 10)) :<> void = x.light_intensity := y implement main () = let var bulb = lightbulb_make (false, 5) val () = lightbulb_turn_on (bulb) val () = lightbulb_change_intensity (bulb, 3) in printf ("intensity is now: %d\n", @(bulb.light_intensity)) end
Improve this answer

3 Comments

I would appreciate if you can transform your example into Common Lisp or Scheme. But thanks anyway.
@Amumu: It didn't actually occur to me you were interested in CL or Scheme, sorry. (Could you clarify this in your question?) However, both languages have a facility of mutable (unrestricted) references. So that should be (mostly) enough for efficient handling of state (excepting handling of scarce resources, i.e. resources with limited lifetime, e.g. file handles, sockets, or manual memory management). If you are interested in a purely functional way, then I'd suggest looking into lenses (these crop up often in Haskell). Another thing would be a zipper data structure.
Thanks. I updated the question. I often find myself revert back to the imperative style when trying to be functional in Common Lisp. I think I will study Haskell to understand the concept better.
0

I know you already answered to your question but just for fun, here's some insight of what can be done with functions: -Constants can be defined by functions that just return one value -The natural numbers can be represented by a constant (0) and a function (adding 1) -Text can be considered an array of constants -The real numbers can also be defined via a function -Some functions can output other functions

Basically, you can do everything with functions, even representing types, it's a little bit more abstract than with imperative languages but I think it's pretty cool that you can do absolutely everything with just functions.

Some of this stuff just has theoretical implications and nothing more but, yeah it's fun :) Ftr I don't miss imperative logic when I'm writting functional stuff, you just have to get used to it I guess.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.