algorithm - 什么是枚举 lambda 项的算法？

Question

按长度顺序枚举 lambda 演算表达式的算法是什么？比如(λx.x), (λx.(x x)), (λx.(λy.x))等等？

Answer 1

作为长度，我会在这个(无类型的)lambda 表达式的 BNF 中选择 T-expansions(“深度”)的数量:

V ::= x | y
T ::= V    | 
      λV.T |
      (T T)

在 python 中，您可以按照上述生成规则为给定变量和给定深度定义一个生成器，如下所示:

def lBNF(vars, depth):
  if depth == 1:
    for var in vars:
      yield var
  elif depth > 1:
    for var in vars:
      for lTerm in lBNF(vars,depth-1):
        yield 'l%s.%s' % (var,lTerm)
    for i in range(1,depth):
      for lTerm1 in lBNF(vars,i):
        for lTerm2 in lBNF(vars,depth-i):
          yield '(%s %s)' % (lTerm1,lTerm2)

现在您可以枚举给定深度的 lambda 项:

vars = ['x','y']
for i in range(1,5):
  for lTerm in lBNF(vars,i):
    print lTerm