Method Calls

It might seem that methods are very straightforward, and if you stick to the method calls in the javainterop package, then there should be no surprises. However, JFuncMachine provides CallMethod, CallStaticMethod, CallTailCallMethod, and CallTailCallStaticMethod.

Tail Calls

One of the common features of functional programming languages is that they support tail call optimization. This means that when a function calls another function from the tail position - that is, when the function call is the return value of the calling function, then the new function call can reuse the stack space of the current function. The upshot of this is that tail calls can recurse infinitely without overflowing the stack.

Tail Call Example in Java

In case this definition of a tail call seems hazy, here are two examples of a factorial function in Java:

public class Factorials {
  public static int fact1(int n) {
    if (n < 2) {
      return 1;
    } else {
      return n * fact1(n-1);
    }
  }

  public static int fact2(int n, int acc) {
    if (n < 2) {
      return acc;
    } else {
      return fact2(n-1, n*acc);
    }
  }

  public static void main(String[] args) {
    System.out.println(fact1(10));
    System.out.println(fact2(10, 1));
  }
}

First, look at the fact1 function. It looks like the recursive call to itself is the very last thing that is done in the function, but that’s not the case. It has to wait for the result of the recursive call so it can then multiply it by n and return it. So the recursive call in fact1 is not in the tail position.

fact2, on the other hand is just returning the result of its recursive call, so the recursive call in fact2 is in the tail position.

Java does not currently support tail call optimization, but JFuncMachine has some ways to implement it.

Local Calls

The simplest form of tail call optimization occurs when a function calls itself from the tail position. In this case, JFuncMachine automatically converts the function call into a jump, where it first replaces the local variables representing the function/method parameters with the values that are being passed to the new call. Then when it jumps back to the beginning of the function, this is the equivalent of a recursive call, but does not take additional stack space. This function can be disabled by setting the generator option localTailCallsToLoops to false.

If you disable localTailCallsToLoops, you can still access that capability. Instead of making a recursive function call, you can use the LocalRecurse expression, which does the same jump back to the beginning of the function.

Full Tail Calls

JFuncMachine also has a mechanism to implement full tail calls, and can even do so automatically, but this option is off by default because it is much less efficient than a normal function call, and you may want to selectively flag methods as being tail-callable.

The way JFuncMachine does tail calls is that it changes all the return values of tail-callable functions to Object. When a function returns a value that isn’t a tail call, then it returns an object version of that value (i.e. boxed if it is a native type). Otherwise, if a function’s return value is a tail call, it returns a tail-call lambda. Then, whenever a function is called from a non-tail position, it checks to see if the returned value is one of these lambdas, and if so, it invokes the lambda, and continues to do so as long as it sees that lambda as a result.

When JFuncMachine generates tail-callable methods automatically, it generates two versions of the method - one that uses the normal calling convention and doesn’t do tail call optimization, and another that does support the tail calling conventions, and has as $$TC$$ appended to its method name. This means that you can expose methods to Java classes and the Java classes don’t have to understand the tail call optimization because they won’t be using it. But, for methods that are generated within JFuncMachine, you can get TCO without having to write it explicitly.

Now, if you decide to keep the automatic TCO turned off, you can still enable it in specific methods by setting the isTailCallable flag to true, and then using CallTailCallMethod or CallTailCallStatic method to invoke it.

Example Local Tail Call

The following function, if compiled without disabling the localTailCallsToLoops option will result in a function that returns a value after looping 100 million times. This same function, if compiled with localTailCallsToLoops set to false, but fullTailCalls set to true, will also return the correct value without a stack overflow. However, if both options are false, the call will fail with a stack overflow.

MethodDef method = new MethodDef("summer", Access.PUBLIC + Access.STATIC, new Field[] {
    new Field("n", SimpleTypes.INT),
    new Field("acc", SimpleTypes.INT) },
    SimpleTypes.INT,
    new If(new BinaryComparison(Tests.LT, new GetValue("n", SimpleTypes.INT),
        new IntConstant(2)),
        new GetValue("acc", SimpleTypes.INT),
        new CallStaticMethod("summer", new Type[] { SimpleTypes.INT, SimpleTypes.INT },
            SimpleTypes.INT,
            new Expression[] {
                new InlineCall(Inlines.IntSub, new Expression[] {
                    new GetValue("n", SimpleTypes.INT),
                    new IntConstant(1)
                }),
                new InlineCall(Inlines.IntAdd, new Expression[] {
                    new GetValue("n", SimpleTypes.INT),
                    new GetValue("acc", SimpleTypes.INT)
                })
    })));

Tail Recursive Lambdas

Lambda functions are anonymous functions, so the notion of making a recursive lambda is a bit odd. But, in some languages it is possible to do this by assigning the lambda to a symbol and then referring to that symbol within the lambda. This is difficult in Java because of the way are implemented. Any symbol used by the lambda that isn’t one of its arguments “captured” variable. In Java, the captured variables are passed to a bootstrap method that creates the lambda (both the Java compiler and JFuncMachine do this for you automatically), and since the lambda doesn’t exist at the time you are calling the method to create it, it can’t capture a self-reference.

As far as JFuncMachine goes, there are two ways that a lambda can call itself recursively. First, it can use the LocalRecurse expression to call itself locally. Or, it can use CallStaticMethod without supplying a class name or method name.

JFuncMachine does not implement full tail call optimization for lambdas, so if you disable the local tail call optimization and a lambda recursively calls itself with CallStaticMethod, there will be no tail call optimization and the stack will grow with each recursive call. Note that the body of a lambda function is turned into a static method, which is why you use CallStaticMethod when making a recursive lambda call.

If you think that you might disable the local tail call optimization, and you want to allow lambdas to call themselves recursively, you should consider using LocalRecurse for those calls to at least let lambdas do recursive tail calls that don’t take up more stack space.

Here is an example Lambda method that uses LocalRecurse to call itself:

new Lambda(new Field[]{
        new Field("n", SimpleTypes.INT),
        new Field("acc", SimpleTypes.INT)
}, SimpleTypes.INT,
        new If(new BinaryComparison(Tests.LT,
                new GetValue("n", SimpleTypes.INT),
                new IntConstant(2)),
                new GetValue("acc", SimpleTypes.INT),
                new LocalRecurse(SimpleTypes.INT, new Expression[] {
                        new InlineCall(Inlines.IntSub, new Expression[] {
                                new GetValue("n", SimpleTypes.INT),
                                new IntConstant(1)
                        }),
                        new InlineCall(Inlines.IntMul, new Expression[] {
                                new GetValue("n", SimpleTypes.INT),
                                new GetValue("acc", SimpleTypes.INT)
                        })
                })))

Here is the same lambda using CallStaticMethod:

new Lambda(new Field[]{
        new Field("n", SimpleTypes.INT),
        new Field("acc", SimpleTypes.INT)
}, SimpleTypes.INT,
        new If(new BinaryComparison(Tests.LT,
                new GetValue("n", SimpleTypes.INT),
                new IntConstant(2)),
                new GetValue("acc", SimpleTypes.INT),
                new CallStaticMethod(
                        new Type[] { SimpleTypes.INT, SimpleTypes.INT },
                        SimpleTypes.INT, new Expression[] {
                        new InlineCall(Inlines.IntSub, new Expression[] {
                                new GetValue("n", SimpleTypes.INT),
                                new IntConstant(1)
                        }),
                        new InlineCall(Inlines.IntMul, new Expression[] {
                                new GetValue("n", SimpleTypes.INT),
                                new GetValue("acc", SimpleTypes.INT)
                        })
                })))