mirror of
https://github.com/foo-dogsquared/wiki.git
synced 2025-01-31 01:57:54 +00:00
84 lines
20 KiB
HTML
84 lines
20 KiB
HTML
<!DOCTYPE html><html><head><meta name="viewport" content="width=device-width"/><meta charSet="utf-8"/><title>Structure and interpretation of computer programs</title><script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script><script id="MathJax-script" async="" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script><script type="text/x-mathjax-config">
|
|
MathJax = {
|
|
tex: {
|
|
inlineMath: [ ['$','$'], ['\(','\)'] ],
|
|
displayMath: [ ['$$','$$'], ['[',']'] ]
|
|
},
|
|
options = {
|
|
processHtmlClass = "math"
|
|
}
|
|
}
|
|
</script><meta name="next-head-count" content="6"/><link rel="preload" href="/wiki/_next/static/css/52fc2ba29703df73922c.css" as="style"/><link rel="stylesheet" href="/wiki/_next/static/css/52fc2ba29703df73922c.css" data-n-g=""/><noscript data-n-css=""></noscript><link rel="preload" href="/wiki/_next/static/chunks/main-ae4733327bd95c4ac325.js" as="script"/><link rel="preload" href="/wiki/_next/static/chunks/webpack-50bee04d1dc61f8adf5b.js" as="script"/><link rel="preload" href="/wiki/_next/static/chunks/framework.9d524150d48315f49e80.js" as="script"/><link rel="preload" href="/wiki/_next/static/chunks/commons.0e1c3f9aa780c2dfe9f0.js" as="script"/><link rel="preload" href="/wiki/_next/static/chunks/pages/_app-8e3d0c58a60ec788aa69.js" as="script"/><link rel="preload" href="/wiki/_next/static/chunks/940643274e605e7596ecea1f2ff8d83317a3fb76.4841a16762f602a59f00.js" as="script"/><link rel="preload" href="/wiki/_next/static/chunks/pages/%5B%5B...slug%5D%5D-1aa198f87ede1cd0e1dc.js" as="script"/></head><body><div id="__next"><main><h1>Structure and interpretation of computer programs</h1><section class="post-metadata"><span>Date: <!-- -->2020-06-02 12:41:43 +08:00</span><span>Date modified: <!-- -->2021-11-07 00:39:27 +08:00</span></section><nav class="toc"><ol class="toc-level toc-level-1"><li class="toc-item toc-item-h1"><a href="/wiki/literature.structure-and-interpretations-of-computer-programs#elements-of-programming" class="toc-link toc-link-h1">Elements of programming</a></li><li class="toc-item toc-item-h1"><a href="/wiki/literature.structure-and-interpretations-of-computer-programs#higher-order-functions" class="toc-link toc-link-h1">Higher-order functions</a></li><li class="toc-item toc-item-h1"><a href="/wiki/literature.structure-and-interpretations-of-computer-programs#data-abstractions" class="toc-link toc-link-h1">Data abstractions</a></li></ol></nav><p>This is just my personal notes on <a href="http://mitpress.mit.edu/sicp">Structure and interpretation of computer programs</a>.
|
|
I also studied with the <a href="https://archive.org/details/ucberkeley-webcast-PL3E89002AA9B9879E?sort=titleSorter">Brian Harvey's SICP lectures</a> because I am a scrub. ;p
|
|
</p><h1 id="elements-of-programming">Elements of programming</h1><p>Programming often requires the following:
|
|
</p><ul><li><p>Simple expressions with atomic value.
|
|
</p></li><li><p>A way to combine procedures into complex expressions.
|
|
</p></li><li><p>A way to define procedures for abstractions of higher-level functions.
|
|
</p></li></ul><p>In order to do programming, we must have a programming language.
|
|
A programming language often requires the following to have an effective way of expressing code:
|
|
</p><ul><li><p>Expressions which varies from primitive expressions (e.g., <code class="inline-code">42</code>, <code class="inline-code">1.683</code>, <code class="inline-code">53819492184</code>) to compound expressions (e.g., <code class="inline-code">(+ 53 20)</code>, <code class="inline-code">(- 464 254)</code>).
|
|
</p></li><li><p>An environment of objects which you can refer by name either with values (e.g., <code class="inline-code">(define x 10)</code>, <code class="inline-code">(define pi 3.14)</code>, <code class="inline-code">(define e 2.71828)</code>) or procedures (e.g., <code class="inline-code">(define (square x) (* x x))</code>, <code class="inline-code">(define (my-formula height weight length) (* 23 (/ height weight) (+ 3500 length)))</code>).
|
|
</p></li><li><p>An evaluation model for expressions since certain procedures can have different output from the order of operations.
|
|
</p></li></ul><p>A programming language lets us abstract procedures as a black box.
|
|
Here's an example of implementing the square root given a number.
|
|
</p><pre class="src-block"><code class="language-racket">(define (square x) (* x x))
|
|
(define (improve guess x)
|
|
(/ (+ guess (/ x guess)) 2))
|
|
|
|
(define (good-enough? guess x)
|
|
(< (abs (- (square guess) x)) 0.001))
|
|
|
|
(define (sqrt-iter guess x)
|
|
(if (good-enough? guess x)
|
|
guess
|
|
(sqrt-iter (improve guess x) x)))
|
|
|
|
(define (sqrt x)
|
|
(sqrt-iter 1.0 x))
|
|
|
|
(sqrt 4)
|
|
(sqrt 100)
|
|
(sqrt 45.65)
|
|
</code></pre><pre class="fixed-width">2.0000000929222947
|
|
10.000000000139897
|
|
6.756478442187127</pre><p>
|
|
In order to do the square root extraction in our implementation, we define multiple procedures with each solving a part of the procedure: one procedure for indicating whether the guess is good enough, one for creating an improved guess for the next iteration, and one for actually doing the square root extraction.
|
|
</p><p>In general cases, we don't implement things as one thing as it will result in a messy state of code.
|
|
Instead, we modularize those functions.
|
|
We classify these procedures as a <strong>procedural abstraction</strong>.
|
|
</p><h1 id="higher-order-functions">Higher-order functions</h1><p>Functions and data are often separated similarly to verbs and subjects.
|
|
We tend to think of them as different things relying on each other to do things: functions need data to manipulate while data are raw information to be arranged by a function.
|
|
However, the reality is that there is a blurry line to how distinct both of them are.
|
|
Functions can be treated similarly to data and vice versa.
|
|
</p><p>The lesson of higher-order functions proves this.
|
|
It is one of the foundations of functional programming.
|
|
In order to learn about it, you need to know the key: <strong>generalizing patterns</strong>.
|
|
</p><p>For example, say we have different functions for knowing the area of a shape.
|
|
</p><pre class="src-block"><code class="language-racket">(define pi 3.14)
|
|
|
|
(define (square-area r) (* r r))
|
|
(define (circle-area r) (* pi r r))
|
|
(define (hexagon-area r) (* (sqrt 3) 1.5 r r))
|
|
</code></pre><p>This could pass as a decent code if each area function is distinct from each other.
|
|
However, all of the given area functions involves squaring the given parameter (<code class="inline-code">r</code>).
|
|
We can separate that step in a function like the following.
|
|
</p><pre class="src-block"><code class="language-racket">(define pi 3.14)
|
|
(define (area shape r) (* shape r r))
|
|
|
|
(define square 1)
|
|
(define circle pi)
|
|
(define hexagon (* (sqrt 3) 1.5))
|
|
|
|
;; We can then use it like this.
|
|
;; Calcuating the area of square with a length of 4.
|
|
(area square 4)
|
|
|
|
;; Calculating the area of a circle with a radius of 10.
|
|
(area circle 10)
|
|
|
|
;; Calculating the area of a hexagon with length of 9.
|
|
(area hexagon 9)
|
|
</code></pre><h1 id="data-abstractions">Data abstractions</h1><p>The idea behind data abstractions is to make procedures in a way that doesn't make assumptions to our data.
|
|
To make this possible, we have to separate the implementation of our data and the procedures that make use of that data.
|
|
</p><p>One powerful way to start implementing abstract data is through wishful thinking — that is, assuming we already we have the components fully defined.
|
|
</p><section><h2>Backlinks</h2><ul><li><a href="/wiki/challenges.structure-and-interpretation-of-computer-programs">Solutions: Structure and interpretation of computer programs</a></li></ul></section></main></div><script id="__NEXT_DATA__" type="application/json">{"props":{"pageProps":{"metadata":{"date":"\"2020-06-02 12:41:43 +08:00\"","date_modified":"\"2021-11-07 00:39:27 +08:00\"","language":"en","source":""},"title":"Structure and interpretation of computer programs","hast":{"type":"root","children":[{"type":"element","tagName":"nav","properties":{"className":"toc"},"children":[{"type":"element","tagName":"ol","properties":{"className":"toc-level toc-level-1"},"children":[{"type":"element","tagName":"li","data":{"hookArgs":[{"type":"element","tagName":"h1","properties":{"id":"elements-of-programming"},"children":[{"type":"text","value":"Elements of programming"}]}]},"properties":{"className":"toc-item toc-item-h1"},"children":[{"type":"element","tagName":"a","properties":{"className":"toc-link toc-link-h1","href":"/literature.structure-and-interpretations-of-computer-programs#elements-of-programming"},"children":[{"type":"text","value":"Elements of programming"}]}]},{"type":"element","tagName":"li","data":{"hookArgs":[{"type":"element","tagName":"h1","properties":{"id":"higher-order-functions"},"children":[{"type":"text","value":"Higher-order functions"}]}]},"properties":{"className":"toc-item toc-item-h1"},"children":[{"type":"element","tagName":"a","properties":{"className":"toc-link toc-link-h1","href":"/literature.structure-and-interpretations-of-computer-programs#higher-order-functions"},"children":[{"type":"text","value":"Higher-order functions"}]}]},{"type":"element","tagName":"li","data":{"hookArgs":[{"type":"element","tagName":"h1","properties":{"id":"data-abstractions"},"children":[{"type":"text","value":"Data abstractions"}]}]},"properties":{"className":"toc-item toc-item-h1"},"children":[{"type":"element","tagName":"a","properties":{"className":"toc-link toc-link-h1","href":"/literature.structure-and-interpretations-of-computer-programs#data-abstractions"},"children":[{"type":"text","value":"Data abstractions"}]}]}]}]},{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"This is just my personal notes on "},{"type":"element","tagName":"a","properties":{"href":"http://mitpress.mit.edu/sicp"},"children":[{"type":"text","value":"Structure and interpretation of computer programs"}]},{"type":"text","value":".\nI also studied with the "},{"type":"element","tagName":"a","properties":{"href":"https://archive.org/details/ucberkeley-webcast-PL3E89002AA9B9879E?sort=titleSorter"},"children":[{"type":"text","value":"Brian Harvey's SICP lectures"}]},{"type":"text","value":" because I am a scrub. ;p\n"}]},{"type":"element","tagName":"h1","properties":{"id":"elements-of-programming"},"children":[{"type":"text","value":"Elements of programming"}]},{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"Programming often requires the following:\n"}]},{"type":"element","tagName":"ul","properties":{},"children":[{"type":"element","tagName":"li","properties":{},"children":[{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"Simple expressions with atomic value.\n"}]}]},{"type":"element","tagName":"li","properties":{},"children":[{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"A way to combine procedures into complex expressions.\n"}]}]},{"type":"element","tagName":"li","properties":{},"children":[{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"A way to define procedures for abstractions of higher-level functions.\n"}]}]}]},{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"In order to do programming, we must have a programming language.\nA programming language often requires the following to have an effective way of expressing code:\n"}]},{"type":"element","tagName":"ul","properties":{},"children":[{"type":"element","tagName":"li","properties":{},"children":[{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"Expressions which varies from primitive expressions (e.g., "},{"type":"element","tagName":"code","properties":{"className":["inline-code"]},"children":[{"type":"text","value":"42"}]},{"type":"text","value":", "},{"type":"element","tagName":"code","properties":{"className":["inline-code"]},"children":[{"type":"text","value":"1.683"}]},{"type":"text","value":", "},{"type":"element","tagName":"code","properties":{"className":["inline-code"]},"children":[{"type":"text","value":"53819492184"}]},{"type":"text","value":") to compound expressions (e.g., "},{"type":"element","tagName":"code","properties":{"className":["inline-code"]},"children":[{"type":"text","value":"(+ 53 20)"}]},{"type":"text","value":", "},{"type":"element","tagName":"code","properties":{"className":["inline-code"]},"children":[{"type":"text","value":"(- 464 254)"}]},{"type":"text","value":").\n"}]}]},{"type":"element","tagName":"li","properties":{},"children":[{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"An environment of objects which you can refer by name either with values (e.g., "},{"type":"element","tagName":"code","properties":{"className":["inline-code"]},"children":[{"type":"text","value":"(define x 10)"}]},{"type":"text","value":", "},{"type":"element","tagName":"code","properties":{"className":["inline-code"]},"children":[{"type":"text","value":"(define pi 3.14)"}]},{"type":"text","value":", "},{"type":"element","tagName":"code","properties":{"className":["inline-code"]},"children":[{"type":"text","value":"(define e 2.71828)"}]},{"type":"text","value":") or procedures (e.g., "},{"type":"element","tagName":"code","properties":{"className":["inline-code"]},"children":[{"type":"text","value":"(define (square x) (* x x))"}]},{"type":"text","value":", "},{"type":"element","tagName":"code","properties":{"className":["inline-code"]},"children":[{"type":"text","value":"(define (my-formula height weight length) (* 23 (/ height weight) (+ 3500 length)))"}]},{"type":"text","value":").\n"}]}]},{"type":"element","tagName":"li","properties":{},"children":[{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"An evaluation model for expressions since certain procedures can have different output from the order of operations.\n"}]}]}]},{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"A programming language lets us abstract procedures as a black box.\nHere's an example of implementing the square root given a number.\n"}]},{"type":"element","tagName":"pre","properties":{"className":["src-block"]},"children":[{"type":"element","tagName":"code","properties":{"className":["language-racket"]},"children":[{"type":"text","value":"(define (square x) (* x x))\n(define (improve guess x)\n (/ (+ guess (/ x guess)) 2))\n\n(define (good-enough? guess x)\n (\u003c (abs (- (square guess) x)) 0.001))\n\n(define (sqrt-iter guess x)\n (if (good-enough? guess x)\n guess\n (sqrt-iter (improve guess x) x)))\n\n(define (sqrt x)\n (sqrt-iter 1.0 x))\n\n(sqrt 4)\n(sqrt 100)\n(sqrt 45.65)\n"}]}]},{"type":"element","tagName":"pre","properties":{"className":["fixed-width"]},"children":[{"type":"text","value":"2.0000000929222947\n10.000000000139897\n6.756478442187127"}]},{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"\nIn order to do the square root extraction in our implementation, we define multiple procedures with each solving a part of the procedure: one procedure for indicating whether the guess is good enough, one for creating an improved guess for the next iteration, and one for actually doing the square root extraction.\n"}]},{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"In general cases, we don't implement things as one thing as it will result in a messy state of code.\nInstead, we modularize those functions.\nWe classify these procedures as a "},{"type":"element","tagName":"strong","properties":{},"children":[{"type":"text","value":"procedural abstraction"}]},{"type":"text","value":".\n"}]},{"type":"element","tagName":"h1","properties":{"id":"higher-order-functions"},"children":[{"type":"text","value":"Higher-order functions"}]},{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"Functions and data are often separated similarly to verbs and subjects.\nWe tend to think of them as different things relying on each other to do things: functions need data to manipulate while data are raw information to be arranged by a function.\nHowever, the reality is that there is a blurry line to how distinct both of them are.\nFunctions can be treated similarly to data and vice versa.\n"}]},{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"The lesson of higher-order functions proves this.\nIt is one of the foundations of functional programming.\nIn order to learn about it, you need to know the key: "},{"type":"element","tagName":"strong","properties":{},"children":[{"type":"text","value":"generalizing patterns"}]},{"type":"text","value":".\n"}]},{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"For example, say we have different functions for knowing the area of a shape.\n"}]},{"type":"element","tagName":"pre","properties":{"className":["src-block"]},"children":[{"type":"element","tagName":"code","properties":{"className":["language-racket"]},"children":[{"type":"text","value":"(define pi 3.14)\n\n(define (square-area r) (* r r))\n(define (circle-area r) (* pi r r))\n(define (hexagon-area r) (* (sqrt 3) 1.5 r r))\n"}]}]},{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"This could pass as a decent code if each area function is distinct from each other.\nHowever, all of the given area functions involves squaring the given parameter ("},{"type":"element","tagName":"code","properties":{"className":["inline-code"]},"children":[{"type":"text","value":"r"}]},{"type":"text","value":").\nWe can separate that step in a function like the following.\n"}]},{"type":"element","tagName":"pre","properties":{"className":["src-block"]},"children":[{"type":"element","tagName":"code","properties":{"className":["language-racket"]},"children":[{"type":"text","value":"(define pi 3.14)\n(define (area shape r) (* shape r r))\n\n(define square 1)\n(define circle pi)\n(define hexagon (* (sqrt 3) 1.5))\n\n;; We can then use it like this.\n;; Calcuating the area of square with a length of 4.\n(area square 4)\n\n;; Calculating the area of a circle with a radius of 10.\n(area circle 10)\n\n;; Calculating the area of a hexagon with length of 9.\n(area hexagon 9)\n"}]}]},{"type":"element","tagName":"h1","properties":{"id":"data-abstractions"},"children":[{"type":"text","value":"Data abstractions"}]},{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"The idea behind data abstractions is to make procedures in a way that doesn't make assumptions to our data.\nTo make this possible, we have to separate the implementation of our data and the procedures that make use of that data.\n"}]},{"type":"element","tagName":"p","properties":{},"children":[{"type":"text","value":"One powerful way to start implementing abstract data is through wishful thinking — that is, assuming we already we have the components fully defined.\n"}]}]},"backlinks":[{"path":"/challenges.structure-and-interpretation-of-computer-programs","title":"Solutions: Structure and interpretation of computer programs"}]},"__N_SSG":true},"page":"/[[...slug]]","query":{"slug":["literature.structure-and-interpretations-of-computer-programs"]},"buildId":"Ie9t5zutrXP6Of75Cb5xF","assetPrefix":"/wiki","nextExport":false,"isFallback":false,"gsp":true}</script><script nomodule="" src="/wiki/_next/static/chunks/polyfills-99d808df29361cf7ffb1.js"></script><script src="/wiki/_next/static/chunks/main-ae4733327bd95c4ac325.js" async=""></script><script src="/wiki/_next/static/chunks/webpack-50bee04d1dc61f8adf5b.js" async=""></script><script src="/wiki/_next/static/chunks/framework.9d524150d48315f49e80.js" async=""></script><script src="/wiki/_next/static/chunks/commons.0e1c3f9aa780c2dfe9f0.js" async=""></script><script src="/wiki/_next/static/chunks/pages/_app-8e3d0c58a60ec788aa69.js" async=""></script><script src="/wiki/_next/static/chunks/940643274e605e7596ecea1f2ff8d83317a3fb76.4841a16762f602a59f00.js" async=""></script><script src="/wiki/_next/static/chunks/pages/%5B%5B...slug%5D%5D-1aa198f87ede1cd0e1dc.js" async=""></script><script src="/wiki/_next/static/Ie9t5zutrXP6Of75Cb5xF/_buildManifest.js" async=""></script><script src="/wiki/_next/static/Ie9t5zutrXP6Of75Cb5xF/_ssgManifest.js" async=""></script></body></html> |