4 ms·

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

by 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
  Still not quite my point :-) What I'm talking about is modeling this aspect of Scheme's behavior: (define x 5) (define (f y) (+ x y)) (f 5) => 10 (set! x 10) (f 5) => 15 Scheme's lambda evaluates its body during application, under the environment of its evaluation. Your LexLam evaluated its body with the right env, but in the wrong time: A subsequent mutation of env would not alter the result of application. Conversely, DynLam evaluates its body at the right time (during application), but with the wrong env. Given this code: (define (f y) (+ x y)) (let ((x 5)) (f 5)) => Error, x is unbound in f Your DynLam would incorrectly evaluate to 10, right? I just don't see how to model this behavior without IORefs :-)
  - jerf 12y ago
    It's possible you just need to work with it for a while. IORefs can't do anything the State type can't do in a single-threaded execution context. Nothing prevents any evaluation strategy you propose that makes sense from being adopted by Haskell. FWIW, I recognize your confusion as something I've had myself. I worked it out in Erlang, not Haskell, but it's the same principles. Again, ignoring threading, functional programming can do anything imperative programming can do with at most a log n penalty because at worst the functional program can simply simulate a raw expanse of memory in a tree and implement mutation on top of that. What you're asking about is ultimately much simpler than that but you may just have to work with it for a while. All I can really do is assure you that no, IORefs are completely unnecessary in this case. And again let me emphasize my sympathies with your position and that I do not mean this harshly... I am recalling where I myself was in the past. Until I worked with it for long enough for it to click I'm not sure anyone really could have explained it to me. I'd been imperating for a long time.
    - tel 12y ago
      I wrote a number of posts pertaining to that log n trick: http://jspha.com/posts/mutable_algorithms_in_immutable_languges_part_1/ http://jspha.com/posts/mutable_algorithms_in_immutable_langu...
  - tel 12y ago
dllthomas 12y ago
"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." The first part of this is your error. "Env" is the entire runtime environment we are modeling, which includes the values of any mutable variables at the point in time we are considering. Therefore, it must be (in Haskell space) a function of Env. That doesn't mean that it is (explicitly) a function of Env in Scheme space - you typically have no way of reifying Env in Scheme space to talk about that.

by tpush 12y ago

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
Still not quite my point :-) What I'm talking about is modeling this aspect of Scheme's behavior: (define x 5) (define (f y) (+ x y)) (f 5) => 10 (set! x 10) (f 5) => 15 Scheme's lambda evaluates its body during application, under the environment of its evaluation. Your LexLam evaluated its body with the right env, but in the wrong time: A subsequent mutation of env would not alter the result of application. Conversely, DynLam evaluates its body at the right time (during application), but with the wrong env. Given this code: (define (f y) (+ x y)) (let ((x 5)) (f 5)) => Error, x is unbound in f Your DynLam would incorrectly evaluate to 10, right? I just don't see how to model this behavior without IORefs :-)
- jerf 12y ago
  It's possible you just need to work with it for a while. IORefs can't do anything the State type can't do in a single-threaded execution context. Nothing prevents any evaluation strategy you propose that makes sense from being adopted by Haskell. FWIW, I recognize your confusion as something I've had myself. I worked it out in Erlang, not Haskell, but it's the same principles. Again, ignoring threading, functional programming can do anything imperative programming can do with at most a log n penalty because at worst the functional program can simply simulate a raw expanse of memory in a tree and implement mutation on top of that. What you're asking about is ultimately much simpler than that but you may just have to work with it for a while. All I can really do is assure you that no, IORefs are completely unnecessary in this case. And again let me emphasize my sympathies with your position and that I do not mean this harshly... I am recalling where I myself was in the past. Until I worked with it for long enough for it to click I'm not sure anyone really could have explained it to me. I'd been imperating for a long time.
  - tel 12y ago
    I wrote a number of posts pertaining to that log n trick: http://jspha.com/posts/mutable_algorithms_in_immutable_languges_part_1/ http://jspha.com/posts/mutable_algorithms_in_immutable_langu...
- tel 12y ago

dllthomas 12y ago

"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." The first part of this is your error. "Env" is the entire runtime environment we are modeling, which includes the values of any mutable variables at the point in time we are considering. Therefore, it must be (in Haskell space) a function of Env. That doesn't mean that it is (explicitly) a function of Env in Scheme space - you typically have no way of reifying Env in Scheme space to talk about that.