Implementare il binding in un'espressione di calcolo personalizzata

Question

Sto cercando di imparare un po 'di più sulle espressioni di calcolo di F # implementando uno dei miei. Tuttavia, ho riscontrato un ostacolo in relazione al metodo Bind. Ecco quello che ho finora:

type public op<'a> = Op of ('a list -> 'a list) 

let inline (>>) (Op a) (Op b) = Op (a >> b) 

module Op = 
    let id = Op id 
    let bind (b : 'b -> op<'a>) (v : 'b) = b v 
    let call (Op f) = f 
    let push v = Op (fun t -> v :: t) 
    // .. snip .. 

type OpBuilder() = 
    member __.Bind (v, b) = Op.bind b v 
    member __.Yield (()) = Op.id 
    member __.Return (m) = Op.call m 

    [<CustomOperation("push")>] 
    member __.Push (m : op<'a>, v : 'a) = m >> Op.push v 
    // .. snip .. 

let op = new OpBuilder() 

Ora, la mia comprensione è che tutte le seguenti dovrebbe essere grosso modo equivalente:

// Use only the Op module methods 
let f1 = Op.call(Op.bind (fun x -> Op.push x) 1) 

// Use op builder with external closure 
let f2 = Op.call(let x = 2 in op { push x }) 

// Use op builder bind explicitly 
let f3 = op.Return(op.Bind(3, fun x -> op.Push(op.Yield(), x))) 

// Use op builder with let! binding 
let f4 = op { let! x = 4 in push x } 

I primi 3 sembrano funzionare bene, tuttavia, f4 dà questo errore:

This expression was expected to have type
  unit
but here has type
  int

ottengo lo stesso errore se uso let invece di let!. Tutto ciò che ho letto suggerisce che questo è il modo corretto di implementare Bind, ma a quanto pare mi manca qualcosa. Qualcuno può far notare cosa sto facendo male?

Answer 1

Se si sta tentando di implementare qualcosa come un DSL stack-based, le espressioni di calcolo non sono molto adatte. Si può perfettamente rappresentare questo solo con una lista di operazioni:

type Op = 
    | Push of int 
    | Dup 
    | Add 

let sample = 
    [ Push 2 
    Dup 
    Add ] 

E non ho potuto resistere a scrivere un semplice valutatore troppo:

let rec eval stack ops = 
    match ops, stack with 
    | (Push n)::ops, stack -> eval (n::stack) ops 
    | Dup::ops, s::stack -> eval (s::s::stack) ops 
    | Add::ops, s1::s2::stack -> eval ((s1+s2)::stack) ops 
    | [], stack -> stack 
    | _ -> failwith "Wrong arguments" 

eval [] sample 

espressioni di calcolo sono utili se si vuole dare un significato speciale per costrutti di linguaggio ordinario come il binding variabile let!, altri costrutti come for e try o la restituzione di un valore come acquisito da yield o return. Sebbene tu possa implementare alcune delle monadi Haskell, quelle non sono così utili in F # - quindi è un po 'complicato trovare un esempio di giocattolo utile con cui giocare.

Answer 2

Mentre una soluzione adeguata che consente di sviluppare la respirazione comporta l'utilizzo di una monade di stato a pieno titolo come discusso nei commenti, è comunque possibile ottenere un po 'di distanza dal proprio tipo di Op come definito. È necessario definire una sorta di generatore degenerato per esso - non è una monade, è essenzialmente un costruttore di "composizione di funzioni", ma è solo abbastanza espressivo per do!, quindi si ottiene una sintassi piacevole.

Quindi supponendo che si dispone di un tipo Op come questo:

type Op<'a> = 'a list -> 'a list 

Definite il vostro costruttore come questo - con un'unità di prendere posto di una "propria" valore scartare nella legatura e tornare - pensare a come il parte mancante da stato tipo monade:

type OpBuilder() = 
    member __.Bind (ma, f) = ma >> f() 
    member __.Return (_) = id 

let op = new OpBuilder() 

Poi le operazioni:

[<AutoOpen>] 
module Ops = 

    let push (x:'a) : Op<'a> = fun st -> x::st 

    let dup: Op<'a> = fun st -> 
     match st with 
     | h::t -> h::h::t 
     | [] -> [] 

    let add: Op<int> = fun st -> 
     match st with 
     | a::b::t -> (a+b)::t 
     | _ -> failwith "not enough operands" 

E pinna alleato:

let comp : Op<_> = 
    op { 
     do! push 2 
     do! dup 
     do! add 
    } 

comp []