Spiiin's blog1 - (2009) Python in imaginary world
2 - (2015) Scala in imaginary world
3 - (2021) Nim in imaginary world
4 - (2022) daScript in imaginery world
5 - (2023) AI in imaginery world
Ещё один язык — еще один подход к решению пазла из James Bond Jr!
https://github.com/spiiin/james_bond_jr_problem/tree/main/fsharp
F# — язык для полиглотов#
С одной стороны, для изучения функционального программирования проще выучить какой-нибудь ML-язык.
С другой — он всё же существует на платформе .NET, и взаимодействует с библиотеками, так что нужно ориентироваться и в C#.
С третьей — его можно применять как транспилер (Fable) в другие языки (JavaScript/Python/Rust), что требует хорошего знания синтаксиса этих языков.
С четвёртой — если использовать его для тестирования передовых академических функциональных приёмов программирования, то заодно удобно уметь читать код на lisp/haskell/других вариантах ml.
С пятой — F# можно использовать для создания мини-языков (Domain Specific Languages, the functional way)
Я использую “задачку Джеймса Бонда” как одно из первых упражнений при изучении языка, чтобы потыкать его фичи. Для F# это — лаконичность кода, параллельные вычисления, использования инструментария .net для профилирования, провайдеры типов и цитирование кода/транспиляция в gpu-код, ну и немного идиом функционального программирования.
Первая версия#
Первая особенность — лаконичность, по количеству строк он попадает в одну категорию со Scala:
1-james_bond_fsharp_slow.fs
Особенности синтаксиса:
- Паттерн-матчинг везде
Используется не только в явном match, но и например, в определении локальной переменной или в аргументах функцииlet (State es) = endState in es //inplaced pattern-matching with captured endState
let filterNumbers = function | 1 | 2 | 3 -> printfn "Found 1, 2, or 3!"
Можно расширять кастомными паттернами
- Computational expressions
Можно “выворачивать” нелинейный код в линейный с помощью вычислительных выражений.
seq {
if List.isEmpty paths then
yield! Seq.empty
else
//... calculate more dfs moves
yield sortedPaths
yield! next_search_step more explored endState
}seq — не вшитый в язык генератор, а объект, который можно написать самому. Как и другие типы вычислений — кастомные корутины, асинхронные вычисления, продолжения, вычисления с возвратом, linq-выражения, etc. В первом приближении, можно рассматривать вычислительные выражения, как способ перегрузить стандартный синтаксис языка.
Чуть более быстрая версия#
Наивно написанный код работает около 7 секунд. Он возвращает первое найденное решение задачи, не всегда оптимальное. С помощью ИИ перебирая алгоритмы на Python, я знал, что кроме первого найденного решения в 9 ходов существует и решение в 8 ходов, поэтому добавил отбрасывание неоптимальных решений. Такое решение нашлось за 85 секунд. Я убрал явный мусор, и разогнал его до 14 секунд.
6-james_bond_fsharp_slow_only_8_custom_hash.fs
- закешировать значение функции оценки
- заменить тормозные структуры более быстрыми (в F# списки иммутабельны, так что могут шарить свои хвосты, дальше можно было бы заменять массивом)
- написать свою функцию хеширования взамен тормозной дефолтной
В целом, можно разойтись в оптимизациях достаточно далеко, но как можно посмотреть в конце плейлиста, в случаях скорости лучше сразу проектировать код в data oriented, что уже за пределами первого подхода к языку.
Вместо этого, можно попробовать пойти другим путём, применяя оптимизации, которые специфичны для функционального программирования или F# в частности.
Параллельная версия#
7-james_bond_fsharp_slow_only_8_pseq.fs
В теории, написанный в функциональном стиле код можно распараллелить с минимальными усилиями. Лёгким движением меняет Seq на PSeq и добавляем в конвейер обработки withDegreeOfParallelism:
let more =
sortedPaths
|> PSeq.withDegreeOfParallelism Environment.ProcessorCount // <-- 1
|> PSeq.collect (fun path ->
moves
|> Seq.map (fun move -> path.Extend(move, endState, rate))
|> Seq.filter filterPath
)
|> Seq.toList
more
|> PSeq.withDegreeOfParallelism Environment.ProcessorCount // <-- 2
|> PSeq.iter (fun path -> explored.TryAdd(path.State, ()) |> ignore)Почти получилось — программа падает на explored.TryAdd в словарь. Для исправления нужно использовать thread-safe ConcurrentDictionary.
Это не самый оптимальный способ, можно изменить алгоритм и структуры данных (Parallel A* Search), но зато потребовалось изменение всего трёх строк, для игрушечной задачки сойдёт. Время поиска сократилось с 14 до 8 секунд.
Напоследок можно улучшить саму функцию оценки позиции на поле. Простейшее улучшение — “оцениваем не только элементы на своих местах, но и те, которым остался 1 шаг до своего места” ускоряет поиск с 8 до 1.5 секунд.
9.5-james_bond_fsharp_slow_only_8_better_rate_5000_arr.fs
Такой код уже показывает относительно равномерное “размазывание” производительности в профайлере:
что значит, что его пора было бы выбросить и переписать нормально
Чуть рефакторинга#
10-james_bond_fsharp_slow_only_8_refactor_reader.fs
let rec nextSearchStep (paths: Path array) =
Reader.reader {
let! { TransformPaths = transformPaths; FilterPath = filterPath; Rate = rate; Explored = explored; EndState = endState } = Reader.ask
//...
}С помощью монады Reader можно:
- спрятать настраиваемые аргументы функции в сам тип вычисления
- убрать жёстко заданный порядок выполнения кода, вместо этого передать настройку способа вычислений вызывающей стороне
(у меня тут “ненастоящая” монада, без такого разделения, это тоже как-то не уложилось в первый подход к языку)
Six approaches to dependency injection — про этот Reader, а такж паттерн Interpreter на Free monads
Prefer Continuations to API Classes in F#
Более глобально про идиомы и организацию кода на F#
Functional Programming Design Patterns
Library patterns Multiple levels of abstraction
Library patterns Why frameworks are evil
Compile-time версия#
F# не поддерживает произвольных compile-time вычислений, но, как и во многом другом, предлагает свой путь — Type Providers. Провайдеры типов предоставляют хук компилятора на запрос какого-либо типа. Т.е. тут даже не Compile-Time, а Intellisense-Time вычисления.
Провайдер типов должен находится в отдельной .Net-сборке, к которой будет обращаться компилятор из основной программы. Для написания и тестирования сборки с провайдерами типов лучше использовать интерактивную основную программу, а не работать из IDE, потому что сама IDE может блочить сборку с провайдером типом (для генерации всплывающих подсказок о типе). Удобно использовать Jupyter Lab
Type Providers бывают двух типов — erased создают ограниченное количество типов, а generative позволяют сгенерировать типы по запросу.
Теперь код решения задачи выглядит так:
open MyProvider2
//создаём тип, содержащий ответ
type RateType = MyProvider2.RateProvider<
"1; 2; 2; 1; 3; 4; 4; 3; 3; 4; 4; 3; 2; 4; 4; 2",
"4; 3; 4; 2; 3; 1; 2; 4; 4; 2; 4; 3; 2; 4; 3; 1"
>
let rateInstance = RateType()
let prop: string = rateInstance.Property;
printfn $"{prop}"TypeProviderSolution.fs
F# не позволяет передать массив чисел в качестве аргумента провайдеру типов, поэтому передаётся строка
Сборка с провайдерами типов подключается только во время компиляции, сама программа теперь не нуждается в параллельных коллекциях и запуске процессов.
GPU compiled-time версия#
Можно пойти ещё дальше. Из одного провайдера типов вызвать следующий.
Например, провайдер типов может запросить предпросчитанные значения функции оценки для всех возможных состояний игрового поля.
Состояний для разных вариантов поля существует ~10-100 миллионов. Если попытаться заставить посчитать функцию оценки для каждого в провайдере типов на CPU, можно уронить компилятор (после пары минут размышлений). Но если задействовать видеокарту — рассчёт займёт около 7-8 секунд.
В чистом виде это больное решение, так как пришивает зависимость компиляции от видеокарты. Но позволяет взглянуть на программу под новым углом — как на конфигурируемую систему сборки самой себя. В том числе — асинхронной сборки, которая может начать рассчёты ещё во время написания программы (например, провайдер типов может запустить фоновый рассчёт на видеокарте во время объявления типа, чтобы к моменту НАЧАЛА компиляции уже иметь результат).
Существует несколько библиотек, которые позволяют генерировать из F#-кода код, пригодный для выполнения на GPU:
- зацитировать код в выражение и транспилировать его в текстовый код на языках для gpgpu
- зацитировать код в выражение и отдать само выражение альтернативной программе
- собрать специальную сборку с il-кодом, и разобрать его альтернативным компилятором
ilgpu, Alea.GPU, Brahma.FSharp, FShade
правда, любой из трёх подходов требует изменений функции rate, что естественно для кода, который будет выполняться в совершенно другой среде
Code quotations — цитирование выражений.
BrahmaFSharp.fs — proof of concept такого решения. Не удалось нормально собрать провайдер типов из-за конфликта зависимостей версий библиотеки (который скорее всего можно решить чёрной .net магией remap assemblies versions, другие провайдеры типов как-то это побеждают). Так что в виде утилиты командной строки, которую может запустить провайдер типов.
Функция для вычисления на gpu, без использования .net коллекций:
let rateKernel (clContext: ClContext) workGroupSize =
let kernel =
<@
fun (range: Range1D) (endState: ClArray<int>) (packedPerms: ClArray<int>) (ratings: ClArray<int>) ->
let getWrapDistance a b size =
min ((a - b + size) % size) ((b - a + size) % size)
let unpack (packedValue: int) (output: int[]) =
for i = 0 to 15 do
output.[i] <- ((packedValue >>> (i * 2)) &&& 0b11) + 1
let mutable total = 0
let id = range.GlobalID0
let baseIdx = id * 16
let packedPermutation = packedPerms.[id]
let perms = Array.zeroCreate 16
unpack packedPermutation perms
for i = 0 to 15 do
if perms.[baseIdx + i] <> endState.[i] then
let row = i / 4
let col = i % 4
let target = endState.[i]
let mutable rowShifts = 9999
for j = 0 to 3 do
if perms.[baseIdx + row * 4 + j] = target then
rowShifts <- min rowShifts (getWrapDistance j col 4)
let mutable colShifts = 9999
for j = 0 to 3 do
if perms.[baseIdx + j * 4 + col] = target then
colShifts <- min colShifts (getWrapDistance j row 4)
total <- total + min rowShifts colShifts
ratings.[id] <- total
@>
clContext.Compile kernelВизуализация решения#
Напоследок, простая часть. Для визуализации можно использовать FuncUI, декларативную надстройку над AvaloniaUI.
Don Syme - Functional UI, Functional Apps
let colorIndicesList = ... //answer steps
let currentIndex = ctx.useState(0) //reactive binding
//grid for 4x4 color rectangles
Grid.create [
Grid.rowDefinitions "64,64,64,64"
Grid.columnDefinitions "64,64,64,64"
let indices = colorIndicesList.[currentIndex.Current]
Grid.children [
for row in 0 .. 3 do
for col in 0 .. 3 do
let index = indices.[row * 4 + col]
let color = colors.[index - 1]
Rectangle.create [
Grid.row row
Grid.column col
Rectangle.fill (SolidColorBrush(color))
Rectangle.stroke (SolidColorBrush Colors.Black)
Rectangle.strokeThickness 4.0
]
]
]