7 ms·

Programming with Less Than Nothing

468 points by signa11 1y ago

abstractspoon 1y ago
Read all the way to the end!
mgh95 1y ago
** SPOILER ** > You lean back, exhausted but triumphant. > Dana is dead. Thank you for a good laugh.
- hshdhdhehd 1y ago
  Universal Functional Organelles killed her.
andersmurphy 1y ago
Awesome explainer of combinator logic, the writing style reminded me of this series of posts (which is always a good thing in my opinion): https://aphyr.com/posts/353-rewriting-the-technical-interview https://aphyr.com/posts/353-rewriting-the-technical-intervie...
- stavros 1y ago
  It's clearly inspired from those, there should have been some credit by the author, I think.
  - nemoniac 1y ago
    The author references is in the sectino on Further Reading
    - stavros 1y ago
      Hm, thanks, I somehow missed it the first look around.
  - gpderetta 1y ago
    I love that the interviewer is clearly aware of the meme here.
- teiferer 1y ago
  Explainer? There is little explanation. It's mostly a show off. (A quite impressive one nonetheless.)
  - andersmurphy 1y ago
    Watching people with mastery show off is a great way to get insight. It can be quite an engaging way to learn.
- LandR 1y ago
  Unavailable Due to the UK Online Safety Act sigh
  - JonChesterfield 1y ago
    Yeah, right there with you. It's an extremely good series of posts which thankfully I dimly remember, but now will have to download when I'm next in different country. > "C is not a DSL!" Wonderful writing.
  - andai 1y ago
    Due to the witchcraft?
    - andsoitis 1y ago
      ;-) Author wrote why: https://aphyr.com/posts/395-geoblocking-multiple-localities-with-nginx https://aphyr.com/posts/395-geoblocking-multiple-localities-...
      - gpderetta 1y ago
        well, that's geo blocked as well, so I guess I'll never know. (yes yes, of course I have a vpn)
    - deleted 1y ago
      [deleted]
  - masfuerte 1y ago
    https://web.archive.org/web/20211103164456/https://aphyr.com/posts/353-rewriting-the-technical-interview https://web.archive.org/web/20211103164456/https://aphyr.com...
334f905d22bc19 1y ago
nice 9.5/10 (minus half a point because my brain got hurt a little)
rgovostes 1y ago
The last code block scrolls, by the way. It's 166 kB. Note that S and K are curried functions which take one argument at a time. Further reading: https://stackoverflow.com/a/36321/ https://stackoverflow.com/a/36321/
- q0uaur 1y ago
  the syntax highlighting giving up while i'm scrolling down was my favorite part of the whole thing
jaeyson 1y ago
sheeeshhh, that's harsh
- hshdhdhehd 1y ago
  SKIIIISKKK you mean?
jackdoe 1y ago
haha I was not expecting this journey :) brilliant work!
- hshdhdhehd 1y ago
  Both the code AND the humorous writing. Had to check it wasn't Randall.
  - jacquesm 1y ago
    Who is Randall?
    - hshdhdhehd 1y ago
      xkcd cartoonist
    - Latitude7973 1y ago
      Randall Munroe, I am guessing.
pjmlp 1y ago
And after all of this, all that one gets to do is using AI prompts to configure integrations on a MACH architecture cloud product, fetching data from a content cloud into a CMS. Great article by the way.
deleted 1y ago
[deleted]
tromp 1y ago
let A = (x) => (y) => (z) => x(z)(y((w) => z)) Just need to combine this a few times. let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A); // (x) => (y) => x let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A); // (x) => (y) => (z) => x(z)(y(z)) > “I would never be caught dead using Lambda calculus. It’s a bloated language.” Actually, combinatory logic is more bloated than lambda calculus, generally needing more bits to express the same program [1]. One can argue that lambda calculus is one of the most concise languages ever [2]. > Dana smirks. “Well, yeah. JavaScript is an eager language. Can’t use the Y combinator.” Eager languages can be made lazy by wrapping arguments in lambdas with dummy arguments, as done in the Javascript BLC interpreter [3]. [1] https://tromp.github.io/cl/LC.pdf https://tromp.github.io/cl/LC.pdf [2] https://www.ioccc.org/2012/tromp/ https://www.ioccc.org/2012/tromp/ [3] https://github.com/tromp/AIT/blob/master/uni.js#L56 https://github.com/tromp/AIT/blob/master/uni.js#L56
- teiferer 1y ago
  > let A = (x) => (y) => (z) => x(z)(y((w) => z)) What is w?
  - tromp 1y ago
    The name for a dummy argument that is not used. We could also write A as \x y z => x z (y (K z)), since K is the const function that ignores its second argument and returns the first.
- js8 1y ago
  What is interesting though, the fastest interpreters for lambda calculus (such as yours uni.c) work by translating the term to combinatory logic (although with a bigger base than S,K) and calculating with it.
  - tromp 1y ago
    My uni.c was based on Ben Lynn's combinatory logic VM to which he compiled a large subset of Haskell [1] in a winning IOCCC entry. Lennart Augustsson made an even more comprehensive Haskell implementation with a combinator based runtime [2]. [1] https://crypto.stanford.edu/~blynn/compiler/ https://crypto.stanford.edu/~blynn/compiler/ [2] https://github.com/augustss/MicroHs https://github.com/augustss/MicroHs
latexr 1y ago
You explained the thing, gave references to learn more about the thing, and even listed one con of the thing: > It is also extremely difficult to understand. But nowhere do I see a reason why we should learn the thing. Is It useful in any way? Is it just a curiosity? Does it develop your thinking? Any reason is fine, but if you don’t give one we’re just left looking at something which looks both complex and useless, so why would we learn further? To really drive the point home, I have no doubt this would be fun to learn and even useful for a certain kind of people. But because you don’t say, we don’t know if we fit the bill.
- jacquesm 1y ago
  You started off with 'I' and that was all fine and good but then you switched to 'we' and it wasn't. I fit the bill, and you don't speak for me.
  - latexr 1y ago
    Alright, you fit the bill, but how do you know that? The fact that you fit the bill in no way invalidates the point that I believe the author could’ve done more to help readers understand if they do or don’t. I didn’t understand, and I’m confident I’m not alone. I’m not even criticising the post, I enjoyed it! But at the end I don’t know if there’s a point in me reading more about the subject or not. It feels stupid that I’m getting pushback in response to a comment trying to help both the author and future readers to learn more about this subject. Clearly I didn’t do a good job at communicating my intention.
    - jacquesm 1y ago
      I know it because (a) I read the article and (b) the combinators, brainfuck and so on have something magical to me: they show how unbelievably simple universal computation can be. When I was a kid I always imagined these layers underneath my code. BASIC, then the interpreter (written in assembly) then the machine code represenation of that read out by the CPU (in a way another interpreter, this time in hardware), and underneath that the logic gates. But there were so many logic gates, it still seemed quite complex. Adders, shifters, counters and so on. What this does is it strips away that last layer and compresses it into the most simple abstractions. Just like the 'one instruction set computers', another favorite. https://esolangs.org/wiki/OISC https://esolangs.org/wiki/OISC So the hardware all but evaporates, it is software until the very lowest level and then there is this very simple substrate.
