프로그래밍언어론 2023-04-06 수업정리

Flow

• Scheme(2)
• Lab - Tail Recursive Factorial

Scheme(2)

---

3.30 Scheme에서 이어짐

• Scheme은 LISP를 모태로 하는 함수형 프로그래밍 언어이다.
• LISP과 마찬가지로 Eval - Apply model을 따른다.

Eval - Apply

• Scheme은 리스트로 함수 적용을 나타낸다.
• 수식은 상수이거나 함수 적용 형태, 둘 중 하나이다.
• 함수와 인수를 모두 계산하고(Eval), 함수를 적용한다(Apply).
• ' 기호를 사용하여 Eval의 예외 처리가 가능하다.(cont.)

Defining Values

• 나중에 사용할 값을 정의하기 위해 define문법을 사용한다.
• define문법은 타 언어의 assignment와 유사하게 동작한다. 하지만 이는 틀린 표현이다.
  • Scheme에서 define은 Storage에 값을 저장하는 방식으로 동작하는 것이 아닌, binding을 만드는 방식으로 동작한다.
  • binding을 통해 name과 value간의 1:1대응이 가능하다.

Input and Output

• 입력 함수 사용 예시

(define num(read)) // 입력 받은 후 출력

• 출력 함수 사용 예시
  • write는 있는 그대로 출력한다.
  • display는 개행문자 등 표준 출력을 반영하여 출력한다.

(write (+ num 1)) // num+1 출력 
(display (+ num 1)) // num+1 출력
(wirte "Hello \n World!") // "Hello \n World!" 출력
(display "Hello \n World!") // 표준 출력으로 따음표 없이 Hello -> 개행 -> World 출력

List

• cons(construct) 를 이용하여 List의 생성이 가능하다.
  • 첫 번째 인자로 받은 원소를 두 번째 인자로 받은 리스트의 앞에 붙인 리스트를 반환)

(cons 1 '(2 3)) // (1 2 3)

• list를 이용하여 cons를 사용하지 않고 한번에 리스트 생성이 가능하다.

(list 1 2 3) // (1 2 3)

• car를 사용하여 리스트의 맨 앞 원소를 반환할 수 있다.

(car (list 1 2 3)) // 1

• cdr을 이용하여 리스트의 맨 앞을 제외한 나머지 리스트를 반환할 수 있다. 이때 리스트에는 1개 이상의 원소가 있어야 한다.(null에서는 맨 앞을 제외할 수 없으니까)

(cdr '(a b c)) // (b c)

• car, cdr 명령어의 다소 특이한 이름은 초기 IBM 704의 레지스터 이름에서 유래했다.
• List는 빈 리스트와 원소가 있는 리스트의 두 가지 형태로 나눌 수 있다.
• pair는 리스트를 구현하는 기본적인 방법이다.
  • (x y)는 (x.y)로 표현한다.
  • (a b c)는 (a .(b.(c.())))로 구현된다.
  • 위의 표기를 트리 구조로 나타내면 아래와 같다.
• pair? 술어를 사용하여 어떤 S-expression이 pair인지 아닌지 검사 가능하다.
  • 리스트 중 원소가 하나라도 있는 경우 pair? 의 결과가 #t 이다.

(pair? (list 1 2 3)) // #t

• 어떤 리스트가 빈 리스트라면 null이다.
• null? 술어를 사용하여 null인지 아닌지 판단 가능하다.

(null? '()) // #t

• List가 아니면서 null도 아니고 pair도 아니라면 atom이다. 아래는 atom인지 아닌지 판별하는 함수이다.

(define atom?
  (lambda (x)
	  (and (not (pair? x)) (not (null? x)))))

• 실행하면 아래와 같다.

(atom? 3) // #t
(atom? '()) // #f

quote

• quote 함수는 인자로 받은 값을 계산하지 말고 심볼로 보라는 뜻이다.
  • eval-apply의 예외 처리이다.
  • 앞서 설명한 '와 같은 의미이다.
• 상수 값에 대해서는 quote가 의미 없다.
• 아래는 quote, ' 의 사용 예시이다.
  • 가장 마지막 예시 결과는 quote에 의해 '1이 '1이라는 심볼 그 자체로 출력된 것이다.

(1 2 3) // error
(quote (1 2 3)) // (1 2 3)
(atom? (quote (1 2 3))) // #f
(atom? (quote ())) // #f
(atom? '(1 2 3)) // #f
(atom? 'Scheme) // #t
(quote 1) // 1
'1 // 1
(quote '1) // '1

Predicates

• 술어(predictate)란 참/거짓을 반환하는 함수이다.(boolean functions)
• Scheme에서 술어는 물음표로 끝내는 것이 관례이다.
• 앞서 살펴본 술어 이외에 대표적인 술어는 아래와 같다.
  • number? : 인수가 수인지 검사한다.
    • 수 : 1, 2, 3, 10, 100, 123 ...
    • 숫자 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
  • eq? : 인수로 주어진 두 개의 atom이 같은지 검사(list도 되긴 한다.)
  • complex? : 복소수인지 검사
  • real? : 실수인지 검사
  • rational? : 유리수인지 검사
  • integer? : 정수인지 검사
  • zero? : 0인지 검사
  • exact? : 주어진 인수가 정확한 숫자인지 검사(정수, 유리수)
  • inexact? : 주어진 인수가 부동 소수점 수인지 판단.
  • odd?, even? : 주어진 홀수 또는 짝수인지 판단.

(exact? 3.0) // #f
(exact? 1/2) // #t

• Scheme에서는 위의 술어들의 인자들에 대해서 C언어 등에서와 같이 그 자체만으로 형이 결정되는 것이 아닌 수의 포함관계를 모두 반영한다는 특징이 있다.

(integer? 1.0) // #t

Comparison Operators and Others

• 숫자값이 같은지 비교하는 연산자는 =하나 뿐이다.
  • !=는 (not (= a b)) 형태로 사용해야 한다.
• 그 이외의 대소 비교 연산자는 C연산자와 동일하다.
• max min등의 프로시저는 알아두면 유용하게 사용할 수 있다.

Multiple Selection Using cond

• 개별 조건을 검사하기 위해서 cond를 사용할 수 있다.
• 아래 코드는 atom?을 cond를 사용하여 다시 구현한 것이다.

(define atom?
  (lambda (x)
	  (cond
		  ((null? x) #f)
		  ((pair? x) #f)
		  (else #t))))

• 위의 구문 중 else부분은 아래와 같이 처리해도 된다.

(define atom?
  (lambda (x)
	  (cond
		  ((null? x) #f)
		  ((pair? x) #f)
		  (#t #t))))

Lab - Tail Recursive Factorial

---

Tail Recursion(꼬리 재귀)

• 재귀함수에서 재귀가 일어나는 부분에서 온전히 재귀 함수의 호출만을 반환하는 경우
• 아래와 같은 코드는 꼬리 재귀 코드가 아니다.

int fact(int n) {
	if(n == 0) return 1;
	else return n*fact(n-1);
}

• 이를 꼬리 재귀 코드로 고치면 아래와 같다.

int ifact(int n, int x = 1) {
	if(n == 0) return x;
	else return ifact(n-1, n*x);
}

Scheme을 사용한 factorial Tail recursive implementation

• 아래는 Scheme으로 구현한 tail-recursion factorial calculating function이다.

(define ifact
  (lambda (n x)
	  (if (= n 0) x
	  (ifact (- n 1) (* n x)))))

실행 결과