I understand the use of JavaScript to try to bridge some lingua franca, but the examples are much more verbose than languages where these concepts are first-class that it feels like a diservice to the ideas as looking complicated when they aren’t. Languages that prioritize this style, lambdas are often so brief there isn’t this need to name all of these variables & functions as the usage of these combinators is sufficiently terse, expressive, & readable.
That is to say, I would have loved to see each example in an array and/or functional language next to the JavaScript as a comparison to highlight the concepts in their best light. …That & a small-viewport-friendly stylesheet.
Thank you, and I agree about the better-suitedness of array languages. That said, I specifically avoided adding array examples because that sort of post (rather understandably) becomes read as a sell on array languages, and the subsequent discussion tends to be about the languages rather than this one little bit.
I do agree that, if someone were to be totally sold on this style of programming, JavaScript is probably the worst language to do it in, which is an unfortunate tension.
I’m mostly responding to say that I’ve fixed the style sheet and it should now be much better on mobile!
Certain readers (including myself) would appreciate the Rosetta Stone of examples. It was examples like that that led me into to function programming a decade ago. Seeing the ideas I wanted to use it but shoehorning the concept into JavaScript it work just made everything nastier & now coworkers couldn’t follow it. Eventually I realized my path was to leave JS & if these patterns clicked as they did, I need to be pursuing work in languages that support it first-class. Seeing the ‘real’ examples then not only showed the concepts in the optimal light for me to understand what a code base like that would look like, but also I could re-reference posts to either translate syntax I didn’t yet understand from JavaScript or translate to JavaScript to help explain concept to those outside my space. I think all thru history we have relied on said translations as a time capsule for our history of languages—spoken or not. Recently I’ve had on-&-off interest in the array languages & these posts that show in in Haskell or SML or whatever are the ones that to me click the fastest getting to see the mapping from Language α to Language β.
Nice overview of the basics. I appreciate the honesty about the traditional names. It’s too bad that Smullyan’s names never caught on.
For comparison, I have a table of names here. I should add some tacit vocabularies; I haven’t found category theorists or logicians identifying combinators like under.
A classic introduction to the possibilities and potential of tacit and combinatory programming, outside the context of array languages, is John Backus’s Turing Award Lecture.
I would say that the two main benefits of this programming style are:
Sometimes, tacit code is shorter and clearer than the alternative.
In Haskell, filter (\x -> x > 0) is more verbose and less clear than filter (> 0).
The latter employs a tacit expression (> 0) which doesn’t require a dummy variable x.
Tacit code is sometimes easier to reason about, because you can use equational reasoning.
The Backus lecture goes into detail about what that means.
I say that tacit code is sometimes better because it’s not difficult to go overboard and create tacit code that is obfuscated, so that even the author can’t understand it later on. Tacit programming is functional programming without variables, but sometimes, in complex expressions, you need those variables to give names to subexpressions, so that you can use the names to track the flow of values and understand what the code does.
Tacit code is good when the data flow is simple, local and hierarchical, but can be a liability when combinators are used to shuttle data around through complex paths. The data flow in an ordinary, non-tacit expression is local and hierarchical. Data flows up the parse tree from leaves towards the root. Non-hierarchical / non-local data flow is represented using named parameters and local variables. In box-and-wire visual programming languages like Labview or Pure Data, variable names are replaced by wires. Programs with complex data flow end up looking like a bowl of spaghetti, but at least you can see the wires. In tacit programming, you can use combinators that shuttle data along non-hierarchical paths to model a spaghetti data flow, and the data flow is entirely implicit. You can’t visually reconstruct it by looking at variable names or wires. I call these combinators “spaghetti combinators”. The concatenative languages (like Forth) have a particularly well developed set of spaghetti combinators. These are the “stack operators” like dup, drop. swap, over, rot, nip, tuck.
What is a good set of combinators to use as a base set for elementary tacit programming? John Backus’s FP language (described in the above lecture) and later FL language provide a well chosen and coherent set of non-spaghetti combinators. These combinators are related by a set of algebraic laws that allow you to construct programs by algebraic manipulation and understand programs using equational reasoning.
Backus’s FP includes some useful combinators with 3 or more arguments. These are not considered in the array programming community because array languages restrict combinators to having either 1 or 2 function arguments.
Conditional: (p ⇒ f; g) means λx.(if p x then f x else g x). In Javascript, this could be cond(p,f,g).
List Constructor: [f,g,h] means λx.⟨f x, g x, h x⟩. Note that in FP, ⟨a, b, c⟩ forms a list, like [a, b, c] in Javascript. In Javascript, this combinator could be cons(f,g,h).
Tacit code is sometimes easier to reason about, because you can use equational reasoning. The Backus lecture goes into detail about what that means.
I haven’t read it yet, but could he have been comparing tacit vs imperative? Because in your filter example, it seems like both versions support equational reasoning pretty well.
Equational reasoning is a big topic, you need to be prepared to spend some serious brain power on it. Once you work through some complex examples, it will become obvious why (> 0) is much easier to deal with than (λx.x > 0) in the context of equational reasoning.
Here’s a popular video that works through a series of examples of equational reasoning, where you are transforming one functional program into another using algebraic laws and algebraic identities. https://www.youtube.com/watch?v=seVSlKazsNk
Tacit programming is really beside the point of apl. That combinators feature in j (and kin) is not an accident, but they are not the core idea and you could do as well without them (I say this even though most of the j code I have written is heavily tacit)—it is also not an accident that k lacks them. The conflation is … unfortunate (I won’t say more on the topic for fear of being rude). I don’t think I know any really good introductory materials, sadly (some of the j books are not bad, though), but ‘notation as a tool of thought’ is important and an exposition of many of the important ideas.
great article. Thank you.
I had never heard a term ‘tacit programming’, where variables are a nameless.
But makes sense.
If there is no reason to have the intermediate result of a variable to be exposed – then it should have no name (which then, forces a programmer to combine functions that work on the variable in such a way that the name is not exposed on the site where the transformation begins and ends).
The collision is regrettable, but nevertheless the most suggestive metaphor for 𝝭 seems to be that it calls f under g.
I’ve seen this refered to as: “Are ABC and CBA equal as sorted?” I personally think of it as modulo: “Are ABC and CBA equal modulo sorting?”
I don’t know if these are real combinators, but J also has:
“appose” (::): appose(f, g) is f unless it would it be an error, in which case it’s g. Usually used like inverse :: 0
“agent” (@.): agent(p, f, g) is g(x) if p(x) is true and f(x) otherwise. J does this in the “opposite direction” if if-then-else because it extends this to arbitrary numbers of functions, treating 0 as false and 1 as true.
“fixpoint” (^:_): fixpoint(f)(x) is f(x) if f(x) = x, fixpoint(f)(f(x)). IE “repeat f until the answer converges”.
I understand the use of JavaScript to try to bridge some lingua franca, but the examples are much more verbose than languages where these concepts are first-class that it feels like a diservice to the ideas as looking complicated when they aren’t. Languages that prioritize this style, lambdas are often so brief there isn’t this need to name all of these variables & functions as the usage of these combinators is sufficiently terse, expressive, & readable.
That is to say, I would have loved to see each example in an array and/or functional language next to the JavaScript as a comparison to highlight the concepts in their best light. …That & a small-viewport-friendly stylesheet.
Thank you, and I agree about the better-suitedness of array languages. That said, I specifically avoided adding array examples because that sort of post (rather understandably) becomes read as a sell on array languages, and the subsequent discussion tends to be about the languages rather than this one little bit.
I do agree that, if someone were to be totally sold on this style of programming, JavaScript is probably the worst language to do it in, which is an unfortunate tension.
I’m mostly responding to say that I’ve fixed the style sheet and it should now be much better on mobile!
Certain readers (including myself) would appreciate the Rosetta Stone of examples. It was examples like that that led me into to function programming a decade ago. Seeing the ideas I wanted to use it but shoehorning the concept into JavaScript it work just made everything nastier & now coworkers couldn’t follow it. Eventually I realized my path was to leave JS & if these patterns clicked as they did, I need to be pursuing work in languages that support it first-class. Seeing the ‘real’ examples then not only showed the concepts in the optimal light for me to understand what a code base like that would look like, but also I could re-reference posts to either translate syntax I didn’t yet understand from JavaScript or translate to JavaScript to help explain concept to those outside my space. I think all thru history we have relied on said translations as a time capsule for our history of languages—spoken or not. Recently I’ve had on-&-off interest in the array languages & these posts that show in in Haskell or SML or whatever are the ones that to me click the fastest getting to see the mapping from Language α to Language β.
Well… you make a good argument! Maybe there’s a supplementary article in the making, then.
I would read it! 😃
Nice overview of the basics. I appreciate the honesty about the traditional names. It’s too bad that Smullyan’s names never caught on.
For comparison, I have a table of names here. I should add some tacit vocabularies; I haven’t found category theorists or logicians identifying combinators like
under.Thank you—fyi what I’m calling
underis Psi.A classic introduction to the possibilities and potential of tacit and combinatory programming, outside the context of array languages, is John Backus’s Turing Award Lecture.
I would say that the two main benefits of this programming style are:
filter (\x -> x > 0)is more verbose and less clear thanfilter (> 0). The latter employs a tacit expression(> 0)which doesn’t require a dummy variablex.I say that tacit code is sometimes better because it’s not difficult to go overboard and create tacit code that is obfuscated, so that even the author can’t understand it later on. Tacit programming is functional programming without variables, but sometimes, in complex expressions, you need those variables to give names to subexpressions, so that you can use the names to track the flow of values and understand what the code does.
Tacit code is good when the data flow is simple, local and hierarchical, but can be a liability when combinators are used to shuttle data around through complex paths. The data flow in an ordinary, non-tacit expression is local and hierarchical. Data flows up the parse tree from leaves towards the root. Non-hierarchical / non-local data flow is represented using named parameters and local variables. In box-and-wire visual programming languages like Labview or Pure Data, variable names are replaced by wires. Programs with complex data flow end up looking like a bowl of spaghetti, but at least you can see the wires. In tacit programming, you can use combinators that shuttle data along non-hierarchical paths to model a spaghetti data flow, and the data flow is entirely implicit. You can’t visually reconstruct it by looking at variable names or wires. I call these combinators “spaghetti combinators”. The concatenative languages (like Forth) have a particularly well developed set of spaghetti combinators. These are the “stack operators” like dup, drop. swap, over, rot, nip, tuck.
What is a good set of combinators to use as a base set for elementary tacit programming? John Backus’s FP language (described in the above lecture) and later FL language provide a well chosen and coherent set of non-spaghetti combinators. These combinators are related by a set of algebraic laws that allow you to construct programs by algebraic manipulation and understand programs using equational reasoning.
Backus’s FP includes some useful combinators with 3 or more arguments. These are not considered in the array programming community because array languages restrict combinators to having either 1 or 2 function arguments.
I haven’t read it yet, but could he have been comparing tacit vs imperative? Because in your filter example, it seems like both versions support equational reasoning pretty well.
Equational reasoning is a big topic, you need to be prepared to spend some serious brain power on it. Once you work through some complex examples, it will become obvious why (> 0) is much easier to deal with than (λx.x > 0) in the context of equational reasoning.
Here’s a popular video that works through a series of examples of equational reasoning, where you are transforming one functional program into another using algebraic laws and algebraic identities.
https://www.youtube.com/watch?v=seVSlKazsNk
Tacit programming is really beside the point of apl. That combinators feature in j (and kin) is not an accident, but they are not the core idea and you could do as well without them (I say this even though most of the j code I have written is heavily tacit)—it is also not an accident that k lacks them. The conflation is … unfortunate (I won’t say more on the topic for fear of being rude). I don’t think I know any really good introductory materials, sadly (some of the j books are not bad, though), but ‘notation as a tool of thought’ is important and an exposition of many of the important ideas.
I eventually get what a combinator is. thanks a lot
great article. Thank you. I had never heard a term ‘tacit programming’, where variables are a nameless. But makes sense.
If there is no reason to have the intermediate result of a variable to be exposed – then it should have no name (which then, forces a programmer to combine functions that work on the variable in such a way that the name is not exposed on the site where the transformation begins and ends).
Combinatory programming is very natural in concatenative languages like Factor, though I don’t think they qualify as array langs.
Right! I’m too lazy to chase up the best web page on this, but people can see Factor’s names for combinators by following links from https://docs.factorcode.org/content/article-combinators.html
Also, Rosetta Code has a lot of Factor examples (I bet you wrote some of them), so people can also use that to compare names of combinators if they don’t mind following a lot of separate links. https://rosettacode.org/wiki/Category:Factor?pagefrom=Number+reversal+game#mw-pages
I’ve seen this refered to
as: “Are ABC and CBA equal as sorted?” I personally think of it asmodulo: “Are ABC and CBA equal modulo sorting?”I don’t know if these are real combinators, but J also has:
::):appose(f, g)is f unless it would it be an error, in which case it’sg. Usually used likeinverse :: 0@.):agent(p, f, g)isg(x)ifp(x)is true andf(x)otherwise. J does this in the “opposite direction” ifif-then-elsebecause it extends this to arbitrary numbers of functions, treating0as false and1as true.^:_):fixpoint(f)(x)isf(x)iff(x) = x,fixpoint(f)(f(x)). IE “repeat f until the answer converges”.