12. FPL (1)

Functional Programming Languages

What do we study in this chapter?

• Introduction
• Mathematical Functions
• Fundamentals of Functional Programming Languages
• The First Functional Programming Language: Lisp Introduction to Scheme
• Common Lisp
• ML
• Haskell
• F#
• Support for Functional Programming in Primarily Imperative Languages
• Comparison of Functional and Imperative Languages

Introduction

The design of imperative language

• Based on von Neumann architecture
• 이 구조에서는 프로그램과 데이터가 같은 메모리에 저장되고, 프로세서가 명령어를 순차적으로 실행함
• Primary concern: efficiency (rather than suitability for SW development)
• 초기 명령형 언어의 목적은 개발자의 편의성보다 실행 효율성을 우선시
• 하드웨어 자원을 최대한 효율적으로 쓰는 것이 중요했기 때문에, 직관적이지 않은 저수준 연산이 많고, 에러 유발 가능성도 높음
• Reliance on the underlying architecture is thought by some to be an unnecessary restriction
• Uses of variables are important
• How program's state change
• 변수 값이 바뀌면서 상태가 변하므로, 큰 프로그램에서는 상태의 흐름을 추적하는 것이 매우 어렵고 복잡해짐
• → This is a daunting task for a large program

The design of functional language

• Based on mathematical functions
• 입력 → 함수 → 출력의 관계로, 상태 변경 없이 결과를 계산하는 것이 핵심
• Solid theoretical basis (oriented more to particular programming paradigms or methodologies than to efficiency)
• 함수형 언어는 람다 계산법($\lambda$-calculus) 같은 이론적 기반이 튼튼
• 효율성보다 명확한 패러다임(모듈성, 불변성, 재귀 등)에 초점을 둠
• Closer to user (relatively less concerned with machine architecture)
• 함수형 언어는 기계의 작동 방식에 덜 의존하고, 개발자의 사고 흐름에 더 가까움
• 명령형 언어처럼 상태(state)를 추적하지 않아도 됨
• LISP: began as pure functional language (1950년대 개발)
• But, acquired some important imperative features
• 명령형 특성(루프, 변수 할당 등, (ex.) set!, loop, progn)
• Used in knowledge representation, machine learning, intelligent training systems, and the modeling of speech
• Common LISP is a dialects of LISP (다양한 LISP 방언을 통합한 표준화된 버전)
• Scheme is a small, static-scoped dialect of LISP
• ML, Haskell, OCaml, and F#: typed functional programming languages

Mathematical Functions

Mapping member of domain(정의역) set to range(치역) set

• Function definition specifies domain and range sets
• Along with mapping described by expression or table
• Functions are applied to elements of domain set to yield elements of range set
• Fundamental characteristics of mathematical functions
• Evaluation order is controlled by recursion and conditional expressions
• Rather than sequencing and iterative repetition
• 명령형 언어처럼 for, while 같은 반복문에 의존하지 않음
• No side effects and cannot depend on any external values
• 같은 입력에 대해 항상 같은 출력 → 참조 투명성(referential transparency) 보장
• No concept of stage of function
• 명령형 언어처럼 함수가 중간 상태(stage)를 갖지 않음
• 함수는 그 자체로 완결된 계산 단위이며, 이전 상태를 기억하지 않음

Function definitions are written

• Name, list of parameters in parentheses and mapping expression
• “함수 이름 + 괄호 속 매개변수 + 정의 수식”의 형태로 정의됨
• [EX] cube(x) ≡ x * x * x
• ≡: “is defined as” (cube는 함수 이름, x는 매개변수(parameter), x * x * x는 함수가 수행하는 계산을 나타냄) (수학적으로 "…로 정의된다"를 의미함)
• Parameter x can be any member of domain set but fixed during evaluation
• 평가 과정에서는 고정됨 → 특정 값으로 바인딩(binding) 됨
• [EX] cube(2.0) = 2.0 * 2.0 * 2.0 = 8
• x is bound to 2.0 during the evaluation and there are no unbound parameters
• 평가 중에는 모든 변수들이 값에 묶여 있으며, 따라서 명확하고 예측 가능한 결과를 보장함

Early theoretical work on functions separated the task of defining a function from that of naming the function → 함수를 정의할 수 있지만 꼭 이름을 붙일 필요는 없다는 개념이 생김 → nameless function

• Lambda expression specifies parameter(s) and mapping functions
• [EX] $\lambda(x) x * x * x$ ($\lambda$(변수) 식) vs cube(x) ≡ x * x * x (이름 있음)
• 잠깐 쓸 함수인데 굳이 이름 붙이기 싫을 때
• numbers = [1, 2, 3]
• doubled = map(lambda x: x * 2, numbers) # 함수 이름 없이 사용
• 다른 함수에 함수를 전달할 때
• 이름 없이 함수를 바로 정의해서 전달 가능
• 함수가 일회성일 때 매우 유용

Formal computation model using lambda expressions → lambda calculus

