How to Design Programs : An Introduction to Computing and Programming

프로그래밍 기초라고 하면 흔히 프로그래밍 언어를 배우는 것으로 생각합니다. 프로그래밍이란 게 컴퓨터로 무언가를 처리하기 위한 것이고 그렇게 하려면 언어를 알아야 하므로 어찌 보면 당연한 것일 겁니다. 하지만 프로그래밍이란 게 언어를 안다고 끝나는 건 아닙니다. 더욱 중요한 것은 프로그래밍 언어에 관계 없이 문제를 어떻게 해결해야 할지, 프로그램은 어떻게 만들어야 좋은 것인지 하는 것이죠. 많은 시간을 프로그래밍 언어와 API, 프레임워크 등의 사용법에 집중할 뿐 이런 것에는 그리 신경 쓰지 않다 보니 결국 동작은 하지만 매우 좋지 못한 구조와 비효율적인 프로그램이 탄생하는 것이죠.

이른바 프로그래밍에 대한 비전서로 통하는 책이 두 권 있습니다. 하나는 SICP(Structure and Interpretation of Computer Programs)이고 다른 하나가 바로 HTDP(How to Design Programs)입니다. 둘 모두 학부 수준의 프로그래밍 기초 교재입니다만 실제 SICP는 다루는 문제 범위가 매우 넓고 종종 문제 난이도가 높아 내용을 잘 이해하고 있는 누군가로부터 배우지 않는다면 제대로 이해하기가 매우 어렵다고 합니다. 이에 반해 HTDP는 이런 단점을 해결하기 위해 만든 것으로 내용이 대체로 평이해 이해하기 쉽다고 합니다.

How To Design Programs

개인적으로도 프로그래밍에 대해 제대로 배운 적은 없었기에 과거에 HTDP를 읽어보려 했다 흐지부지 접었으나 최근 다시 시도하고 있습니다. 앞으로도 틈틈이 이 글에 주요 내용을 계속 정리하며 문제 풀이도 올릴 생각입니다. 코드에 주석은 가능한 영어로 쓰고 있지만 잘 못하므로 분명 잘못된 내용이 많을 겁니다. 대충 의미만 통하면 그러려니 하시길. 코드는 아래에서 볼 수 있습니다.

주요 내용 요약

2.5 Designing Programs

;; 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

Figure 3: The design recipe: A complete example

Phase Goal Activity
Contract Purpose and Header to name the functionto specify its classes of input data and its class of output datato describe its purposeto formulate a header choose a name that fits the problem

  • study the problem for clues on how many unknown ‘givens’ the function consumes
  • pick one variable per input; if possible, use names that are mentioned for the ‘givens’ in the problem statement
  • describe what the function should produce using the chosen variables names
  • formulate the contract and header
;; name : number ... --> number
;; to compute ... from x1 ...
(define (name x1 ...) ...)
Examples to characterize the input-output relationship via examples search the problem statement for examples

  • work through the examples
  • validate the results, if possible
  • make up examples
Body to define the function formulate how the function computes its results

  • develop a Scheme expression that uses Scheme’s primitive operations, other functions, and the variables
  • translate the mathematical expressions in the problem statement, when available
Test to discover mistakes (‘typos’ and logic) apply the function to the inputs of the examples

  • check that the outputs are as predicted

Figure 4: The design recipe at a glance

3.1 Composing Functions

Guideline on Auxiliary Functions

Formulate auxiliary function definitions for every dependency between quantities mentioned in the problem statement or discovered with example calculations.

3.2 Variable Definitions

Guideline on Variable Definitions

Give names to frequently used constants and use the names instead of the constants in programs.

4.4 Designing Conditional Funcitons

Phase Goal Activity
Data Analysis to determine the distinct situations a function deals with inspect the problem statement for distinct situations

  • enumerate all possible situations
Examples to provide an example per situation choose at least one example per situation

  • for intervals or enumerations, the examples must include borderline cases
Body (1) Conditions to formulate a conditional expression write down the skeleton of a condexpression, with one clause per situation

  • formulate one condition per situation, using the parameters
  • ensure that the conditions distinguish the examples appropriately
Body (2) Answers to formulate the answers for the cond-clauses deal with each cond-line separately

  • assume the condition holds and develop a Scheme expression that computes the appropriate answer for this case

Figure 6: Designing the body of a conditional function

6.5  Designing Functions for Compound Data

;; Data Analysis & Definitions:
(define-struct student (last first teacher))
;; A student is a structure: (make-student l f t) where f, l, and t are symbols.

;; Contract: subst-teacher : student symbol  ->  student

;; Purpose: to create a student structure with a new
;; teacher name if the teacher's name matches 'Fritz