bryanrasmussen 1y ago
I wonder if this guy has a problem getting hired.
tonyedgecombe 1y ago
I did something similar by abusing Func and dynamic in C#: https://github.com/tonyedgecombe/functionalfizzbuzz/blob/master/FunctionalFizzBuzz/FunctionalFizzBuzz.cs https://github.com/tonyedgecombe/functionalfizzbuzz/blob/mas...
JadeNB 1y ago
Lots of fun, though I think "less than nothing" oversells (undersells?) it. I appreciate the author's taking time to explain somewhat at the end, rather than leaving the reader just to feel stupid if they miss, for example, the reference to Smullyan. I also can't help wondering if Dana is just a choice of name, or a cheeky reference to Dana Scott.
- defrost 1y ago
  I assumed it was a shout out to Dana Scott.
  - joshmoody24 1y ago
    ;)
    - defrost 1y ago
      Was there a nod to Christopher in there? * https://www.youtube.com/watch?v=c11KqZOv908 https://www.youtube.com/watch?v=c11KqZOv908 * https://en.wikipedia.org/wiki/Christopher_Strachey https://en.wikipedia.org/wiki/Christopher_Strachey
- joshmoody24 1y ago
  Yeah, "less than nothing" is definitely an exaggeration. There's a similar article called "Programming With Nothing" that is about lambda calculus, so my intent is conveying the idea that you can get even simpler than that.
caporaltito 1y ago
Let me put that in my list of articles to make you feel dumb
xcf_seetan 1y ago
I'm on Firefox and all i can see is boxes with code... Don't understand what this site is about.
- JonChesterfield 1y ago
  It's about the code in the boxes :)
- zamadatix 1y ago
  Text loads between the boxes for me (on Firefox).
mrkeen 1y ago
> Dana smirks. “Well, yeah. JavaScript is an eager language. Can’t use the Y combinator.” Does anyone know off the top of their head if the Z combinator would just work here? (Instead of switching to Skoobert)
- eru 1y ago
  You can make the Y combinator work in eager languages. Famously, in Scheme and other Lisps. This website we are discussing on is written in a sort-of Scheme dialect.
  - zelphirkalt 1y ago
    Yep. The comment about eager languages I think is not really correct, as their eagerness is not really the problem. The problem is being bad at recursion and not having TCO, thus running into a stack overflow. But maybe even more correct would be to say that this or that JS engine doesn't implement TCO. Would Y have simply worked in Safari?
- joshmoody24 1y ago
  The Z combinator does work, but when you try to convert it into point-free form it starts crashing again. I tried pretty hard to avoid having to rewrite JavaScript for this article, but I couldn't find a way around it, since one of my constraints was making everything point-free.
