I've just posted some additional examples of sweet-expressions for even more Lisp dialects, at: http://www.dwheeler.com/readable/version02.html
So my examples now cover these dialects: Scheme, Common Lisp, Arc, ACL2, PVS, BitC, AutoCAD Lisp (AutoLisp), Emacs Lisp, SUO-KIF, Scheme Shell (Scsh), GCC Register Transfer Language (RTL), MiddleEndLispTranslator (MELT), and Satisfiability Modulo Theories Library (SMT-LIB). I think these samples from different dialects show that sweet-expressions are NOT tied to any specific semantic. Past "readable" Lisp notations (M-expressions, Logo, etc.) all failed in part because they were too tied to a particular semantic. Thus they fell apart once you started to use lists seriously (e.g., in macros). By showing that samples in these other dialects can be reasonably represented in sweet-expressions, I can be more confident that sweet-expressions are useful while not tied to a particular semantic. Below is a cut-and-paste for SUO-KIF, Scsh (Scheme Shell), Paul Graham's Arc, RTL, MELT, and Satisfiability Modulo Theories Library (SMT-LIB). These are pretty different, and yet they SEEM to work well. Comments welcome. If the below is hard to read, look at the web page: http://www.dwheeler.com/readable/version02.html --- David A. Wheeler ============================================================= SUO-KIF Standard Upper Ontology Knowledge Interchange Format (SUO-KIF) is a language designed for use in the authoring and interchange of knowledge, e.g., by the Suggested Upper Merged Ontology (SUMO). Original Lisp Here's the original Lisp of a trivial example, "All farmers like tractors": (forall (?F ?T) (=> (and (instance ?F Farmer) (instance ?T Tractor)) (likes ?F ?T))) Infix non-default Without using any infix operators, we can get a nicer result: forall (?F ?T) => and instance(?F Farmer) instance(?T Tractor) likes ?F ?T However, both "and" and "=>" (implies) are traditionally used as infix operators, rather than prefix operators. Using {...}, we can use them in that traditional manner: forall (?F ?T) {{instance(?F Farmer) and instance(?T Tractor)} => likes(?F ?T)} or forall (?F ?T) { {instance(?F Farmer) and instance(?T Tractor)} => likes(?F ?T)} Scsh (Scheme Shell) Scheme shell is an implementation of Scheme, plus a high-level process notation for doing shell-script-like tasks (running programs, establishing pipelines, and I/O redirection). Scsh's documentation (section 1.4) notes that scsh is (currently) "primarily designed for the writing of shell scripts - programming. It is not a very comfortable system for interactive command use: the current release lacks job control, command-line editing, a terse, convenient command syntax, and it does not read in an initialisation file analogous to .login or .profile." Most of these limitations can be easily fixed by reusing existing code; e.g., job control code can be copied from other shells, there are trivial libraries (such as readline) that implement command-line editing, and reading an initialization file is trivially done. But the "convenient command syntax" is a serious stumbling block to using scsh as a shell, and that is not trivially fixed by simply reusing arbitrary code. It can be fixed by using sweet-expressions. Original Lisp In traditional shells, you might write a command like this: gunzip < paper.tex.gz | detex | spell | lpr -Ppulp & In scsh, this could be written as: (& (| (gunzip) (detex) (spell) (lpr -Ppulp)) ; background a pipeline (< paper.tex.gz)) ; with this redirection Infix non-default In sweet-expressions, the same expression of scsh can be written as: & | gunzip() detex() spell() lpr(-Ppulp) ; background a pipeline < paper.tex.gz ; with this redirection or as: & {gunzip() | detex() | spell() | lpr(-Ppulp)} ; background a pipeline < paper.tex.gz ; with this redirection I think it's better if punctuation-only names are used primarily for infix operators; it helps with consistency. At the least, I'd rename "&" into the synonym "background". Then it becomes: background {gunzip() | detex() | spell() | lpr(-Ppulp)} ; background a pipeline < paper.tex.gz ; with this redirection Arc Paul Graham is developing a new dialect of Lisp named Arc; Paul Graham's Arc site and Arclanguage.org have more information. Semantically, it's a lot like a special combination of Common Lisp and Scheme. For example, like Common Lisp, both "false" and "empty list" are nil (Scheme has separate objects for false and the empty list). But like Scheme, Arc has a single namespace (it's a Lisp-1), as compared with Common Lisp (which is a Lisp-2). Arc has some cool ideas, but Paul Graham seems to be very busy on other things, so an informal community called 'Anarki' has formed to evolve Arc. (It uses "=" for assignment, which I think is unfortunate because "=" is often confused with is-equal-to, but anyway...). A good place to start is the Arc tutorial. In Arc, [...] has a special meaning. More specifically, "[... _ ...]" is an abbreviation for "(fn (_) (... _ ...))". For example: arc> (map [+ _ 10] '(1 2 3)) (11 12 13) This makes me think that sweet-expressions should not mandate that [...] be equivalent to (...), necessarily, in sweet-expressions. Instead, the meaning of [...] may be somewhat language-dependent in sweet-expressions; a Scheme using sweet-expressions might consider [...] equivalent to (...), since the normal Scheme R6 does, but it doesn't necessarily follow that this must be true for all languages. If you disable sweet-expression's definition that [...] is the same as (...), it looks like Arc and sweet-expressions could be easily used together. Original Lisp The Arc tutorial has several really tiny examples; let's pick out a few and put them in one place: (+ (+ 1 2) (+ 3 (+ 4 5))) (def average (x y) (/ (+ x y) 2)) (let x 10 (while (> x 5) (= x (- x 1)) (pr x))) (mac repeat (n . body) `(for ,(uniq) 1 ,n ,@body)) (def firstn (n xs) (if (and (> n 0) xs) (cons (car xs) (firstn (- n 1) (cdr xs))) nil)) (def nthcdr (n xs) (if (> n 0) (nthcdr (- n 1) (cdr xs)) xs)) (def tuples (xs (o n 2)) (if (no xs) nil (cons (firstn n xs) (tuples (nthcdr n xs) n)))) (def mylen (xs) (if (no xs) 0 (+ 1 (mylen (cdr xs))))) (mac n-of (n expr) (w/uniq ga `(let ,ga nil (repeat ,n (push ,expr ,ga)) (rev ,ga)))) Infix non-default Here are the sweet-expression equivalents: {{1 + 2} + {3 + {4 + 5}}} def average (x y) {{x + y} / 2} let x 10 while {x > 5} {x = {x - 1}} pr x mac repeat (n . body) `for ,uniq() 1 ,n ,@body def firstn (n xs) if {{n > 0} and xs} cons car(xs) firstn({n - 1} cdr(xs)) nil def nthcdr (n xs) if {n > 0} nthcdr {n - 1} cdr(xs) xs def tuples (xs (o n 2)) if no(xs) nil cons firstn(n xs) tuples nthcdr(n xs) n def mylen (xs) if no(xs) 0 {1 + mylen(cdr(xs))} mac n-of (n expr) w/uniq ga `let ,ga nil repeat ,n push(,expr ,ga) rev ,ga Note the last macro; even though it's short, the original required 4 closing parentheses to complete it, while the sweet-expression required none. RTL (GCC Register Transfer Language) The GNU Compiler Collection (GCC) has an internal structure for representing programs (at a low level), the GCC Register Transfer Language (RTL). It's often useful to print out RTL; it's useful for debugging, and other tools use it too (such as RTL-check and Egypt. Here's a summary of some RTL semantics. RTL has a Lisp-like external representation, which is why it's noted here. Original Lisp "Compilation of Functional Programming Languages using GCC - Tail Calls" by Andreas Bauer, has some RTL examples. Section 2.3 shows a trivial C program: int foo () { return bar (5); } Here is an incomplete translation to RTL expressions (before any sibling call optimization): (call_insn 19 9 20 (nil) (call_placeholder 16 10 0 0 (call_insn 17 16 18 (nil) (set (reg:SI 0 eax) (call (mem:QI (symbol_ref:SI ("bar")) [0 S1 A8]) (const_int 4 [0x4]))) -1 (nil) (expr_list:REG_EH_REGION (const_int 0 [0x0]) (nil)) (nil))) -1 (nil) (nil) (nil)) (insn 20 19 21 (nil) (set (reg:SI 58) (reg:SI 59)) -1 (nil) (nil)) (jump_insn 21 20 22 (nil) (set (pc) (label_ref 25)) -1 (nil) (nil)) (barrier 22 21 23) (note 23 22 27 NOTE_INSN_FUNCTION_END) (insn 27 23 28 (nil) (clobber (reg/i:SI 0 eax)) -1 (nil) (nil)) (insn 28 27 25 (nil) (clobber (reg:SI 58)) -1 (nil) (nil)) (code_label 25 28 26 6 "" [0 uses]) (insn 26 25 29 (nil) (set (reg/i:SI 0 eax) (reg:SI 58)) -1 (nil) (nil)) (insn 29 26 0 (nil) (use (reg/i:SI 0 eax)) -1 (nil) (nil)) Infix non-default Below is a sweet-expression equivalent. One question: Should lists here be represented as x(...) or (x ...)? They are equivalent; it's merely a matter of what is clearer. The first parameter is a special marker, so it's reasonable to represent them as x(...); besides, it helps to show off sweet-expressions. I won't do that with strings; a list beginning with a string will be shown as ("x"). RTL isn't really typical Lisp, but has its own syntactic extensions. I'll show RTL bracketed expressions [...] exactly as they would be in RTL (leaving them as-is). So here's one approach to representing RTL: call_insn 19 9 20 nil() call_placeholder 16 10 0 0 call_insn 17 16 18 nil() set reg:SI(0 eax) call(mem:QI(symbol_ref:SI(("bar")) [0 S1 A8]) const_int(4 [0x4])) -1 nil() expr_list:REG_EH_REGION const_int(0 [0x0]) nil() nil() -1 nil() nil() nil() insn 20 19 21 nil() set(reg:SI(58) reg:SI(59)) -1 nil() nil() jump_insn 21 20 22 nil() (set pc() (label_ref 25)) -1 nil() nil() barrier 22 21 23 note 23 22 27 NOTE_INSN_FUNCTION_END insn 27 23 28 nil() clobber(reg/i:SI(0 eax)) -1 nil() nil() insn 28 27 25 nil() clobber(reg:SI(58)) -1 nil() nil() code_label 25 28 26 6 "" [0 uses] insn 26 25 29 nil() set(reg/i:SI(0 eax) reg:SI(58)) -1 nil() nil() insn 29 26 0 nil() use(reg/i:SI(0 eax)) -1 nil() nil() MELT (MiddleEndLispTranslator) MELT (MiddleEndLispTranslator) is a "high-level Lisp-like language designed to fit very closely in the [GNU Compile Collection (GCC)] internal representations, thru an automated translation of MELT code into GCC specific C code, compiled by a C compiler (usually some GCC) and then loaded as plugins. This enables easier development of high-level static analysis and transformation, working on GCC middle end representation (GIMPLE tuple)." If you're interested in the general topic of gcc plug-ins, see "Plugging into GCC" (lwn.net). The MELT work is partly funded by the French Ministery of Economy, thru ITEA within the GlobalGCC (GGCC) project. The lead, Basile Starynkevitch, has contributed his GCC contributions using a copyright transfer signed by CEA to FSF. It was presented at the GCC Summit 2007. A special MELT branch was created on February 19, 2008. Semantically, MELT is a "Lisp1" Lisp dialect (so it's more like Scheme than like Common Lisp regarding names and bindings). You can define primitives, which get translated to C, compiled, and linked into the compiler during the compilation process. The (unboxed) integer addition is pre-defined in MELT as: (defprimitive +i (:long a b) :long "((" a ") + (" b "))") Where "the first :long occurrence describes the types of the formal arguments a and b, the second occurrence describes the result. There is an minimal object system (single-inheritance hierarchy, rooted at CLASS_ROOT... Tail-recursion is not handled (looping should use the forever keyword, and loops are can be exited)". Original Lisp Here is an example from the main MELT page. This is "a sample MELT function repeat-times [that applies] a function f to an argument x some specified n times. f and x are values, n is an unboxed long argument.": (defun repeat-times (f x :long n) ; n is an unboxed formal argument of type long (forever reploop ; infinite loop called reploop (if (<=i n 0) ; test if the unboxed n is negative (exit reploop)) ; exit the loop if yes (f x) ; call f (setq n (-i n 1)))) ; decrement n Infix non-default Here is a sweet-expression equivalent: defun repeat-times (f x :long n) ; n is an unboxed formal argument of type long forever reploop ; infinite loop called reploop if {n <=i 0} ; test if the unboxed n is negative exit reploop ; exit the loop if yes f x ; call f setq n -i(n 1) ; decrement n This is an interesting case regarding "infix default" vs. "infix non-default". The comparison operator here is "<=i" - and as a result, the comparison wouldn't be automatically detected by the proposed automatic infix detection rules. This is another argument for not trying to automatically detect infix operators; too often they will be missed, so don't bother. Instead, let the developer specify them using a single uniform syntax. Satisfiability Modulo Theories Library (SMT-LIB) The Satisfiability Modulo Theories Library (SMT-LIB) The major goal of the SMT-LIB initiative is to "establish a library of benchmarks for Satisfiability Modulo Theories, that is, satisfiability of formulas with respect to background theories for which specialized decision procedures exist... [these] have applications in formal verification, compiler optimization, and scheduling, among others... the initiative first aims at establishing a common standard for the specification of benchmarks and of background theories." The SMT-LIB syntax is "attribute-based and Lisp-like". It permits a syntactic category "user value", used for user-defined annotations or attributes, that start with an open brace "{" and end with a closed brace "}". Original Lisp The QF_RDL benchmarks's "check" subset includes this small benchmark as bignum_rd1.smt. I've re-indented the last lines slightly so that it fits inside the usual 80 columns: (benchmark bignum :source { SMT-COMP'06 Organizers } :notes "This benchmark is designed to check if the DP supports bignumbers." :status sat :difficulty { 0 } :category { check } :logic QF_RDL :extrafuns ((x1 Real)) :extrafuns ((x2 Real)) :extrafuns ((x3 Real)) :extrafuns ((x4 Real)) :formula (and (<= (- x1 x2) (/ 1 1000000000000000000000000000000000)) (<= (- x2 x3) (/ 1 2000000000000000000000000000000011)) (<= (- x3 x4) (~ (/ 1 1000000000000000000000000000000000))) (<= (- x4 x1) (~ (/ 1 2000000000000000000000000000000012))))) The indentation above is misleading, since "difficulty" isn't a part of ":status". So let's first use a reasonable indentation, trying to make it as readable as possible without changing Lisp syntax. Also, "user values" are written with {...}, which isn't standard Lisp; let's rewrite them as strings ("...."), since they have essentially the same role (they are uninterpreted data): (benchmark bignum :source "SMT-COMP'06 Organizers" :notes "This benchmark is designed to check if the DP supports bignumbers." :status sat :difficulty "0" :category "check" :logic QF_RDL :extrafuns ((x1 Real)) :extrafuns ((x2 Real)) :extrafuns ((x3 Real)) :extrafuns ((x4 Real)) :formula (and (<= (- x1 x2) (/ 1 1000000000000000000000000000000000)) (<= (- x2 x3) (/ 1 2000000000000000000000000000000011)) (<= (- x3 x4) (~ (/ 1 1000000000000000000000000000000000))) (<= (- x4 x1) (~ (/ 1 2000000000000000000000000000000012))))) Infix non-default One problem with this data is that there is an implied syntax that isn't actually embedded in the Lisp formatting. Namely, an atom beginning with ":" is followed by a parameter in this syntax. A pretty-printer that wasn't specially rigged with this convention would not show this format in a pretty way, and a normal sweet-expression reader wouldn't know about this either. This means that the "obvious" sweet-expression notation isn't right. E.G., this fragment: benchmark bignum :source "SMT-COMP'06 Organizers" :notes "This benchmark is designed to check if the DP supports bignumbers." :status sat Would be interpreted as: (benchmark bignum (:source "SMT-COMP'06 Organizers") (:notes "This benchmark is designed to check if the DP supports bignumbers.") (:status sat)) We could use this kind of formatting, but I find it ugly and counter-intuitive; it also wastes lots of space: benchmark bignum :source "SMT-COMP'06 Organizers" :notes "This benchmark is designed to check if the DP supports bignumbers." :status sat But this isn't really a problem. One way to make this "pretty" would be to use "(...)" at an outer level - such as with function-calling syntax - which disables indentation processing. Then, we can choose any indentation we like, just as we can in traditional Lisp syntax. We can still use {...} for infix operators. In our examples, I won't use "and" as an infix operator, because the sub-expressions are so long, but I will use infix for "<=", "-", and "/". I'll also use "~" (unary minus) as a one-parameter function. benchmark( bignum :source "SMT-COMP'06 Organizers" :notes "This benchmark is designed to check if the DP supports bignumbers." :status sat :difficulty "0" :category "check" :logic QF_RDL :extrafuns ((x1 Real)) :extrafuns ((x2 Real)) :extrafuns ((x3 Real)) :extrafuns ((x4 Real)) :formula and { {x1 - x2} <= {1 / 1000000000000000000000000000000000} } { {x2 - x3} <= {1 / 2000000000000000000000000000000011} } { {x3 - x4} <= ~({1 / 1000000000000000000000000000000000}) } { {x4 - x1} <= ~({1 / 2000000000000000000000000000000012})} ) The above looks reasonable enough. But if you were able to change the required expressions, you could make the structure of the parameters much clearer by connecting the parameter names and their values inside lists, instead of merely implying it through a naming convention. This would be an annoyance in traditional Lisp, because it'd require additional parentheses for each parameter, but this is a non-problem for sweet-expressions. If this was done, you could write it this way: benchmark bignum :source "SMT-COMP'06 Organizers" :notes "This benchmark is designed to check if the DP supports bignumbers." :status sat :difficulty "0" :category "check" :logic QF_RDL :extrafuns ((x1 Real)) :extrafuns ((x2 Real)) :extrafuns ((x3 Real)) :extrafuns ((x4 Real)) :formula and { {x1 - x2} <= {1 / 1000000000000000000000000000000000} } { {x2 - x3} <= {1 / 2000000000000000000000000000000011} } { {x3 - x4} <= ~({1 / 1000000000000000000000000000000000}) } { {x4 - x1} <= ~({1 / 2000000000000000000000000000000012})} --- David A. Wheeler ------------------------------------------------------------------------- This SF.Net email is sponsored by the Moblin Your Move Developer's challenge Build the coolest Linux based applications with Moblin SDK & win great prizes Grand prize is a trip for two to an Open Source event anywhere in the world http://moblin-contest.org/redirect.php?banner_id=100&url=/ _______________________________________________ Readable-discuss mailing list Readable-discuss@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/readable-discuss
