Tuesday, December 19, 2023

The difference between Applicative and Concatenative programming

In the previous post, I outlined the difference between object oriented (noun.verb) and applicative (verb(noun)) programming.  The differences between the applicative and concatenative (noun verb) programming styles are a bit more subtle.  


The basic difference is in the storage of data.  Applicative programs store data in named variables.  Every piece of data at every step along the way must have an assigned name to store it for processing.  Concatenative programming makes use of a stack for passing data. All functions work on data that must already be on the stack, and leave their results on top of the stack.  As a result, you don't need to label or assign intermediate values.  You don't even have to assign the final value of a complex series of functions to a variable.  You can just leave it on the top of the stack, ready for the next function to work on.

Applicative:  Simple functions are applied to each other to create more complex functions, and their results are assigned to variable names.  The syntax is either inside out, or requires the use of intermediate variable assignments.
    final_noun = verb3(verb2(verb1(noun)))
-or-
    noun2 = verb1(noun1)
    noun3 = verb2(noun2)
    final_noun = verb3(noun3)

Concatenative:  Complex functions are created by the concatenation of simpler ones.  The syntax is the order of operations. No variable names or assignments are required.
    noun verb1 verb2 verb3


Let's say I want to construct a house, given a plot of land and materials.

Applicative:
    house = paint(build(dig(plot), materials)))
-or-
    foundation = dig(plot)
    unpainted_house = build(foundation, materials)
    house = paint(unpainted_house)
function definition:
    define construct_house(dirt: plot, stuff: materials): house =
        let home = paint(build(dig(dirt), stuff)))
        return home

Concatenative:
    plot dig materials build paint
function definition:
    define: "construct_house" [materials, plot --> house]
        {dig build paint}


Concatenative programming's strength is the lack of intermediate variable assignments, allowing a smooth flow of data through functions.  This is also its weakness, as you don't have descriptive names to show exactly what form the data is in at each step.  The reversal of data and function names also takes some getting used to, but this is balanced by the direct order of functions one after another.  Concatenative programming style may be summarized as: given this data, do this, then this, then this.

The peculiarity of concatenative programming comes from the stack.  The data must be in the correct order for the functions to operate upon.  This may require some manipulation of the data on the stack, swapping, duplicating, and deleting as necessary.  Some concatenative languages allow the use of temporary variables to make this manipulation more explicit and easier to read, at the expense of requiring temporary variable assignment and storage.

Example: The "construct house" function above requires the data to be in materials, plot order.  If these were reversed, it would be written as:

    define: "construct_house_v2" [plot, materials --> house]
        {swap dig build paint}

If the "build" function required the data to be in foundation, materials order, it would be require another swap.

    define: "construct_house_v3" [plot, materials --> house]
        {swap dig swap build paint}

For this reason, when using a concatenative programming language, much attention must be paid to the order of data used in each function.  A little planning can eliminate a lot of swapping. 

No comments:

Post a Comment

I reserve the right to remove egregiously profane or abusive comments, spam, and anything else that really annoys me. Feel free to agree or disagree, but let's keep this reasonably civil.