Введение в F#

F# — новый функциональный и объектно-ориентированный язык программирования для Microsoft .NET Framework, и в этом году он интегрирован в Microsoft Visual Studio 2010. F# сочетает простой четкий синтаксис со строгой статической типизацией и позволяет не только создавать сравнительно небольшие экспериментальные блоки кода в F# Interactive, но и вести крупномасштабную разработку компонентов на основе .NET Framework в Visual Studio.

F# спроектирован с нуля и рассчитан на выполнение в CLR. Как язык на основе .NET Framework, F# использует богатство библиотек, доступных в .NET Framework, и его можно применять для создания .NET-библиотек или реализации .NET-интерфейсов. F# также использует множество основополагающих механизмов CLR, в том числе обобщения, сбор мусора, инструкции «вызова в хвостовой позиции» (tail call) fn и фундаментальную систему типов Common Language Infrastructure (CLI). Вызов подпрограммы, которая находится в выражении return. — Прим. ред.

В этой статье рассматриваются некоторые основные концепции языка F# и его реализация поверх CLR.

Краткий обзор F#

Начнем с краткого обзора ряда основных языковых средств F#. Подробнее об этих средствах и многих других интересных концепциях в F# см. документацию в F# Developer Center по ссылке fsharp.net.

Самая главная особенность F# — ключевое слово let, которое связывает значение с именем. Оно может использоваться для связывания данных и значений функции, а также для связывания на локальном и глобальном уровнях:

let data = 12

let f x =
    let sum = x + 1
    let g y = sum + y*y
    g x

F# предоставляет несколько базовых типов данных и языковый синтаксис для работы со структурными данными, в том числе со списками, типизированными необязательными значениями и tuple-типами:

let list1 = ["Bob"; "Jom"]

let option1 = Some("Bob")
let option2 = None

let tuple1 = (1, "one", '1')

В этих и других блоках структурных данных можно искать соответствия заданному шаблону с помощью специальных выражений F#. Проверка на соответствие шаблону аналогична применению выражений switch в C-подобных языках, но ее возможности шире: можно не только искать, но и извлекать части из совпадающих выражений; в этом смысле выражения поиска соответствия шаблону напоминают то, как регулярные выражения используются для получения строк, соответствующих шаблону:

let person = Some ("Bob", 32)

match person with
| Some(name,age) -> printfn "We got %s, age %d" name age
| None -> printfn "Nope, got nobody"

F# применяет библиотеки .NET Framework для многих задач, например для доступа к данным из самых разнообразных источников; причем эти .NET-библиотеки могут быть задействованы из F# точно так же, как и в других .NET-языках:

let http url =
    let req = WebRequest.Create(new Uri(url))
    let resp = req.GetResponse()
    let stream = resp.GetResponseStream()
    let reader = new StreamReader(stream)
    reader.ReadToEnd()

F# также является объектно-ориентированных языком и может определять любой .NET-класс или структуру (struct) подобно C# или Visual Basic:

type Point2D(x,y) =
    member this.X = x
    member this.Y = y
    member this.Magnitude =
        x*x + y*y
    member this.Translate(dx, dy) =
        new Point2D(x + dx, y + dy)

Кроме того, F# поддерживает две особые разновидности типов: записи (records) и размеченные объединения (discriminated unions). Записи — простое представление значений данных именованными полями, а размеченные объединения — выразительный способ представления типов, которые могут содержать несколько видов значений, причем с каждым видом могут быть сопоставлены разные данные, например:

type Person =
    { Name : string;
      HomeTown : string;
      BirthDate : System.DateTime }

type Tree =
    | Branch of Tree * Tree
    | Leaf of int

F# поверх CLR

F# во многих отношениях является более высокоуровневым языком, чем C#, с его системой типов, синтаксисом и языковыми конструкциями, еще больше отдаленными от метаданных и промежуточного языка (intermediate language, IL) общеязыковой исполняющей среды (CLR). Это влечет за собой несколько интересных последствий. Самое важное заключается в том, что разработчики на F# зачастую могут решать задачи и думать о своих программах на более высоком уровне, ближе к конкретной предметной области, для которой они ведут разработки. Но это же означает, что компилятор F# выполняет больше работы, связанной с преобразованием F#-кода под CLR, и это преобразование менее прямолинейное.

Компилятор C# 1.0 и CLR создавались в одно время, и их функциональность очень близко выровнена друг относительно друга. Почти все языковые конструкции C# 1.0 имеют предельно прямое представление в системе типов CLR и в CIL. В последующих версиях C# это было выражено уже не столь явно, так как язык C# развивался быстрее самой CLR. Итераторы и анонимные методы были фундаментальными языковыми средствами C# 2.0, для которых не было прямых эквивалентов в CLR. В C# 3.0 выражения запросов и анонимные типы еще больше усилили эту тенденцию.

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

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

