Seminar05.fsx

// -----------------------------------------------------------------------------
// КЛАССЫ

// Дисклеймер: мы рассмотрим минимальный синтаксис, который нам понадобится в F#
// для работы в рамках нашего курса. Поэтому текст, который написан дальше,
// некорректным полностью корректным. Например, некоторые фразы вида "есть ..."
// на самом деле должны быть записаны как "есть ..., если не ... или ..."

// Классы отличаются от алгебраических типов данных тем, что у него есть
// конструктор, методы и поля

// В скобках аргументы конструктора. Скобки обязательны, список может быть пуст
type User (name) =
    // Внутри методы и поля
    member this.SayHi () = printfn "Hi, I'm %s!" this.Name
    member this.Name = name
    // Слово this - это идентификатор текущего объекта класса (нужен, когда
    // объект взаимодействует с другими объектами того же типа).
    // При определении класса это может быть любое слово, в том числе даже
    // разные для разных методов и полей

// Создадим объект класса User
let elfo = User "Elfo"
elfo.SayHi ()

// Вот мы и закончили изучать классы :)

// -----------------------------------------------------------------------------
// ВЫЧИСЛИТЕЛЬНЫЕ ВЫРАЖЕНИЯ

// Вычисления могут быть разными. Чаще всего встречается последовательное
// однопоточное исполнение, это самый простой вариант. Однако есть и более
// сложные вычисления: недетерминированные, асинхронные, вычисления с эффектами

// В чистом функциональном программировании сложнее реализовывать алгоритмов,
// работающих пошагово. Виной тому модель подстановки, которая говорит, что
// значение выражение - это результат редукций выражений, то есть многократного
// переписывания. Более того, если вычисление происходит и в ленивом подходе, то
// порядок вычисления часто сильно зависит от внутреннего устройства функции,
// а не от того, что мы в коде записали раньше, а что позже (это критично,
// например, для вывода на экран)

// Таким образом, внутри функционального языка все равно в каком-то виде
// нужно поддерживать императивность. В F# это позволяют сделать вычислительные
// выражения, то есть выражения, вычисление которых будет происходит в некотором
// контексте, который может меняться при исполнении

// Например, для недетерминированных вычислений это может быть время или
// какое-то состояние рандомайзера, для ввода-вывода - консоль (это все,
// конечно, не очень строго)

// В коде для реализации вычислительного выражения нужно иметь два типа:
// * тип выражения - если выражение имеет такой тип, то это
//   означает, что его значение контекстно-зависимое. Это может быть в принципе
//   любой тип, как правило, полиморфный
// * тип вычисления - это класс, реализующий взаимодействие с контекстом

(*

// Какой-то тип выражения
type 't ExpressionType = ...

// Какой-то тип вычисления
type ComputationType () =
    member ...
    ...
    
// Для записи вычислительного выражения нужно создать объект, в котором
// будут производится вычисления
let builderExpr : ComputationType = ComputationType ()

// Дальше нам доступен такой синтаксис
let computationExpression : int ExpressionType = builderExpr {
    ...
    // Здесь пишется само контекстно-зависимое вычисление
}

*)

// Внутри блока builderExpr в зависимости от методов, определенных в классе,
// можно использовать ключевые слова, недоступные для обычных выражений.

// { let! ... }
// { do! ... }
// { yield ... }
// { yield! ... }
// { return ... }
// { return! ... }
// { match! ... }

// Каждое из них - синтаксический сахар, и он разворачивается в цепочку вызовов
// методов класса вычисления. Если какой-то из методов не реализован, то и
// ключевое слово недоступно. Смысл каждого из них зависит от типа вычисления

// В F# есть всего три встроенных типа вычислительных выражений - это
// seq (последовательные вычисления), async (асинхронные вычисления) и query
// (не рассматривается в курсе)

// -----------------------------------------------------------------------------
// ПОСЛЕДОВАТЕЛЬНЫЕ ВЫЧИСЛЕНИЯ

// Мы уже знакомы с одним типом вычислительных выражений - это последовательные
// вычисления

let rec fibs : int seq = seq {
    yield 0
    yield 1
    yield! Seq.zip fibs (Seq.tail fibs) |> Seq.map (function (a, b) -> a + b)
}

// Здесь seq - объект типа вычисления и имя типа выражения (помним, что имена
// типов и контант живут в разных пространствах имен)

// -----------------------------------------------------------------------------
// РЕАЛИЗАЦИЯ ПОСЛЕДОВАТЕЛЬНЫХ ВЫЧИСЛЕНИЙ

// Вспомним наш тип Stream из третьего семинара и реализуем для него те же
// возможности, что и для встроенных последовательностей

