> Is my understanding correct that Lisp's powerful macro system stems from the ability to write the eval function in Lisp itself?
I wouldn't say this is the case. Nearly any language could implement an `eval` for itself, but obviously, it is much simpler in Lisps because there's little syntax and few rules.
What makes Lisp macros different from say, C preprocessor macros, is the body of the macro is just Lisp code - so the "preprocessor" in this case has full access to the host languages facilities, which may include `eval`. The macros don't take textual input, but they take structured input in the form of S-expressions.
Implementing macros is obviously simpler due to eval, because we need to run the evaluator on the macro body, but it's not a strict requirement, as macro functionality could be provided by the implementation and could encapsulate its own evaluator.
Lisp macros are also simple due to the fact that Lisp code is just lists of data - you don't have to navigate a complex AST to walk through the code and emit particular syntax. You walk through the input with `car` and `cdr`, and you emit new syntax with `cons` (or `list`/`list*` which are derived from it). Macros can take code as their argument, and produce new code which is evaluated in place.
Macros still have hygiene issues though, because they're based on expanding code before evaluating it, variables used in macros can accidentally shadow variables in the scope of the macro's caller. There are workarounds (gensym) to navigate these hygiene problems.
> From what I gather, Lisp starts with a small set of primitives and special forms—seven in the original Lisp, including lambda. I recall Paul Graham demonstrating in one of his essays that you can build an eval function using just these primitives.
This is largely a theoretical demonstration but not real-world usage. In practice, Lisps have dozens or hundreds of "primitives". Common Lisp in particular is a big language and not trivial to implement. Scheme is a bit smaller, though r6rs started to also grow quite large, but this approach was revisited in r7rs (current), which aims for a small core, with additional functionality being provided through SRFIs (Scheme requests for implementation).
> Those primitives are typically implemented in a host language like C, but once you have an eval function in Lisp, you can extend it with new rules.
Using Scheme as an example, some SRFIs can be implemented purely in Scheme, as libraries, but others require the implementation to provide support, which often requires writing C code to provide them.
> This seems like a way to understand macros, where you effectively add new language rules. I know Lisp macros are typically defined using specific keywords like defmacro
As you note, it's `defmacro`, or `macro`, or `syntax-rules`, `syntax-case`, etc, which introduce new syntax - not eval in particular. Some macros will use `eval` in their bodies, which permits control of evaluation other than the regular applicative form of lambdas.
Macros are more than just `eval`. They're a multi-stage evaluation model where we first need to do some `macroexpand` (which will internally use `eval`), and afterwards the the resulting expression from the macro call is evaluated.
> but is the core idea similar—extending the language by building on the eval function with new rules?
There are some Lisps which still attempt this kind of minimalism.
One example is Ian Piumarta's Maru[1], which support extending `eval` (and `apply`) with new functionality at runtime based on the type being evaluated. Maru basically has global maps of type->evaluator and type->applicator, where we can add new pairs to at runtime and augment the behavior of `eval`/`apply`.
Kernel[2] also aims for the minimalist approach and does away with macros, quote and special-forms entirely, instead replacing them with a more general feature called an operative. The Kernel evaluator does not need to implement special rules for things like `lambda`, `cond`, `car`, `cdr` (as in Graham's "On Lips" essay) - but it just discriminates two forms - operative or applicative. Obviously, some kinds of operative are "primitive", but there's no difference from the PoV of the programmer. Which set of symbols you decide to implement as primitive is up to the implementation. The Kernel report suggests a small set of primitives and demonstrates the remaining standard features can be implemented using only the functionality provided so far.