5 ms·
Anonymous recursive functions in Racket
- userbinator 1y agoA relevant article to the domain name of this site.
- drivenextfunc 1y agoIf you look at the code, you'll be (unpleasantly) surprised, I think. The author does not seem to have known what Y combinator is.
- almostgotcaught 1y agoThese are my favorite types of comments on hn
- neilv 1y agoThe HN guidelines suggest assuming the strongest interpretation of what someone said, so obviously the commenter was making a joke. :)
- plaitowin 1y agoI'm pretty sure Shriram Krishnamurthi understands the Y combinator...
- srpablo 1y agolmao Google him
- Philpax 1y agohttps://en.wikipedia.org/wiki/Shriram_Krishnamurthi https://en.wikipedia.org/wiki/Shriram_Krishnamurthi
- skrishnamurthi 1y agoDon't see Y-combinator mentioned anywhere on that page.
- adityaathalye 1y agoBut I do see that page mentioned on Y Combinator's page. The joke can go on forever...
- shawn_w 1y agoSomebody forgot to add a base case.
- adityaathalye 1y agoNo need... Shriram is already based.
- skrishnamurthi 1y agoIf it helps, you will find the Y-combinator described (indeed, derived) in the first edition (https://cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/ https://cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-0...) of the author's programming languages book (https://www.plai.org/ https://www.plai.org/). (Page 228, if that helps, though the derivation begins on page 223.) For added fun, the day he teaches it in class, he wears a t-shirt from Y-combinator the startup accelerator (and explains what its name means). Now that we've gotten that out of the way, it remains unclear what is surprising or unpleasantly surprising about the code.
- adityaathalye 1y agoShriram invoking Shriram ... (λ.x (x x) λ.x (x x)) forever \m/ :)
- userbinator 1y agoThis reminds me of when John Nagle showed up in a thread about his algorithm on here.
- blahedo 1y agoIn addition to the general sibling comments, I can personally attest that Shriram knows what the Y combinator is and has been teaching students about it for at least 25 years. My own lecture notes from one of his classes about the lambda calculus and the Y combinator were for a long time on the front page of google results for info about either!
- CyberDildonics 1y agoI would rather use a loop so I can debug it.
- treyd 1y agoTail-recursive functions in Racket are optimized down to essentially for loops.
- skrishnamurthi 1y agoThis isn't meant to be a good programming mechanism, it's meant to be an illustration of how to use the macro system. But also, if you're processing non-linear data, you're going to want to do with a recursive function anyway. E.g., when dealing with a tree. Code below; can't seem to get multi-line code-formatting so it looks hideous: #lang racket (require "anon-rec.rkt") (require rackunit) (struct mt ()) (struct node (v l r)) (define sum-tree (lam/anon (t) (cond [(mt? t) 0] [(node? t) (+ (node-v t) ($MyInvocation (node-l t)) ($MyInvocation (node-r t)))]))) (define t (node 5 (node 3 (mt) (mt)) (node 7 (node 9 (mt) (mt)) (mt)))) (check-equal? (sum-tree t) 24)
- CyberDildonics 1y agoRecursion just ends up using the call stack as a stack data structure. I would much rather use an actual stack data structure, that will be easier to debug and have better locality since there isn't an entire call frame overhead to put one value into the stack.
- maplant 1y agoThis isn't specific to racket, any implementation of R6RS scheme should fully support this, although the define-syntax form is slightly different. I checked this with my R6RS implementation and it works just as you would expect (https://github.com/maplant/scheme-rs https://github.com/maplant/scheme-rs)
- valorzard 1y agoHow close are you to getting a "full" implementation of R6RS? I've been thinking of picking either your project or Steel[0] for a Rust Scheme thing [0] https://github.com/mattwparas/steel https://github.com/mattwparas/steel
- maplant 1y agoI’m hoping by the end of the year. All of the “difficult” things are finished (control flow, syntax transformers, call/cc, dynamic wind, exceptions, libraries, etc) and it’s just a matter of filling missing base library functions. If there’s something in particular that you need you’re welcome to file and issue or post a message on the discord and I’ll prioritize it. That being said, Steel is excellent and I highly recommend it if you just need R5RS with syntax transformers
- deleted 1y ago[deleted]
- skrishnamurthi 1y agoWow — scheme-rs is such a neat project! Hadn't heard of it before!
- maplant 1y agoThanks! I haven’t really publicized it, my goal is to get it finished first, but I will be presenting on it at the scheme workshop at ICFP/SPLASH
- skrishnamurthi 1y ago
- behnamoh 1y agocan we implement this in Python?
- eliben 1y agoThe Y combinator in Python: https://eli.thegreenplace.net/2016/some-notes-on-the-y-combinator/ https://eli.thegreenplace.net/2016/some-notes-on-the-y-combi... (scroll down, after the concept is explained using Clojure) A bit crazier, in Go with generics: https://eli.thegreenplace.net/2022/the-y-combinator-in-go-with-generics/ https://eli.thegreenplace.net/2022/the-y-combinator-in-go-wi...
- skrishnamurthi 1y agoThis isn't the Y-combinator.
- h4ch1 1y agoTangential, but I've been wanting to dive back into FP for quite sometime; for context I used Haskell at a payments corp ~10 years back, working mostly with Typescript, Zig and Nim for the past couple of years, realizing I am basically trying to do FP in most of these languages. Is Racket a good language to pick up and re-learn my concepts + implement some tools? Or are there some other languages that would be better to both brush up and learn the syntax of, I do not want to fight the syntax but rather express functions as seamlessly as I can.
- skrishnamurthi 1y agoRacket is a rich and powerful language, but it is also designed with certain specific ideas in mind. You can learn more about the "zen" of Racket here: https://cs.brown.edu/~sk/Publications/Papers/Published/fffkbmt-programmable-prog-lang/ https://cs.brown.edu/~sk/Publications/Papers/Published/fffkb... That might help you decide whether Racket will help you with what you're trying to brush up on.
- h4ch1 1y agoThank you for the response professor, really appreciate it from one of the creators of the language itself; I did give your document a read and my (naive) understanding is you basically create DSLs for each sub-part of the problem you're trying to solve? >A LOP-based software system consists of multiple, cooperating components, each written in domain-specific languages. and >cooperating multi-lingual components must respect the invariants that each participating language establishes. So basically you're enforcing rules/checks at the language level rather than compile time? How would you recommend a complete novice attain this sort of state of mind/thought process while working in this language? Because my thoughts go simply to creating types and enforcing type-checking coupled with pure functions to avoid successful-fail at runtime programs. Also how would one navigate the complexity of multiple abstractions while debugging? The paper also mentions a web-server language (footnote 27), if I use racket will I be productive "out of the box" or is the recommended path to take is writing a web server language first. Thank you again for taking the time to respond, and please do forgive me for these naive questions.
- user3939382 1y agoAll the languages I like have niche ecosystems which have a lot of drawbacks
- neilv 1y agoIn such ecosystems, for long-term, evolving production work (when you don't know all your eventual needs upfront), you need to have the institutional capability to build from scratch whatever components you might need. Just in case whatever you need later doesn't yet exist in the ecosystem. Then you need to retain the personnel who give you that capability. Because they are rare, in a field in which 99%+ of developers only glue together NPM or PyPI packages. (And many use Web search or, now, Claude Code to do the glue part.) If I founded a startup doing mostly Web-like server backend work, I'd consider doing it in Racket or another Scheme, and then using that as a carrot to be able to hire some of the most capable programmers. (And not having to bother with resume spamming noise from hardly any of the 99%+ developers, who will be pounding the most popular resume tech stack keywords instead, because their primary/sole goal is employability.)
- skrishnamurthi 1y agoThe correlation is likely causal in both directions. They're niche because they're doing weird, interesting things. Like creating their own VMs to support funky features. So nobody wants to depend on them: low bus-factor. They can do weird, interesting things because they don't have a large user-base that will yell at them about how they're breaking prod.
- shawn_w 1y agoThe Racket Discourse thread on this: https://racket.discourse.group/t/illustrate-anonymous-recursive-functions-a-la-powershell/3932 https://racket.discourse.group/t/illustrate-anonymous-recurs... (Just me suggesting other alternatives right now)
- skrishnamurthi 1y agoThanks for the suggestion to replace the reference to MzLib with SRFI-31. I've done that now. https://github.com/shriram/anonymous-recursive-function/commit/6c05e1bcd67014c56308a44d4ef2d8a4ce94eb6c https://github.com/shriram/anonymous-recursive-function/comm...
- adityaathalye 1y agoIn Clojure... ((fn [xs ret] (if (empty? xs) ret (recur (rest xs) (+ ret (first xs))))) (range 5) 0) => 10 nb. Clojure doesn't have automatic tail call optimisation. We need to explicitly emulate it with`recur`.
- JonChesterfield 1y agoDo the clojure folks still insist this is a feature, as opposed to an incomplete compiler leaking limitations into their world?
- jayceedenton 1y agoWithout the explicit recur it's far too easy to misidentify a tail call and use recursion where it's not safe. Recur has zero inconvenience. It's four letters, it verifies that you are in a tail position, and it's portable if you take code to a new function or rename a function. What's not to love?
- rgherdt 1y agoThat doesn't work for mutual recursion, what is quite common in Scheme programs. Besides, tail call optimization is not only useful in recursion.
- skrishnamurthi 1y agoTails calls are especially useful in languages with macros. You don't know what context you are in, you just generate the call that makes sense. If the call happens to be in tail-position, you get the benefit of it. Moreover, you can design cooperating macros that induce and take advantage of tail-position calls. Here's a simple example that motivates tail-calls that are not tail-recursive: https://cs.brown.edu/~sk/Publications/Papers/Published/sk-automata-macros/ https://cs.brown.edu/~sk/Publications/Papers/Published/sk-au...
- 1y ago
- shakna 1y agoProbably worth noting that there's already an SRFI for this. [0] And that macro will work on any Scheme implementing the standard since about '98. (define-syntax rec (syntax-rules () ((rec (NAME . VARIABLES) . BODY) (letrec ( (NAME (lambda VARIABLES . BODY)) ) NAME)) ((rec NAME EXPRESSION) (letrec ( (NAME EXPRESSION) ) NAME)))) [0] https://srfi.schemers.org/srfi-31/srfi-31.html https://srfi.schemers.org/srfi-31/srfi-31.html
- skrishnamurthi 1y ago1. This isn't the same. `rec` names the function. This does not name the function. The point is to illustrate how the name-capture works. 2. The README literally says "Don't Use This Macro!" and references `rec` to use instead: https://github.com/shriram/anonymous-recursive-function?tab=readme-ov-file#dont-use-this-macro https://github.com/shriram/anonymous-recursive-function?tab=...