4 ms·

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 i

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.
- galaxyLogic 3y ago
  I can see that making a call to a sub-function and returning from, it to the calling function means the state of the execution has changed. But it means the state of the engine that evaluates the functions. As was said earlier the functions themselves do not have a state. I don't think anybody would try to model a state-machine by making each state-change they want to model a call to a sub-function. The engine evaluating the function-expressions has its state but the functional program itself does not, it just has it code, arguments, and result. It can be in one of the states 1. Not Called 2. Calculating the result 3. The result has been calculated.
  - Jtsummers 3y ago
    > It can be in one of the states > 1. Not Called 2. Calculating the result 3. The result has been calculated. That describes an oracle, not a purely functional program. A program describes a process (whether the program is purely functional or totally imperative). The state of the process can be captured in progress because, well, it's a process. There is a series of steps which are applied to produce the calculated result. In purely functional programs, that would be the reduction rules. Each application of a reduction rule produces a new state (in essence the remaining computation to be performed).
mrkeen 3y ago
>> I thought functional programs have no 'state' > The point of FP to me is that you can hide the state from the programmer Well which is it?
- galaxyLogic 3y ago
  No programmer-visible state. If you ask the programmer "What is the current state of your functional program?" they probably cannot answer can they? The functional programs have no state, the engine that runs the program of course has. But the engine that runs the program is not a functional program.

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.

galaxyLogic 3y ago
I can see that making a call to a sub-function and returning from, it to the calling function means the state of the execution has changed. But it means the state of the engine that evaluates the functions. As was said earlier the functions themselves do not have a state. I don't think anybody would try to model a state-machine by making each state-change they want to model a call to a sub-function. The engine evaluating the function-expressions has its state but the functional program itself does not, it just has it code, arguments, and result. It can be in one of the states 1. Not Called 2. Calculating the result 3. The result has been calculated.
- Jtsummers 3y ago
  > It can be in one of the states > 1. Not Called 2. Calculating the result 3. The result has been calculated. That describes an oracle, not a purely functional program. A program describes a process (whether the program is purely functional or totally imperative). The state of the process can be captured in progress because, well, it's a process. There is a series of steps which are applied to produce the calculated result. In purely functional programs, that would be the reduction rules. Each application of a reduction rule produces a new state (in essence the remaining computation to be performed).

mrkeen 3y ago

>> I thought functional programs have no 'state' > The point of FP to me is that you can hide the state from the programmer Well which is it?

galaxyLogic 3y ago
No programmer-visible state. If you ask the programmer "What is the current state of your functional program?" they probably cannot answer can they? The functional programs have no state, the engine that runs the program of course has. But the engine that runs the program is not a functional program.