Ungolf my tinylisp code

Question

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). Two items may be separated by a single space; the space may also be omitted, unless it is necessary to separate two adjacent atoms. There will not be spaces anywhere else in the input; in particular, there will never be spaces immediately after an opening parenthesis or immediately before a closing parenthesis. 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
(1((2 3))4
(((((xyz)))))
(((((

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.
• The closing parenthesis at the end of a list should immediately follow the last element of the list, with no whitespace in between.

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))))))

I/O requirements and clarifications

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. You may not take input as a nested list; parsing the input is part of the challenge.

Output may be a multiline string; it may also be a list of strings, each string representing one line. It may optionally contain trailing spaces and/or leading or trailing newlines. It may not contain extra leading spaces.

The input will always represent 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.

Reference solution

Here's a reference solution in Python 3: Try it online!

Test cases

()
=>
()

(load library
=>
(load library)

(q(1 2
=>
(q (1 2))

(q((1)(2
=>
(q
 ((1) (2)))

(q '"""\
=>
(q '"""\)

(((((
=>
((((()))))

(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)))))))

This is code-golf; the shortest answer in each language (in bytes) wins.

Answer 1

tinylisp, 1022 bytes

(load library
(d ? contains?
(d r reverse
(d O last
(d _(q((S T C)(i S(i(e(h S)32)(_(t S)(i C(c(r C)T)T)())(i(?(q(40 41))(h S))(_(t S)(c(h S)(i C(c(r C)T)T))())(_(t S)T(c(h S)C))))(r(i C(c(r C)T)T
(d @(q((T A D)(i T(@(t T)(c(+(w T)D)A)(+(w T)D))(r(c(+(w T)D)A
(d w(q((T)(-(e(h T)40)(e(h T)41
(d #(q((T A)(i A(#(c 41 T)(- A 1))(r T
(d E(q((T)(max(@ T()0
(d p(q((L A)(i A(p(c 32 L)(- A 1))L
(d n(q((D T A)(i(l 0(h D))(n(t D)(t T)(c(h T)A))(r(c(h T)A
(d N(q((T)(n(@ T()0)T(
(d H(q((T A)(i T(i(*(e(h T)40)(e(cadr T)41))(H(t(t T))(c(q(40 41))A))(H(t T)(c(h T)A)))(r A
(d W(q((L)(i(c()L)L(c L(
(d :(q((I L)(i I(:(- I 1)(t L))L
(d ;(q((L)(:(s(last-index(r(@(r L)()0))1)1)L
(d }(q((D T)(i(l 0(h D))(}(t D)(t T))(t T
(d f(q((T S P)(i T(f(t T)(concat S(i(e(h T)41)(c 41())(i(+(l(E(N(concat(; P)T)))3)(*(not((q((T)(}(@ T()0)T)))(t(; P))))(l(E(N T))2)))(p(W(h T))(- 1(?(q(()40))(O P))))(i(e(O P)40)(W(h T))(c 10(p(W(h T))(O(@ P()0))))))))(insert-end(h T)P))S
(d F(q((S)(string(f(H((q((T)(#(r T)(last(@ T()0)))))(_(chars S)()()))())()(

Try it online!

This took several hours days, but now it actually works.

This emits a couple of errors, which I think are unavoidable, and now a lot more which are avoidable.

-18 thanks to DLosc.

Because tinylisp doesn't have string literals, you'll need to pass your input through this python script.

Ungolfed.

I only sorta understand this, but here's the basic algorithm the code follows:

• Convert the string to a list of characters for easier manipulation.

• Parse the string into a list of tokens

  • Parentheses are left on their own, other tokens are grouped into lists.

• Iterate through the string, keeping a list of the previous tokens:

  • If it's a ), immediately append it. Else:
  • If:
    • Backtrack through the previous tokens to the start of the parent expression.
    • Use this index to get the depth of the parent expression, is it less than 3?
  • or:
    • Backtrack to the parent expression
    • Remove the first parenthesis and remove the first expression after that.
    • Is it empty?
    • and:
      • is the current expression depth less than 2?
  • If so, this token should go on the same line, possibly with a space.
  • Else, it should be on a new line - get the depth of the current expression and indent by that.

• Finally, return the string.

Answer 2

Python3, 629 bytes:

import re
d=lambda x,c=0:c if type(x)!=list or not x else max(d(i,c+1)for i in x)
def p(s):
 r=[];S=str.lstrip
 while s:
  if(c:=s[0])==')':s=S(s[1:]);break
  if c=='(':s=(l:=p(s[1:]))[1];r+=[l[0]]
  else:r+=[l:=re.findall('[^() ]+',s)[0]];s=S(s[len(l):])
 return r,S(s)
def f(r,t=0):
 j=lambda x:x if type(x)!=list else'()'
 k,s=[],0
 if all(d(i)<2 for i in r):k=[f(i,t+1)if d(i)else j(i)for i in r]
 else:
  for i,a in enumerate(r):
   D=d(a);F=f(a,t+1)if D else j(a)
   if not i:k+=[F]
   elif i==1 and D<2:k+=[F]
   else:k+=['\n'+' '*(t+1)+F]
 return'('+' '.join(k)+')'
g=lambda x:f(p(x+')'*((c:=x.count)('(')-c(')')))[0][0])

Try it online!

Answer 3

Python 3, 388 bytes

Basically a golfed version of the reference solution @DLosc gave

import re
k=" "
def p(e,*t,l=0):
 for n in e:
  if")"==n:break
  if")">n:z=p(e);l=max(l,z[0]+1);t+=z,
  else:l=max(l,1);t+=n,
 return[l,*t]
t=p(iter(re.findall("[^() ]+|\S",input())[1:]))
def f(t,d=k):
 if[*t]==t:
  r="(";s=[f(i,d+k)for i in t[1:]]
  if t[0]>2:
   if len(t)>2and""in t[2]or t[2][0]<2:r+=s[0]+k;s=s[1:]
   q="\n"+d
  else:q=k
  return r+q.join(s)+")"
 return t
print(f(t))

Try it online!

The regex used in the code [^() ]+|\S is the a shorter way of writing the regex [()]|[^() ]+ given in the question by 2 bytes

[*t]==t is a sneaky trick to cut back 6 bytes instead of type(t)==list

""in t[2] is another trick to cut down 7 bytes instead of type(t[2])!=list

-3 thx to @pxeger

-1 thx to @aidenchow

Answer 4

Retina 0.8.2, 330 bytes

^((\()|(?<-2>\))|[^()])+
$&$#2$*)
[^ (](?=\()|\)(?=[^) ])
$& 
{%`^(( *)\(+?([^() ]+ |((\()|(?<-5>\))|[^()])+(?(5)^) )+)(\(([^() ]+ |\(\) )*\([^)])
$1¶$2 $6
 ¶
¶
%+`^(( *)\(([^() ]+|((\()|(?<-5>\))|[^()])+(?(5)^))( [^() ]+| \([^()]+\))+)( [^() ]+| \([^()]+\))+$
$1¶$2$7
%+`^(( *)\(([^() ]+|((\()|(?<-5>\))|[^()])+(?(5)^))\)) 
$1¶$2

Try it online! Link includes test cases. Explanation:

^((\()|(?<-2>\))|[^()])+
$&$#2$*)

Use a .NET balancing group to count how many extra (s there are and append that many trailing )s.

[^ (](?=\()|\)(?=[^) ])
$& 

Insert spaces before (s and after )s where necessary.

{`

Repeat until no more transforms can be made.

%`^(( *)\(+?([^() ]+ |((\()|(?<-5>\))|[^()])+(?(5)^) )+)(\(([^() ]+ |\(\) )*\([^)])
$1¶$2 $6
 ¶
¶

Split lists of nesting level 3 or more.

%+`^(( *)\(([^() ]+|((\()|(?<-5>\))|[^()])+(?(5)^))( [^() ]+| \([^()]+\))+)( [^() ]+| \([^()]+\))+$
$1¶$2$7

For those lists, where there are only lists of nesting level 0 or 1 left, put all but the first on their own line. (We need to check explicitly to ensure that the list was in fact split in the first place.)

%+`^(( *)\(([^() ]+|((\()|(?<-5>\))|[^()])+(?(5)^))\)) 
$1¶$2

Lists of nesting level 0 or 1 after a list of nesting level 2 or more also need to go on their own line. (We know they can't have also nesting level 2 or more because they would have been split off earlier, so we don't actually need to check their nesting level.)

Answer 5

Charcoal, 166 bytes

⊞υ⟦⟧≔ωηＦ⁺θ×)⁻№θ(№θ)«Ｆ№( )ιＦ›ηω«⊞§υ±¹⟦η¹⟧≔ωη»≡ι ω(⊞υ⟦⟧)«≔∨⊟υ⟦⟦ω⁰⟧⟧ι≔∧⊖Ｌι›³§§ι¹±¹δ≔⌈Ｅι⊕⊟κζＦ›⁴ζ≔⊖Ｌιδ≔Ｅ§ι⁰⁺§ (¬λκεＦδ⊞ε⁺⁺⊟ε ⊟§ι⊕κＦΦι›λδＦκ⊞ε⁺ λ⊞ε⁺⊟ε)⊞εζ⊞§υ±¹ε»≔⁺ηιη»✂⊟⊟υ⁰±¹

Try it online! Link is to verbose version of code. Explanation:

⊞υ⟦⟧

Add a dummy container to the predefined empty list to hold the final result.

≔ωη

Start off with no atom.

Ｆ⁺θ×)⁻№θ(№θ)«

Append enough trailing )s to balance the input and loop over its characters.

Ｆ№( )ιＦ›ηω«⊞§υ±¹⟦η¹⟧≔ωη»

If the current character is one of ( ) then push any current token to the most recent expression. (Note that my nesting levels are one greater than those used by the question, because the nesting level of () evaluates to 1.)

≡ι ω

If the current character is a space then do nothing more at this point.

(⊞υ⟦⟧

If the current character is a ( then start a new subexpression.

)«

If the current character is a ):

≔∨⊟υ⟦⟦ω⁰⟧⟧ι

Get the latest expression, or an empty token if there wasn't one. (Since this makes () contain an empty token with a nesting level of 0, its nesting level evaluates to 1.)

≔∧⊖Ｌι›³§§ι¹±¹δ

Calculate whether the second term should be concatenated to the end of the first.

≔⌈Ｅι⊕⊟κζ

Calculate the depth of this term.

Ｆ›⁴ζ≔⊖Ｌιδ

If this term is shallow enough then concatenate all the terms together.

≔Ｅ§ι⁰⁺§ (¬λκε

Indent the first term, except for the first line, which is prefixed with a leading ( instead.

Ｆδ⊞ε⁺⁺⊟ε ⊟§ι⊕κ

Concatenate the desired number of terms to the first term.

ＦΦι›λδＦκ⊞ε⁺ λ

Indent and append any remaining terms.

⊞ε⁺⊟ε)

Append a final ) to the last line.

⊞εζ

Append the nesting level to this term.

⊞§υ±¹ε

Append this term to its parent expression.

»≔⁺ηιη

For any other character, append it to the current token.

»✂⊟⊟υ⁰±¹

Output the pretty-printed expression, excluding its nesting depth.