NOTE 1: Check all Lisp code with the Unit Tester and the Lisp Critic before submitting. Even when there are no unit tests, all code can and should be checked with the Lisp Critic. If I notice mistakes in code that the Critic catches, I stop reviewing immediately and return the code.
NOTE 2: Define all functions in a file, using a Lisp editor. Code typed in the Listener window, or edited in an plain text editor like Sublime, will be incorrectly indented. Such code will be returned unreviewed for proper indentation.
This course is about several different ways to represent and use symbolic knowledge representations to answer questions and solve problems. We will cover three major approaches to representing and using everyday knowledge. Along the way, we will also explore some of the technologies used to share knowledge of the web.
- Semantic networks:
- Ontologies and triples
- Graph networks and paths
- Graph queries and patterns
- Pattern matching with variables
- RDF and RDFa-Lite
- Ontologies and triples
- Hierarchical frame systems
- Memory organization packets (MOPs)
- Inheritance and defaults
- Case-based reasoning
- Deductive rules
- Unification and backward chaining
- Deductive retrieval
- Declarative programming
- OWL and CYC
Don't panic if some section takes you longer than you expected. But do panic if your productivity falls below what I expect. Make sure you understand how this course works.
Exercises are small coding problems. Like calisthenics, they help you focus on and strengthen specific "coding muscles." Exercises are more focused on a specific coding challenge, and have very thorough unit tests.
Applications are larger coding problems, requiring you to apply multiple coding skills and basic AI concepts to do something useful. There are fewer unit tests, meant only to verify that the overall system works for some basic examples.
You are evaluated, continuously, on both exercises and applications. Exercises show effort. Applications show mastery. Both matter. You can't do well in this class with just exercies or just applications.
The exercises and applications below are organized into topic bundles. The exercises in a bundle prepare you for the applications in that bundle.
- Submit each exercise as soon as you have a working solution that passes all tests and gets no critiques.
- Do not do an entire bundle before sending anything.
- You don't need to do every bundle. But you do want to do a variety of bundles.
- You don't need to do everything in a bundle. But don't just cherry pick the easy exercises from each bundle.
- If you find a bundle easy to code without critiques, do just one or two of the hardest exercises in a bundle, so that you can move on to more interesting exercises.
A number of older exercises are not in any bundle right now. You can do them for practice if you want, but don't submit them to Code Critic. Email me if you want help on a non-bundled exercise.
Exercises are where I do the most critiquing of the quality of your code. There is too much bad code in the real world because developers never learned to write clean solid code in the small.
Applications are where I evaluate how well you have learned to program. I critique them but not in as much detail.
If you think a critique does not apply, include a comment with the critique, and why you think it doesn't apply in this case. As soon as I see code that gets a Lisp Critic critique without such a comment, I stop reviewing and return the code for re-work.
When doing exercises from Graham, be sure to read both the book's requirements, and my notes.
Recursion is central to AI Programming, for numerous tasks, including
- searching and matching recursively nested knowledge structures ("John knows Mary believes Bill feels Mary likes him")
- searching and matching graphs of interconnected knowledge triples
- searching through spaces of alternative action choices
Time to stop thinking recursion is a funky way to implement factorial!
- Exercises: Ex 2-4+7+8+9 Lisp Basics (skip if you know Lisp/Scheme from before), Ex 3-8 List Printing, Ex 5-9 Breadth-First Search, Generalized BFS, Ex 3-9 Longest Path
- Applications: Iterative Deepening Search
Sequence Functions Bundle
- Lisp Exercises: Lisp #1: HAS-NUMBER-P, Lisp #5: COLLECT-NUMBERS, Lisp #11: MAP-RANGE, FIND-RANGE, EVERY-RANGE, REDUCE-RANGE
- Applications: TBD
Text Processing Bundle
In our code, we pass and return values, so reading and printing are not needed as much as you may be used to. But text processing does become important when analyzing linguistic input or passing data over the web.
- Exercises: Ex 7-2 map-stream, Ex 7-5+6 stream-subst, Ex 8-5 Henley
- Applications: Tokenizer
Pattern Matcher Bundle
- Lisp Exercises: Instructions on loading and testing the Lisp matcher, Matcher #1: ?NOT, ?OR, ?=, Matcher #2: ?CONTAINS
- Applications: TBD
Tries (pronounced like "trees" as in re-trie-val) are a specializaed recursive data structure that can pay off with big speed up in code, when appropriately used.
- Exercises: Ex 8-4 Packages
- Applications: Word Tries, Boggle Solver, Crossword helper
Multiple Values and Continuations Bundle
Lisp has a special facility for efficiently returning multiple values from code without creating temporary lists that need to be garbage collected.
- Exercises: Ex 5-8 max-min, Ex 9-2 make-change, Ex 9-6 horner, reduce-tree
- Applications: rename-vars
Numeric Application Bundle
Lisp is not thought of as a language for numeric processing, but it actually does quite well. With type declarations and adjustment of the compiler's options, numeric Lisp code can be competitive with C++.
The applications here are easy to understand, but are surprisingly hard to solve with clean readable code.
- Exercises: Ex 9-2 Make Change, Ex 9-5 Equation Solver
- Applications: Make Best Change, Intersect Segments
Deductive Retrieval Bundle
Don't do these until we have discussed deductive retrieval in class. Deductive retrieval, i.e., retrieving data deductively inferred from other data, is surprisingly simple to implement, surprisingly powerful, but hard to optimize.
- Exercises: member, map Coloring
- Applications: Shakey exercises
Generated Lists Bundle
Want to have an infinite list? Or a list of future values? Here's one simple way to do it. For even more on this idea, see the ReactiveX API.
- Exercises: Generated list exercises
- Applications: ask-1 exercise
Cleaning Up Legacy Code Bundle
Why do I spend so much time getting you to write 10 line functions as cleaner shorter 3 line functions? Because if you don't nip certain coding practices in the bud, you end up with the code in the joke generator in the applications.
- Exercises: Ex 8-5 Henley
- Applications: Clean Joke Code, Faster Riddles, One Riddle at a Time
Semantic Web Bundle
Wait until we've discussed triples in class.
- Exercises: camelize, hyphenate, atomize :NOT queries
- Applications: read-json-ld
Frames (MOPS) Bundle
This is a new set of exercises, so expect changes for a while
- Exercises: has-slots-p, linearize, mop-search
- Applications: Bug Helper (under construction), Parsing (DMAP)
Macros are a super-simple way to extend Lisp syntax. Having said that, extending the syntax of a language can lead to hard to maintain code. Use with caution.
- Exercises: Chapter 10 macro exercises, test-exp
- Applications: list-of, with-collector