snippetMinor
How can I represent state or environment in the $\lambda$-Calculus?
Viewed 0 times
cantherepresentcalculusenvironmentstatehowlambda
Problem
I have seen in different tutorials how to represent numbers and booleans in the pure $\lambda$-Calculus, and how to define some arithmetic and logic operations. But what if I want to represent other constructs, not usually encouraged in pure functional languages, like state (assignment of values to variables) and sequencing (evaluating $e_1$ before $e_2$)?
For example, how would I encode an assignment "$v := e$" (where $v$ is a variable and $e$ an environment)? And what about encoding "$x := 2; y := y + x$"? (The point is that there is a dependency among statements, and they should be evaluated/executed in the correct order.)
For example, how would I encode an assignment "$v := e$" (where $v$ is a variable and $e$ an environment)? And what about encoding "$x := 2; y := y + x$"? (The point is that there is a dependency among statements, and they should be evaluated/executed in the correct order.)
Solution
Such a thing is, for the most part, impossible in the pure lambda calculus: all variables represent immutable values.
However, you can fake it in a number of ways.
The simplest is parameter passing. For a function which has a "state", you give it an extra parameter, which is a data structure mapping variables to their values. Any time you alter a variables value, you just create a new store with the updated value, and use it as the new parameter.
This pattern of passing the state to each computation in sequence can be abstracted using a State monad, or something similar. A state monad provides a pattern where the machinery of creating a new store, updating its values, and correctly passing it to future functions.
Monads provide a sequencing operator, which allow for the ordered evaluation that you mention.
There exists calculi which have mutation built into them, but first off, they aren't the pure calculus as you asked for, and in such cases, you don't encode mutation, you add it as a primitive operation.
However, you can fake it in a number of ways.
The simplest is parameter passing. For a function which has a "state", you give it an extra parameter, which is a data structure mapping variables to their values. Any time you alter a variables value, you just create a new store with the updated value, and use it as the new parameter.
This pattern of passing the state to each computation in sequence can be abstracted using a State monad, or something similar. A state monad provides a pattern where the machinery of creating a new store, updating its values, and correctly passing it to future functions.
Monads provide a sequencing operator, which allow for the ordered evaluation that you mention.
There exists calculi which have mutation built into them, but first off, they aren't the pure calculus as you asked for, and in such cases, you don't encode mutation, you add it as a primitive operation.
Context
StackExchange Computer Science Q#55211, answer score: 4
Revisions (0)
No revisions yet.