Неизменяемость по умолчанию

Связывание через let в F# аналогично var в C# с единственным важным отличием: после связывания значения с именем через let это значение становится неизменяемым. То есть по умолчанию в F# значения являются неизменяемыми:

let x = 5
x <- 6 // error: This value is not mutable

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

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

let mutable y = 5
y <- 6

Аналогичным образом типы в F# тоже являются неизменяемыми по умолчанию:

let bob = { Name = "Bob";
            HomeTown = "Seattle" }
// error: This field is not mutable
bob.HomeTown <- "New York"

let bobJr = { bob with HomeTown = "Seattle" }

В этом примере, когда изменение не разрешено, вместо прямой модификации используется копирование и обновление для создания новой копии из старой при изменении одного или более полей. Хотя при этом создается новый объект, он разделяет многие свои части с исходным. В данном примере нужна лишь единственная строка «Bob». Такое разделение (совместное использование) — одна из важнейших характеристик неизменяемости.

Разделение можно увидеть и в наборах F#. Например, F#-тип list является структурой данных «связанный список», которая может разделять свою хвостовую часть (tail) с другими списками:

let list1 = [1;2;3]
let list2 = 0 :: list1
let list3 = List.tail list1

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

Здесь большую роль играет CLR. В программировании с применением неизменяемости наблюдается тенденция к созданию более короткоживущих объектов — это результат того, что данные преобразуются, а не изменяются «по месту». Сборщик мусора (garbage collector, GC) в CLR хорошо справляется с такой ситуацией. Малые короткоживущие объекты создают минимум издержек благодаря тому, что CLR GC использует сбор мусора на основе поколений объектов.

Функции

F# — функциональный язык, и не удивительно, что функции играют важную роль в этом языке. Функции являются полноценной частью системы типов в F#. Например, тип «char -> int» представляет F#-функции, которые принимают char и возвращают int.

Хотя F#-функции аналогичны .NET-делегатам, они имеют два важных отличия. Во-первых, они не номинальные. Любая функция, которая принимает char и возвращает int, имеет тип «char -> int», тогда как для представления функций с этой сигнатурой может быть использовано несколько делегатов с разными именами, и они не являются взаимозаменяемыми.

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

let add x y = x + y

let add3a = add 3
let add3b y = add 3 y
let add3c = fun y -> add 3 y

Все значения F#-функции являются экземплярами типа FSharpFunc<, >, который определен в библиотеке исполняющей среды F# — FSharp.Core.dll. При использовании библиотеки F# из C# этот тип имеют все значения F#-функции, принимаемые как параметры или возвращаемые из методов. Этот класс выглядит примерно так (если вы определили его в C#):

public abstract class FSharpFunc<T, TResult> {
    public abstract TResult Invoke(T arg);
}

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

FSharpFunc<int, FSharpFunc<char, bool>>

т. е. функцией, которая принимает int и возвращает другую функцию, а та в свою очередь принимает char и возвращает bool. Распространенный случай полного применения (full application) реализуется за счет набора вспомогательных типов из базовой библиотеки F#.

Когда значение F#-функции создается с помощью лямбда-выражения (ключевого слова fun) или в результате частичного применения другой функции (как в случае add3a, показанном ранее), компилятор F# генерирует класс замыкания (closure class):

internal class Add3Closure : FSharpFunc<int, int> {
    public override int Invoke(int arg) {
        return arg + 3;
    }
}

Эти замыкания аналогичны замыканиям, создаваемым компиляторами C# и Visual Basic для своих конструкций с лямбда-выражениями. Замыкание — одна из наиболее часто генерируемых компилятором конструкций в .NET Framework, не имеющих прямой поддержки на уровне CLR. Замыкания существуют практически во всех .NET-языках программирования и особенно интенсивно используются в F#.

Объекты-функции — распространенное явление в F#, поэтому компилятор F# использует множество видов оптимизации, чтобы избежать необходимости создавать эти замыкания. За счет применения подстановки в строку, аннулирования лямбд (lambda-lifting) и прямого представления в виде .NET-методов, когда это возможно, внутренний код, генерируемый компилятором F#, зачастую отличается от описанного в этом разделе.

Распознавание типов и обобщения

Одна заметная особенность всех примеров кода, приведенных до сих пор, — отсутствие всяких обозначений типов (type annotation). Хотя F# является языком программирования со статической типизацией, явные обозначения типов зачастую не требуются, так как F# интенсивно использует логическое распознавание типов (type inference).

Распознавание типов знакомо разработчикам на C# и Visual Basic, которые используют его для локальных переменных, как в этом фрагменте кода на C# 3.0:

var name = "John";

