将其论证应用于自身的函数？

Question

考虑以下SML函数:

fn x => x x

这会产生以下错误(新泽西标准ML v110.72):

stdIn:1.9-1.12 Error: operator is not a function [circularity]
  operator: 'Z
  in expression:
    x x

我可以理解为什么这是不允许的 - 一方面,我不确定如何写下它的类型 - 但它并非完全没有意义; 例如,我可以将身份函数传递给它并将其恢复.

这个功能有名字吗？(有没有办法在SML中表达它？)

Answer 1

无法用具有ML类型系统的语言表达此功能.即使使用标识功能,它也不起作用,因为第一个x和第二个x x必须是该函数的不同实例,类型(_a -> _a) -> (_a -> _a)和_a -> _a某些类型的实例_a.

事实上,类型系统被设计为禁止类似的结构

(?x . x x) (?x . x x)

在无类型的lambda演算中.在动态类型语言Scheme中,您可以编写此函数:

(define (apply-to-self x) (x x))

并获得预期的结果

> (define (id x) x)
> (eq? (apply-to-self id) id)
#t