5 ms·

Interesting paper. My question is: Turing Machines are easily and intuitively understood as state-machines. But what about Functional Programming? I thought fu

Interesting paper. My question is: Turing Machines are easily and intuitively understood as state-machines. But what about Functional Programming? I thought functional programs have no 'state'. What is the simplest way to explain how functions are also state-machines?

ww520 3y ago
Functions in functional programming have states, the input parameters and return output are states.
- robotresearcher 3y ago
  Being in particular function is itself a state, too. The program counter, stack pointer, and stack contents are all state.
  - skydhash 3y ago
    That’s the C abstract machine, not the Lisp one.
    - robotresearcher 3y ago
      Most language implementations have these or similar things. Variations don’t change the point I’m making.
    - deleted 3y ago
      [deleted]
    - kazinator 3y ago
      The C abstract machine has nothing about stacks or program counters. There is the concept of sequencing: what is currently being evaluated, what has been evaluated and what is not yet evaluated. When a function is called, the calling function is suspended; then when the invoked function returns, the caller is resumed. From that we can infer that there must exist an activation chain. Mainstream Lisps have all these abstract elements also. The main differences are in data, and environments what constitutes a value; what is a type; what is a variable; what is the lifetime of an object, and the scope of visibility of a binding, ...
- 082349872349872 3y ago
  ...which implies that (when viewing a computation as a sequence of states [vertices] connected by transitions [edges]) the more functional one's program is, the larger the chunks are that one can effectively model as atomic transitions, and the shorter these state sequences are. Reducing N may not qualitatively do much from the pedant's point of view, but if one's (formal or informal) analyses tend to scale as O(N*3), reducing N quantitatively may make a difference: between tractable (for formal analysis) or "fits in developers' heads" (for informal analysis) on the one hand, and a big ball of mud on the other.