aleph_minus_one 1y ago
While the constructions are for sure interesting for people who love thinking about different programming models, I opine that the story framing with the programming interview is "wrong": Programming interviews serve two purposes to find out: 1. Is the candidate knowledgeable in programming? 2. Does the programming style (somewhat) fit the one that is desired by the company? 1 should be clear, and the author clearly passes this part. For 2: In particular since programming is separated into so many "cultures" of which many of them take deep effort to get more than a superficial knowledge (that's why you talk of "Java shops", "Microsoft/C# shops", ...), in a programming interview, you also want to see whether the candidate will likely be a fit for the prevalent programming culture in the respective company. If you advertise a JavaScript position, it is highly unlikely that if you are that deeply into combinatory logic, you will be a good fit for this position - and thus he would very likely (for good reasons) be rejected if he came up with such a solution.
- JonChesterfield 1y ago
  Someone that could whiteboard correct programs written in SKI is someone I'd be delighted to hire. Likewise someone that can write correct forth by hand. It's holding a very large compute graph in your head comfortably enough that serialising it with a pen doesn't really slow you down. I can't do either of those things though. I'll have to stay in the high level world instead. Sadness.
  - aleph_minus_one 1y ago
    > Someone that could whiteboard correct programs written in SKI is someone I'd be delighted to hire. Likewise someone that can write correct forth by hand. This is potentially true. Nevertheless don't confuse "the kind of person who has very nerdy interests, thus I would like to sit near to him in the office" with "candidate who will likely be the best one to do the work that has to be done in the best possible way". While I do agree that cognitive capabilities are one factor that often correlates well with the subclause "in the best possible way", there exist other factors, too. I don't claim that you mingled these two very different personal profiles, but in my opinion quite some programmers with nerdy interests do. But if you work in an environment where being able to whiteboard correct programs written in SKI or being able to write correct Forth by hand is indeed (plausibly) highly correlated with "likely [to] be the best one to do the work that has to be done in the best possible way" I congratulate you on having a work environment that in my opinion very few programmers can relish.
JonChesterfield 1y ago
Since people are a bit WTF is this, here's a point to combinators. A combinator is a function that doesn't mutate global state and doesn't close over variables. It's the base case in software. Pass it the same argument, get the same result, doesn't change anything about the rest of the system. If you combine some of these combinators, you get another combinator - because when you put pure functions together, what you get is a pure function. These are also the functions that are easy to write in assembly. Or C. Because the don't do very much. So if you write S and K in x64, and then compile common lisp to combinators written in terms of combinators written in terms of S and K, what you've got is common lisp running on those two hand written assembly functions. That's not a great idea for performance, but if you go with a less spartan set of maybe a few hundred of the most commonly occurring patterns inlined into each other and given names, you've got a viable way "machine" to compile functional programs into. This looks a bit like a forth that fears mutation. Or a bytecode vm. Or a CPU, where the combinators are called "instructions". So what combinators are, broadly, is an expression of applied computer science with implementation details ignored as much as possible. That's the sense in which it's simpler than the lambda calculus. Equally, if you implement the lambda calculus on a handful of combinators, then implement lisp on the lambda calculus, then write stuff in that lisp, you've really cut down how much machine specific work needs to be done at the bottom of the stack.
- ai-christianson 1y ago
  Somewhere, a function just called itself and raised a seed round.
  - TYPE_FASTER 1y ago
    It's pitch decks all the way down.
- arethuza 1y ago
  "implement the lambda calculus on a handful of combinators, then implement lisp on the lambda calculus, then write stuff in that lisp" Having done this years ago as a student (not Lisp, but a simple language that macro expanded into lambda calculus) - it is both mind-blowing that you can do anything (including recursion) with just S & K but also impressive as to just how phenomenally inefficient this is... though as you say things do get a lot better as your "instruction set" gets larger.
amelius 1y ago
To make it closer to less than nothing I suggest to use this programming language: https://en.wikipedia.org/wiki/Whitespace_(programming_language) https://en.wikipedia.org/wiki/Whitespace_(programming_langua...
TedHerman 1y ago
Shout out to those hardcores using De Bruijn notation. And bonus points if you're using just S, K, and I. Points off if you're using Y or some other fancy combinators.
fschuett 1y ago
What inane, impure nonsense. You are still using "execution" and "output", these filthy, contingent effects of reality. Why would you use THREE entire combinators, when you could've just defined ιx = xSK. Pathetic. A true, pure program never needs to run. It just exists as a proof, and by its existence as such it simply reconfigures the consciousness of the user to align with its obvious, Manichaean-esque purity. "Running" the "program", please. What are we, barbarians?
RickJWagner 1y ago
I’ve retired after a 35 year career in programming. I knew programmers that could write code I wouldn’t understand. Some of them wrote large, valuable systems. I drew the conclusion that some people think in different ways, some had cognitive gifts different from my own. Some were just better at some things. But the very best programmers wrote code I could follow. It was dirt simple and well documented. Their code made me feel smart as I maintained it. I could understand what the other person was thinking, how the next section would probably go. We were sharing ideas and architectures, but may have never met! I really liked working with that second type.
temperceve 1y ago
> It is also extremely difficult to understand. haha
davedx 1y ago
See also https://www.richard-towers.com/2023/03/11/typescripting-the-technical-interview.html https://www.richard-towers.com/2023/03/11/typescripting-the-...
dvt 1y ago
> “Is that the… Y combinator?” Dana asks. > “Can’t recurse without it.” Fun fact: there are an infinite number of fixed-point combinators (and therefore infinite ways you can recurse without the Y combinator).
andyferris 1y ago
Sadly, it doesn't actually run in NodeJS :( Uncaught RangeError: Maximum call stack size exceeded at REPL2:1:16 at REPL1:1:30 at REPL1:1:34 at REPL1:1:30 at REPL1:1:30 at REPL1:1:30 at REPL1:1:35 at REPL1:1:34 at REPL1:1:34
- the_af 1y ago
  From TFA (note: I didn't test it) Uncaught RangeError: Maximum call stack size exceeded Dana smirks. “Well, yeah. JavaScript is an eager language. Can’t use the Y combinator.” You saw this coming. You paste your code into Skoobert [1]. “Skoobert?” Dana asks. “JavaScript but lazy,” you explain. “And without the bloat.” ---- [1] https://joshmoody24.github.io/skoobert/?example=language-overview https://joshmoody24.github.io/skoobert/?example=language-ove...
- deleted 1y ago
  [deleted]
- joshmoody24 1y ago
  If you're running it as true JavaScript, that's expected. Needs to be run as a Skoobert program.
TYPE_FASTER 1y ago
> Bluebird, cardinal, warbler, thrush. Avian friends you know well. And I have a new favorite naming convention. > “Barendregt. Church is too mainstream.” > “It won’t be JavaScript for much longer.” Douglas Adams teaches SICP.
- Jtsummers 1y ago
  The bird names come from Smullyan's To Mock a Mockingbird. He has a few more named birds in there and there are some other articles online (on mobile so not searching at the moment) about them.
Atomic_Torrfisk 1y ago
Im sorry, this is just bad. There are some neat tricks here, don't get me wrong, but the story is irrelevant/distracting and just feels like a "and everyone clapped" type post on Reddit.
- 63 1y ago
  I like the way that the framing calls attention to the disparity between academic computer science and industry software development
  - Atomic_Torrfisk 1y ago
    I raise an eyebrow and speak, nervous of the down vote I just received But does it really? there is no explicit reference to academia vs industry, which is a fair game. Im just saying the presentation is superfluous.
- deleted 1y ago
  [deleted]
the_af 1y ago
I was so sure I was reading a post by Aphyr, I had to do a double take.
alienbaby 1y ago
ok, but if you did this in an inteview I was giving I would say "clever, but you didn't get the job". Mainly because you missed the point of the interview. We have a guy who joined recently who constantly tries to be as clever as possible when writing his code. He ignores established patterns and conventions because he knows better. He does some cool stuff. Really cool stuff. He's so far bounced thorugh 3 different teams, I don't think he'll be with us long.
- bluGill 1y ago
  I want proof that you normally write readable code, but that you can pull the above off is impressive and I'm interested. Once in a while I need people who can work with weird problems. (More than once I've traced a production bug to something in gcc - this happens about once every 10 years on a project with 200 developers, but it happens and someone needs to be able to trace such things down)
- joshmoody24 1y ago
  Totally fair point. But hey, for my job I recently had to make a fully interactive 3D shopping cart using nothing but CSS. It required some truly diabolical, unreadable code to do things like state management and cart total calculations with nothing but stylesheets. Every once in a while, weird code has real value! And it keeps me from getting bored.
egypturnash 1y ago
“Are you familiar with fizzbuzz?” “Yes. Do you want the ten-character code golf version, the twelve-line eminently readable version that the junior devs can understand, or the one that’s an excuse to show off some extremely esoteric knowledge and do it in a completely sideways fashion?”
- egypturnash 1y ago
  Also this inspired me to try to do FizzBuzz in C64 Basic with the fastest execution speed possible, that was a fun way to waste my morning. https://dragon.style/@anthracite/115424139996607107 https://dragon.style/@anthracite/115424139996607107
  - lgas 1y ago
    Surely if fastest execution speed is your goal then something like PRINT "1";CHR(13);"2";$CHR(13);"Fizz";$(CHR)...etc would be your best bet? Of course if you are happy with spaces instead of newlines as in your C64 code then you can even do it in one big string so you don't have to pay for concatenation.
    - egypturnash 1y ago
      Precalcing the entire thing and delivering absolutely nothing but a bunch of print statements is certainly an option that's completely in the spirit of the kinds of stuff one does to speed up an 8-bit computer(1) but the toy problem of "how can I speed up this for-next loop and the various logic inside it" was more fun. :) (also the spaces-instead-of-newlines choice was made so as to avoid scrolling the screen, the c64's slow enough that having the ROM routines copying ~2k bytes of screen/color memory to scroll every second line of output makes changes in text-generation speed pretty much inconsequential. If that code's optimized for anything it's size, not speed. (2) ) (now that I think about it, there's also the fact that while the c64's BASIC interpreter is limited to about 250 tokens per line, the screen editor limits you to 80 characters per line.) and now I am wondering how fast some form of for i=1 to 100 step 15 print i;i+1;"fizz";i+3;"buzz fizz";i+6;i+7;"fizz buzz";i+10;"fizz";i+12;i+13;"fizzbuzz";:next would work, okay I'm gonna fire up VICE: 49 jiffies, a ton faster than the 134 jiffies my previous best took. And if not for the 80-character input limit it could be one line. Hah. Thanks! Finding the right level to unroll a loop at is always your best bet in the 8-bit world. :) (with the caveat that this generates fizzbuzz for 1-105 instead of 1-100, and logic to stop at 100 and/or logic to stop at any arbitrary limit would probably slow it down) 1: just this morning I was reading a series of blog posts where one of the original authors of Lemmings wrote a port of it to the ZX Spectrum Next and ended up writing some code that would read the data files from the PC version and generate lengthy chunks of hilariously unrolled assembly source that contained one routine to write every image frame to the screen in the fastest way possible, because a more traditional software sprite routine could only handle about ten lemmings at once; that's absolutely insane and absolutely beautiful: https://lemmings.info/porting-lemmings-to-the-zx-spectrum-next/ https://lemmings.info/porting-lemmings-to-the-zx-spectrum-ne... 2: https://pagetable.com/c64ref/c64disasm/#E8EA https://pagetable.com/c64ref/c64disasm/#E8EA
pbohun 1y ago
Haha! You know, I think this is a perfect illustration between something being mathematically beautiful verses pragmatically beautiful. The beauty of one often looks ugly by the standards of the other.
p0w3n3d 1y ago
Congratulations, you've created another Brainfuck
NoSalt 1y ago
Sometimes ... I can overcome impostor syndrome. I feel "good" about being a "successful" coder. Then I [attempt to] read an article like this, and it's right back into the "I'm just a pathetic code monkey." state of mind. I just can't win. :-(
- joshmoody24 1y ago
  For the record, I'm the author of the article, and even I barely understand any of this code. And that's after months of thinking about combinatory logic on a daily basis. It's not designed to be understood. And I can empathize - watching Hacker News dissect this post is causing me some serious imposter syndrome right now, lol
