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.
"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.
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.
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].
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.
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.
“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?”
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!
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.
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.
>> 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.
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".
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.
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.
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.
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).
Surprised no one mentioned Tree Calculus - 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.
[+] [-] JonChesterfield|5 months ago|reply
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|5 months ago|reply
[+] [-] arethuza|5 months ago|reply
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.
[+] [-] Joker_vD|5 months ago|reply
And also; numbers. I would be impressed if you at least used two-complement integers, and decently effective destructors for your data structures.
[+] [-] tromp|5 months ago|reply
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
[+] [-] js8|5 months ago|reply
[+] [-] nmilo|5 months ago|reply
[+] [-] jandrese|5 months ago|reply
[+] [-] voidmain|5 months ago|reply
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()));
[+] [-] SupaShotty|5 months ago|reply
[+] [-] teiferer|5 months ago|reply
What is w?
[+] [-] egypturnash|5 months ago|reply
“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|5 months ago|reply
[+] [-] MehYam|5 months ago|reply
[+] [-] RickJWagner|5 months ago|reply
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.
[+] [-] andersmurphy|5 months ago|reply
https://aphyr.com/posts/353-rewriting-the-technical-intervie...
[+] [-] teiferer|5 months ago|reply
[+] [-] stavros|5 months ago|reply
[+] [-] LandR|5 months ago|reply
sigh
[+] [-] rgovostes|5 months ago|reply
Note that S and K are curried functions which take one argument at a time. Further reading: https://stackoverflow.com/a/36321/
[+] [-] q0uaur|5 months ago|reply
[+] [-] aleph_minus_one|5 months ago|reply
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.
[+] [-] andai|5 months ago|reply
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? ;)
[+] [-] debo_|5 months ago|reply
[+] [-] ux266478|5 months ago|reply
[+] [-] JonChesterfield|5 months ago|reply
I can't do either of those things though. I'll have to stay in the high level world instead. Sadness.
[+] [-] wiseowise|5 months ago|reply
> Below x IQ only
Pay enough money and I'll dance like a circus bear in your favorite OOP/FP/FRP flavor.
[+] [-] pjmlp|5 months ago|reply
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.
[+] [-] vorticalbox|5 months ago|reply
https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
[+] [-] CraigJPerry|5 months ago|reply
[+] [-] hanslub42|5 months ago|reply
[+] [-] TYPE_FASTER|5 months ago|reply
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|5 months ago|reply
[+] [-] dvt|5 months ago|reply
> “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).
[+] [-] fschuett|5 months ago|reply
[+] [-] pbohun|5 months ago|reply
[+] [-] mrkeen|5 months ago|reply
Does anyone know off the top of their head if the Z combinator would just work here? (Instead of switching to Skoobert)
[+] [-] eru|5 months ago|reply
Famously, in Scheme and other Lisps. This website we are discussing on is written in a sort-of Scheme dialect.
[+] [-] joshmoody24|5 months ago|reply
[+] [-] mgh95|5 months ago|reply
> You lean back, exhausted but triumphant.
> Dana is dead.
Thank you for a good laugh.
[+] [-] hshdhdhehd|5 months ago|reply
[+] [-] pjmlp|5 months ago|reply
Great article by the way.
[+] [-] underdeserver|5 months ago|reply
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.
[+] [-] bryanrasmussen|5 months ago|reply
[+] [-] andreybaskov|5 months ago|reply
[+] [-] amelius|5 months ago|reply
https://en.wikipedia.org/wiki/Whitespace_(programming_langua...