Home » forums » LtU Forum

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

By Doug Auclair at 2005-04-27 00:12 | LtU Forum | previous forum topic | next forum topic | other blogs | 5728 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Glad you found us

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

By Chris Rathman at Wed, 2005-04-27 00:42 | login or register to post comments

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

By Charles A Stewart at Wed, 2005-04-27 00:59 | login or register to post comments

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?

By Charles A Stewart at Wed, 2005-04-27 17:38 | login or register to post comments