Can I pass function as a parameter?

[gsvgit]

Mazeppa produces error on the following version of map.

main(lst, op1, op2) := map(map(lst, op2), op1);

map(xs, op) := match xs {
    Nil() -> Nil(),
    Cons(x, xs) -> Cons(op(x), map(xs, op))
};

$ ./scripts/play.sh
error: No such f-function `op`
    note: While reducing `main(lst, op1, op2)` -> `map(map(lst, op2), op1)` -> `map(.g0(lst, op2), op1)` -> `map(Cons(op(.v0), map(.v1, op2)), op1)` -> `.g0(Cons(op(.v0), map(.v1, op2)), op1)` -> `Cons(op(op(.v0)), map(map(.v1, op2), op1))` -> `op(op(.v0))`

Does it mean that I can not pass function as a parameter or just my code is incorrect?

[hirrolot]

In Mazeppa, functions are second-class citizens: we treat them as meta-level term rewriting rules, and there is no way to reify them into objects. The reason behind this is that a first-order language is much easier to deal with, especially in the case of supercompilation; for example, we do not need to rename variables during substitution (avoiding name capture is known to make supercompilation "dreadfully slow" [^taming]).

Before releasing the first version, I did some experiments with first-class symbols, as in your example (i.e., just function symbols without environment capture). However, this turned out not so easy because undefined function symbols could end up in residual programs. For example:

main() := Combine(`f, `f, `f);

f(x) := Foo(x);

this would be supercompiled to:

main() := Combine(`f, `f, `f);

but since f is not called, it's simply removed by supercompilation.

Perhaps, Mazeppa could somehow detect those function symbols that lost their definitions during supercompilation. However, I decided to simply not deal with this problem.

Now, speaking of possible solutions:

1. Our object language is pretty close to Wadler's language for deforestation [^deforestation]. Wadler proposed so-called "higher-order macros" to regain some expressivity, which desugar to specialized higher-order functions such as map. Since we do not have higher-order macros (yet?), we can use any of existing preprocessors such as CPP or M4 or whatever and feed the result to Mazeppa. However, I don't think that this technique applies to your example, inasmuch as op1 and op2 are unknown variables.
2. In the README, there is an example that demonstrates how to supercompile the classical untyped lambda calculus using normalization-by-evaluation. This is a special case of metasystem transition: by writing an interpreter for a higher-order language, we can implement (simulate) first-class functions in Mazeppa. However, I think that it's only useful when the object language you're trying to supercompile is higher-order; if you just want to avoid duplication in Mazeppa code itself, the first option is better.
3. You can use defunctionalization. Assign unique identifiers to your functions, then write a routine that pattern-matches on the incoming ID and executes the appropriate function with the provided argument(s). Whenever you want to call a function, call this routine instead. This should work for your example, but beware of the issue that residual code may contain IDs of undefined functions.

Let's apply defunctionalization to your code snippet:

main(lst, op1, op2) := map(map(lst, op2), op1);

map(xs, op) := match xs {
    Nil() -> Nil(),
    Cons(x, xs) -> Cons(call(op, x), map(xs, op))
};

call(op, x) := match op {
    F() -> +(x, 5i32),
    G() -> /(x, 10i32),
    H() -> *(x, x)
};

After supercompilation:

main(lst, op1, op2) := f1(lst, op1, op2);

f0(x0, x1) := match x1 {
    F() -> +(x0, 5i32),
    G() -> /(x0, 10i32),
    H() -> *(x0, x0)
};

f1(x0, x1, x2) := match x0 {
    Cons(x3, x4) -> Cons(f0(f0(x3, x2), x1), f1(x4, x1, x2)),
    Nil() -> Nil()
};

Works as expected: the intermediate list was completely eliminated.

I hope this answer was helpful.

[^taming]: Jonsson, Peter & Nordlander, Johan. (2011). Taming code explosion in supercompilation. PERM'11 - Proceedings of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation. 33-42. 10.1145/1929501.1929507.

[^deforestation]: Philip Wadler. 1988. Deforestation: transforming programs to eliminate trees. Theor. Comput. Sci. 73, 2 (June 22, 1990), 231–248. https://doi.org/10.1016/0304-3975(90)90147-A

[hirrolot]

@gsvgit, did I answer your question?

[gsvgit]

Sure! Thank you.