Реализуйте привязку в пользовательском вычислительном выражении

Я пытаюсь узнать немного больше о вычислительных выражениях F #, реализуя одно из моих собственных. Однако я наткнулся на камень преткновения в отношении метода Bind. Вот что у меня есть на данный момент:

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()

Насколько я понимаю, все следующее должно быть примерно эквивалентно:

// 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 }

Первые 3 вроде работают нормально, однако f4 выдает эту ошибку:

Ожидалось, что это выражение будет иметь тип
unit
, но здесь есть тип
int

Я получаю ту же ошибку, если использую let вместо let!. Все, что я прочитал, предполагает, что это правильный способ реализации Bind, но, видимо, я чего-то упускаю. Кто-нибудь может указать, что я делаю не так?


.net f# computation-expression
person p.s.w.g    schedule 15.07.2016    source источник
comment
Что представляет собой этот рабочий процесс? Теперь я могу сказать вам, что типы вашего связывания и возврата не соответствуют норме, по крайней мере, в том, что касается монадического связывания и возврата, но я понятия не имею, на что я смотрю.   -  person scrwtp    schedule 16.07.2016
comment
@scrwtp Идея состоит в том, чтобы создать своего рода стек-ориентированный DSL. например op { push 2; dup; add } [] → [4].   -  person p.s.w.g    schedule 16.07.2016
comment
То, что вы называете bind, - это не привязка, а просто приложение-функция. Чтобы сделать это монадическим связыванием, второй параметр должен быть op<'b>, а не 'b.   -  person Fyodor Soikin    schedule 16.07.2016
comment
@FyodorSoikin Хорошо, точка взята. Конечной целью было реализовать что-то вроде let swap = op { let! x = pop; let! y = pop; push x; push y }, и я решил, что начать с постоянных значений (let! x = 4) будет проще. pop - это разновидность op<'a>, поскольку он изменяет стек, но я понятия не имел, как получить всплывающее значение в качестве переменной.   -  person p.s.w.g    schedule 16.07.2016
comment
@ p.s.w.g: То, к чему вы действительно хотите прийти, - это монада состояния - это та часть, которую вам не хватает для реализации pop - поскольку ее тип будет соответствовать 'a list -> 'a * 'a list, а одинокий 'a - это всплывающее значение. Я могу дать вам такой ответ, но не хочу портить вам удовольствие.   -  person scrwtp    schedule 16.07.2016
comment
@scrwtp прямо сейчас у меня Op.pop : ('a -> op<'a>) -> op<'a> (например, pop (fun x -> pop (fun y -> push x >> push y)), но я не уверен, как перевести это на OpBuilder. Я попробую ваше предложение.   -  person p.s.w.g    schedule 16.07.2016
comment
@ p.s.w.g: Я попробовал и пришел к тому, что работает. Это выглядит и ощущается как рабочий процесс с нарушенным состоянием, что интересно само по себе.   -  person scrwtp    schedule 16.07.2016
comment
См. stackoverflow.com/questions/ 14110532 / возможно?   -  person kvb    schedule 16.07.2016
comment
@kvb Я несколько раз пытался прочитать исходный код ILBuilder, но все еще трудно понять. Есть ли у вас какая-либо другая документация о логике и обосновании того, как вы ее спроектировали?   -  person p.s.w.g    schedule 16.07.2016
comment
@pswg - код ILBuilder (надеюсь) намного сложнее, чем вам нужно (например, он отслеживает не только содержимое стека, но и другие мелочи правил .NET IL, например, какие инструкции могут завершать метод, типы byref, и т.д.).   -  person kvb    schedule 16.07.2016
comment
@pswg - основная идея состоит в том, чтобы закодировать тип стека, содержащий значения типов 'a0, 'a1, ..., 'an, как общий тип T<'a0 * (a1 * (... * (an * unit)))> (где нет ничего особенного в unit или конструкторе двоичного кортежа * - вам просто нужно некоторый понятный способ кодирования пустого списка на уровне типа и преобразования одного элемента в другой список). Затем для каждого оператора, который вас интересует, вы даете ему подпись, которая учитывает правильную семантику (например, pop принимает T<'a * 'as> на T<'as>, dup принимает T<'a * 'as> на T<'a * ('a * 'as)> и т. Д.).   -  person kvb    schedule 16.07.2016
comment
@ p.s.w.g - Но под этим уровнем набора текста вы можете сделать так, чтобы ваши значения времени выполнения имели более простую структуру, такую ​​как предложенный Томасом список значений DU. У вас будет что-то вроде type T<'x> = T of Instruction list, где параметр типа 'x является фантомным типом, поскольку он не встречается в правой части определения. Тогда, пока ваши открытые операции имеют правильные подписи, все работает нормально. Надеюсь, что это поможет - это немного сложно, но, надеюсь, основные концепции не так уж и плохи.   -  person kvb    schedule 16.07.2016
comment
Возможно, вам будет интересно, что монаду стека можно рассматривать как особый случай более универсальной государственной монады.   -  person Jwosty    schedule 16.07.2016

