tag:blogger.com,1999:blog-31455766006247396002024-02-07T10:40:47.534-08:00I want to write programsMy journey into the huge world of computer programmingRenehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.comBlogger28125tag:blogger.com,1999:blog-3145576600624739600.post-74066736123266072402007-03-26T08:22:00.000-07:002007-03-26T09:03:17.656-07:00MzScheme in Aquamacs Emacs<style>.code{font-family:monospace;}.overline{text-decoration:overline;}.reversed{background-color:#ffcccc;}.red{color:#ff0000;}</style><p>Aquamacs Emacs has built in support for Scheme, but not for MzScheme, which is one of the versions of Scheme of PLT DrScheme. You envoke it by <span class="code">M-x run-scheme</span>, which searches for <span class="code">scheme</span> in the path.<br /><br />I have put MzScheme in the path, and I could rename it to <span class="code">scheme</span>, but that would break DrScheme. The solution is to create a symbolic link (symlink) of <span class="code">mzscheme</span> and rename that symlink into <span class="code">scheme</span>. I could do that in Terminal with <span class="code">ln -s mzscheme scheme</span>, but there is also a way to do that in Mac OS X, with the freeware application <a href="http://seiryu.home.comcast.net/symboliclinker.html" target="_blank">SymbolicLinker</a>, wich appears in the contextual menu of Finder.<br /><br />That makes sense, because the reason to use Aquamacs Emacs was to stay in the GUI of Mac OS X, and this SymbolicLinker contextual menu continues using this strategy.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEht9kp_TdK9SwIifFm3A38Xj6iNvr4zZP-5jkLaHJRW4LmIDyPrYjxw4toe8hojUXZl4s33ucVPcQjT4v4HqCdc477EpA-IElJ_Katrqr8iiNY1UGg7qzRLr5-QPon6ss8G6GXeuxqjyoxy/s1600-h/MzScheme-Aquamacs.png"><img style="cursor: pointer;text-align:center;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEht9kp_TdK9SwIifFm3A38Xj6iNvr4zZP-5jkLaHJRW4LmIDyPrYjxw4toe8hojUXZl4s33ucVPcQjT4v4HqCdc477EpA-IElJ_Katrqr8iiNY1UGg7qzRLr5-QPon6ss8G6GXeuxqjyoxy/s400/MzScheme-Aquamacs.png" alt="" id="BLOGGER_PHOTO_ID_5046263799362117058" border="0" /></a></p>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com2tag:blogger.com,1999:blog-3145576600624739600.post-15431939844111867922007-03-25T10:07:00.000-07:002007-03-25T14:52:40.474-07:00Pondering about programming<p>Sometimes it is good to take some distance from what you're doing, so you can set your priorities for the near future.</p><h2>Wat is programming, actually?</h2><p>Seems to be a silly question, because you'd think that programming is about producing code, but it's not.<br /><br />I suggest you read <a href="http://norvig.com/21-days.html" target="_blank">Teach Yourself Programming in Ten Years</a>, by Peter Norvig. Most noteworthy programs are written as team efforts, and if you want to become a good programmer, you need to be able to work in a team, sometimes as an experienced leader and sometimes as a novice to the software project (in order to give orders, you have to be able to follow orders as well).<br /><br />A good programmer has good interpersonal skills and can work in teams. Interactions between programmers are perhaps more important than the code they write.</p><h2>Writing good code should be the goal</h2><p>Unfortunately, the coding community has the reputation of writing bad, bug-ridden code, that needs constant updating and lots of support to and feedback from the end-users (which explains why good customer support is such a large chuck in the total costs of software development). Also, people tend to own a part of a project, do poor documentation, then run away from projects and leave the team with undocumented, buggy code, which has to be fixed by other people. There are a lot of bad coding teams out there. Not necessarily because the team members are bad coders, but because the team's organization, well um, sucks.<br /><br />So how to spot good coding practices? Read <a href="http://www.joelonsoftware.com/articles/fog0000000043.html" target="_blank">The Joel Test: 12 Steps to Better Code</a> and learn.</p>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-35885298750645944412007-03-24T05:11:00.000-07:002007-03-24T05:54:38.194-07:00Concepts, Techniques, and Models of Computer ProgrammingI found another good resource for learning how to write computer programs, called "Concepts, Techniques, and Models of Computer Programming", by Peter Van Roy and Seif Haridi. It uses declarative programming and distributive computing as a programming paradigm, and its programming language of choice is <a href="http://www.mozart-oz.org/" target="_blank">Mozart-Oz</a>.<br /><br />One could see this as a successor of "Structure and Interpretation of Computer Programs" by Harold Abelson and Gerald Jay Sussman, which used functional programming as a programming paradigm, and Scheme as the programming language of choice.<br /><br />Both have their values as instructional books, because they learn you to see computer programming in new ways you never imagined existed before.<br /><br />I will be concentrating on the SICP book for now, but it is good to know that there are more excellent books to learn how to write programs using your human intelligence and imagination, instead of copying and pasting what others have done before you. Nothing wrong with the latter, but I don't aspire to become a <a href="http://en.wikipedia.org/wiki/Script_kiddie" target="_blank">script kiddie</a>, or even a <a href="http://en.wikipedia.org/wiki/Code_monkey" target="_blank">code monkey</a>. I want to design programs.Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-59646634813128235022007-03-24T04:57:00.000-07:002007-03-26T11:34:53.896-07:00Aquamacs Emacs<p><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgaQogpeJwVh-l9JQFXVyXLn2iC6F7ocClXB_WHMDtkdMxY-JKoOAc8hvFSr9ZZQdHmYm2LPCgam1OWHmxvet3emWQlqQb6hJYj57Ztd8D91lvADIml_yJzm3expW3sEr6gjhsA78ZGhhZx/s1600-h/AquamacsEmacs.png"><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer;margin-right:10px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgaQogpeJwVh-l9JQFXVyXLn2iC6F7ocClXB_WHMDtkdMxY-JKoOAc8hvFSr9ZZQdHmYm2LPCgam1OWHmxvet3emWQlqQb6hJYj57Ztd8D91lvADIml_yJzm3expW3sEr6gjhsA78ZGhhZx/s400/AquamacsEmacs.png" alt="" id="BLOGGER_PHOTO_ID_5046303235751828962" border="0" /></a>I was trying to get to grips with GNU Emacs, when I came across a Mac OS X specific equivalent, called Aquamacs. Well, it isn't really an equivalent, but, if I understood correctly, it is a graphical user interface (GUI) shell around GNU Emacs. It is meant to keep you in the spirit of GUI, not having to switch gears to a command-line-interpreter-state of mind.</p><ul><li><a href="http://aquamacs.org/" target="_blank">Aquamacs website</a></li></ul>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-59544695376353861572007-03-21T04:05:00.000-07:002007-03-21T08:53:30.344-07:00Thinking in COn Mindview.net there is an excellent C foundation course in Shockwave Flash format that you can download from <a href="http://mindview.net/CDs/ThinkingInC/" target="_blank">here</a> as a ZIP archive for off-the-Net viewing. It isn't a full introductory course, but rather concentrating on the parts of C you'll need to better understand Java or C++.<br /><br />Mindview also has courses in C++ and Java, called <a href="http://www.mindview.net/Books/TIJ/" target="_blank">Thinking in Java</a> and <a href="http://www.mindview.net/Books/TICPP/ThinkingInCPP2e.html" target="_blank">Thinking in C++</a>, so this Thinking in C course could be seen as an introductory course for these other, more advanced courses. If I understood correctly, the old versions of these two courses can be downloaded for free, but if you want the most recent versions, you have to buy the printed copies, which seems reasonable to me.<br /><br />I have done the first introductory chapter and it seems to be excellent for those who have little programming experience. However, I don't recommend it for the absolute newbies in programming, because it might be a little too steep in the learning curve for those. You need to be aware of some basic concepts of program development, and how your system works on the command line.<br /><br />For those absolute newbies to programming, I recommend a site like the platform-independent <a href="http://computerprogramming.suite101.com/article.cfm/computerprogramming101" target="_blank">Programming 101</a>.<br /><br />For how the command line works, I advice to visit:</p><ul> <li><a href="http://www.microsoft.com/resources/documentation/windows/xp/all/proddocs/en-us/ntcmds_o.mspx" target="_blank">Command-line reference</a> (Windows)</li><li><a href="http://www.macdevcenter.com/pub/ct/51" target="_blank">Learning the Mac OS X Terminal</a> (Mac OS X)</li><li><a href="http://www.tuxfiles.org/linuxhelp/cli.html" target="_blank">An introduction to the Linux command line</a> (Linux)</li></ul><p>I realize that these might not be the best links for newbies (especially the Windows link). If anyone has suggestions, feel free to put it in a comment.</p>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com1tag:blogger.com,1999:blog-3145576600624739600.post-51964672102031714712007-03-20T01:46:00.000-07:002007-03-21T04:23:19.318-07:00Alternative to MIT course<style>.code{font-family:monospace;}.overline{text-decoration:overline;}.reversed{background-color:#ffcccc;}.red{color:#ff0000;}</style>At UC Berkeley there is an alternative to the MIT course "Structure and Interpretation of Computer Programs". The webcast page can be found <a href="http://webcast.berkeley.edu/course_details.php?seriesid=1906978270" target="_blank">here</a>. The video is only streaming (Real Media), but the audio can be downloaded as a (MP3) podcast through iTunes.<br /><br />There is a UCB Scheme, called STk, which has versions for Windows, Linux and Mac OS X.<br /><br />In Mac OS X (which I happen to use), you'll need to run from a X11 terminal window, which needs to be pre-installed. For versions of Mac OS X before 10.4 (Tiger), you need to download <a href="http://www.xdarwin.org/" target="_blank">XDarwin</a>, if you haven't done so already. For OS X 10.4 and higher, there is a X system—X11 and Xorg—on the install disk, which should be used instead of the download from XDarwin.org. If you have X11 available in your <span class="code">/Applications/</span> folder, you already have X installed.<br /><br /><b>NB:</b> While the podcast is convenient, it is not very useful to understand the lessons. You really need to watch the video stream, and perhaps use the podcast as a preview, to get a quick overview of the lecture before paying attention to details.Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-10487096767674725842007-03-14T08:15:00.000-07:002007-03-24T07:19:38.612-07:00SICP - 1.1 The Elements of Programming<style>.code{font-family:monospace;}.overline{text-decoration:overline;}.reversed{background-color:#ffcccc;}.red{color:#ff0000;}</style><p><b>Exercise 1.1.</b><br /><br />Below is a sequence of expressions. What is the result printed by the interpreter in response to each expression? Assume that the sequence is to be evaluated in the order in which it is presented.</p><blockquote class="code">10<br />(+ 5 3 4)<br />(- 9 1)<br />(/ 6 2)<br />(+ (* 2 4) (- 4 6))<br />(define a 3)<br />(define b (+ a 1))<br />(+ a b (* a b))<br />(= a b)<br />(if (and (> b a) (< b (* a b)))<br /> b<br /> a)<br />(cond ((= a 4) 6)<br /> ((= b 4) (+ 6 7 a))<br /> (else 25))<br />(+ 2 (if (> b a) b a))<br />(* (cond ((> a b) a)<br /> ((< a b) b)<br /> (else -1))<br /> (+ a 1))</blockquote><p><em>Solution</em></p><blockquote class="code"><em>10<br />12<br />8<br />3<br />19<br />4<br />16<br />6<br />16</em></blockquote><p><b>Exercise 1.2.</b><br /><br />Translate the following expression into prefix form</p><blockquote class="code">5 + ⅓ + (2 - (3 - (6 + ⅓)))<br />————————————————————————————<br /> 3(6 - 2)(3 - 7)</blockquote><p><em>Solution</em></p><blockquote class="code">(/<br /> (+ 5<br /> 1/3<br /> (- 2<br /> (- 3<br /> (+ 6 1/3))))<br /> (* 3<br /> (- 6 2)<br /> (- 3 7)))</blockquote><p><b>Exercise 1.3.</b><br /><br />Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.<br /><br /><em>Solution</em></p><blockquote class="code">(define (sum-squares-largest-two a b c)<br /> (if (> a b)<br /> (if (> b c)<br /> (+ (sq a) (sq b))<br /> (+ (sq a) (sq c)))<br /> (if (> a c)<br /> (+ (sq a) (sq b))<br /> (+ (sq b) (sq c)))))<br />(define (sq x)<br /> (* x x))</blockquote><p><b>Exercise 1.4.</b><br /><br />Observe that our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behavior of the following procedure:</p><blockquote class="code">(define (a-plus-abs-b a b)<br /> ((if (> b 0) + -) a b))</blockquote><p><em>Solution</em><br /><br />If <span class="code">b</span> is larger than zero, the <span class="code">+</span> operation is used to combine <span class="code">a</span> and <span class="code">b</span>, otherwise the <span class="code">-</span> operation is used. The latter operation negates the negative (or zero) value of <span class="code">b</span>, and, in effect, adds the absolute value of <span class="code">b</span> to <span class="code">a</span>.<br /><br /><b>Exercise 1.5.</b><br /><br />Ben Bitdiddle has invented a test to determine whether the interpreter he is faced with is using applicative-order evaluation or normal-order evaluation. He defines the following two procedures:</p><blockquote class="code">(define (p) (p))<br /><br />(define (test x y)<br /> (if (= x 0)<br /> 0<br /> y))</blockquote><p>Then he evaluates the expression</p><blockquote class="code">(test 0 (p))</blockquote><p>What behavior will Ben observe with an interpreter that uses applicative-order evaluation? What behavior will he observe with an interpreter that uses normal-order evaluation? Explain your answer. (Assume that the evaluation rule for the special form if is the same whether the interpreter is using normal or applicative order: The predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression.)<br /><br /><em>Solution</em><br /><br />In the case of normal-order evaluation, <span class="code">(test 0 (p))</span> is evaluated as follows:</p><blockquote class="code"><span class="reversed">(test 0 (p))</span><br /><br /><span class="reversed">(if (= 0 0)<br /> 0<br /> (p)</span><br /><br />(if <span class="reversed">(= 0 0)</span><br /> 0<br /> (p)<br /><br />(if <span class="reversed">#t</span><br /> 0<br /> (p)<br /><br /><span class="reversed">0</span></blockquote><p>In the applicative order, <span class="code">(test 0 (p))</span> is evaluated as follows:</p><blockquote class="code"><span class="reversed">(test 0 (p))</span><br /><br />(test 0 <span class="reversed">(p)</span>)<br /><br />(test 0 (<span class="reversed">(p)</span>))<br /><br />(test 0 ((<span class="reversed">(p)</span>)))<br /><br />...</blockquote><p>The interpreter keeps adding parentheses around <span class="code">(p)</span> until infinity, and there will never be a result printed, because it will take forever to evaluate the expression <span class="code">(test 0 (p))</span>.<br /><br /><b>Exercise 1.6.</b><br /><br />Alyssa P. Hacker doesn't see why if needs to be provided as a special form. "Why can't I just define it as an ordinary procedure in terms of cond?" she asks. Alyssa's friend Eva Lu Ator claims this can indeed be done, and she defines a new version of if:</p><blockquote class="code">(define (new-if predicate then-clause else-clause)<br /> (cond (predicate then-clause)<br /> (else else-clause)))</blockquote><p>Eva demonstrates the program for Alyssa:</p><blockquote class="code">(new-if (= 2 3) 0 5)<br />5<br /><br />(new-if (= 1 1) 0 5)<br />0</blockquote><p>Delighted, Alyssa uses new-if to rewrite the <span class="code">square-root</span> program:</p><blockquote class="code">(define (sqrt-iter guess x)<br /> (new-if (good-enough? guess x)<br /> guess<br /> (sqrt-iter (improve guess x)<br /> x)))</blockquote><p>What happens when Alyssa attempts to use this to compute square roots? Explain.<br /><br /><em>Solution</em><br /><br />The program goes into an endless loop, because it keeps evaluating <span class="code">(sqrt-iter (improve guess x) x)</span> with new values for <span class="code">guess</span>, adding a <span class="code">new-if</span> in each iteration after the existing <span class="code">new-if</span>.<br /><br />The reason that this happens is because <span class="code">if</span> is a keyword and</p><blockquote class="code">(if <em>predicate</em> <em>consequent</em> <em>alternative</em>)</blockquote><p>is a special case, instead of a regular combination or a procedure (like <span class="code">new-if</span>). This means the order in which terms are evaluated in the <span class="code">if</span> special form is different than in the <span class="code">new-if</span> procedure.<br /><br />The special form <span class="code">if</span> evaluates the predicate first and if it returns a non-false value (everything else than <span class="code">#f</span>), it evaluates the consequence, never evaluating the alternative. This means that if there is a base case, the recursion will end at some point. In the original definition there is such a base case, namely when the absolute value of the difference between the square of the guess and the number value the <span>sqrt-iter</span> definition consumes is less than a certain constant value.<br /><br />When the <span class="code">new-if</span> procedure is used, the three argument expressions of the procedure call are evaluated before <span class="code">new-if</span> is applied to the evaluated expressions. In order to evaluate the third argument expression, which is a recurvive call to <span class="code">sqrt-iter</span>, the <span class="code">new-if</span> of that recursive call has to be evaluated first. Of course, this recursive call also has a third argument expression, with the same consequence of calling <span class="code">new-if</span> for that successive recursive call, and so on. The result is that <span class="code">new-if</span> calls are being added to the evaluation process and there is never going to be a base case that ends this. The program gets into an endless loop until the user halt it.<br /><br /><b>Exercise 1.7.</b><br /><br />The <span class="code">good-enough?</span> test used in computing square roots will not be very effective for finding the square roots of very small numbers. Also, in real computers, arithmetic operations are almost always performed with limited precision. This makes our test inadequate for very large numbers. Explain these statements, with examples showing how the test fails for small and large numbers. An alternative strategy for implementing <span class="code">good-enough?</span> is to watch how guess changes from one iteration to the next and to stop when the change is a very small fraction of the guess. Design a <span class="code">square-root</span> procedure that uses this kind of end test. Does this work better for small and large numbers?<br /><br /><em>Solution</em><br /><br />For <span class="code">x < 1e-6</span>, the square root of <span class="code">x</span> is always smaller than <span class="code">0.001</span>, so the absolute value of the difference between the square of <span class="code">guess</span> and <span class="code">x</span> will always be smaller than <span class="code">0.001</span>, and the result of <span class="code">good-enough?</span> will always be a <span class="code">true</span> value.<br /><br />In real computers, if <span class="code">x</span> is sufficiently large, the number of decimal places will be too small to hold enough precision to let <span class="code">guess²</span> close in on <span class="code">x</span>.</p><blockquote class="code">(define (sqrt x)<br /> (sqrt-iter 2.0 1.0 x))<br /><br />(define (sqrt-iter old-guess guess x)<br /> (if (good-enough? old-guess guess)<br /> guess<br /> (sqrt-iter guess (improve guess x)<br /> x)))<br /><br />(define (good-enough? old-guess guess)<br /> (<<br /> (if (< old-guess guess)<br /> (/ guess old-guess)<br /> (/ old-guess guess))<br /> 1.001))<br /><br />(define (improve guess x)<br /> (average guess (/ x guess)))<br /><br />(define (average x y)<br /> (/ (+ x y) 2))</blockquote><p><b>Exercise 1.8.</b><br /><br />Newton's method for cube roots is based on the fact that if <span class="code">y</span> is an approximation to the cube root of <span class="code">x</span>, then a better approximation is given by the value</p><blockquote class="code">x/y<sup>2</sup> + 2y<br />—————————<br /> 3</blockquote><p>Use this formula to implement a cube-root procedure analogous to the <span class="code">square-root</span> procedure. (In section 1.3.4 we will see how to implement Newton's method in general as an abstraction of these <span class="code">square-root</span> and <span class="code">cube-root</span> procedures.)<br /><br /><em>Solution</em></p><blockquote class="code">(define (cube-root x)<br /> (cube-root-iter 2.0 1.0 x))<br /><br />(define (cube-root-iter old-guess guess x)<br /> (if (good-enough? old-guess guess)<br /> guess<br /> (cube-root-iter guess (improve guess x)<br /> x)))<br /><br />(define (good-enough? old-guess guess)<br /> (<<br /> (if (< old-guess guess)<br /> (/ guess old-guess)<br /> (/ old-guess guess))<br /> 1.001))<br /><br />(define (improve guess x)<br /> (/ (+ (/ x (sqr guess)) (* 2 guess)) 3))</blockquote>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-77954428422318422232007-03-12T14:47:00.000-07:002007-03-12T15:07:02.450-07:00What is a Good First Programming Language?While Googling, I came across the web article <a href="http://www.acm.org/crossroads/xrds10-4/firstlang.html" target="_blank">What is a Good First Programming Language</a>, by Diwaker Gupta. In short, it depends on the audience. For first-graders, qBasic is probably a good choice, while for college freshmen, C is probably the best choice for a first programming language.<br /><br />My first language was Apple II Basic, followed by 6502 micro-assembler, in college, late 1970s (actually, I learned Fortran first, on a mainframe PDP computer, with punch cards input and teletype printout; the programs were written ('developed') by hand with pen and paper, and transfered along with the data onto punch cards, which where read by a punch card reader; next, you needed to wait a few hours for your program to be executed and the results printed on a line printer, collected by an assistant, who put it in your print bin). Later on, I bought a Commodore 64, learned Basic, micro-assembler, hexcoding, macro-assembler, and Pascal. I did some C, C++, Java, JavaScript, Python and Lua, and now I'm learning Scheme. So I can claim that Scheme is certainly not my first language (and probably not my last as well).Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-12980902169227117752007-03-12T08:41:00.000-07:002007-03-12T08:43:21.984-07:00How to Design Programs - 3.3 Finger Exercises on Composing Functions<style>.code{font-family:monospace;}.overline{text-decoration:overline;}.reversed{background-color:#ffcccc;}.red{color:#ff0000;}</style><p><b>Exercise 3.3.1.</b><br /><br />The United States uses the English system of (length) measurements. The rest of the world uses the metric system. So, people who travel abroad and companies that trade with foreign partners often need to convert English measurements to metric ones and vice versa.<br /><br />Here is a table that shows the six major units of length measurements of the English system:</p><p><table border="0"><tr style="text-align:center"><th>English</th><td></td><th colspan="2">metric</th></tr><tr style="text-align:center"><td><br />1 inch</td><td>=</td><td>2.54</td><td>cm</td></tr><tr style="text-align:center"><td><br />1 foot</td><td>=</td><td>12</td><td>in.</td></tr><tr style="text-align:center"><td><br />1 yard</td><td>=</td><td>3</td><td>ft.</td></tr><tr style="text-align:center"><td>1 rod</td><td>=</td><td>5(1/2)</td><td>yd.</td></tr><tr style="text-align:center"><td>1 furlong</td><td>=</td><td>40</td><td>rd.</td></tr><tr style="text-align:center"><td>1 mile</td><td>=</td><td>8</td><td>fl.</td></tr></table></p><p>Develop the functions <span class="code">inches->cm</span>, <span class="code">feet->inches</span>, <span class="code">yards->feet</span>, <span class="code">rods->yards</span>, <span class="code">furlongs->rods</span>, and <span class="code">miles->furlongs</span>.<br /><br />Then develop the functions <span class="code">feet->cm</span>, <span class="code">yards->cm</span>, <span class="code">rods->inches</span>, and <span class="code">miles->feet</span>.<br /><br /><b>Hint:</b> Reuse functions as much as possible. Use variable definitions to specify constants.<br /><br /><em>Solution</em></p><blockquote class="code">;; inches->cm : number -> number<br />;; convert inches into cm<br />(define (inches->cm inches)<br /> (* inches INCH->CM))<br /><br />;; feet->inches : number -> number<br />;; convert feet into inches<br />(define (feet->inches feet)<br /> (* feet FOOT->INCH))<br /><br />;; yards->feet : number -> number<br />;; convert yards into feet<br />(define (yards->feet yards)<br /> (* yards YARD->FOOT))<br /><br />;; rods->yards : number -> number<br />;; convert rods into yards<br />(define (rods->yards rods)<br /> (* rods ROD->YARD))<br /><br />;; furlongs->rods : number -> number<br />;; convert furlongs into rods<br />(define (furlongs->rods furlongs)<br /> (* furlongs FURLONG->ROD))<br /><br />;; miles->furlongs : number -> number<br />;; convert miles into furlongs<br />(define (miles->furlongs miles)<br /> (* miles MILE->FURLONG))<br /><br />(define MILE->FURLONG 8)<br />(define FURLONG->ROD 40)<br />(define ROD->YARD 5.5)<br />(define YARD->FOOT 3)<br />(define FOOT->INCH 12)<br />(define INCH->CM 2.54)<br /><br />;; feet->cm : number -> number<br />;; convert feet into cm<br />(define (feet->cm feet)<br /> (inches->cm<br /> (feet->inches feet)))<br /><br />;; yards->cm : number -> number<br />;; convert yards into cm<br />(define (yards->cm yards)<br /> (feet->cm<br /> (yards->feet yards)))<br /><br />;; rods->inches : number -> number<br />;; convert rods into inches<br />(define (rods->inches rods)<br /> (feet->inches<br /> (yards->feet<br /> (rods->yards rods))))<br /><br />;; miles->feet : number -> number<br />;; convert miles into feet<br />(define (miles->feet miles)<br /> (yards->feet<br /> (rods->yards<br /> (furlongs->rods<br /> (miles->furlongs miles)))))</blockquote><p><b>Exercise 3.3.2.</b><br /><br />Develop the program <span class="code">volume-cylinder</span>. It consumes the radius of a cylinder's base disk and its height; it computes the volume of the cylinder.<br /><br /><em>Solution</em></p><blockquote class="code">;; volume-cylinder : number number -> number<br />;; calculate volume of cylinder<br />;; example: (volume-cylinder 4 4) -> 201.06176<br />(define (volume-cylinder radius height)<br /> (*<br /> (area-circle radius)<br /> height))<br /><br />;; area-circle : number -> number<br />;; calculate area of circle<br />;; example: (area-circle 4) -> 50.26544<br />(define (area-circle radius)<br /> (* PI (sqr radius)))<br /><br />(define PI 3.14159)</blockquote><p><b>Exercise 3.3.3.</b><br /><br />Develop <span class="code">area-cylinder</span>. The program consumes the radius of the cylinder's base disk and its height. Its result is the surface area of the cylinder.<br /><br /><em>Solution</em></p><blockquote class="code">;; area-cylinder : number number -> number<br />;; calculate surface area of cylinder<br />;; example: (area-cylinder 4 4) -> 201.06176<br />(define (area-cylinder radius height)<br /> (+<br /> (* 2<br /> (area-circle radius))<br /> (* height<br /> (circumference-circle radius))))<br /><br />;; circumference-circle : number -> number<br />;; calculate circumference of circle<br />;; example: (circumference-circle 4) -> 25.13272<br />(define (circumference-circle radius)<br /> (* 2 <br /> (* PI radius)))<br /><br />;; area-circle : number -> number<br />;; calculate area of circle<br />;; example: (area-circle 4) -> 50.26544<br />(define (area-circle radius)<br /> (* PI (sqr radius)))<br /><br />(define PI 3.14159)</blockquote><p><b>Exercise 3.3.4.</b><br /><br />Develop the function <span class="code">area-pipe</span>. It computes the surface area of a pipe, which is an open cylinder. The program consumes three values: the pipe's inner radius, its length, and the thickness of its wall.<br /><br />Develop two versions: a program that consists of a single definition and a program that consists of several function definitions. Which one evokes more confidence?<br /><br /><em>Solution</em></p><blockquote class="code">;; area-pipe number number number -> number<br />;; calculate surface area of open pipe<br />;; example: (area-pipe-multi 3 5 0.1) -> 195.4697298<br />(define (area-pipe-multi inner-radius length thickness-wall)<br /> (+ <br /> (area-pipe-wall inner-radius length)<br /> (area-pipe-wall<br /> (+ inner-radius thickness-wall) <br /> length)<br /> (*<br /> 2<br /> (-<br /> (area-circle (+ inner-radius thickness-wall))<br /> (area-circle inner-radius)))))<br /><br />;; area-pipe-wall : number number -> number<br />;; calculate area of pipe wall<br />;; examples:<br />;; (area-pipe-wall 3 5) -> 94.2477<br />;; (area-pipe-wall 3.1 5) -> 97.38929<br />(define (area-pipe-wall radius length)<br /> (* (circumference-circle radius)<br /> length))<br /><br />;; area-circle : number -> number<br />;; calculate area of circle<br />;; examples:<br />;; (area-circle 3) -> 28.27431<br />;; (area-circle 3.1) -> 30.1906799<br />(define (area-circle radius)<br /> (* PI (sqr radius)))<br /><br />;; circumference-circle : number -> number<br />;; calculate circumference of circle<br />;; examples:<br />;; (circumference 3) -> 18.84954<br />;; (circumference 3.1) -> 19.477858<br />(define (circumference-circle radius)<br /> (* 2 PI radius))<br /><br />(define PI 3.14159)<br /><br />;; area-pipe : number number number -> number<br />;; calculate surface area of open pipe<br />(define (area-pipe radius length thickness-wall)<br /> (+<br /> (* 2 3.14159 radius length)<br /> (* 2 3.14159<br /> (+ radius thickness-wall)<br /> length)<br /> (* 2<br /> (-<br /> (* 3.14159 (sqr <br /> (+ radius thickness-wall)))<br /> (* 3.14159 (sqr radius))))))</blockquote><p>Obviously, the solution with the multiple definitions evokes more confidence, because you can develop a higher order function before getting into the details of the lower order functions.<br /><br /><b>Exercise 3.3.5.</b><br /><br />Develop the program <span class="code">height</span>, which computes the height that a rocket reaches in a given amount of time. If the rocket accelerates at a constant rate g, it reaches a speed of <span class="code">g * t</span> in t time units and a height of <span class="code">1/2 * v * t</span> where v is the speed at t.<br /><br /><em>Solution</em></p><blockquote class="code">;; height : number -> number<br />;; calculate height of rocket at certain time<br />;; example: (height 3) -> 45<br />(define (height time)<br /> (* 0.5 (speed time) time))<br /><br />;; speed : number -> number<br />;; calculate speed of rocket at certain time<br />;; example: (speed 3) -> 30<br />(define (speed time)<br /> (* G time))<br /><br />(define G 10)</blockquote><p><b>Exercise 3.3.6.</b><br /><br />Recall the program <span class="code">Fahrenheit->Celsius</span> from <a href="http://wanttowriteprograms.blogspot.com/2007/03/how-to-design-programs-22-variables-and.html">exercise 2.2.1</a>. The program consumes a temperature measured in Fahrenheit and produces the Celsius equivalent.<br /><br />Develop the program <span class="code">Celsius->Fahrenheit</span>, which consumes a temperature measured in Celsius and produces the Fahrenheit equivalent.<br /><br />Now consider the function</p><blockquote class="code">;; I : number -> number<br />;; to convert a Fahrenheit temperature to Celsius and back<br />(define (I f)<br /> (Celsius->Fahrenheit (Fahrenheit->Celsius f)))</blockquote><p>Evaluate (I 32) by hand and using DrScheme's stepper. What does this suggest about the composition of the two functions?<br /><br /><em>Solution</em></p><blockquote class="code">;; Fahrenheit->Celsius number -> number<br />;; examples:<br />;; (Fahrenheit->Celsius 32) -> 0<br />;; (Fahrenheit->Celsius 212) -> 100<br />(define (Fahrenheit->Celsius F)<br /> (* (- F 32) (/ 5 9)))<br /><br />;; Celsius->Fahrenheit number -> number<br />;; examples:<br />;; (Celsius->Fahrenheit 0) -> 32<br />;; (Celsius->Fahrenheit 100) -> 212<br />(define (Celsius->Fahrenheit C)<br /> (+ (* C (/ 9 5)) 32))<br /><br />;; I : number -> number<br />;; to convert a Fahrenheit temperature to Celsius and back<br />(define (I f)<br /> (Celsius->Fahrenheit (Fahrenheit->Celsius f)))</blockquote><p><span class="code">(I 32)</span> is <span class="code">Celsius->Fahrenheit</span> applied to <span class="code">(Fahrenheit-Celsius 32)</span><br /><br /><span class="code">(Fahrenheit-Celsius 32)</span><br />evaluates to<br /><span class="code">(/ (* (- 32 32) 5) 9)<br />(/ (* 0 5) 9)<br />(/ 0 9)<br />0</span><br /><br /><span class="code">(Celsius-Fahrenheit 0)</span><br />evaluates to<br /><span class="code">(+ (/ (* 0 9) 5) 32)<br />(+ (/ 0 5) 32)<br />(+ 0 32)<br />32</span><br /><br />DrScheme's Stepper:</p><blockquote class="code"><span class="reversed">(I 32)</span><br /><br /><span class="reversed">(Celsius->Fahrenheit<br /> (Fahrenheit->Celsius 32))</span><br /><br />(Celsius->Fahrenheit<br /> <span class="reversed">(Fahrenheit->Celsius 32)</span>)<br /><br />(Celsius->Fahrenheit<br /> <span class="reversed">(* (- 32 32) (/ 5 9))</span>)<br /><br />(Celsius->Fahrenheit<br /> (* <span class="reversed">(- 32 32)</span> (/ 5 9)))<br /><br />(Celsius->Fahrenheit<br /> (* <span class="reversed">0</span> (/ 5 9)))<br /><br />(Celsius->Fahrenheit<br /> (* <span class="reversed">(/ 5 9)</span>))<br /><br />(Celsius->Fahrenheit (* 0 <span class="reversed">5/9</span>))<br /><br />(Celsius->Fahrenheit <span class="reversed">(* 0 5/9)</span>)<br /><br />(Celsius->Fahrenheit <span class="reversed">0</span>)<br /><br /><span class="reversed">(Celsius->Fahrenheit 0)</span><br /><br /><span class="reversed">(+ (* 0 (/ 9 5)) 32)</span><br /><br />(+ (* 0 <span class="reversed">(/ 9 5)</span>) 32)<br /><br />(+ (* 0 <span class="reversed">9/5</span>) 32)<br /><br />(+ <span class="reversed">(* 0 9/5)</span> 32)<br /><br />(+ <span class="reversed">0</span> 32)<br /><br /><span class="reversed">(+ 0 32)</span><br /><br /><span class="reversed">32</span></blockquote><p>The constants <span>32</span> and <span>5/9</span> could be incorporated in both as variables.</p>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-23691174278577278802007-03-12T05:32:00.000-07:002007-03-12T05:35:52.192-07:00How to Design Programs - 3.2 Variable Definitions<style>.code{font-family:monospace;}.overline{text-decoration:overline;}.reversed{background-color:#ffcccc;}.red{color:#ff0000;}</style><blockquote class="code">;; How to design a program<br />(define (profit ticket-price)<br /> (- (revenue ticket-price)<br /> (cost ticket-price)))<br /><br />(define (revenue ticket-price)<br /> (* (attendees ticket-price) ticket-price))<br /><br />(define (cost ticket-price)<br /> (+ 180<br /> (* 0.04 (attendees ticket-price))))<br /><br />(define (attendees ticket-price)<br /> (+ 120<br /> (* (/ 15 .10) (- 5.00 ticket-price))))</blockquote><p><b>Exercise 3.2.1.</b><br /><br />Provide variable definitions for all constants that appear in the above profit program and replace the constants with their names.<br /><br /><em>Solution</em></p><blockquote class="code">;;; How to design a program<br />(define (profit ticket-price)<br /> (- (revenue ticket-price)<br /> (cost ticket-price)))<br /><br />(define (revenue ticket-price)<br /> (* (attendees ticket-price) ticket-price))<br /><br />(define (cost ticket-price)<br /> (+ FIXED-COST<br /> (* COST-PER-ATTENDEE (attendees ticket-price))))<br /><br />(define (attendees ticket-price)<br /> (+ ATTENDEES-AT-BASE-PRICE<br /> (*<br /> (/ <br /> MORE-ATTENDEES-PER-PRICE-DECREASE <br /> PRICE-DECREASE) <br /> (- BASE-PRICE ticket-price))))<br /><br />(define FIXED-COST 180)<br />(define COST-PER-ATTENDEE 0.04)<br />(define ATTENDEES-AT-BASE-PRICE 120)<br />(define BASE-PRICE 5.00)<br />(define MORE-ATTENDEES-PER-PRICE-DECREASE 15)<br />(define PRICE-DECREASE .10)</blockquote>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-22127610193386603542007-03-10T08:10:00.000-08:002007-03-10T08:17:57.094-08:00How to Design Programs - 3.1 Composing Functions<style>.code{font-family:monospace;}.overline{text-decoration:overline;}.reversed{background-color:#ffcccc;}.red{color:#ff0000;}</style><p>Consider the following problem:</p><blockquote><p>Imagine the owner of a movie theater who has complete freedom in setting ticket prices. The more he charges, the fewer the people who can afford tickets. In a recent experiment the owner determined a precise relationship between the price of a ticket and average attendance. At a price of $5.00 per ticket, 120 people attend a performance. Decreasing the price by a dime ($.10) increases attendance by 15. Unfortunately, the increased attendance also comes at an increased cost. Every performance costs the owner $180. Each attendee costs another four cents ($0.04). The owner would like to know the exact relationship between profit and ticket price so that he can determine the price at which he can make the highest profit.</p></blockquote><p><b>Exercise 3.1.1.</b><br /><br />The next step is to make up examples for each of the functions. Determine how many attendees can afford a show at a ticket price of $3.00, $4.00, and $5.00. Use the examples to formulate a general rule that shows how to compute the number of attendees from the ticket price. Make up more examples if needed.<br /><br /><em>Solution</em></p><ul><li>120 people can afford 5 dollar per ticket</li><li>decreasing the ticket price by 0.1 dollar increases attendance by 15<br />or:<br />decreasing the ticket price by 1 dollar increases attendance by 150</br><br />or:<br />for every dollar less, 150 more people will attend</li><li>if the ticket price is decreased by 5 dollar, 870 people will attend<br />so:<br />number of people = 870 - (price in dollars) * (150 per dollar)</li></ul><table border="0"><tr style="text-align:center;"><th>price</th><th>attendees</th></tr><tr style="text-align:center;"><td>5</td><td>120</td></tr><tr style="text-align:center;"><td>4</td><td>270</td></tr><tr style="text-align:center;"><td>3</td><td>420</td></tr><tr style="text-align:center;"><td>2</td><td>570</td></tr><tr style="text-align:center;"><td>1</td><td>720</td></tr><tr style="text-align:center;"><td>0</td><td>870</td></tr></table><br /><p><b>Exercise 3.1.2.</b><br /><br />Use the results of exercise 3.1.1 to determine how much it costs to run a show at $3.00, $4.00, and $5.00. Also determine how much revenue each show produces at those prices. Finally, figure out how much profit the monopolistic movie owner can make with each show. Which is the best price (of these three) for maximizing the profit?<br /><br /><em>Solution</em></p><ul><li>the costs are 180 dollars, plus 0.04 dollars timers the number of attendees</li><li>the revenue is the number of attendees times the ticket price</li><li>profit is revenue minus cost</li></ul><table border="0"><tr style="text-align:center;"><th>price</th><th>attendees</th><th>cost</th><th>revenue</th><th>profit</th></tr><tr style="text-align:center;"><td>5</td><td>120</td><td>184.8</td><td>600</td><td>415.2</td></tr><tr style="text-align:center;"><td>4</td><td>270</td><td>190.8</td><td>1080</td><td>889.2</td></tr><tr style="text-align:center;"><td>3</td><td>420</td><td>196.8</td><td>1260</td><td>1063.2</td></tr><tr style="text-align:center;"><td>2</td><td>570</td><td>202.8</td><td>1140</td><td>937.2</td></tr><tr style="text-align:center;"><td>1</td><td>720</td><td>208.8</td><td>720</td><td>511.2</td></tr><tr style="text-align:center;"><td>0</td><td>870</td><td>214.8</td><td>0</td><td>-214.8</td></tr></table><br /><p>$3.00 is the best price of the three.</p><blockquote class="code">;; How to design a program<br />(define (profit ticket-price)<br /> (- (revenue ticket-price)<br /> (cost ticket-price)))<br /><br />(define (revenue ticket-price)<br /> (* (attendees ticket-price) ticket-price))<br /><br />(define (cost ticket-price)<br /> (+ 180<br /> (* .04 (attendees ticket-price))))<br /><br />(define (attendees ticket-price)<br /> (+ 120<br /> (* (/ 15 .10) (- 5.00 ticket-price))))</blockquote><blockquote class="code">;; How not to design a program<br /> (define (profit price)<br /> (- (* (+ 120<br /> (* (/ 15 .10)<br /> (- 5.00 price)))<br /> price)<br /> (+ 180<br /> (* .04<br /> (+ 120<br /> (* (/ 15 .10)<br /> (- 5.00 price)))))))</blockquote><p><b>Exercise 3.1.3.</b><br /><br />Determine the profit that the movie owner makes at $3.00, $4.00, and $5.00 using both program definitions. Make sure that the results are the same as those predicted in exercise 3.1.2.<br /><br /><em>Solution</em></p><blockquote class="code">;; How to design a program<br />> (profit 5)<br />415.2<br />> (profit 4)<br />889.2<br />> (profit 3)<br />1063.2</blockquote><blockquote class="code">;; How not to design a program<br />> (profit 5)<br />415.2<br />> (profit 4)<br />889.2<br />> (profit 3)<br />1063.2</blockquote><p>The results are the same as before.<br /><br /><b>Exercise 3.1.4.</b><br /><br />After studying the cost structure of a show, the owner discovered several ways of lowering the cost. As a result of his improvements, he no longer has a fixed cost. He now simply pays $1.50 per attendee.<br /><br />Modify both programs to reflect this change. When the programs are modified, test them again with ticket prices of $3.00, $4.00, and $5.00 and compare the results.<br /><br /><em>Solution</em><blockquote class="code">;; How to design a program<br />(define (profit ticket-price)<br /> (- (revenue ticket-price)<br /> (cost ticket-price)))<br /><br />(define (revenue ticket-price)<br /> (* (attendees ticket-price) ticket-price))<br /><br />(define (cost ticket-price)<br /> (* 1.50 (attendees ticket-price)))<br /><br />(define (attendees ticket-price)<br /> (+ 120<br /> (* (/ 15 .10) (- 5.00 ticket-price))))</blockquote><blockquote class="code">> (profit 5)<br />420<br />> (profit 4)<br />675<br />> (profit 3)<br />630</blockquote><blockquote class="code">;; how not to design a program<br />(define (profit price)<br /> (- (* (+ 120<br /> (* (/ 15 .10)<br /> (- 5.00 price)))<br /> price)<br /> (* 1.50<br /> (+ 120<br /> (* (/ 15 .10)<br /> (- 5.00 price))))))</blockquote><blockquote class="code">> (profit 5)<br />420<br />> (profit 4)<br />675<br />> (profit 3)<br />630</blockquote><p>The results for both methods are the same. Compared to the results in exercise 3.1.3, a ticket price of $4.00 is more favorable, instead of the earlier $3.00.Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-25292347791961693422007-03-09T07:25:00.000-08:002007-03-21T04:25:33.958-07:00Towers of Hanoi - 3<style>.code{font-family:monospace;}.overline{text-decoration:overline;}.reversed{background-color:#ffcccc;}.red{color:#ff0000;}</style><p>Let's look at the steps for <span class="code">(move 3 1 2 3)</span>:</p><blockquote class="code">step disk from to spare<br /> 1 1 1 2 3<br /> 2 2 1 3 2<br /> 3 1 2 3 1<br /> 4 3 1 2 3<br /> 5 1 3 1 2<br /> 6 2 3 2 1<br /> 7 1 1 2 3</blockquote><p>Now reorder the lines on the disk row, in reverse order:<blockquote class="code">step disk from to spare<br /> 4 3 1 2 3<br /> 2 2 1 3 2<br /> 6 2 3 2 1<br /> 1 1 1 2 3<br /> 3 1 2 3 1<br /> 5 1 3 1 2<br /> 7 1 1 2 3</blockquote><p>This means disk 3 is moved once, disk 2 is moved twice, and disk 1 is moved four times. What causes this?<br /><br />See what happens for each disk:</p><ol><li>move pile on top of disk 3 on to spare</li><li>move disk to destination</li><li>move pile back on top of disk (at destination)</li></ol><p>So, for each move of a disk, the pile on top of it is moved twice as often:</p><ul><li>disk 3 is moved once</li><li>pile on top of disk 3 (disks 1 and 2) are moved twice</ul><ul><li>disk 2 is moved twice</li><li>for each move of disk 2, disk 1 on top of disk 2 is moved twice</li></ul><ul><li>disk 1 is moved four times</li></ul><p>More general for a pile of <span class="code">n</span> disks, for <span class="code">p</span> between <span class="code">1</span> and <span class="code">n</span>:</p><ol><li>move pile on top of disk p (consisting of disks 1 tru p-1) to spare</li><li>move disk p to destination</li><li>move pile at spare to destination</li></ol><ul><li>disk 1 tru p-1 is moved twice as often as disk p</li></ul><p>Therefore, the total number of moves is:</p><blockquote class="code">Sum(p=1 tru n) { 2<sup>n-p</sup> }</blockquote><p>or</p><blockquote class="code">2<sup>n</sup> - 1</blockquote><p>Another observation is that:</p><ul><li>disk 1 is always moved in odd steps (1, 3, 5, etc.)</li><li>disk 2 is always moved in steps 2, 6, 10, etc.</li><li>disk 3 is always moved in steps 4, 12, 20, etc.</li><li>disk p is always moved in step<blockquote class="code">2<sup>p-1</sup> mod 2<sup>p</sup></blockquote></li></ul><p>Look at the following moves, depending on the number of disks, <span class="code">n</span>:</p><blockquote class="code">n = 1<br />disk 1: from → to<br /><br />n = 2<br />disk 2: from → to<br />disk 1: from → spare → to<br /><br />n = 3<br />disk 3: from → to<br />disk 2: from → spare → to<br />disk 1: from → to → spare → from → to<br /><br />n = k<br />disk k-0: from → to<br />disk k-1: from → spare → to<br />disk k-2: from → to → spare → from → to<br />disk k-3: from → spare → to → from → spare → to → from → spare → to<br />...</blockquote><p>To find the <span class="code">disk</span> of a <span class="code">n</span> disk Towers of Hanoi puzzle, depending on the current value of <span class="code">step</span>, use this program:</p><blockquote class="code">;; find-disk-for-step: number number -> number<br />;; find the disk that is moved in a step<br />;; in a n high Tower of Hanoi<br />;; if step is out of range, then return a -1<br />(define (find-disk-for-step step n)<br /> (if (> step (- (expt 2 n) 1))<br /> -1<br /> (find-disk-for-step-loop step n 1)))<br />;; find-disk-loop number number number -> number<br />;; check which disk is moved in a certain step<br />;; of the Towers of Hanoi puzzle<br />;; seed this recursion with disk = 1<br />(define (find-disk-for-step-loop step n disk)<br /> (if (= (modulo step (expt 2 disk)) (expt 2 (- disk 1)))<br /> disk<br /> (find-disk-for-step-loop step n (+ disk 1))))</blockquote><p>The program consists of two definitions.<br /><br />There is a the definition called <span class="code">find-disk-for-step</span>, which consumes <span class="code">step</span> (which stands for the step, or move number, in the puzzle) and <span class="code">n</span> (which stands for the total number of disks in the puzzle), and produces either the <span class="code">disk</span> that is moved in that step, or a value of <span class="code">-1</span> if the value of <span class="code">step</span> is out of range (too high).<br /><br />Then there is the definition that is called from the first definition, as a helper definition. This second definition is called <span class="code">find-disk-for-step-loop</span>, which consumes <span class="code">step</span> and <span class="code">n</span>, and a <span class="code">disk</span> parameter, which should be seeded with the value <span class="code">1</span>. The definition tests if a <span class="code">disk</span> is moved for the given values of <span class="code">step</span> and <span class="code">n</span>. It checks if the following condition is true:</p><blockquote class="code">step mod 2<sup>disk</sup> == 2<sup>disk-1</sup></blockquote><p>if it is true, <span class="code">disk</span> has been found and is returned as a result, otherwise a higher value of <span class="code">disk</span> is tested, by recursing the <span class="code">find-disk-for-step-loop</span> with <span class="code">disk + 1</span> as an argument for the <span class="code">disk</span> parameter, and the same values as before for the other parameters.<br /><br />Now we now which disk is moved in a particular step, we can use what we have observed before to formulate a definition that finds the move of a <span class="code">disk</span> in a certain <span class="code">step</span>, expressed in the values of <span class="code">from</span>, <span class="code">to</span> and <span class="code">spare</span>, as used as arguments in <span class="code">(move n from to spare)</span>. Of course, we already know what <span class="code">disk</span> moves.<br /><br />What we observed was, that the bottom disk in the starting position, moves as follows:</p><blockquote>disk <span class="code">n</span>: <span class="code">from</span> → <span class="code">to</span></blockquote><p>The disk on top of the bottom disk, moves as follows:</p><blockquote>disk <span class="code">n-1</span>: <span class="code">from</span> → <span class="code">spare</span> → <span class="code">to</span></blockquote><p>The disk on top of that disk, moves as follows:</p><blockquote>disk <span class="code">n-2</span>: <span class="code">from</span> → <span class="code">to</span> → <span class="code">spare</span> → <span class="code">from</span> → <span class="code">to</span></blockquote><p>In general:</p><blockquote>disk <span class="code">n - </span>(even number):<br /><span class="code">from</span> → <span class="code">to</span> → <span class="code">spare</span> → <span class="code">from</span> → <span class="code">to</span> → <span class="code">spare</span> → ...<br /><br />disk <span class="code">n - </span>(odd number):<br /><span class="code">from</span> → <span class="code">spare</span> → <span class="code">to</span> → <span class="code">from</span> → <span class="code">spare</span> → <span class="code">to</span> → ...</blockquote><p>Restated as follows:</p><blockquote>if <span class="code">(modulo n 2)</span> is equal to <span class="code">(modulo disk 2)</span> then:<br /><span class="code">from</span> → <span class="code">to</span> → <span class="code">spare</span> → <span class="code">from</span> → <span class="code">to</span> → <span class="code">spare</span> → ...<br />else:<br /><span class="code">from</span> → <span class="code">spare</span> → <span class="code">to</span> → <span class="code">from</span> → <span class="code">spare</span> → <span class="code">to</span> → ...</blockquote><p>If we want to find how many times a disk has moved in the puzzle, based on the value of <span class="code">step</span>, we can use this formula:</p><blockquote class="code"><br /> step - 2<sup>disk-1</sup><br />moved = —————————————<br /> 2<sup>disk</sup></blockquote><p>If <span class="code">moved</span> is equal to zero, this particular disk hasn't moved. If it's equal to one, it has moved once, etc. We can use this to determine a move, once we have established which disk moves, which is based on the value of <span class="code">step</span>. Now about the details:<p><blockquote>if <span class="code">(modulo n 2)</span> is equal to <span class="code">(modulo disk 2)</span> then:<blockquote>in case<blockquote class="code">(= (modulo moved 3) 0)<br /> (print-move disk from to)</blockquote><blockquote class="code">(= (modulo moved 3) 1)<br /> (print-move disk to spare)</blockquote><blockquote class="code">(= (modulo moved 3) 2)<br /> (print-move disk spare from)</blockquote></blockquote>else:<blockquote>in case<blockquote class="code">(= (modulo moved 3) 0)<br /> (print-move disk from spare)</blockquote><blockquote class="code">(= (modulo moved 3) 1)<br /> (print-move disk spare to)</blockquote><blockquote class="code">(= (modulo moved 3) 2)<br /> (print-move disk to from)</blockquote></blockquote></blockquote><p>So, now we can run the value of <span class="code">step</span> from <span class="code">1</span> to <span class="code">2<sup>n</sup>-1</span>, inclusive, determine which <span class="code">disk</span> is moved, what the move is, and print that to the screen.<br /><br />This all is enough to write the definitions:</p><blockquote class="code">;; move : number number number number -> string<br />;; calculate moves for Towers of Hanoi<br />;; side effect: display move disk: from -> to<br />;; example:<br />;; (move 3 1 2 3)<br />;; 1: 1 -> 2<br />;; 2: 1 -> 3<br />;; 1: 2 -> 3<br />;; 3: 1 -> 2<br />;; 1: 3 -> 1<br />;; 2: 3 -> 2<br />;; 1: 1 -> 2<br />;; "done"<br />(define (move n from to spare)<br /> (move-loop n from to spare 1))<br /><br />;; calculate each move through iteration<br />;; using step as a counter<br />;; seed step with 1<br />(define (move-loop n from to spare step)<br /> (define disk (find-disk step n 1))<br /> (if (< step (expt 2 n))<br /> (begin<br /> (print-step-move step n disk from to spare)<br /> (move-loop n from to spare (+ step 1)))<br /> "done"))<br /><br />;; print a move of a disk<br />(define (print-step-move step n disk from to spare)<br /> (define moved (/ (- step (expt 2 (- disk 1))) (expt 2 disk)))<br /> (cond<br /> [(= (modulo n 2) (modulo disk 2))<br /> (cond<br /> [(= (modulo moved 3) 0)<br /> (print-move disk from to)]<br /> [(= (modulo moved 3) 1)<br /> (print-move disk to spare)]<br /> [else<br /> (print-move disk spare from)])]<br /> [else<br /> (cond<br /> [(= (modulo moved 3) 0)<br /> (print-move disk from spare)]<br /> [(= (modulo moved 3) 1)<br /> (print-move disk spare to)]<br /> [else<br /> (print-move disk to from)])]))<br /><br />;; print a move<br />(define (print-move n from to)<br /> (begin<br /> (display n)<br /> (display ": ")<br /> (display from)<br /> (display " -> ")<br /> (display to)<br /> (newline)))<br /><br />;; find which disk is moved in the current step<br />(define (find-disk step n disk)<br /> (if (= (modulo step (expt 2 disk)) (expt 2 (- disk 1)))<br /> disk<br /> (find-disk step n (+ disk 1))))</blockquote><p>The iterative process is not necessarily faster than the recursive process, because, in contrast to the recursive process in the <a href="http://wanttowriteprograms.blogspot.com/2007/03/fibonacci-numbers.html">Fibonacci numbers</a>, there are no steps that could be calculated from earlier steps, or something.<br /><br />Remember, that in the Fibonacci number problem,</p><blockquote class="code">Fib(n) = Fib(n-1) - Fib(n-2)</blockquote><p>uses <span class="code">Fib(n-2)</span> when trying to calculate <span class="code">Fib(n-1)</span> (which is equal to <span class="code">Fib(n-2) + Fib(n-3)</span>). This lead to inefficiency when using the formulas straight in a code definition.<br /><br />In the Towers of Hanoi, on the other hand, there is no such inefficiency. A recursive or iterative process is just another way to express a solution to the problem.</p>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-85542310363914509962007-03-08T02:13:00.000-08:002007-03-21T04:26:46.901-07:00Towers of Hanoi - 2<style>.code{font-family:monospace;}.overline{text-decoration:overline;}.reversed{background-color:#ffcccc;}.red{color:#ff0000;}.rev1{background-color:#ffcccc;}.rev2{background-color:#ccffcc;}.rev3{background-color:#ffffcc;}</style><p>In the video tutorial 1b of the <a href="http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/" target="_blank">MIT Lisp video tutorials</a>, the solution of the Towers of Hanoi puzzle is expressed as this Lisp definition:</p><blockquote class="code">(define (move n from to spare)<br /> (cond<br /> ((= n 0) "done" )<br /> (else)<br /> <span class="rev1">(move (-1+ n) from spare to)</span><br /> <span class="rev2">(print-move n from to)</span><br /> <span class="rev3">(move (-1+ n) spare to from)</span>)))<br /></blockquote><p>I have translated that into DrScheme, using Textual (MzScheme, includes R5RS), which can be found at the end of this posting (see <a href="#program">Program</a>).<br /><br />Now look at the program trace of <span class="code">(move 3 1 2 3)</span>, using substitution (as explained in the video tutorial):</p><blockquote class="code">(move 3 1 2 3) ;; n T F S<br /> <span class="rev1">(move (-1+ 3) 1 3 2)</span> ;; 3 1 2 3<br /> <span class="rev1">(move (-1+ 2) 1 2 3)</span> ;; 2 1 3 2<br /> <span class="rev1">(move (-1+ 1) 1 3 2)</span> ;; 1 1 2 3<br /> "done" ;; 0 1 3 2<br /> <span class="rev2">(print-move 1 1 2)</span> ;; 1 1 2 3<br /> <span class="rev3">(move (-1+ 1) 3 2 1)</span> ;; 1 1 2 3<br /> "done" ;; 0 3 2 1<br /> <span class="rev2">(print-move 2 1 3)</span> ;; 2 1 3 2<br /> <span class="rev3">(move (-1+ 2) 2 3 1)</span> ;; 2 1 3 2<br /> <span class="rev1">(move (-1+ 1) 2 1 3)</span> ;; 1 2 3 1<br /> "done" ;; 0 2 1 3<br /> <span class="rev2">(print-move 1 2 3)</span> ;; 1 2 3 1<br /> <span class="rev3">(move (-1+ 1) 1 3 2)</span> ;; 1 2 3 1<br /> <span class="rev2">(print-move 3 1 2)</span> ;; 3 1 2 3<br /> <span class="rev3">(move (-1+ 3) 3 2 1)</span> ;; 3 1 2 3<br /> <span class="rev1">(move (-1+ 2) 3 1 2)</span> ;; 2 3 2 1<br /> <span class="rev1">(move (-1+ 1) 3 2 1)</span> ;; 1 3 1 2<br /> "done" ;; 0 3 2 1<br /> <span class="rev2">(print-move 1 3 1)</span> ;; 1 3 1 2<br /> <span class="rev3">(move (-1+ 1) 2 1 3)</span> ;; 1 3 1 2<br /> "done" ;; 0 2 1 3<br /> <span class="rev2">(print-move 2 3 2)</span> ;; 2 3 2 1<br /> <span class="rev3">(move (-1+ 2) 1 2 3)</span> ;; 2 3 2 1<br /> <span class="rev1">(move (-1+ 1) 1 3 2)</span> ;; 1 1 2 3<br /> "done" ;; 0 1 3 2<br /> <span class="rev2">(print-move 1 1 2)</span> ;; 1 1 2 3<br /> <span class="rev3">(move (-1+ 1) 3 2 1)</span> ;; 1 1 2 3<br /> "done" ;; 0 3 2 1</blockquote><p>I have used indentation to show how deep the trace is in the iteration (in essence, how low the value of <span class="code">n</span> is), and color coding to indicate which of the three steps is being executed inside the combination of the alternative expression (see <a href="http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Conditionals.html" target="_blank">MIT/GNU Scheme - Conditionals</a>) as used in the definition above. Furthermore, I have added in the comments fields the substituted values for <span class="code">n</span>, <span class="code">from</span>, <span class="code">to</span>, and <span class="code">spare</span> (<span class="code">n F T S</span>).<br /><br />As you can see, this is a recursive process, and certainly not an iteration. Now, can we rewrite this program, so it does an iterative process to solve the puzzle, instead of the current recursive process?</p><h2><a name="program"></a>Program</h2><blockquote class="code">;; Towers of Hanoi, solution 1<br /><br />;; move : number number number number -> string<br />;; calculate moves for Towers of Hanoi<br />;; side effect: display move disk: from -> to<br />;; example:<br />;; (move 3 1 2 3)<br />;; 1: 1 -> 2<br />;; 2: 1 -> 3<br />;; 1: 2 -> 3<br />;; 3: 1 -> 2<br />;; 1: 3 -> 1<br />;; 2: 3 -> 2<br />;; 1: 1 -> 2<br />;; "done"<br />(define (move n from to spare)<br /> (cond<br /> [(= n 0) "done" ]<br /> [else (begin<br /> (move (-1+ n) from spare to)<br /> (print-move n from to)<br /> (move (-1+ n) spare to from))]))<br />(define (print-move n from to)<br /> (begin<br /> (display n)<br /> (display ": ")<br /> (display from)<br /> (display " -> ")<br /> (display to)<br /> (newline)))<br />(define (-1+ x)<br /> (- x 1))</blockquote>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-81529597046935830602007-03-07T04:47:00.000-08:002007-03-21T04:26:20.285-07:00Towers of Hanoi<style>.code{font-family:monospace;}.overline{text-decoration:overline;}.reversed{background-color:#ffcccc;}.red{color:#ff0000;}</style><p>The <a href="http://en.wikipedia.org/wiki/Tower_of_Hanoi" target="_blank">Towers of Hanoi</a> puzzle is not that easy to solve. If you want to play a digital version of that puzzle, go to <a href="http://www.dynamicdrive.com/dynamicindex12/towerhanoi.htm" target="_blank">Towers of Hanoi DHTML game</a>.<br /><br />Now let's see how to solve a four disk puzzle.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgoIr6OdaVa08s5wGbatbcVydoqKPPaCZA0Uo9OCDWSk7J0JR5Bb2oaRUdj7PEIttgiG_uVm9hvnewtsQqoEYxND6-82I4hZYQPTrduLWyRV9XqRdls2w7udaZ5JV9NPJFnJJdXkOb97SAB/s1600-h/01.png"><img style="cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgoIr6OdaVa08s5wGbatbcVydoqKPPaCZA0Uo9OCDWSk7J0JR5Bb2oaRUdj7PEIttgiG_uVm9hvnewtsQqoEYxND6-82I4hZYQPTrduLWyRV9XqRdls2w7udaZ5JV9NPJFnJJdXkOb97SAB/s400/01.png" alt="" id="BLOGGER_PHOTO_ID_5039163859588427474" border="0" /></a><br /><br />This is the start position.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgyChkJ5Mka-nQg6Nxk0IDbOSqK1Cyu8LQKxFdyuGNQeElxhVS5Uw_8Id0ew22C_NT6GDS4j1xiGzKo1fTs9pv4xMXv8L71LhuaNpER7d7MdVnBd9iTN-bT5dUN-C6_eO698-ho4FZS5zRG/s1600-h/16.png"><img style="cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgyChkJ5Mka-nQg6Nxk0IDbOSqK1Cyu8LQKxFdyuGNQeElxhVS5Uw_8Id0ew22C_NT6GDS4j1xiGzKo1fTs9pv4xMXv8L71LhuaNpER7d7MdVnBd9iTN-bT5dUN-C6_eO698-ho4FZS5zRG/s400/16.png" alt="" id="BLOGGER_PHOTO_ID_5039164310559993570" border="0" /></a><br /><br />And this is the end position.<br /><br />A step in between the start and end position could be something like this:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjiPtcbVrqY3oCt05JsA9_G1ColKm5qyXxrtsQnbBELNPXEn5ZyNPCcpT3Cwxw1G1uCa9hyO2r4fOPa4NPVOpeAwD6vYEJu8y4Ihs7U1sMGpk5a6t-YFmeRUDqIgfWYcv_i1U7S2HzBuE1A/s1600-h/08.png"><img style="cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjiPtcbVrqY3oCt05JsA9_G1ColKm5qyXxrtsQnbBELNPXEn5ZyNPCcpT3Cwxw1G1uCa9hyO2r4fOPa4NPVOpeAwD6vYEJu8y4Ihs7U1sMGpk5a6t-YFmeRUDqIgfWYcv_i1U7S2HzBuE1A/s400/08.png" alt="" id="BLOGGER_PHOTO_ID_5039164933330251506" border="0" /></a><br /><br />Directly followed by this:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgVQiVe_0bbPxHIzTZz1SVXJRm6MmYtDirBcZkhZsgKDnAhKJUtrEPXwwq857B6INIoOc6UIFfNSDzz6gKr6m5cibFQEb4TRvFJHaDuGnldF3zgNwb9DnUa_V_IqnzHC7h_46bDYLXtVxEA/s1600-h/09.png"><img style="cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgVQiVe_0bbPxHIzTZz1SVXJRm6MmYtDirBcZkhZsgKDnAhKJUtrEPXwwq857B6INIoOc6UIFfNSDzz6gKr6m5cibFQEb4TRvFJHaDuGnldF3zgNwb9DnUa_V_IqnzHC7h_46bDYLXtVxEA/s400/09.png" alt="" id="BLOGGER_PHOTO_ID_5039165448726327042" border="0" /></a><br /><br />This is the only move the largest red disk will make.<br /><br />How about the next disk, the yellow one?<br /><br />Well, it has three positions, the start position, on tower 2 (while the red disk is still on tower 1), and on top of the red disk on tower 3):<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiRDRucLSMUkJCpG8LQL7IynlDU8cjOZQUaImcAgT7B8o-Ln0lU4_mgb9GRVUDDxt7WViI8jNZsPkSHGfn5tGMaeM1uYZGqffysNL-ENO9zh1aGSHukLtJYlrZM_NhWlsBjcgF4MfFtxsp8/s1600-h/05.png"><img style="cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiRDRucLSMUkJCpG8LQL7IynlDU8cjOZQUaImcAgT7B8o-Ln0lU4_mgb9GRVUDDxt7WViI8jNZsPkSHGfn5tGMaeM1uYZGqffysNL-ENO9zh1aGSHukLtJYlrZM_NhWlsBjcgF4MfFtxsp8/s400/05.png" alt="" id="BLOGGER_PHOTO_ID_5039167171008212754" border="0" /></a><br /><br />The red disk hasn't moved yet, and the yellow disk have moved to tower 2.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgsgO6tnGfWat8xxSilg6S1rctzkNdsREKRoZSBSA76gUw84dObMIw0yQ1k4Po41m01oEOwNqL2IZnfCFTznM7yQmkoIJUY9HuPqwA_PFSTg-qBxGzgvr0W_RV6m3OHk9SReS3e6nsM5IVC/s1600-h/13.png"><img style="cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgsgO6tnGfWat8xxSilg6S1rctzkNdsREKRoZSBSA76gUw84dObMIw0yQ1k4Po41m01oEOwNqL2IZnfCFTznM7yQmkoIJUY9HuPqwA_PFSTg-qBxGzgvr0W_RV6m3OHk9SReS3e6nsM5IVC/s400/13.png" alt="" id="BLOGGER_PHOTO_ID_5039167523195531042" border="0" /></a><br /><br />The red disk has moved, and the yellow disk has moved on top of the red disk on tower 3.<br /><br />Now, let's recap what we've done so far:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8Fj0MLGDXxoCZIfExiCn3xT_5jBukbsJagC3xr-d_HWb_T8lxJaywQIkhqyNLunAVJXv6Oho_CI5un2-9fpY5LTIaE6utsJHzd47CYLzCl0CVYYN74doMss3Om4GCEc-RLaLNbg-v9TAW/s1600-h/red_yellow.png"><img style="cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg8Fj0MLGDXxoCZIfExiCn3xT_5jBukbsJagC3xr-d_HWb_T8lxJaywQIkhqyNLunAVJXv6Oho_CI5un2-9fpY5LTIaE6utsJHzd47CYLzCl0CVYYN74doMss3Om4GCEc-RLaLNbg-v9TAW/s400/red_yellow.png" alt="" id="BLOGGER_PHOTO_ID_5039172939149291314" border="0" /></a></p><ul><li>We have moved the disks on top of the red disk, to make the red disk free, and move it to it's final tower.</li><li>In order to make the red disk free to move from tower 1 to tower 3, we have to move the other disks to tower 2, with the yellow disk at the bottom of the pile of disks. In order to be able to move the yellow disk to tower 2, we need to move the disks on top of it to tower 3. Then we move the yellow disk to tower 2, and the other disks on top of the yellow disk on tower 2.</li><li>Once the red disk is on tower 3, we need to move the yellow disk on tower 2 to tower 3. In order to do that, we need to move the disks on top of the yellow disk to tower 1. After that, we can move the yellow disk on top of the red disk on tower 3.</li></ul><p>I see a pattern there, in order to move a disk at the bottom of a pile of disks, we need to move the disks on top of it to the spare tower. If you want to move a disk from tower O to tower D, the remaining tower S is the spare tower (where O, D, and S can either be one of 1, 2, 3). That smells like a recursive process.<br /><br />So this is the process:</p><ul><li>move disks on top of red disk to tower 2:<ul><li>move disks on top of yellow disk to tower 3:<ul><li>move cyan disk on top of green disk to tower 2</li><li>move green disk to tower 3</li><li>move cyan disk to tower 3, on top of green disk</li></ul></li><li>move yellow disk to tower 2</li><li>move disks on tower 3 to tower 2, on top of yellow disk:<ul><li>move cyan disk on top of green disk to tower 1, on top of red disk</li><li>move green disk to tower 2, on top of yellow disk</li><li>move cyan disk to tower 2, on top of green disk</li></ul></li></ul></li><li>move red disk to tower 3</li><li>move disks on tower 2 to tower 3, on top of red disk:<ul><li>move disks on top of yellow disk to tower 1:<ul><li>move cyan disk on top of green disk to tower 3</li><li>move green disk to tower 1</li><li>move cyan disk to tower 1, on top of green disk</li></ul></li><li>move yellow disk top tower 3, on top of red disk</li><li>move disks on tower 1 to tower 3, on top of yellow disk:<ul><li>move cyan disk on top of green disk to tower 2</li><li>move green disk to tower 3, on top of yellow disk</li><li>move cyan disk to tower 3, on top of green disk</li></ul></li></ul></li></ul><p>Here is an animation of this procedure:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg6_hB0HJLVqVcB5wHvvoSAWj4dcEHPWWkWdqd5Wch8fxbVbEJIdJsgqc9V66X21kTLejz5GNjA6V2PgDegwyWSlScF6ax4Y9eLyXUDBTjhKDemOyQU60LjzBe9MUUXdHXS4t23RKmk6jNI/s1600-h/complete.gif"><img style="cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg6_hB0HJLVqVcB5wHvvoSAWj4dcEHPWWkWdqd5Wch8fxbVbEJIdJsgqc9V66X21kTLejz5GNjA6V2PgDegwyWSlScF6ax4Y9eLyXUDBTjhKDemOyQU60LjzBe9MUUXdHXS4t23RKmk6jNI/s400/complete.gif" alt="" id="BLOGGER_PHOTO_ID_5039188688794365762" border="0" /></a><br /><br />If we study this more closely, we can see that in order to move a pile of disks from the origin to the destination, you need to:</p><ol><li>park the disks on top of the bottom disk to the spare</li><li>move the freed bottom disk to it's destination</li><li>move the parked pile back on the bottom disk</li></ol><p>That should be enough to understand the puzzle, but not quite enough to develop our program to solve the puzzle.</p>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-80172830661150077852007-03-04T11:56:00.000-08:002007-03-21T04:28:09.285-07:00Fibonacci numbers<style>.code{font-family:monospace;}.overline{text-decoration:overline;}.reversed{background-color:#ffcccc;}.red{color:#ff0000;}</style> <p>Fibonacci numbers can be defined as follows:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh7NnPwCV2dFFEp9ctIQ1bbrndboqdhBeVPeyZZ8HR1m360tPlq-6UNhKS1JzXTs_V7NsZuPju2lX3xkZfW_wyU9KK0-NBYEAx5OWksYYlLvRcDVW0w9zBD-U898g9r1GEtFWiBYUcgv_Z8/s1600-h/470072226d1629b5b6b973fdj6.png"><img style="cursor: pointer;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh7NnPwCV2dFFEp9ctIQ1bbrndboqdhBeVPeyZZ8HR1m360tPlq-6UNhKS1JzXTs_V7NsZuPju2lX3xkZfW_wyU9KK0-NBYEAx5OWksYYlLvRcDVW0w9zBD-U898g9r1GEtFWiBYUcgv_Z8/s400/470072226d1629b5b6b973fdj6.png" alt="" id="BLOGGER_PHOTO_ID_5038177485318278610" border="0" /></a><br /><br />We can simply write a Scheme program that does just that:</p><blockquote class="code">;; Fib : number -> number<br />;; calculate Fibonacci number<br />;; examples:<br />;; (Fib 0) -> 0<br />;; (Fib 1) -> 1<br />;; (Fib 5) -> 5<br />;; (Fib 10) -> 55<br />(define (Fib n)<br /> (cond <br /> [(< n 2) n]<br /> [else <br /> (+ <br /> (Fib (- n 1)) <br /> (Fib (- n 2)))]))</blockquote><p>Testing:</p><blockquote class="code">> (Fib 0)<br />0<br />> (Fib 1)<br />1<br />> (Fib 5)<br />5<br />> (Fib 10)<br />55</blockquote><p>Here is the trace of <span class="code">(Fib 4)</span>, leaving out the uninteresting bits:</p><blockquote class="code">(Fib 4)<br />(+ (Fib 3) (Fib (- 4 2)))<br />(+ (+ (Fib 2) (Fib (- 3 2))) (Fib (- 4 2)))<br />(+ (+ (+ (Fib 1) (Fib (- 2 2))) (Fib (- 3 2))) (Fib (- 4 2)))<br />(+ (+ (+ 1 (Fib 0)) (Fib (- 3 2))) (Fib (- 4 2)))<br />(+ (+ 1 (Fib 1)) (Fib (- 4 2)))<br />(+ 2 (Fib 2))<br />(+ 2 (+ (Fib 1) (Fib (- 2 2)))<br />(+ 2 (+ 1 (Fib 0)))<br />3</blockquote><p>Compare this with <span class="code">(Fib 3)</span>:</p><blockquote class="code"><br />(Fib 3)<br />(+ (Fib 2) (Fib (- 3 2)))<br />(+ (+ (Fib 1) (Fib (- 2 2))) (Fib (- 3 2)))<br />(+ (+ 1 (Fib 0)) (Fib (- 3 2)))<br />(+ 1 (Fib 1))<br />2</blockquote><p>According to the lecture video (see <a href="#credits">below</a>), in this process, space of <span class="code">Fib(n)</span> is proportional to <span class="code">n</span>, and time is proportional to <span class="code">Fib(n)</span>.<br /><br />Notice that some terms are calculated several times, which indicates code inefficiency. This is clearly not an iterative process, but rather some kind of recursive process.<br /><br />Can the program be rewritten so, that it does an iterative process, instead of the current recursive process?<br /><br />Well, how about starting the calculation from 2 and going upwards to <span class="code">n</span>? If <span class="code">n</span> is <span class="code">0</span> or <span class="code">1</span>, the answers are <span class="code">0</span> and <span class="code">1</span>, respectively. Then we use the following definition of <span class="code">Fibs</span>, in which we pass intermediate Fibonacci values as parameters of <span class="code">Fibs</span>, in a recursive fashion:</p><blockquote class="code">(define (Fibs a b c n)<br /> (cond<br /> [(> c n) b]<br /> [else (Fibs b (+ a b) (+ c 1) n)]))</blockquote><p>In this definition, <span class="code">b</span> is the previous Fibonacci number, <span class="code">a</span> is the Fibonacci number before that, <span class="code">c</span> indicates the order of the current intermediate Fibonacci number, and <span class="code">n</span> indicates the desired order for the Fibonacci number. We seed <span class="code">Fibs</span> with <span class="code">a = 0, b = 1, c = 2, n = n</span>.<br /><br />Let's try <span class="code">(Fibs 0 1 2 5)</span> in a trace:</p><blockquote class="code">(Fibs 0 1 2 5)<br />(Fibs 1 1 3 5)<br />(Fibs 1 2 4 5)<br />(Fibs 2 3 5 5)<br />(Fibs 3 5 6 5)<br />5</blockquote><p>We can see that the time of <span class="code">Fibs</span> is proportional to <span class="code">n</span>, and the space is proportional to <span class="code">1</span>. This, therefore, is an iteration process.<br /><br />Here is the complete program for calculating a Fibonacci number:</p><blockquote class="code">;; Fib : number -> number<br />;; calculate a Fibonacci number<br />;; e.g. (Fib 4) -> 3<br />;; e.g. (Fib 10) -> 55<br />(define (Fib n)<br /> (cond<br /> [(< n 2) n]<br /> [else (Fibs 0 1 2 n)]))<br />(define (Fibs a b c n)<br /> (cond<br /> [(> c n) b]<br /> [else (Fibs b (+ a b) (+ c 1) n)]))<br /></blockquote><p>And <span class="code">(Fib 10)</span> produces 55:</p><blockquote class="code">> (Fib 10)<br />55</blockquote><p>If you try out both programs with a really large number (say 100000), you will notice a distinct difference in speed. The second is much faster than the first.</p><h2><a name="credits"></a>Credits</h2><p>I have to confess that I didn't come up with the solutions myself.<br /><br />The first solution was taken from a Lisp tutorial video (lesson 1b of the <a href="http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/" target="_blank">MIT Lisp video tutorials</a>), and converted into Scheme.<br /><br />The second solution was taken from <a href="http://www.ics.uci.edu/~eppstein/161/960109.html" target="_blank">Lecture notes about Fibonacci numbers</a> by David Eppstein, professor of Computer Science. The code was written in Python, so I needed to convert from an imperative language notation into the declarative language notation of Scheme, which I had never done before. So there was indeed a, though modest, learning experience in all of this. On that same notes page are some alternative methods you could try.<br /><br />When in need for a solution, <a href="http://www.google.com/" target="_blank">Google is your friend</a>.</p>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-85125035845859867302007-03-04T01:46:00.000-08:002007-03-21T04:29:10.414-07:00Linear iteration and linear recursion<style>.code{font-family:monospace;}.overline{text-decoration:overline;}.reversed{background-color:#ffcccc;}.red{color:#ff0000;}</style><p>Although all loops in Scheme are done using recursion, the resulting code execution, can be quite different. Observe this <a href="http://planetmath.org/encyclopedia/PeanoArithmetic.html" target="_blank">peano arithmetic</a> (only increment and decrement by one) addition, taken from the lesson 1b (Procedures and Processes; Substitution Model) of the <a href="http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/" target="_blank">MIT Lisp video tutorial page</a> and modified for <a href="http://www.drscheme.org/" target="_blank">DrScheme</a> (also see this tutorial on <a href="http://video.google.com/videoplay?docid=-1634408017041876836" target="_blank">Google Video</a>):</p><blockquote class="code">;; plus1 : number number -> number<br />;; add two numbers<br />;; by only using increments and decrements<br />;; example : (plus1 3 5) should produce 8<br />(define (plus1 x y)<br /> (if (= x 0)<br /> y<br /> (plus1 (dec x) (inc y))))<br />(define (inc x)<br /> (+ x 1))<br />(define (dec x)<br /> (- x 1))<br /><br />(plus1 3 5)</blockquote><p>If we trace this <span class="code">(plus1 3 5)</span>, leaving out the uninteresting parts, we get this:</p><blockquote class="code">(plus1 3 5) |<br />(plus1 2 6) |<br />(plus1 1 7) | time = O(x)<br />(plus1 0 8) |<br />8 |<br />------------<br />space = O(1)<br /><br />linear iteration : time = O(x), space = O(1)</blockquote><p>The time it takes to run the code is proportional to the value of <span class="code">x</span>, in other words, ordinal to <span class="code">x</span> (<span class="code">O(x)</span>). The amount of memory storage it takes to execute this code, the space, is constant, or ordinal to <span class="code">1</span> (<span class="code">O(1)</span>). This is the hallmark of a linear iteration.<br /><br />If we modify the code of <span class="code">plus1</span>, so it delays the addition of <span class="code">y</span> until the end of the execution, we get something like this:</p><blockquote class="code">;; plus2 : number number -> number<br />;; add two numbers<br />;; by only using increments and decrements<br />;; example : (plus2 3 5) should produce 8<br />(define (plus2 x y)<br /> (if (= x 0)<br /> y<br /> (inc (plus2 (dec x) y))))<br />(define (inc x)<br /> (+ x 1))<br />(define (dec x)<br /> (- x 1))<br /><br />(plus2 3 5)</blockquote><p>If we trace <span class="code">(plus2 3 5)</span> as before, we get this:</p><blockquote class="code">(plus2 3 5) |<br />(inc (plus2 2 5)) |<br />(inc (inc (plus2 1 5))) |<br />(inc (inc (inc (plus2 0 5)))) | time = O(x)<br />(inc (inc (inc 5))) |<br />(inc (inc 6)) |<br />(inc 7) |<br />8 |<br />------------------------------<br /> space = O(x)<br /><br />linear recursion : time = O(x), space = O(x)</blockquote><p>Again, the number of steps is proportional to the value of <span class="code">x</span> (that there are twice as many steps doesn't matter at this point). However, the amount of space isn't constant, but proportional to value of <span class="code">x</span>. This is the hallmark of a linear recursion.<br /><br />Although both methods <span class="code">plus1</span> and <span class="code">plus2</span> use the same recursive looping technique, the resulting code execution (process) is quite different.<br /><br />There are two other interesting problems discussed in this video tutorial lesson, <a href="http://en.wikipedia.org/wiki/Fibonacci_number" target="_blank">Fibonacci numbers</a> and the <a href="http://en.wikipedia.org/wiki/Towers_of_Hanoi" target="_blank">Towers of Hanoi</a>. These can be expressed both as a recursive and an iterative process. I will discuss both problems in separate posts, once I've digested the concepts of this video tutorial.</p>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-3466014501872305322007-03-03T01:26:00.000-08:002007-03-12T15:40:22.111-07:00Software Development Process<p>I haven't considered that there are different methods to develop software, especially if it is done in collaboration.<br /><br />I have five interesting Wikipedia entries I should read and digest (entry summaries taken from Wikipedia): </p><dl><dt><a href="http://en.wikipedia.org/wiki/Software_development_process" target="_blank">Software development process</a></dt><dd>A software development process is a structure imposed on the development of a software product. Synonyms include software lifecycle and software process. There are several models for such processes, each describing approaches to a variety of tasks or activities that take place during the process.</dd><dt><a href="http://en.wikipedia.org/wiki/Waterfall_model" target="_blank">Waterfall model</a></dt><dd>The waterfall model is a sequential software development model (a process for the creation of software) in which development is seen as flowing steadily downwards (like a waterfall) through the phases of requirements analysis, design, implementation, testing (validation), integration, and maintenance. The origin of the term "waterfall" is often cited to be an article published in 1970 by W. W. Royce; ironically, Royce himself advocated an iterative approach to software development and did not even use the term "waterfall". Royce originally described what is now known as the waterfall model as an example of a method that he argued "is risky and invites failure".</dd><dt><a href="http://en.wikipedia.org/wiki/Iterative_development" target="_blank">Iterative and incremental development</a></dt><dd>Iterative and Incremental development is a software development process developed in response to the weaknesses of the more traditional waterfall model. The two most well known iterative development frameworks are the Rational Unified Process and the Dynamic Systems Development Method. Iterative and incremental development is also an essential part of Extreme Programming and all other agile software development frameworks.</dd><dt><a href="http://en.wikipedia.org/wiki/Agile_software_development" target="_blank">Agile software development</a></dt><dd>Agile software development is a conceptual framework for undertaking software engineering projects.<br /><br />There are a number of agile software development methods, such as those espoused by The Agile Alliance. Most agile methods attempt to minimize risk by developing software in short timeboxes, called iterations, which typically last one to four weeks. Each iteration is like a miniature software project of its own, and includes all of the tasks necessary to release the mini-increment of new functionality: planning, requirements analysis, design, coding, testing, and documentation. While an iteration may not add enough functionality to warrant releasing the product, an agile software project intends to be capable of releasing new software at the end of every iteration. In many cases, software is released at the end of each iteration. This is particuarly true when the software is web-based and can be released easily. Regardless, at the end of each iteration, the team reevaluates project priorities.<br /><br />Agile methods emphasize realtime communication, preferably face-to-face, over written documents. Most agile teams are located in a bullpen and include all the people necessary to finish software. At a minimum, this includes programmers and their "customers" (customers are the people who define the product; they may be product managers, business analysts, or actual customers). The bullpen may also include testers, interaction designers, technical writers, and managers.<br /><br />Agile methods also emphasize working software as the primary measure of progress. Combined with the preference for face-to-face communication, agile methods produce very little written documentation relative to other methods. This has resulted in criticism of agile methods as being undisciplined.</dd><dt><a href="http://en.wikipedia.org/wiki/Formal_method" target="_blank">Formal methods</a></dt><dd>In computer science and software engineering, formal methods are mathematically-based techniques for the specification, development and verification of software and hardware systems. The use of formal methods for software and hardware design is motivated by the expectation that, as in other engineering disciplines, performing appropriate mathematical analyses can contribute to the reliability and robustness of a design. However, the high cost of using formal methods means that they are usually only used in the development of high-integrity systems, where safety or security is important.</dd></dl><p>Of course, there are many more articles to read on this subject. There is a list on Wikipedia of all entries about the <a href="http://en.wikipedia.org/wiki/Category:Software_development_process" target="_blank">Software Development Process</a>.<br /><br />After listening to the <a href="http://www.cincomsmalltalk.com/userblogs/cincom/blogView?content=podcasts" target="_blank">Cincon Smalltalk podcast series</a> (of which most episodes have Industry Misinterpretations in their title), episode <a href="http://www.cincomsmalltalk.com/audio/2007/industry_misinterpretations-02-17-07.mp3" target="_blank">Industry Misinterpretations Episode 23: Retrospective Coherence</a> (MP3 file), I came to the conclusion that this topic, the software development process, is a really interesting.<br /><br />Some fun and interesting paraphrases from that podcast episode:</p><blockquote>Most people hear to listen, not to understand, like they have read-only memory</blockquote><blockquote>in order for a complex system to have resilience, it has to have some degree of inefficiency</blockquote><blockquote>process and code optimization should always be the last step in development, otherwise the system loses it's flexibility and ultimately breaks down</blockquote><blockquote>the purpose of most meetings is to keep people from taking responsibility</blockquote><p>And then there are many more profound notions in this episode. Be sure to listen, but be warned that the audio quality is a bit poor.</p>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-14529269986564759022007-03-02T15:37:00.000-08:002007-03-02T16:03:29.752-08:00How to read technical texts<p>Perhaps I should reveal a recipe how to read technical texts more efficiently. It is really simple:</p><ol><li>read the text through and try to keep track of the global ideas; stop if you lose track of the material, and restart from the point you started, using method 2</li><li>read the text more carefully, and do all the exercise and examples; stop if you lose track and get stuck in solving the exercise or doing the examples, and restart from the point you started, using method 3</li><li>read the text for a third time, do all the exercise and examples, and add some of yourself; stop if you get stuck</li></ol><p>Every time you get stuck, start over again from the point you started the last time, up to the point you got stuk. During the rereading of this part of the text, use a higher order method (1, 2, 3). So you could be reading little pieces of text, each time in another reading mode (1, 2, 3). Once you get past the point you got stuck in the text in the latest iteration, switch back to a lower order reading method.<br /><br />If you get stuck in step 3, you need to find alternative information sources to supplement your reading. Try to find those sources through <a href="http://www.google.com/" target="_blank">Google</a>, by using the items you didn't understand as search terms. It simply means you lack information you need to understand the text. Once you have grasped the new concepts, reread the difficult parts of the technical text, using method 3.<br /><br />You should have read the complete text at least three times, using methods 1, 2, and 3. Here is a diagram of the reading methods</p><blockquote>1) global reading without doing exercises and examples<br>-><br>2) detailed reading doing all exercises and examples<br>-><br>3) reading doing all exercises and examples with some examples of your own</blockquote>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-50167579332262262762007-03-02T11:52:00.000-08:002007-03-03T04:04:35.970-08:00Structure and Interpretation of Computer ProgramsThrough the <a href="http://codenewbie.com/forum/" target="_blank">Code Newbie forum</a> (I'm forum member Rasheed), I got a reference to <a href="http://mitpress.mit.edu/sicp/full-text/book/book.html" target="_blank">Structure and Interpretation of Computer Programs</a> by MIT Press. They use Scheme, just like that other great on-line book, <a href="http://www.htdp.org/" target="_blank">How to Design Programs</a> (also see <a href="http://wanttowriteprograms.blogspot.com/2007/02/why-this-blog.html">Why this blog?</a>, and the tag <a href="http://wanttowriteprograms.blogspot.com/search/label/How%20to%20Design%20Programs">How to Design Programs</a> on this blog).<br /><br />There is also a series of hour long lectures on Google video. I have here a list of videos I have found (lectures 9a, 9b, and 10a were missing when I did a search on Google Video):<ul><li><a href="http://video.google.com/videoplay?docid=5546836985338782440" target="_blank">Lecture 1a: Overview and Introduction to Lisp</a></li> <li><a href="http://video.google.com/videoplay?docid=-1634408017041876836" target="_blank">Lecture 1b: Procedures and Processes; Substitution Model</a></li> <li><a href="http://video.google.com/videoplay?docid=-3980624564484146912" target="_blank">Lecture 2a: Higher-order Procedures</a></li> <li><a href="http://video.google.com/videoplay?docid=-8799490545977047833" target="_blank">Lecture 2b: Compound Data</a></li> <li><a href="http://video.google.com/videoplay?docid=6594093439128145415" target="_blank">Lecture 3a: Henderson Escher Example </a></li> <li><a href="http://video.google.com/videoplay?docid=5571878527594356342" target="_blank">Lecture 3b: Symbolic Differentiation; Quotation</a></li> <li><a href="http://video.google.com/videoplay?docid=6196234900528730258" target="_blank">Lecture 4a: Pattern Matching and Rule-based Substitution</a></li> <li><a href="http://video.google.com/videoplay?docid=2524302227918976752" target="_blank"> Lecture 4b: Generic Operators</a></li> <li><a href="http://video.google.com/videoplay?docid=3727739741840340025" target="_blank">Lecture 5a: Assignment, State, and Side-effects</a></li> <li><a href="http://video.google.com/videoplay?docid=3370680209439308476" target="_blank">Lecture 5b: Computational Objects</a></li> <li><a href="http://video.google.com/videoplay?docid=-7496022041893185723" target="_blank">Lecture 6a: Streams, Part 1</a></li> <li><a href="http://video.google.com/videoplay?docid=4695893584856767001" target="_blank">Lecture 6b: Streams, Part 2</a></li> <li><a href="http://video.google.com/videoplay?docid=-5297666536291617925" target="_blank"> Lecture-7a: Metacircular Evaluator, Part 1</a></li> <li><a href="http://video.google.com/videoplay?docid=-1948330067288371542" target="_blank">Lecture 7b: Metacircular Evaluator, Part 2</a></li> <li><a href="http://video.google.com/videoplay?docid=3609395881121407059" target="_blank">Lecture 8a: Logic Programming, Part 1</a></li> <li><a href="http://video.google.com/videoplay?docid=7471042783128169794" target="_blank">Lecture 8b: Logic Programming, Part 2</a></li> <li><a href="http://video.google.com/videoplay?docid=-234489474016411632" target="_blank">Lecture 10b: Storage Allocation and Garbage Collection </a></li></ul><p>I also found the original videos, which you can download from <a href="http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/" target="_blank">this page</a>. That is perhaps the best way to retrieve the videos. You can either download or torrent a DIVX .avi or a MPEG video file from each of the 20 lectures (ten times a and b lessons). This was a good reason for me to start using the Azureus bit-torrent client, because I want these lessons burnt on DVD.</p>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com1tag:blogger.com,1999:blog-3145576600624739600.post-46432461401267285192007-03-02T08:38:00.000-08:002007-03-02T08:44:25.560-08:00How to Design Programs - 2.4 Errors<style>.code{font-family:monospace;}.overline{text-decoration:overline;}.reversed{background-color:#ffcccc;}.red{color:#ff0000;}</style><p>Here are the exercises and my solotions of Section 2.4, called "Errors", in <a href="http://htdp.org/" target="_blank">How to Design Programs</a>.<br /><br /><b>Exercise 2.4.1.</b><br /><br />Evaluate the following sentences in DrScheme, one at a time:</p><blockquote class="code">(+ (10) 20)<br />(10 + 20)<br />(+ +)</blockquote><p>Read and understand the error messages.<br /><br /><em>Solution</em></p><blockquote class="code">> (+ (<span class="reversed">10</span>) 20)<br /><span class="red">function call: expected a defined name or a primitive operation name after an open parenthesis, but found a number</span></blockquote><p>The number <span class="code">10</span> shouldn't be between parentheses here.</p><blockquote class="code">> (<span class="reversed">10</span> + 20)<br /><span class="red">function call: expected a defined name or a primitive operation name after an open parenthesis, but found a number</span></blockquote><p>The number <span class="code">10</span> is at the wrong position, it should read <span class="code">(+ 10 20)</span></p><blockquote class="code">> (+ <span class="reversed">+</span>)<br /><span class="red">+: this primitive operator must be applied to arguments; expected an open parenthesis before the primitive operator name</span></blockquote><p>There should be a value or expression at that position (followed by a second value or expression).<br /><br /><b>Exercise 2.4.2.</b><br /><br />Enter the following sentences, one by one, into DrScheme's Definitions window and click Execute:</p><blockquote class="code">(define (f 1)<br /> (+ x 10))<br /><br />(define (g x)<br /> + x 10)<br /><br />(define h(x) <br /> (+ x 10))</blockquote><p>Read the error messages, fix the offending definition in an appropriate manner, and repeat until all definitions are legal.<br /><br /><em>Solution</em></p><blockquote class="code">(define (f <span class="reversed">1</span>)<br /> (+ x 10))<br />__________<br /><br /><span class="red">define: expected a name for the function's 1st argument, but found a number</span></blockquote><p>The faulty <span class="code">1</span> should be replaced by a <span class="code">x</span>:</p><blockquote class="code">(define (f x)<br /> (+ x 10))</blockquote><p></p><blockquote class="code">(define (g x)<br /> + <span class="reversed">x</span> 10)<br />__________<br /><br /><span class="red">define: expected only one expression for the function body, but found at least one extra part</span></blockquote><p>There is a open parenthesis missing, and a close parenthesis should be added to the end:</p><blockquote class="code">(define (g x)<br /> (+ x 10))</blockquote><p><b>Exercise 2.4.3.</b><br /><br />Evaluate the following grammatically legal Scheme expressions in DrScheme's Interactions window:</p><blockquote class="code">(+ 5 (/ 1 0))<br /><br />(sin 10 20)<br /><br />(somef 10)</blockquote><p>Read the error messages.<br /><br /><em>Solution</em></p><blockquote class="code">> (+ 5 <span class="reversed">(/ 1 0)</span>)<br /><span class="red">/: division by zero</span><br />> <span class="reversed">(sin 10 20)</span><br /><span class="red">sin: expects 1 argument, given 2: 10 20</span><br />> (<span class="reversed">somef</span> 10)<br /><span class="red">reference to an identifier before its definition: somef</span></blockquote><p><b>Exercise 2.4.4.</b><br /><br />Enter the following grammatically legal Scheme program into the Definitions window and click the Execute button:</p><blockquote class="code">(define (somef x)<br /> (sin x x))</blockquote><p>Then, in the Interactions window, evaluate the expressions:</p><blockquote class="code">(somef 10 20)<br /><br />(somef 10)</blockquote><p>and read the error messages. Also observe what DrScheme highlights.<br /><br /><em>Solution</em></p><blockquote class="code">> <span class="reversed">(somef 10 20)</span><br /><span class="red">somef: this procedure expects 1 argument, here it is provided 2 arguments</span></blockquote><p>There should only be one argument, e.g. <span class="code">(somef 10)</span></p><blockquote class="code">(define (somef x)<br /> <span class="reversed">(sin x x)</span>)<br /><br />__________<br /><br />> (somef 10)<br /><span class="red">sin: expects 1 argument, given 2: 10 10</span></blockquote><p>The <span class="code">sin</span> primitive accepts only one argument, it should read <span class="code">(sin x)</span> in the definition.Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-46077401370141922612007-03-02T04:49:00.000-08:002007-03-02T04:53:32.368-08:00How to Design Programs - 2.3 Word Problems<style>.code{font-family:monospace;}.overline{text-decoration:overline;}</style><p>Here are the exercises and my solotions of Section 2.3, called "Word Problems", in <a href="http://htdp.org/" target="_blank">How to Design Programs</a>.<br /><br /><b>Exercise 2.3.1.</b><br /><br />Utopia's tax accountants always use programs that compute income taxes even though the tax rate is a solid, never-changing 15%. Define the program tax, which determines the tax on the gross pay.<br /><br />Also define <span class="code">netpay</span>. The program determines the net pay of an employee from the number of hours worked. Assume an hourly rate of $12.<br /><br /><em>Solution</em><br /><br />The gross pay is</p><blockquote class="code">gross = 12 * h</blockquote><p>the tax is 15% of the gross pay, or</p><blockquote class="code">tax = gross * 0.15</blockquote><p>The net pay is gross pay minus tax, or</p><blockquote class="code">netpay = grosspay - tax</blockquote><p>This means that both tax and net pay are depending on the number of hours worked.</p><blockquote class="code">(define (grosspay h)<br /> (* h 12))<br /><br />(define (tax h)<br /> (* (grosspay h) 0.15))<br /><br />(define (netpay h)<br /> (- (grosspay h) (tax h)))</blockquote><p><b>Exercise 2.3.2.</b><br /><br />The local supermarket needs a program that can compute the value of a bag of coins. Define the program <span class="code">sum-coins</span>. It consumes four numbers: the number of pennies, nickels, dimes, and quarters in the bag; it produces the amount of money in the bag.<br /><br /><em>Solution</em><br /><br />This is really easy:</p><blockquote class="code">value = pennies * 1 + nickels * 5 + dimes * 10 + quorters * 25</blockquote><p>or in DrScheme:</p><blockquote class="code">(define (sum-coins p n d q)<br /> (+ p (+ (* n 5) (+ (* d 10) (* q 25)))))<br /></blockquote><p><b>Exercise 2.3.3.</b><br /><br />An old-style movie theater has a simple profit function. Each customer pays $5 per ticket. Every performance costs the theater $20, plus $.50 per attendee. Develop the function <span class="code">total-profit</span>. It consumes the number of attendees (of a show) and produces how much income the attendees produce.<br /><br /><em>Solution</em><br /><br />Each performances brings in a revenue of:</p><blockquote class="code">revenue = attendees * 5</blockquote><p>The performance costs are:</p><blockquote class="code">cost = 20 + attendees * 0.5</blockquote><p>The profit is:</p><blockquote class="code">profit = revenue - cost</blockquote><p>or in DrScheme:</p><blockquote class="code">(define (revenue n)<br /> (* n 5))<br />(define (cost n)<br /> (+ 20 (* n 0.5)))<br />(define (total-profit n)<br /> (- (revenue n) (cost n)))</blockquote>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-75996451582687333182007-03-01T07:23:00.000-08:002007-03-12T08:18:43.837-07:00How to Design Programs - 2.2 Variables and Programs<style>.code{font-family:monospace;}.overline{text-decoration:overline;}</style><p>Here are the exercises and my solotions of Section 2.2, called "Variables and Programs", in <a href="http://htdp.org/" target="_blank">How to Design Programs</a>.<br /><br /><b>Exercise 2.2.1.</b><br /><br />Define the program <span class="code">Fahrenheit->Celsius,</span> which consumes a temperature measured in Fahrenheit and produces the Celsius equivalent. Use a chemistry or physics book to look up the conversion formula.<br /><br /><em>solution</em><br /><br />I found a formula <a href="http://www.plvwtelco.net/Temperature%20Conversion.htm" target="_blank">here</a>:</p><blockquote class="code">(F-32)*5/9 = C</blockquote><p>Expressing this in DrScheme:</p><blockquote class="code">(define (Fahrenheit->Celsius F)<br /> (* (- F 32) (/ 5 9)))</blockquote><p><b>Exercise 2.2.2.</b><br /><br />Define the program dollar->euro, which consumes a number of dollars and produces the euro equivalent. Use the currency table in the newspaper to look up the current exchange rate.<br /><br /><em>Solution</em><br /><br />Type this into <a href="http://www.google.com/" target="_blank">Google</a></p><blockquote class="code">1 dollar in euros</blockquote><p>The result was:</p><blockquote class="code">1 U.S. dollar = 0.757002271 Euros</blockquote><p>So we need to multiply the amount of dollars with <span class="code">0.757002271</span>:</p><blockquote class="code">(define (dollar->euro D)<br /> (* D 0.757002271))</blockquote><p><b>Exercise 2.2.3.</b><br /><br />Define the program triangle. It consumes the length of a triangle's side and the perpendicular height. The program produces the area of the triangle. Use a geometry book to look up the formula for computing the area of a triangle.<br /><br /><em>Solution</em><br /><br />According to <a href="http://www.mathgoodies.com/lessons/vol1/area_triangle.html" target="_blank">this math page</a>, the area of a triangle is calculated as follows:</p><blockquote class="code">A = (w * h) / 2</blockquote><p>This means expressed in DrSchema, as a function:</p><blockquote class="code">(define (triangle w h)<br /> (/ (* w h) 2))</blockquote><p><b>Exercise 2.2.4.</b><br /><br />Define the program convert3. It consumes three digits, starting with the least significant digit, followed by the next most significant one, and so on. The program produces the corresponding number. For example, the expected value of</p><blockquote class="code">(convert3 1 2 3)</blockquote><p>is <span class="code">321</span>. Use an algebra book to find out how such a conversion works.<br /><br /><em>Solution</em><br /><br />According to <a href="http://www.321know.com/plc21cx2.htm" target="_blank">this page</a>, a number like <span class="code">123</span> can be expressed as follows:</p><blockquote class="code">123 = 1 * 100 + 2 * 10 + 3</blockquote><p>So, if the digits are given in the reverse order, <span class="code">3, 2, 1</span>, then the first value should be multiplied by <span class="code">100</span>, the second with <span class="code">10</span>, and the products should be added together with the third digit. This gives the following program:</p><blockquote class="code">(define (convert3 n1 n2 n3)<br /> (+ n1 (+ (* 10 n2) (* 100 n3))))</blockquote><p><b>Exercise 2.2.5.</b><br /><br />A typical exercise in an algebra book asks the reader to evaluate an expression like</p><div align="center"><img src="http://img235.imageshack.us/img235/7665/curriculum1azg4io1.gif" /></div><p>for n = 2, n = 5, and n = 9. Using Scheme, we can formulate such an expression as a program and use the program as many times as necessary. Here is the program that corresponds to the above expression:</p><blockquote class="code">(define (f n)<br /> (+ (/ n 3) 2))</blockquote><p>First determine the result of the expression at <span class="code">n = 2</span>, <span class="code">n = 5</span>, and <span class="code">n = 9</span> by hand, then with DrScheme's stepper.<br /><br />Also formulate the following three expressions as programs:</p><div><ol><li class="code">n<sup>2</sup> + 10</li><li class="code">(1/2) · n<sup>2</sup> + 20</li><li class="code">2 - (1/n)</li></ol></div><p>Determine their results for <span class="code">n = 2</span> and <span class="code">n = 9</span> by hand and with DrScheme.<br /><br /><em>Solution</em><br /><br />For <span class="code">n = 2</span>, <span class="code">n = 5</span>, <span class="code">n = 9</span>,</p><div align="center"><img src="http://img235.imageshack.us/img235/7665/curriculum1azg4io1.gif" /></div><p>is <span class="code">2(2/3)</span>, <span class="code">3(2/3)</span>, and <span class="code">5</span>. With Stepper the results are <span class="code">8/3</span>, <span class="code">11/3</span>, and <span class="code">5</span>.<br /><br />For <span class="code">n = 2</span> and <span class="code">n = 9</span> in <span class="code">n<sup>2</sup> + 10</span>, the results are <span class="code">14</span> and <span class="code">91</span>.</p><blockquote class="code">(define (g n)<br /> (+ (sqr n) 10))</blockquote><p>gives:</p><blockquote class="code">> (g 2)<br />14<br />> (g 9)<br />91</blockquote><p>For <span class="code">n = 2</span> and <span class="code">n = 9</span> in <span class="code">(1/2) · n<sup>2</sup> + 20</span>, the results are <span class="code">22</span> and <span class="code">60(1/2)</span>.</p><blockquote class="code">(define (h n)<br /> (+ (* 1/2 (sqr n)) 20))</blockquote><p>gives:</p><blockquote class="code">> (h 2)<br />22<br />> (h 9)<br />60.5</blockquote><p>For <span class="code">n = 2</span> and <span class="code">n = 9</span> in <span class="code">2 - (1/n)</span>, the results are <span class="code">1(1/2)</span> and <span class="code">1(8/9)</span>.</p><blockquote class="code">(define (j n)<br /> (- 2 (/ 1 n)))</blockquote><p>gives:</p><blockquote class="code">> (j 2)<br />1.5<br />> (j 9)<br />1.<span class="overline">8</span><br /></blockquote><p>which are all correct.</p>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-47942448098153611262007-03-01T06:41:00.000-08:002007-03-01T13:41:46.208-08:00How to Design Programs - 2.1 Numbers and Arithmetic<style>.code{font-family:monospace;}</style><p>Here are the exercises and my solotions of Section 2.1, called "Numbers and Arithmetic", in <a href="http://htdp.org/" target="_blank">How to Design Programs</a>.<br /><br /><b>Exercise 2.1.1.</b><br /><br />Find out whether DrScheme has operations for squaring a number; for computing the sine of an angle; and for determining the maximum of two numbers.<br /><br /><em>Solution:</em><br /><br />In the Help Desk, Manuals, Beginning Student Language, there are these entries:</p><blockquote class="code">sqr : (num -> num)<br /><br />purpose: <br />to compute the square of a number<br /><br />sin : (num -> num)<br /><br />purpose: <br />to compute the sine of a number (radians)<br /><br />pi : real<br /><br />purpose: <br />the ratio of a circle's circumference to its diameter<br /><br />max : (real real ... -> real)<br /><br />purpose: <br />to determine the largest number</blockquote><p>Now, this would mean the following:</p><blockquote class="code">(define (square n)<br /> (sqr n))<br /><br />(define (sin-angle a)<br /> (sin (* (* 2 pi) (/ a 360))))<br /><br />(define (maximum n1 n2)<br /> (max n1 n2))</blockquote><p>Running this code gives the following output:</p><blockquote class="code">> (square 5)<br />25<br />> (sin-angle 90)<br />#i1.0<br />> (sin (/ pi 2))<br />#i1.0<br />> (sin-angle 180)<br />#i1.2246467991473532e-16<br />> (sin pi)<br />#i1.2246467991473532e-16<br />> (maximum 3 5)<br />5<br />> (maximum -3 -5)<br />-3</blockquote><p>So, there is the primitive <span class="code">sqr</span> to calculate the square of a number, you need to use a formula with <span class="code">pi</span> to convert from angles to radian, and there is the primitive <span class="code">max</span> to calculate the maximum of two numbers.<br /><br /><b>Exercise 2.1.2.</b><br /><br />Evaluate (sqrt 4), (sqrt 2), and (sqrt -1) in DrScheme. Then, find out whether DrScheme knows an operation for determining the tangent of an angle.<br /><br /><em>Solution:</em></p><blockquote class="code">> (sqrt 4)<br />2<br />> (sqrt 2)<br />#i1.4142135623730951<br />> (sqrt -1)<br />0+1i<br />> (tan (* (* 2 pi) (/ 45 360)))<br />#i0.9999999999999999</blockquote>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-40643862135889625052007-02-28T18:41:00.000-08:002007-02-28T19:58:03.808-08:00Free Pascal with Lazarus IDE<p>I'm on a Mac, and installing Free Pascal with the Lazarus integrated development environment (IDE) wasn't easy, and really not very automated once installed. It uses GTK+, which has to be installed using Fink. Then three additional files have to be installed (two for Lazarus, and one for the Free Pascal compiler). Lazarus is a X11 application (X11 is equivalent to X on Linux).<br /><br /><img src="http://img95.imageshack.us/img95/3526/lazarusaboutlogoty3.jpg" border="0" alt="" /><br /><br />I guess this is often the disadvantage of using open source software. It is somewhat more difficult to install, and the user experience is less well defined as with commercial and free software. Designing programs and designing user interfaces are two separate disciplines, few people have mastered both.</p><p><ul><li><a href="http://www.freepascal.org/" target="_blank">Free Pascal</a></li> <li><a href="http://www.lazarus.freepascal.org/" target="_blank">Lazarus Project</a></li></ul></p><p>I haven't really looked into this, but the <a href="http://www.taoyue.com/tutorials/pascal/" target="_blank">Learn Pascal Tutorial</a> by Taoyue.com seems to be a descent introduction into the Pascal Language. Because Pascal is a compiler language, developing small programs is somewhat less comfortable than with an interactive mode, as some of the more modern languages have baked into them. Nevertheless, Pascal is the descendant of Algol, and the forerunner of a plethora of C type languages (e.g. C, C++, Objective-C, C#, etc.).<br /><br />Should I mention that Free Pascal is compatible to Borland's Delphi? There was the original Pascal by Dr. Niklaus Wirth, Turbo Pascal by Borland Inc., Modula-2 (also by Wirth), and Delphi (by Borland). With both Free Pascal and Delphi it is possible to write GUI driven programs, and both compile lightning fast.</p>Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0tag:blogger.com,1999:blog-3145576600624739600.post-6639258382864747602007-02-28T15:35:00.000-08:002007-02-28T15:43:52.940-08:00J<img src="http://img207.imageshack.us/img207/4637/46187146wd6.png" border="0" alt="" style="float:left;margin-left:10px;" />J is a powerful abstract language, which is a direct descender of the (in)famous programming language APL (A Programming Language). While APL uses mathematical notation with non-standard characters (which makes it look very cryptic, thus the earlier infamous reference), J uses standard ASCII characters. The free development software (IDE) is governed by <a href="http://www.jsoftware.com/" target="_blank">JSoftware</a>. It has a graphical user interface and good documentation--even for novice programmers--built in.Renehttp://www.blogger.com/profile/16323552654626708636noreply@blogger.com0