CODEWITHSUNDEEP
compiler-constructionf#functional-programming
user901037
user901037

Reputation:

F# - Mutable context when applying sequence transformation

Apologies for the strange title of the post, I'm not sure what the best way to describe it is.

The general problem:

Do a sequential application of Seq.map (or similar function), except for each item in the list, also pass in a "context". Each iteration can modify this "context", and the updated version should be passed into the next item in the list.

The specific problem:

I'm creating a compiler in F#. The step that I am currently on is transforming stack-based IL to register-based IL. I was thinking I could "walk" the stack-based IL and carry along the current "eval stack" (similar to .NET's eval stack). Each stack IL opcode, would, obviously, mutate the stack (example: the "add" opcode pops two items off the stack and pushes the result). This updated stack would be passed into the next opcode's emit cycle.

Note that I am very new to functional programming (I learned of it a week ago), coming from a C# background, and my primary question is "what is the 'functional' way to do this?"

Here's my best guess of what a 'functional' approach to this would be (psudocode). I dislike the tuple return value of "transformStackToRegisterIL", is it required if I want to keep with the standard of immutable values? Also, I'm worried about a stack overflow on excessively long blocks of IL, is this a valid concern of mine?

let rec translate evalStack inputIl =
    match inputIl with
        | singleOpcode :: tail ->
            let (transformed, newEvalStack) = transformStackToRegisterIL evalStack singleOpcode
            transformed :: translate newEvalStack tail
        | [] -> []

Edit: Is List.scan a built-in function of what I want? (it seems similar, but not exactly right... but it might be the correct one, I'm not sure)

Upvotes: 2

Views: 177

Answers (3)

Tomas Petricek
Tomas Petricek

Reputation: 243051

I'll try to explain this using a very basic example that is somewhat motivated by your question (but does not implement anything realistic).

So, let's assume that we have IL instruction Push that pushes a named variable on the stack and Add that adds two last items on the stack (to keep it simple, let's say that it just prints the result to the console). The target is a registry language with Nop and Add that takes two variable names, adds them (and prints the result to the console):

type IL = 
  | Push of string
  | Add

type Reg =
  | Add of string * string
  | Nop

let input = [ IL.Push "a"; IL.Push "a"; IL.Push "b"; IL.Add; IL.Push "c"; IL.Add ]

The input should be transformed to Reg.Add("b", "a") and Reg.Add("c", "a") and some Nops. The transformation function takes the current stack and a single instruction:

let transform stack = function
  | IL.Push var -> Reg.Nop, var::stack
  | IL.Add -> Add(stack.Head, stack.Tail.Head), stack.Tail.Tail

To transform the entire list, we can use List.fold which keeps current "state". It calls a provided function with current state and a single input instruction and the provided function must return a new state. Here, the "state" is the stack, but also a list of register machine instructions that we are producing:

let endStack, regsReversed =
  input |> Seq.fold (fun (stack, regs) il ->
      // Transform current IL instruction, given current 'stack'
      let reg, newStack = transform stack il
      // Add new registry instruction to 'regs' and return new stack
      (newStack, reg::regs) ) ([], [])

The same can be done using recursion. The structure is very similar, except that we keep the state as parameter and change it by making a recursive call:

let rec compile (stack, regs) = function
  | [] -> (stack, regs)
  | il::ils -> 
      // Transform current IL instruction, given current 'stack'
      let reg, newStack = transform stack il
      // Add new registry instruction to 'regs' and return new stack
      compile (newStack, reg::regs) ils

let endStack, regs = compile ([], []) input

Now we can check that the stack was empty at the end and print the registry machine instructions (Note that we append them to the front, so we need to reverse the result):

if endStack <> [] then printfn "Stack is not empty!"
regs |> List.rev

As Jack mentioned - you can also use more advanced ways of handling this like computation expressions (state). I think writing serious compilers is actually a place where it makes sense to use them, but if you're learning F#, it is easier to start with basic concepts like folds and recursion.

Upvotes: 3

Jack P.
Jack P.

Reputation: 11525

Passing a "context" around and mutating it -- you're talking about the state workflow; there, the state would be your eval stack.

If you do use the state workflow (and I'd recommend you do), you can use the State.List.map function from ExtCore -- it maps one list to another, passing a context value from one element to the next while processing the list.

Don't worry about overflowing the stack with long IL blocks (i.e., large method bodies) -- stack overflows are really only a concern once you have really deep call stacks.

Upvotes: 3

N_A
N_A

Reputation: 19897

You can do that with List.reduce or with a custom computation expression (similar to how async works). I would probably use List.reduce unless you were going to reuse it frequently or it didn't fix List.reduce for some other reason.

Upvotes: 0

Related Questions