title: 编程语言概述 layout: true <!-- .bottom-bar[ {{title}} ] --> <style> .left-column { width: 50%; float: left; } .left-column h2:last-of-type, .left-column h3:last-child { color: #000; } .right-column { width: 50%; float: right; padding-top: -10em; } </style> --- class: impact # {{title}} ## 郭 鸣 ## 计算分院 ### guom@hzcu.edu.cn ### 13989879111 ### v.20 --- # 目录 ## 引言 ## 编程语言历史 ## 编程语言学习 --- ## Tower of Babel  --- ## 如此多语言 如何学习 ## [主要语言列表](https://www.levenez.com/lang/lang_letter.pdf) > 每个都学学?? --- ## 领域 思考方法 > 时间 空间 考查 语言的**历史** - 发展脉络 考查 语言的**分类** - 编程范式 --- # 编程语言历史 ## 前传 .left-column[ - Charles Babbage’s 差分机 (1830s & 40s) 英国人 - 机械计算机 - Ada Lovelace 第一个程序员 - 伯努利数列程序 - 程序--->卡片 ] .right-column[   ] --- ## 第一台电子计算机 - Konrad Zuse 德国人 - Z3 1941 - 第1台 图灵完备的**电子**计算机 .right-column[  ] `ENIAC` vs `ABC` --- ## Konrad Zuse The 1940s - in Germany in isolation `because of the war` - defined `Plankalkul` (program calculus) circa 1945 but never implemented it - Wrote `algorithms` in the language, including a program to `play chess` - His work finally published in 1972 --- ## Plankalkul notation ```java A(7) := 5 * B(6) | 5 * B => A V | 6 7 (subscripts) S | 1.n 1.n (data types) ``` - Included some advanced `data type` features such as - `Floating point`, used two's complement and hidden bits, nested `Records`, `Arrays` --- ## 冯·诺依曼 Von Neumann 1944 led a team that built computers with `stored programs` and a `central processor` `ENIAC` was programmed with `patch cards`  数学家，业余贡献 --- ## Machine Codes 机器码 (40’s) initial computers were programmed in `raw machine codes` These were entirely `numeric` What was wrong with using machine code? **Everything!** - Poor `readability` - Poor `modifiability` - Expression coding was `tedious` - Inherit deficiencies of `hardware`, e.g., **no** `indexing` or `floating point numbers` ---  --- ## 第一个编程语言-汇编语言 (1949) • Pseudocodes: interpreters for `assembly language` • Short Code or `SHORTCODE` - John Mauchly, 1949. • Pseudocode interpreter for math problems, on Eckert and Mauchly’s `BINAC` and later on `UNIVAC I and II`. • Possibly the `first attempt` at a `higher level language`. • Expressions were coded, left to right, e.g.: ```java X0 = sqrt(abs(Y0)) 00 X0 03 20 06 Y0 ``` • Some operations: ```java 01 – 06 abs 1n (n+2)nd power 02 ) 07 + 2n (n+2)nd root 03 = 08 pause 4n if <= n 04 / 09 ( 58 print & tab ``` --- ## 第一个高级语言 Fortran (1954-57) • `FOR`mula `TRAN`slator • Developed at IBM under the guidance of `John Backus` primarily for `scientific, computational` programming • Dramatically `changed forever the way `computers used • Has continued to evolve, adding new features & concepts. FORTRAN II, FORTRAN IV, FORTRAN66, FORTRAN77, `FORTRAN90` • Always among the` most efficient compilers`, producing fast code - 高效编译器 科学计算 --- ## John Backus  提出`描述`编程语言的语法 `BNF范式` --- ## Fortran 77 Examples ```java C Hello World in Fortran 77 C (lines must be 6 characters indented) PROGRAM HELLOW WRITE(UNIT=*, FMT=*) 'Hello World' END PROGRAM SQUARE DO 15,I = 1,10 WRITE(*, *) I*I 15 CONTINUE END ``` --- ## Fortran 0 and 1 FORTRAN 0 – 1954 (not implemented) FORTRAN I - 1957 Designed for the new `IBM 704`, which had `index registers` and `floating point hardware` Environment of development: Computers were `small and unreliable` Applications were `scientific` **`No`** programming `methodology or tools` Machine `efficiency` was most important Impact of environment on design •  No need for `dynamic storage` •  Need good array handling and counting loops •  `No string handling`, decimal arithmetic, or powerful input/ output --- ## Fortran I Features •  Names could have up to `six characters` •  Post-test counting `loop` (DO I=1, 100) •  `Formatted` I/O, User-defined `subprograms` •  Three-way selection statement (arithmetic `IF with GOTO`) IF (ICOUNT-1) 100 200 300 •  Implicit data typing statements variables beginning with `i, j, k, l, m` or `n` were `integers`, all else `floating point` •  Programs larger than` 400 lines` rarely compiled correctly, mainly due to `poor reliability` of the 704 •  Code was `very fast` •  No separate compilation •  Quickly became `widely used` --- ## Fortran 90 (1990) Added many `features` of more `modern` programming languages, including •  `Pointers` •  `Recursion` •  `CASE` statement •  Parameter `type checking` •  A collection of `array operations`, DOTPRODUCT, MATMUL, TRANSPOSE, etc •  `dynamic allocations` and deallocation of arrays •  a form of `records` (called derived types) •  `Module` facility (similar Ada’s package) --- ## COBOL • `CO`mmon `B`usiness `O`riented `L`anguage • Principal mentor: (Rear Admiral Dr.) `Grace Murray Hopper` (1906-1992) • Based on FLOW-MATIC which had such features as: • Names `up to 12 characters`, with embedded hyphens • `English names` for arithmetic operators • Data and code were completely separate • `Verbs` were first word in every statement • `CODASYL committee` (Conference on Data Systems Languages) developed a programming language by the name of COBOL --- ## Grace Murray Hopper  COBOL --- ## COBOL First CODASYL Design Meeting - `May 1959` `Design goals`: • Must look like `simple English` • Must be `easy to use`, even if that means it will be less powerful • Must `broaden` the base of computer users • Must not be biased by current compiler problems Design committee were all from computer `manufacturers and DoD branches` Design Problems: arithmetic expressions? subscripts? Fights among manufacturers --- ## COBOL Example ```java IDENTIFICATION DIVISION. PROGRAM-ID. HelloWorld. AUTHOR. Fabritius. ENVIRONMENT DIVISION. CONFIGURATION SECTION. INPUT-OUTPUT SECTION. DATA DIVISION. FILE SECTION. WORKING-STORAGE SECTION. LINKAGE SECTION. PROCEDURE DIVISION. DISPLAY "Hello World". STOP RUN. ``` --- ## LISP (1959) •  LISt Processing language (Designed at MIT by `John McCarthy`) •  AI research needed a language that: •  Process data in `lists` (rather than arrays) •  `Symbolic` computation (rather than numeric) • First `GC`, First `metacircular interpreter` •  One universal, recursive data type: the `s-expression` •  Syntax is based on the `lambda calculus` •  Pioneered `functional programming` •  No need for variables or assignment •  Control via `recursion` and conditional expressions •  Still` the dominant language for AI` •  `COMMON LISP` and `Scheme` are contemporary dialects •  ML, Miranda, and Haskell are related languages --- ## John Mccarthy McCarthy was one of the founders of the discipline of `artificial intelligence`. He `coined` the term "artificial intelligence" (AI), developed the `Lisp programming language` family, significantly influenced the design of the ALGOL programming language, popularized `timesharing`.  AI, Lisp, timesharing, Garbage Collector --- ## LISP Examples ```s (print "Hello World") (defun fact (n) (if (zerop n) 1 (* n (fact (1- n))))) (format t “factorial of 6 is: ~A~%" (fact 6)) (defun print-squares (upto) (loop for i from 1 to upto do (format t "~A^2 = ~A~%" i (* i i)))) ``` --- ## Algol 1958 Environment of development: 1.  FORTRAN had (barely) arrived for IBM 70x 2.  Many other languages were being developed, all for specific machines 3.  No `portable language`; all were machine dependent 4.  No `universal language` for communicating algorithms four days for design, `Goal` of the language: 1. Close to `mathematical notation` 2. Good for `describing algorithms` 3. Must be translatable to machine code --- ## Algol 60 Modified ALGOL 58 at 6-day meeting in Paris adding such new features as: • `Block structure` (local scope) • `Two parameter passing `methods • Subprogram `recursion` • `Stack-dynamic` arrays • Still no i/o and no string handling Successes: • It was the standard way to publish algorithms for over 20 years • `All subsequent imperative languages` are based on it • `First machine-independent` language • First language whose ` syntax was formally defined` `(BNF)` --- ## Algol 60 Examples ```java 'begin' --Hello World in Algol 60 outstring(2, 'Hello World'); 'end' 'begin' 'comment' Squares from 1 to 10 'integer' I; 'for' i := 1 'step' 1 'until' 10 'do' 'begin' outinteger(2,i*i); 'end' --for 'end' --program ``` --- ## APL late 1950’s • designed by K.Iverson at Harvard in late 1950’s • `A` `P`rogramming` L`anguage • A language for programming `mathematical computations` especially those using `matrices` • Functional style and many whole `array operations` • Drawback is requirement of **`special keyboard`** --- ### APL keyboard  --- ## The 1960s: An Explosion in PL • The development of hundreds of programming languages • `PL/1` designed in 1963-4 –  supposed to be `all purpose` –  `combined features` of FORTRAN, COBOL and Algol60 and more! –  `translators` were slow, huge and unreliable –  some say it was `ahead of its time`...... • Algol68 • SNOBOL • Simula • BASIC --- ## PL/I (1963) PL/I contributions: 1. First unit-level `concurrency` 2. First `exception` handling 3. `Switch-selectable` recursion 4. First `pointer` data type 5. First array `cross` sections Comments: • `Many new `features were poorly designed • `Too large` and too complex • Was (and still is) actually used for both scientific and business applications • Subsets (e.g. PL/C) developed which were more manageable --- ## Simula (1962-67) •  Designed and built by Ole-Johan Dahl and Kristen Nygaard at the Norwegian Computing Centre (NCC) in Oslo between 1962 and 1967 •  Originally designed and implemented as a language for `discrete event simulation` •  Based on ALGOL 60 Primary Contributions: •  `Coroutines` - a kind of subprogram •  `Classes` (data plus methods) and `objects` •  `Inheritance` •  `Dynamic binding` => Introduced the `basic ideas` that developed into ` object oriented `programming. --- ## Ole-Johan Dahl and Kristen Nygaard  Simula --- ## BASIC (1964) •  `Beginner`'s All purpose Symbolic Instruction Code •  Designed by Kemeny & Kurtz at `Dartmouth` for the GE 225 with the `goals`: • `Easy to learn` and use for non-science students and as a path to Fortran and Algol • Must be `“pleasant` and friendly” • Fast turnaround for homework • `Free` and private access • `User time is more important` than computer time •  Well suited for implementation on `first PCs` (e.g., **`Gates`** and Allen’s `4K Basic interpreter` for the MITS Altair personal computer (circa `1975`) •  Current popular dialects: Visual BASIC --- ## BASIC Examples ```java PRINT "Hello World" FOR I=1 TO 10 PRINT I*I; NEXT I ``` --- ## Bill Gates Altair 8800 (MITS),`BASIC interpreter`, over the course of a `few weeks` they developed an `Altair emulator` that ran on a minicomputer, and then the `BASIC interpreter`. `February 1976`, Gates wrote an `Open Letter` to Hobbyists in the MITS newslette. 开启了`软件产业`的时代. --- ## Bill Gates  BASIC, Windows --- ## The 1970s: Simplicity,Abstraction, Study • Algol-W -` Nicklaus Wirth` and `C.A.R.Hoare` –  reaction against 1960s –  simplicity • Pascal –  small, simple, efficient structures –  for `teaching` program • C - 1972 - `Dennis Ritchie` –  aims for `simplicity` by reducing restrictions of the type system –  allows `access to underlying system` –  interface with O/S - `UNIX` --- ## Pascal (1971) • Designed by `Wirth`, who `quit the ALGOL 68 committee` (didn't like the direction of that work) • Designed for teaching `structured programming` • ` Small`, `simple` • Introduces some modest improvements, such as the case statement • Was `widely used for teaching` programming ~ 1980-1995. --- ## Nicklaus Wirth  p-code, Pascal, Compiler --- ## C (1972-) • Designed for `systems programming` at `Bell Labs` by `Dennis Richie` and `Ken Thompson` • Evolved primarily from` B`, but also `ALGOL 68` • Powerful set of operators, but` poor type checking` • Initially spread through `UNIX` and the availability of` high quality, free c`ompilers. --- ## Dennis Richie, Ken Thompson  B,C,Unix,ed,Plan9,UTF-8,Go C, Unix --- ## Smalltalk (1972-80) • Developed at Xerox PARC by` Alan Kay` and colleagues (esp. Adele Goldberg) inspired by Simula 67 • First compilation in 1972 was written on a bet to come up with "the `most powerful language` in the world" in `"a single page of code"`. • In 1980, Smalltalk 80, a uniformly `OO object-oriented` programming environment • Pioneered the `GUI graphical user interface `everyone now uses • First `IDE`, ideas learned by Apple --- .left-column[ ## Alan Kay  pioneering work on `OO` object-oriented programming and windowing graphical user interface design `GUI`, Concepts of `Notebook` ] .right-column[ ## dynabook  ] --- ## Xerox PARC - 激光打印机 - 面向对象编程（OOP）/ Smalltalk - 个人计算机 - 以太网（Ethernet）/ 分布式计算 - 图形用户界面（GUI）/ 鼠标 / 所见即所得（WYSIWYG）    --- ## C++ (1985) • Developed at Bell Labs by `Stroustrup` • Evolved from `C` and `SIMULA 67` • Facilities for `object-oriented programming`, taken partially from SIMULA 67, added to C • A `large` and `complex` language, in part because it supports `both procedural and OO programming` • Rapidly grew in popularity, along with OOP --- ## Stroustrup  C++ programming language --- ## Java • Developed at `Sun` in the early 1990s with original goal of a language for `embedded` computers • Principals: `Bill Joy`, `James Gosling`, Mike Sheradin, Patrick Naughton • Original name, `Oak`, changed for copyright reasons • Based on` C++ `but significantly simplified • Supports only OOP • Has references, but `not pointers` • Includes support for `applets` and a form of `concurrency` --- ## Bill Joy, James Gosling   Java --- ## JavaScript • influenced by programming languages such as `Self` and `Scheme`. • Initially only implemented` client-side in web` browsers • As a multi-paradigm language, JavaScript supports` event-driven`, `functional`, and `imperative` (including object-oriented and prototype-based) programming styles. • design by `Brendan Eich` in 10 days • Strong outward similarities between JavaScript and Java, including language name, syntax, and respective standard libraries, • the two languages are distinct and `differ greatly` in design; --- ## Brendan  JavaScript --- ## 编程语言入门 ## 简单 > Language is `Simple` ## 困难 > Language is `Simple` ====> **`Syntax`** > What's really **`hard`** is the **`Concepts and Ideas`** --- ## Concepts & Ideas behind C - 对机器硬件的低级抽象 `*p &a` - 伪装为高级语言的 汇编语言 `struct` - 内存地址 `p++` - 预编译 `#include <stdio.h>` - 程序加载,入口 `int main()` - C运行时,链接 `printf()` - Shell环境 `return 0` - 字符数组/整型数组 `\0` null terminated string > **Too Much** Overhead! > 没有对`机器硬件和系统底层`的充分认识,不能说学会了**`C的本质`** > 理解C`语法` < > 理解C的`本质` --- ## fundamental concepts - syntax vs. semantics • names vs. values - interface vs. implementation - environment vs. store • continuations - compilation vs. evaluation - types • invariants • modules - macros and meta-programming tools - abstractions for concurrency and distribution [Programming languages: fundamental concepts for expanding and disciplining the mind ](https://cn.bing.com/academic/profile?id=1b26933de3c60f63c7bfe068ec8052d6&encoded=0&v=paper_preview&mkt=zh-cn) --- ## 入门编程语言推荐 ### 入门编程教授 `编程思想`为主 ### `C`**不是**一个好的`入门`语言 > 个人观点 供参考 --- ## C vs. Java vs. Python ## 对立的观点?? ### 高等教育之特点 > 毕业之后应具备 ### 批判思维能力 ### 自主学习能力 --- ## 入门编程语言推荐 ### Scheme - 书籍 - Sketchy Lisp - How To Design Programs - 工具 - DrRacket, 选`R5RS` --- ## 推荐 ### Python - 书籍 - `像计算机科学家那样思考` python版 - 编程零基础入门 👍 - 工具 - ptpython - 先安装官方 python - 运行命令 > pip install ptpython -i https://pypi.douban.com/simple --- class: impact # {{title}} ## 郭 鸣 ## 计算分院 ### guom@zucc.edu.cn ### 13989879111 --- ## 序言 - 元知识 ### 如何 “学习编程” ### 知识 元知识 ### 学习 如何学 --- ## 序言 ## 深度 ### 表面现象 ===> 原理本质 ## 广度 ### 单维度 ===> 多维度 ## 高度 ### 局部 ===> 整体 --- ## 序言 ## 职业技术 ### 熟练操作 ## 专业人士 ### 追溯原理 --- ## 序言 ## 大学四年 ## 合格的专业人士 ？？？ --- ## 序言 ## 深入了解 学科本质 ## 探索发现 基本原理 ## 体验感受 计算之美 # 真 --- 美 -- # 善 --- ## 序言 ## 没有捷径 ---- Euclid（欧几里得） ### There was no royal road to geometry(Computer Science). --- ## 序言 ## 但是 ## -- ## 正确的路径很重要 !!! --- ## 序言 - 学习层次 |层次|范围|本质|期限|举例| |-|-|-|-|-| |**道**| 普适| 原理、边界Why|**永远**|图灵机，算法复杂性，图论，香农定理，逻辑| |**法**| 特定领域|基本原则How|**长期**|七层模型、**编程范式**、设计模式、快速排序，哈希表| |**术**|具体场景|最佳实践How-to|**经常变化**|流行的语言 ，技术，框架Kotlin/Spark/Vue/Nosql，具体实现| - 计算机专业 - 须将主要精力放到 **`道 法`** 层面 - 虽然较困难，但是有**内在的**乐趣 ===> 少数人 --- ## 课程体系 - 理论基础 `计算理论` `数理逻辑` - 专业基础 算法 数据结构 - **专业核心** 计算机系统 操作系统 编程语言与编译 `分布式系统` - 专业核心 计算机网络 数据库系统原理 - 应用领域 图形图像 物联网 嵌入式系统 移动计算 人机交互技术 软件工程 计算机安全 大数据 人工智能... (计算机,偏应用类,`未开课,请自学`) --- ## 编程语言本质 ### 程序 - **计算模型** ===> 解决特定领域问题 ### 编程语言 - **计算模型**的描述机制 --- ## 描述机制 ### **多样性** ## 核心本质 ### 内在**一致性** --- ## 编程语言范式 |计算模型|编程范式|代表语言|经典实现| |:-|-|-|-| |图灵模型|命令式|Algol/C|Gcc/Clang| | 消息传递|对象式 |Smalltalk|Pharo| | **Lambda 算子**|函数式 |Lisp/ML|Racket/Ocaml| | 形式逻辑,Unification|逻辑式 |Prolog|SWI-prolog| - 实际语言可能**`混合`**多种范式 - 较独特的语言：Forth,Io,Rebol,Factor... - 以上为主要范式,其他还有声明式,数据流... - 参考 [wikipedia](https://en.wikipedia.org/wiki/Programming_paradigm#/media/File:Programming_paradigms.svg) --- ## A Brief Chronology 年表 - Early 1950s “order codes” (primitive assemblers) - 1957 `FORTRAN` the first high-level programming language - 1958 `ALGOL` the first modern, imperative language - 1960 `LISP` First MetaCircular Interpreter, interactive programming - 1960 `COBOL` Business programming - 1962 `APL`, SIMULA the birth of OOP (SIMULA) - 1964 `BASIC` Language for Beginner - 1964 `PL/I` Large and complex, many new feature,concurrency,exception - 1966 `ISWIM` first modern functional language (a proposal) - 1970 `Prolog` logic programming is born - 1972 `C` the systems programming language - 1974 `SQL` Domain-specific language used in RDBMS - 1975 `Pascal`, Scheme two teaching languages - 1978 `CSP` Concurrency matures --- ## A Brief Chronology 年表 - 1978 `FP` Backus’ proposal - 1983 `Smalltalk-80`, `Ada` OOP is reinvented - 1984 `Standard ML` FP becomes mainstream (?) - 1986 `C++`, `Eiffel` OOP is reinvented (again) - 1988 `CLOS`, `Oberon`, `Mathematica` - 1990 `Haskell` FP is reinvented - 1990s `Perl, Python, Ruby, JavaScript` Scripting languages become mainstream - 1995 `Java` OOP is reinvented for the internet - 2000 `C#` - 2009 `Go Rust Pony` 新的系统编程语言 - `DSL` 硬件设计,嵌入式系统,大数据处理,人工智能 --- ## 范式 paradigms [paradigms](paradigms.png) [Concepts, Techniques, and Models of Computer Programming CTM](http://ctm.info.ucl.ac.be/) --- ## 范式 paradigms ### 介绍不同范式代表性语言 ### 语言的简单Demo --- ## 命令式/过程式 语言 - Fortran 1957 first high level,scientific computing - **Algol** 1960 `many inovation`,block,recursion,stack,dynamic array - C 1972 system programming - Pascal 1975 CS education - C++ 1986 system programming - Java 1995 enterprise app C++? Java ? ==> not `native OO` - `C with Class` --- ## Algol The Algol-like programming languages evolved in parallel with the LISP family of languages, beginning with Algol 58 and Algol 60 in the late 1950s. The main characteristics of the` Algol family` are: - the familiar `semicolon-separated` `sequence of statements`, - `block structure`, - `functions` and `procedures`, and - `static typing` --- ## Algol innovations - Use of `BNF` syntax description. - `Block` structure. - `Scope rules` for local variables. - Dynamic lifetimes for variables. - `Nested` if-then-else expressions and statements. - `Recursive` subroutines. - Call-by-value and call-by-name arguments. - Explicit `type declarations` for variables. - Static typing. - Arrays with `dynamic` bounds. ### ALGOL IS DEAD BUT ITS DESCENDANTS LIVE ON! - Ada, C, C++, Java etc. --- class: impact ## Demo start --- ## C ```c int factorial(int n) { int result = 1; for (int i = 1; i <= n; ++i) result *= i; return result; } ``` [demo](http://rosettacode.org/wiki/Factorial#Iterative_16) --- ## Java ```java public static long fact(final int n) { if (n < 0){ System.err.println("No negative numbers"); return 0; } return (n < 2) ? 1 : n * fact(n - 1); } ``` [demo](http://rosettacode.org/wiki/Factorial#Recursive_35) --- ## 函数式语言 - `lambda calculus`(Church, 1932-33) early model of computation that has deeply influenced programming language design. - `Lisp` (McCarthy, 1960) is a language that unifies data and programs. Functions are represented as lists that resemble lambda expressions and are then interpreted or compiled. - `APL` (Iverson, 1962) is a language for manipulating arrays and arrays of arrays. Programs are built up of functional operators applied to arrays. Later languages like Mathematica owe a great deal to APL. - `ISWIM` (Landin, 1966) is a paper language design that has strongly influenced the design of functional languages like Haskell. - `ML`(Edinburgh, 1979) was designed as a `theorem-proving` meta-language, but ended up being a general purpose functional language. - `SASL, KRC, Miranda` (Turner, 1976-85) and friends introduced “lazy evaluation” to the functional paradigm. - `Haskell` (Hudak, Wadler, 1988) unified and cleaned up many of these ideas. --- ## Programming without State ### Imperative style ```java n := x; a := 1; while n>0 do begin a:= a*n; n := n-1; end; ``` ### Programs in imperative languages change **states** --- ## Programming without State ### Functional style ```java // ML fac n = if n == 0 then 1 else n * fac (n-1) ``` ### Programs in pure functional languages have **no explicit state** ### Programs are constructed entirely by composing expressions ### resembles much more the typical mathematical definition --- ## Functional Programming Languages - Imperative Programming: > Program = Algorithms + Data - Functional Programming: > Program = Functions o Functions ## What is a Program in FP? - A program (computation) is a **transformation** from input data to output data. --- ## Key features of FP 1. All programs and procedures are `functions` 2. There are `no variables or assignments` — only input parameters 3. There are no loops — only `recursive functions` 4. The `value returned` by a function depends only on the values of its parameters 5. Functions are `first-class` values --- class: impact ## Haskell Demo start --- ## Pattern Matching > specifying case-based function definitions: ```java //Haskell fac 0 = 1 fac n = n * fac (n-1) ``` ### 数学归纳法的定义 Many [demo](http://rosettacode.org/wiki/Factorial#Haskell) for factorial [try haskell](http://www.tryhaskell.org/) [haskell.org](https://www.haskell.org/) ### Thinking in Math, Every thing is expression (with some value). --- ## Lists Lists are pairs of elements and lists of elements: > [ ] — stands for the empty list > x:xs — stands for the list with `x` as the head and `xs` as the tail (rest of the list) The following short forms make lists more convenient to use > [1,2,3] — is syntactic sugar for 1:2:3:[ ] > [1..n] — stands for [1,2,3, ... n] [try haskell](http://www.tryhaskell.org/) --- ## List with Pattern Matching ```java head (x:_) = x len [ ] = 0 len (_:xs) = 1 + len xs prod [ ] = 1 prod (x:xs) = x * prod xs fac n = prod [1..n] // some demo problem in tryhaskell // try it in ghci ``` [try haskell](http://www.tryhaskell.org/) --- ## Referential Transparency A function has the property of **`referential transparency`** if its value depends only on the values of its `parameters`. > ✎ Does` f(x)+f(x)` equal `2*f(x)`? In C? Referential transparency means that **“equals can be replaced by equals”.** In a pure functional language, all functions are referentially transparent, and therefore always yield the same result no matter how often they are called. --- ## Lazy Evaluation - “Lazy”, or “normal-order” evaluation only evaluates expressions when they are` actually needed`. ```java sqr n = n * n sqr (2+5) ➭ (2+5) * (2+5) ➭ 7 * 7 ➭ 49 ifTrue True x y = x ifTrue False x y = y ifTrue True 1 (5/0) ➭ 1 // try it in ghci ``` --- ## Lazy Lists Lazy lists are `infinite data structures` whose values are generated by need: ```java from n = n : from (n+1) take 0 _ = [ ] take _ [ ] = [ ] take (n+1) (x:xs) = x : take n xs from 100 ➭ [100,101,102,103,.... take 2 (from 100) ➭ take 2 (100:from 101) ➭ 100:(take 1 (from 101)) ➭ 100:(take 1 (101:from 102)) ➭ 100:101:(take 0 (from 102)) ➭ 100:101:[] ➭ [100,101] // try it in ghci ``` NB: The lazy list (from n) has the special syntax: [n..] --- ## Higher Order Functions Higher-order functions treat other functions as first-class values that can be `composed` to produce `new functions`. ```java map f [ ] = [ ] map f (x:xs) = f x : map f xs map fac [1..5] ➭ [1, 2, 6, 24, 120] ``` ```java mfac l = map fac l mfac [1..3] ➭ [1, 2, 6] // try it in ghci ``` - NB: `map fac` is a new function that can be applied to lists: - that we can also write simply: `mfac = map fac` --- ## Anonymous functions Anonymous functions can be written as “lambda abstractions”. The function `(\x -> x * x)` behaves exactly like `sqr`: ```java sqr x = x * x sqr 10 ➭ 100 (\x -> x * x) 10 ➭ 100 ``` ### Anonymous functions are first-class values: ```java map (\x -> x * x) [1..10] ➭ [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] ``` ### 函数本身也是普通值 ===>　强大的抽象机制 --- ## Lisp - Developed in the late 1950s and early 1960s by a team led by `John McCarthy` at MIT. McCarthy described LISP as a “a scheme for representing the partial recursive functions of a certain class of symbolic expressions”. - Motivating problems: `Symbolic computation` (symbolic differentiation), logic (Advice taker), experimental programming. - Software `embedding` LISP: `Emacs` (text editor), `GTK` (Linux graphical toolkit), `Sawfish` (window manager), `GnuCash` (accounting software). - Current dialects: `Common Lisp`, `Scheme`, `Clojure`. Common Lisp is ‘most traditional’, Clojure is implemented on `JVM`. --- ## Lisp - LISP is an `expression-based` language, introduced the idea of `conditional` expressions. - `Lists` – dynamic storage allocation, hd (CAR) and tl (CDR). - Recursive functions. - `Garbage collection`. - `Programs as data`. - `Self-definitional interpreter `(LISP interpreter explained as a LISP program). The `core` of LISP is `pure functional`, but impure (side-effecting) constructs (such as SETQ, RPLACA, RPLACD) were there from the start. --- ## Scheme - Dialects of Lisp. Follows a `minimalist` design philosophy. - Created during the `1970s` at the `MIT AI Lab` `Guy L. Steele` and `Gerald Jay Sussman` - It was the first dialect of Lisp to choose `lexical scope` and the first to require implementations to perform `tail-call optimization` giving stronger support for recursive algorithms. - Support `first-class continuations`. - [SICP](https://en.wikipedia.org/wiki/Structure_and_Interpretation_of_Computer_Programs) classic book - 建议阅读[R5RS](http://www.schemers.org/Documents/Standards/R5RS/)标准 --- ## Lisp machine .left-column[ hacker from MIT, 1980s: Symbolics - general-purpose computers designed to efficiently run Lisp as their main software and programming language, usually via hardware support. - They are an example of a high-level language computer architecture, and in a sense, they were the first commercial single-user workstations. ] .right-column[ <img src="lisp.machine.jpg" alt="lisp machine" style="zoom:67%;" /> ] --- class: impact ## Lisp/Scheme Demo start --- ## Scheme ```java (define (fac n ) (if (= n 0) 1 (* n (fac (- n 1)) ))) (fac 5) ``` - [newlisp][newlisp] - [DrRacket](http://racket-lang.org/) --- ## Collatz conjecture The `Hailstone sequence` of numbers can be generated from a starting positive integer, n by: - If n = 1 then the sequence `ends`. - If n is even then `n/2 ➭ n ` - If n is odd then `(3 * n) + 1 ➭ n ` ``` 任意写出一个自然数N，并且按照以下的规律进行变换： 如果是个奇数，则下一步变成3N+1。 如果是个偶数，则下一步变成N/2。 ``` The` (unproven) Collatz conjecture` is that the hailstone sequence for any starting number always terminates. 是不是所有的正整数都符合这个规律? **尚未解决** --- ## Collatz conjecture ```scheme (define (collatz n) (if (= n 1) '(1) (cons n (collatz (if (even? n) (/ n 2) (+ 1 (* 3 n))))))) (define (collatz-length n) (let aux ((n n) (r 1)) (if (= n 1) r (aux (if (even? n) (/ n 2) (+ 1 (* 3 n))) (+ r 1))))) (define (collatz-max a b) (let aux ((i a) (j 0) (k 0)) (if (> i b) (list j k) (let ((h (collatz-length i))) (if (> h k) (aux (+ i 1) i h) (aux (+ i 1) j k)))))) ``` ``` //newlisp (print (collatz 13)) => (13 40 20 10 5 16 8 4 2 1) ``` [newlisp][newlisp] --- ## 对象式语言 - The formal programming concept of objects was introduced in the mid-1960s with `Simula 67`, a programming language designed for discrete event simulation, created by Ole-Johan Dahl and Kristen Nygaard of the Norwegian Computing Center. - `SIMULA`: The first object-oriented language. - Extremely influential as the first language with classes, objects, dynamic lookup, subtyping, and inheritance. Based on Algol 60. - `Smalltalk`: A dynamically typed object-oriented language. Many object-oriented ideas originated or were popularised by the Smalltalk group - built on Alan Kay’s idea of the Dynabook (sketch oftablet computer). http://worrydream.com/EarlyHistoryOfSmalltalk/ --- ## Basic concepts in object-oriented languages Four main language concepts for object-oriented languages: 1. Dynamic lookup. 2. Abstraction. 3. Subtyping. 4. Inheritance. --- ## Smalltalk - Extended and refined the object metaphor. - Used some ideas from SIMULA; but it was a completely new language, with new terminology and an original syntax. - Abstraction via private instance variables and public methods . - `Everything` is an object; `even a class`. - All operations are `messages` to objects. Dynamically typed. - Objects and classes were shown useful organising concepts for building an entire programming environment and system. Like Lisp, easy to build a `self-definitional` interpreter. - Very `influential`, one can regard it as an object-oriented analogue of LISP: “Smalltalk is to Simula (or Java) as Lisp is to Algol”. - Reflection, live object and IDEs,TDD,Refactor --- class: impact ## Smalltalk/pharo demo start --- ## [Smalltalk-78](https://lively-web.org/users/bert/Smalltalk-78.html)  --- ## Smalltalk Syntax on Post Card  --- ## Pharo > http://mooc.pharo.org/ --- ## Stack-based Programming - A stack-oriented programming language is one that relies on a `stack` machine model for `passing parameters`. - ` Forth, RPL, PostScript, BibTeX `style design language[1] and many assembly languages (on a much lower level). - Stack-oriented languages operate on `one or more` stacks, each of which may serve a different purpose. - Further, some stack-oriented languages operate in `postfix` or `Reverse Polish notation`, that is, any arguments or parameters for a command are stated before that command. - JVM, CLR --- ## Reverse Polish notation - postfix notation `2, 3, multiply` - Prefix notation `multiply, 2, 3 ` - Infix notation `2 multiply 3` --- ## PostScript `PostScript` “is a simple interpretive programming language ... to describe the appearance of text, graphical shapes, and sampled images on printed or displayed pages.” - dynamically typed - concatenative programming language - created at `Adobe` Systems by `John Warnock, Charles Geschke, Doug Brotz, Ed Taft and Bill Paxton` from 1982 to 1984. > display standard supported by all major printer vendors > simple, stack-based programming language > large set of built-in operators > PostScript programs are usually generated from applications, rather than hand-coded > language for driving laser printers. `Hardware interpreter` in `every` printer. --- ## The operand stack Compute the average of 40 and 60: > 40 60 add 2 div At the end, the result is left on the **`top`** of the **`operand stack`**  --- ## Procedures and Variables Define a general procedure to compute averages: `key value def` - associate key and value in current dictionary ```java /average { add 2 div } def 40 60 averag % bind the name “average” to “{ add 2 div }” ```  --- class: impact ## PostScript demo start --- ### PostScript ```java newpath % clear the current drawing path 50 50 moveto % move to (50,50) 50 100 lineto % draw a line to (50,100) 100 100 lineto 100 50 lineto 50 50 lineto 10 setlinewidth % set width for drawing stroke % draw along current path showpage % and display current page ```  [PostScript online interpreter](https://wps-sigcc.pages.dev/) [code](http://logand.com/sw/wps/) --- ## Factorial ... ```java /showFact { % n -> __ dup showInt % show n (! = ) show % ! = fact showInt % show n! } def /newline { % __ -> __ currentpoint exch pop % get current y FS 2 add sub % subtract offset LM exch moveto % move to new x y } def /Times-Roman findfont FS scalefont setfont LM 600 moveto 0 1 20 { showFact newline } for % do from 0 to 20 showpage ``` [RoPS PostScript Interpreter] (http://www.rops.org/) --- ### 逻辑式 语言 - Logic programming is a type of programming paradigm which is largely based on` formal logic`. - Any program written in a logic programming language is` a set of sentences in logical form`, expressing facts and rules about some problem domain. - Major logic programming language families include `Prolog`, Answer set programming (ASP) and Datalog. In all of these languages, rules are written in the form of clauses: > Logic Programming: Program = Facts + Rules --- ### Prolog - The language was first conceived by a group around `Alain Colmerauer` in Marseille, France, in the early 1970s and the first Prolog system was developed in `1972` by `Colmerauer with Philippe Roussel`. - Prolog was one of the `first logic` programming languages, and remains the most popular among such languages - The language has been used for `theorem proving`, `expert systems`, term rewriting, type inference, and automated planning, as well as its original intended field of use, natural language processing. - part of IBM’s `Watson` QA supercomputer were coded in Prolog --- ### Prolog A Prolog program consists of `facts, rules, and questions`: - `Facts` are named relations between objects: - `Rules` are relations (goals) that can be inferred from other relations (subgoals): - `Questions` are statements that can be answered using facts and rules: --- class: impact ## Prolog Demo start --- ### prolog ``` %facts parent(charles, elizabeth). % elizabeth is a parent of charles female(elizabeth). % elizabeth is female %rules mother(X, M) :- parent(X,M), female(M). % M is a mother of X % if M is a parent of X and M is female %query ?- parent(charles, elizabeth). ➪ yes ?- mother(charles, M). ➪ M = elizabeth <cr> yes ``` [swi-prolog][swi] --- ### prolog ``` % Factorial fact(X, 1) :- X<2. fact(X, F) :- Y is X-1, fact(Y,Z), F is Z*X. ?fact(3,F) % GCD gcd(X, 0, X):- !. gcd(0, X, X):- !. gcd(X, Y, D):- X > Y, !, Z is X mod Y, gcd(Y, Z, D). gcd(X, Y, D):- Z is Y mod X, gcd(X, Z, D). ``` [swi-prolog][swi] --- ### prolog http://www.learnprolognow.org https://swish.swi-prolog.org/ http://www.cdglabs.org/prolog/#/ http://tau-prolog.org/ --- class: impact #书籍推荐 ## 本讲座~最重要~部分 --- ### 书籍 - 原理本质    --- ### Books Scheme    --- ### Books haskell  --- ### 编程语言原理、范式   [Seven * in Seven Weeks](https://www.douban.com/doulist/168976/) --- ###编程语言原理、范式  --- ### Unix   [Cambridage CL unix course](https://www.cl.cam.ac.uk/teaching/1819/UnixTools/materials.html) --- ### 开卷有益   --- ### 开卷有益   --- ### 开卷有益   --- ### Books essay  --- ## 一些文章 - [十年学会编程 Teach Yourself Programming in Ten Years](http://www.norvig.com/21-days.html) [中文版](http://daiyuwen.freeshell.org/gb/misc/21-days-cn.htmlf) - [编程之道 The Tao of Programming](http://www.mit.edu/~xela/tao.html) [中文版](https://book.douban.com/subject/1899158/) - [10-papers](https://coderwall.com/p/vmsa0g/10-papers-every-programmer-should-read-at-least-twice-with-links) --- class: impact ## 找到心中的 真正快乐 愉快学习 ## Happy Learning Learn Happy ## 人生短暂 学海无涯 ## Life is short and art is boundless ## 确立长远格局 而不是 陷入当前细节 --- ## 参考 http://www.cl.cam.ac.uk/teaching/1617/ConceptsPL/materials.html --- ## 问题,联系方式 👂❓ ## 郭 鸣 ## 计算分院 ### 📧guom@hzcu.edu.cn ### 📞13989879111 --- ## QR code <img src="qr.png" alt="image-20231113192227306" style="zoom: 50%;" /> [thinkcs]: https://book.douban.com/subject/26870407/ [swi]: https://swish.swi-prolog.org/ [newlisp]: http://www.newlisp.org/newlisp-js/