0
$\begingroup$

There are at least two ways to flatten out a nested function. Both of them need to keep a certain amount of state to accomplish this. The two ways are:

  1. By creating several boolean variables for each part of the function.
  2. By creating a tree data structure that is navigated.

Say we have this function system:

function a(p) {
  var x = b(p)
  var y = c(p)
  return x + y
}

function b(p) {
  var x = d(p)
  var y = e(p)
  var z = f(p)
  return x - y * z
}

function c(p) {
  return p * 2
}

function d(p) {
  return c(p) + 3
}

function e(p) {
  return 3 * c(p) + 2
}

function f(p) {
  return 1 - d(p)
}

Then the first part of it could be represented by boolean variables (1) like this:

a_start
a_end
ab_start
ab_end
abd_start
abd_end
abdc_start
abdc_end
...

Then the evaluation would be along the lines of:

if (!a_start) {
  a_start = true
}
if (a_start && !ab_start) {
  ab_start = true
}
if (a_start && ab_start && !abd_start) {
  abd_start = true
}
if (a_start && ab_start && abd_start && !abdc_start) {
  abdc_start = true
}
if (a_start && ab_start && abd_start && abdc_start && !abdc_end) {
  abdc_val = p * 2
  abdc_end = true
}
if (a_start && ab_start && abd_start && !abd_end && abdc_end) {
  abd_val = abdc_val + 3
  abd_end = true
}
if (a_start && ab_start && abd_start && abd_end) {
  ab_x_val = abd_val
  ...
}

It gets confusing really quick and I'm not sure (a) if I'm exactly doing it right or (b) if it's even possible this way. But it seems like it is. In addition, all of these boolean checks would add up, so I'm not sure it would be as efficient as the nested method.

The other way (2) is instead creating a tree data structure and navigating that. This is roughly how it would look:

var base = {}
while (true) { ... } leads to:

a = { label: 'a', parent: base }
b = { label: 'b', parent: a }
d = { label: 'd', parent: b }
c = { label: 'c', parent: d, val: p * 2 }
next = c.parent = d
d.val = c.val + 3
next = d.parent = b
b.val = d.val
...

This seems closer to the stack approach like in normal iterative techniques.

The questions are:

  1. If it's possible to represent the nested function system as (1) boolean expressions with a while loop and/or (2) a tree datastructure with a while loop.
  2. If so, if it is possible to do it as efficiently (or more efficiently) than the corresponding nested version in either (1) or (2).
  3. If either way (1) or (2) is "better" than the other. (I am not considering the nested version as part of the better equation, since the nested one is easiest to understand). It seems that way (1) is closer to a rule-based system, and uses minimal memory, while (2) is less brittle, a bit easier to understand, and might have better performance, but might use more memory. Also, (1) seems like it might be more robust, in that you can be at "multiple places at once" theoretically (so you could do multiple nesting branches at the same time), whereas in (2) you're always at one point in the tree. Also, I don't think I am modeling (1) correctly, since each iteration it will reevaluate the same expression over and over again until the booleans are false. This doesn't happen in the tree version. Maybe the booleans need to be more like the tree nodes somehow...
  4. If there are any alternative "iterative" (flat) ways of simulating the nested function that would be helpful to be aware of.
$\endgroup$
  • $\begingroup$ I don't think memory in (2) would be a big issue as long as you don't implement it with a lot of overhead. Considering nested functions already use memory in the stack, and would essentially act like a tree, you're just moving the memory used elsewhere and making it more explicit. What is your goal of flattening these functions? You could just in-line all of them if you really wanted (if they're this simple). $\endgroup$ – ryan Jul 1 '18 at 19:54
  • $\begingroup$ CPS transform, defunctionalize. $\endgroup$ – Derek Elkins Jul 1 '18 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.