gradschool 1y ago
I know everyone says SK combinators can express any computable function, but I don't get it. How do we write this function foo in terms of SK combinators alone? Is there some obvious programming trick I'm missing that makes it trivial? (It wouldn't be the first time.) foo(x) = if (x == K) return S else return K
- subleq 1y ago
  That's not a computable function. Function equality (x==K) is undecidable.
  - Jtsummers 1y ago
    And that's covered in the last chapter of To Mock a Mockingbird (this submission prompted me to pull it off the shelf this morning).
  - solomonb 1y ago
    Just postulate function extensionality and move on with life. :D
- andoando 1y ago
  Are you asking how to do a if else statement?
deleted 1y ago
[deleted]
wrs 1y ago
In case you’re trying to follow the code: The letters definition is slightly too late. It needs to be before extractString.
- joshmoody24 1y ago
  My bad! I'll fix this
vorticalbox 1y ago
This reminds me of one I read a few years ago “fizzbuzz in tensorflow” https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/ https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
- CraigJPerry 1y ago
  At least i could follow through this one... thanks!
  - MattSayar 1y ago
    Good luck following the Enterprise Edition https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpriseEdition https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpris...
1dolinski 1y ago
grok => make fizzbuzz up to 20 only starting with these combinatory functions let S = (x) => (y) => (z) => x(z)(y(z)); let K = (x) => (y) => x; 10 seconds later https://gist.github.com/1dolinski/93c2e193e5bc6fad9acfc33d71ae7341 https://gist.github.com/1dolinski/93c2e193e5bc6fad9acfc33d71...
- zahlman 1y ago
  As far as I can tell, it mostly ignored the constraint (it came up with encodings for 1 and "true" in terms of S and K, but its "if" and "false" are the usual) and copy-pasted an existing lambda-calculus implementation.
- SCdF 1y ago
  You are taking a forklift to the gym. The goal isn't actually to move the weights from one place to another. The goal is the process.
01HNNWZ0MV43FF 1y ago
Absolute Urbit
andreybaskov 1y ago
Surprised no one mentioned Tree Calculus - https://treecalcul.us/ https://treecalcul.us/. It uses binary trees to represent functions and data. K=ΔΔ, S=Δ(Δx), and so on. Though I won't pretend I fully understand it.
drob518 1y ago
Well done. Kingsbury’s series was equally fun but didn’t use combinators.
mikewarot 1y ago
It seems to me that we just need to update the standard FizzBuzz question to count upward from 1 Billion to eliminate shenanigans like those in the article.
underdeserver 1y ago
If you're interested, the variable-less version takes up 166,664 characters, out of 178,071 characters in the page (counted by Cmd+A, so including newlines and tabs, but no markup), or 93.6% of the output. Since Astro throws in a lot of inline styles (though it gave up halfway through, which is what prompted me to do this math), the line in the HTML that produces that textarea is 558,580 bytes long (or about 3.3 times as big). It all adds up to a 700k page.
kragen 1y ago
This is a fanfic of aphyr's "Foobaring the Technical Interview" series, though with less literary flair: https://aphyr.com/tags/interviews https://aphyr.com/tags/interviews I hadn't heard of Barendregt numerals before; the reference seems to be to Barendregt, H.P. (1976). A global representation of the recursive functions in the lambda calculus, Theoretical Computer Science 3, pp. 225–242. https://repository.ubn.ru.nl/bitstream/handle/2066/17239/13255.pdf https://repository.ubn.ru.nl/bitstream/handle/2066/17239/132.... The bit about numerals starts in §4.1 on p. 238 (p. 15/19), so you can just skip there if you don't need an introduction to the λ-calculus and Schönfinkel/Curry combinatory logic. I wonder if the academic literature would be more enjoyable to read if it were still structured as dialogues, the way it originally was—Hofstadter and Galileo were just calling back to Plato. I think aphyr and Moody fall somewhat short of the standards they set, since the antagonists of their dialogues never raise any real objections, serving only as flimsy, symbolic opposition to the Invincible Hero Mary Sue protagonists, who never make any mistakes or change their minds about anything. As I wrote yesterday in https://news.ycombinator.com/item?id=45669385 https://news.ycombinator.com/item?id=45669385, narratives are central to how the humans understand anything; even adept, experienced programmers often anthropomorphize parts of their programs, indulging in the "this guy talks to that guy" metaphor that Dijkstra so famously deplored, on the perhaps reasonable grounds that it led to illogical thinking.
- deleted 1y ago
  [deleted]
- joshmoody24 1y ago
  You noticed the thing about my article I'm the least comfortable with: the idea of a "Barendregt numeral." The number encoding scheme I use in the article is from To Mock a Mockingbird. Near the end of the book, a character says: "Oh, there are many other [number encodings] that would work... but this particular one is technically convenient. I have adopted this idea from the logician Henk Barendregt." But I couldn't find any other source that claims Barendregt invented it. Thanks for finding another source, I'll take a look at it and update the article!
  - kragen 1y ago
singpolyma3 1y ago
two combinators? So bloated
beepbooptheory 1y ago
Title on here makes it look like its referring to some proper noun "Less Than Nothing". Rather than the op which also capitalizes "With". Was absolutely shocked for second seeing Žižek on the hn frontpage.
hanslub42 1y ago
This would be a good place to remember Moses Schönfinkel, who invented Combinatory Logic as a student of David Hilbert at Göttingen in 1920. His life was tragic: after his return to his native Russia he became mentally ill, and he died in Moscow in poverty. According to Wikipedia, "His papers were burned by his neighbors for heating".
senfiaj 1y ago
Unfortunately couldn't run that long code VM90:2 Uncaught RangeError: Maximum call stack size exceeded
dc10tonite 1y ago
This is the hardest I've laughed this year. Dear lord i'm dying - I'm Dana.
darthvaden 1y ago
[dead]
TZubiri 1y ago
By Vidrun! This sounds like a ripoff from (inspired by) "Hexxing the technical interview"!
tdeck 1y ago
This is a great example of how pure FP folks tend to communicate and why their languages aren't more popular.
0xCE0 1y ago
If someone wants to see SKs in their dreams, read following :) https://writings.stephenwolfram.com/2020/12/combinators-a-centennial-view/ https://writings.stephenwolfram.com/2020/12/combinators-a-ce...
tripzilch 1y ago
BTW there's some variants on the Y or Z combinators that do allow for recursion with plain non-lazy JS. It's been a few months since I did this, and the details evaporate from the mind rather quickly when you don't use the knowledge :) Afaik the idea was to put some kind of indirection/evaluation "speed bump" type of thing around the recursive part. That said, I don't think you actually _need_ recursion for a finite problem like FizzBuzz? The Church Numeral for 100 is literally the function `f f f f f f f.. f x` nested 100 times. So that's your loop.
- tripzilch 1y ago
  Also btw in my experience, the JS engine (both Chrome and FF) was surprisingly good at dealing with 100s (maybe even 1000s) of nested function calls, and definitely didn't take seconds to execute stuff like this.
