jjzjj

javascript - 在 JavaScript 中用 SKI-Combinators 表达 Y

coder 2024-12-23 原文

我正在摆弄 JavaScript 中的组合子，并为(希望)让 S 工作而感到自豪，这时我偶然发现维基百科说:“Y 组合子可以在 SKI 演算中表示为:Y = S (K (S I I )) (S (S (K S) K) (K (S I I)))"，所以我不得不尝试:

var I = function (x) {
            return x;
        };
    
var K = function (x) {
        return function(){
            return x;}
        };

var S = function (x) {
           return function (y) {
               return function (z) {
                   return x(z)(y(z));
               }
           }
       };

var Y = S (K(S(I)(I))) (S(S(K(S))(K)) (K(S(I)(I))));

Y;    //evals to:
//function (z) {return x(z)(y(z));}

//And this (lifted from Crockford's Site):
var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});    //fails:
//RangeError: Maximum call stack size exceeded

我做错了什么？我没有正确翻译那个表达吗？我这样做有什么问题吗？它甚至有意义吗？大多数要阅读的关于此类内容的内容只会让我的大脑想要爆炸，所以对我来说，这个练习的重点主要是看看我是否理解该符号(并因此能够将其翻译成 JavaScript)。

哦，顺便说一下:让我再次阅读和摆弄的是 prototype.js 作为 Prototype.K 实现的实际上是 I 组合器。有人注意到了吗？

最佳答案

这里的问题是您使用的是经过严格评估的编程语言。 Y 组合器与任何其他定点组合器非常相似，只有在您的函数根据需要调用或“延迟计算”时才能正常工作。

我知道一种解决此问题的方法 (one of my professors looked into it a while ago)，但它会使您的代码完全不可读。

下面我展示了具体情况，希望您能明白为什么 JavaScript 无法处理 SKI 演算的直接实现。

这是 Y 在 JavaScript 评估你的 SKI 表达式后的样子:

var Y = function (q) {
    return (function(p){return q(p(p))})(function(p){return q(p(p))});
};

现在让我们看看如果将函数 function (fac) { ... } 提供给它会发生什么。我们称该函数为 f:

var factorial = (function(p){return f(p(p))})(function(p){return f(p(p))});

由于第一个匿名函数应用于一个参数，它将被计算为:

var factorial = f(
    (function(p){return f(p(p))})(function(p){return f(p(p))})
);

在惰性求值语言中，f 的参数现在将被单独保留，而 f 本身将被求值。然而，由于 JavaScript 是一种严格评估的语言(或“按值调用”)，它想知道在实际运行该函数之前需要将什么参数传递给函数 f。那么让我们评估一下这个论点，好吗？

var factorial = f(f(
        (function(p){return f(p(p))})(function(p){return f(p(p))})
    )
);

我猜你现在开始明白哪里出了问题，以及 Y 组合器的实际工作原理。在任何情况下，您的 JavaScript 机器都会耗尽堆栈空间，因为它正在尝试构建对 f 的无限调用堆栈。

关于javascript - 在 JavaScript 中用 SKI-Combinators 表达 Y，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7368507/

SKI-Combinators中用functioncodereturnjavascriptcombinatorsy-combinatorcombinatory-logic

