Church Numerals in C++ (and Haskell) | Hacker News Reader

Church Numerals in C++ (and Haskell)

nonchalantlytyped.net

23 pointsdons10 comments

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

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.

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

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.

This is pointless but fun to do,

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

You have a problem.

You've decided to use C++ templates.

Now you have two problems.

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.

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.

4) Implementing Turing-complete type level languages

:-)

Where would you place expression templates that help designers to embed simple domain specific languages in C++? The end user doesn't have to know much about templates, but this approach leads to high performance AND very concise and expressive code.

Reply on news.ycombinator.com