ask-calculus

The SKA-calculus and the ask-calculus are products of a thought experiment by Chris Pressey in or around May 2020 to produce a concatenative version of the SKI combinator calculus.

We start with combinatory logic with the S, K basis. We are told this is an "applicative language", and that there is also a kind of language called a "concatenative language" which everyone supposes is a different thing, and no-one supposes SK-calculus to be. So we apply a series of transformations to turn it into a concatenative language.

First, combinatory logic has parentheses, but concatenative languages do not. We observe that it only needs parentheses because there is a tacit infix "apply" operator which is not associative. We replace it with an explicit prefix operator which we notate as A, obtaining the "SKA-calculus". For example, where in combinatory logic we would write SSK (taken to be parenthesized as (SS)K) and S(SK), in SKA calculus we would instead write AASSK and ASASK. We have thus eliminated the need for parentheses.

Second, we observe that the SKA-calculus eliminates parentheses by being, essentially, forward Polish notation, but also that we are told that concatenative languages almost universally use reverse Polish notation instead. So we define the "ask calculus" thusly: for every string s in the language of SKA-calculus, there is a string t in the ask-calculus which is equal to s except it is lower-case and reversed. Importantly, t has the same meaning in the ask-calculus as s has in the SKA-calculus. So the equivalents of the above two examples, in ask-calculus, are kssaa and ksasa.

The operational semantics of the ask-calculus are intentionally not specified. Perhaps a programmer who programs in concatenative languages would say that k pushes the K combinator onto the stack, s pushes the S combinator onto the stack, and a pops two combinators from the stack, applies the first to the second, and pushes the result back on the stack -- I mean I don't want to put words in anyone's mouth but it sounds like a reasonable guess any reasonable programmer might make, right? -- but it should be stressed that nowhere in the definition of the ask-calculus is there any mention of a stack. Conversely, someone who writes parsers all day might wonder instead why there is no mention of a stack in the SKA-calculus, nor in the SKI-calculus from whence it came, when it is crystal clear that something like a stack is required to parse it correctly.

From this experiment we can only conclude that function composition is a special case of function application, and also vice versa, or something.

Computability class

Both SKA-calculus and ask-calculus are Turing complete by virtue of being derived directly from SKI combinator calculus which is Turing complete.