Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.7k views
in Technique[技术] by (71.8m points)

haskell - Get value from IO rather than the computation itself

Being quite new to Haskell, I'm currently trying to improve my skills by writing an interpreter for a simple imperative toy language.

One of the expressions in this language is input, which reads a single integer from standard input. However, when I assign the value of this expression to a variable and then use this variable later, it seems ot me that I actually stored the computation of reading a value rather the read value itself. This means that e.g. the statements

x = input;
y = x + x;

will cause the interpreter to invoke the input procedure three times rather than one.

Internally in the evaluator module, I use a Map to store the values of variables. Because I need to deal with IO, this gets wrapped in an IO monad, as immortalized in the following minimal example:

import qualified Data.Map as Map

type State = Map.Map String Int
type Op = Int -> Int -> Int

input :: String -> IO State -> IO State
input x state = do line <- getLine
                   st <- state
                   return $ Map.insert x (read line) st

get :: String -> IO State -> IO Int
get x state = do st <- state
                 return $ case Map.lookup x st of
                            Just i -> i

eval :: String -> Op -> String -> IO State -> IO Int
eval l op r state = do i <- get l state
                       j <- get r state
                       return $ op i j

main :: IO ()
main = do let state = return Map.empty
          let state' = input "x" state
          val <- eval "x" (+) "x" state'
          putStrLn . show $ val

The second line in the main function simulates the assignment of x, while the third line simulates the evaluation of the binary + operator.

My question is: How do I get around this, such that the code above only inputs once? I suspect that it is the IO-wrapping that causes the problem, but as we're dealing with IO I see no way out of that..?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

Remember that IO State is not an actual state, but instead the specification for an IO machine which eventually produces a State. Let's consider input as an IO-machine transformer

input :: String -> IO State -> IO State
input x state = do line <- getLine
                   st <- state
                   return $ Map.insert x (read line) st

Here, provided a machine for producing a state, we create a bigger machine which takes that passed state and adding a read from an input line. Again, to be clear, input name st is an IO-machine which is a slight modification of the IO-machine st.

Let's now examine get

get :: String -> IO State -> IO Int
get x state = do st <- state
                 return $ case Map.lookup x st of
                            Just i -> i

Here we have another IO-machine transformer. Given a name and an IO-machine which produces a State, get will produce an IO-machine which returns a number. Note again that get name st is fixed to always use the state produced by the (fixed, input) IO-machine st.

Let's combine these pieces in eval

eval :: String -> Op -> String -> IO State -> IO Int
eval l op r state = do i <- get l state
                       j <- get r state
                       return $ op i j

Here we call get l and get r each on the same IO-machine state and thus produce two (completely independent) IO-machines get l state and get r state. We then evaluate their IO effects one after another and return the op-combination of their results.

Let's examine the kinds of IO-machines built in main. In the first line we produce a trivial IO-machine, called state, written return Map.empty. This IO-machine, each time it's run, performs no side effects in order to return a fresh, blank Map.Map.

In the second line, we produce a new kind of IO-machine called state'. This IO-machine is based off of the state IO-machine, but it also requests an input line. Thus, to be clear, each time state' runs, a fresh Map.Map is generated and then an input line is read to read some Int, stored at "x".

It should be clear where this is going, but now when we examine the third line we see that we pass state', the IO-machine, into eval. Previously we stated that eval runs its input IO-machine twice, once for each name, and then combines the results. By this point it should be clear what's happening.

All together, we build a certain kind of machine which draws input and reads it as an integer, assigning it to a name in a blank Map.Map. We then build this IO-machine into a larger one which uses the first IO-machine twice, in two separate invocations, in order to collect data and combine it with an Op.

Finally, we run this eval machine using do notation (the (<-) arrow indicates running the machine). Clearly it should collect two separate lines.


So what do we really want to do? Well, we need to simulate ambient state in the IO monad, not just pass around Map.Maps. This is easy to do by using an IORef.

import Data.IORef

input :: IORef State -> String -> IO ()
input ref name = do
  line <- getLine
  modifyIORef ref (Map.insert name (read line))

eval :: IORef State -> Op -> String -> String -> IO Int
eval ref op l r = do
  stateSnapshot <- readIORef ref
  let Just i = Map.lookup l stateSnapshot
      Just j = Map.lookup l stateSnapshot
  return (op i j)

main = do
  st <- newIORef Map.empty   -- create a blank state, embedded into IO, not a value
  input st "x"               -- request input *once*
  val <- eval st (+) "x" "x" -- compute the op
  putStrLn . show $ val

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...