path: root/docs/sexp-primer.md

# S-expressions: a primer for krino

krino's configuration is written in **s-expressions**, the notation Lisp has
used since 1958. You do not need to know any Lisp to write a krino config. This
page teaches exactly the part of the notation krino uses, where it comes from,
and how to read a rule at a glance. It ends with exercises and a reading list.

## 1. Two kinds of thing

Everything in an s-expression is one of two things.

An **atom** is a single word or value:

```lisp
pdf            ; a symbol: a bare word
30d            ; also a symbol, krino reads it as "30 days"
"acme ltd"     ; a string: anything in double quotes
```

A **list** is a pair of parentheses holding atoms or other lists, separated by
spaces:

```lisp
(type pdf docx)
(move "Work/2026")
(when (type pdf) (size > 10M))
```

That is the whole grammar. There are no commas, no semicolons between items,
no operators with special spelling, no indentation rules. Whitespace and line
breaks only separate things; you can lay a list out on one line or twenty.

A `;` starts a comment that runs to the end of the line. By convention `;;`
begins a comment on its own line and `;` a comment after code.

## 2. The first element says what to do

In every list, the **first element names the operation** and the rest are
what it operates on:

```lisp
(type pdf docx)        ; operation: type    arguments: pdf, docx
(move "Photos")        ; operation: move    argument:  "Photos"
(and A B C)            ; operation: and     arguments: A, B, C
```

This is **prefix notation**: the operator comes before its operands. Ordinary
arithmetic is *infix* (`3 + 4`, operator in the middle). Prefix writes it
`(+ 3 4)`.

Because the parentheses mark exactly where each list ends, an operator can
take any number of arguments. `(+ 1 2 3 4)` adds four numbers; `(and A B C)`
requires three conditions; `(type pdf docx odt)` accepts three extensions.
Infix cannot do that without repeating the operator: `1 + 2 + 3 + 4`.

## 3. Where prefix notation comes from

The Polish logician **Jan Łukasiewicz** introduced prefix notation in 1924, to
write logic without any parentheses at all: "I came upon the idea of a
parenthesis-free notation in 1924." It became known as **Polish notation**.

The trick works when every operator takes a fixed number of operands. Then
the order alone determines the grouping:

| Infix             | Polish (prefix) | Reverse Polish (postfix) |
|-------------------|-----------------|--------------------------|
| `3 + 4`           | `+ 3 4`         | `3 4 +`                  |
| `(3 + 4) × 5`     | `× + 3 4 5`     | `3 4 + 5 ×`              |
| `3 + (4 × 5)`     | `+ 3 × 4 5`     | `3 4 5 × +`              |

**Reverse Polish notation** puts the operator *after* its operands. It is how
stack calculators and the Unix `dc` calculator work. You can try it now:

```sh
echo '3 4 + 5 * p' | dc      # (3 + 4) × 5, prints 35
echo '3 4 5 * + p' | dc      # 3 + (4 × 5), prints 23
```

(`p` tells `dc` to print the top of its stack.)

Lisp's s-expressions are Polish notation **with the parentheses kept**. That
costs a few brackets and buys two things: operators may take any number of
arguments, and you can always see at a glance where an expression ends.

## 4. Nesting

A list can contain lists, to any depth. Read nested lists from the outside
in: the outer operation first, then each argument in turn.

```lisp
(or (type image) (size > 10M))
```

"**or** of two things: the file is an image; the file is bigger than 10 MB."

```lisp
(and (type document)
     (or (content "acme ltd") (name "\bacme\b"))
     (not (name "^draft")))
```

"**and** of three things:
1. the file is a document;
2. **or** of two things: its text mentions *acme ltd*; its name contains the word *acme*;
3. **not**: its name starts with *draft*."

There is no precedence to remember. In infix, `A and B or C` could mean
`(A and B) or C` or `A and (B or C)`, and you have to know the rule. In an
s-expression you must write one or the other:

```lisp
(or (and A B) C)     ; (A and B) or C
(and A (or B C))     ; A and (B or C)
```

## 5. What a krino config looks like