• “계산을 함수로만 표현하자”는 수학적 모델
• 모든 계산을 함수 정의와 적용으로 설명할 수 있는 이론적 기초 제공
• → "계산이라는 건 결국, 어떤 값을 함수에 넣고, 결과를 얻는 과정일 뿐이다."
• 모든 계산을 다음 두 가지만으로 설명하려고 함
• 함수를 정의하기
• 그 함수에 값을 적용하기
• 함수형 프로그래밍 언어의 이론적 뿌리
• Can be typed or untyped
• Untyped lambda calculus: 모든 표현을 자유롭게 사용
• Typed lambda calculus: 타입 제약 존재 (→ Haskell, ML 등 함수형 언어로 발전)

Are applied to parameter(s) by placing the parameter(s) after the expression

• [EX] $(\lambda(x) x * x * x) (2)$
• = 8
• $\lambda(x) x * x * x$는 익명 함수
• (2)는 인자 적용(application)

Functional forms

A higher-order function, or functional form

• 함수도 숫자처럼 다룰 수 있다면… 고차함수
• Takes functions as parameters
• Yields a function as its result
• Or both above
• 고차 함수는 함수형 프로그래밍의 핵심 도구
• 코드를 더 유연하고 재사용 가능하게 만듦

Functional composition

• A functional form that takes two functions as parameters
• Yields a function whose value is the first actual parameter function
• applied to the application of the second
• [EX] Form: h ≡ f ˚ g (˚ is operator for function composition)
• means h(x) ≡ f(g(x))
• for f(x) ≡ x + 2, g(x) ≡ 3*x, h ≡ f ˚ g yields (3*x) + 2

def compose(f, g):
    return lambda x: f(g(x))

def square(x): return x * x
def add_one(x): return x + 1

new_func = compose(square, add_one)
print(new_func(3)) # 결과: square(add_one(3)) → square(4) = 16

Apply-to-all

• A functional form that takes a single function as a parameter
• Yields a list of values obtained by applying the given function to each element of a list of parameters
• Form: $\alpha$
• For h(x) ≡ x * x
• $\alpha(h, (2, 3, 4))$ yields (4, 9, 16)

def h(x):
    return x * x

numbers = [2, 3, 4]
result = list(map(h, numbers))
print(result) # [4, 9, 16]

# with 람다 표현식
result = list(map(lambda x: x * x, [2, 3, 4]))

Fundamentals of Functional Programming Languages

Objective of design of FPL

• Mimic mathematical functions
• 입력이 주어지면 항상 같은 결과를 반환하고 중간 상태나 변수 없이 계산이 이뤄짐 → 예측 가능하고 안전한 계산
• The basic process of computation is fundamentally different from imperative language
• In imperative
• 컴퓨터에게 "어떻게(how)" 계산할지 명령을 내리는 방식
• Operations are done → results are stored in variables
• Management of variable is concern and course of complexity
• [EX] (x+y)/(a-b)
• Value of (x+y) is computed and stored while (a-b) is evaluated
• In FPL
• "무엇을(what)" 계산할지를 선언(declare)하는 방식
• 계산 순서나 중간 변수에 신경 쓰지 않고, 모든 것이 표현식(expression)으로 구성됨
• [EX] (x+y)/(a-b)
• 변수 값이 주어지면, 내부적으로 계산이 자동으로 진행됨 중간 상태 없이, 결과만 반환됨
• Variables and assignments are not necessary (as in math)
• 수학에서 x = 3라고 하면, x는 절대 바뀌지 않는 값
• 반면 명령형 언어에선 x = x + 1 같은 문장이 가능
• 함수형 언어에선 값이 한 번 정해지면 절대 바뀌지 않음 → 변수가 아니라 상수에 가까움
• → Freeing programmer from concerns of memory cells
• Iterative construct → recursion
• 상태(state)를 바꾸는 반복 대신 순수한 함수 호출로 해결
• Referential Transparency - Evaluation of a function always produces the same result given the same parameters
• 같은 입력 → 항상 같은 출력
• 외부 상태에 영향을 받지 않음 = 순수 함수
• 이런 성질이 있으면 디버깅이 훨씬 쉽고, 테스트도 간단함
• Makes semantics of FPL far simpler than imperative
• 변수 변화 없음, 순수 함수만 존재, 상태도 없음
• A set of primitive functions are provided (smaller number is good)
• FPL은 보통 적은 수의 기본 함수만 제공하고, 그걸 조합해서 복잡한 동작을 만들게 유도함.

Original Lisp

The first functional language

• LISt Processing의 줄임말 → 리스트 기반 데이터 구조를 다루기 아주 좋음
• No longer represents the latest design concepts for functional languages
• Represent well the fundamental concepts of functional programming
• LISP는 람다 표현식, 재귀, 함수 자체를 값처럼 다루는 방식 등 함수형 프로그래밍의 핵심 개념을 담고 있음
• Therefore worthy of study
• All LISP dialects include imperative-language features
• Imperative-style variables, assignment statements, and iteration

Lisp Data Types and Structures

Data object types: originally only atoms and lists

• (1) Atom (원자): 쪼갤 수 없는 단일 값
• 숫자, 기호(symbol), 문자 등이 포함
• 예: A, 42, 'hello”
• (2) List (리스트)
• 괄호로 둘러싸인 원자와 리스트의 집합
• 리스트 안에는 다른 리스트도 포함될 수 있어 (중첩 가능)
• List form: parenthesized collections of sublists and/or atoms
• [EX] (A (B C) D (E (F G)))
• 첫 번째 원소: A (atom)
• 두 번째: (B C) (sublist)
• 세 번째: D (atom)
• 네 번째: (E (F G)) (sublist 안에 또 sublist)

