Guys, your language is functional. So, you have functions, right? Are your functions "actually" binary relations with properties? Do your functions consists of pairs (x,y) such that...?

If yes, where do you keep all those sets?

If not, what's your definition of "function"?

An update: here's what people say on Stackoverflow: 

"each type being an object in Hask and each function being an arrow between the argument type and the return type"

"In Haskell, a function is something which maps some input to an output. A function is a value which you can apply to some other value to get a result."

See, no sets involved. No sets. Haskell programming language is not based on set theory (neither is lambda).

Уже чуть не месяц прошел. Присоветовали добрые люди МакБрайда с Патерсоном перепереть на язык родных Скал. Перепёр - не работает. Только что багу у себя нашел. Теперь работает.

implicit def ski[env,a,b](ef:env=>a=>b) = new { val S = (ea:env=>a) => (e:env) => ef(e)(ea(e))}
def K[env,a](x:a) = (gamma:env) => x
type E = Any => Int
def KEnv[X](x: X) = K[E, X](x)

val add = (i: Int) => (j: Int) => i+j

def fetch(x: String) = (env: E) => env(x)
trait Expr
case class Var(x: String)        extends Expr
case class Val(i: Int)           extends Expr
case class Add(p: Expr, q: Expr) extends Expr

def eval(exp: Expr): (E => Int) = exp match {
  case Var(x) => fetch(x)
  case Val(i) => KEnv(i)
  case Add(p,q) => KEnv(add) S eval(p) S eval(q)
}

eval(Add(Var("one"),Add(Var("three"), Val(11))))(Map("one" -> 1, "two" -> 2, "three" -> 3))

Пойду на огороде поработаю, на велике покатаюсь, и дальше чесать.