첫번째 과제 풀이 및 두번째 과제

여러분 두번째 과제는 첫번째 과제보다 훨씬 간단합니다. 첫번째 과제를 못내서 실망하신 분들도 훨씬 가볍게 도전해서 성공할 수 있습니다.

람다계산법에 대해 이어서 설명

LamCalc 노트북에서도 확인했듯이 일반적으로 람다식에는 하나 이상의 줄일식(redex)가 있을 수 있으므로, 다음 번에 어떤 redex를 줄일지에 대한 전략을 세울 수 있는데 이를 줄이기 전략(reduction strategy)이라고 한다.

대표적인 줄이기 전략 두 가지로는

• applicative order reduction (또는 call-by-value reduction)
• normal order reduction (또는 call-by-name reduction)

이것을 추론규칙(inference rule)의 형태로 표기하는 방법들에 대해서도 짧은 시간 안에 칠판에 설명

Normalization vs. Evaluation

관례적으로 람다계산법에서

• Normalization
  • 함수 안까지 찾아들어가서 계속 식을 줄인다.
  • 다음 번에 줄일 부분이 하나로 결정되어 있지 않을 수도
  • 이론적인 람다식에 대한 성질을 연구하기 위해 주로 활용하는 개념
• Evaluation
  • 취급하여 함수 안에 들어있는 식을 줄이러 들어가지 않는다 (즉 함수가 value)
  • 보통 다음 번에 줄일 부분을 한가지로 결정한다
    • 함수 안으로 식을 줄이로 들어가지 않더라도 여전히 여러개의 redex가 있을 수 있다
    • 다음 번에 어떤 redex를 줄일지 evaluation strategy가 여러가지 있을 수 있다
  • 람다식을 이용한 효과적인 계산방법 또는 프로그래밍 언어 설계에 주로 활용하는 개념

이는 대표적인 evaluation strategy 세 가지로는 Call-by-Value, Call-by-Name, Call-by-Need가 있다. 수업에서는 람다계산법을 예로 설명하지만 프로그래밍 언어 설계에서도 이와 관련된 이슈들이 반복해서 나타난다.

call-by-value evaluation을 다른 말로는 eager(적극적) evaluation또는 strict(엄격한) evaluation이라고도 한다. call-by-need evaluation을 다른 말로는 lazy(게으른) evaluation이라고도 한다. 프로그래밍 언어 설계에서 call-by-name은 프로그래밍 언어의 실행 의미를 규정하는 evaluation으로써보다는 매크로 확장과 같은 소스코드 레벨에서의 전처리 개념과 연관지어 이해하기도 한다. 그리고 call-by-name이나 call-by-need 등을 non-strict evaluation으로 분류하기도 한다.

주교재 읽기 자율과제: 이와 관련된 주교재 내용이 8.3절에 있으니 한번 읽어보라.

그리고 앞으로는 CBV evaluation을 하스켈로 프로그래밍하게 될 것이다.

• https://github.com/kyagrd/courseREhs

위 저장소의 cbvEval 노트북을 살펴보자.