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.
Yeah, you can do all of that. But normally, you can (in fact, have to) chose a much more pragmatic computing substrate instead of graph-rewriting, so unless you're trying to poke at the theoretical limits of what is computability, it's mostly a party trick, and not even a very amusing one unless you attend a very peculiar kind of party.
And also; numbers. I would be impressed if you at least used two-complement integers, and decently effective destructors for your data structures.
"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.
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].
A bloated language means the language has bloat i.e unnecessary features, e.g C++ is a bloated version of C even if you can write the same programs in less code.
You're right; I should have said "In a sense" instead of actually, since I consider the less common bloat in codesize rather than the more common bloat in features.
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.
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].
Thanks for the pointer to MicroHS, looks interesting.
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.
Yes; that's sort of how the lambda calculus self-interpreter works.
There's another connection too, where a lambda term is obtained from its binary code by successive applying an initial term to true or false [1].
It's possible that I messed up in transcribing from my working code
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;
that assumes application is left associative.
> 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.
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.
“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?”
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.
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.
It's correct to underline the heterogeneous nature of programming, but you don't go far enough. What you speak of is only one singular manifestation of a programming role. In this sense, what you're hiring for is expertise with a specific ecosystem, usually because you want to leverage some pre-existing piece of software that exists in that ecosystem, often times due to legacy code. This is not universal.
>> 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.
> Below x IQ only
Pay enough money and I'll dance like a circus bear in your favorite OOP/FP/FRP flavor.
Unfortunely that isn't what happens in most cases.
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.
>
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.
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.
> 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.
I think I like teams with specialisms. I can think of a few instances where things went better because people were doing things they loved, where other people would have really struggled with the same task.
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.
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.
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?
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.
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.)
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?
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.”
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.
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!
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.
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.
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.
> 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 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.
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.
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.
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.
I think there is something beyond that, but possibly not for you.
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 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 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.
That’s not what I said. I don’t think the author is necessarily trying to “convince” anyone, but clearly they care about the subject and welcome the idea of more people learning about it (hence providing more resources). All I’m saying is it would be nice to have some reasons why it’s worth investigating further. For all I know from the post, the author may think this is just a fun curiosity with no other applications. Which is fine, but I (and I believe more people) would be grateful to know if that’s the only reason or there’s something more (and what).
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.
> And what I am asking is precisely if there’s any reason other than that.
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.
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.
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)
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.
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.
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.
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.
Somewhere, a function just called itself and raised a seed round.
It's pitch decks all the way down.
Yeah, you can do all of that. But normally, you can (in fact, have to) chose a much more pragmatic computing substrate instead of graph-rewriting, so unless you're trying to poke at the theoretical limits of what is computability, it's mostly a party trick, and not even a very amusing one unless you attend a very peculiar kind of party.
And also; numbers. I would be impressed if you at least used two-complement integers, and decently effective destructors for your data structures.
"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.
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
[2] https://www.ioccc.org/2012/tromp/
[3] https://github.com/tromp/AIT/blob/master/uni.js#L56
A bloated language means the language has bloat i.e unnecessary features, e.g C++ is a bloated version of C even if you can write the same programs in less code.
You're right; I should have said "In a sense" instead of actually, since I consider the less common bloat in codesize rather than the more common bloat in features.
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.
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/
[2] https://github.com/augustss/MicroHs
Thanks for the pointer to MicroHS, looks interesting.
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.
Yes; that's sort of how the lambda calculus self-interpreter works. There's another connection too, where a lambda term is obtained from its binary code by successive applying an initial term to true or false [1].
[1] https://cstheory.stackexchange.com/questions/32309/concatena...
I think there must be typos in your K and S - the parentheses do not match. I get (with no warranty express or implied):
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()));
It's possible that I messed up in transcribing from my working code
that assumes application is left associative.> 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 A = (x) => (y) => (z) => x(z)(y((w) => z))
What is w?
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.
“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?”
This reminds me of one I read a few years ago “fizzbuzz in tensorflow”
https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
At least i could follow through this one... thanks!
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-intervie...
Explainer? There is little explanation. It's mostly a show off. (A quite impressive one nonetheless.)
Watching people with mastery show off is a great way to get insight. It can be quite an engaging way to learn.
It's clearly inspired from those, there should have been some credit by the author, I think.
The author references is in the sectino on Further Reading
Hm, thanks, I somehow missed it the first look around.
I love that the interviewer is clearly aware of the meme here.
Unavailable Due to the UK Online Safety Act
sigh
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.
https://web.archive.org/web/20211103164456/https://aphyr.com...
Due to the witchcraft?
;-)
Author wrote why: https://aphyr.com/posts/395-geoblocking-multiple-localities-...
well, that's geo blocked as well, so I guess I'll never know.
(yes yes, of course I have a vpn)
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.
I had assumed it to be a clear reference to this series, although it isn't listed in the references.
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? ;)
> although it isn't listed in the references.
Third item under "Further reading". (Though maybe that was added between when you wrote the above and now.)
> There will be other meetings, but you need not participate. Send an eagle in your place.
Thank you, I missed that.
It's correct to underline the heterogeneous nature of programming, but you don't go far enough. What you speak of is only one singular manifestation of a programming role. In this sense, what you're hiring for is expertise with a specific ecosystem, usually because you want to leverage some pre-existing piece of software that exists in that ecosystem, often times due to legacy code. This is not universal.
>> 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.
> Below x IQ only
Pay enough money and I'll dance like a circus bear in your favorite OOP/FP/FRP flavor.
Unfortunely that isn't what happens in most cases.
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.
> 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.
What test designer?
I have seen people requested on the spot to join a meeting interview where the candidate is already on the room.
> 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.
Sometimes I feel like everyone who comments on HN submissions has forgotten what fun looks like.
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.
> 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.
I think I like teams with specialisms. I can think of a few instances where things went better because people were doing things they loved, where other people would have really struggled with the same task.
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.
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/93c2e193e5bc6fad9acfc33d71...
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/
the syntax highlighting giving up while i'm scrolling down was my favorite part of the whole thing
> 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.
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.
> “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).
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?
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.
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
That's not a computable function. Function equality (x==K) is undecidable.
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).
Are you asking how to do a if else statement?
> 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)
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.
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?
In case you’re trying to follow the code: The letters definition is slightly too late. It needs to be before extractString.
Absolute Urbit
To make it closer to less than nothing I suggest to use this programming language:
https://en.wikipedia.org/wiki/Whitespace_(programming_langua...
Sadly, it doesn't actually run in NodeJS :(
From TFA (note: I didn't test it)
----[1] https://joshmoody24.github.io/skoobert/?example=language-ove...
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.
I wonder if this guy has a problem getting hired.
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.
** SPOILER **
> You lean back, exhausted but triumphant.
> Dana is dead.
Thank you for a good laugh.
Universal Functional Organelles killed her.
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.
Read all the way to the end!
I did something similar by abusing Func and dynamic in C#: https://github.com/tonyedgecombe/functionalfizzbuzz/blob/mas...
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.
:-(
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.
> 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 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.
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.
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.
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
So the hardware all but evaporates, it is software until the very lowest level and then there is this very simple substrate.
> I read the article
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.
I think there is something beyond that, but possibly not for you.
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 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 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.
> But nowhere do I see a reason why we should learn the thing
What makes you think the post was trying to convince you to learn it?
That’s not what I said. I don’t think the author is necessarily trying to “convince” anyone, but clearly they care about the subject and welcome the idea of more people learning about it (hence providing more resources). All I’m saying is it would be nice to have some reasons why it’s worth investigating further. For all I know from the post, the author may think this is just a fun curiosity with no other applications. Which is fine, but I (and I believe more people) would be grateful to know if that’s the only reason or there’s something more (and what).
Welcome to theoretical computer science and mathematics. Your complaint applies to most of modern mathematics.
The point is evident; It's interesting.
> 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.
> And what I am asking is precisely if there’s any reason other than that.
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.
nice 9.5/10 (minus half a point because my brain got hurt a little)
haha I was not expecting this journey :)
brilliant work!
Both the code AND the humorous writing. Had to check it wasn't Randall.
Who is Randall?
Randall Munroe, I am guessing.
xkcd cartoonist
I'm on Firefox and all i can see is boxes with code... Don't understand what this site is about.
Text loads between the boxes for me (on Firefox).
It's about the code in the boxes :)
See also https://www.richard-towers.com/2023/03/11/typescripting-the-...
> It is also extremely difficult to understand.
haha
I was so sure I was reading a post by Aphyr, I had to do a double take.
Congratulations, you've created another Brainfuck
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.
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)
Let me put that in my list of articles to make you feel dumb
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.
I assumed it was a shout out to Dana Scott.
sheeeshhh, that's harsh
SKIIIISKKK you mean?
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.
I like the way that the framing calls attention to the disparity between academic computer science and industry software development
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.