Effect system을 공부하던 중, Demystifying Functional Effect Systems in Scala라는 좋은 글을 접했다. Rust에서 effect system을 적용하면 어떤 모습이 될 지 궁금하여, 해당 글을 한국어로 간단히 요약하면서 Rust로 코드를 옮겨보았다.
프로그래밍 언어 이론을 공부하는 초심자의 시선에서 작성했기 때문에 내용에 부정확한 점이나 오역이 있을 수 있습니다. 이메일 [email protected] 로 연락 주시면 정정하겠습니다. 감사합니다.
1장: 이펙트 생성하고 조합하기
이펙트는 일반적으로 IO 모나드의 개념에서 출발한다. IO 모나드는 인자 없는 함수를 감싸 효과(이펙트)를 (필요하면) 만들어내고 반환값을 생성해내는 객체1다. 모나드가 됨으로서 여러 개의 ‘감싸진’ (혹은 일시정지된) 이펙트가 합성되어 이펙트들의 순차적 실행을 표현할 수 있게 된다.
참고로, 일반적인 모나드에 대한 설명은 이 글에서 다루지 않으나, 이러한 개념을 이해하는 것은 이 글을 따라가는 데 상당히 중요할 것이다.
기본적인 IO 모나드는 아마도 다음과 같은 trait으로 정의할 수 있을 텐데, ToyIo::effect 생성자(대개 pure라는 이름으로도 불려짐)를 통해 실존하는 ’toy’ 구현체를 생성할 수 있게 된다(아직 세부적인 구현은 이루어지지 않음).
pub trait IoExt: Io + Sized {
fn flat_map<R: Io, F: FnOnce(Self::Success) -> R>(self, f: F) -> FlatMap<Self, F>;
fn map<S, F: FnOnce(Self::Success) -> S>(self, f: F) -> Map<Self, F>;
}
impl<T: Io> IoExt for T {
fn flat_map<R: Io, F: FnOnce(Self::Success) -> R>(self, f: F) -> FlatMap<T, F> {
FlatMap {
inner: self,
func: f,
}
}
fn map<S, F: FnOnce(Self::Success) -> S>(self, f: F) -> Map<T, F> {
Map {
inner: self,
func: f,
}
}
}
// ToyIo는 Io를 구현하는 어떠한 구조체 타입이다. 자세한 구현은 뒤에 나온다.
pub struct ToyIo<T>(T);
impl<T, F: FnOnce() -> T> ToyIo<F> {
pub fn effect(f: F) -> Self {
Self(f)
}
}
실제 코드에서는
flat_map,map을IoExtextension trait으로 구현하었고 뒤따라오는 코드들에서도 해당 구현을 기반으로 작성될 예정이다.
이제 우리는 IO로 감싸진 이펙트들을 조합해 어떤 프로그램이든 만들어낼 수 있다:
fn program() {
use std::io::{self, BufRead};
ToyIo::effect(|| println!("what's your name?"))
.flat_map(|()| {
ToyIo::effect(|| {
let mut stdin = io::stdin().lock();
let mut buf = String::new();
stdin.read_line(&mut buf).expect("cannot read");
buf
})
})
.map(|name| ToyIo::effect(move || println!("hello, {name}!")))
.run();
}
원문에서는 Scala의 for comprehension을 사용했으나 Rust에는 그러한 문법 설탕이 존재하지 않으므로 직접 desugaring하였다. 이는 Rust에서 이펙트 시스템을 적극적으로 채용하려면 proc-macro 등으로 문법을 확장하거나 컴파일러에서 문법 설탕을 지원해줘야 함을 함의한다.
ToyIo 구현
이제 ToyIo 모나드를 본격적으로 구현해보자. ToyIo는 ZIO3의 API를 얼추 따르지만 typed error나 environment같은 기능은 단순함을 위해 제외되었다.
impl<T, F: FnOnce() -> T> Io for ToyIo<F> {
type Success = T;
fn run(self) -> Self::Success {
todo!()
}
}
pub struct FlatMap<T, F> {
inner: T,
func: F,
}
impl<T: Io, R: Io, F: FnOnce(T::Success) -> R> Io for FlatMap<T, F> {
type Success = R::Success;
fn run(self) -> Self::Success {
todo!()
}
}
pub struct Map<T, F> {
inner: T,
func: F,
}
impl<T: Io, S, F: FnOnce(T::Success) -> S> Io for Map<T, F> {
type Success = S;
fn run(self) -> Self::Success {
todo!()
}
}
코드가 원문에 비해 훨씬 장황한 이유는, 타입-레벨 프로그래밍과 정적 디스패치를 사용해 런타임 비용을 없애고자, 각 trait method의 리턴형을 독립된 타입으로 정의하였기 때문이다. 동적 디스패치로 처리한 코드는 그렇게 복잡하지 않다:
pub trait Io {
type Success;
fn flat_map<R: Io, F: FnOnce(T) -> R>(self, f: F) -> R::Success;
fn map<S, F: FnOnce(T) -> S>(self, f: F) -> S;
fn run(self) -> T;
}
pub struct ToyIo<T>(Box<dyn FnOnce() -> T>);
impl<T> ToyIo<T> {
pub fn effect<F: FnOnce() -> T + 'static>(f: F) -> Self {
Self(Box::new(f))
}
}
impl<T> Io for ToyIo<T> {
type Success = T;
fn flat_map<R: Io, F: FnOnce(T) -> R>(self, f: F) -> R::Success {
todo!()
}
fn map<S, F: FnOnce(T) -> S>(self, f: F) -> S { todo!()
}
fn run(self) -> T {
todo!()
}
}
또한, 원문에서는
TIO.succeed()를 활용해map의 구현을flatMap으로 넘기고 있지만, Rust에서는 그렇게 하면 익명 함수의 타입 파라미터를 만들어낼 수 없기 때문에 불가능하다. RPITIT(return-position-impl-trait-in-trait)이 안정화되지 않는 한 각각 구현하는 것이 최선이라고 판단하였다.
ToyIo와 FlatMap, Map은 이펙트가 어떻게 실행되어야 하는지를 정의한다. 이 정의는 가끔 ‘대수’로 불리기도 한다. (작성자 주: ‘대수적 이펙트’의 그 ‘대수’인 것으로 보인다.)
엄밀히 원문의 Scala case class를 사용한 코드를 Rust로 옮기면 열거형으로 FlatMap과 Map을 표현했어야 하나, zero-cost를 강조하기 위해 각각을 구조체로 표현하고 타입 레벨 프로그래밍을 도입하였다.
이제 이 ToyIo와 친구들의 실행 방법을 정의할 차례이다.
use std::error::Error;
type BoxError = Box<dyn Error + Send + Sync + 'static>;
pub trait Run: Io {
fn eval(self) -> Result<Self::Success, BoxError>;
}
impl<T, F: FnOnce() -> T> Run for ToyIo<F> {
fn eval(self) -> Result<Self::Success, BoxError> {
Ok(self.0())
}
}
impl<T: Run, R: Run, F: FnOnce(T::Success) -> R> Run for FlatMap<T, F> {
fn eval(self) -> Result<Self::Success, BoxError> {
(self.func)(self.inner.eval()?).eval()
}
}
impl<T: Run, S, F: FnOnce(T::Success) -> S> Run for Map<T, F> {
fn eval(self) -> Result<Self::Success, BoxError> {
Ok((self.func)(self.inner.eval()?))
}
}
엄밀히 따지면, 에러를 박싱함으로서 zero-cost에서 벗어났다고도 할 수 있다. 그러나 에러 처리 자체를 zero-cost로 구현하는 것에 집중하기보다는(필자가 생각하는 선에서는 완벽한 zero-cost 에러 처리를 타입 레벨 프로그래밍으로 구현할 수는 없을 것 같다) effect system을 구현하는 것에 집중하는 것이 옳다는 판단 하에 에러를 박싱하였다.
이제 ToyIo를 실제로 사용해보자. 그러기 위해서는 ToyIo를 실행해줄 실행기가 필요하다.
pub fn unsafe_run_sync<R: Run>(r: R) -> Result<R::Success, Box<dyn Error + Send + Sync + 'static>> {
r.eval()
}
fn sequence_effects() {
let effect = ToyIo::effect(|| println!("running first effect"))
.flat_map(|()| ToyIo::effect(|| println!("running second effect")));
unsafe_run_sync(effect).expect("cannot unsafe_run_sync");
}
running first effect
running second effect
원문에서는
unsafe_run_sync이eval().unwrap()을 수행하는 것에 가까우나 이는 idiomatic Rust에서 멀어지게 되므로 지양하였다.
1장의 전체 코드는 https://github.com/cr0sh/demystifying-functional-effect-systems-in-rust/blob/master/iteration1/src/lib.rs 에 있다.
2장: 에러로부터 복구하기
에러 핸들링을 지원하기 위해, 어떻게 이펙트의 실패를 표현할 수 있을지 알아보자.
pub struct ToyIoFail<E>(E);
impl<E> ToyIoFail<E> {
pub fn fail(e: E) -> Self {
Self(e)
}
}
impl<E> Io for ToyIoFail<E> {
type Success = Never; // #[feature(never_type)] 이 안정화되면 `!`일 것이다.
}
impl<E: Error + Send + Sync + 'static> Run for ToyIoFail<E> {
fn eval(self) -> Result<Self::Success, BoxError> {
Err(Box::new(self.0))
}
}
#[derive(Debug, Clone, Copy)]
pub enum Never {}
이제 실패한 이펙트의 복구 방법도 알아보자:
pub trait IoExt: Io + Sized {
// ...
fn recover<U: Io<Success = Self::Success>, F: FnOnce(BoxError) -> U>(
self,
f: F,
) -> Recover<Self, F>;
}
impl<T: Io> IoExt for T {
// ...
fn recover<U: Io<Success = T::Success>, F: FnOnce(BoxError) -> U>(
self,
f: F,
) -> Recover<Self, F> {
Recover {
inner: self,
func: f,
}
}
}
pub struct Recover<T, F> {
inner: T,
func: F,
}
impl<T, S: Io<Success = T>, U: Io<Success = T>, F: FnOnce(BoxError) -> U> Io for Recover<S, F> {
type Success = T;
}
impl<T, S: Run<Success = T>, U: Run<Success = T>, F: FnOnce(BoxError) -> U> Run for Recover<S, F> {
fn eval(self) -> Result<Self::Success, BoxError> {
match self.inner.eval() {
Ok(x) => Ok(x),
Err(e) => (self.func)(e).eval(),
}
}
}
이제 실제로 이를 사용해 오류를 복구해보자.
use std::{error::Error, fmt::Display};
use super::*;
#[derive(Debug)]
struct StrError(&'static str);
impl Display for StrError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}", self.0)
}
}
impl Error for StrError {}
fn fail_and_recover() {
let effect = ToyIo::effect(|| println!("running first effect"))
.flat_map(|()| ToyIoFail::fail(StrError("some error")))
.flat_map(|_| ToyIo::effect(|| println!("second effect - will not run")))
.recover(|e| ToyIo::effect(move || println!("recovered from failure: {e}")));
unsafe_run_sync(effect).expect("cannot execute");
}
running first effect
recovered from failure: some error
여기까지만 해도 충분히 강력하지만, 우리의 ToyIo 예제는 두 가지 문제점이 있다:
- 비동기를 지원하지 않는다.
- Stack-safe하지 않다.
두 번쩨 포인트를 짚어보자면, 우리의 구현은 재귀에 의존하기 때문에 타입의 깊이가 깊어지면 그만큼 재귀의 깊이도 깊어진다.
pub struct ToyIoForEach<I, F> {
it: I,
func: F,
}
impl<I, F> ToyIoForEach<I, F> {
pub fn for_each(it: I, f: F) -> Self {
Self { it, func: f }
}
}
impl<Item, I: Iterator<Item = Item>, R: Io, F: FnMut(Item) -> R> Io for ToyIoForEach<I, F> {
type Success = Vec<R::Success>;
fn eval(self) -> Result<Self::Success, BoxError> {
self.it
.fold(ToyIo::effect(|| Vec::new()), |acc, curr| {
// mismatched types
IoExt::flat_map(acc, |x| {
(self.func)(curr).map(|y| {
let mut z = x;
z.push(y);
z
})
})
})
.eval()
}
}
Checking iteration2 v0.1.0 (/Users/namjh/dev/personal/demystifying-functional-effect-systems-in-rust/iteration2)
error[E0308]: mismatched types
--> iteration2/src/lib.rs:146:17
|
145 | .fold(ToyIo::effect(|| Vec::new()), |acc, curr| {
| --
| |
| the expected closure
| the found closure
146 | / IoExt::flat_map(acc, |x| {
147 | | (self.func)(curr).map(|y| {
148 | | let mut z = x;
149 | | z.push(y);
150 | | z
151 | | })
152 | | })
| |__________________^ expected `ToyIo<[[email protected]:145:33]>`, found `FlatMap<ToyIo<[[email protected]:145:33]>, ...>`
|
= note: expected struct `ToyIo<_>`
found struct `FlatMap<ToyIo<_>, [closure@iteration2/src/lib.rs:146:38: 146:41]>`
어라?
생각해보니 스칼라는 동적 디스패치를 vtable로 구현하는 언어고, 그렇기 때문에 flatMap이 n번 중첩된 객체와 m번 중첩된 객체를 TIO라는 같은 trait으로 다룰 수 있다. Rust의 문법을 빌리면, ToyIo<_>와 FlatMap<ToyIo<_>, _>, FlatMap<FlatMap<...FlatMap<ToyIo<_>, _>..._> _>이 모두 한 변수에 들어갈 수 있어야 하는 것이다. 그런데 내가 구현한 방식은 타입 레벨 프로그래밍을 사용해 정적 디스패치만을 고수하였으므로 이렇게 런타임에 디스패치를 할 수가 없다!
😱
해법을 찾아보자. 스칼라의 방법을 그대로 모사해서 Box로 type erasure을 구현할 수 있다. 원문의 코드를 가져오면 다음과 같다:
// Initial algebra
case class Effect[+A](a: () => A) extends TIO[A]
case class Fail[A](e: Throwable) extends TIO[A]
// Effect combinators
case class FlatMap[A, B](tio: TIO[A], f: A => TIO[B]) extends TIO[B]
case class Recover[A](tio: TIO[A], f: Throwable => TIO[A]) extends TIO[A]
이를 Rust enum으로 모델링해보자. Case class의 타입 파라미터가 모두 같지 않아서 불가능할 것 같지만, extends TIO[_]에서 _에 해당하는 부분을 기준으로 잡아 T로 통일하고 나머지 타입 파라미터를 박싱으로 지우면 가능하다.
/// A 'toy' IO effect that can either succeed with `T` or fail with `E`.
pub enum ToyIo<T, E> {
Effect(Box<dyn FnOnce() -> Result<T, E>>),
Fail(E),
// Should be boxed to 'erase' the return type of the inner effect
FlatMap(Box<dyn FlatMap<Success = T, Error = E>>),
Recover(Box<Self>, Box<dyn FnOnce(E) -> Self>),
}
pub trait FlatMap {
type Success;
type Error;
fn mapped(&mut self) -> ToyIo<Self::Success, Self::Error>;
}
struct FlatMapImpl<T, U, E, F: FnOnce(T) -> ToyIo<U, E>> {
inner: ToyIo<T, E>,
func: F,
}
enum으로 구현하는 김에, 에러 타입을 박싱하지 않도록 해 최대한 컴파일 타임에 에러를 식별할 수 있도록 해 보았다. (아마도 실용적인 면에서
map_err같은 메서드가 필요할 것이다.)
이제 Scala 구현을 참조해 이펙트 생성자와 친구 메서드들을 구현해주면 다음과 같다.
impl<T: 'static, E: 'static> ToyIo<T, E> {
pub fn succeed(x: T) -> Self {
Self::Effect(Box::new(move || Ok(x)))
}
pub fn effect(f: impl FnOnce() -> T + 'static) -> Self {
Self::Effect(Box::new(move || Ok(f())))
}
pub fn fail(err: E) -> Self {
Self::Fail(err)
}
pub fn map<U: 'static>(self, f: impl FnOnce(T) -> U + 'static) -> ToyIo<U, E> {
ToyIo::FlatMap(Box::new(Some(FlatMapImpl {
inner: self,
func: move |x| ToyIo::succeed(f(x)),
})))
}
pub fn recover(self, f: impl FnOnce(E) -> Self + 'static) -> Self {
Self::Recover(Box::new(self), Box::new(f))
}
}
물론, (ToyIo<T, E>, T -> ToyIo<U, E>)에서 T를 지워 ToyIo<U, E>의 모양새만 남기는 FlatMap trait의 구현도 잊어서는 안 된다:
impl<T, U, E, F: FnOnce(T) -> ToyIo<U, E>> FlatMap for Option<FlatMapImpl<T, U, E, F>> {
type Success = U;
type Error = E;
fn mapped(&mut self) -> ToyIo<Self::Success, Self::Error> {
let this = self.take().unwrap();
match this.inner.eval().map(|x| (this.func)(x)) {
Ok(eff) => eff,
Err(e) => ToyIo::Fail(e),
}
}
}
이제 Option<FlatMapImpl<T, U, E, F>>를 Box<dyn FlatMap<U, E>로 박싱해 T를 지울 수 있다.
impl<T: 'static, E: 'static> ToyIo<T, E> {
// ...
pub fn flat_map<U: 'static>(self, f: impl FnOnce(T) -> ToyIo<U, E> + 'static) -> ToyIo<U, E> {
ToyIo::FlatMap(Box::new(Some(FlatMapImpl {
inner: self,
func: f,
})))
}
}
다시 본론으로 돌아와서 ForEach를 구현해보자. 이제는 ToyIo::flat_map이 ToyIo를 내뱉으므로 flat_map을 임의의 개수만큼 중첩시킬 수 있다.
pub struct ForEach<I, F> {
it: I,
func: F,
}
impl<
Item: 'static,
I: Iterator<Item = Item>,
T: 'static,
E: 'static,
F: FnOnce(Item) -> ToyIo<T, E> + Clone + 'static,
> Io for ForEach<I, F>
{
type Success = Vec<T>;
type Error = E;
fn eval(self) -> Result<Self::Success, Self::Error> {
self.it
.fold(ToyIo::effect(|| Vec::new()), |acc, curr| {
let func = self.func.clone();
acc.flat_map(move |x| {
(func)(curr).map(|y| {
let mut z = x;
z.push(y);
z
})
})
})
.eval()
}
}
그리고 10만번 순회하는 for_each를 실행하면…
fn for_each() {
let effect = ToyIo::<i32, Infallible>::for_each(0..100000, |x| {
ToyIo::<_, Infallible>::effect(move || {
println!("{x}");
x
})
});
unsafe_run_sync(effect).expect("cannot execute");
}
thread 'test::for_each' has overflowed its stack
fatal runtime error: stack overflow
error: test failed, to rerun pass `--lib`
너무 많이 중첩된 flat_map을 해석하던 중 스택 오버플로우가 발생하는 모습을 볼 수 있다.
2장의 전체 코드는 https://github.com/cr0sh/demystifying-functional-effect-systems-in-rust/blob/master/iteration2/src/lib.rs 에 있다.
3장과 4장은 [part 2](TBD)에서 이어집니다.
각주
-
원문은 ‘construct’다. ↩︎
-
원문의 Scala 코드에 따르면
Io<T>trait이 타입 파라미터T에 대해 covariant해야 하나(trait IO[+A]), Rust에서는 trait에서 variance를 표현할 방법이 없다. 상속 기반 서브타이핑이 Rust에서는 사용되지 않기 때문에 invariance가 큰 문제를 일으키지 않는다고 판단했다. ↩︎ -
Scala에서 유명한 Effect system 라이브러리다. ↩︎
-
원문에서는 이 이후로
.run()을 사용하는 예시가 나오지 않으므로 추후의 구현에서run메서드는 생략하도록 한다. 참고로, 타입 시스템의 한계로 인해 Rust에서 이.run()을 구현하려 하면<FlatMap as Io>::run의 구현을 만들어내는 것이 불가능하다. ↩︎