Lisp Function Programming for the First Time reading notes

About LISP

LISP is a programming language widely used in the fields of artificial intelligence and artificial language processing. The main features of LISP are as follows

• Lists (linked lists) are the basic data structure: LISP data is represented as lists, which themselves are evaluated as LISP programs. By taking advantage of this feature, LISP can handle highly flexible data structures.
• Supports functional programming: LISP is a functional programming language, which allows functions to be treated as first-class values. Functions can also be used as meta “higher-order functions” that can be passed to other functions as arguments or return values, or assigned to variables.
• Supports self-referencing: LISP programs can self-reference and refer to their own structure. This makes LISP highly flexible and allows writing programs that are self-modifiable.
• Simple syntax: The syntax of LISP is very simple, making it easy to write programs.
• Many derivatives: There are many derivatives of LISP, each of which has its own characteristics and uses. Typical derivatives include Common Lisp, Scheme, and Clojure.

In this issue, we will introduce”First Lisp Function Programming“, a reference book .and Reading notes are provided.

Lisp Function Programming for the First Time reading notes

What are the advantages of Lisp and functional programming – programming without side effects is the first one. This reduces bugs by far. Furthermore, it is easy to reuse code, and it is good at parallel processing. But that’s not all. It also features dynamic typing, lambda computation, closures, and even object-oriented programming. There are universal ideas in Lisp that have transcended the decades and are still applicable today. This book explains various Lisp programs (Tower of Hanoi, Eight Queens, online bookstore, etc.) and teaches refactoring all at once. You can get the essence of functional programming in this book.

Chapter 1: What is Functional Programming--and Why is it Hard?

1.1 What is Functional Programming?

1.1.1 Pure Functions and Reference Transparency
1.1.2 Side Effects
1.1.3 Overview of Functional Programming

1.2 History of Functional Programming

1.2.1 The Dawn of Functional Programming (1930s-1960s): From the Birth of Lambda Calculus to Lisp
1.2.2 The Cradle of Functional Programming (1970s) The Lisp v.s. ML War
1.2.3 Development of Functional Programming (1980s) Golden Age of AI
1.2.4 Lull in Functional Programming (1990s) Lisp's Lull and Haskell's Birth
1.2.5 Functional Programming Revival Period (2000s): A New Era with F# and Scala
1.2.6 The Second Growth Period of Functional Programming Languages (2010s) Towards Functional Programming in the IoT Era

1.3 What's so great about functional programming?

1.3.1 Easy to reuse
1.3.2 Good for Parallel Processing
1.3.3 Fewer Bugs
1.3.4 Easy to test
1.3.5 Suitable for code optimization / application of formal methods / automatic code generation
1.3.6 Capable of dynamic programming--Abstract programming
1.3.7 Other nice things

1.4 Why is functional programming so difficult?

1.4.1 Can't use variables -> Variables with destructive assignment statements--Program without side effects
1.4.2 Can't Use Assignment Statements -> Destructive Assignment Statements -- Programs without Side Effects
1.4.3 Cannot Use Arrays -> Mutable Data Structures--Programs without Side Effects
1.4.4 Difficulty in Recursive Programming--Programs without Side Effects
1.4.5 Difficult to Apply Functions Continuously -- Programs without Side Effects
1.4.6 Higher-Order Functions are Difficult -- Useful and Difficult Features of Functional Programming
1.4.7 Troublesome Evaluation Strategies -- Useful and Difficult Features of Functional Programming
1.4.8 Other Functions Look Difficult--Convenient and Difficult Functions of Functional Programming
1.4.9 I don't know how to design functional types
1.4.10 Paradigm Shift is Hard
1.4.11 Functional Programming is Not Difficult

1.5 How to master functional programming

1.5.1 For programs with no side effects
1.5.2 For Useful Features of Functional Programming
1.5.3 Recommendations for Impure Functional Programming
1.5.4 Recommendations for Functional Programming in Non-Functional Programming Languages

1.6 Summary

Chapter 2: Introduction to Lisp for Learning Functional Programming

2.1 Getting Started with Lisp

