Two papers on combinators

Hello! I have a couple of papers on using combinators in Combinatory Logic (CL).

I've just updated a paper I wrote some time ago that examines the derivation of a combinator that consumes its argument. "Meditations on the Void" is available at http://www.cotilliongroup.com/code/void-meditations.html.

I have developed a new combinator, P (for Propositional combinator) that curries two arguments at linear cost (currying arguments using combinators usually have an exponential size cost); it is also useful for expressing propositions in CL. "Penguin" is available at http://www.cotilliongroup.com/code/penguin.html.

More generally, my research is in programming languages using the predicate and lambda calculus. The main page for my explorations is at http://www.cotilliongroup.com/code/research.htm.

Sincerely,
Doug Auclair

Comment viewing options

Being as Combinators and LC are subjects of interest in PL's, I invited to Doug to post links to his works on LtU.

Cost-complexity of combinators

I have developed a new combinator, P (for Propositional combinator) that curries two arguments at linear cost (currying arguments using combinators usually have an exponential size cost)

Didn't Curiens' categorical combinators behave decently with respect to complexity? What's the benefit of P? I haven't looked at your papers, but I plan to...

Afterthought. Marketing hint: you might like to edit your post to URLify the links on your post: ever so slightly more people will bother to read your paper that way

Got it!

I've just looked at Meditations on the Void, and I see the point: you can express your combintor using SKI-logic and the rewrites involving it belong to the right complexity class. This wasn't clear from the story...

It reminds me of a talk I attended: it turns out that beta-eta equality in SI-logic is decidable. Who knew?