Ответы (2)


arrow_upward
6
arrow_downward

Если вы пытаетесь реализовать что-то вроде DSL на основе стека, то вычислительные выражения вам не подходят. Вы можете прекрасно представить это просто списком операций:

 type Op = 
  | Push of int
  | Dup
  | Add

let sample = 
  [ Push 2
    Dup
    Add ]

И я не удержался и написал простой оценщик:

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

Выражения вычисления полезны, если вы хотите придать особое значение обычным языковым конструкциям, таким как связывание переменных let!, другие конструкции, такие как for и try, или возвращение значения, захваченного yield или return. Хотя вы можете реализовать некоторые из монад Haskell, они не так уж полезны в F #, поэтому немного сложно найти полезный игрушечный пример, с которым можно было бы поиграть.

person Tomas Petricek    schedule 16.07.2016
comment
Я не уверен, что согласен - вы можете использовать выражение вычисления, чтобы заставить вас никогда не вставлять пустой стек, например, если вы готовы терпеть некоторые шаткие типы. Вы можете сделать это без использования вычислительных выражений, составив вместо этого последовательность методов, но вы не можете добиться этого со списком значений DU. - person kvb; 16.07.2016
comment
Это похоже на то, с чего я начал, но пришел к выводу, что это слишком ограничивает (например, было бы сложно определять новые модули). Кроме того, построители вычислительных выражений всегда казались мне чем-то вроде колдовства, поэтому я хотел воспользоваться возможностью, чтобы немного демистифицировать их. - person p.s.w.g; 16.07.2016
comment
@ p.s.w.g Да, это имеет смысл - писать какой-нибудь построитель вычислений - это весело :) Все, что я пытаюсь сказать, это то, что легче начать с чего-то, что больше соответствует традиционным монадоподобным структурам. - person Tomas Petricek; 16.07.2016
comment
@kvb Я полагаю, что моя формулировка была слишком сильной - вы, безусловно, можете сделать это с помощью конструктора, и это может дать вам некоторые приятные преимущества (с шаткими типами :-)). Но я думаю о построителе как о последнем шаге, который вы можете попытаться добавить, чтобы увидеть, делает ли его синтаксис лучше, как только вы выясните, как именно работает композиция в вашем домене (без построителей вычислений). - person Tomas Petricek; 16.07.2016

arrow_upward
6
arrow_downward

Хотя правильное решение, которое дает вам передышку для роста, включает использование полноценной монады состояния, как обсуждается в комментариях, вы все равно можете получить некоторую отдачу от своего типа операции, как определено. Вам нужно определить для него своего рода вырожденный построитель - это не монада, это, по сути, построитель "композиции функций", но он достаточно выразителен для do!, так что вы получите красивый синтаксис.

Итак, если у вас есть такой тип операции:

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

Вы определяете свой построитель следующим образом - с единицей, занимающей "правильное" развернутое значение в связывании и возврате - думайте об этом как о части, отсутствующей в типе монады состояния:

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

let op = new OpBuilder()

Затем операции:

[<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"

И наконец:

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

comp []
person scrwtp    schedule 15.07.2016
comment
Спасибо, мне придется попробовать это еще немного, когда я вернусь за свой компьютер. Я понял, что одна проблема, с которой я столкнулся, заключалась в том, что Return должен был быть Run в моем конструкторе (поэтому мне понадобилось call в f2). - person p.s.w.g; 16.07.2016