Can everything be modelled as functions?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.