maplant2 days ago
This 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)
valorzard2 days ago
How 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
maplant2 days ago
I’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]2 days agocollapsed
skrishnamurthi2 days ago
Wow — scheme-rs is such a neat project! Hadn't heard of it before!
maplant2 days ago
Thanks! 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
skrishnamurthia day ago
Neat! Will see if I can make it (though I'll probably have to be dealing with OOPSLA stuff at the same time )-:).
shawn_w2 days ago
The Racket Discourse thread on this: https://racket.discourse.group/t/illustrate-anonymous-recurs...
(Just me suggesting other alternatives right now)
skrishnamurthia day ago
Thanks for the suggestion to replace the reference to MzLib with SRFI-31. I've done that now.
https://github.com/shriram/anonymous-recursive-function/comm...
h4ch12 days ago
Tangential, 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.
skrishnamurthi2 days ago
Racket 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/fffkb...
That might help you decide whether Racket will help you with what you're trying to brush up on.
h4ch12 days ago
Thank 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.
skrishnamurthi2 days ago
These are great questions!
Yes, what you're describing is the "extreme" version of LOP. Of course you don't have to do it that aggressively to get working code.
Two references I like to point to:
https://www.hashcollision.org/brainfudge/
They will give you a sense of how one uses LOP productively.
You do not need to write a "web server language"! To the contrary, the Web server provides several languages to give you a trade-off between ease and power in writing server-side Web applications. So you can just write regular Racket code and serve it through the server. The server also comes with some really neat, powerful primitives (orthogonal to LOP) — like `send/suspend` — that make it much easier to write server-based code.
h4ch12 days ago
Understood. Will dive deeper into Racket to get a proper understanding since it's created an itch because I still don't understand it :)
Even if I don't go fully into it as a production language, hopefully it'll open some avenues of thought that I do not yet possess.
Thank you for taking the time to respond, have a great day!
humanfromearth92 days ago
You could try Purescript, with the book¹ written by Charles Scalfani.
It focuses exclusively on FP and does not deviate from it.
adityaathalye2 days ago
In Clojure...
((fn [xs ret]
(if (empty? xs)
ret
(recur (rest xs)
(+ ret (first xs)))))
(range 5) 0)
=> 10
skrishnamurthia day ago
It's not the same thing. `recur` in Clojure must be in tail-position. This program
https://news.ycombinator.com/item?id=45154253
would therefore not work.
adityaathalyea day ago
I was trying to say something like that with my note in the GP comment:
> "nb. Clojure doesn't have automatic tail call optimisation. We need to explicitly emulate it with`recur`."
JonChesterfield2 days ago
Do the clojure folks still insist this is a feature, as opposed to an incomplete compiler leaking limitations into their world?
jayceedenton2 days ago
Without 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?
rgherdta day ago
That doesn't work for mutual recursion, what is quite common in Scheme programs. Besides, tail call optimization is not only useful in recursion.
skrishnamurthia day ago
Tails 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-au...
adityaathalyea day ago
Yeah, absent automatic TCO, we have to do it all, explicitly, by hand... `recur` and `trampoline`.
recur: https://clojuredocs.org/clojure.core/recur
> Evaluates the exprs in order, then, in parallel, rebinds the bindings of (def factorial
(fn [n]
(loop [cnt n
acc 1]
(if (zero? cnt)
acc
(recur (dec cnt) (* acc cnt))
; in loop cnt will take the value (dec cnt)
; and acc will take the value (* acc cnt)
))))
> trampoline can be used to convert algorithms requiring mutual recursion without stack consumption.
(edit: formatting)
skrishnamurthia day ago
Thanks for the pointers. Trampolining is an old idea for obtaining tail-calls. It's a kind of folk-wisdom that has been rediscovered many times, as the related work here shows:
https://dl.acm.org/doi/pdf/10.1145/317636.317779
Usually the trampoline is implemented automatically by the language rather than forcing the author to confront it, though I can see why Clojure might have chosen to put the burden on the user.
adityaathalye19 hours ago
Yeah, Rich's HOPL lecture covers that ground...
https://clojure.org/about/history
> Clojure is not the product of traditional research
> and (as may be evident) writing a paper for this setting
> was a different and challenging exercise.
> I hope the paper provides some insight into why
> Clojure is the way it is and the process and people
> behind its creation and development.skrishnamurthi12 hours ago
Ah, I didn't know there was a HOPL paper! Some day I will have time to run a course reading HOPL papers. Some day I will have the time to read HOPL papers myself (-:. Thanks for the pointer.
userbinator2 days ago
A relevant article to the domain name of this site.
drivenextfunc2 days ago
If you look at the code, you'll be (unpleasantly) surprised, I think. The author does not seem to have known what Y combinator is.
skrishnamurthi2 days ago
If it helps, you will find the Y-combinator described (indeed, derived) in the first edition (https://cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-0...) of the author's programming languages book (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.
userbinator2 days ago
This reminds me of when John Nagle showed up in a thread about his algorithm on here.
adityaathalye2 days ago
Shriram invoking Shriram ... (λ.x (x x) λ.x (x x)) forever \m/ :)
blahedo2 days ago
In 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!
plaitowin2 days ago
I'm pretty sure Shriram Krishnamurthi understands the Y combinator...
Philpax2 days ago
skrishnamurthi2 days ago
Don't see Y-combinator mentioned anywhere on that page.
adityaathalye2 days ago
But I do see that page mentioned on Y Combinator's page.
The joke can go on forever...
shawn_w2 days ago
Somebody forgot to add a base case.
adityaathalyea day ago
No need... Shriram is already based.
almostgotcaught2 days ago
These are my favorite types of comments on hn
neilv2 days ago
The HN guidelines suggest assuming the strongest interpretation of what someone said, so obviously the commenter was making a joke. :)
srpablo2 days ago
lmao Google him
shakna2 days ago
Probably 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))))
skrishnamurthia day ago
1. 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=...
user39393822 days ago
All the languages I like have niche ecosystems which have a lot of drawbacks
neilv2 days ago
In 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.)
skrishnamurthia day ago
The 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.
behnamoh2 days ago
can we implement this in Python?
eliben2 days ago
The Y combinator in Python: 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-wi...
skrishnamurthia day ago
This isn't the Y-combinator.
CyberDildonics2 days ago
I would rather use a loop so I can debug it.
skrishnamurthi2 days ago
This 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)
neilv2 days ago
For formatting code blocks on HN, prefixing each line with 4+ leading spaces works:
(define sum-tree
(lam/anon (t)
(cond ((mt? t) 0)
((node? t) (+ (node-v t)
($MyInvocation (node-l t))
($MyInvocation (node-r t)))))))skrishnamurthia day ago
Aaah, thanks Neil!
CyberDildonics2 days ago
Recursion 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.
fookera day ago
You’d be right if this was 1950. Since then literally all hardware, and compilers, have this specific use case so optimized that you’ll likely see the opposite if you benchmark it.
CyberDildonicsa day ago
Prove it. You can put your stack data structure on the stack anyway. A balanced tree isn't going to have more depth than your memory address bit length. Why would copying a single value be slower than pushing an entire call frame to the stack? Locality is what matters and there is no truth to what you're saying.
More important is the debugability. If you have a normal data structure you can see the full stack of values. If you use recursion you have to unwind through multiple call frames and look at each one individually.
Recursion is for people who want to show a neat clever trick, it isn't the best way to program.
fooker10 hours ago
Here you go : https://godbolt.org/z/haroWGa3c
Recursive DFS took 4 ms Iterative DFS took 8 ms
I'm sure you could optimize the explicit stack based one a bit more to reach parity with a significantly more complex program.
But might as well let ~75 years of hardware, OS, and compiler advancements do that for you when possible.
> Why would copying a single value be slower than pushing an entire call frame to the stack
Because that's not what happens. The stack arithmetic is handled in hardware increasing IPC significantly, and the 'frame' you are talking about it almost the same same size as a single value in the happy path when all the relevant optimizations work out.
> More important is the debugability
Debugging recursive programs is pretty neat with most debuggers. No, you don't unwind through anything manually, just generate a backtrace.
CyberDildonics3 hours ago
One reason it's slower is because your stack doesn't reserve any memory and grows to 40441 at its max size then shrinks back down again. Stack uses a dequeue by default which stores elements in chunks which likely causes lots of memory allocations (and deallocations) which don't happen in the recursive version. Also at n=80,000 your recursive version blows the stack.
https://en.cppreference.com/w/cpp/container/deque.html
The stack arithmetic is handled in hardware increasing IPC significantly, and the 'frame' you are talking about it almost the same same size as a single value in the happy path when all the relevant optimizations work out.
The program stack isn't magically special, it isn't going to beat writing a single value to memory, especially if that memory is some constant sized array already on the stack.
Debugging recursive programs is pretty neat with most debuggers. No, you don't unwind through anything manually, just generate a backtrace.
No matter what kind of debugger it is you're still going to be looking at a lot of information that contains the values you're looking for instead of just looking at the values directly in an array.
Recursion gets used because it's quick, dirty and clever, not because it's the best way to do it.
fooker2 hours ago
Go on, 'Prove it'. Write a version that's faster.
I know it's doable, because I have done it.
You don't seem to understand yet how complex it will be. My guess is ~10x the number of lines of code. It'll be significantly less readable, let alone debuggable.
(btw changing from stack to vector and reserving memory outright for the allocations has virtually no change in performance.)
> The program stack isn't magically special
This is what you're missing. Yes, it is magical because the hardware optimizes for that path. That's why it's faster than what you'd think from first principles.
> it isn't going to beat writing a single value to memory
If you examine the kernel trace from this, you'll find that it has the exact same memory usage and bandwidth (and about twice the ipc). Magical, yes.
CyberDildonicsan hour ago
Go on, 'Prove it'. Write a version that's faster.
You're trying to say that pushing a function call frame is faster than writing a single value to memory and incrementing an index, and when asked to prove it you made something that allocates and deallocates chunks of memory to a linked list where every access takes multiple pointer dereferences.
treyd2 days ago
Tail-recursive functions in Racket are optimized down to essentially for loops.
stirfish2 days ago
What's it like to debug them?
rgherdta day ago
One strategy is by "tracing" a function call: