Ungolf my tinylisp code
code-golf parsing whitespace lisp balanced-string
I like golfing in tinylisp:
(d M(q((x)(i x(i(disp x)0(M x))0
But I also like posting explanations with nicely formatted code:
(d M
(q
((x)
(i x
(i (disp x) 0 (M x))
0))))
Can you help me generate the ungolfed code for my explanations?
The task
Given a line of tinylisp code, return or output the same code, formatted to the following specifications:
Input syntax
Tokens in tinylisp are (, ), or any string of one or more printable ASCII characters excluding parentheses or space. (I.e. the following regex: [()]|[^() ]+.) A non-parenthesis token is called an atom. Spaces are ignored, except insofar as they separate tokens.
For this challenge, the input code will consist of a single parenthesized list containing 0 or more items. The items in the list may be either (arbitrarily deeply nested) lists or single-token atoms (or a mixture). There may be spaces between items; spaces may also be omitted if they are not necessary to separate two adjacent atoms. Closing parentheses at the end of the expression may be omitted.
Some examples:
()
(1 2 3)
(1 2 3
(1 (2)
(1(2
(1((2))3
(((((xyz)))))
(((((
Bare atoms, like xyz, do not have to be handled for this challenge.
Nesting levels
We define a nesting level for a tinylisp expression as follows:
- Atoms and the empty list
() have a nesting level of 0.
- A nonempty list has nesting level N+1, where N is the maximum nesting level of its items.
Some examples:
Expression Nesting level
() 0
(1 2 3) 1
(1 2 ()) 1
(1 (2)) 2
(1 ((2)) 3) 3
((((())))) 4
How to ungolf
To ungolf a tinylisp expression, first supply any missing closing parentheses. Then, add newlines and whitespace according to the following rules:
- For an expression of nesting level 0, do not add any whitespace.
- For a list of nesting level 1 or 2, make sure the elements of the list are separated by a single space.
- Lists of nesting level 3 or higher must be broken across multiple lines:
- The first element of the list should be on the same line as the opening parenthesis, with no whitespace in between.
- More specifically, the first element should begin on the same line. If the first item itself has nesting level 3 or higher, it will of course be spread over multiple lines itself.
- IF the second element of the list has nesting level 0 or 1, place it on the same line as the first, with a space in between; otherwise, if its nesting level is 2 or higher, place it on its own line.
- The third and subsequent elements of the list must each be on their own line.
- Elements on their own line must be indented by a number of spaces equal to how deeply they are nested in the expression. The top-level list should be indented 0 spaces, its elements 1 space, their elements 2 spaces, etc.
- Closing parentheses always go with the preceding list.
A worked example
Suppose this is our input:
(d E(q((n)(i(l n 2)(s 1 n)(E(s n 2
First, supply missing close-parens:
(d E(q((n)(i(l n 2)(s 1 n)(E(s n 2))))))
The outermost list has nesting level 6, so it must be split over multiple lines. Its second element is E (nesting level 0), so we keep that on the same line. We place the third element on its own line, indented by one space.
(d E
(q((n)(i(l n 2)(s 1 n)(E(s n 2))))))
The next list has nesting level 5. Its second element has nesting level 4, so it goes on its own line, indented by two spaces.
(d E
(q
((n)(i(l n 2)(s 1 n)(E(s n 2))))))
The next list has nesting level 4. Its second element has nesting level 3, so it goes on its own line, indented by three spaces.
(d E
(q
((n)
(i(l n 2)(s 1 n)(E(s n 2))))))
The next list has nesting level 3. Its second element has nesting level 1, so it goes on the same line as the first element, separated by a space. We place the third and fourth elements on their own lines, indented by four spaces.
(d E
(q
((n)
(i (l n 2)
(s 1 n)
(E(s n 2))))))
The list (s 1 n) has nesting level 1 and thus goes on one line. It has spaces between its elements, so it is already ungolfed.
The list (E(s n 2)) has nesting level 2 and thus goes on one line. It needs spaces between its elements.
Final result:
(d E
(q
((n)
(i (l n 2)
(s 1 n)
(E (s n 2))))))
Submission requirements
The input will always be a single (possibly nested) list. Thus, it will always start with (, never an atom. The number of opening parentheses will be greater than or equal to the number of closing parentheses. The input will not have any leading or trailing whitespace. The input will consist only of printable ASCII characters; in particular, it will not contain newlines or tabs.
Your solution may be a program or function. You may use any of the default I/O methods.
Input must be a string, a list of characters, or the nearest equivalent in your language.
Output may be a multiline string or a list of strings. It may optionally contain trailing spaces and/or a single trailing newline.
Examples
()
=>
()
(load library
=>
(load library)
(q(1 2
=>
(q (1 2))
(q((1)(2
=>
(q
((1) (2)))
(((((
=>
((((()))))
(d C(q((Q V)(i Q(i(l Q 0)0(i V(a(C(s Q(h V))V)(C Q(t V)))0))1
=>
(d C
(q
((Q V)
(i Q
(i (l Q 0)
0
(i V
(a
(C
(s Q (h V))
V)
(C Q (t V)))
0))
1))))
((q (g (c (c (q q) g) (c (c (q q) g) ())))) (q (g (c (c (q q) g) (c (c (q q) g) ())))))
=>
((q
(g
(c
(c (q q) g)
(c
(c (q q) g)
()))))
(q
(g
(c
(c (q q) g)
(c
(c (q q) g)
())))))
(d f(q((x y z p)(i p(i(l p 0)(f(s x p)y(a z p)0)(i x(f(s x 1)(a y 1)z(s p 1))(i y(f x(s y 1)(a z 1)(s p 1))(f x y z 0))))(c x(c y(c z(
=>
(d f
(q
((x y z p)
(i p
(i (l p 0)
(f (s x p) y (a z p) 0)
(i x
(f (s x 1) (a y 1) z (s p 1))
(i y
(f x (s y 1) (a z 1) (s p 1))
(f x y z 0))))
(c x
(c y (c z ())))))))
(def even? (lambda (num) (divides? 2 num)))
=>
(def even?
(lambda (num) (divides? 2 num)))
(def odd? (lambda (num) (not (divides? 2 num))))
=>
(def odd?
(lambda (num)
(not (divides? 2 num))))
(def divides? (lambda (divisor multiple) (if (negative? divisor) (divides? (neg divisor) multiple) (if (negative? multiple) (divides? divisor (neg multiple)) (if (less? multiple divisor) (zero? multiple) (divides? divisor (sub2 multiple divisor)))))))
=>
(def divides?
(lambda (divisor multiple)
(if (negative? divisor)
(divides? (neg divisor) multiple)
(if (negative? multiple)
(divides? divisor (neg multiple))
(if (less? multiple divisor)
(zero? multiple)
(divides? divisor (sub2 multiple divisor)))))))
Reference solution
Here's a reference solution in Python 3: Try it online!
Similar questions
I haven't found an exact duplicate yet. The closest is:
but there are many significant differences between that question and this: input on multiple lines vs. one line; different criteria for when to insert newlines; having to add missing close-parens; having to handle (), etc.
Other related questions:
Sandbox questions
- Is the TIO link enough for the reference solution, or should I put the code in the actual post?
- Is there any existing question that's close enough to be a duplicate?
- Which makes a better challenge: 1) input is a single expression on a single line, or 2) input is one or more expressions, each on its own line? #1 is the way it's currently written, and makes the challenge simpler; #2 would be more generally useful.
