7 ms·

This was my very first 'big' haskell project! I had a lot of fun making it and afterwards I decided to start following compilers courses at my university!(https

This was my very first 'big' haskell project! I had a lot of fun making it and afterwards I decided to start following compilers courses at my university!(https://github.com/arianvp/Haskeme https://github.com/arianvp/Haskeme). I'd recommend anyone dabbling in their first days of haskell to take a try at this project. You will learn a great deal and most of all it's just extremely cool. Was a lot of fun to build and I would do it totally differently if I would do it again. For example I would've added lexical scoping and handle variables with a Reader or State instead of IORefs . It's quite possible to make an almost fully pure implementation without using I/O for variables.

tpush 12y ago
How would you implement mutable closures without using IORefs, though? In Scheme the environment that is captured by a lambda expression is mutable; how would you accomplish that without IORefs? (Genuine question, as I'm currently implementing an R7RS Scheme interpreter in Haskell and was wondering this before I just went with IORefs.)
- tome 12y ago
  A variable that is mutable to Scheme doesn't need to be implemented as mutable in Haskell. Simulate mutable state in the usual way by passing the "before" state into functions and the "after" state out.
  - tpush 12y ago
    How would that work to model mutable closures? During the evaluation of a Scheme lambda expression, the current environment needs to be captured somehow. Assuming the resulting value of the evaluated lambda expression is something like (Haskell pseudocode): (env, (Env -> [Value] -> Cont -> IO ())) where 'env' is the captured environment. Further assuming this tuple is stored in the environment, how would you propagate a change to 'env' without it being an IORef and using writeIORef?
    - 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.
- dllthomas 12y ago
  A mutable variable in the hosted language is a getter and setter (or equivalently, a lens) on the hosted environment.
bitL 12y ago
Don't forget to make a Prolog as well. 48h should be sufficient as well ;-)

tpush 12y ago

How would you implement mutable closures without using IORefs, though? In Scheme the environment that is captured by a lambda expression is mutable; how would you accomplish that without IORefs? (Genuine question, as I'm currently implementing an R7RS Scheme interpreter in Haskell and was wondering this before I just went with IORefs.)

tome 12y ago
A variable that is mutable to Scheme doesn't need to be implemented as mutable in Haskell. Simulate mutable state in the usual way by passing the "before" state into functions and the "after" state out.
- tpush 12y ago
  How would that work to model mutable closures? During the evaluation of a Scheme lambda expression, the current environment needs to be captured somehow. Assuming the resulting value of the evaluated lambda expression is something like (Haskell pseudocode): (env, (Env -> [Value] -> Cont -> IO ())) where 'env' is the captured environment. Further assuming this tuple is stored in the environment, how would you propagate a change to 'env' without it being an IORef and using writeIORef?
  - 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.
dllthomas 12y ago
A mutable variable in the hosted language is a getter and setter (or equivalently, a lens) on the hosted environment.

bitL 12y ago

Don't forget to make a Prolog as well. 48h should be sufficient as well ;-)