{"id":218,"date":"2012-04-14T12:12:52","date_gmt":"2012-04-14T16:12:52","guid":{"rendered":"http:\/\/codefork.com\/blog\/?p=218"},"modified":"2012-04-14T12:52:33","modified_gmt":"2012-04-14T16:52:33","slug":"an-sicp-exercise-implementing-cons-car-cdr","status":"publish","type":"post","link":"https:\/\/codefork.com\/blog\/index.php\/2012\/04\/14\/an-sicp-exercise-implementing-cons-car-cdr\/","title":{"rendered":"An SICP exercise in implementing cons, car, and cdr"},"content":{"rendered":"<p>I started working my way through the <a href=\"http:\/\/mitpress.mit.edu\/sicp\/\">Structure and Interpretation of Computer Programs<\/a> this week. <\/p>\n<p>Contemporary &#8220;intro to programming concepts&#8221; texts tend to focus on real-world examples in areas like business and web-based applications. In contrast, SICP involves a lot of math problems. I&#8217;m liking this about the book. Math is particularly good for illustrating the difference between declarative and imperative knowledge, between &#8220;describing properties of things and describing how to do things.&#8221; You may know, formally, what a <a href=\"http:\/\/mitpress.mit.edu\/sicp\/full-text\/book\/book-Z-H-10.html#%_sec_1.1.7\">square root<\/a> is, but coming up with a procedure for calculating the square root of a number is another matter. Bridging these two kinds of knowledge is the essence of what computer programming is about. <\/p>\n<p>The second section, &#8220;Building Abstractions with Data,&#8221; starts by discussing different ways to implement an abstraction for <a href=\"https:\/\/en.wikipedia.org\/wiki\/Rational_number\">rational numbers<\/a>. The text walks through using a Lisp cons cell to store a numerator and denominator pair, and using car and cdr as selectors. Then it provides this exercise, which I found particularly intriguing:<\/p>\n<p><code>Exercise 2.5.  Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2<sup>a<\/sup>3<sup>b<\/sup>. Give the corresponding definitions of the procedures cons, car, and cdr.<\/code><\/p>\n<p>That&#8217;s a really clever way to store a pair! But perhaps I only think so because I&#8217;m not a math person.<\/p>\n<p>At any rate, I wrote a solution in Common Lisp, with some helper lambdas to calculate log and pow arithmetically.<\/p>\n<p><script src=\"https:\/\/gist.github.com\/2385339.js\"> <\/script><\/p>\n<p>I&#8217;m finding that thinking about math problems and learning Lisp are helping me think more algorithmically about solving problems in the code I write for work. Maybe I&#8217;m starting to experience what Eric S Raymond <a href=\"http:\/\/www.catb.org\/~esr\/faqs\/hacker-howto.html\">famously wrote<\/a> about Lisp: that it &#8220;will make you a better programmer for the rest of your days, even if you never actually use Lisp itself a lot.&#8221; I&#8217;m holding out hope for that last part though&#8230;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I started working my way through the Structure and Interpretation of Computer Programs this week. Contemporary &#8220;intro to programming concepts&#8221; texts tend to focus on real-world examples in areas like business and web-based applications. In contrast, SICP involves a lot of math problems. I&#8217;m liking this about the book. Math is particularly good for illustrating &hellip; <a href=\"https:\/\/codefork.com\/blog\/index.php\/2012\/04\/14\/an-sicp-exercise-implementing-cons-car-cdr\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;An SICP exercise in implementing cons, car, and cdr&#8221;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19],"tags":[],"class_list":["post-218","post","type-post","status-publish","format-standard","hentry","category-lisp"],"_links":{"self":[{"href":"https:\/\/codefork.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/218","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codefork.com\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codefork.com\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codefork.com\/blog\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/codefork.com\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=218"}],"version-history":[{"count":19,"href":"https:\/\/codefork.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/218\/revisions"}],"predecessor-version":[{"id":238,"href":"https:\/\/codefork.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/218\/revisions\/238"}],"wp:attachment":[{"href":"https:\/\/codefork.com\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=218"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codefork.com\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=218"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codefork.com\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=218"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}