2.1.1 Why Lisp is Recommended as a Language for Learning Functional Programming
2.1.2 Introduction to Lisp Processors
2.1.3 The first Lisp program "factorial calculation
2.1.4 Prefix Notation
2.1.5 Dynamic typing
2.1.6 S-expressions--lists and atoms
2.1.7 Lisp Evaluation Strategies

2.2 Lisp Function Roundup

2.2.1 Functions and macros, special forms
2.2.2 Function definitions, if functions, comparison functions, and arithmetic operations
2.2.3 Special forms quote and function
2.2.4 Lists
2.2.5 Symbols
2.2.6 Truth values and predicate functions
2.2.7 Functions for Functional Programming
2.2.8 Macro Functions
2.2.9 Procedural Functions in Lisp
2.2.10 Object-oriented functions
2.2.11 Other Functions

2.3 Implementation of Functional Functions in Lisp--Closure

2.3.1 Closures and their implementation
2.3.2 Example of a simple closure [1]
2.3.3 Example of Multiple Closures with a Common Environment [2]

2.4 Summary

Chapter 3 Basics of Functional Programming

3.1 Functions

3.1.1 Defining Functions Again
3.1.2 What it takes to be a function--reference transparency and no side effects
3.1.3 Advantages of Functions--general advantages of functions, including non-pure functions

3.2 Lambda Calculus

3.2.1 Notation and Rules for Lambda Calculus
3.2.2 Carying
3.2.3 Church's number
3.2.4 Properties of Lambda Calculus

3.3 Side Effects

3.3.1 Comparison of Functions with and without Side Effects
3.3.2 Renormalization of states
3.3.3 Accomplishments of side effects -- What are the merits and demerits of side effects?
3.3.4 Original Sin of Side Effects -- What is the Merit of Side Effects?

3.4 Use of Lists--Immutable Data Structures

3.4.1 Arrays are mutable
3.4.2 Lists are immutable
3.4.3 Implementing Rich Data Structures with Lists--Graphs, Random Access Lists

3.5 Recursive Programming

3.5.1 Side effects revisited
3.5.2 The first recursive program "factorial"
3.5.3 Generalization of Recursive Programming
3.5.4 Implementation of Recursive Programming on the Stack
3.5.5 Tips on Recursive Programming--Discovery of Recursion
3.5.6 Recursive Programming Pattern 1--List Pattern
3.5.7 Patterns in Recursive Programming 2--Integer Pattern
3.5.8 Patterns in recursive programming3--Storage patterns
3.5.9 Terminal recursion
3.5.10 Debugging Recursive Programming--Trace
3.5.11 Efficiency and Safety of Recursive Programming

3.6 Higher-Order Functions

3.6.1 First-Order Functions and Second-Order Functions
3.6.2 Examples of Higher-Order Functions--Full Number Search
3.6.3 Examples of Higher-Order Functions--Function Composition compose
3.6.4 Examples of higher-order functions--map and reduce
3.6.5 Examples of higher-order functions--Cullying
3.6.6 Execution Speed and Comprehensibility of Higher-Order Functions

3.7 Evaluation Strategies--Lazy Evaluation

3.7.1 Inner-Left Preference Strategy--Positive Evaluation
3.7.2 Change of Evaluation Strategy by Closure--Non-Positive Evaluation
3.7.3 Implementation of Lazy Evaluation by Macro
3.7.4 Term Rewriting System
3.7.5 Inner Priority Evaluation vs. Outer Priority Evaluation
3.7.6 When to Use Nonpositive Evaluation (Lazy Evaluation)

3.8 Functional Oriented Design

3.8.1 Combinational Design of Components
3.8.2 Module Partitioning and Differential Development
3.8.3 Data design and relationship between data
3.9 Around functional programming--generic functions, type inference, monoids, monads, FRP
3.9.1 Generic function (inclusive function)
3.9.2 Type inference type inference
3.9.3 Monoid monoid
3.9.4 Monad
3.9.5 Functional Reactive Programming Functional Reactive Programming (FRP)

