shwars Apr 11 2019 at 10:00

Функциональное мышление. Часть 11: Финал

11 min

9.5K

Microsoft corporate blogProgramming*.NET*Mathematics*F#*

Translation

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

Хочу отдельно поблагодарить @kleidemos. Именно он выступил главным переводчиком и менеджером всей серии статей. Спасибо!

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

Схема простого вычисления на стеке:

Прежде чем проектировать подобную систему, следует порассуждать над тем, как она будет использоваться. Следуя Forth-подобному синтаксису, дадим каждому действию соответствующую метку, чтобы в приведенном выше примере можно было написать нечто вроде:

EMPTY ONE THREE ADD TWO MUL SHOW

Возможно, точно такой синтаксис получить не удастся, но попробуем приблизиться к этому как можно ближе.

Тип данных стека

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

type Stack = float list

Но лучше обернуть его в single case union type, чтобы сделать тип более наглядным, например так:

type Stack = StackContents of float list

Почему лучше делать именно так, можно прочитать здесь.

Теперь создадим новый стек, используя StackContents в качестве конструктора:

let newStack = StackContents [1.0;2.0;3.0]

Для извлечения содержимого из существующего Stack-а используется сопоставление с образцом StackContents:

let (StackContents contents) = newStack 

// Значение "contents" будет равно
// float list = [1.0; 2.0; 3.0]

Функция Push

Далее нам потребуется способ помещать числа в этот стек. Для этого достаточно добавить новое значение в начало списка, используя "::".

Пример функции:

let push x aStack =   
    let (StackContents contents) = aStack
    let newContents = x::contents
    StackContents newContents

Эта функция имеет ряд особенностей, которые стоит обсудить.

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

Input: Stack и еще какой-либо параметр
Output: новый Stack

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

Наконец, функцию можно сделать более краткой с помощью сопоставления с образцом в самом параметре функции, вместо let в теле функции.

Переписанная версия:

let push x (StackContents contents) =   
    StackContents (x::contents)

Намного лучше!

Между прочим, посмотрите на её изящную сигнатуру:

val push : float -> Stack -> Stack

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

Так или иначе, проверим:

let emptyStack = StackContents []
let stackWith1 = push 1.0 emptyStack 
let stackWith2 = push 2.0 stackWith1

Прекрасно работает!

Надстрока вершины стека при помощи "push"

С помощью этой простой функции можно легко определить операцию, помещающую определенное число в стек.

let ONE stack = push 1.0 stack
let TWO stack = push 2.0 stack

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

let ONE = push 1.0
let TWO = push 2.0
let THREE = push 3.0
let FOUR = push 4.0
let FIVE = push 5.0

Теперь очевидно, что если бы функция pushимела другой порядок параметров, stack пришлось бы упоминать дважды.

Стоит также определить функцию, создающую пустой стек:

let EMPTY = StackContents []

Проверим полученные функции:

let stackWith1 = ONE EMPTY 
let stackWith2 = TWO stackWith1
let stackWith3  = THREE stackWith2

Эти промежуточные стеки раздражают? Можно ли избавиться от них? Конечно! Заметьте, что функции ONE, TWO и THREE имеют одинаковую сигнатуру:

Stack -> Stack

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

let result123 = EMPTY |> ONE |> TWO |> THREE 
let result312 = EMPTY |> THREE |> ONE |> TWO

Выталкивание из стека

С добавлением в стек разобрались, но что насчет функции pop?

При извлечении из стека, очевидно, необходимо вернуть вершину стека, но только ли ее?

В объектно-ориентированном стиле ответом будет "да". Но в случае ООП, стек был бы изменен за кулисами, так что верхний элемент был бы удален.

Однако в функциональном стиле стек неизменяем. Есть только один способ удалить верхний элемент — создать новый стек без этого элемента. Для того, чтобы вызывающий объект имел доступ к новому уменьшенному стеку, его необходимо вернуть вместе с верхним элементом.

Другими словами, функция pop должна возвращать два значения, верхний элемент и новый стек. Простейший способ сделать это в F# — это просто использовать кортеж.

Реализация:

/// Вытолкнуть значение из стека
/// и вернуть его и новый стек в виде пары
let pop (StackContents contents) = 
    match contents with 
    | top::rest -> 
        let newStack = StackContents rest
        (top,newStack)

Полученная функция также очень проста.

