About the definition of fixed-point combinators

Question

I am reading this wikipedia page to understand Fixed-point combinators:

In computer science, a fixed-point combinator (or fixpoint combinator[1]) is a higher-order function y that satisfies the equation, $y\ f = f\ (y\ f)$

• about the notation: if $y$ is a function, then do we write $y\ f$ instead of $y(f)$?
• is it implied that $y\ f$, which is a function, belongs to the domain of $f$?

(I hope I am not off-topic; my question is about the mathematical notation and definition rather than the application to computer science)

Answer 1

In lambda calculus the only operation is function application. Because it is so common, it is usually denoted by juxtaposition. It is read as a left-associative operation, parentheses are used for grouping only.

In real-number algebra, we usually use juxtaposition for multiplication, and thus we have to invent a different notation for functions.

The syntax goes: $$ T ::= \lambda V . T \mid T\; T \mid (T) \mid V $$ $$ V ::= x, y, z, \dots $$

The fixed-point combinator is necessary to implement recursion, seeing as there is no way to name a function definition in lambda calculus. Essentially it takes a function looking, for example, like this: $$ f(me, x_1, x_2) = x_1 + x_2\cdot me(x_1 + 1, x_2 - 1) $$ and replaces every instance of $me$ with $Y(f)$: $$ Y(f)(x_1, x_2) = x_1 + x_2\cdot Y(f)(x_1 + 1, x_2 - 1) $$

Answer 2

Function in lambda calculus bind to the left so $a b c d$ means $((a b) c) d$ where $x y$ means calling function $x$ with parameter $y$. Therefore you first call function $a$ with parameter $b$ then you get resulting function $u = (a b)$ and you call function $u$ with parameter $c$ and you get resulting function $v = (u c) = (a b) c$. Then you call $v$ with parameter $d$ so you get $v d = ((a b) c) d$ or omitting parentheses $v d = a b c d$. You should really start reading on some basic syntax of lambda calculus if you want to read about fixed-point combinators.