xplt 1y ago
> You open your laptop and begin. FizzBuzz in an on-site interview on your personal laptop?
lincpa 1y ago
[dead]

468 points by signa11 1y ago

abstractspoon 1y ago

Read all the way to the end!

mgh95 1y ago

** SPOILER ** > You lean back, exhausted but triumphant. > Dana is dead. Thank you for a good laugh.

hshdhdhehd 1y ago
Universal Functional Organelles killed her.

andersmurphy 1y ago

Awesome explainer of combinator logic, the writing style reminded me of this series of posts (which is always a good thing in my opinion): https://aphyr.com/posts/353-rewriting-the-technical-interview https://aphyr.com/posts/353-rewriting-the-technical-intervie...

stavros 1y ago
It's clearly inspired from those, there should have been some credit by the author, I think.
- nemoniac 1y ago
  The author references is in the sectino on Further Reading
  - stavros 1y ago
    Hm, thanks, I somehow missed it the first look around.
- gpderetta 1y ago
  I love that the interviewer is clearly aware of the meme here.
teiferer 1y ago
Explainer? There is little explanation. It's mostly a show off. (A quite impressive one nonetheless.)
- andersmurphy 1y ago
  Watching people with mastery show off is a great way to get insight. It can be quite an engaging way to learn.
LandR 1y ago
Unavailable Due to the UK Online Safety Act sigh
- JonChesterfield 1y ago
  Yeah, right there with you. It's an extremely good series of posts which thankfully I dimly remember, but now will have to download when I'm next in different country. > "C is not a DSL!" Wonderful writing.
- andai 1y ago
  Due to the witchcraft?
  - andsoitis 1y ago
    ;-) Author wrote why: https://aphyr.com/posts/395-geoblocking-multiple-localities-with-nginx https://aphyr.com/posts/395-geoblocking-multiple-localities-...
    - gpderetta 1y ago
      well, that's geo blocked as well, so I guess I'll never know. (yes yes, of course I have a vpn)
  - deleted 1y ago
    [deleted]
- masfuerte 1y ago
  https://web.archive.org/web/20211103164456/https://aphyr.com/posts/353-rewriting-the-technical-interview https://web.archive.org/web/20211103164456/https://aphyr.com...

334f905d22bc19 1y ago

nice 9.5/10 (minus half a point because my brain got hurt a little)

rgovostes 1y ago

The last code block scrolls, by the way. It's 166 kB. Note that S and K are curried functions which take one argument at a time. Further reading: https://stackoverflow.com/a/36321/ https://stackoverflow.com/a/36321/

q0uaur 1y ago
the syntax highlighting giving up while i'm scrolling down was my favorite part of the whole thing

jaeyson 1y ago

sheeeshhh, that's harsh

hshdhdhehd 1y ago
SKIIIISKKK you mean?

jackdoe 1y ago

haha I was not expecting this journey :) brilliant work!

hshdhdhehd 1y ago
Both the code AND the humorous writing. Had to check it wasn't Randall.
- jacquesm 1y ago
  Who is Randall?
  - hshdhdhehd 1y ago
    xkcd cartoonist
  - Latitude7973 1y ago
    Randall Munroe, I am guessing.

pjmlp 1y ago

And after all of this, all that one gets to do is using AI prompts to configure integrations on a MACH architecture cloud product, fetching data from a content cloud into a CMS. Great article by the way.

deleted 1y ago

[deleted]

tromp 1y ago

let A = (x) => (y) => (z) => x(z)(y((w) => z)) Just need to combine this a few times. let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A); // (x) => (y) => x let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A); // (x) => (y) => (z) => x(z)(y(z)) > “I would never be caught dead using Lambda calculus. It’s a bloated language.” Actually, combinatory logic is more bloated than lambda calculus, generally needing more bits to express the same program [1]. One can argue that lambda calculus is one of the most concise languages ever [2]. > Dana smirks. “Well, yeah. JavaScript is an eager language. Can’t use the Y combinator.” Eager languages can be made lazy by wrapping arguments in lambdas with dummy arguments, as done in the Javascript BLC interpreter [3]. [1] https://tromp.github.io/cl/LC.pdf https://tromp.github.io/cl/LC.pdf [2] https://www.ioccc.org/2012/tromp/ https://www.ioccc.org/2012/tromp/ [3] https://github.com/tromp/AIT/blob/master/uni.js#L56 https://github.com/tromp/AIT/blob/master/uni.js#L56

teiferer 1y ago
> let A = (x) => (y) => (z) => x(z)(y((w) => z)) What is w?
- tromp 1y ago
  The name for a dummy argument that is not used. We could also write A as \x y z => x z (y (K z)), since K is the const function that ignores its second argument and returns the first.
js8 1y ago
What is interesting though, the fastest interpreters for lambda calculus (such as yours uni.c) work by translating the term to combinatory logic (although with a bigger base than S,K) and calculating with it.
- tromp 1y ago
  My uni.c was based on Ben Lynn's combinatory logic VM to which he compiled a large subset of Haskell [1] in a winning IOCCC entry. Lennart Augustsson made an even more comprehensive Haskell implementation with a combinator based runtime [2]. [1] https://crypto.stanford.edu/~blynn/compiler/ https://crypto.stanford.edu/~blynn/compiler/ [2] https://github.com/augustss/MicroHs https://github.com/augustss/MicroHs

latexr 1y ago

You explained the thing, gave references to learn more about the thing, and even listed one con of the thing: > It is also extremely difficult to understand. But nowhere do I see a reason why we should learn the thing. Is It useful in any way? Is it just a curiosity? Does it develop your thinking? Any reason is fine, but if you don’t give one we’re just left looking at something which looks both complex and useless, so why would we learn further? To really drive the point home, I have no doubt this would be fun to learn and even useful for a certain kind of people. But because you don’t say, we don’t know if we fit the bill.

jacquesm 1y ago
You started off with 'I' and that was all fine and good but then you switched to 'we' and it wasn't. I fit the bill, and you don't speak for me.
- latexr 1y ago
  Alright, you fit the bill, but how do you know that? The fact that you fit the bill in no way invalidates the point that I believe the author could’ve done more to help readers understand if they do or don’t. I didn’t understand, and I’m confident I’m not alone. I’m not even criticising the post, I enjoyed it! But at the end I don’t know if there’s a point in me reading more about the subject or not. It feels stupid that I’m getting pushback in response to a comment trying to help both the author and future readers to learn more about this subject. Clearly I didn’t do a good job at communicating my intention.
  - jacquesm 1y ago
    I know it because (a) I read the article and (b) the combinators, brainfuck and so on have something magical to me: they show how unbelievably simple universal computation can be. When I was a kid I always imagined these layers underneath my code. BASIC, then the interpreter (written in assembly) then the machine code represenation of that read out by the CPU (in a way another interpreter, this time in hardware), and underneath that the logic gates. But there were so many logic gates, it still seemed quite complex. Adders, shifters, counters and so on. What this does is it strips away that last layer and compresses it into the most simple abstractions. Just like the 'one instruction set computers', another favorite. https://esolangs.org/wiki/OISC https://esolangs.org/wiki/OISC So the hardware all but evaporates, it is software until the very lowest level and then there is this very simple substrate.

bryanrasmussen 1y ago

I wonder if this guy has a problem getting hired.

tonyedgecombe 1y ago

