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.
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.
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.
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.
Yeah, "less than nothing" is definitely an exaggeration. There's a similar article called "Programming With Nothing" that is about lambda calculus, so my intent is conveying the idea that you can get even simpler than that.
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.
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.
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.
>> 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.
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.
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.
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.
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?
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!
78 comments
[ 4.7 ms ] story [ 75.3 ms ] thread> You lean back, exhausted but triumphant.
> Dana is dead.
Thank you for a good laugh.
https://aphyr.com/posts/353-rewriting-the-technical-intervie...
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.
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
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 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 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)
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.
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? ;)
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.
> 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.
And also; numbers. I would be impressed if you at least used two-complement integers, and decently effective destructors for your data structures.
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