Partial Function Application in Concatenative Programming Languages

Question

Say I have a haskell function f n l = filter (n<) l where it takes an integer n and list l and returns all of the integers in l greater then n.

I'm trying to figure out how to best write this function in a language like Joy. I've generally had good luck with converting the haskell function to pointfree form f = filter . (<) and then trying to rewrite it in Joy from there. But I can't figure out how to simulate partial function application in a concatenative language.

So far, I've tried to do something like swap [[>] dip] filter, but it seems like there must be a better/cleaner way to write this.

Also, I'm experimenting with writing my own concatenative language and was wondering if lazy-evaluation could be compatible with concatenative languages.

Answer 1

swap [[>] dip] filter won’t work because it assumes n is accessible for each call to the quotation by which you’re filtering; that implies filter can’t leave any intermediate values on the stack while it’s operating, and > doesn’t consume n. You need to capture the value of n in that quotation.

First “eta”-reduce the list parameter:

l n f = l [ n > ] filter
n f = [ n > ] filter

Then capture n by explicitly quoting it and composing it with >:

n f = n quote [ > ] compose filter

(Assuming quote : a -> (-> a) a.k.a. unit, takes a value and wraps it in a quotation and compose : (A -> B) (B -> C) -> (A -> C) a.k.a. cat, concatenates two quotations.)

Then just “eta”-reduce n:

f = quote [ > ] compose filter

I put “eta” in scare quotes because it’s a little more general than in lambda calculus, working for any number of values on the stack, not just one.

You can of course factor out partial application into its own definition, e.g. the papply combinator in Cat, which is already defined as swons (swap cons) in Joy, but can also be defined like so:

DEFINE

  papply (* x [F] -- [x F] *)
    == [unit] dip concat ;

  f (* xs n -- xs[>=n] *)
    == [>] papply filter .

In Kitten this could be written in a few different ways, according to preference:

// Point-free
function \> compose filter

// Local variable and postfix
-> n; { n (>) } filter

// Local variable and operator section
-> n; \(n <) filter

Any evaluation strategy compatible with functional programming is also compatible with concatenative programming—popr is a lazy concatenative language.