> You lean back, exhausted but triumphant.
> Dana is dead.
Thank you for a good laugh.
https://aphyr.com/posts/353-rewriting-the-technical-intervie...
sigh
> "C is not a DSL!"
Wonderful writing.
Author wrote why: https://aphyr.com/posts/395-geoblocking-multiple-localities-...
(yes yes, of course I have a vpn)
Note that S and K are curried functions which take one argument at a time. Further reading: https://stackoverflow.com/a/36321/
brilliant work!
Great article by the way.
let A = (x) => (y) => (z) => x(z)(y((w) => z))
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))
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
What is w?
BTW, this is probably obvious to you, there are also 5 combinators to which you can directly translate (with proper parentheses) the bits of BLC expression and it sort of self-evaluates in combinatory logic.
The self-evaluation works with the stack of de Bruijn terms as the second argument. One combinator represents lambda abstraction which puts a term to the stack, another is S which represents application, two combinators are used to drop/select the de Bruijn term from the stack and there needs to be another combinator to mark the end of input.
[1] https://cstheory.stackexchange.com/questions/32309/concatena...
Good stuff -- thanks for sharing. IOCCC, like Perl Golf, is brilliantly absurd.
let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A));
let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)(A(A)))))))(A)(A);
> Eager languages can be made lazy by wrapping arguments in lambdas with dummy arguments
So, something like this?
let A = x => y => z => () => x()(z())(y()(w=>z()));
K = A (A A) (A (A A) A A A A A);
S = A (A (A A (A A (A A))(A (A (A A (A A)))))) A A;
> So, something like this? > let A = x => y => z => () => x()(z())(y()(w=>z()));
The javascript code I linked to would change an application like x(z) in A's definition to x ((a) => z(a)), which is really just an eta-expansion of the argument, and would similarly treat the other 2 applications in the definition.
let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A);
let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A);
> 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.
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.
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
So the hardware all but evaporates, it is software until the very lowest level and then there is this very simple substrate.
So did I. It was interesting, but didn’t really make me want to know more.
> the combinators, brainfuck and so on have something magical to me
Right, so in other words, it was because it’s interesting. Which is fine and something I said from from the start:
> Is It useful in any way? Is it just a curiosity? Does it develop your thinking? Any reason is fine (…)
I understand it can be interesting by itself (“Is it just a curiosity?”), I explicitly wanted to know if there’s something beyond that, which the article doesn’t say.
Just like philosophy possibly isn't directly useful to you or men on the moon or a thousand other things that other people find fascinating, and useful to them.
What is useful to you is entirely yours, it is informed by your past and it is shaping your outlook of the future. So in that sense you could write that comment about anything that you find interesting but are not actually interested in, in the sense that you would pursue the thing for its own sake. It is probably better to approach such things in the same way that you would approach art: it may not be useful to you but if it is just interesting then that's enough.
The utility of a statue is very limited, though I guess technically you can hit someone over the head with a stone arm as a stand-in club. But that's not why statues are made. Sometimes the ability to wonder or observe is the utility and if you don't want to end up in a nihilistic place (nothing has ultimate utility on account of the heat death of the universe) then that may help you to appreciate the journey and the views rather than just the 'what's in it for me angle'.
For me the utility of these really low level computing abstractions lies in the fact that I have been wondering for a long time how I could compile a piece of software into a generic piece of hardware. These combinators are simple enough that they can be expressed with a gatecount that is low enough that I can make something more than just a counter (which I could do directly with fewer gates).
This is in turn related to cellular automata, computing fabrics and so on. If you aren't interested in any of those then there is zero utility here.
What makes you think the post was trying to convince you to learn it?
The point is evident; It's interesting.
And what I am asking is precisely if there’s any reason other than that. Again:
> Is It useful in any way? Is it just a curiosity? Does it develop your thinking? Any reason is fine (…)
Clearly I understand that being interesting is in itself a reward, but if that’s the only reason, I’ll probably pass this time. Which is fine, everyone is interested in different things. But if there’s another reason, I might reconsider.
The author is explicit that that is the reason for which additional information is provided. So, the natural reading is from the perspective of the author in promoting the additional learning material, no, there is no other reason that is the focus of their promotion.
If you are looking for some more direct, specific, or immediate payoff, I’m sure there are lots of other things tailored to you.
I mean, reducing motivations down to the fundamentals:
- Will it give you power?
- Will it get you laid?
Yes and yes, but only indirectly; you need to be in the right environment that allows you to use this knowledge to convince others you're smart, and you need to be able to capitalize on it. Other than that? Nope.
I would submit to you that it is quite probable that the information for further learning is provided for people who do not need anything more said to know they “fit the bill”, and if you read the article and don’t know if you do, them you don’t—at least from the author’s perspective.
You might still enjoy learning more about it but you aren’t the audience the author is promoting it to.
Does anyone know off the top of their head if the Z combinator would just work here? (Instead of switching to Skoobert)
Famously, in Scheme and other Lisps. This website we are discussing on is written in a sort-of Scheme dialect.
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.
I can't do either of those things though. I'll have to stay in the high level world instead. Sadness.
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.
I'm on ten years of trying and failing to make any sense of cmake. As a nominally C++ developer, I owe being able to contribute to the projects substantially to other people managing to make cmake do things, and periodically baby-stepping me through trivial changes to it. I'm eternally grateful to the many people who have helped me with that, though I'd also like cmake to die and go away forever.
I remember James being the right guy for release checklists. Every release he'd read the checklist (not try to remember it) so saw when it had changed. Did all the things on it, even when some sounded redundant, or couldn't possibly be worth checking. Took hours, showed every sign of enjoying the process.
I also remember Richard for wizardry with procedural arithmetic. For loops nested six deep with exciting integer arithmetic scattered across the levels implementing some AI thing, written with no indication that he was losing track of the details. Would cheerfully review code of unreasonable complexity and pick out errors in it from the browser diff.
I'm in compiler dev. Lots of applied graph theory really. Hypothetical SKI/forth chap would have better spacial reasoning than me and sometimes that's the limiting factor in the work. Thank you - it is fortunate that our current environment is supportive of language implementation work, long may that remain the case.
Names are very helpful. You get to design your own high-level world, but then you get to use it. Since you can replace any name by its definition in SKI, it's easy to expand, just very tedious.
https://aphyr.com/posts/340-reversing-the-technical-intervie...
Although TFA at least comes with half a page of explanations! That should be plenty, yeah? ;)
Third item under "Further reading". (Though maybe that was added between when you wrote the above and now.)
Thank you, I missed that.
Instead we get a bunch of frustated people that think they are equally valuable as any other FAANG founder, or they are going to be the next SV wonder even though they aren't located in SV, and try to impose their views of the worlds on the candidates.
Also in the end, the actual work has nothing to do with the coding interview.
Of course, for very obvious reasons a programming interview is different from the actual work, but if the test designer did not make a serious attempt that success in the questions that are tested are is much correlated as possible to the actual work, it is in my opinion rather likely that the test should be redesigned.
I have seen people requested on the spot to join a meeting interview where the candidate is already on the room.
Such kinds of interviews of course exist, but they often rather serve the purpose of chatting so that one can see whether the candidate gets on well with the future colleagues.
"Improvised" programming interviews are, of course, often a bad idea, but nevertheless these may also serve a purpose: do some more open-ended discussions about programming topics the candidate likes so that the colleagues/company can see whether they would profit from this kind of knowledge.
> Below x IQ only
Pay enough money and I'll dance like a circus bear in your favorite OOP/FP/FRP flavor.
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.
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.
An overview for Rule 110: https://cs.stackexchange.com/a/4780
And also; numbers. I would be impressed if you at least used two-complement integers, and decently effective destructors for your data structures.
Not only have combinator-graph-reduction machines been used as a target for compilation for pure functional languages, they have been both implemented in hardware and in software. Once you introduce the B, B*, C, and Y combinators as primitives, you can get reasonably efficient compiled programs. The pure combinator-graph-reduction approach isn't currently in fashion; https://dl.acm.org/doi/pdf/10.1145/62678.62716 is a paper by A. C. Norman from 01988 discussing the reasons why it largely fell from grace. Koopman did his dissertation on such a machine around the same time.
https://en.wikipedia.org/wiki/Whitespace_(programming_langua...
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.
haha
> “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).
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 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-ove...
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.
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.
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.
“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?”
PRINT "1";CHR(13);"2";$CHR(13);"Fizz";$(CHR)...etc
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.
(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-ne...
:-(
And I can empathize - watching Hacker News dissect this post is causing me some serious imposter syndrome right now, lol
foo(x) = if (x == K) return S else return K
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/93c2e193e5bc6fad9acfc33d71...
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.
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/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, 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.
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!
I'm not sure Barendregt is claiming to have invented it, and in your quote, Smullyan doesn't either. I've only skimmed the paper, but the paper is framed as an introduction to the λ-calculus and SKI-combinators, not as a presentation of novel results in the field. Its section "0. Preliminaries" (♥) does claim to present a novel representation of recursive functions, but doesn't bother to mention the numerals. In a journal paper published today, the absence of an endnote there would amount to a claim that the representation of numerals was novel, but I don't think that was necessarily true in that less-bibliometrics-plagued time. Though Barendregt does cite 18 sources in his endnotes, so maybe so.
Was absolutely shocked for second seeing Žižek on the hn frontpage.
https://writings.stephenwolfram.com/2020/12/combinators-a-ce...
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.
FizzBuzz in an on-site interview on your personal laptop?
abstractspoon•3mo ago