I did something similar by abusing Func and dynamic in C#: https://github.com/tonyedgecombe/functionalfizzbuzz/blob/master/FunctionalFizzBuzz/FunctionalFizzBuzz.cs https://github.com/tonyedgecombe/functionalfizzbuzz/blob/mas...

JadeNB 1y ago

Lots of fun, though I think "less than nothing" oversells (undersells?) it. I appreciate the author's taking time to explain somewhat at the end, rather than leaving the reader just to feel stupid if they miss, for example, the reference to Smullyan. I also can't help wondering if Dana is just a choice of name, or a cheeky reference to Dana Scott.

defrost 1y ago
I assumed it was a shout out to Dana Scott.
- joshmoody24 1y ago
  ;)
  - defrost 1y ago
    Was there a nod to Christopher in there? * https://www.youtube.com/watch?v=c11KqZOv908 https://www.youtube.com/watch?v=c11KqZOv908 * https://en.wikipedia.org/wiki/Christopher_Strachey https://en.wikipedia.org/wiki/Christopher_Strachey
joshmoody24 1y ago
Yeah, "less than nothing" is definitely an exaggeration. There's a similar article called "Programming With Nothing" that is about lambda calculus, so my intent is conveying the idea that you can get even simpler than that.

caporaltito 1y ago

Let me put that in my list of articles to make you feel dumb

xcf_seetan 1y ago

I'm on Firefox and all i can see is boxes with code... Don't understand what this site is about.

JonChesterfield 1y ago
It's about the code in the boxes :)
zamadatix 1y ago
Text loads between the boxes for me (on Firefox).

mrkeen 1y ago

> Dana smirks. “Well, yeah. JavaScript is an eager language. Can’t use the Y combinator.” Does anyone know off the top of their head if the Z combinator would just work here? (Instead of switching to Skoobert)

eru 1y ago
You can make the Y combinator work in eager languages. Famously, in Scheme and other Lisps. This website we are discussing on is written in a sort-of Scheme dialect.
- zelphirkalt 1y ago
  Yep. The comment about eager languages I think is not really correct, as their eagerness is not really the problem. The problem is being bad at recursion and not having TCO, thus running into a stack overflow. But maybe even more correct would be to say that this or that JS engine doesn't implement TCO. Would Y have simply worked in Safari?
joshmoody24 1y ago
The Z combinator does work, but when you try to convert it into point-free form it starts crashing again. I tried pretty hard to avoid having to rewrite JavaScript for this article, but I couldn't find a way around it, since one of my constraints was making everything point-free.

aleph_minus_one 1y ago

