sum, product, and function structures

interpret axioms in various domains (logic, arithmetic, structures)

use axioms to determine equality in various domains

symbols, sequences, and strings

understand the basic ideas of semiotics (aspects of signs)

recognize how symbols may be encoded using lower-level symbols

(e.g., especially ASCII and Unicode UTF-8)

regular languages

basic facts about DFAs, NFAs, and regular expressions

render a described language as a regular expression or DFA

determine a language from a DFA or RE

numbers and numerals

basic facts about numeral representations (especially place-value reps)

Horner’s technique for efficient evaluation of numerals (and polynomials)

conversion of numbers between bases

algebraic terms

understand algebraic data types and their folds

know how to render a term as an A(lgebraic)DT constructed value (and vice versa)

understand how folds operate on values of ADTs

recognize the variety of “meaning domains” applicable to terms

values proper (e.g., numbers), abstractions (e.g., sign), elaborations (calculation), syntax (pretty-printing)

free variables and polynomial functions

understand how Horner's technique applies to polynomials

recognize that polynomials are just one simple class of (potentially infinite) functions

context-free languages and grammars

know the definition of a context-free grammar

understand how a derivation shows that a string or tree derives from a grammar

recognize how grammars can be ambiguous

parsing combinators

know how to use Haskell “do notation” to parse strings

logic and proofs

recognize the languages or propositional and predicate logic

understand the basics of truth tables

understand the idea of inference or proof rules

be able to provide or understand proofs of simple formulæ

lambda calculus and combinators

know the definition of lambda calculus and combinators

understand the abbreviation conventions for writing lambda terms

understand the notion of variable scoping

be able to reduce terms (to normal form, if possible)

understand how non-termination effects normalization

Turing machines

understand the basic idea behind a Turing machine and “mechanical” computability

recognize the limitations of computability (undecidable problems, Halting problem)