Как и прежде, contents извлекается прямо из параметра.

Затем с помощью выражения match..with проверяется содержимое contents.

Потом верхний элемент отделяется от остальной части списка, создается новый стек на основе оставшихся элементов, и наконец все это возвращается парой в виде кортежа.

Попробуйте запустить этот код и посмотрите, что произойдёт. Вы получите ошибку компиляции!
Компилятор обнаружил случай, который не был отработан — что произойдет, если стек пуст?

Надо решить, как это обрабатывать.

Вариант 1: Вернуть специальное состояние "Success" или "Error", как это делалось в посте из серии "why use F#?".
Вариант 2: Выбросить исключение.

Обычно я предпочитаю использовать специальное состояние для ошибки, но в данном конкретном случае я предпочел выбросить исключение. Исправленная версия pop с обработкой пустого случая:

let pop (StackContents contents) = 
    match contents with 
    | top::rest -> 
        let newStack = StackContents rest
        (top,newStack)
    | [] -> 
        failwith "Stack underflow"

Проверим:

let initialStack = EMPTY  |> ONE |> TWO 
let popped1, poppedStack = pop initialStack
let popped2, poppedStack2 = pop poppedStack

и тест на исключение:

let _ = pop EMPTY

Арифметические функции

Теперь когда добавление и удаление на месте, можно начать работу с функциями "add" и "multiply":

let ADD stack =
   let x,s = pop stack  //извлечь вершину стека
   let y,s2 = pop s     //извлечь вершину полученного стека
   let result = x + y   //вычислить арифметическое выражение
   push result s2       //добавить его обратно в стек

let MUL stack = 
   let x,s = pop stack  //извлечь вершину стека
   let y,s2 = pop s     //извлечь вершину полученного стека
   let result = x * y   //вычислить арифметическое выражение 
   push result s2       //добавить его обратно в стек

Проверка в интерактивном режиме:

let add1and2 = EMPTY |> ONE |> TWO |> ADD
let add2and3 = EMPTY |> TWO |> THREE |> ADD
let mult2and3 = EMPTY |> TWO |> THREE |> MUL

Работает!

Время рефакторинга...

Очевидно, что в этих двух функциях значительное количество кода дублируется. Как мы можем это исправить?

Обе функции извлекают два значения из стека, применяют к ним некую бинарную функцию, после чего помещают результат обратно в стек. Можно вывести общий код в функцию "binary", которая принимает математическую функцию с двумя параметрами:

let binary mathFn stack = 
    // вытолкнуть вершину стека
    let y,stack' = pop stack    
    // снова вытолкнуть вершину стека
    let x,stack'' = pop stack'  
    // вычислить
    let z = mathFn x y
    // положить результат обратно в стек
    push z stack''

Обратите внимание, что в этой реализации разные версии "одного" объекта помечены различным количеством штрихов-кавычек. Это сделано потому, что числовые суффиксы могут легко привести к путанице.

Вопрос: почему параметры имеют именно такой порядок, вместо mathFn идущего после stack?

Теперь, когда есть функция binary, можно гораздо проще определить ADD и другие функции:

Первая попытка реализации ADD с помощью binary:

let ADD aStack = binary (fun x y -> x + y) aStack

Но можно избавиться от лямбды, т.к. она представляет точное определение встроенной функции +:

let ADD aStack = binary (+) aStack

Опять же, можно использовать частичное применение, чтобы скрыть параметр "стек". Итоговое определение:

let ADD = binary (+)

Определение других математических функций:

let SUB = binary (-)
let MUL = binary (*)
let DIV = binary (../)

Попробуйте в интерактивном режиме:

let div2by3 = EMPTY |> THREE|> TWO |> DIV
let sub2from5 = EMPTY  |> TWO |> FIVE |> SUB
let add1and2thenSub3 = EMPTY |> ONE |> TWO |> ADD |> THREE |> SUB

Схожим образом можно создать вспомогательную функцию для унарных операций

let unary f stack = 
    let x,stack' = pop stack
    push (f x) stack'

И определить несколько унарных функций:

let NEG = unary (fun x -> -x)
let SQUARE = unary (fun x -> x * x)

Интерактивный режим:

let neg3 = EMPTY  |> THREE|> NEG
let square2 = EMPTY  |> TWO |> SQUARE

Putting it all together | Собираем всё вместе

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

