Church Numerals in C++ (and Haskell)

http://nonchalantlytyped.net/blog/2010/04/24/church-numerals-in-c/

by dons • 16 years ago

23 10 16 years ago

cgranade• 16 years ago

Great argument as to why C++, though it works for functional programming in some technical sense, is far less than ideal.

Niten• 16 years ago

If you want to be picky, you might even say this doesn't really implement Church numerals in C++ (it implements them in the C++ compiler), since the conversion between integers and Church numerals takes place in compile time template expansion. What happens if you want to throw a new integer at this program at runtime?

> You might have to pass -ftemplate-depth-1024 to g++ to get this compiled.

Yeah, no kidding. Semantic arguments aside, this made my head hurt, and I've actually done a reasonable amount of C++ programming.

For comparison, here are what Church numerals look like in Clojure, another language that (like Haskell) has first-class higher order functions:

    (defn church [n]
      (cond (= n 0) (fn [f x] x)
            (> n 0) (fn [f x] (f ((church (dec n)) f x)))))

    (defn unchurch [n]
      (n inc 0))

And it works at runtime.

wheaties• 16 years ago

I love reading about all the template meta-programming people like to do. Then again, I'm sure compile times are a bitch.

mahmud• 16 years ago

Would you like some run-time meta programming? if it didn't take too long to explain, I would slap you with some CLOS-fu.

Imagine a language with a programmable object system. Programmable representation of methods and classes. Programmable evaluation order. Programmable persistence, sharing, and initialization.

http://lispm.dyndns.org/documentation/amop/toc.html

Wherever you see the word "Protocol" in that index, it means there are hooks in place to let you override the defaults.

Common Lisp is so malleable, every programmer is almost forced to become a language architect. You will spend a great deal of your time searching for the most aesthetically pleasing way to do something, instead of the easiest.

The best part is your ability to step into macro expansion one step at a time. You will never be confronted with a pile of machine generated low-level rubbish. Macroexpand-1 each form, repeatedly, and you get to see the onion unfold in slow-mo.

guano___• 16 years ago

This is pointless but fun to do,

  church = (foldr (.) id .).replicate
  unchurch = ($ 0).($ (+1))

rikthevik• 16 years ago

You have a problem.

You've decided to use C++ templates.

Now you have two problems.

tomjen3• 16 years ago

Templates are useful when you need to use the standard containers.

When you start doing metaprogramming beyound that, guys like me start to get very nervous.

hazzen• 16 years ago

I like to make a very important distinction with templates in C++, categorizing uses into three classes:

1) "Java" generics. That is, anything you could do with generics in Java. No one should have an issue using templates like this.

2) Non-recursive "typedef" programming. That is, uses like "::value_type" in the STL containers. These are incredibly useful to have around when writing generic algorithms, but their overuse leads to unparseable code to some set of C++ programmers. Use with caution, but still use.

3) Recursive templates and other subtle uses I haven't covered with the above two. Try very, very, very hard to avoid.

That makes the "will my coworkers understand this code?" question very easy to answer.

Church Numerals in C++ (and Haskell)

Related Stories