컴공지식/프로그래밍언어론

First-class function

개강한 공대생 2024. 10. 12. 17:00

일급함수(First-class function)이란 함수 자체가 다른 값처럼 취급될 수 있는 걸 말한다.

그렇기 때문에 다른 함수의 인자값으로 들어갈 수 있다.

 

추상문법에서는 다음과 같이 정의될 수 있겠다.

App이 함수를 부르는 쪽인데 기존의 App 함수와 달라진 부분은 ftn인자값의 형태가 Expr이라는거다.

즉, Expr을 상속하고 있는 Fun 또한 이 인자값이 될 수 있다는 것을 의미한다.

 

여기서 사용 예를 볼 수 있는데, 왼쪽의 콘크리트 문법을 보면 첫번째 줄은 함수를 인자로 넣고 10이 함수의 인자가 되는 것을 볼 수 있다.

근데 두번째 줄도 첫번째 줄과 시멘틱적으로 똑같다.

왜냐면 with로 인해 y가 fun이 되는데 y에 10을 넣는다는 것은 함수의 인자에 10을 넣는거나 마찬가지이기 때문이다.

 

우리의 언어 만들기 프로젝트는 벌써 절반 온 것 같다.

AE -> WAE -> F1WAE -> FWAE(현재)

많은 기능이 추가되었다.

간단한 연산에서, with를 사용한 대체, 뭔가 아쉬운 함수, 이제 완벽한 것 같은 함수

 

이제 바뀐 FWAE의 인터프리터를 알아보자

 

def interp(expr: Expr): Expr = expr match {
  case Num(n) => expr
  case Add(l, r) => numAdd(interp(l), interp(r))
  case Sub(l, r) => numSub(interp(l), interp(r))
  case With(i, v, e) => interp(subst(e, i, interp(v)))
  case Id(s) => throw new Exception(s"Free identifier: $s")
  case Fun(p, b) => expr
  case App(ftn, arg) =>
    val evaluatedFtn = interp(ftn)
    evaluatedFtn match {
      case Fun(param, body) => interp(subst(body, param, interp(arg)))
      case _ => throw new SimpleException("Expected a function")
    }
}

 

Fun 부분과 App 부분이 바뀐 것을 확인할 수 있다.

또 한가지 바뀐 부분이 있는데, 기존의 F1WAE의 함수 반환 타입은 Num이었지만, FWAE는 Expr로 반한활 수 있게 됐다.

App의 바뀐 것 중 중요한 부분은 evaluatedFtn을 통해 이게 Fun을 이용한 것이 맞는지 체크하는 부분이다.

함수가 Expr이 됐으니, 다른 Num도 App에 들어갈 수 있지 않은가? 그런 것을 걸러주는 역할을 한다.

 

일급 함수의 대표적인 예시를 보자

def numAdd(x: Expr, y: Expr): Expr = (x, y) match {
  case (Num(x), Num(y)) => Num(x + y)
}

def numSub(x: Expr, y: Expr): Expr = (x, y) match {
  case (Num(x), Num(y)) => Num(x - y)
}

 

이 둘은 값을 받고 값을 반환하는데 뭔가 비효율적으로 보이지 않나?

겨우 더하기 빼기만 바뀌는건데 이렇게 두 개로 나누어 작성해야 한다니..

이런 중복을 없애기 위해서 다음과 같이 바꿀 수 있다.

 

def numOperator(op: (Int, Int) => Int): (Expr, Expr) => Expr = {
  case (Num(x), Num(y)) => Num(op(x, y))
  case _ => throw new SimpleException("Expected numerical expressions")
}

 

여기서 op는 두 개의 Int를 받아서 어떤 연산을 수행하는 함수다.

 

val numAdd: (Expr, Expr) => Expr = numOperator(_ + _)  // 익명 함수로 + 연산
val numSub: (Expr, Expr) => Expr = numOperator(_ - _)  // 익명 함수로 - 연산

여기서 _ + _와 _ - _는 익명 함수로, (x: Int, y: Int) => x + y 같은 의미다.

이렇게 하면 더 깔끔하고 유지보수가 쉽다.

 

이제 대체 쪽 정의도 바꿔야 한다.

def subst(expr: Expr, idtf: Id, value: Expr): Expr = expr match {
  case Id(s) => if (s == idtf) value else expr
  case App(ftn, arg) => App(subst(ftn, idtf, value), subst(arg, idtf, value))
  case Fun(id, body) => if (id == idtf) expr else Fun(id, subst(body, idtf, value))
}

 

App(Id("f"), Id("x"))에서 x를 대체하면 함수는 그대로지만, 인자 x가 Num(3)으로 바뀌는 식으로 진행된다.

case Fun(id, body)에서 중요한 건 만약 함수의 매개변수 id가 우리가 대체하려는 식별자 idtf와 같다면, 대체를 멈춰야 한다. 그 이유는, 함수 내부에서 그 매개변수는 새롭게 바인딩되기 때문이다. 그래서 expr(즉, 함수 자체)을 그대로 반환한다.

 

예를 들어
with {x 3} {fun {x} {+ x y}}
이건 대체되는 x와 함수 인자 x가 같기 때문에 대체를 멈춘다.

with {x 3} {fun {y} {+ x y}}

이건 인자와 대체되는 값이 서로 다르기 때문에 대체를 진행하여 결과가 Fun(Id("y"), Add(Num(3), Id("y"))) 이렇게 된다.

 

자 그러면 이제 중요한 부분 또 알아보자

변수 대체가 어떻게 함수 안에서 알아서 진행이 될까?

 

subst(With(Id(y), Num(10), Id(z)), Id(z), Fun(Id(x), Add(Id(x), Id(y))))

