расширяющие функции в F #

Question

в следующем коде функция executeProg выполняет список инструкций программы. он выполняет программу с "PU SH ax, POP bx ..et c".

//Execute a program as a list of operations. Note how pc is incremented
//so any jump instruction must be written carefully.
let mutable executeProg = fun (program:operation list) ->
  pc <- 0
  fault <- false
  while not(fault) && pc<program.Length do
    let instruction = program.[pc];
    execute instruction
    pc <- pc+1
  // end of while by indentation
  if not(fault) then printfn "top of stack holds value %d" (RAM.[sp-1]);

я пытаюсь сделать следующее: изменить executeProg так, чтобы он выполнял следующие действия:

push ax
pop bx      --> replace with single instruction mov ax bx 

push ax
pop ax      --> eliminate altogether

mov ax bx
mov bx ax   -->   mov ax bx

Мой вопрос заключается в том, как реализовать новый модуль executeProg без изменить оригинал? мой код выглядит следующим образом:

let rec optimize = fun newProgram program ->
    let mutable newProgram = newProgram
    match program with
    | (PUSH(Reg(a)):: POP(Reg(b)) :: r) when String.Equals(a,b) ->
        optimize newProgram r
    | (PUSH(Reg(a)):: POP(Reg(b)) :: r) ->
        newProgram <- newProgram @ [MOV(Reg(a),Reg(b))]
        optimize newProgram r
    | (PUSH(Imm(a)):: POP(Imm(x)):: r) when a = x ->
        optimize newProgram r 
    | (MOV(Reg(a), Reg(b)) :: MOV(Reg(b), Reg(a)) :: r) ->
        newProgram <- newProgram @ [MOV(Reg(a),Reg(b))]
        optimize newProgram r
    | (a::r) ->
        newProgram <- newProgram @ [a]
        optimize newProgram r
    | [] -> newProgram

Я новичок в языке F # и мне интересно, правильный ли мой синтаксис. Буду благодарен за любую помощь. Спасибо.

Answer 1

Я думаю, что вам не нужно иметь изменяемую функцию. Возможно, вы можете изменить дизайн, чтобы использовать неизменяемые составные структуры, которые позволят вам добавить новые функциональные возможности в ваше решение.

Я немного поиграл с проблемой, и вот что я получил.

Заявить типы, которые вы будете использовать в программе:

type Register = 
    | AX 
    | BX

type Operand =
    | Register of Register
    | Int of int


type Command = 
| MOV of Register * Operand
| PUSH of Operand
| POP of Operand

type FnBinaryOp = Register -> Operand -> Command
type FnUnaryOp = Operand -> Command

type Program = Command list

//two helper functions to save some typing
let i n = Int n
let r n = Register n

//helper functions to clarify the declaration syntax
let mov:FnBinaryOp = 
    fun reg op -> MOV (reg, op)

let push: FnUnaryOp = fun op -> PUSH (op)

let pop: FnUnaryOp = fun op -> POP (op)

Реализуйте свой метод оптимизации - он возвращает измененный список команд. Вот где недостатки кода исправляются.

///optimize the program - remove cancelling stack commands, simplify MOV commands
let optimize (program:Program) = 
   let rec recOptimize stack prog = 
       match prog with
       | PUSH (Register r1)::POP (Register r2)::xs when r1 = r2 -> //push ax; pop ax => nop
           xs |> recOptimize stack
       | PUSH (Register r1)::POP (Register r2)::xs when r1 <> r2 -> //push ax; pop bx => move ax bx
           xs |> recOptimize (MOV(r1, Register(r2))::stack)
       | PUSH (Int i1)::POP (Int i2)::xs when i1 = i2 -> //push 3; pop 3 => nop
           xs |> recOptimize stack
       | ((MOV (r1, Register r2 )) as op1)::((MOV (r3, Register r4 )) as op2)::xs when r1 = r4 && r2 = r3 -> //move ax bx; move bx ax => move ax bx
           xs |> recOptimize (op1::stack)
       | ((MOV (r1, Register r2 )) as op1)::((MOV (r3, Register r4 )) as op2)::xs when r1 = r3 && r2 = r4 -> //move ax bx; move ax bx => move ax bx
           xs |> recOptimize (op1::stack)
       | op::xs -> //all other cases - pass through
           xs |> recOptimize (op::stack)
       | [] -> stack

   program 
   |> recOptimize []

Реализуйте фактическое выполнение вашей программы (здесь не реализовано)

let runProgram (program:Program) = 
    let rec run stack prog =
        []
    program |> run []

И вот как вы можете вызвать это:

let program:Program = [
    mov AX (r BX)
    push (r BX)
    pop (r BX)
    mov AX (r BX)
    ]

program 
|> optimize 
|> runProgram

Если вам нужно добавить новую функциональность на шаг оптимизации, вы можете просто заменить элемент оптимизации составного вызова. Вы можете выполнить несколько проходов оптимизации, чтобы охватить случаи, когда определенные операции становятся «парными», и вы также хотите оптимизировать их. program |> optimize |> optimize |> runProgram

Вот несколько тестов:

[<Fact>]
let ``push 42; pop 42 => nop`` () =
    let program:Program = [
        push (i 42)
        pop (i 42)
        ]
    let optimized = program |> optimize

    //should be reduced to empty list
    Assert.Empty(optimized)

[<Fact>]
let ``push ax; pop ax => nop`` () =
    let program:Program = [
        push (r AX)
        pop (r AX)
        ]
    let optimized = program |> optimize

    //should be reduced to empty list
    Assert.Empty(optimized)

[<Fact>]
let ``push ax; pop bx => move ax bx`` () =
    let program:Program = [
        push (r AX)
        pop (r BX)
        ]
    let optimized = program |> optimize

    //should be reduced to a single element list mov ax bx
    let expected = MOV( AX, (r BX))
    let op = optimized.Head
    Assert.Equal(1, optimized.Length)
    Assert.Equal(expected, op)

[<Fact>]
let ``move ax bx; move bx ax => move ax bx`` () =
    let program:Program = [
        mov AX (r BX)
        mov BX (r AX)
        ]
    let optimized = program |> optimize

    //should be reduced to a single element list mov ax bx
    let expected = MOV( AX, (r BX))
    let op = optimized.Head
    Assert.Equal(1, optimized.Length)
    Assert.Equal(expected, op)

[<Fact>]
let ``run optimize on program`` () =
    let program:Program = [
        mov AX (r BX)
        push (r BX)
        pop (r BX)
        mov AX (r BX)
        ]
    let optimized = program 
                    |> optimize
                    |> optimize
                    |> optimize

    //should be reduced to a single element list mov ax bx
    let expected = MOV( AX, (r BX))
    let op = optimized.Head
    Assert.Equal(1, optimized.Length)
    Assert.Equal(expected, op)