skydhash 3y ago
Functional programming is all about substitution as an evaluation mechanism. So you do substitution until it’s no longer possible. The final expression is thus your solution or how you can find your solution. And the final expression is equivalent to the initial one. The state does not lies in the code, but in the set of variables. Once a specific combination of variable/values is known, so is the output.
- galaxyLogic 3y ago
  When you do substitutions the state of your engine changes while you do them. The implementation is keeping track of your intermediate results by storing them in the state-machine that is your runtime. But to me this just suggests that you are using a state-machine to SIMULATE Lambda Calculus. The point of FP to me is that you can hide the state from the programmer. As far as the programmer, or the reader of the source-code is concerned there is no state and no state-machine. Lambda Calculus is a specific "model of computation" which does not look like a "state-machine" to me. So calling it a "state-machine" is a bit misleading. Yes you need a state-machine to "simulate" Lambda Calculus. But how it is implemented, the programmer does not need to know or care. All they see is functions and no state, at least no state they could directly modify. The program state (if any) and runtime state are two separate things. And if you the programmer can not modify the state of the state-machine, then it is not a state-machine for you.
  - Jtsummers 3y ago
    Check out section 2.2 where he compares different models to state machines and expresses how they can be mapped. In particular look at the BNF grammar one, where he talks about production rules. In functional languages (especially pure ones) there is the notion of "reductions" which are rewrite rules for the language. So in Scheme (to pick a concrete language) an expression like: (+ 5 2) Is reduced by applying the addition operation: (+ 5 2) => 7 Or (with a suitable definition of factorial to continue his example): ;; using his Program 3 in Scheme instead of C (define (factorial i) (if (= i 1) 1 (* i (factorial (- i 1))))) (factorial 7) => (if (= 7 1) 1 (* 7 (factorial (- 7 1)))) ;; because we substitute 7 for i => (if #f 1 (* 7 (factorial (- 7 1)))) ;; reducing (= 7 1) => #f => (* 7 (factorial (- 7 1))) ;; reducing (if #f e_t e_f) => e_f => ... Each of these arrived at by applying a reduction rule (in this case there's only one reduction rule available at each point). This is analogous to his discussion of BNF grammars. The state transitions are moving from an expression e to an expression e' where some reduction rule has been applied to e. EDIT: Grammar and comments describing application of reduction rules.
mrkeen 3y ago
> What is the simplest way to explain how functions are also state-machines? Here is a complete specification of a state machine's transitions: f LightOff OnPressed = LightOnDimmed f LightOnDimmed OnPressed = LightOnMedium f LightOnDimmed OffPressed = LightOff f LightOnMedium OnPressed = LightOnBright f LightOnMedium OffPressed = LightOff f LightOnBright OnPressed = LightOnDimmed f LightOnBright OffPressed = LightOff Here is a Haskell function which models the above state machine's transitions: f LightOff OnPressed = LightOnDimmed f LightOnDimmed OnPressed = LightOnMedium f LightOnDimmed OffPressed = LightOff f LightOnMedium OnPressed = LightOnBright f LightOnMedium OffPressed = LightOff f LightOnBright OnPressed = LightOnDimmed f LightOnBright OffPressed = LightOff
- jbritton 3y ago
  Is then executed something like: foldr f LightOff input_stream
  - galaxyLogic 3y ago
    It seems to me it calculates the result given some input. Can you incrementally give it new inputs and have the result depend on not only the new input but also all previous inputs? Where are the previous inputs and results (= state) of the calculation stored which allow the next calculation depend on previous results? In some variable?
    - jbritton 3y ago
      # foldr above was a mistake # foldl state = LightOff while data { input = get_next(data) state = f(state, input) }
    - mrkeen 3y ago
      Sure, but I've run after the shifting goal post enough. I want you to translate the above state machine to a Turing Machine, or demonstrate in any way how a TM is a tool or model which brings any kind of clarity or simplicity to any modelling, design, compilation or coding activity.
tromp 3y ago
It's not that functions are themselves state machines, but functional languages are sometimes implemented as state machines. E.g. the lambda calculus can be implemented on an abstract machine known as the Krivine machine [1]. [1] https://en.wikipedia.org/wiki/Abstract_machine#Functional_programming_languages https://en.wikipedia.org/wiki/Abstract_machine#Functional_pr...
- f1shy 3y ago
  The metacircular evaluator is the state machine
  - tromp 3y ago
    I wouldn't call something like this metacircular evaluator of binary lambda calculus (λ11)(λλλ1(λλλλ3(λ5(3(λ2(3(λλ3(λ123)))(4(λ4(λ31(21)))))) (1(2(λ12))(λ4(λ4(λ2(14)))5))))(33)2)(λ1((λ11)(λ11))) a state machine.
    - galaxyLogic 3y ago
      Right, what would be the states in it? What would be the state-transitions? How many are there? How does it model a physical system with multiple states and state-transitions? Can a functional program return to its previous state ever? If not I don't think it should be called "state-machine". It can calculate what should be the next state of some state-machine, but that does not mean it is that "state-machine".
- mrkeen 3y ago
  > It's not that functions are themselves state machines The functions are the transitions of the state machine. The datatypes are the rest.
f1shy 3y ago
While there is no state inside funcions, there is an execution state (the execution stack)
deterministic 3y ago
f(state,event) = next_state In other words, each call to f “updates” the state machine by calculating the next state of the state machine.

ww520 3y ago

Functions in functional programming have states, the input parameters and return output are states.

robotresearcher 3y ago
Being in particular function is itself a state, too. The program counter, stack pointer, and stack contents are all state.
- skydhash 3y ago
  That’s the C abstract machine, not the Lisp one.
  - robotresearcher 3y ago
    Most language implementations have these or similar things. Variations don’t change the point I’m making.
  - deleted 3y ago
    [deleted]
  - kazinator 3y ago
    The C abstract machine has nothing about stacks or program counters. There is the concept of sequencing: what is currently being evaluated, what has been evaluated and what is not yet evaluated. When a function is called, the calling function is suspended; then when the invoked function returns, the caller is resumed. From that we can infer that there must exist an activation chain. Mainstream Lisps have all these abstract elements also. The main differences are in data, and environments what constitutes a value; what is a type; what is a variable; what is the lifetime of an object, and the scope of visibility of a binding, ...
082349872349872 3y ago
...which implies that (when viewing a computation as a sequence of states [vertices] connected by transitions [edges]) the more functional one's program is, the larger the chunks are that one can effectively model as atomic transitions, and the shorter these state sequences are. Reducing N may not qualitatively do much from the pedant's point of view, but if one's (formal or informal) analyses tend to scale as O(N*3), reducing N quantitatively may make a difference: between tractable (for formal analysis) or "fits in developers' heads" (for informal analysis) on the one hand, and a big ball of mud on the other.

skydhash 3y ago

Functional programming is all about substitution as an evaluation mechanism. So you do substitution until it’s no longer possible. The final expression is thus your solution or how you can find your solution. And the final expression is equivalent to the initial one. The state does not lies in the code, but in the set of variables. Once a specific combination of variable/values is known, so is the output.

galaxyLogic 3y ago
When you do substitutions the state of your engine changes while you do them. The implementation is keeping track of your intermediate results by storing them in the state-machine that is your runtime. But to me this just suggests that you are using a state-machine to SIMULATE Lambda Calculus. The point of FP to me is that you can hide the state from the programmer. As far as the programmer, or the reader of the source-code is concerned there is no state and no state-machine. Lambda Calculus is a specific "model of computation" which does not look like a "state-machine" to me. So calling it a "state-machine" is a bit misleading. Yes you need a state-machine to "simulate" Lambda Calculus. But how it is implemented, the programmer does not need to know or care. All they see is functions and no state, at least no state they could directly modify. The program state (if any) and runtime state are two separate things. And if you the programmer can not modify the state of the state-machine, then it is not a state-machine for you.
- Jtsummers 3y ago
  Check out section 2.2 where he compares different models to state machines and expresses how they can be mapped. In particular look at the BNF grammar one, where he talks about production rules. In functional languages (especially pure ones) there is the notion of "reductions" which are rewrite rules for the language. So in Scheme (to pick a concrete language) an expression like: (+ 5 2) Is reduced by applying the addition operation: (+ 5 2) => 7 Or (with a suitable definition of factorial to continue his example): ;; using his Program 3 in Scheme instead of C (define (factorial i) (if (= i 1) 1 (* i (factorial (- i 1))))) (factorial 7) => (if (= 7 1) 1 (* 7 (factorial (- 7 1)))) ;; because we substitute 7 for i => (if #f 1 (* 7 (factorial (- 7 1)))) ;; reducing (= 7 1) => #f => (* 7 (factorial (- 7 1))) ;; reducing (if #f e_t e_f) => e_f => ... Each of these arrived at by applying a reduction rule (in this case there's only one reduction rule available at each point). This is analogous to his discussion of BNF grammars. The state transitions are moving from an expression e to an expression e' where some reduction rule has been applied to e. EDIT: Grammar and comments describing application of reduction rules.

mrkeen 3y ago

> What is the simplest way to explain how functions are also state-machines? Here is a complete specification of a state machine's transitions: f LightOff OnPressed = LightOnDimmed f LightOnDimmed OnPressed = LightOnMedium f LightOnDimmed OffPressed = LightOff f LightOnMedium OnPressed = LightOnBright f LightOnMedium OffPressed = LightOff f LightOnBright OnPressed = LightOnDimmed f LightOnBright OffPressed = LightOff Here is a Haskell function which models the above state machine's transitions: f LightOff OnPressed = LightOnDimmed f LightOnDimmed OnPressed = LightOnMedium f LightOnDimmed OffPressed = LightOff f LightOnMedium OnPressed = LightOnBright f LightOnMedium OffPressed = LightOff f LightOnBright OnPressed = LightOnDimmed f LightOnBright OffPressed = LightOff

jbritton 3y ago
Is then executed something like: foldr f LightOff input_stream
- galaxyLogic 3y ago
  It seems to me it calculates the result given some input. Can you incrementally give it new inputs and have the result depend on not only the new input but also all previous inputs? Where are the previous inputs and results (= state) of the calculation stored which allow the next calculation depend on previous results? In some variable?
  - jbritton 3y ago
    # foldr above was a mistake # foldl state = LightOff while data { input = get_next(data) state = f(state, input) }
  - mrkeen 3y ago
    Sure, but I've run after the shifting goal post enough. I want you to translate the above state machine to a Turing Machine, or demonstrate in any way how a TM is a tool or model which brings any kind of clarity or simplicity to any modelling, design, compilation or coding activity.

tromp 3y ago

It's not that functions are themselves state machines, but functional languages are sometimes implemented as state machines. E.g. the lambda calculus can be implemented on an abstract machine known as the Krivine machine [1]. [1] https://en.wikipedia.org/wiki/Abstract_machine#Functional_programming_languages https://en.wikipedia.org/wiki/Abstract_machine#Functional_pr...

f1shy 3y ago
The metacircular evaluator is the state machine
- tromp 3y ago
  I wouldn't call something like this metacircular evaluator of binary lambda calculus (λ11)(λλλ1(λλλλ3(λ5(3(λ2(3(λλ3(λ123)))(4(λ4(λ31(21)))))) (1(2(λ12))(λ4(λ4(λ2(14)))5))))(33)2)(λ1((λ11)(λ11))) a state machine.
  - galaxyLogic 3y ago
    Right, what would be the states in it? What would be the state-transitions? How many are there? How does it model a physical system with multiple states and state-transitions? Can a functional program return to its previous state ever? If not I don't think it should be called "state-machine". It can calculate what should be the next state of some state-machine, but that does not mean it is that "state-machine".
mrkeen 3y ago
> It's not that functions are themselves state machines The functions are the transitions of the state machine. The datatypes are the rest.

f1shy 3y ago

While there is no state inside funcions, there is an execution state (the execution stack)

deterministic 3y ago

f(state,event) = next_state In other words, each call to f “updates” the state machine by calculating the next state of the state machine.