CS 378: Symbolic Programming: Lecture Notes


Copyright © Gordon S. Novak Jr.

Permission is granted for individuals to make copies of these notes for personal use, or for instructors to make copies for classroom use.

Note: Some of these pages use math symbols such as: ∀ ∃ . Microsoft Internet Explorer will not display the math symbols, but Firefox will.

Index

1. CS 378, Symbolic Programming
2. Course Topics
3. Symbolic Programming
4. Functional Programming
5. Clojure
6. Why Symbolic and Functional Programming?
7. Class Projects
8. Clojure
9. Quotation
10. List
11. Constructing a List
12. Access to Parts of a List
13. List Access Functions
14. IF statement
15. Tests on cons
16. Recursion
17. Tracing Function Calls
18. Designing Recursive Functions
19. Design Pattern for Recursive Functions
20. Recursive Processing of List
21. Recursive List Design Pattern
22. Tail Recursive Processing of List
23. Tail Recursive List Design Pattern
24. Constructive Tail Recursive Reverse
25. Tail Recursive Reverse Execution
26. Append
27. Append: Big O Sucker Trap
28. Beware the Bermuda Triangle
29. Set as Linked List
30. Intersection
31. Tail-Recursive Intersection
32. Union and Set Difference
33. Association List
34. Let
35. Map
36. Some and Every
37. println, do, when
38. doseq and sort
39. Trees
40. Arithmetic Expressions as Trees
41. Computer Programs as Trees
42. English Sentences as Trees
43. Representations of Trees
44. First-Child / Next-Sibling Tree
45. Linked List Tree
46. Binary Tree Recursion
47. Design Pattern: Binary Tree Recursion
48. Flattening Binary Tree
49. Examples: Flattening Tree
50. Tracing Flattening Binary Tree
51. Postorder
52. Search
53. State Space Search
54. Depth-First Order: Recursive Default
55. Tree Recursion
56. Answer for State Space Search
57. Design Pattern: Depth-first Search
58. Comments on Search Algorithm
59. Tail-Recursive Search
60. Robot Mouse in Maze
61. Robot Mouse Program
62. Robot Mouse Example
63. Tracing the Robot Mouse
64. Tracing the Robot Mouse ...
65. Depth-First Search
66. Big O for Trees
67. Bounded Depth-First Search
68. Iterative Deepening
69. Cost of Iterative Deepening
70. Depth-First Search
71. Solving Equations
72. Solving an Equation by Search
73. Examples: Base Cases
74. Recursive Cases: Operators
75. Recursive Tree Search
76. Recursive Tree Search Example
77. Big O and Termination
80. Solving a Set of Equations by Search
81. Solving Physics Story Problems
82. Generating Code from Equations
83. Eliminating Unused Equations
84. Conservation Laws
85. Double-Entry Bookkeeping
86. Representing Financial Contracts
87. Finance Combinators
88. Pattern Matching Overview
89. Copy Tree and Substitute
90. Substitution Examples
91. Loop Unrolling
92. Loop Unrolling Code
93. Binding Lists
94. Multiple Substitutions
95. Instantiating Design Patterns
96. Tree Equality
97. Tracing Equal
98. Design Pattern: Nested Tree Recursion
99. Tracing Nested Tree Recursion
100. Pattern Matching
101. Specifications of Match
102. Match Function
103. Matching and Substitution
104. Transformation by Patterns
105. Solving Equations with Patterns
106. Symbolic Differentiation
107. Repetitive Transformation
108. Optimization by Patterns
109. Constant Folding
110. Correctness of Transformations
111. Knuth-Bendix Algorithm
112. Programs and Trees
113. Macros
114. In-line Compilation
115. Partial Evaluation
116. Partial Evaluation
117. Example
118. Simple Partial Evaluator
119. Simple Partial Evaluator...
120. Examples
121. Examples
122. Binding-Time Analysis
123. Futamura Projections
124. Interpreter
125. Specialization
126. Parameterized Programs
127. Pitfalls of Partial Evaluation
128. Pitfalls ...
129. Language Translation
130. Program Transformation using Lisp
131. Max and Min of a Function
132. Knowledge Representation and Reasoning
133. Representation Hypothesis
134. Kinds of Knowledge
135. Logic
136. Logical Representation
137. Propositional Logic
138. Interpretation in Propositional Logic
139. Equivalent Formula Laws
140. Ways to Prove Theorems
141. Rules for Backward Chaining
142. Backward Chaining
143. Backchaining
144. Backchaining Code
145. Backchaining Code, version 2
146. Normal Forms
147. Satisfiability Checking
148. SAT Solvers
149. Uses of SAT Solvers
150. Predicate Calculus (First-order Logic)
151. Order of Quantifiers
152. Skolemization
153. Unification
154. Examples of Unification
155. Substitutions
156. Unification Code
157. Unification Code ...
158. Unification Examples
159. Soundness and Completeness
160. Resolution
161. Resolution Example
162. Resolution Example
163. Natural Deduction
164. Backchaining Theorem Prover
166. Deductive Composition of Astronomical
167. Difficulty of Programming
168. Domain Theory
169. Astronomical Domain
170. Problem Difficulty
171. Where is the shadow of Io on Jupiter?
172. Shadow of Io Theorem
173. Shadow of Io Program
174. Performance
175. Deductive Composition of Programs
176. Logic Form of Rules
177. Navigation in the Plane
178. Navigation Predicates
179. Example Navigation Problem
180. Difficulties with Deductive Synthesis
181. Knowledge Rep. in Predicate Calculus
182. Rules
183. Backward Chaining
184. Importance of Backchaining
185. PROLOG
186. Predicate Calculus as Programming Language
187. When to Use Logic
188. Unit Conversion
189. Conversion Using SI Units
190. Unit Checking
191. Special Conversions
192. Unit Simplification
193. Problem Solving by Unit Conversion
194. Fixing Conversion Errors
195. Units in Programming Languages
196. Expert Systems
197. Power-Based Strategy
198. Expert Reasoning
199. Expert Knowledge
200. Choosing a Domain
201. Rule-Based Systems
202. Advantages of Rules
203. EMYCIN
204. Rule-Based Expert Systems
205. Reasoning Under Uncertainty
206. Bayes' Theorem
207. Uses of Bayes' Theorem
208. Joint Probability Distribution
209. Chain Rule
210. Bayesian Networks
211. Computing with Bayesian Networks
212. A Heretical View
213. EMYCIN's Certainty Factors
214. Certainty Factor Meaning
215. EMYCIN Data CF's
216. EMYCIN Antecedent CF
217. Rule Certainty Factors
218. Certainty Factor Combination
219. Certainty Factor Combination
220. Summary of CF Computations
221. Contradictions:
222. Duplicate Rules
223. Rule Subsumption
224. Increasing Certainty
225. EMYCIN CF vs. Probability Theory
226. Sensitivity Analysis
227. Explanation
228. Expert Systems vs. Decision Trees
229. Rule Induction
230. Sample Decision Tree:
231. Example of Rule Induction
232. Final Decision Tree with Classifications
233. Algorithm for Rule Induction
234. Alternatives for select-feature
235. Limitations of Rule Induction
236. Digital Low-Pass Filter
237. Getting Knowledge From Expert
238. Interaction with Expert
239. Conceptual Islands
240. Advantages of Conceptual Islands
241. Expansion with Conceptual Islands
242. Orthogonal Knowledge Sources
243. Example of Orthogonal Knowledge Sources
244. The Tuning Fallacy
245. Natural Language Processing (NLP)
246. Why Study Natural Language?
247. Model of Natural Language Communication
248. Minimality of Natural Language
249. Zipf's Law
250. Areas of Natural Language
251. Computer Language Understanding
252. Problems in Understanding Language ...
253. Morphology
254. Lexicon
255. Lexical Features
256. Size of Lexicon
257. Statistical Natural Language Processing
258. Part-of-Speech Tagging
259. AI View of Syntax
260. Grammar
261. Language Generation
262. Parsing
263. Ambiguity
264. Sources of Ambiguity
265. Foreign Languages
266. Formal Syntax
267. Notation
268. Phrase Structure Grammar
269. Recognizing Automaton
270. Regular Languages
271. Context Free Languages
272. What Kind of Language is English?
273. Parsing
274. Top-down Parser
275. Bottom-up Parsing
276. Augmented Transition Networks
277. Augmented Transition Networks
278. Separability of Components
279. Problems with Separability
280. Combining Syntax and Semantics
281. How to Combine Syntax \& Semantics
282. Natural Language as an AI Problem
283. Reference
284. Referent Identification
285. English
286. Expression Trees to English
287. Generating English
288. Simple Language Processing: ELIZA
289. Spectrum of Language Descriptions
290. Semantic Grammar
291. Semantic Grammar: Extended Pattern Matching
292. Example Semantics for a Semantic Grammar
293. Compositional Semantics
294. Additional Language Features
295. Recursive Descent
296. Parsing English
297. ATN Program
298. Parsing Functions
299. Grammar Compiler
300. Sentence Pointer Handling
301. Sentence Pointer Handling ...
302. Lexicon Example
303. Word Category Testing
304. Database Access
305. Building Database Access
306. Restaurant Database Grammar
307. Restaurant Queries
308. Physics Problems
309. Physics Queries
310. Natural Language Interfaces
311. Problems with NL Interfaces
312. Mapping
313. Implementation of Mapping
314. Functional Programming
315. Associative and Commutative
316. Computation as Simulation
317. Mapping in Lisp
318. Mapcat and Filter
319. Input Filtering and Mapping
320. Reduce
321. Combining Map and Reduce
322. MapReduce and Massive Data
323. Distributed Programming is Hard!
324. What MapReduce Does for Us
325. Map Sort Reduce
326. Simplified MapReduce
327. Mapreduce in Clojure
328. Simple MapReduce Example
329. MapReduce Example
330. Hamburger Example
331. How MapReduce Works
332. Map Worker
333. Buffering
334. Load Balancing
335. Reduce Worker
336. PageRank
337. PageRank Example
338. Running PageRank Example
339. Advanced Performance
340. Performance Techniques in MapReduce
341. Algorithm Failure
342. Atomic Commit


CS 378