Originally, Lisp was a typeless language

• 초기 Lisp에서는 모든 값이 리스트 또는 atom으로 표현됨
• 정수, 문자열, 불리언 같은 타입 구분이 명확하지 않았음
• 나중에 Common Lisp 등에서 다양한 타입이 추가됨 (예: integer, float, string 등)
• Lisp lists are stored internally as singlelinked lists
• (A B C)
• [A] → [B] → [C] → NIL

Lisp Interpretation

The first requirement for the universal LISP function

• The first Lisp interpreter appeared only as a demonstration of the universality of the computational capabilities of the notation
• Lisp의 핵심 철학 중 하나인 코드와 데이터의 동일한 표현 (Code-as-Data)
• Notation allowing functions to be expressed in the same way data expressed
• [EX] (A B C) , [ex] (+ 2 3) ; → 5
• [1] 데이터로 해석: Can be interpreted as a simple list of three atoms
• 원자 A, B, C가 들어 있는 리스트
• [2] 코드로 해석: Can be interpreted as if function named A is applied to two parameters
• 함수 A가 B와 C를 인자로 받아 호출되는 것
• 코드도 데이터처럼
• 프로그램이 자기 자신을 분석하거나 수정할 수 있음 → 메타프로그래밍 가능
• (eval '(+ 1 2))
• 컴파일러, 인터프리터, 매크로 시스템 등을 언어 내부에서 구현할 수 있음

Specified in a prefix list form (Cambridge Polish or Cambridge prefix)

• 수식이나 함수 호출을 항상 앞에서부터 읽음
• (function_name argument1 … argumentn)
• 앞에 함수 이름이 오는 형식(prefix)을 씀
• (+ 5 7)
• (+ 3 4 7 6)
• Lambda notation is used to specify functions and function definitions
• 함수를 만들 때 LAMBDA라는 키워드를 사용
• (function_name (LAMBDA (arg1 ... argn) expression))
• 이건 "이름이 있는 함수"를 정의하는 방식
• (define square (lambda (x) (* x x)))
• square라는 이름의 함수 정의
• (lambda (x) (* x x)) → x를 받아서 x * x를 계산하는 함수
• ((lambda (x) (* x x)) 5) ; → 25
• 이름 없는 함수도 가능
• 함수에 이름 없이 바로 정의하고, 5를 넣어 실행함

All LISP structures, both data and code, were called S-expression

• S-expressions became LISP’s only notation
• 괄호로 둘러싸인 리스트 구조
• 이 안에 데이터든 함수 호출이든 다 표현
• (+ 2 3) ; 함수 호출, 실행 가능한 함수 호출
• (A (B C) D) ; 데이터 리스트, 단순한 리스트 데이터

McCarthy successfully developed a universal function (EVAL) that could evaluate any other function

• 어떤 코드든 실행할 수 있는 함수
• Implementation of EVAL could serve as a LISP interpreter
• EVAL은 S-expression을 받아서 실제로 실행시킴
• Lisp 코드 자체를 입력값으로 받아 처리함
• (eval '(+ 2 3)) ; → 5
• 존 매카시(John McCarthy)는 이 EVAL 함수 하나로 모든 Lisp 프로그램을 실행할 수 있게 만듦 → Lisp 인터프리터 자체를 Lisp로 구현할 수 있게 됨
• Before 1975, dialects of LISP are dynamic scoping
• Contemporary dialects use static scoping or can choose static or dynamic.

Origins of Scheme

A mid-1970s dialect of Lisp, designed to be a cleaner, more modern, and simpler version than the contemporary dialects of Lisp

• Uses only static scoping (이전 Lisp은 동적 스코핑 사용)
• Functions are first-class entities
• A first-class object refers to an object that supports all operations that are generally applicable to other objects
• They can be the values of expressions and elements of lists
• They can be assigned to variables, passed as parameters, and returned from functions

The Scheme Interpreter

Scheme의 인터프리터 동작 방식

• In interactive mode, the Scheme interpreter is an infinite read-evaluate-print loop (REPL)
• → Read (읽기) → Eval (평가) → Print (출력) → 반복
• → 사용자가 입력한 식(expression)을 읽고, 평가하고, 그 결과를 출력한 뒤 다시 대기
• This form of interpreter is also used by Python and Ruby (현대 스크립트 언어)
• Expressions are interpreted by the function EVAL (주어진 식을 해석하고 실행하는 기능)
• Literals evaluate to themselves
• If typing a number to interpreter → simply display the number
• EVAL은 Scheme 내부에서 표현식을 받아 실행 결과를 반환하는 함수
• Scheme에서는 코드도 일종의 리스트 구조(S-expression)이기 때문에, 리스트로 표현된 코드를 그대로 실행시킬 수 있음
• > (eval '(+ 2 3))
• 5
• 보통은 직접 eval을 자주 쓰진 않지만, 다음과 같은 상황에서 유용
• 사용자가 입력한 문자열을 코드로 실행하고 싶을 때
• 메타프로그래밍 (코드를 조작하는 코드)을 구현할 때
• REPL을 구현할 때 (eval이 핵심 함수)

Primitive Function Evaluation

Primitive Function Evaluation의 과정

• [인자평가] Parameters are evaluated, in no particular order
• → 인자 간 부작용(side effect)이 있다면 결과가 달라질 수 있음
• → 순수 함수 사용이 권장됨
• [전달] The values of the parameters are passed into the function body
• 전달된 인자 값을 이용해 함수 로직 수행
• [분문 실행] The function body is evaluated
• [반환] The value of the last expression in the body is the value of the function
• Scheme에서는 마지막 식의 결과값이 전체 함수의 반환값

Primitive Functions & LAMBDA Expressions

Primitive Arithmetic Functions: +, -, * , /, MODULO, ROUND, MAX, MIN, LOG, SIN, and SQRT

• 접두(prefix) 표기법을 사용
• If no parameters are given for *, 1 is returned (곱셉의 항등원)
• If no parameters are given to +, 0 is returned (덧셈의 항등원)
• Use uppercase letters for all reserved words and predefined functions

Lambda Expressions

• Nameless function actually includes the word LAMBDA
• Form is based on $\lambda$ notation
• [EX] (LAMBDA (x) (* x x))
• 이 식 자체는 함수 객체(function object)를 반환
• Lambda expressions can be applied to parameters
• [EX] ((LAMBDA (x) (* x x)) 7)
• x is called a bound variable (never change after being bound)
• Lambda expressions can have any number of parameters
• [EX] (LAMBDA (a b x) (+ (* a x x) (* b x)))

Special Form Function: DEFINE

DEFINE - Two forms:

• The evaluation process (interpreted by EVAL) for DEFINE is different!
• [1] To bind a symbol to an expression (어떤 이름에 값을 "정의"하는 방식)
• [EX] (DEFINE pi 3.141593)
• pi는 3.141593에 바인딩됨
• [EX of use] (DEFINE two_pi (* 2 pi))
• two_pi는 (* 2 pi)의 평가 결과인 6.283186에 바인딩됨
• These symbols are not variables – they are like the names bound by Java’s final declarations
• → 다시 DEFINE하지 않는 이상 변경 불가
• [2] To bind names to lambda expressions (LAMBDA is implicit)
• 이 경우 LAMBDA가 암묵적으로 포함됨
• [EX] (DEFINE (square x) (* x x)) → (DEFINE square (LAMBDA (x) (* x x)))
• [EX of use] (square 5)
• The first parameter is never evaluated
• The second parameter is evaluated and bound to the first parameter

Output Functions

Usually not needed

• Because interpreter always displays the result of a function evaluated at the top level (not nested)
• 단, 이건 최상위 수준에서만 해당됨. 함수 내부에서 출력을 원할 경우 명시적 출력 함수값이 필요함
• Scheme has PRINTF, which is similar to the printf function of C
• 대부분의 표준 Scheme에는 없고, 일부 구현에서만 지원

Display and Read Functions

DISPLAY function: simply prints the arguments

• (DISPLAY 21) 21
• (DISPLAY "hello") hello

READ function: enter what we type on the keyboard

• (DEFINE x (READ)) 7

Numeric Predicate Functions

A predicate function is one that returns a Boolean value

• #T (or #t) is true and #F (or #f) is false
• (= 3 3) ; → #t
• (< 3 5) ; → #t
• (> 7 10) ; → #f
• Sometimes () is used for false
• 주요 판별 연산자 (=, <>, >, <, >=, <=)
• 숫자 관련 판별 함수 (EVEN?, ODD?, ZERO?, NEGATIVE?)
• Notice that the names for all predefined predicate functions that have words for names end with question marks
• The NOT function inverts the logic of a Boolean expression
• (NOT #t) ; → #f
• (NOT #f) ; → #t
• (NOT (EVEN? 3)) ; → #t
• (DEFINE x 11)
• (= x 11) returns #T
• (> x 11) returns ()
• (< x 15) return #T
• (EVEN? x) returns ()
• (ODD? x) returns #T

Control Flow

Selection- the special form, IF (two-way selector function)

• (IF predicate then_exp else_exp)

(IF (> 3 2) 'yes 'no)
; returns yes

(DEFINE x 7)
(DEFINE y 10)
(IF (> x y)
    (- x y)
    (- y x))
; returns 3

(DEFINE (test x)
  (IF (>= x 70)
      (DISPLAY "pass")
      (DISPLAY "fail")))
(test 75) ; returns pass

(DEFINE (factorial n)
  (IF (<= n 1)
      1
      (* n (factorial (− n 1)))))

Recall from Chapter 8 the COND function (multiple selection):

(DEFINE (admissionfee age)
  (COND
    ((<= age 6) 0)
    ((< age 60) 5000)
    (ELSE 2500)))
(admissionfee 65) ; returns 2500

(DEFINE (leap? year)
  (COND
    ((ZERO? (MODULO year 400)) #T)
    ((ZERO? (MODULO year 100)) #F)
    (ELSE (ZERO? (MODULO year 4)))))
(leap? 2024) ; returns #T

List Functions

QUOTE - takes one parameter; returns the parameter without evaluation

• QUOTE is required because the Scheme interpreter, named EVAL, always evaluates parameters to function applications before applying the function
• QUOTE is used to avoid parameter evaluation when it is not appropriate
• 평가를 막고, 원래 모양 그대로 넘김
• QUOTE can be abbreviated with the apostrophe prefix operator
• '(A B) is equivalent to (QUOTE (A B))
• 만약 QUOTE 없이 그냥 (A B)를 쓰면, Scheme은 A라는 함수를 B에 적용하려고 시도함 → 오류 발생 가능
• Recall that CAR, CDR, and CONS were covered in Chapter 6

CAR and CDR operations:

• (CAR '(A B C)) returns A

• (CAR ′((A B) C D)) returns (A B)

• (CAR ′A) is an error because A is not a list

• (CAR '(A)) returns A

• Names lies in the first implementation (IBM 704) of LISP

• IBM 704는 하나의 레지스터를 두 개의 필드로 나누어 사용

• CAR (contents of the address part of a register) - 헤드를 표현

• CDR (contents of the decrement part of a register) - 꼬리를 표현

• (CAR '()) is an error

• (CDR '(A B C)) returns (B C)

• (CDR ′((A B) C D)) returns (C D)

• (CDR ′A) is an error

• (CDR ′(A)) returns ()

• (CDR '()) is an error

Combine CAR and CDR

• (DEFINE (second a_list) (CAR (CDR a_list)))
• (second '(A B C)) returns B
• [함수 합성 축약형 (Built-in Compositions)] Some of the most commonly used functional compositions in Scheme are built in as single functions
• (CAAR x) is equivalent to (CAR(CAR x))
• (CADR x) is equivalent to (CAR (CDR x))
• (CADDAR x) is equivalent to (CAR (CDR (CDR (CAR x))))

CONS: inverse of CAR and CDR

• Two parameters to CONS: CAR and CDR of the new list
• (CONS (CAR a_list) (CDR a_list)) returns a_list
• (CONS 'A '()) returns (A)
• (CONS 'A '(B C)) returns (A B C)
• (CONS ′() ′(A B)) returns (() A B)
• (CONS ′(A B) ′(C D)) returns ((A B) C D)

LIST is a function for building a list from any number of parameters

• (LIST ′apple ′orange ′grape) returns (apple orange grape)
• = (CONS 'apple (CONS 'orange (CONS 'grape '())))
• 내부적으로는 CONS를 여러 번 중첩해서 리스트를 만드는 것과 같음

Predicate Function

Predicate Function: EQ? (객체의 동일성(identity)을 비교)

• EQ? takes two expressions as parameters (usually two atoms);
• It returns #T if both parameters have the same pointer value; otherwise #F
• 두 객체가 동일한 메모리 주소(= 포인터)를 참조하는가를 검사
• (EQ? 'A 'A) yields #T
• (EQ? 'A 'B) yields #F
• (EQ? 'A '(A B)) yields #F
• (EQ? '(A B) '(A B)) yields #T or #F
• 서로 구조가 같아도 다른 객체일 수 있음 (리스트는 매번 새로 생성됨)
• (EQ? 3.4 (+ 3 0.4)) yields #T or #F
• 부동소수점 연산 결과가 내부적으로 같아도 객체는 다를 수 있음

Predicate Function: EQV?

• EQ? works for symbolic atoms but does not necessarily work for numeric atoms
• = predicate works for numeric atoms but not symbolic atoms
• 값(value)이 같은지를 비교하는 predicate 함수
• EQV? is like EQ?, except that it works for both symbolic and numeric atoms
• EQ?와 비슷하지만, 더 유연하고 넓은 범위의 타입에 대해 잘 작동
• It is a value comparison, not a pointer comparison
• (EQV? 3 3) yields #T
• (EQV? 'A 3) yields #F
• (EQV 3.4 (+ 3 0.4)) yields #T
• (EQV? 3.0 3) yields #F (floats and integers are different)
• Primary reason to use EQ? or =
• Faster than EQV?

Predicate Functions: LIST? and NULL?

• LIST? takes one parameter;
• It returns #T if the parameter is a list; otherwise #F
• x가 리스트인지 확인
• (LIST? '(X Y)) returns #T
• (LIST? 'X) returns #F ; 단순 심볼
• (LIST? '()) yields #T ; 빈 리스트도 리스트임
• NULL? takes one parameter;
• It returns #T if the parameter is the empty list; otherwise #F
• x 가 빈 리스트인지 확인
• (NULL? '(A B)) returns #F
• (NULL? '()) returns #T
• (NULL? 'A) returns #F ; 심볼은 리스트도, 빈 리스트도 아님
• (NULL? '(())) yields #F ; 요소로 빈 리스트를 가진 리스트 → 비어있지 않음

Example Scheme Function: sort

(DEFINE (insert atm lst)
  (COND
    ((NULL? lst) (CONS atm '()))
    ((< atm (CAR lst)) (CONS atm lst))
    (ELSE (CONS (CAR lst) (insert atm (CDR lst))))))

(DEFINE (sort lst)
  (if (NULL? lst)
      '()
      (insert (CAR lst) (sort (CDR lst)))))

(sort '(3 7 5 1 9)) ; returns (1 3 5 7 9)

• 1. (insert atm lst)

• 목적: 숫자 하나 atm을 정렬된 리스트 lst에 알맞은 위치에 삽입

• 작동 방식:

• 리스트가 비었으면 → 단독 리스트로 만들기

• atm이 리스트의 첫 원소보다 작으면 → 앞에 넣기

• 아니면 → 리스트의 나머지에 재귀적으로 삽입

• 2. (sort lst)

• 목적: 리스트 lst를 오름차순으로 정렬

• 작동 방식:

• 리스트가 비었으면 → 빈 리스트 반환

• 아니면 → 첫 원소는 빼서 sort로 정렬한 나머지에 insert함수로 삽입

Example C Function: sort

// insert: 정렬된 리스트에 value 삽입
Node* insert(int value, Node* lst) {
    if (lst == NULL || value < lst->value) {
        Node* new_node = create_node(value);
        new_node->next = lst;
        return new_node;
    } else {
        lst->next = insert(value, lst->next);
        return lst;
    }
}

// sort: 삽입 정렬
Node* sort(Node* lst) {
    if (lst == NULL) return NULL;
    Node* sorted = sort(lst->next);
    return insert(lst->value, sorted);
}

• 1. insert(int value, Node* lst)

• 목적: 숫자 하나 value을 정렬된 리스트 lst에 알맞은 위치에 삽입

• 작동 방식:

• 리스트가 비었거나, value가 리스트의 첫 원소보다 작으면 → 앞에 넣기

• 아니면 → 리스트의 나머지에 재귀적으로 삽입

• 2. sort(Node* lst)

• 목적: 리스트 lst를 오름차순으로 정렬

• 작동 방식:

• 리스트가 비었으면 → 빈 리스트 반환

• 아니면 → 첫 원소는 빼서 sort로 정렬한 나머지에 insert함수로 삽입

Example Scheme Function: member

(DEFINE (member atm a_list)
  (COND
    ((NULL? a_list) #F) ; 리스트가 비었으면 찾을 수 없음
    ((EQ? atm (CAR a_list)) #T) ; 첫 원소가 같으면 찾았음
    (ELSE (member atm (CDR a_list))))) ; 아니면 나머지에서 계속 찾기

(member 'B '(A B C)) ; returns #T
(member 'B '(A C D E)) ; returns #F

// 리스트에 해당 값이 있는지 검사 (member 함수)
bool member(const char* atom, Node* list) {
    if (list == NULL) return false;
    if (strcmp(atom, list->value) == 0)
        return true;
    return member(atom, list->next);
}

Example Scheme Function: equalsimp

• equalsimp takes two simple lists as parameters; returns #T if the two simple lists are equal; #F otherwise

(DEFINE (equalsimp list1 list2)
  (COND
    ((NULL? list1) (NULL? list2)) ; 둘 다 빈 리스트면 같음
    ((NULL? list2) #F) ; list1만 비었고 list2는 안 비었으면 다름
    ((EQ? (CAR list1) (CAR list2)) ; 첫 원소가 같으면
     (equalsimp (CDR list1) (CDR list2))) ; 나머지를 재귀적으로 비교
    (ELSE #F))) ; 첫 원소가 다르면 다름

• *Simple list: 리스트 안에 또 다른 리스트가 없는 구조. 모든 요소가 원자(atom) 또는 심볼(symbol) 같은 단순한 값

// equalsimp 함수: 두 리스트가 같은지 비교
bool equalsimp(Node* list1, Node* list2) {
    if (list1 == NULL && list2 == NULL)
        return true;
    if (list1 == NULL || list2 == NULL)
        return false;
    if (strcmp(list1->value, list2->value) != 0)
        return false;
    return equalsimp(list1->next, list2->next);
}

Example Scheme Function: equal

• equal takes two general lists as parameters;
• Complex than simple list case because sublist must be traced (리스트 안에 sublist가 있어도 비교 가능)
• Returns #T if the two lists are equal; #F otherwise (두 리스트가 모양과 값 모두 같은지를 판단)

(DEFINE (equal list1 list2)
  (COND
    ((NOT (LIST? list1)) (EQ? list1 list2)) ; Handle the situation where either of the parameters is an atom instead of a list
    ((NOT (LIST? list2)) #F)
    ((NULL? list1) (NULL? list2)) ; Handle the situation where one or both lists are empty
    ((NULL? list2) #F)
    ((equal (CAR list1) (CAR list2)) ; 첫 원소 비교
     (equal (CDR list1) (CDR list2))) ; 나머지 비교
    (ELSE #F)))

• equal is equivalent to EQUAL? (but slower than EQ? and EQV?)

Example Scheme Function: append

• append takes two lists as parameters;
• Returns the first parameter list with the elements of the second parameter list appended at the end
• (append '(A B) '(C D R)) returns (A B C D R)
• (append '((A B) C) '(D (E F))) returns ((A B) C D (E F))

(DEFINE (append list1 list2)
  (COND
    ((NULL? list1) list2) ; list1이 비었으면, list2 그대로 반환
    (ELSE (CONS (CAR list1) ; list1의 첫 원소를 유지하고
                (append (CDR list1) list2))))) ; 나머지(list1의 꼬리)와 list2를 재귀적으로 이어붙임

Example Scheme Function: guess

• guess takes two lists as parameters;
• Yields a simple list that contains the common elements of its two parameter lists
• 두 리스트 간의 공통 요소를 찾아내는 함수

(DEFINE (guess list1 list2)
  (COND
    ((NULL? list1) '()) ; list1이 비었으면 공통 요소도 없으므로 빈 리스트 반환
    ((member (CAR list1) list2) ; list1의 첫 원소가 list2에 포함되면
     (CONS (CAR list1) (guess (CDR list1) list2))) ; 그 원소를 결과에 추가하고 나머지 재귀 호출
    (ELSE (guess (CDR list1) list2)))) ; 포함되지 않으면 그냥 나머지에서 계속 탐색

(guess '(A B C D) '(B D F)) ; → (B D)

Example Scheme Function: adder

• adder takes lists as parameters;
• Yields sum of the lists (숫자로만 구성된 리스트의 합을 계산하는 함수)

(DEFINE (adder a_list)
  (COND
    ((NULL? a_list) 0) ; 리스트가 비었으면 합은 0
    (ELSE (+ (CAR a_list) (adder (CDR a_list)))))) ; 첫 원소와 나머지의 합을 더함

(adder '(1 2 3)) returns 6
(adder '(1 (2) 3)) returns error

int adder(Node* list) {
    if (list == NULL)
        return 0;
    return list->value + adder(list->next);
}

• Resolved! (중첩 리스트(nested list)까지 모두 순회해서 안에 있는 숫자를 전부 합산)

(DEFINE (adder a_list)
  (COND
    ((NULL? a_list) 0) ; 리스트가 비었으면 0 반환
    ((LIST? (CAR lst)) ; 첫 원소가 리스트이면
     (+ (adder (CAR lst)) (adder (CDR lst)))) ; 그 리스트와 나머지를 재귀적으로 더함
    (ELSE (+ (CAR a_list) (adder (CDR a_list)))))) ; 숫자면 그대로 더하고 나머지 재귀 호출

int adder(Node* list) {
    if (list == NULL) return 0;
    Element e = list->value;
    int head_sum = 0;
    if (e.type == NUMBER) {
        head_sum = e.number;
    } else if (e.type == LIST) {
        head_sum = adder(e.list); // 중첩 리스트 재귀 호출
    }
    return head_sum + adder(list->next);
}

Example Scheme Function: LET

• LET is actually shorthand for a LAMBDA expression applied to a parameter
• LET은 이름에 값을 임시로 바인딩하고, 그 값을 표현식 안에서 사용하는 구조
• 실제로는 LAMBDA + 즉시 호출로 구현된 문법적 편의(syntactic sugar)
• (LET ((alpha 7)) (* 5 alpha)) ; → 35
• is the same as: ((LAMBDA (alpha) (* 5 alpha)) 7)
• alpha라는 매개변수를 받아 (* 5 alpha)를 수행 인자 7이 alpha에 전달됨
• LET creates a local scope in which names are temporarily bound to the values of expressions
• These names can then be used in the evaluation of another expression, but they cannot be rebound to new values in LET.
• LET 내부에서 바인딩된 이름은 다시 SET! 등으로 바꿀 수 없음
• 변수 재정의는 불가능: 단순히 값 하나를 일시적으로 할당할 뿐

LET Example

• 이차방정식의 근의 공식을 이용해 두 근을 구하는 함수

(DEFINE (quadratic_roots a b c)
  (LET (
        ; 판별식의 제곱근을 2a로 나눈 부분
        (root_part_over_2a
         (/ (SQRT (- (* b b) (* 4 a c))) (* 2 a)))
        (minus_b_over_2a (/ (- 0 b) (* 2 a))))
    ; 결과를 리스트로 반환: 두 근
    (LIST (+ minus_b_over_2a root_part_over_2a)
          (- minus_b_over_2a root_part_over_2a))))

Tail Recursion in Scheme

• Definition: A function is tail recursive if its recursive call is the last operation in the function → 즉, 재귀 호출 뒤에 아무 연산도 남지 않아야 함
• A tail recursive function can be automatically converted by a compiler to use iteration, making it faster
• 컴파일러가 스택 프레임을 유지하지 않고, 반복문처럼 처리할 수 있음 → 메모리 낭비 없음, 성능 향상, 스택 오버플로우 방지
• Scheme language definition requires that Scheme language systems convert all tail recursive functions to use iteration
• Scheme 컴파일러 또는 인터프리터는 tail call을 자동으로 최적화해야 함

(DEFINE (member atm a_list)
  (COND
    ((NULL? a_list) #F)
    ((EQ? atm (CAR a_list)) #T)
    (ELSE (member atm (CDR a_list)))))

• Example of rewriting a function to make it tail recursive, using helper a function

; Original
(DEFINE (factorial n)
  (IF (<= n 0)
      1
      (* n (factorial (- n 1)))))

; Tail recursive
(DEFINE (factorial n)
  (DEFINE (facthelper n factpartial)
    (IF (<= n 0)
        factpartial
        (facthelper (- n 1) (* n factpartial))))
  (facthelper n 1))

Functional Form - Composition

• If h is the composition of f and g, h(x) = f(g(x)) (두 함수 f와 g를 합쳐서 새로운 함수 h를 만드는 것)

(DEFINE (g x) (* 3 x)) ; g(x) = 3 * x
(DEFINE (f x) (+ 2 x)) ; f(x) = x + 2
(DEFINE (h x) (f (g x))) ; 함수 합성
(DEFINE (h x) (+ 2 (* 3 x))) ; (The composition) ; f(g(x)) 직접 계산

• In Scheme, the functional composition function compose can be written:
• 합성용 고차 함수 compose를 직접 정의할 수도 있음

(DEFINE (compose f g)
  (LAMBDA (x)
    (f (g x))))

• compose는 두 함수를 받아서 새로운 합성 함수를 만들어 반환

• (compose f g)는 수학적으로 f(g(x))와 같음

• ((compose CAR CDR) '((a b) c d)) yields c → CADR

• CDR → ((a b) c d)의 꼬리: (c d)

• CAR → (c d)의 첫 원소: c

• 결과: c → 즉, CADR

• ((compose CDR CAR) '((a b) c d)) yields (b) → CDAR

• CAR → ((a b) c d)의 첫 원소: (a b)

• CDR → (a b)의 꼬리: (b)

• 결과: (b) → 즉, CDAR

• (DEFINE (third a_list)((compose CAR (compose CDR CDR)) a_list)) is equivalent to CADDR

• (compose CDR CDR) → CDDR

• compose CAR ... → CAR(CDDR(x)) → 즉, CADDR

Functional Form – Apply-to-All

• Apply to All - one form in Scheme is map
• Applies the given function to all elements of the given list
• 리스트의 모든 요소에 어떤 함수를 적용해서 새로운 리스트를 만드는 함수

(DEFINE (map fun a_list)
  (COND ((NULL? a_list) '()) ; 리스트가 비었으면 빈 리스트 반환
        (ELSE (CONS (fun (CAR a_list)) ; 현재 원소에 함수 적용
                    (map fun (CDR a_list)))))) ; 나머지 리스트에 재귀적으로 map

• (map (LAMBDA (num) (* num num num)) '(3 4 2 6)) yields (27 64 8 216)
• (cons 27 (cons 64 (cons 8 (cons 216 '())))) → (27 64 8 216)

FOLD – 누적 계산

(DEFINE (FOLD F BASE A_LIST)
  (COND
    ((NULL? A_LIST) BASE) ; 리스트 끝 → 누적값 반환
    (ELSE (F (CAR A_LIST) (FOLD F BASE (CDR A_LIST)))))) ; 재귀적으로 누적 계산

(FOLD + 0 '(1 2 3 4)) ; → 10
(FOLD * 1 '(2 3 4)) ; → 24

FILTER – 조건에 맞는 값만 걸러내는 함수

(DEFINE (FILTER PRED A_LIST)
  (COND
    ((NULL? A_LIST) '()) ; 리스트가 비었으면 종료
    ((PRED (CAR A_LIST))
     (CONS (CAR A_LIST) (FILTER PRED (CDR A_LIST)))) ; 현재 원소가 조건 만족 → 포함 + 나머지 재귀
    (ELSE (FILTER PRED (CDR A_LIST))))) ; 조건 불만족 → 건너뛰기

(FILTER EVEN? '(1 2 3 4)) ; → (2 4)

Functions That Build Code

It is possible in Scheme to define a function that builds Scheme code and requests its interpretation

• Scheme은 “코드를 데이터처럼” 다룰 수 있는 언어
• 그래서 코드를 생성하는 함수를 만들고, 그 코드를 해석해서 실행할 수도 있음.
• Scheme이 가진 메타프로그래밍 능력 중 하나
• This is possible because the interpreter is a user-available function, EVAL
• Scheme에서는 코드 구조가 리스트(S-expression) 표현
• 프로그램 안에서 코드를 조립하고, EVAL을 통해 그걸 실제로 실행할 수 있음

(DEFINE (make-def name val)
  (LIST 'DEFINE name val))

• 함수 make-def는 실제로 정의문(DEFINE x 42)를 "데이터"로 만든 다음, EVAL을 통해 실행시켜 → 실제로 변수를 정의함
• (make-def 'x 42) ; → '(DEFINE x 42)
• (EVAL (make-def 'x 42) (interaction-environment))
• x ; → 42

Adding a List of Numbers

The parameter is a list of numbers to be added;

• Cannot apply + directly on the list, because + can take only atomic parameters
• Write a function that repeatedly adds the CAR of the list to the sum of its CDR, using recursion

(DEFINE (adder a_list)
  (COND
    ((NULL? a_list) 0)
    (ELSE (+ (CAR a_list) (adder (CDR a_list))))))

• adder inserts a + operator and evaluates the resulting list
• Use CONS to insert the atom + into the list of numbers.
• Be sure that + is quoted to prevent evaluation
• Submit the new list to EVAL for evaluation

(DEFINE (adder a_list)
  (COND
    ((NULL? a_list) 0)
    (ELSE (EVAL (CONS '+ a_list)))))

• 리스트의 숫자들을 다 더해야 하는데, + 연산자를 리스트 앞에 붙여서 하나의 Scheme 코드로 만든 뒤, 그걸 EVAL로 실행하는 방식