It's not really different than Lisp. Lists are not a native data representation on any computer other than a Lisp Machine, and S-exprs are a textual representa

It's not really different than Lisp. Lists are not a native data representation on any computer other than a Lisp Machine, and S-exprs are a textual representation of a list, not a list itself. Also, most realistic Lisps still admit other primitive types like numbers, strings, symbols, and booleans. Many also have hashtables, structs, and binary blobs. Nobody programs with numbers represented by Peano axioms. Nevertheless, Lisp is still a very useful primitive for understanding computation, because the means of combination of these primitives are all themselves represented with Lisps. That makes for a very succinct definition for the rules that define computation, because there are fewer special cases to handle. Likewise, it makes it easy to write program-manipulating-programs, because there are fewer special cases to handle. In theory a graph-based language could have similar benefits. Most compilers already represent programs as graphs internally: there are call graphs, control flow graphs, data flow graphs, type graphs, etc. You could imagine a language that tries to make graph construction & manipulation very succinct, and then see how far it gets you. Sure, at some point you have to implement on real hardware, but you can hide the actual implementation, just like the sophisticated compiler techniques used to transform lists into efficient machine code are hidden from a Lisp programmer who just wants to write some macros.