Ключевое слово let в F# работает аналогично, но поддержка распознавания типов в F# гораздо обширнее: она применима к полям, параметрам и возвращаемым типам. В следующем примере у двух полей (x и y) логически определяется тип int, который является типом по умолчанию для операторов + и *, применяемых к этим значениям в теле определения типа. Тип метода Translate логически распознается как «Translate : int * int -> Point2D»:

type Point2D(x,y) =
    member this.X = x
    member this.Y = y
    member this.Magnitude =
        x*x + y*y
    member this.Translate(dx, dy) =
        new Point2D(x + dx, y + dy)

Конечно, вы можете использовать обозначения типов, если вам нужно сообщить компилятору F#, какой тип на самом деле ожидается для определенного значения, поля или параметра. Эта информация потом будет использована при распознавании типа. Например, вы можете изменить определение Point2D, чтобы использовать float вместо int, просто добавив пару обозначений типов:

type Point2D(x : float,y : float) =
    member this.X = x
    member this.Y = y
    member this.Magnitude =
        x*x + y*y
    member this.Translate(dx, dy) =
        new Point2D(x + dx, y + dy)

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

Например, следующая функция map проходит по списку значений и генерирует новый список, применяя свой аргумент f к каждому элементу:

let rec map f values =
    match values with
    | [] -> []
    | x :: rest -> (f x) :: (map f rest)

Заметьте, что обозначений типов не требуется, а логически определенный тип для map — «map : ('a -> 'b) -> list<'a> -> list<'b>». F# способен логически определять типы по соответствию шаблону (pattern matching) и использованию параметра f в качестве функции, по типам двух параметров, имеющим определенную форму, но не полностью фиксированным. Так что F# делает функцию максимально обобщенной, и в то же время имеющей типы, необходимые для реализации. Обратите внимание на то, что обобщенные параметры в F# помечаются префиксом ', чтобы синтаксически отличать их от других имен.

Дон Сайм (Don Syme), проектировщик F#, ранее был ведущим исследователем и разработчиком в проекте реализации обобщений в .NET Framework 2.0. Концепция языков вроде F# крайне зависима от поддержки обобщений исполняющей средой, и интерес Сайма к созданию F# отчасти вызван желанием по-настоящему полно задействовать преимущества этой функциональности CLR. F# интенсивно использует .NET-обобщения; например, в самой реализации компилятора F# присутствует более 9000 параметров обобщенных типов.

Но в конечном счете, распознавание типов — это функциональность периода компиляции, и каждая часть кода на F# получает свой (логически определенный) тип, который кодируется в метаданных CLR для F#-сборки.

Вызовы в хвостовой позиции

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

let rec sumOfSquares nums =
    match nums with
    | [] -> 0
    | n :: rest -> (n*n) + sumOfSquares rest

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

let rec sumOfSquaresAcc nums acc =
    match nums with
    | [] -> acc
    | n :: rest -> sumOfSquaresAcc rest (acc + n*n)

Компилятор F# реализует функции с хвостовой рекурсией (tail-recursive functions), используя два приема, которые гарантируют, что стек не будет разрастаться. Для прямых хвостовых вызовов той же функции, как в вызове sumOfSquaresAcc, компилятор F# автоматически преобразует рекурсивный вызов в цикл while, тем самым избегая вообще всяких вызовов и генерируя код, очень похожий на императивную реализацию той же функции.

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

В CLR есть IL-инструкция, предназначенная специально для поддержки хвостовой рекурсии: tail. -префикс. Инструкция tail. сообщает CLR, что она может отбросить состояние метода вызвавшего кода до выполнения связанного вызова. То есть при приеме этого вызова стек не будет увеличиваться. Это также означает, что, по крайней мере в принципе, JIT-компилятор сможет эффективно выполнить вызов, используя лишь инструкцию перехода. Это очень удобно для F# и гарантирует безопасность хвостовой рекурсии почти во всех случаях:

IL_0009:  tail.
IL_000b:  call    bool Program/SixThirtyEight::odd(int32)
IL_0010:  ret

Для обработки хвостовых вызовов в CLR 4.0 было внесено несколько важных усовершенствований. Версия x64 JIT ранее реализовала хвостовые вызовы очень эффективно, но этот вариант не годился для всех случаев, где появлялась инструкция tail. Это означало, что какой-то F#-код, успешно выполняемый на платформах x86, приводил бы к переполнению стека на платформах x64. В CLR 4.0 эффективная реализация хвостовых вызовов в x64 JIT была распространена на более широкий круг ситуаций, а также реализован механизм с более высокими издержками, необходимый для аналогичной поддержки хвостовых вызовов в x86 JIT.

