개요
First-order 함수는 function의 인자로 다른 함수를 받거나, return으로 함수를 내보내지 못하는 함수를 의미한다.
Environment(Env)를 다음과 같이 Id를 특정 값으로 매핑하는 집합이라고 하자 (즉, val x= 5; 에서 x가 어떤 값인지를 찾아주는 집합이다). 이떄 Env 를 다음과 같이 정의하면:
- [math]\displaystyle{ Env \,\, \sigma \in Id \rightarrow (Id \times Expr) }[/math]
First-order 함수(Func, Func(x) => e)는 다음과 같이 정의할 수 있다.
- [math]\displaystyle{ \begin{array}{c} {x\in\mathit{Domain}(\sigma) } \\\hline {\sigma,Func\vdash x\Rightarrow \sigma(x)} \end{array} }[/math]
- Domain의 의미는 x가 함수가 받는 인자와 같은 타입임을 의미한다.
Abstract syntax를 통해서 나타내면 다음과 같다.
case App(f, a) =>
val (x, e) = lookupFD(f, fEnv)
interp(e, Map(x -> interp(a, env, fEnv)), fEnv)