A krino config file is a sequence of lists. Each top-level list is a
**form**, and the first word of the form says what it sets:

```lisp
;; ~/.config/krino/dirs/downloads.conf
(path "~/downloads")
(ignore "*.part" "*.aria2" ".*")

(rule "acme"
  (when (type document)
        (or (content "acme ltd" "0000000000")
            (name "\bacme\b")))
  (move "Work/Acme/{mtime:%Y}")
  (stop))
```

`(rule "acme" ...)` is a form whose first argument is the rule's name and
whose remaining arguments are more lists: `when` holds the condition,
`move` and `stop` are actions. The whole rule is itself just a list.

Two krino conventions to know:

- **`when` with several conditions means all of them.** The rule above
  could have been written `(when (and (type document) (or ...)))`; the `and`
  is implied. You need `and` only inside an `or` or a `not`.
- **Tests that take several arguments mean "any of them".** `(type pdf docx)`
  is true for a PDF *or* a DOCX. `(content "a" "b")` is true if the text
  contains *a* or *b*. For "all of", combine tests: `(content "a") (content "b")`.

### Symbols or strings?

Bare words (`pdf`, `yes`, `strict`, `>`, `30d`) are **symbols**. Paths,
keywords, rule names and regular expressions go in **double quotes**. If a
value could contain a space, a parenthesis, a `;` or a `"`, quote it.