有关javascript - 在 JavaScript 中用 SKI-Combinators 表达 Y的更多相关文章

  1. ruby - 在 Ruby 中用键盘诅咒数组浏览 - 2

    我正在尝试在Ruby中制作一个cli应用程序，它接受一个给定的数组，然后将其显示为一个列表，我可以使用箭头键浏览它。我觉得我已经在Ruby中看到一个库已经这样做了，但我记不起它的名字了。我正在尝试对soundcloud2000中的代码进行逆向工程做类似的事情，但他的代码与SoundcloudAPI的使用紧密耦合。我知道cursesgem，我正在考虑更抽象的东西。广告有没有人见过可以做到这一点的库或一些概念证明的Ruby代码可以做到这一点？ 最佳答案 我不知道这是否是您正在寻找的，但也许您可以使用我的想法。由于我没有关于您要完成的工作

  2. ruby - 有没有办法从 ruby​​ case 语句中访问表达式？ - 2

    我想从then子句中访问c​​ase语句表达式，即food="cheese"casefoodwhen"dip"then"carrotsticks"when"cheese"then"#{expr}crackers"else"mayo"end在这种情况下，expr是食物的当前值(value)。在这种情况下，我知道，我可以简单地访问变量food，但是在某些情况下，该值可能无法再访问(array.shift等)。除了将expr移出到局部变量然后访问它之外，是否有直接访问caseexpr值的方法？罗亚附注我知道这个具体示例很简单，只是一个示例场景。 最佳答案

  3. ruby-on-rails - 使用 javascript 更改数据方法不会更改 ajax 调用用户的什么方法？ - 2

    我遇到了一个非常奇怪的问题，我很难解决。在我看来，我有一个与data-remote="true"和data-method="delete"的链接。当我单击该链接时，我可以看到对我的Rails服务器的DELETE请求。返回的JS代码会更改此链接的属性，其中包括href和data-method。再次单击此链接后，我的服务器收到了对新href的请求，但使用的是旧的data-method，即使我已将其从DELETE到POST(它仍然发送一个DELETE请求)。但是，如果我刷新页面，HTML与"new"HTML相同(随返回的JS发生变化)，但它实际上发送了正确的请求类型。这就是这个问题令我困惑的

  4. python - python中有没有类似于ruby的||=的表达式 - 2

    我在Ruby中遇到了一个有趣的表达式:a||="new"表示如果没有定义a，则将"new"值赋给a；否则，a将保持原样。在进行一些数据库查询时很有用。如果设置了该值，我不想触发另一个数据库查询。所以我在Python中尝试了类似的思路:a=aifaisnotNoneelse"new"失败了。我认为这是因为如果未定义a，则无法在Python中执行“a=a”。所以我能得出的解决方案是检查locals()和globals()，或者使用try...except表达式:myVar=myVarif'myVar'inlocals()and'myVar'inglobals()else"new"或try:

  5. ruby - 在 Mechanize 中使用 JavaScript 单击链接 - 2

    我有这个:AccountSummary我想单击该链接，但在使用link_to时出现错误。我试过:bot.click(page.link_with(:href=>/menu_home/))bot.click(page.link_with(:class=>'top_level_active'))bot.click(page.link_with(:href=>/AccountSummary/))我得到的错误是:NoMethodError:nil:NilClass的未定义方法“[]” 最佳答案 那是一个javascript链接。Mechan

  6. javascript - jQuery 的 jquery-1.10.2.min.map 正在触发 404(未找到) - 2

    我看到有关未找到文件min.map的错误消息:GETjQuery'sjquery-1.10.2.min.mapistriggeringa404(NotFound)截图这是从哪里来的？ 最佳答案 如果ChromeDevTools报告.map文件的404(可能是jquery-1.10.2.min.map、jquery.min.map或jquery-2.0.3.min.map，但任何事情都可能发生)首先要知道的是，这仅在使用DevTools时才会请求。您的用户不会遇到此404。现在您可以修复此问题或禁用sourcemap功能。修复:获取文

  7. ruby-on-rails - 我将 Rails3 与 tinymce 一起使用。如何呈现用户关闭浏览器javascript然后输入xss？ - 2

    我有一个用Rails3编写的站点。我的帖子模型有一个名为“内容”的文本列。在帖子面板中，html表单使用tinymce将“content”列设置为textarea字段。在首页，因为使用了tinymce，post.html.erb的代码需要用这样的原始方法来实现。.好的，现在如果我关闭浏览器javascript，这个文本区域可以在没有tinymce的情况下输入，也许用户会输入任何xss，比如alert('xss');.我的前台会显示那个警告框。我尝试sanitize(@post.content)在posts_controller中，但sanitize方法将相互过滤tinymce样式。例如

  8. Ruby 缺少常量表达式优化？ - 2

    我希望Ruby的解析器会进行这种微不足道的优化，但似乎并没有(谈到YARV实现，Ruby1.9.x、2.0.0):require'benchmark'deffib1a,b=0,1whileb由于这两种方法除了在第二种方法中使用预定义常量而不是常量表达式外是相同的，因此Ruby解释器似乎在每个循环中一次又一次地计算幂常数。是否有一些Material说明为什么Ruby根本不进行这种基本优化或只在某些特定情况下进行？ 最佳答案 很抱歉给出了另一个答案，但我不想删除或编辑我之前的答案，因为它下面有有趣的讨论。正如JörgWMittag所说，

  9. ruby - 使用 Selenium WebDriver 启用/禁用 javascript - 2

    出于某种原因，我必须为Firefox禁用javascript(手动，我们按照提到的步骤执行http://support.mozilla.org/en-US/kb/javascript-settings-for-interactive-web-pages#w_enabling-and-disabling-javascript)。使用Ruby的SeleniumWebDriver如何实现这一点？ 最佳答案 是的，这是可能的。而是另一种方式。您首先需要查看链接Selenium::WebDriver::Firefox::Profile#[]=

  10. ruby - `+` 在 `*` 之后的含义，当后者在正则表达式中用作量词时 - 2

    今天我遇到了下面的正则表达式，想知道Ruby会用它做什么:>"#a"=~/^[\W].*+$/=>0>"1a"=~/^[\W].*+$/=>nil在这种情况下，Ruby似乎忽略了+字符。如果这是不正确的，我不确定它在做什么。我猜它没有被解释为量词，因为*没有转义并且被用作量词。在Perl/Ruby正则表达式中，有时当一个字符(例如，-)在不能被解释为特殊字符的上下文中使用时，它会被视为文字。但如果在这种情况下发生这种情况，我希望第一个匹配失败，因为左值字符串中没有+。这是对+字符的巧妙正确使用吗？以上行为是错误吗？我是否遗漏了一些明显的东西？ 最佳答案

随机推荐