Prologue
본 교재는, 저자가 1996년부터, 전북대학교 컴퓨터과학과와 컴퓨터공학부에서 강의했던, “고급프로그래밍언어” 과목의 강의 자료를 정리하고 보강한 결과물이다.
저자는 교재를 만들면서 많은 생각이 들었다. 그 중, 가장 중요한 것은, 내가 그 동안 얼마나 체계적인 학습을 소홀히 했는가에 대한 자책이었고, 또 하나는, 내가 왜 진작 이런 교재를 만들지 않았던가에 대한 후회였다. 그 이유는 다음과 같다.
저자가 처음 프로그램에 매료되었던 시점은 학부 3학년 2학기 Assembly 언어를 배울 때였다. 지금은 기억도 희미한, IBM 출신의 중년 여교수로부터, IBM3070 architecture 기반 assembly 언어로, binary tree를 이용한 sort, search 등과 같은 연산을 수행하는 기말 프로젝트로 수행하던 때였다. Memory와 register 등의 연산에서 단 한 치(bit)의 오류도 허용하지 않았던 assembly 언어에 대한 컴퓨터 프로그래밍의 경험은 컴퓨터에 대한 엄밀성을 넘어서, 컴퓨터에 대한 경외심을 자아내기에 충분했다. Memory에서의 모든 데이터의 크기와 위치를 정밀하게 계산해서, 앞으로 전개될 binary tree에 의한 재귀적인 함수의 호출에 요구되는 입력과 출력 데이터의 크기를 반영해야 하는 상황은, 이전의 프로그래밍에서 느낄 수 없었던 성취감을 느끼게 해 주었다.
이러한 Assembly 언어에 대한 학습과 경험은 다음 학기인 4학년 1학기의 운영체제와 컴파일러 과목에서 도적전인 프로젝트를 성공적으로 수행할 수 있는 기반을 마련해 주었다. 특히, Unix OS의 fork 시스템 함수와 socket과 pipe 통신 메커니즘을 활용한, 다수의 사용자의 문서 편집을 위한 min-OS를 개발하던 프로젝트와, Lex와 Yacc을 이용한 mini C 컴파일러를 개발하던 프로젝트는, 성취감 이상의 자부심을 느끼게 해 주었다. 특히, 두 대의 terminal에서 사용자가 독립적으로 동시에 login을 할 수 있고, 그 terminal에서 각 사용자에게 서로에게 문자와 문서를 주고 받을 수 있는 min-OS의 프로그램이 실제 작동이 될 때의 환희는, 또한 C 언어로 간단한 프로그램을 작성해서, 그 프로그램을 컴파일하고 실재 그 결과가 실행이 될 때의 환희는 지금도 가슴을 설레게 만든다. 당시, 중간고사를 마치고 나면 본격적으로 시작되는 프로젝트 기간은 참으로 많은 전설을 만들어 내었다. 서로 경쟁을 하듯이, 먼동이 틀 때까지 밤을 새워 가며 코딩을 하던 동료들의 모습도 눈에 선하기만 하다.
하지만 이런 성취감과 자부심에 사로잡혀 있던 저자에게 4학년 2학기 최고의 위기가 찾아왔다. 그것은 바로 인공지능 과목에서 배우는 Prolog와 Lisp 언어 때문이었다. 지금까지 내가 배웠던, 그 어떤 언어와는 전혀 차원이 다른 언어들이었다. 특히, Lisp로 Lisp interpreter를 개발하는 프로젝트는 그 동안 저자가 구축해왔던 성취감과 자부심을 산산이 무너뜨리고 말았다. 그나마, 겨우 졸업을 할 수 있었던 것은, 수학에서 배웠던 논리학이 도움이 되기는 했지만, 언어적인 관점에서의 Prolog와 Lisp는 단순히 수학의 논리학 또는 이산수학으로 해결할 수 없는 언어였고, 저자는 이 언어 때문에 심각한 좌절감에 사로잡혀 있었다. 하지만 이런 저자에게 천운과 같은 기회가, 너무도 우연히 찾아왔다.
저자는 학부를 졸업하고, “우연히”, 대학원에 진학할 기회가 생겼다. 그리고, 대학원 첫학기에, 필수 과목인 “프로그래밍언어론” 과목에서, Carl Gunter라는 젊은 교수에게 ML이라는 새로운 언어를 배우게 되었다. 당시 저자는 ML이라는 언어가 있었다는 것을 학부과정 내내 전혀 몰랐었다.
저자는 처음으로, ML이라는 언어를 접하면서, 프로그램언어에 대한 이론적인 경험을 비로소 하게 되었다. 그리고 언어에는 다양한 언어의 유형(paradigm)이 존재하고, 그러한 언어들의 유형은 그 유형의 용도에 따라 사용될 수밖에 없다는 타당성에 대한 체계적인 체험을 하게 되었다. 이러한 경험 중, ML이 복합성, 즉 다중패러디임(multi-paradigm)의 성질을 가진 언어라는 것을, 실제 코딩을 통해서, 이해하게 되었다. 이 과정은, ML의 함수언어적인 성질, 논리언어적인 성질, 객체지향적인 성질 등의 다양한 언어의 유형을 일체적으로 이해할 수 있는 천운의 기회였다. 개인적으로 이 과정은, 이전 학부 과정에서 Prolog와 Lisp를 통해서 겪었던 좌절감을 체계적으로 극복하고, 그 이상의 질적 성장을 이룰 수 있었던 너무도 소중한 학습과 경험이었다. 아마도 ML로 Scheme interpreter를 작성하는 이 과목의 프로젝트는 내 일생의 어떤 프로젝트나 과제와는 비교할 수 없을 정도로 혁신적이었다고, 또한 도전적이었다고 평가하고 싶다 - 그리고 이 Prologue를 통해, Carl Gunter 교수에게 짐심으로 고마움을 전하고 싶다.
사실 이 이후, 30년 이상의 프로그래밍에 대한 활동은 주로 과학자와 교수라는 직업과 관련된 것들이 주된 것들이다. 실용적인 면에서는, SW재역공학에서 요구되던 SRE(Software Re/everse-engineering Environment) 도구의 구축과, 이론적인 면에서는, dTP-Calculus에 기반을 둔 SAVE(Specification, Analysis, Veirication, and Evaluation) 도구의 구축으로 정리할 수 있다. 전자는 Meta-Programming에 기반을 둔 SW 개발방법론에 대한 활동이라면, 후자는 Process Algebra 이론을 Modeling 및 분석 및 검증에 적용하기 위한 모델링 및 모의실험 방법론에 대한 활동이었다. 그리고 돌이켜, 이런 활동에 가장 큰 도움이 되었던 대표적인 경험을 제시하라고 한다면, 저자는 주저하지 않고 Carl Gunter에게 배웠던 ML에 대한 경험이라고 말할 수 있다.
아마도 이런 이유 때문이었는지는 몰라도, 전북대학교에 부임한 이후로 지금까지, “고급프로그래밍언어” 과목의 기본 언어로 ML과 더불어, 관련 언어인 Scheme과 Prolog와 Smalltalk을 가르치게 되었다. 일반적으로, Scheme과 Prolog와 Smalltalk을 개별적으로 학습하는 것은 결코 쉬운 일이 아니다. 하지만 ML과 그 다중패러다임적인 특성을 이해하고 나면, 이러한 언어를 학습하는 것이 절대 어려운 일은 아닐 수 있다. 그 이유는 당연히, ML을 통해서, 이들 언어가 가지고 있는, 패러다임적인 관점에서의 각각의 특성을 이해할 수 있기 때문이다.
이 교재의 목적도, 당연히 이런 관점에 있다. 본 교재는 ML 언어의 기본적인 특성들을 기술하고, 이를 다중패러다임적인 관점에서 해석하였다. 그리고 이를, 각 패러다임에 해당하는 대표적인 언어로 확대하여 적용하였다. 즉 ML의 기본 특성들이 어떻게 다중패러다임적인 관점에서 해석이 될 수 있는지를 각 패러다임의 대표적인 언어로 체험하도록 하였다. 이런 관점에서 ML 언어 하나를 심도 있게 학습함으로써, 다른 3가지 유형의 언어도 같이 학습할 수 있게 하였다.
이런 면에서, 이 교재는 기본적으로 학부 4학년과 대학원 1학년 수준에 맞게 조정을 하였다. 그리고, 이론적인 측면에만 치우치지 않고, 프로그램이 실제 어떻게 실행이 되는지에 대한 실기적인 측면에서도 도식적으로 상세히 기술하였다. 그 중, 가장 강조를 한 것은, 귀납법에 기반을 둔 재귀함수의 수행성에 대한 것으로, 재귀함수의 실행 과정과 단계를 절차적으로, 또한 시각적으로 상세히 기술하였다. 즉 하위언어인 assembly 언어에서의 정밀성과 정확성이 상위언어인 함수언어나 논리언어에도 절대적으로 요구되고 있음을 단계별로, 도식적인 방법을 통해서 표현하고 기술하였다. 이렇게 함으로써, 상위언어에서의 논리, 즉 알고리즘이 관련 데이터와 일체적으로 어떻게 연동해야 하는지를 구체적으로 이해할 수 있도록 했다.
이런 관점에서, 본 교재를 다음과 같이 구성하였다:
1) 제1장: 프로그램의 원리
프로그래밍언어를 정의하고, 그 유형을 HOW에 기반을 둔 절차중심 프로그래밍언어와 WHAT에 기반을 둔 비절차중심 프로그래밍언어로 구분하여 특성을 분석하였다.
프로그래밍언어의 쟁점을 알고리즘과 복잡도의 관점, 그리고 실행체계의 관점에서, 절차중심언어와 비절차중심언의 예를 들어, 기술하였다.
이를 기반으로, 기본적인 프로그래밍언어의 원리와 개념들을 정리하였다.
2) 제2장: 절차중심언어
Pascal과 C를 중심으로 절차중심 프로그램언어의 정의 및 특성을 정리하였다.
C와 Pascal 언어를 중심으로 언어의 구성 요소, 구조 및 제어들을 정리하였다.
절차중심언어의 함수와 프로시저의 정의, 실행 및 적용에 대해 정리하였다.
3) 제3장: ML - 다중패러다임 프로그래밍언어
ML의 기본 특성 및 요소에 대해 기술하였다.
ML의 함수 개념과 high-order 함수의 개념을 기술하였다.
특히, Curried 함수와 partial instantiation에 대해 기술하였다.
사용자 자료 유형과 재귀적 복합 자료유형에 대해 기술하였다.
Side-effect를 허용하는 reference와 array 방법을 기술하였다
ML의 module system인 structure와 유형인 signature에 대해 기술하였다.
Information hiding의 세 가지 방법에 대해 기술하였다.
Functor에 대해 구술하였다.
특히, high-order 함수, Curried 함수와 partial instantiation를 C로 정의하였다.
또한, ML의 재귀구조와 관련 연산을 C로 정의하였다.
ML을 함수 프로그래밍언어, 논리 프로그래밍언어 및 객체지향 프로그래밍언어의 관점에서 기술하였다.
4) 제4장: 프로그래밍언어 패러다임들
본 장에서는 세 가지 유형의 프로그래밍언어를 ML과 비교하여 기술하였다.
제4.1장: Scheme
대표적인 함수 프로그래밍언어 Scheme의 특징과 요소를 기술하였다.
특히, high-order procedure와 λ-procedure를 상세히 기술하였다.
λ-procedure를 기반으로 Church Numeral과 연산들을 상세히 기술하였다.
이를 ML과 비교하고, ML의 함수로 전환하였다.
제4.2장: Prolog
첫 번째이며, 대표적인 논리 프로그래밍언어 Prolog의 특징과 요소를 기술하였다.
특히, clause를 구성하는 fact와 inference rule을 상세히 기술하였다.
논리 실행모델과 절차 실행모델에 대해 자세히 기술하였다.
대입(substitution), 적용(application), 조합(composition), 통합(Unification) 등의 기본 개념을 상세히 기술하였다.
예제를 통해서, 특정한 질의(query)가 어떻게 만족(satisfied)이 되는지를 절차적 실행모델에 기반하여, 도식적으로 상세히 기술하였다.
이를 ML과 비교하고, ML의 함수로 전환하였다.
제4.3장: Smalltalk
첫 번째 객체지향 프로그래밍언어로 알려진 Smalltalk의 특징과 요소를 기술하였다.
Smalltalk의 모든 요소들, 즉, value, name, expression들이 object임을, if-수식, while-수식 및 iteration도, 심지어는 class도 객체임을 기술하였다.
이를 통해, 다른 객체지향언어에 비해, 객체지향도(object-oriented-ness)가 높음을 입증하였다.
이를 ML과 비교하고, ML의 Structure로 전환하였다.
저자는, 컴퓨터과학 분야에 존재하는 많은 프로그램언어 이론서들의 형식을 따르지 않았다. 본 교재는 앞에서 거론한 바와 같이, assembly 언어에서 요구되는 수준의 정밀성과 정확성을 다중패러다임 프로그래밍언어인 ML을 중심으로, 각 프로그래밍언어 패러다임의 대표 언어인 Scheme, Prolog 및 Smalltalk에서도 요구됨을 각 언어의 의미론적 형식에 준하여 도식적인 방법으로 표현하고 기술하고자 하였다.
저자는 앞으로, 전북대학교에서, “고급프로그래밍언어” 과목을, 언제까지, 어떻게, 강의할 지는 모르겠다. 다만 과거 25년 동안 저자의 수업을 받았던 학생들에게, 본인들이 받았던 강의 주제와 내용 및 예시들이, 기본적으로 이러한 교재의 구조와 내용에 있었다는 것을 이해할 수 있는 조그만 계기가 되기를 진심으로 바랄 뿐이다.
이 교재가 나오기까지, 자료를 정리할 수 있도록 도움을 준 송준섭 학생에게 진심으로 감사의 마음을 전한다. 그리고 이 저서는 2019년도 전북대학교 저술장려 지원에 의하여 연구되었으며, 그리고 이런 출판의 기회를 준 전북대학교 출판문화원에 감사를 표한다.
2021년 1월 1일
화산(華山)의 석양 앞에서
저자 이문근
Prologue
This textbook is the final product that I re-organized, with supporting materials, from the lecture notes for the“Advanced Programming Languages” in the department of computer science and engineering at Jeonbuk National University in Korea since 1996.
While developing the materials for the textbook, there were some thoughts that I could not get rid of. Among the thoughts, there were two most critical ones: 1) the inner blame why I had been so indifferent for systematic and theoretical study for such languages in the book so a long time, and 2) the regret why I had not published this kind of the book earlier far years before. The reason for the blame and the regret is as follows.
The time for me to attract to programming was about the second semester of the junior year at Penn State when I was learning Assembly Languages. Vividly, if I recall, it was about the time when I was performing the final project for the course by constructing sort, search, and other operations using binary trees with the IBM3070 assembly language, instructed by a middle-aged lady professor from IBM. The project provided me with a chance to realize how critically important the correctness of the computing systems, as well as how admiral such systems were. Not allowing a “bit” of error for the operations at the registers and memory of the IBM 3070 computer, represented in the assembly language was so valuable experience. The situation that I had to reflect the proper size and locations of the inputs and output for the recursive functions using the operation on the binary trees by calculating the exact sizes and locations of all the data with respect to the definition of their structures allowed me to feel some unmeasurable and incomprehensible achievement that I could not obtain from other projects in other courses.
The experience of performing the project with the assembly language in the course provided me with some sort of sound ability and solid confidence to perform successfully the highly challenging projects of Operating Systems (OS) and Compiler at Penn State in the following first semester of the senior year. Especially, both the OS project using the fork system function and the socket and pipe communication mechanisms to develop a mini OS for an editor for multiple concurrent users and the Compiler project using Lex and Yacc to develop a mini C Compiler made me feel such ability and confidence in pride as some kind of the achievement. I still have the felling of joy, with my heart, getting from the moment of executing properly, as planned, at the end of the OS project, the C/Unix program that two users logged in at two independent terminals concurrently and were able to exchange texts and documents each other, and from the moment of executing properly, as planned, the Yacc/Lex program that a simple C program was compiled and executed on Unix as expected.
We made a number of legends for such moments in the computer labs during the competitive project periods on the campus, mostly, after the mid-term exams. I still canimagine the colleagues, including myself, at the computer labs, who had spent nights until dawns in competition while coding such programs.
However, I in such a pride encountered the most difficult time in the university during the second semester of the senior year, which was caused by Prolog and List in the AI course at Penn State. The languages were totally different from those I had learned before the semester. Especially the achievement and the pride I got from the previous projects were totally destroyed by a single project to develop a Lisp interpreter with List language itself, in the course.
I barely was able to finish the course for graduation with the inductive reasoning learned from some mathematical courses, but I was so suppressed and distracted due to the fact that there were such languages, like Prolog and List, that I could not perform the project throughly even with understanding of Logic and Descret Mathematics. However a chance to overcome the problem came to me unexpectedly like an heavenly opportunity.
I had a chance to go to a graduate school, that is, Moore School at Penn, after graduation from Penn State. And I had a chance to learn a new language, namely, ML, from a young professor at the “Theory of Programming Languages” course. Until that time, I did not have any knowledge of the ML language at all.
I am sure that I had the first experience of learning the programming languages in the theoretical perspective from ML at Penn. And I learned, as a systematic and structural experience, validity that there are a set of different language paradigms and that the languages of the paradigms are due to be used for the purpose of the paradigms. Among the experiences, I could understand the linguistic complexity of ML, from the actual coding, that is, performing a heavy loaded project, that ML is of multi-paradigms. This experience provided me with a so valuable opportunity to comprehend the functional, logical and the object-oriented paradigms of ML in terms of linguistic perspective of the programming languages. Personally the opportunity became the academic foundation and actualization that I could overcome systematically and structurally the suppression and depression I had gotten from the Prolog and Lisp languages in the AI course during my last semester at Penn State. I am sure that the final project of the Theory of Programming Languages of developing a Scheme Interpreter with ML was the most innovative, as well as, the most challenging project I ever experienced up to the present time – and I truly expressed my sincere gratitude to Prof. Carl Gunter through this Prologue.
After this period of the experience, actually, my programming activities over 30 years were, mainly, related to and with those of a scientist and a professor in profession. Those can be summarized to be of developing the SRE (Software Re/everse-engineering Environment) tool in the field of the SW Re/Reverse Engineering in the practical perspective, and the SAVE (Specification, Analysis, Verification and Evaluation) tool based on dTP-Calculus in the field of the SW Forward Engineering in the theoretical perspective. If we consider that the former was a kind of an activity for a SW development methodology based on Meta-Programming, the latter can be considered to be a kind of an activity for a modeling and simulation methodology which can be applied to modelling, analysis and verification of computer systems and theis software with the Process Algebra theory. And, if I recall, I can say, without any hesitation, that the most valuable and helpful experience that I got for the activities is the experience of ML I learned from Prof. Carl Gunter.
Perhaps, because of the experience, I used to teach ML as a primary language, supported by the related languages, such as, Scheme, Prolog and Smalltalk, in the “Advanced Programming Languages” course in Jeonbuk University since 1996 up to the present. In general, it is not easy to learn Scheme, Prolog and Smalltalk independently. However, it is not difficult to learn these languages after learning the ML language in respect to its multi-paradigms perspective. The reason for such a convenience is that the main characteristics of these languages can be comprehended in the perspective of the multi-paradigms perspective of the ML language.
Definitely, the goal of this textbook is on this perspective. The textbook shows the basic features of the ML language and interprets them in the perspective of the multi-paradigms. And it also extends the interpretation and applies the extended to the representative language of each paradigms. That is, it is allowed to experience how the basic features of the ML language can be interpreted to the representative languages of each paradigms in the perspective of the ML’s multi-paradigm. In this perspective, three different types of languages can be studied and learned at the same time while learning a main language, that is, ML, throughly.
In this objective, the book was leveled to be suitable for the Senior and Master students. And, with the balance to the theory, it is also throughly descried how the actual programs of ML and its related languages are executed step by step in the pictorial representation. Among these, the most emphasis was made on the execution of the recursive function based on inductive definition by describing their execution processes and steps in the pictorial and diagrammatic representations. That is, it is represented in the pictorial method that the correctness and preciseness from the underneath assembly languages are absolutely also required at the higher level of the functional and logical languages. With such representation, the book made it understandable concretely how the logic, that is, algorithms at the higher languages are integrated with their related data, as well as their structures, at the lower level, as one.
The book was organized as follows in this perspective:
1) Chapter 1: Principle of Programming
The notion of the programming languages is defined, and the types of the languages are classified into two groups: 1) the procedural languages based on the “how” approach, and 2) non-procedural ones based on the “what” approach. The issues in the principle are described in the perspectives of algorithms, their complexities, and execution structures, with the example of both the procedural and the non-procedural types of the languages. From the issues, the basic principles and related concepts of the programming languages are defined.
2) Chapter 2: Procedural Languages
The notion and basic characteristics of the procedural languages are defined with respect to Pascal and C. The basic elements, structures and controls of the languages are described with respect to Pascal and C. The definition, execution and application of the functions and procedures of the procedural languages are described.
3) Chapter 3: ML – Multi-Paradigm Programming Languages
The basic characteristics and elements of ML are described. The concepts of the basic function and the high-order function of ML are described. Especially, the curried function and the partial instantiation are described. The user-defined data structure and the recursive composite data structure are described. The reference and array methods to allow side-effect are described. The structure for the ML’s module system, that is, signature, is described. Three methods for the information hiding in ML are described. The basic definition and examples of the functor in ML are described. Especially, the high-order function, curried function and the partial instantiation in ML are represented in C for their definitions. In addition. the recursive structures and their related operations are represented in C, too. ML is also analyzed theoretically in order to describe ML itself in the perspectives of the functional, logical and the object-oriented programming languages.
4) Chapter 4: Paradigms of Programming Languages
Three types of the programming languages are described with respect to ML.
4.1) Section 4.1 Scheme
The basic characteristics and elements of Scheme, which is one of the best known and the most representative functional languages, are described in this section. Especially, the high-order procedure and the λ-procedure are described in detail. The Church Numerals and their related operations are represented in detail as examples, based on the λ-procedure. In addition, the numbers and operations are compared with ML and are converted into the ML functions.
4.2) Section 4.2: Prolog
The basic characteristics and elements of Prolog, which is the first logical language designed for Artificial intelligence, are described in this section. Especially, the fact and the inference rules as clause are described in detail. The logical execution model and the procedural execution model are described in detail in comparison. The basic definitions of the Substitution, Application, Composition, Unification of Prolog are described in detail. Through examples, it is described in the pictorial representation in detail how the specific query is satisfied based on the procedural execution model.
4.3) Section 4.2: Smalltalk
The basic characteristics and elements of Smalltalk, which is the first object-oriented language designed tp model real world, are described in this section. It is described that the basic elements of Smalltalk, that is, value, name, expression, etc., are objects, as we as that if-expression, while-expression and iteration, even class, are, too. Through the notions with the examples, it is shown that Smalltalk is very highly object-oriented compared to other ones, such as, C++, Java, etc.
I, as the author of the book, did not follow the basic structure of most of the programming language textbooks in the field of Computer Science.
As stated in the beginning of the prologue, I tried to demonstrate, in the pictorial representation, that the linguistic preciseness and correctness are required for each representative paradigm languages, that is, Scheme, Prolog and Smalltalk, in the perspective of the multi-paradigms programming language of ML, as shown that the preciseness and correctness were definitely required for the assembly language.
I am not sure how long, as well as, in which manner, I am going to conduct the lectures for the Advanced Programming Languages”course in Jeonbuk National University. However, simply, I really wish that there will be some moment, in the future, for the students who took the course for last 25 years to realize that the materials for the lectures of the course were basically and fundamentally based on those of this textbook.
I truly thanks Junsup Song for supporting me to collect some lecture materials for the book to be published in this form. In addition, I want to expression my gratitude to the JBNU Press for providing me the opportunity to publish the book as the 2029 Publication Supporting Project of JBNU.
1 Jan 2021
In the front of the sunset at the Hwa Mountain in Jeonju
Prof. Moonkun Lee
Division of Computer Science and Engineering
School of Engineering
Jeonbuk National University, South Korea