Ryan's Manuals

Scheme

I am hacker man! I read HTDP!


Contents



Installation on Windows

I know, not UNIX, but it’s what I have in front of me. Let’s install Racket and iracket for use with Jupyter.

  1. Use the Windows installer
  2. Add C:\Program Files\Racket to the system path
  3. Run raco pkg install iracket

Learning Material

I’ve got a physical copy of HTDP 2001. A copy of this book is accessible online along with the answer key.

Notes on MIT’s “How To Design Programs” (HTDP) 1e

Chapter summaries and important notes from my own learning.

I Processing Simple Forms of Data

1 Students, Teachers, and Computers

Some programs are as small as essays. Others are like sets of encyclopedias. Writing good essays and books requires careful planning, and writing good programs does, too. Small or large, a good program cannot be created by tinkering around. It must be carefully designed.

2 Numbers, Expressions, Simple Programs

Scheme uses parentheses ( ) or round brackets to organize programs. A set of parentheses encloses an expression.

Parenthesized expressions.

(operator input... )

Expressions can take in a number of variables:

(define (area-of-disk r)
  (* 3.14 r r))

(define (area-of-ring outer-r inner-r)
  (- (area-of-disk outer-r) (area-of-disk inner-r)))

If it’s not in parentheses it’s an atom.

; Exercise 2.2.1.   Define the program Fahrenheit->Celsius,
; which consumes a temperature measured in Fahrenheit and
; produces the Celsius equivalent. Use a chemistry or
; physics book to look up the conversion formula.

(define (fahrenheit->celsius x)
  (* (- x 32) (/ 5 9)))

(convert-gui fahrenheit->celsius)

Scheme allows you to represent fractions directly as well:

(define (fahrenheit->celsius x)
  (* (- x 32) 5/9 ))

…though I’m not a huge fan of that.

Inexact numbers are represented with an #i in front.

Here’s a word problem and my solution:

Company XYZ & Co. pays all its employees $12 per hour. A typical employee works between 20 and 65 hours per week. Develop a program that determines the wage of an employee from the number of hours of work.

(define (wage h)
  (* 12 h))

(define (tax gross-pay)
  (* 0.15 gross-pay))

(define (subtract-taxes net-pay)
  (- net-pay (tax net-pay)))

(define (net-pay h)
  (subtract-taxes (wage h)))

My solution is slightly more efficient than the solution as it does not recompute the gross pay by including the subtract-taxes function.

Designing programs is something that must be done intentionally and with care. SICP provides a Design Recipe which can be followed to yield reliably useful programs.

We need to determine what’s relevant in the problem statement and what we can ignore. We need to understand what the program consumes, what it produces, and how it relates inputs to outputs. We must know, or find out, whether Scheme provides certain basic operations for the data that our program is to process. If not, we might have to develop auxiliary programs that implement these operations. Finally, once we have a program, we must check whether it actually performs the intended computation.

Here is Figure 3, the example recipe:

;; Contract: area-of-ring : number number  ->  number

;; Purpose: to compute the area of a ring whose radius is
;; outer and whose hole has a radius of inner

;; Example: (area-of-ring 5 3) should produce 50.24

;; Definition: [refines the header]
(define (area-of-ring outer inner)
  (- (area-of-disk outer)
     (area-of-disk inner)))

;; Tests:
(area-of-ring 5 3)
;; expected value
50.24

A summary of these phases is provided in Figure 4 in this section of the textbook, but I’ll summarize here quickly:

(Funny, Elixir has real good support for inline tests with the doctest feature. Makes me miss Elixir.)

3 Programs are Function Plus Variable Definitions

4 Conditional Expressions and Functions

5 Symbolic Information

6 Compound Data, Part 1: Structures

7 The Varieties of Data

8 Intermezzo 1: Syntax and Semantics

II Processing Arbitrarily Large Data

9 Compound Data, Part 2: Lists

9.1 Lists 9.2 Data Definitions for Lists of Arbitrary Length 9.3 Processing Lists of Arbitrary Length 9.4 Designing Functions for Self-Referential Data Definitions 9.5 More on Processing Simple Lists

10 More on Processing Lists

11 Natural Numbers

12 Composing Functions, Revisited Again

13 Intermezzo 2: List Abbreviations

III More on Processing Arbitrarily Large Data

14 More Self-referential Data Definitions

15 Mutually Referential Data Definitions

16 Development through Iterative Refinement

17 Processing Two Complex Pieces of Data

18 Intermezzo 3: Local Definitions and Lexical Scope

IV Abstracting Designs

19 Similarities in Definitions

20 Functions are Values

21 Designing Abstractions from Examples

22 Designing Abstractions with First-Class Functions

23 Mathematical Examples

24 Intermezzo 4: Defining Functions on the Fly

V Generative Recursion

25 A New Form of Recursion

26 Designing Algorithms

27 Variations on a Theme

28 Algorithms that Backtrack

29 Intermezzo 5: The Cost of Computing and Vectors

VI Accumulating Knowledge

30 The Loss of Knowledge

31 Designing Accumulator-Style Functions

32 More Uses of Accumulation

33 Intermezzo 6: The Nature of Inexact Numbers

VII Changing the State of Variables

34 Memory for Functions

35 Assignment to Variables

36 Designing Functions with Memory

37 Examples of Memory Usage

38 Intermezzo 7: The Final Syntax and Semantics

VIII Changing Compound Values

39 Encapsulation

40 Mutable Structures

41 Designing Functions that Change Structures

42 Equality

43 Changing Structures, Vectors, and Objects

FIN.



Site Directory



Page Information

Title: Scheme
Word Count: 1592 words
Reading Time: 8 minutes
Permalink:
https://manuals.ryanfleck.ca/scheme/