{"id":310,"date":"2007-02-15T21:45:30","date_gmt":"2007-02-15T21:45:30","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/02\/15\/not-quite-basics-the-logicians-idea-of-calculus\/"},"modified":"2007-02-15T21:45:30","modified_gmt":"2007-02-15T21:45:30","slug":"not-quite-basics-the-logicians-idea-of-calculus","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/02\/15\/not-quite-basics-the-logicians-idea-of-calculus\/","title":{"rendered":"Not quite Basics: The Logician's Idea of Calculus"},"content":{"rendered":"

In yesterdays basics post, I alluded to the second kind of calculus – the thing that computer scientists like me call a<\/em> calculus. Multiple people have asked me to explain what our kind of calculus is.<\/p>\n

In the worlds of computer science and logic, calculus isn’t a particular thing:
\nit’s a kind<\/em> of thing. A calculus is a sort of a logician’s automaton: a purely
\nsymbolic system where there is a set of rules about how to perform transformations of
\nany value string of symbols. The classic example is lambda calculus<\/a>,
\nwhich I’ve written about before, but there are numerous other calculi.<\/p>\n

<\/p>\n

For a few examples: here are two calculi designed by one of my favorite researchers, Robin Milner, for describing distributed computation with communication: the calculus of communicating systems (CCS)<\/a>, and the π calculus<\/a>. Another great programming language researcher, Luca Cardelli, designed a calculus for describing object-oriented computation<\/a>. There’s another calculus that combines properties of Cardelli’s object calculus and π-calculus, called Join calculus<\/a>. At some point, I’m going to do some writing about π calculus here – I did a lot of π-calculus work for my dissertation, and I think it’s remarkably cool.<\/p>\n

Just to give you a very brief idea of what I mean by this kind of thing, I’ll
\ngive you a quick taste of lambda calculus. To see an explanation of lambda calculus and how it works, you can look here<\/a>.<\/p>\n

Assuming that we handwave a bit to let us use recursion (lambda calculus allows recursion, but it does it by way of a fairly complicated construction called the Y combinator<\/a>); and also assuming we have Peano arithmetic (so we have numbers, comparison, increment, and decrement) we can write a general addition function as:<\/p>\n

Add ≡ λ x y . if (= x 0) y (Add (Dec x) (Inc y))<\/p>\n

The way that this would “run” on an example like 2+3 is:<\/p>\n

    \n
  1. Add 2 3 ≡ if (= 2 0) 3 (Add (Dec 2) (Inc 3)) = (Add 1 4)<\/li>\n
  2. Add 1 4 ≡ if (= 1 0) 4 (Add (Dec 1) (Inc 4)) = (Add 0 5)<\/li>\n
  3. Add 0 5 ≡ if (= 0 0) 5 (Add (Dec 0) (Inc 5)) = 5<\/li>\n<\/ol>\n

    One important thing to understand that sequence is that if<\/em> is a function with three arguments: a test expression, and expressions for the true and false cases. It’s all functions in lambda calculus.<\/p>\n","protected":false},"excerpt":{"rendered":"

    In yesterdays basics post, I alluded to the second kind of calculus – the thing that computer scientists like me call a calculus. Multiple people have asked me to explain what our kind of calculus is. In the worlds of computer science and logic, calculus isn’t a particular thing: it’s a kind of thing. A […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[74],"tags":[],"class_list":["post-310","post","type-post","status-publish","format-standard","hentry","category-basics"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-50","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/310","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=310"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/310\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=310"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=310"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=310"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}