이 부분에서 z라는 변수를 함수 fun {x} {+ x y}로 대체하려는 거다.

즉, z가 Fun(Id(x), Add(Id(x), Id(y)))로 바뀌는 과정이다.

대체 후에는 이렇게 바뀐다.

With(Id(y), Num(10), Fun(Id(x), Add(Id(x), Id(y))))

이 식은 with {y 10} {fun {x} {+ x y}}가 되는 거다. 이제 y가 함수 안에서도 나오는 상황이다.

이제 함수 내부의 y를 찾아 대체해주면 다음과 같다.

Fun(Id(x), Add(Id(x), Num(10)))

 

결론적으로 대체하려는 변수가 함수 내부에서 자유 변수(즉, 함수 안에 바인딩되지 않은 변수)일 때는 그 변수를 계속 찾아서 대체해줘야 한다. 그래서 y가 함수 바깥에서 정의된 값이니까, 함수 본문에서도 그 값을 찾아서 바꿔준 거다.

 

이제 일급 함수를 배우니 더 이상 with를 사용할 필요가 없어보인다.

함수 자체가 with 의 기능과 완벽히 일치할 수 있기 때문이다.

하지만 우리는 계속 with를 콘크리트 문법으로써 사용할 것이다.

왜냐하면 Snytax sugar로써 사용할 수 있기 때문이다.

 

그럼 이제 이렇게 일급함수로 바꿨으니까 대체의 연기 과정도 변경시켜줄 필요가 있다.

trait ExprValue
case class NumV(n: Int) extends ExprValue
case class ClosureV(param: Id, value: Expr, ds: DefrdSub) extends ExprValue

trait DefrdSub
case object MtSub extends DefrdSub
case class ASub(name: Id, value: ExprValue, saved: DefrdSub) extends DefrdSub

 

여기서 ClosureV와 ASub가 중요한 역할을 한다.

ExprValue는 값을 표현하는 추상 클래스다. 이 클래스를 상속받는 두 가지 값 타입이 있다.

 

  • NumV(n: Int): 숫자를 값으로 표현하는 클래스. NumV는 Num과 달리, 해석된 숫자 값을 의미.
  • ClosureV(param: Id, value: Expr, ds: DefrdSub): 클로저(Closure)를 표현하는 값. 함수 정의가 클로저로 저장되는데, 여기서 중요한 건 이 클로저가 변수를 바인딩한 환경(ds)도 함께 저장한다는 거다. 이렇게 하면 함수가 정의될 당시의 환경을 기억하고, 호출될 때 그 환경을 참고해서 변수 값을 사용할 수 있다.

DefrdSub는 지연된 대체(Deferred Substitution)를 관리하는 구조다.

 

  • MtSub: 비어 있는 대체 환경. 더 이상 대체할 것이 없을 때 이걸 사용.
  • ASub(name: Id, value: ExprValue, saved: DefrdSub): 특정 변수 name이 value로 대체될 때 사용. 여기서 saved는 기존 대체 환경을 저장하고 있다, 대체할 값들이 계속해서 누적되는 구조.

예시를 통해 작동 방식을 확인하자

interp(parse("{with {y 10} {fun {x} {+ y x}}}"), MtSub)

이 코드의 해석 과정은 이렇게 진행된다

  1. with {y 10}: y라는 변수를 10으로 바인딩. 이때 y의 값이 대체 환경(ASub)에 저장.
  2. fun {x} {+ y x}: 함수가 정의될 때, 현재의 대체 환경을 함께 저장해서 클로저가 만들어진다. 이 클로저에는 y = 10이라는 정보가 포함된다. ClosureV는 param = "x", value = {+ y x}, 그리고 대체 환경 ds = ASub("y", NumV(10), MtSub)로 표현.
  3. 이 클로저를 나중에 사용할 때도, 그 함수가 정의된 당시의 y = 10이라는 바인딩 정보가 유지되기 때문에, 동적 스코프(dynamic scope) 대신 정적 스코프(static scope)가 보장된다.

 

 

이제 이 모든 것을 때려박으면 다음과 같은 인터프리터가 된다.

def interp(expr: Expr, ds: DefrdSub): ExprValue = expr match {
  case Num(n) => NumV(n)
  case Add(l, r) => numAdd(interp(l, ds), interp(r, ds))
  case Sub(l, r) => numSub(interp(l, ds), interp(r, ds))
  case Id(s) => lookup(Id(s), ds)
  
  case Fun(p, b) => ClosureV(p, b, ds)
  
  case App(ftn, arg) =>
    val f_val = interp(ftn, ds)    // 함수를 평가
    val a_val = interp(arg, ds)    // 인자를 평가
    f_val match {
      case ClosureV(param, body, closure_ds) =>
        interp(body, ASub(param, a_val, closure_ds))
      case _ => throw new SimpleException("Expected a function")
    }
}

 

Fun(p, b) => ClosureV(p, b, ds) 이렇게 함수를 정의하면, 함수는 함수 본문과 정의된 환경을 함께 기억하게 된다. 이 클로저는 함수 호출 시 이 환경을 참조하게 돼서, 바깥에서 정의된 변수를 잊지 않게 되는 거다.

App(ftn, arg) 부분은 그 함수가 ClosureV인지 확인한 후, 본문을 실행한다.

case ClosureV(param, body, closure_ds)에서 ClosureV가 발견되면, 이제 함수 본문(body)을 실행한다. 여기서 중요한 건, 함수를 정의했을 당시의 환경(closure_ds)이 있다는 거다. 

case _ => throw new SimpleException("Expected a function") 이건 함수가 아닌 값이 함수처럼 호출됐다는 뜻이다.