3 ms·

How would that work to model mutable closures? During the evaluation of a Scheme lambda expression, the current environment needs to be captured somehow. As

• tome 12y ago
  If you have many references to mutable closures I guess indeed it would be simplest to use IORefs or STRefs. However, you can simulate most of the functionality of IORefs and STRefs using a state monad so it is possible to avoid them, at least theoretically.
• jerf 12y ago
  You end up with something more like Env -> [Value] -> Cont -> IO (Env, Value) Immutability in functional programming is better understood as "the only time something can change is when a function is being called, which can be passed new arguments", rather than "nothing can ever change". This means that things can't change within the execution of a function. So when you produce the new Env, you pass it along to the next opcode's implementation, and it is just as if the Env changed from the point of view of the next opcode implementation. It just didn't change uncontrollably. Whereas an imperative program works with a lot of loops, I imagine a functional program as passing through endless, endless stack frames, like https://youtu.be/77f0Yj9uMRA?t=2m5s https://youtu.be/77f0Yj9uMRA?t=2m5s . Stack frames, endless stack frames being created. (Tail-call optimization is often cited as important to avoid blowing out the stack. It's also important just for sheer performance, so we're not literally making calls for every function call, i.e., pushing registers and state.) Haskell plays immutability to the hilt, as laziness is very difficult to imagine without it. Most other languages with immutability should probably instead have Rust-style mutation control, in my opinion, as it maintains almost all of the interesting properties of immutability in strict languages while being easier to program with, and easier to make high performance.
  • tpush 12y ago
    I'm sorry, I didn't quite convey what I actually wanted to know. I'm aware of how to model mutable state by simply passing in and "returning" the state, that's not the problem. Let me try to explain again, bear with me: Assuming the evaluation function is evalLambda :: Env -> LambdaExpr -> Proc (I'm purposefully ignoring continuations and possible IO here. Also, a new Env is not returned because evaluating a lambda doesn't mutate the environment.) The result of evaluating a lambda expression is a procedure that closed over its environment, so let's assume Proc is a function that has a copy of the environment passed to evalLambda. Note that it is not a function that takes an Env, as the closing-over happens when evaluating a lambda and not during its application. Now, the interesting thing happens when the result of the lambda, the function, is stored somewhere, and after that a variable whose binding was closed over by evalLambda is mutated: The function evaluating the assignment/definition correctly produces an updated environment, but how will the stored Proc know? I can't see how this can be done without IORefs, honestly.
    • tel 12y ago
      If you're talking about dynamic scoping then the cheapest way to pull that off is just to store the AST for your lambda, unevaluated, in the Env and evaluate it in the new Env which is available at call time. It's all about controlling what evaluation occurs at what time. Here's another example: a language with dynamic and lexical bindings. You can see how the time when evaluation of the body of the lambda varies. I'm being very heavy-handed here, though—this only works for a pure language. type Name = String data Exp = Var Name | LexLam Name Exp | DynLam Name Exp | App Exp Exp | Base eval :: Exp -> Exp eval = eval0 emptyEnv where eval0 env e = case e of Var nm -> lookup nm env -- throws exception on failure Base -> Base LexLam name body -> LexLam name (eval0 (add env name (Var name)) body) DynLam _ _ -> e App l r -> case (eval0 env l, eval0 env r) of (LexLam name body, val) -> eval0 (singletonEnv name val) body (DynLam name body, val) -> eval0 (add env name val) body
      • tpush 12y ago
• tel 12y ago
  Typically you want to talk about a function like eval :: Syntax -> Semantics In Scheme `Syntax` is some kind of tree-like Sexpr thing or possibly a more well-defined AST. So let's focus on `Semantics` instead. Ultimately, a perfectly fine semantics is `IO ()`. As Haskell's "sin bin", `IO` circumscribes all of the effects you need. So, the entirety of this game is to capture as much effect as you can "purely" so that it is reflected intelligently in the type. The key pure semantic component for managing changing state is to focus on "changes" instead of points in state space. This we need a notion of the initial state (the empty env) and then a series of functions Env -> Env If we let `Semantics = Env -> Env` then we've already captured a meaningful chunk of Scheme semantics purely. We cannot observe Scheme side effects---they would have to be faked and thrown away---but we can observe how the env evolves. To be a bit more clear, this eval "respects" the syntax properly---if `seq :: Syntax -> Syntax -> Syntax` sequences two Sexprs then eval (seq sexpr1 sexpr2) = eval sexpr2 . eval sexpr1 e.g. sequencing of syntax is just function composition in the "Env transformer semantics". So that's how we avoid IORefs. From here we just build more. Another fun thing to add would be input and output. Here we note that any given Syntactic fragment no longer merely transforms Envs but may also either attempt to print out some text or want to read it in. data Print e = Simple e | Read (Text -> e) | Write (Text, e) type Semantics = Env -> Print Env and now we'd expect things like eval "(read)" env === Read (\input -> env) eval "(write \"foo\") env === Write ("foo", env)