[HN Gopher] Computation and State Machines (2008) [pdf]
___________________________________________________________________
Computation and State Machines (2008) [pdf]
Author : Jtsummers
Score : 56 points
Date : 2023-07-12 15:12 UTC (7 hours ago)
(HTM) web link (lamport.azurewebsites.net)
(TXT) w3m dump (lamport.azurewebsites.net)
| dlisboa wrote:
| For anyone interested, Dr. Lamport has a book called "Specifying
| Systems", which has more in-depth explanations of many of the
| topics in the linked paper:
|
| http://lamport.azurewebsites.net/tla/book-21-07-04.pdf
| galaxyLogic wrote:
| 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?
| skydhash wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| >> 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?
| ww520 wrote:
| Functions in functional programming have states, the input
| parameters and return output are states.
| robotresearcher wrote:
| Being in particular function is itself a state, too. The
| program counter, stack pointer, and stack contents are all
| state.
| skydhash wrote:
| That's the C abstract machine, not the Lisp one.
| kazinator wrote:
| 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, ...
| robotresearcher wrote:
| Most language implementations have these or similar
| things. Variations don't change the point I'm making.
| [deleted]
| 082349872349872 wrote:
| ...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.
| f1shy wrote:
| While there is no state inside funcions, there is an execution
| state (the execution stack)
| tromp wrote:
| 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_pr...
| f1shy wrote:
| The metacircular evaluator is the state machine
| tromp wrote:
| I wouldn't call something like this metacircular evaluator
| of binary lambda calculus
| (l11)(lll1(llll3(l5(3(l2(3(ll3(l123)))(4(l4(l31(21))))))
| (1(2(l12))(l4(l4(l2(14)))5))))(33)2)(l1((l11)(l11)))
|
| a state machine.
| mrkeen wrote:
| > It's not that functions are themselves state machines
|
| The functions are the transitions of the state machine. The
| datatypes are the rest.
| mrkeen wrote:
| > 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
| WhitneyLand wrote:
| (summary via gpt4/editing)
|
| Discusses the fundamental role of state machines in computer
| science.
|
| In computer science, there's an excessive focus on languages,
| often obscuring the fact that languages all describe state
| machines.
|
| The document intends to demonstrate how state machines express
| computation and clarify the concepts underpinning the various
| languages used to describe computations. It then delves into
| state machines' function within the sphere of 'correctness' in
| computer science, drawing on works related to Abstract State
| Machines by Yuri Gurevich and others.
| mistrial9 wrote:
| > languages all describe state machines
|
| this is not accurate; some computer programs behave like state
| machines, but others do not .. not even close
| jonsen wrote:
| Computers are general concrete state machines. Computer
| programs behave by conducting a computer into a specific
| state machine behaviour. So it can't be wrong to say that all
| computer programs describe state machines.
| WhitneyLand wrote:
| I think you're correct practically speaking. The spirit of
| what you're saying is true.
|
| However technically, and pedantically, all programs must
| behave like state machines.
|
| Btw it looks like it's the author of the paper, not gpt4
| making this confusing point so if one disagrees with the
| summary it's a disagreement with the paper.
|
| Here's a link that covers your specific point:
| https://softwareengineering.stackexchange.com/a/288063
| Jtsummers wrote:
| Three past discussions:
|
| * https://news.ycombinator.com/item?id=11854376 - June 7, 2016 (6
| comments)
|
| * https://news.ycombinator.com/item?id=13153846 - Dec 11, 2016
| (24 comments)
|
| * https://news.ycombinator.com/item?id=18012672 - Sept 18, 2018
| (8 comments)
| strogonoff wrote:
| Brilliant summary (and subsequent discussion) of Lamport's
| paper in one of those older threads:
| https://news.ycombinator.com/item?id=13155666
___________________________________________________________________
(page generated 2023-07-12 23:01 UTC)