How to Design Programs : An Introduction to Computing and Programming

by Surpreem · Published May 29, 2012 · Updated December 14, 2016

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

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

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

HTDP 문제 풀이: https://bitbucket.org/Surpreem/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

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

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

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

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

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

;; 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. 매우 볼품 없는 코드를 보일 생각을 하니 벌써부터 부끄럽습니다. 이래서 미리미리 깔끔한 코드 만드는 법을 공부해 뒀어야 하는 건데 말이죠.

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

How to Design Programs : An Introduction to Computing and Programming

주요 내용 요약

2.5 Designing Programs

3.1 Composing Functions

3.2 Variable Definitions

4.4 Designing Conditional Funcitons

6.5 Designing Functions for Compound Data

7.2 Designing Functions for Mixed Data

You may also like...

Archives

Categories

이메일로 받아 보세요.

How to Design Programs : An Introduction to Computing and Programming

주요 내용 요약

2.5 Designing Programs

3.1 Composing Functions

3.2 Variable Definitions

4.4 Designing Conditional Funcitons

6.5 Designing Functions for Compound Data

7.2 Designing Functions for Mixed Data

관련글이 없어요.

You may also like...

Boost.Asio C++ Network Programming 2판

Think Python: How to Think Like a Computer Scientist 2판

Archives

Categories

Tags

이메일로 받아 보세요.