Inside a string, a backslash escapes only `"` and `\`. Every other backslash
is kept as written, so regular expressions need no doubling:

```lisp
(name "\bacme\b")           ; the regex \bacme\b, exactly as written
(content "say \"hello\"")   ; the text: say "hello"
```

## 6. Translating ordinary logic

| You mean                                               | You write                                          |
|--------------------------------------------------------|----------------------------------------------------|
| PDFs                                                   | `(type pdf)`                                       |
| PDFs or Word files                                     | `(type pdf docx)`                                  |
| PDFs over 10 MB                                        | `(type pdf) (size > 10M)`                          |
| images or anything over 1 GB                           | `(or (type image) (size > 1G))`                    |
| mentions "invoice" but not "draft"                     | `(content "invoice") (not (content "draft"))`      |
| name starts with `IMG_`, in strict case                | `(name "^IMG_")` plus `(case strict)` on the rule  |
| a document, and either the name or the text says acme  | `(type document) (or (name "acme") (content "acme"))` |

(The left column of conditions all go inside `(when ...)`.)

## 7. Common mistakes

**Unbalanced parentheses.** Every `(` needs a `)`. krino reports the line
where an unclosed list *opened*, which is usually the rule that is broken:

```
downloads.conf:12:1: "(" never closed: (rule "acme" ...)
```

Count from the inside out, or let your editor do it (see below).

**`not` takes exactly one condition.** To negate several, wrap them:
`(not (or A B))` means "neither A nor B".

**A bare word where a string is needed.** `(move Work/Acme)` is a symbol with
a slash in it, which krino rejects for a path; write `(move "Work/Acme")`.

**Forgetting the implied `and` is only at the top of `when`.** Inside `or`,
each argument is a separate alternative:
`(or (type pdf) (size > 1M))` is "PDF, or big", never "big PDF".

## 8. Editor help

Any editor with a Lisp mode matches parentheses and indents s-expressions.
krino's generated files start with lines that switch it on:

```lisp
;; -*- mode: lisp -*-
;; vim: set ft=lisp :
```

In **vim**: `%` jumps between matching parentheses; `:set showmatch` flashes
the partner of each `)` you type; `=` re-indents a selection using Lisp rules.
In **Emacs**: `C-M-f` / `C-M-b` move over a whole list; `C-M-q` re-indents it.

## 9. Exercises

1. Write `(2 + 3) × 4` as an s-expression, in Polish notation, and as a `dc`
   command. Check the `dc` one in your shell.
2. Write the condition: "videos or audio files older than a year".
3. Write the condition: "spreadsheets that mention *budget* but not *draft*".
4. Find the mistake: `(when (and (type pdf) (content "invoice"))`
5. Do these mean the same? `(or (and A B) C)` and `(and A (or B C))`
6. Write a rule named `screenshots` that moves PNG files whose name starts
   with `Screenshot` into `Pictures/Screenshots`, and stops.

### Answers

1. `(* (+ 2 3) 4)`; `* + 2 3 4`; `echo '2 3 + 4 * p' | dc` prints `20`.
2. `(when (type video audio) (age > 365d))`. One `type` with two groups
   already means "either".
3. `(when (type spreadsheet) (content "budget") (not (content "draft")))`
4. One `)` is missing at the end: the `when` list is never closed. Count:
   `(when` opens 1, `(and` 2, `(type` 3 closes to 2, `(content` 3 closes to
   2, and the final `)` closes `and`, leaving `when` open.
5. No. Take A false, C true: the first is true (because of C), the second is
   false (because A is false).
6. ```lisp
   (rule "screenshots"
     (when (type png) (name "^Screenshot"))
     (move "Pictures/Screenshots")
     (stop))
   ```

## 10. Further reading

All links checked on 2026-09-11.

**Start here**

- Paul Graham, *The Roots of Lisp* (2002). A short essay that rebuilds Lisp
  from seven primitive operators; the clearest explanation of why
  s-expressions are both code and data.
  <https://www.paulgraham.com/rootsoflisp.html>
- Wikipedia, *S-expression* and *Polish notation*.
  <https://en.wikipedia.org/wiki/S-expression>,
  <https://en.wikipedia.org/wiki/Polish_notation>
- *Learn X in Y minutes: Scheme*. One page of syntax.
  <https://learnxinyminutes.com/scheme/>

**Learn to think in s-expressions**

- Daniel P. Friedman and Matthias Felleisen, *The Little Schemer*, 4th ed.,
  MIT Press, 1995, ISBN 978-0-262-56099-3. Written entirely as questions and
  answers; the gentlest route.
- Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, Shriram
  Krishnamurthi, *How to Design Programs*, 2nd ed. A free beginner course.
  <https://htdp.org/>
- Harold Abelson and Gerald Jay Sussman, *Structure and Interpretation of
  Computer Programs*, 2nd ed. Chapter 1 is enough for this purpose. Free HTML
  edition: <https://sarabander.github.io/sicp/>
- Robert J. Chassell, *An Introduction to Programming in Emacs Lisp*. Also
  available as `info eintr` where Emacs is installed.
  <https://www.gnu.org/software/emacs/manual/html_node/eintr/>
- Peter Seibel, *Practical Common Lisp* (2005). Chapter 3 builds a small
  database out of s-expressions, close in spirit to a krino config.
  <https://gigamonkeys.com/book/>
- Daniel Higginbotham, *Clojure for the Brave and True*. A modern Lisp.
  <https://www.braveclojure.com/>

**Try it interactively**

- GNU Guile (Scheme). Debian: `guile-3.0`; OpenBSD: `guile3`; FreeBSD:
  `pkg search guile`. <https://www.gnu.org/software/guile/manual/>
- Racket. Debian: `racket`; OpenBSD: `racket-minimal`.
  <https://docs.racket-lang.org/guide/>
- `dc(1)` for reverse Polish notation: `man dc`.

**Build one**

The fastest way to understand a notation is to write a parser for it.

- Daniel Holden, *Build Your Own Lisp*. A Lisp in C, parser included.
  <https://buildyourownlisp.com/>
- *mal: Make a Lisp*. A step-by-step guide with implementations in dozens of
  languages, Go among them. <https://github.com/kanaka/mal>

**Original sources**

- John McCarthy, "Recursive Functions of Symbolic Expressions and Their
  Computation by Machine, Part I", *Communications of the ACM*, 1960. The
  paper that defined s-expressions.
  <http://www-formal.stanford.edu/jmc/recursive.html>
- R. Rivest and D. Eastlake 3rd, RFC 9804, *Simple Public Key Infrastructure
  (SPKI) S-Expressions* (2025). S-expressions specified as a data format.
  <https://www.rfc-editor.org/rfc/rfc9804>