DCGs unsugar into lists, but the very fact that there's a non-list-based syntax (although lists are used for terminals, that could easily be avoided) shows that

DCGs unsugar into lists, but the very fact that there's a non-list-based syntax (although lists are used for terminals, that could easily be avoided) shows that lists aren't actually essential. One has to pick some basic data structure, and lists are good for it, but they're not essential. (For example, one could use a lambda-calculus-based formalism, and then, if desired, encode lists in it in the usual way; or, as Prolog actually does it, encode lists as terms, as tempguy9999 (https://news.ycombinator.com/item?id=21772069 https://news.ycombinator.com/item?id=21772069) points out.