0

I have a data type:

data Instr = LOADI Val| LOAD Val| ADD Val| STORE Val | JMP Val| JMPLESS Val| JMPGE Val deriving (Eq, Read, Show)

and a function iexec that takes an instruction and a configuration to perform a process and returns the new configuration.

iexec :: Instr -> Config -> Config

where Config is defined as: type Config = (Int, [*], [*]) An example is LOADI which takes value Val (an Integer) and loads it onto a stack, with the config argument giving the information on the stack. It would look something like this in GHCI:

>iexec (LOADI 5) (0, empty, []) > (1, fromList[], [5])

where the program counter increases to 1, and 5 is added to the stack (I'm not sure what the fromList[] means, any explanation for that would be appreciated). I'm also not sure if my config type declaration is correct.

How would I finish the iexec function to allow this to work? Anything to point me in the right direction would be appreciated. Thank you.

Improve this question
2
  • What should the second list represent? I assume 1 is the "program counter? and the third one is the stack, but it is unclear what the second item does. Commented Nov 4, 2021 at 16:34
  • @WillemVanOnsem I'm not too sure either. I think it is a mapping for elements already in the stack, and it is empty in this case as it is a fresh stack. It is very unclear in the specification. Commented Nov 4, 2021 at 16:38

1 Answer 1

Reset to default
2

This looks like an exercise based on the book Concrete Semantics. This language appears on page 96. From this description there, it looks like the configuration is a combination of a program counter, a "memory" (i.e., list of integer-indexed variables), and a stack.

The Haskell type:

type Config = (Int, [*], [*])

is "interesting", and it's certainly not the type you want. Since all values in this language are Vals, you instead want:

type Config = (Int, [Val], [Val])

which says that the configuration is a an integer program counter, a memory that's a list of Vals and a stack that's another list of Vals.

The instruction LOADI loads an "immediate" value into the stack, so its implementation is:

iexec (LOADI n) (pc, mem, stk) = (pc+1, mem, n:stk)

That is, it bumps the program counter, doesn't change the memory, and pushes the value n onto the stack.

The instruction LOAD fetches the value of a variable from memory and pushes it onto the stack. Assuming that type Val = Int, its implementation is:

iexec (LOAD i) (pc, mem, stk) = (pc+1, mem, n:stk) where n = mem !! i

It's the same as LOADI except the pushed value is looked up in memory with mem !! i.

Hopefully you can figure out the rest. If you need hints, an ML implementation of iexec is given on page 97 of the above book.

Note that your definition of ADD looks wrong, as that instruction isn't supposed to take an argument. It just adds the top two values of the stack together, presumably putting the answer in place of the original two values.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

"Interesting" indeed. The combination of Int with * might even be termed "unfortunate".
You can declare data family Hmph :: k, at which point '(Hmph, '[Int, Char], '[Bool, ()]) inhabits the Config kind, but that's probably not very useful.
@dfeuer you may be able to guess how effective my teaching of Haskell was haha
Thank you guys for your help. Turns out I wasn't too far off with my pseudo code and it was more the syntax and implementation I needed help with. Thank you again for the help.
@EthanGallagher, it was just a bit of fun to try to find a way to make "sense" of the *s that somehow crept into your type. Just being a bit silly, really, but * is traditionally the kind (type) of (lifted) types, so your type kind of makes sense as a kind. But Int is not normally inhabited as a kind. What to do? Well ... GHC actually allows data families to inhabit arbitrary kinds. Very weird, but occasionally useful. So the Hmph type actually has kind Int, and kind *, and so on.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.