While the constructions are for sure interesting for people who love thinking about different programming models, I opine that the story framing with the programming interview is "wrong": Programming interviews serve two purposes to find out: 1. Is the candidate knowledgeable in programming? 2. Does the programming style (somewhat) fit the one that is desired by the company? 1 should be clear, and the author clearly passes this part. For 2: In particular since programming is separated into so many "cultures" of which many of them take deep effort to get more than a superficial knowledge (that's why you talk of "Java shops", "Microsoft/C# shops", ...), in a programming interview, you also want to see whether the candidate will likely be a fit for the prevalent programming culture in the respective company. If you advertise a JavaScript position, it is highly unlikely that if you are that deeply into combinatory logic, you will be a good fit for this position - and thus he would very likely (for good reasons) be rejected if he came up with such a solution.

JonChesterfield 1y ago
Someone that could whiteboard correct programs written in SKI is someone I'd be delighted to hire. Likewise someone that can write correct forth by hand. It's holding a very large compute graph in your head comfortably enough that serialising it with a pen doesn't really slow you down. I can't do either of those things though. I'll have to stay in the high level world instead. Sadness.
- aleph_minus_one 1y ago
  > Someone that could whiteboard correct programs written in SKI is someone I'd be delighted to hire. Likewise someone that can write correct forth by hand. This is potentially true. Nevertheless don't confuse "the kind of person who has very nerdy interests, thus I would like to sit near to him in the office" with "candidate who will likely be the best one to do the work that has to be done in the best possible way". While I do agree that cognitive capabilities are one factor that often correlates well with the subclause "in the best possible way", there exist other factors, too. I don't claim that you mingled these two very different personal profiles, but in my opinion quite some programmers with nerdy interests do. But if you work in an environment where being able to whiteboard correct programs written in SKI or being able to write correct Forth by hand is indeed (plausibly) highly correlated with "likely [to] be the best one to do the work that has to be done in the best possible way" I congratulate you on having a work environment that in my opinion very few programmers can relish.

JonChesterfield 1y ago

Since people are a bit WTF is this, here's a point to combinators. A combinator is a function that doesn't mutate global state and doesn't close over variables. It's the base case in software. Pass it the same argument, get the same result, doesn't change anything about the rest of the system. If you combine some of these combinators, you get another combinator - because when you put pure functions together, what you get is a pure function. These are also the functions that are easy to write in assembly. Or C. Because the don't do very much. So if you write S and K in x64, and then compile common lisp to combinators written in terms of combinators written in terms of S and K, what you've got is common lisp running on those two hand written assembly functions. That's not a great idea for performance, but if you go with a less spartan set of maybe a few hundred of the most commonly occurring patterns inlined into each other and given names, you've got a viable way "machine" to compile functional programs into. This looks a bit like a forth that fears mutation. Or a bytecode vm. Or a CPU, where the combinators are called "instructions". So what combinators are, broadly, is an expression of applied computer science with implementation details ignored as much as possible. That's the sense in which it's simpler than the lambda calculus. Equally, if you implement the lambda calculus on a handful of combinators, then implement lisp on the lambda calculus, then write stuff in that lisp, you've really cut down how much machine specific work needs to be done at the bottom of the stack.

ai-christianson 1y ago
Somewhere, a function just called itself and raised a seed round.
- TYPE_FASTER 1y ago
  It's pitch decks all the way down.
arethuza 1y ago
"implement the lambda calculus on a handful of combinators, then implement lisp on the lambda calculus, then write stuff in that lisp" Having done this years ago as a student (not Lisp, but a simple language that macro expanded into lambda calculus) - it is both mind-blowing that you can do anything (including recursion) with just S & K but also impressive as to just how phenomenally inefficient this is... though as you say things do get a lot better as your "instruction set" gets larger.

amelius 1y ago

To make it closer to less than nothing I suggest to use this programming language: https://en.wikipedia.org/wiki/Whitespace_(programming_language) https://en.wikipedia.org/wiki/Whitespace_(programming_langua...

TedHerman 1y ago

Shout out to those hardcores using De Bruijn notation. And bonus points if you're using just S, K, and I. Points off if you're using Y or some other fancy combinators.

fschuett 1y ago

What inane, impure nonsense. You are still using "execution" and "output", these filthy, contingent effects of reality. Why would you use THREE entire combinators, when you could've just defined ιx = xSK. Pathetic. A true, pure program never needs to run. It just exists as a proof, and by its existence as such it simply reconfigures the consciousness of the user to align with its obvious, Manichaean-esque purity. "Running" the "program", please. What are we, barbarians?

RickJWagner 1y ago

I’ve retired after a 35 year career in programming. I knew programmers that could write code I wouldn’t understand. Some of them wrote large, valuable systems. I drew the conclusion that some people think in different ways, some had cognitive gifts different from my own. Some were just better at some things. But the very best programmers wrote code I could follow. It was dirt simple and well documented. Their code made me feel smart as I maintained it. I could understand what the other person was thinking, how the next section would probably go. We were sharing ideas and architectures, but may have never met! I really liked working with that second type.

temperceve 1y ago

> It is also extremely difficult to understand. haha

davedx 1y ago

See also https://www.richard-towers.com/2023/03/11/typescripting-the-technical-interview.html https://www.richard-towers.com/2023/03/11/typescripting-the-...

dvt 1y ago

> “Is that the… Y combinator?” Dana asks. > “Can’t recurse without it.” Fun fact: there are an infinite number of fixed-point combinators (and therefore infinite ways you can recurse without the Y combinator).

andyferris 1y ago

Sadly, it doesn't actually run in NodeJS :( Uncaught RangeError: Maximum call stack size exceeded at REPL2:1:16 at REPL1:1:30 at REPL1:1:34 at REPL1:1:30 at REPL1:1:30 at REPL1:1:30 at REPL1:1:35 at REPL1:1:34 at REPL1:1:34

the_af 1y ago
From TFA (note: I didn't test it) Uncaught RangeError: Maximum call stack size exceeded Dana smirks. “Well, yeah. JavaScript is an eager language. Can’t use the Y combinator.” You saw this coming. You paste your code into Skoobert [1]. “Skoobert?” Dana asks. “JavaScript but lazy,” you explain. “And without the bloat.” ---- [1] https://joshmoody24.github.io/skoobert/?example=language-overview https://joshmoody24.github.io/skoobert/?example=language-ove...
deleted 1y ago
[deleted]
joshmoody24 1y ago
If you're running it as true JavaScript, that's expected. Needs to be run as a Skoobert program.

TYPE_FASTER 1y ago

> Bluebird, cardinal, warbler, thrush. Avian friends you know well. And I have a new favorite naming convention. > “Barendregt. Church is too mainstream.” > “It won’t be JavaScript for much longer.” Douglas Adams teaches SICP.

Jtsummers 1y ago
The bird names come from Smullyan's To Mock a Mockingbird. He has a few more named birds in there and there are some other articles online (on mobile so not searching at the moment) about them.

Atomic_Torrfisk 1y ago

Im sorry, this is just bad. There are some neat tricks here, don't get me wrong, but the story is irrelevant/distracting and just feels like a "and everyone clapped" type post on Reddit.

63 1y ago
I like the way that the framing calls attention to the disparity between academic computer science and industry software development
- Atomic_Torrfisk 1y ago
  I raise an eyebrow and speak, nervous of the down vote I just received But does it really? there is no explicit reference to academia vs industry, which is a fair game. Im just saying the presentation is superfluous.
deleted 1y ago
[deleted]

the_af 1y ago

I was so sure I was reading a post by Aphyr, I had to do a double take.

alienbaby 1y ago

ok, but if you did this in an inteview I was giving I would say "clever, but you didn't get the job". Mainly because you missed the point of the interview. We have a guy who joined recently who constantly tries to be as clever as possible when writing his code. He ignores established patterns and conventions because he knows better. He does some cool stuff. Really cool stuff. He's so far bounced thorugh 3 different teams, I don't think he'll be with us long.

bluGill 1y ago
I want proof that you normally write readable code, but that you can pull the above off is impressive and I'm interested. Once in a while I need people who can work with weird problems. (More than once I've traced a production bug to something in gcc - this happens about once every 10 years on a project with 200 developers, but it happens and someone needs to be able to trace such things down)
joshmoody24 1y ago
Totally fair point. But hey, for my job I recently had to make a fully interactive 3D shopping cart using nothing but CSS. It required some truly diabolical, unreadable code to do things like state management and cart total calculations with nothing but stylesheets. Every once in a while, weird code has real value! And it keeps me from getting bored.

egypturnash 1y ago

“Are you familiar with fizzbuzz?” “Yes. Do you want the ten-character code golf version, the twelve-line eminently readable version that the junior devs can understand, or the one that’s an excuse to show off some extremely esoteric knowledge and do it in a completely sideways fashion?”

egypturnash 1y ago
Also this inspired me to try to do FizzBuzz in C64 Basic with the fastest execution speed possible, that was a fun way to waste my morning. https://dragon.style/@anthracite/115424139996607107 https://dragon.style/@anthracite/115424139996607107
- lgas 1y ago
  Surely if fastest execution speed is your goal then something like PRINT "1";CHR(13);"2";$CHR(13);"Fizz";$(CHR)...etc would be your best bet? Of course if you are happy with spaces instead of newlines as in your C64 code then you can even do it in one big string so you don't have to pay for concatenation.
  - egypturnash 1y ago
    Precalcing the entire thing and delivering absolutely nothing but a bunch of print statements is certainly an option that's completely in the spirit of the kinds of stuff one does to speed up an 8-bit computer(1) but the toy problem of "how can I speed up this for-next loop and the various logic inside it" was more fun. :) (also the spaces-instead-of-newlines choice was made so as to avoid scrolling the screen, the c64's slow enough that having the ROM routines copying ~2k bytes of screen/color memory to scroll every second line of output makes changes in text-generation speed pretty much inconsequential. If that code's optimized for anything it's size, not speed. (2) ) (now that I think about it, there's also the fact that while the c64's BASIC interpreter is limited to about 250 tokens per line, the screen editor limits you to 80 characters per line.) and now I am wondering how fast some form of for i=1 to 100 step 15 print i;i+1;"fizz";i+3;"buzz fizz";i+6;i+7;"fizz buzz";i+10;"fizz";i+12;i+13;"fizzbuzz";:next would work, okay I'm gonna fire up VICE: 49 jiffies, a ton faster than the 134 jiffies my previous best took. And if not for the 80-character input limit it could be one line. Hah. Thanks! Finding the right level to unroll a loop at is always your best bet in the 8-bit world. :) (with the caveat that this generates fizzbuzz for 1-105 instead of 1-100, and logic to stop at 100 and/or logic to stop at any arbitrary limit would probably slow it down) 1: just this morning I was reading a series of blog posts where one of the original authors of Lemmings wrote a port of it to the ZX Spectrum Next and ended up writing some code that would read the data files from the PC version and generate lengthy chunks of hilariously unrolled assembly source that contained one routine to write every image frame to the screen in the fastest way possible, because a more traditional software sprite routine could only handle about ten lemmings at once; that's absolutely insane and absolutely beautiful: https://lemmings.info/porting-lemmings-to-the-zx-spectrum-next/ https://lemmings.info/porting-lemmings-to-the-zx-spectrum-ne... 2: https://pagetable.com/c64ref/c64disasm/#E8EA https://pagetable.com/c64ref/c64disasm/#E8EA

pbohun 1y ago

Haha! You know, I think this is a perfect illustration between something being mathematically beautiful verses pragmatically beautiful. The beauty of one often looks ugly by the standards of the other.

p0w3n3d 1y ago

Congratulations, you've created another Brainfuck

NoSalt 1y ago

Sometimes ... I can overcome impostor syndrome. I feel "good" about being a "successful" coder. Then I [attempt to] read an article like this, and it's right back into the "I'm just a pathetic code monkey." state of mind. I just can't win. :-(

