Full program. No use of regex.
∊{0=≡⍵:⍵
1⌽')(',∇¨⍵}{0=d←|≡⍵:⍵
'I'≡⊃⍵:⊃⌽⍵
(2≤d)∧'K'≡⊃⊃⍵:⊃⌽⊃⍵
(3≤d)∧'S'≡⊃∊⍵:x y,⍥⊂¨⊃⌽(((s x)y)z)←⍵
∇¨⍵}⍣≡⍎⍕{3⍴''''⍵}¨@{⍵∊⎕A}⍞
Try it online!
The program has three distinct parts:
- Input handling
- Evaluation
- Output formatting
Input handling
This part transforms the traditional SKI notation into a nest APL data structure.
⍎⍕{3⍴''''⍵}¨@{⍵∊⎕A}⍞
⍞
prompt for one line of input text
E.g. "(((SI)I)K)"
@{
…}
at locations where:
⍵
the argument characters
∊
are members of
⎕A
the uppercase Alphabet
{
…}¨
replace each one by:
3⍴
a cyclical reshape into length 3, of
''''⍵
the string consisting of a quote character ('
) and the argument character
E.g. ["(","(","(","'S'","'I'",")","'I'",")","'K'",")"]
⍕
stringify (this forces the now nested array into a flat space-separated string)
E.g. "((( 'S' 'I' ) 'I' ) 'K' )"
⍎
evaluate as APL code
E.g. [["SI","I"],"K"]
Evaluation
This part simplifies the data structure according to the three given rules.
{0=d←|≡⍵:⍵
'I'≡⊃⍵:⊃⌽⍵
(2≤d)∧'K'≡⊃⊃⍵:⊃⌽⊃⍵
(3≤d)∧'S'≡⊃∊⍵:x y,⍥⊂¨⊃⌽(((s x)y)z)←⍵
∇¨⍵}
0=
…:
if 0 equals
d←
the variable d
which is (assigned for later use)
|≡⍵
the absolute depth (maximum nesting level) of the argument:
⍵
return the argument as-is (this ensures the continuation of already evaluated parts)
'I'≡
…:
if "I"
matches
⊃⍵
the first element of the argument
⊃⌽⍵
return the last element of the argument (lit. the first of the reversed; this implements (Ix)
→ x
)
(2≤d)∧
…:
if 2 is less than or equal to the depth (d
), AND
'K'≡⊃⊃⍵
if "K"
matches the first element of the first element of the argument:
⊃⌽⊃⍵
return the last element of the first element of the argument (lit. the first of the reversed first; this implements ((Kx)y)
→ x
)
(3≤d)∧
…:
if 3 is less than or equal to the depth (d
), AND
'S'≡
if "S"
matches
⊃∊⍵
the first element of the enlisted (flattened) argument:
(((s x)y)z)←⍵
destructure the argument into individual variables
⊃⌽
pick the last element (lit. first of the reversed) from that (z
)
x y,⍥⊂¨
pair up each of x
and y
with that (this implements (((Sx)y)z)
→ ((xz)(yz))
)
∇¨⍵
otherwise, call self on each element of the argument
Output Formatting
Here, we transform the data structure back into traditional SKI notation.
∊{0=≡⍵:⍵
1⌽')(',∇¨⍵}
0=≡⍵:
if zero is equal to the depth of the argument (i.e. it is a single character)
⍵
return that as-is
∇¨⍵
otherwise, call self on each element of the argument
')(',
prepend ")("
1⌽
cyclically rotate one character from the front to the rear.
((KI)(((SI)I)((SI)I)))
must terminate, or is such an expression allowed to diverge? \$\endgroup\$((KI)(((SI)I)((SI)I)))
can either be reduced toI
with oneK
step (leading to termination) or to((KI)(((SI)I)((SI)I)))
with oneS
step (leading to divergence), and you need to specify whether the former is required, the latter is required, or either are allowed. I suggest “either”. See en.wikipedia.org/wiki/Evaluation_strategy. \$\endgroup\$I
and((SK)K)
, which behave the same way as functions but are different formal terms according to the specification. \$\endgroup\$