Детальное описание усовершенствований в CLR 4.0, касающихся хвостовых вызовов, см. в блоге CLR Code Generation ((blogs.msdn.com/clrcodegeneration/archive/2009/05/11/tail-call-improvements-in-net-framework-4.aspx).

F# Interactive

F# Interactive — утилита командной строки и окно в Visual Studio для интерактивного выполнения F#-кода (рис. 1). Эта утилита позволяет экспериментировать с данными, изучать API и проверять логику приложения на F#. F# Interactive базируется на CLR Reflection.Emit API. Этот API дает возможность программе генерировать новые типы и члены в период выполнения, а также динамически вызывать этот код. F# Interactive использует компилятор F# для компиляции кода, вводимого в строке приглашения, а затем с помощью Reflection.Emit генерирует типы, функции и члены, не записывая сборку на диск.

Рис. 1. Выполнение кода в F# Interactive

Одно из важнейших последствий такого подхода в том, что выполняемый пользовательский код не интерпретируется, а полностью транслируется обычным компилятором и обрабатывается JIT-компилятором с применением всех полезных оптимизаций на обоих этих этапах. Это делает F# Interactive великолепной высокопроизводительной средой для апробации новых подходов к решению каких-либо задач и интерактивного исследования больших наборов данных.

Tuple-типы

Tuple-типы в F# обеспечивают простой способ упаковки данных и их передачи блоком, избавляя от необходимости определять новые собственные типы или использовать сложные схемы параметров, например набор выходных параметров для возврата нескольких значений:

let printPersonData (name, age) =
    printfn "%s is %d years old" name age

let bob = ("Bob", 34)

printPersonData bob


let divMod n m =
    n / m, n % m

let d,m = divMod 10 3

Это простые типы, но у них есть несколько важных свойств в F#. Самое главное — они неизменяемые. После конструирования модифицировать элементы tuple нельзя. Это позволяет безопасно обрабатывать tuple-типы просто как комбинацию их элементов. А также обеспечивает поддержку другой важной особенности tuple-типов: структурной эквивалентности (structural equality). Tuple-типы и другие F#-типы, в частности списки, пользовательские записи и объединения, можно сравнивать на эквивалентность сравнением их элементов.

В .NET Framework 4 tuple-типы теперь являются базовым типом данных, определенным в библиотеке базовых классов. При ориентации на .NET Framework 4 для представления соответствующих значений в F# используется тип System.Tuple. Поддержка этого основополагающего типа в mscorlib означает, что программисты на F# могут использовать tuple-типы в сочетании с кодом на C# и наоборот.

Хотя tuple-типы концептуально являются простыми, при проектировании в тип System.Tuple было заложено много интересных решений. Мэтт Эллис (Matt Ellis) подробно описывал процесс проектирования Tuple в одном из недавних выпусков рубрики «CLR с изнанки» (msdn.microsoft.com/magazine/dd942829).

Оптимизации

Поскольку F#-код не столь прямо транслируется в инструкции CLR, у компилятора F# более широкие возможности для оптимизаций, чем у CLR JIT-компилятора. Компилятор F# использует преимущества этого и реализует более глубокие оптимизации в режиме Release по сравнению с компиляторами C# и Visual Basic.

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

В следующем примере не требуется создание никаких tuple-объектов, так как все его использование сводится к уничтожению в выражении проверки на соответствие шаблону:

let getValueIfBothAreSame x y =
    match (x,y) with
    | (Some a, Some b) when a = b -> Some a
    |_ -> None

Единицы мер

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

[<Measure>] type kg
/// Seconds
[<Measure>] type s

let x = 3.0<kg>
//val x : float<kg>

let y = 2.5<s>
// val y : float<s>

let z = x / y
//val z : float<kg/s>

let w = x + y
// Error: "The unit of measure 's'
// does not match the unit of measure 'kg'"

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

Однако единицы мер, хоть и являются частью системы типов F#, в период компиляции удаляются. То есть в конечной .NET-сборке никакой информации о единицах мер не будет, и CLR будет оперировать всеми значениями, исходя из их нижележащих типов, а значит, никаких издержек не создается. Как видите, эта картина противоположна той, которая наблюдается в случае .NET-обобщений; последние полностью доступны в период выполнения.

Если впоследствии поддержка единиц мер будет интегрирована в базовую систему типов CLR, F# сможет предоставлять информацию о единицах мер, и она будет видна из других .NET-языков программирования.

Заключение

Как вы убедились, F# — это выразительный, функциональный, объектно-ориентированный и исследовательский язык программирования для .NET Framework. Он интегрирован в Visual Studio 2010 и включает утилиту F# Interactive, позволяющую напрямую экспериментировать с кодом на этом языке.

Язык и всего его инструментальные средства используют весь спектр возможностей CLR и добавляют некоторые концепции более высокого уровня, которые проецируются на метаданные и IL-код CLR. Но в конечном счете F# — это просто еще один .NET-язык, и его можно легко включать как компонент в новые или существующие .NET-проекты благодаря общей системе типов и одной исполняющей среде.