3.10 Summary

Chapter 4 Comparison of Programming Paradigms

4.1 Comparison with Object-Oriented Programming

4.1.1 The Essence of Object-Oriented Programming 1 -- Encapsulation and Information Hiding by Classes
4.1.2 Essence of Object-Oriented Programming 2--Differential Programming
4.1.3 Advantages and Disadvantages of Object Oriented Programming
4.1.4 Comparison with Functional Programming

4.2 Relationship with Procedural Programming

4.2.1 The Essence of Procedural Programming State Manipulation by Side Effects--Array and Variable-Centered
4.2.2 Understanding Procedural Programming--Only Instructions, Not Purpose
4.2.3 Advantages and Disadvantages of Procedural Programming
4.2.4 Comparison with Functional Programming

4.3 Analysis of Functional Programming

4.3.1 Programs without side effects and their effects
4.3.2 Ease of Making Programs
4.3.3 Ease of understanding the program
4.3.4 Efficiency of program execution
4.3.5 The Future of Functional Programming

4.4 Functional Programming in Java (Reference)

4.4.1 Return a clone of itself this in state operations
4.4.2 When Modifying Other People's Objects
4.4.3 Copying Objects

4.5 Summary

Chapter 5: Exercises in Functional Programming

5.1 Introduction to Recursive Programming Exercises

5.1.1 Quick Sort (First-Order Function Version)
5.1.2 Hybrid Version of Quicksort (First-Order Function Version)
5.1.3 Tower of Hanoi
5.1.4 Four Towers of Hanoi

5.2 Higher-Order Functions

5.2.1 Whole Number Search
5.2.2 Quick Sort (Second-Order Function Version)
5.2.3 Quick Sort (2-Function Argument Version)

5.3 List of Immutable Data

5.3.1 Eight Queens
5.3.2 Eight Queens (Hybrid version)
5.3.3 Document Structure - Tree Traversing
5.3.4 Queue (Queue)

5.4 States

5.4.1 Piggy Banks and Banks
5.4.2 Random Numbers and Slot Machines

5.5 Latency Evaluation

5.5.1 Tarai Function---Tarai Function (Takeuchi Function)
5.5.2 Infinite Lists

5.6 Object-Oriented Programs--Encapsulation and Differential Programming

5.6.1 Students and Humans--First Steps in Encapsulation and Differential Programming
5.6.2 Coordinates and Windows--Multiple Inheritance

5.7 Refactoring Object-Oriented and Procedural Programs--Anti-Patterns

5.7.1 Unnecessary Global Variables
5.7.2 Unnecessary Classes
5.7.3 Taking global variables around
5.7.4 First Refactoring for an Anti-Pattern Program

5.8 General Exercises -- Lisp Processing System

5.8.1 Parsing flow
5.8.2 Syntax rules of Lisp
5.8.3 Parsing--Literals and function application
5.8.4 Parsing--Special Forms and Lists
5.8.5 Code Generation

5.9 General Exercises--Online Bookstore

5.9.1 Business Objects--Books
5.9.2 Business Logic--ISBN and Publisher Input Checking
5.9.3 Business Logic--Database Access and Hierarchical Lists

5.10 Summary

Chapter 6 Evaluation and Refactoring of Functional Programs

6.1 Evaluation Criteria--Code Metrics

6.1.1 What are code metrics?
6.1.2 Metrics related to code size--number of lines of code, number of statements
6.1.3 Metrics for number of items--number of function calls
6.1.4 Metrics for Code Complexity--Cyclomaticity
6.1.5 Recursion Metrics--Number of Steps in Recursion

6.2 Evaluation Metrics--Code Review

6.2.1 Naming
6.2.2 Simple and Small--One Function, One Function
6.2.3 Abstraction--Balance between generic functions and higher-order functions
6.2.4 Balance between comprehensibility and efficiency

6.3 Refactoring Functional Programs

6.3.1 Renaming
6.3.2 Function Extraction
6.3.3 Terminal recursion
6.3.4 Rethinking programs without side effects

6.4 Summary

Conclusion

References