如何确保命名参数列表的评估顺序和形式参数顺序？

Question

在编译器上工作时，我遇到了一个与命名参数列表和求值顺序相关的问题。基本上，该语言确保对于以下函数和函数调用：

int call(int first, int second) = first - second

int sideEffect(int i) { println(i); return i }

println(call(second: sideEffect(0), first: sideEffect(1)))

输出将是

0
1
1

虽然参数是以相反的顺序给出的。我在 JVM 上工作，因此必须在字节码级别对它们进行排序以匹配 call 的签名。在基于堆栈的伪字节码中：

push 0
call sideEffect(int)
push 1
call sideEffect(int)
swap
call call(int, int)

如您所见，此处需要 swap 字节码指令以确保它们都以正确的顺序进行评估和传递。这可以画成图表：

Actual:   second   first
                \ /
                swap
                / \
Formal:    first   second

只有一条swap指令可以交换栈顶的两个元素，所以对于更多的元素，编译器需要生成局部变量。

Actual: third   second   first
          |       |  /¯¯¯¯
        local0   swap    local0
            ____/ |        |
Formal: first   second   third

在字节码中：

third...
store local0
second...
first...
swap
load local0
call ...

当然这可以扩展到任意数量的实际和形式参数。

我现在正在寻找的是某种算法，它可以确定是否以及在何处插入这些 swap 或局部变量指令。对编译器实现的引用也会有所帮助。

请注意，不是我的问题的一部分，实参属于哪个形参。我的编译器已经解决了。为了简化，问题可以这样看：

给定两个包含相同元素但顺序不同的相同大小的数组，可以从第一个数组交换或移动哪些元素以获得第二个数组的顺序。

Answer 1

只有寄存器，基本上只有一种解决方案。以所需的堆栈顺序遍历参数。如果已经计算了当前参数，则从本地加载它。否则，按执行顺序计算它之前未计算的参数，将它们存储在寄存器中，然后计算当前参数。

swap操作的存在意味着我们可以使用栈顶作为事实上的局部变量。 Python 下面的代码。

import heapq
import itertools


class Allocator:

  def __init__(self):
    self.free_heap = []
    self.next_free = 0

  def allocate(self):
    if self.free_heap:
      return heapq.heappop(self.free_heap)
    i = self.next_free
    self.next_free += 1
    return i

  def free(self, i):
    heapq.heappush(self.free_heap, i)

  def is_allocated(self, i):
    return i < self.next_free and i not in self.free_heap


def loads_and_stores(perm):
  perm = list(perm)
  n = len(perm)
  assert set(perm) == set(range(n))
  location = {}
  allocator = Allocator()
  i = iter(perm)
  # "location 0" is the top of the stack
  for j in range(n):
    if j in location:
      if location[j] != 0:
        # not top of stack; need an actual load
        print 'load', location[j]
        if allocator.is_allocated(0):
          # need to maintain the top of the stack
          print 'swap'
      allocator.free(location[j])
    else:
      while True:
        k = next(i)
        print 'compute', k
        if k == j:
          if allocator.is_allocated(0):
            # need to maintain the top of the stack
            print 'swap'
          break
        location[k] = allocator.allocate()
        if location[k] != 0:
          # not top of stack; need an actual store
          print 'store', location[k]
  return perm


def test(n):
  for perm in itertools.permutations(range(n)):
    print perm
    loads_and_stores(perm)


test(4)

这里有一些有趣的优化，因为 allocate 可以 return 任何免费本地。最佳算法会考虑进行每次分配的执行成本。

如何确保命名参数列表的评估顺序和形式参数顺序？

How to ensure evaluation order and formal parameter order for named argument lists?

algorithm

compiler-construction

associations

postfix-notation

jvm-bytecode