Using a higher order SML code, Write Nested Functions in Java

Question

I am working on my assignment right now on nested functions but in java which isn't possible. We were thought about nested functions in SML. Since, nested functions arent allowed in many languages, we were thought activation records with nested links. However, we were thought how to do these in diagrams and theory and expected to do in Java but I got no clue how to do these in Java as we didn't even get any examples from him. I tried searching something on google but all the references I found were very basic and weren't really helpful. I would take any help on this one.

Following is the code in SML which we were supposed to code in Java.

fun h (x,y) =
  let
    val z = x+1
    fun g w =
      let
        val z = y + 1
        fun f x =
          if x = 0 then 0
          else z + x + g(w - 1)
      in
        if w = 0 then x
        else z + f(w - 1)
      end
  in
    if x = 0 then g y
    else z + g(h(x - 1, y))
  end;

Following is the code I tried till now but couldn't really get anything.

public int f(int w, int x, int y, int z) {
    if (x == 0) {
        return 0;
    } 
    else {
        return (z + x + g(w - 1, y));
    }
}

public int g(int w, int y) {
    int z = y + 1;
    return z;
}

public void h(int w, int x, int y) {
    int z = x + 1;
    g(w, y);
    f(w, x, y, z);
}

public void last(int w, int x, int y, int z) {
    
}

Following are the details given in the assignment:

Consider the ML function defined in the right box, where function g is nested in function h, and function f is nested in function g. You may type this function in a text file and in ML environment use ”use” to load the function and try some input to see the results. This is a function that grows rapidly. This assignment is asking you to use Java where nested functions are not supported to compute function h on some inputs. As you will see, this function grows rapidly.

You can make recursive calls in your java program to simplify your task, but since Java does not allow you to define nested functions, you have to use the technique of activation records with nesting links to solve non-local variables defined in outer functions. You have to explain how do you solve the non-local variable problem in your report. Hint: You can pass a pointer of an activation record to the called function, which serves as the nested link the called function may need. Every activation record should contain the following information:

1. Name of the function the activation record belongs to.
2. A symbol table that contains all local variables and their values.
3. Return address, the point to continue when current function is done and the previous activation record (i.e, the caller) resumed.
4. A pointer to the previous activation record (i.e, the caller’s activation record).
5. Nesting link to resolve non-local variables.
6. A place to save the result of this computation (the value to return). Since this is just a simulation to compute the specific functions defined above, you don’t have to design a universal activation records for every possible function. You can define three different activation records foe the three different ML functions defined above.

---

These are the instructions given straight from the assignment.

Answer 1

Not sure why the task suggests using activation records. There is a general technique called lambda lifting for transforming local functions into global: simply add every non-local variable that a function uses as an additional parameter. That is sufficient as long as the local functions aren't used in a first-class manner as closures. Your attempt already goes in the right direction, here is how I would fix it:

public int f(int x, int g_z, int g_w, int h_x, int h_y) {
  if (x == 0) {
    return 0;
  } else {
    return g_z + x + g(g_w - 1, h_x, h_y);
  }
}

public int g(int w, int h_x, int h_y) {
  int z = h_y + 1;
  if (w == 0) {
    return h_x;
  } else {
    return z + f(w - 1, z, w, h_x, h_y);
  }
}

public int h(int x, int y) {
  int z = x + 1;
  if (x == 0) {
    return g(y, x, y);
  } else {
    return z + g(h(x - 1, y), x, y);
  }
}