joshmoody24 1y ago
For the record, I'm the author of the article, and even I barely understand any of this code. And that's after months of thinking about combinatory logic on a daily basis. It's not designed to be understood. And I can empathize - watching Hacker News dissect this post is causing me some serious imposter syndrome right now, lol

gradschool 1y ago

I know everyone says SK combinators can express any computable function, but I don't get it. How do we write this function foo in terms of SK combinators alone? Is there some obvious programming trick I'm missing that makes it trivial? (It wouldn't be the first time.) foo(x) = if (x == K) return S else return K

subleq 1y ago
That's not a computable function. Function equality (x==K) is undecidable.
- Jtsummers 1y ago
  And that's covered in the last chapter of To Mock a Mockingbird (this submission prompted me to pull it off the shelf this morning).
- solomonb 1y ago
  Just postulate function extensionality and move on with life. :D
andoando 1y ago
Are you asking how to do a if else statement?

deleted 1y ago

[deleted]

wrs 1y ago

In case you’re trying to follow the code: The letters definition is slightly too late. It needs to be before extractString.

joshmoody24 1y ago
My bad! I'll fix this

vorticalbox 1y ago

This reminds me of one I read a few years ago “fizzbuzz in tensorflow” https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/ https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/

CraigJPerry 1y ago
At least i could follow through this one... thanks!
- MattSayar 1y ago
  Good luck following the Enterprise Edition https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpriseEdition https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpris...

1dolinski 1y ago

grok => make fizzbuzz up to 20 only starting with these combinatory functions let S = (x) => (y) => (z) => x(z)(y(z)); let K = (x) => (y) => x; 10 seconds later https://gist.github.com/1dolinski/93c2e193e5bc6fad9acfc33d71ae7341 https://gist.github.com/1dolinski/93c2e193e5bc6fad9acfc33d71...

zahlman 1y ago
As far as I can tell, it mostly ignored the constraint (it came up with encodings for 1 and "true" in terms of S and K, but its "if" and "false" are the usual) and copy-pasted an existing lambda-calculus implementation.
SCdF 1y ago
You are taking a forklift to the gym. The goal isn't actually to move the weights from one place to another. The goal is the process.

01HNNWZ0MV43FF 1y ago

Absolute Urbit

andreybaskov 1y ago

Surprised no one mentioned Tree Calculus - https://treecalcul.us/ https://treecalcul.us/. It uses binary trees to represent functions and data. K=ΔΔ, S=Δ(Δx), and so on. Though I won't pretend I fully understand it.

drob518 1y ago

Well done. Kingsbury’s series was equally fun but didn’t use combinators.

mikewarot 1y ago

It seems to me that we just need to update the standard FizzBuzz question to count upward from 1 Billion to eliminate shenanigans like those in the article.

underdeserver 1y ago

If you're interested, the variable-less version takes up 166,664 characters, out of 178,071 characters in the page (counted by Cmd+A, so including newlines and tabs, but no markup), or 93.6% of the output. Since Astro throws in a lot of inline styles (though it gave up halfway through, which is what prompted me to do this math), the line in the HTML that produces that textarea is 558,580 bytes long (or about 3.3 times as big). It all adds up to a 700k page.

kragen 1y ago

This is a fanfic of aphyr's "Foobaring the Technical Interview" series, though with less literary flair: https://aphyr.com/tags/interviews https://aphyr.com/tags/interviews I hadn't heard of Barendregt numerals before; the reference seems to be to Barendregt, H.P. (1976). A global representation of the recursive functions in the lambda calculus, Theoretical Computer Science 3, pp. 225–242. https://repository.ubn.ru.nl/bitstream/handle/2066/17239/13255.pdf https://repository.ubn.ru.nl/bitstream/handle/2066/17239/132.... The bit about numerals starts in §4.1 on p. 238 (p. 15/19), so you can just skip there if you don't need an introduction to the λ-calculus and Schönfinkel/Curry combinatory logic. I wonder if the academic literature would be more enjoyable to read if it were still structured as dialogues, the way it originally was—Hofstadter and Galileo were just calling back to Plato. I think aphyr and Moody fall somewhat short of the standards they set, since the antagonists of their dialogues never raise any real objections, serving only as flimsy, symbolic opposition to the Invincible Hero Mary Sue protagonists, who never make any mistakes or change their minds about anything. As I wrote yesterday in https://news.ycombinator.com/item?id=45669385 https://news.ycombinator.com/item?id=45669385, narratives are central to how the humans understand anything; even adept, experienced programmers often anthropomorphize parts of their programs, indulging in the "this guy talks to that guy" metaphor that Dijkstra so famously deplored, on the perhaps reasonable grounds that it led to illogical thinking.

deleted 1y ago
[deleted]
joshmoody24 1y ago
You noticed the thing about my article I'm the least comfortable with: the idea of a "Barendregt numeral." The number encoding scheme I use in the article is from To Mock a Mockingbird. Near the end of the book, a character says: "Oh, there are many other [number encodings] that would work... but this particular one is technically convenient. I have adopted this idea from the logician Henk Barendregt." But I couldn't find any other source that claims Barendregt invented it. Thanks for finding another source, I'll take a look at it and update the article!
- kragen 1y ago

singpolyma3 1y ago

two combinators? So bloated

beepbooptheory 1y ago

Title on here makes it look like its referring to some proper noun "Less Than Nothing". Rather than the op which also capitalizes "With". Was absolutely shocked for second seeing Žižek on the hn frontpage.

hanslub42 1y ago

This would be a good place to remember Moses Schönfinkel, who invented Combinatory Logic as a student of David Hilbert at Göttingen in 1920. His life was tragic: after his return to his native Russia he became mentally ill, and he died in Moscow in poverty. According to Wikipedia, "His papers were burned by his neighbors for heating".

senfiaj 1y ago

Unfortunately couldn't run that long code VM90:2 Uncaught RangeError: Maximum call stack size exceeded

dc10tonite 1y ago

This is the hardest I've laughed this year. Dear lord i'm dying - I'm Dana.

darthvaden 1y ago

[dead]

TZubiri 1y ago

By Vidrun! This sounds like a ripoff from (inspired by) "Hexxing the technical interview"!

tdeck 1y ago

This is a great example of how pure FP folks tend to communicate and why their languages aren't more popular.

0xCE0 1y ago

If someone wants to see SKs in their dreams, read following :) https://writings.stephenwolfram.com/2020/12/combinators-a-centennial-view/ https://writings.stephenwolfram.com/2020/12/combinators-a-ce...

tripzilch 1y ago

BTW there's some variants on the Y or Z combinators that do allow for recursion with plain non-lazy JS. It's been a few months since I did this, and the details evaporate from the mind rather quickly when you don't use the knowledge :) Afaik the idea was to put some kind of indirection/evaluation "speed bump" type of thing around the recursive part. That said, I don't think you actually _need_ recursion for a finite problem like FizzBuzz? The Church Numeral for 100 is literally the function `f f f f f f f.. f x` nested 100 times. So that's your loop.

tripzilch 1y ago
Also btw in my experience, the JS engine (both Chrome and FF) was surprisingly good at dealing with 100s (maybe even 1000s) of nested function calls, and definitely didn't take seconds to execute stuff like this.

xplt 1y ago

> You open your laptop and begin. FizzBuzz in an on-site interview on your personal laptop?

lincpa 1y ago

[dead]