type 't Cell =
| NilCell
| ConsCell of 't * 't Stream 
and 't Stream = Lazy<'t Cell>

let ( |Nil|Cons| ) (xs : 't Stream) =
    match xs.Force () with
    | NilCell -> Nil
    | ConsCell (x, xs) -> Cons (x, xs) 

let rec toList = function
| Nil -> []
| Cons (x, xs) -> x :: toList xs

let rec map f xs =
    lazy match xs with
         | Nil -> NilCell
         | Cons (x, xs) -> ConsCell (f x, map f xs)

let rec zip xs ys =
    lazy match xs, ys with
         | Cons (x, xs'), Cons (y, ys') -> ConsCell ((x, y), zip xs' ys')
         | _ -> NilCell

let rec tail xs =
    lazy match xs with
         | Nil -> NilCell
         | Cons (_, xs) -> xs.Force ()

let rec take n xs =
    lazy match n, xs with
         | 0, _ -> NilCell
         | _, Nil -> NilCell
         | _, Cons (x, xs') -> ConsCell (x, take (n - 1) xs')

type SequenceBuilder () =
    // 't -> 't Stream для yield
    member this.Yield x =
        lazy ConsCell (x, lazy NilCell) : 't Stream
    
    // 't Stream -> 't Stream для yield!
    member this.YieldFrom xs =
        xs : 't Stream
    
    // 't Stream * 't Stream -> 't Stream
    member this.Combine (streams : 't Stream * 't Stream ) =
        lazy match fst streams with
             | Nil -> (snd streams).Force()
             | Cons (x, xs) -> ConsCell (x, this.Combine (xs, snd streams))
    
    // (unit -> 't Stream) -> 't Stream
    member this.Delay (getStream : unit -> 't Stream) =
        lazy ((getStream ()).Force())

let sequence = SequenceBuilder ()

let rec fibs'' : int Stream = sequence {
    yield 0
    yield 1
    yield! fibs'' |> tail |> zip fibs'' |> map (function (a, b) -> a + b)
}

printfn "%A" (fibs'' |> take 10 |> toList)

// -----------------------------------------------------------------------------
// АСИНХРОННОСТЬ

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

// Для написания асинхронных вычислений используется строитель async. Он
// сопоставляет выражению типа 't асинхронное вычисление типа 't Async, которое
// затем может объединяться в более сложные конструкции и вычисляться
// параллельно и независимо

let asyncFour = async { return 2 + 2 } // Новое ключевое слово - return

// Объявление асинхронных выражений не запускает сами вычисления!

let asyncPrint = async { return printfn "print" }

// Функции для работы с асинхронными вычислениями живут в модуле Async

// RunSynchronously : 't Async -> 't - функция запускает вычисление в фоновом
// потоке, дожидается его окончания и возвращает результат
printfn "%A" (Async.RunSynchronously asyncFour)
Async.RunSynchronously asyncPrint

// Parallel : 't Async seq -> 't [] Async - преобразует несколько асинхронных
// вычислений в одно, которое завершается после завершения каждого из них
// и возвращает массив результатов (тип обозначается 't []). Порядок сохраняется
let asyncPrints: unit [] Async =
    [ 1 .. 10 ]
    |> List.map (fun i -> async { return printfn "%A" i })
    |> Async.Parallel
    
// Возвращается именно массив, а не список, потому что вычисления
// происходят не по порядку, поэтому для эффективности нужна мутабельная
// структура данных, где доступ по индексу за константное время

Async.RunSynchronously asyncPrints |> ignore // ignore игнорирует аргумент

// Например, так можно реализовать функцию map, работающую параллельно

let parallelMap f xs =
    xs
    |> Seq.map (fun x -> async { return f x } )
    |> Async.Parallel
    |> Async.RunSynchronously
    |> Seq.ofArray
    
parallelMap (( + ) 1) [ 1 .. 10 ] |> Seq.iter (printfn "%A")

// При выполнении задачи используется пул потоков, так что накладные расходы
// на создание и переключение потоков в рамках разумного

// Awake : 't Async -> unit - функция запускает вычисление в пуле потоков,
// не дожидаясь завершения вычисления (даже если основной поток завершает
// работу)
Async.Start (async {
    System.Threading.Thread.Sleep 10000
    return printfn "Zzz..."
})
printfn "Awake"

// Асинхронные вычисления используются для обработки файлов

// -----------------------------------------------------------------------------
// ИНВЕРСИЯ УПРАВЛЕНИЯ

// При написании асинхронного кода, конечно же, не хочется постоянно
// использовать Async.RunSynchronously, хотелось бы запустить вычисление в фоне,
// в это время самим делать что-то полезное, а для асинхронного вычисления
// поставить callback, который будет вызван по завершении вычисления

// Если это сделать, то код будет представлять собой несколько неявно связанных
// функций

// На самом деле мы уже видели кол-беки, когда пытались реализовать хвостовую
// рекурсию с помощью продолжений, ведь это тот же кол-бек

// Рассмотрим, как простой императивный код можно переписать в вычисления с
// продолжениями. Напишем заглушки, чтобы код выглядел как что-то содержательное
let syncRead _ = ()
let processFile () = ()
let syncWrite _ _ = ()

// Синхронная обработка изображения
let image = syncRead "source.jpg"
let result = processFile image
syncWrite "destination.jpg" image
printfn "Done"

// Асинхронный вариант использованием продолжений
let contRead _ _  = ()
let contWrite _ _ _ = ()

// Код выглядит несколько сложнее для восприятия, но работает
contRead "source.jpg" (fun image ->
    let result = processFile image
    contWrite "destination.jpg" result (fun () ->
        printfn "Done"))

// Наконец, реализуем асинхронный вариант с ипользованием вычислительных
// выражений
let asyncRead _ = async { return () }
let asyncWrite _ _ = async { return () }

// Код снова становится императивным, но теперь работает асинхронно. Мы этого
// и хотели, когда говорили, что вычислительные выражения позволяют реализовать
// императивные вещи внутри функциональных языков
async {
    let! image = asyncRead "source.jpg"
    let result = processFile image
    do! asyncWrite "destination.jpg" result
    do printfn "Done"
    return result
} |> ignore

// Если раскрыть синтаксический сахар, то получится примерно следующее
async.Delay (fun () ->
    async.Bind (asyncRead "source.jpg", (fun image ->
        let result = processFile image
        async.Bind (asyncWrite "destination.jpg" result, (fun () ->
            printfn "Done"
            async.Return result))))) |> ignore

// Далее такие асинхронные операции могут объединяться вместе в параллельно
// выполняемые блоки, и в момент асинхронного выполнения ввода-вывода в одном
// потоке будут выполняться вычислительные операции в другом

// -----------------------------------------------------------------------------
// РЕАЛИЗАЦИЯ АСИНХРОННЫХ ВЫЧИСЛЕНИЙ

// Мы не научимся запускать асинхронные вычисления асинхронно, но реализовать
// все методы для такого вычисления, чтобы работал синтаксис выше, сможем

// Представим асинхронное вычисление как ленивое вычисление. Оно также еще
// не вычислено в момент создания. Отличие в том, что исполняется в том же
// потоке и в кешировании результата
type 't Async' = Async' of 't Lazy

type Async'Builder () =
    member this.Delay getAsync =
        Async' (lazy match getAsync () with
                     | Async' comp -> comp.Force())
    
    member this.Bind (compAndCont : 'a Async' * ('a -> 'b Async')) =
        Async' (lazy match fst compAndCont with
                     | Async' comp ->
                         match snd compAndCont (comp.Force ()) with
                         | Async' comp' -> comp'.Force())
  
    member this.Return x = Async' (lazy x)
    
let async' = Async'Builder ()

let async'Read _ = Async' (lazy ())
let async'Write _ _ = Async' (lazy ())

let runAsync' = function
| Async' comp -> comp.Force ()

let async'Process = async' {
    let! image = async'Read "source.jpg"
    let result = processFile image
    do! async'Write "destination.jpg" result
    do printfn "Done"
    return result
}

runAsync' async'Process

// В чем вообще смысл слов let!, do, do!, return, return!, yield, yield!, а
// также match!

// * let name : 't = expr : 't - связывает обычное выражение с именем
// * let! name : 't = compExpr : 't Comp - связывает значение вычислительного
//   выражения с именем, это имя использует поток как значение обычного
//   выражения
// * do (expr : unit) - вычислить обычное выражение типа unit, при этом
//   срабатывают его побочные эффекты (в этом смысл unit'ов)
// * do! (compExpr : unit Comp) - вычислить вычислительное выражение, при этом
//   при этом отрабатывают его побочные эффекты
// * return (expr : 't) - завершить описание вычислительного выражения, оно в
//   итоге вернет значение expr, обернутое в тип результата вычилительного
//   выражения
// * return! (compExpr : 't Comp) - вернуть тот же результат, что и
//   вычислительное выражение compExpr
// * yield (expr : 't) - выдать наружу значение expr, но не завершать
//   вычисление
// * yield! (compExpr : 't Comp) - выдать наружу результаты, выдываемые
//   вычислительным выражением compExpr, при этом не завершая вычисление
// * match! (compExpr : 't Comp) with ... - синтаксический сахар для записи
//   let! x = compExpr
//   match x with ...