;; Examples:
;; (subst-teacher (make-student 'Find 'Matthew 'Fritz) 'Elise)
;; =
;; (make-student 'Find 'Matthew 'Elise)
;; (subst-teacher (make-student 'Find 'Matthew 'Amanda) 'Elise)
;; =
;; (make-student 'Find 'Matthew 'Amanda)

;; Template:
;; (define (process-student a-student a-teacher)
;; ... (student-last a-student) ...
;; ... (student-first a-student) ...
;; ... (student-teacher a-student) ...)

;; Definition:
(define (subst-teacher a-student a-teacher)
  (cond
    [(symbol=? (student-teacher a-student) 'Fritz)
     (make-student (student-last a-student)
                   (student-first a-student)
		   a-teacher)]
    [else a-student]))

;; Tests:
(subst-teacher (make-student 'Find 'Matthew 'Fritz) 'Elise)
;; expected value:
(make-student 'Find 'Matthew 'Elise)

(subst-teacher (make-student 'Find 'Matthew 'Amanda) 'Elise)
;; expected value:
(make-student 'Find 'Matthew 'Amanda)

Figure 11:  The design recipe for compound data: A complete example

Phase Goal Activity
Data Analysis and Design to formulate a data definition determine how many pieces of data describe the ‘interesting’ aspects of the objects mentioned in the problem statement

  • add a structure definition and a data definition (for each class of problem object)
Contract Purpose and Header to name the functionto specify its classes of input data and its class of output datato describe its purposeto formulate a header name the function, the classes of input data, the class of output data, and specify its purpose:


;; name : in1 in2 ...--> out
 ;; to compute ... from x1 ...
 (define (name x1 x2 ...) ...)

Examples to characterize the input-output relationship via examples search the problem statement for examples

  • work through the examples
  • validate the results, if possible
  • make up examples
Template to formulate an outline for those parameters that stand for compound values, annotate the body with selector expressions

  • if the function is conditional, annotate all appropriate branches
Body to define the function develop a Scheme expression that uses Scheme’s primitive operations, other functions, selector expressions, and the variables
Test to discover mistakes (‘typos’ and logic) apply the function to the inputs of the examples

  • check that the outputs are as predicted

Figure 12:  Designing a function for compound data (Refines the recipe in figure 4)

7.2  Designing Functions for Mixed Data

;; Data Definition:
(define-struct circle (center radius))
(define-struct square (nw length))
;; A shape is either
;; 1. a structure: (make-circle p s)
;;    where p is a posn, s a number;
;; 2. a structure: (make-square p s)
;;    where p is a posn, s a number.

;; Contract, Purpose, Header:
;; perimeter : shape  ->  number
;; to compute the perimeter of a-shape

;; Examples: see tests

;; Template:
;; (define (f a-shape)
;;   (cond
;;     [(square? a-shape)
;;     ... (square-nw a-shape) ... (square-length a-shape) ...]
;;     [(circle? a-shape)
;;     ... (circle-center a-shape) ... (circle-radius a-shape) ...]))

;; Definition:
(define (perimeter a-shape)
  (cond
    [(circle? a-shape)
     (* (* 2 (circle-radius a-shape)) pi)]
    [(square? a-shape)
     (* (square-length a-shape) 4)]))

;; Tests: (same as examples)
(= (perimeter (make-square ... 3)) 12)
(= (perimeter (make-circle ... 1)) (* 2 pi))

Figure 17: The design recipe for mixed data: A complete example

Phase Goal Activity
Data Analysis and Design to formulate a data definition determine how many distinct classes of ‘objects’ make up the classes of problem data

  • enumerate the alternatives in a data definition
  • formulate a data definition for each alternative, if it is a form of compound data
Contract Purpose and Header to name the functionto specify its classes of input data and its class of output datato describe its purposeto formulate a header name the function, the classes of input data, the class of output data, and specify its purpose:
;; name : in1 in2 ...--> out
;; to compute ... from x1 ...
(define (name x1 x2 ...) ...)
Examples to characterize the input-output relationship via examples create examples of the input-output relationship

  • make sure there is at least one example per subclass
Template to formulate an outline introduce a cond-expression with one clause per subclass

  • formulate a condition for each case, using built-in and predefined predicates
Body to define the function develop a Scheme expression for each cond-line (an answer), assuming that the condition holds
Test to discover mistakes (‘typos’ and logic) apply the function to the inputs of the examples

  • check that the outputs are as predicted

Figure 18: Designing a function for mixed data (Refine the recipes in figures 4 and 12)

Notes:
1. 매우 볼품 없는 코드를 보일 생각을 하니 벌써부터 부끄럽습니다. 이래서 미리미리 깔끔한 코드 만드는 법을 공부해 뒀어야 하는 건데 말이죠.
매우 볼품 없는 코드를 보일 생각을 하니 벌써부터 부끄럽습니다. 이래서 미리미리 깔끔한 코드 만드는 법을 공부해 뒀어야 하는 건데 말이죠.