Introduction to lisp lisp
计划 lisp介绍 函数 数据结构 java对比 1.lisp背景介绍 2.通过函数和数据抽象作为解决复杂度的重要工具 3.java8新增的lambda表达式支持和streamapi的简单对比
lisp (list processor) 第一门函数式语言 (1958~) 有很多方言 scheme、commons lisp、racket、 clojure 语法简单，括号很多 函数式编程，是一种编程范式，在任意位置定义函数、把函数当做参数、返回结果。类似数学函数的方式，对于特定的输入返回同样的结果。尽量避免修改状态和数据。 语法非常简单，几乎没有语法，非常快的入手，没有那么多的规则，更多的创造力 主要使用scheme代码，和其他方言基本思想是一致的
动机 另一种编程范式 比较有趣 为什么要去(学习)(了解)一门（新）的(语言) 函数式编程，学习不同的思想、思维方式，从中得到一些启发、灵感。 语言不仅是工具，更是思维的载体，了解另外一个世界的风格。 第二古老的语言，存在这么长时间，肯定是有很多价值的 另外，不考虑太多利益。lisp本身是非常有趣的。
(operator operand1 operand2 …) s-expression s表达式 symbolic expression 前缀表示法 在lisp中既用作代码有用作数据 每个operand可能是一个atom，或者是一个s-expression (operator operand1 operand2 …)
基本表达式 > ( + 2 3 ) 5 > ( * 1 2 3 ) 6 基本计算操作，定义变量 组合式包含组合式，递归替换求值 > ( + ( * 2 3 ) ( + 3 4 ) ) 13 > ( define foo 3 ) > ( * foo foo ) 9
> ( define ( square x ) ( * x x ) ) 定义函数 ( define ( <name> <formal parameters> ) <body>) > ( define ( square x ) ( * x x ) ) > ( square 3 ) 定义function 名称 形式参数 9 > ( define ( sum-of-squares x y ) ( + ( square x ) ( square y ) > ( sum-of-squares 4 3) 25
流程控制 (define ( abs x ) ( if ( > x 0 ) x (- x ) ) ) > (abs -1) 1 通过谓词表达式判断，还有cond > (abs -1) 1 > (abs 2) 2
( define ( plus-y y ) ( define ( plus-x x ) ( + x y ) ) plus-x ) 函数中定义函数 ( define ( plus-y y ) ( define ( plus-x x ) ( + x y ) ) plus-x ) closure闭包，包含函数的定义和当前的环境。创建了一个包含此表达式和对自由变量y的引用的闭包 表示函数体内，包含有外层函数的参数 外层函数返回时，参数的绑定被关闭了 又称lexical scoping static scoping ，在定义函数的代码位置确定变量的值。 与之相对应的是dynamic scoping。可能运行恰好遇到一个也叫y的环境。 Clojure, Common Lisp and Scheme make use of static scoping by default while Newlisp, Picolisp and the embedded languages in Emacs and AutoCAD use dynamic scoping. > ( ( plus-y 3 ) 5 ) 8
( lambda ( <formal parameters> ) <body>) λ-expression ( lambda ( <formal parameters> ) <body>) > ( ( lambda ( x ) ( * x x ) ) 3 ) 9 lambda 表达式 currying 可以将多个参数的lambda表达式转化为多个单参数的lambda 的组合 > ( ( lambda ( x y ) ( + x y ) ) 3 4) 7 > ( (lambda ( x ) ( lambda ( y ) ( + x y ) ) ) 3 ) 4) 7
函数中定义函数 ( define ( plus-y y ) ( define ( plus-x x ) ( + x y ) ) ( lambda ( x ) ( + x y ) ) )
( define ( damping f ) ( lambda ( x ) ( / ( + x ( f x ) ) 2 ) ) ) 函数作为参数、返回值 ( define ( damping f ) ( lambda ( x ) ( / ( + x ( f x ) ) 2 ) ) ) 高阶函数做抽象，输入一个过程返回一个过程，high ordered function > ( ( damping square ) 2 ) 3 ( define ( compose f g) ( lambda ( x ) ( f ( g x ) ) ) ) > ( ( compose square ( lambda ( x ) ( + x 1 ) ) ) 5 ) 36
数据结构 ( cons 1 2 ) > ( cons 1 2 ) 2 ‘(1 . 2) construct pair序对，的car cdr 可以是atom也可以是序对,嵌套递归定义。如同lisp代码结构一样。 说明序对满足闭包性质，代数中的概念，一个集合在一个操作下是闭包的，表示操作的结果也在这个集合内 > (car ( cons 1 2 ) ) 1 1 > (cdr ( cons 1 2 ) ) 2
( cons 1 (cons 2 ( cons 3 nil ) ) ) list nil 1 2 3 nil作为序对的链结束，也可以当做不包含任何元素的序列，空表 (car seq) seq列表的第一个元素 (cdr seq) 去掉第一个元素后的列表 ( cons 1 (cons 2 ( cons 3 nil ) ) ) ( list 1 2 3 )
( append ( list 1 2 3 ) (list 4 5 6 ) ) ‘( 1 2 3 4 5 6 ) ( car (list 4 5 6 ) ) ( list 4 5 6 ) = ( cons 4 ( list 5 6 ) ) 4 ( cdr ( list 4 5 6 ) ) ‘( 5 6 ) (cons 1 ( list 2 3 4 ) ) ‘(1 2 3 4 )
生成一个list ( define ( gen-list start end ) ( if ( > start end ) nil (cons start ( gen-list ( + start 1 ) end ) ) ) ) 递归过程，过程的定义中引用了自己 递归计算过程 迭代计算过程 使用递归表示循环 > ( gen 2 5 ) ‘( 2 3 4 5 ) ( define ( gen-list start end ) ( define ( gen-iter next result ) ( if ( < next start ) result ( gen-iter ( - next 1 ) (cons next result ) ) ) ) ( gen-iter end nil ) )
( my-map proc ( cdr seq ) ) ) ) ) ( map proc seq) ( define ( map proc seq ) ( if ( null? seq ) nil ( cons ( proc ( car seq ) ) ( my-map proc ( cdr seq ) ) ) ) ) 介绍一下最基本的实现。map 映射 一个list 通过一个函数映射到另外一个list。 ( map square ( list 1 2 3 4 5 ) ( 1 4 9 16 25 )
( map ( lambda ( x ) ( + x 1 ) ) ( map square ( gen-list 1 5 ) ) )
(filter predicate seq) ( filter prime? ( gen-list 2 10 ) )
accumulate ( define ( accumulate op init seq ) ( if ( null? seq ) init ( accumulate op ( op ( car seq ) init ) ( cdr seq ) ) ) ) fold-right fold-left ( accumulate + 0 ( list 1 2 3 4 ) ) ( + 1 ( + 2 ( + 3 ( + 4 0))))
flatmap (map (lambda (x) (gen-list 1 x)) (gen-list 1 3)) '((1) (1 2) (1 2 3)) flat map accumulate cons nil 变平 将每个list产生的次级list扩展到外层 ( define ( flatmap proc seq ) ( accumulate append nil ( map proc seq ) ) ) ( flatmap ( lambda ( x ) ( gen-list 1 x ) ) ( gen-list 1 3) ) '(1 1 2 1 2 3)
combine them ( accumulate + 0 ( filter ( lambda ( x ) ( > x 0 ) ) ( map ( lambda ( x ) ( - x 5 ) ) (gen-list 1 10 ) ) )
8皇后问题 queenssssssss!!!!!!!!!!!!!!!!!!!! ( 7, 5, 3, 1, 6, 8, 2, 4)
(define (queens board-size) (define (queen-cols k) (if (= k 0) (list empty-board) (filter (lambda (positions) (safe? k positions)) (flatmap (lambda (rest-of-queens) (map (lambda (new-row) (adjoin-position new-row rest-of-queens)) (gen-list 1 board-size))) (queen-cols (- k 1)))))) (queen-cols board-size))
(define empty-board '()) (define (safe-with-col k i positions) (let ((value-k (list-ref positions (- k 1))) (value-i (list-ref positions (- i 1)))) (nor (= value-k value-i) (= (abs (- i k)) (abs (- value-k value-i)))))) (define (safe? k positions) (define (safe-with i) (if (= i k) true (if (not (safe-with-col k i positions)) false (safe-with (+ i 1))))) (safe-with 1)) (define (adjoin-position new-row rest-of-queens) (append rest-of-queens (list new-row)))
Functional style in Java lambda expression java.util.function Stream API java.util.stream 提出公用模式,建立高层抽象 lambda expression 拥有一个抽象方法的类或接口 intermediate operation terminal operation supplier The identity value must be an identity for the combiner function Collectors reactive programming asynchronous programming with observable streams filter(predicate) flatMap(mapper) forEach(action) map(mapper) collect(collector) reduce(identity, accumulator, combiner)
.filter(w -> w.length() > 4) .count() words.stream() List<String> words = … long count = 0; for (String word : words ) { if ( word.length() > 4 ) { count += 1; } 命令式 imperative 迭代将filter 、 map 、reduce 逻辑放在了一个iterator中，并且是sequential的 使用stream方式把各个元件分离开，并且可以在适当的时候换成parallel的模式parallelStream readable and fluent in order to keep code neat and simple. words.stream() .filter(w -> w.length() > 4) .count() words.stream() .filter(w -> w.length() > 4) .map(w -> 1L) .reduce(0, (a, b) -> a + b))
Collection API Map<String, Integer> wordCountMap = new HashMap<>(); List<String> lines = Files.readAllLines(path); for (String line : lines) { String[] words = WHITE_SPACE.split(line); for (String word : words) { if (word.length() > 4) { if (StringUtils.isNotEmpty(word)) { wordCountMap.merge(word, 1, Integer::sum); }
Stream<String> lines = Files.lines(path); Map<String, Long> wordCount = lines .flatMap(WHITE_SPACE::splitAsStream) .filter(w -> w.length() > 4) .collect(Collectors.groupingBy(w -> w, Collectors.counting()));
推荐的书 计算机程序的构造和解释 Cheers
Thanks & QA