let SHOW stack = 
    let x,_ = pop stack
    printfn "The answer is %f" x
    stack  // продолжаем работать с тем же стеком

Обратите внимание, что в данном случае новая версия стека, полученная через pop, игнорируется. Конечным же результатом объявляется исходный стек, как будто он никогда не изменялся.

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

EMPTY |> ONE |> THREE |> ADD |> TWO |> MUL |> SHOW

Идём дальше

Это весело, но что еще можно сделать?

Можно определить несколько дополнительных функций:

/// Дублирование значения на вершине стека
let DUP stack = 
    // получение вершины стека
    let x,_ = pop stack  
    // добавление её обратно в стек
    push x stack 

/// Обменять местами два верхних значения
let SWAP stack = 
    let x,s = pop stack  
    let y,s' = pop s
    push y (push x s')   

/// Создать начальную точку
let START  = EMPTY

С помощью этих дополнительных функций можно написать несколько изящных примеров:

START
    |> ONE |> TWO |> SHOW

START
    |> ONE |> TWO |> ADD |> SHOW 
    |> THREE |> ADD |> SHOW 

START
    |> THREE |> DUP |> DUP |> MUL |> MUL // 27

START
    |> ONE |> TWO |> ADD |> SHOW  // 3
    |> THREE |> MUL |> SHOW       // 9
    |> TWO |> SWAP |> DIV |> SHOW // 9 div 2 = 4.5

Использование композиции вместо конвейеризации

Но и это ещё не всё. На самом деле, существует другой интересный способ представления этих функций.

Как отмечалось ранее, все они имеют одинаковую сигнатуру:

Stack -> Stack

Поскольку ввод и вывод имеют одинаковые типы, эти функции могут быть скомпонованы еще и при помощи оператора композиции >>, а не только посредством конвейерных операторов.

Несколько примеров:

// определение новой функции
let ONE_TWO_ADD = 
    ONE >> TWO >> ADD 

START |> ONE_TWO_ADD |> SHOW

// определяем ещё одну
let SQUARE = 
    DUP >> MUL 

START |> TWO |> SQUARE |> SHOW

// и ещё одна функция
let CUBE = 
    DUP >> DUP >> MUL >> MUL 

START |> THREE |> CUBE |> SHOW

// и ещё
let SUM_NUMBERS_UPTO = 
    DUP                     // n  
    >> ONE >> ADD           // n+1
    >> MUL                  // n(n+1)
    >> TWO >> SWAP >> DIV   // n(n+1) / 2 

START |> THREE |> SQUARE |> SUM_NUMBERS_UPTO |> SHOW

В каждом из этих примеров новая функция определяется с помощью композиции других функций. Это хороший пример "комбинаторного" подхода к построению функциональности.

Конвейеры против композиции

Мы видели два различных способа использования нашей модели; при помощи конвейеров и композиции. Но в чем разница? И почему надо предпочесть один из способов другому?

Разница заключается в том, что конвейеры в некотором смысле являются операцией "трансформации в реальном времени". В момент использования конвейера операции выполняются сразу, через передачу определенного стека.

С другой стороны, композиция — это нечто вроде "плана", который мы хотим осуществить, построение функций из набора составляющих без непосредственного применения.

Например, можно создать "план" вычисления квадрата числа через комбинацию малых операций:

let COMPOSED_SQUARE = DUP >> MUL

Я не могу привести эквивалент на основе конвейеров.

let PIPED_SQUARE = DUP |> MUL

Это приведет к ошибке компиляции. Мне нужен какой-то конкретный экземпляр стека, чтобы выражение заработало:

let stackWith2 = EMPTY |> TWO
let twoSquared = stackWith2 |> DUP |> MUL

И даже в этом случае, я смогу получить ответ только для этого конкретного ввода, а не обобщенный план вычисления на основе любого ввода, как в примере с COMPOSED_SQUARE.

Другой способ создать "план" — явно передать лямбду в более примитивные функции:

let LAMBDA_SQUARE = unary (fun x -> x * x)

Это более явный способ (и скорее всего более быстрый), но теряются все преимущества и ясность композиционного подхода.

В общем, если это возможно, следует стремиться к композиционному подходу!

Полный код

Полный код для всех примеров, представленных выше:

// ==============================================
// Типы
// ==============================================

type Stack = StackContents of float list

// ==============================================
// Стековые примитивы
// ==============================================

/// Поместить значение в стек
let push x (StackContents contents) =   
    StackContents (x::contents)

/// Вытолкнуть значение из стека и вернуть его
/// и новый стек в виде пары
let pop (StackContents contents) = 
    match contents with 
    | top::rest -> 
        let newStack = StackContents rest
        (top,newStack)
    | [] -> 
        failwith "Stack underflow"

// ==============================================
// Ядро (операторы)
// ==============================================

// вытолкнуть два верхних элемента
// применить к ним бинарную операцию
// положить результат в стек 
let binary mathFn stack = 
    let y,stack' = pop stack    
    let x,stack'' = pop stack'  
    let z = mathFn x y
    push z stack''      

// вытолкнуть вершину стека
// применить к ней унарную операцию
// положить результат в стек
let unary f stack = 
    let x,stack' = pop stack  
    push (f x) stack'         

// ==============================================
// Ядро (остальное)
// ==============================================

/// Вытолкнуть и напечатать вершину стека
let SHOW stack = 
    let x,_ = pop stack
    printfn "The answer is %f" x
    stack  // продолжаем с тем же стеком

/// Дублировать вершину стека
let DUP stack = 
    let x,s = pop stack  
    push x (push x s)   

/// Обменять два верхних значения местами
let SWAP stack = 
    let x,s = pop stack  
    let y,s' = pop s
    push y (push x s')   

/// Удалить вершину стека
let DROP stack = 
    let _,s = pop stack  //вытолкнуть вершину стека
    s                    //вернуть всё остальное

// ==============================================
// Слова, построенные на примитивах
// ==============================================

// Костанты
// -------------------------------
let EMPTY = StackContents []
let START  = EMPTY

// Числа
// -------------------------------
let ONE = push 1.0
let TWO = push 2.0
let THREE = push 3.0
let FOUR = push 4.0
let FIVE = push 5.0

// Арифметические функции
// -------------------------------
let ADD = binary (+)
let SUB = binary (-)
let MUL = binary (*)
let DIV = binary (../)

let NEG = unary (fun x -> -x)

// ==============================================
// Слова, построенные с помощью композиции
// ==============================================

let SQUARE =  
    DUP >> MUL 

let CUBE = 
    DUP >> DUP >> MUL >> MUL 

let SUM_NUMBERS_UPTO = 
    DUP                     // n  
    >> ONE >> ADD           // n+1
    >> MUL                  // n(n+1)
    >> TWO >> SWAP >> DIV   // n(n+1) / 2

Заключение

У нас получился простой калькулятор на основе стека. Мы увидели, как, начиная с нескольких примитивных операций (push, pop, binary, unary) и других, можно построить полноценный DSL, простой в реализации и использовании.

Как можно догадаться, данный пример был в изрядной степени основан на языке Forth. Я очень рекомендую бесплатную книгу "Thinking Forth", которая повествует не только о языке Forth, но и о других (не объектно-ориентированных!) методах декомпозиции задач, которые одинаково применимы к функциональному программированию в целом.

Я почерпнул идею для данной статьи из великолепного блога Ashley Feniello. Если есть желание погрузиться глубже в эмуляцию основанного на стеке языка на базе F#, начните с него. Have fun!

Дополнительные ресурсы

Для F# существует множество самоучителей, включая материалы для тех, кто пришел с опытом C# или Java. Следующие ссылки могут быть полезными по мере того, как вы будете глубже изучать F#:

Также описаны еще несколько способов, как начать изучение F#.

И наконец, сообщество F# очень дружелюбно к начинающим. Есть очень активный чат в Slack, поддерживаемый F# Software Foundation, с комнатами для начинающих, к которым вы можете свободно присоединиться. Мы настоятельно рекомендуем вам это сделать!

Не забудьте посетить сайт русскоязычного сообщества F#! Если у вас возникнут вопросы по изучению языка, мы будем рады обсудить их в чатах:

комната #ru_general в Slack-чате F# Software Foundation
чат в Telegram
чат в Gitter
комната #ru_general в Slack-чате F# Software Foundation

Об авторах перевода

Автор перевода @kleidemos
Перевод и редакторские правки сделаны усилиями русскоязычного сообщества F#-разработчиков. Мы также благодарим @schvepsss и @shwars за подготовку данной статьи к публикации.

Tags:

Hubs: