7
\$\begingroup\$

This challenge is to golf an implementation of SKI formal combinator calculus.

Definition

Terms

S, K, and I are terms.

If x and y are terms then (xy) is a term.

Evaluation

The following three steps will be repeated until none of them apply. In these, x, y, and z must be terms.

(Ix) will be replaced by x

((Kx)y) will be replaced by x

(((Sx)y)z) will be replaced by ((xz)(yz))

Input

A string or array, you do not have to parse the strings in the program.

The input is assumed to be a term.

If the simplification does not terminate, the program should not terminate.

Examples

(((SI)I)K) should evaluate to (KK) ((((SI)I)K) > ((IK)(IK)) > (K(IK)) > (KK))

The evaluation order is up to you.

This is . Shortest program in bytes wins.

\$\endgroup\$
  • \$\begingroup\$ Are the inputs strings we have to parse, or can we have them in a tree or similar? \$\endgroup\$ – xnor Jun 8 at 21:03
  • \$\begingroup\$ They don't have to be parsed, you can have them in a tree. \$\endgroup\$ – nph Jun 8 at 21:04
  • 4
    \$\begingroup\$ Some example please. \$\endgroup\$ – Noodle9 Jun 8 at 21:27
  • 1
    \$\begingroup\$ Should we assume the input is a term (i.e. the behavior is unspecified if the input is not a term)? Is a non-strict evaluation order required so that ((KI)(((SI)I)((SI)I))) must terminate, or is such an expression allowed to diverge? \$\endgroup\$ – Anders Kaseorg Jun 8 at 22:53
  • 3
    \$\begingroup\$ @nph The point is that ((KI)(((SI)I)((SI)I))) can either be reduced to I with one K step (leading to termination) or to ((KI)(((SI)I)((SI)I))) with one S 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\$ – Anders Kaseorg Jun 8 at 23:23
5
\$\begingroup\$

Wolfram Language, 63 bytes

#//.{{I,x_}->x,{{K,x_},y_}->x,{{{S,x_},y_},z_}->{{x,z},{y,z}}}&

Try it online!

God, I love pattern matching in Wolfram Language. Represents (xy) as {x,y} (a list of two elements).

Alternatively, if we represent (xy) with x>y, we can do it in 55 bytes.

#//.{I>x_->x,(K>x_)>y_->x,((S>x_)>y_)>z_->(x>z)>(y>z)}&

Try it online!

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

perl -p, 135 bytes

1 while s/\((I)(?<T>[SKI]|\((?&T)(?&T)\))\)|\(\((K)((?&T))\)(?&T)\)|\(\(\((S)((?&T))\)((?&T))\)((?&T))\)/$1?$2:$3?$4:"(($6$8)($7$8))"/e

Try it online!

Just a regexp applying the three rules. Reads a string from STDIN, applies all the rules until there's nothing to apply, writes the result to STDOUT.

(?<T>[SKI]|\((?&T)(?&T)\)) is a recursive pattern recognizing a term. The rest of the pattern is just a mechanically translation of the given rules.

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Retina 0.8.2, 171 bytes

{T`()`<>
<<<S((\w|(<)|(?<-3>>))+)>((\w|(<)|(?<-6>>))+)>((\w|(<)|(?<-9>>))+>)
<<$1$7<$4$7>
<<K((\w|(<)|(?<-3>>))+)>(\w|(<)|(?<-5>>))+>
$1
<I((\w|(<)|(?<-3>>))+)>
$1
T`<>`()

Try it online! Explanation:

{`

Repeat the transformations until there are no more available.

T`()`<>
T`<>`()

Temporarily switch ()s with <>s to avoid having to quote numerous ()s.

<<<S((\w|(<)|(?<-3>>))+)>((\w|(<)|(?<-6>>))+)>((\w|(<)|(?<-9>>))+>)
<<$1$7<$4$7>

Process S operations. (The last capture includes the trailing > in order to avoid repeating it in the replacement.)

<<K((\w|(<)|(?<-3>>))+)>(\w|(<)|(?<-5>>))+>
$1

Process K operations.

<I((\w|(<)|(?<-3>>))+)>
$1

Process I operations.

The (\w|(<)|(?<-[N]>>))+ construct is an example of a .NET regex balancing group. It tries to match characters, but it's only allowed to match >s if it's already seen the same number of <s. (N needs to be replaced with the number of the (<) capturing group. As written it fails if the <>s aren't balanced correctly, but you can use conditional regex to check for that.)

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 92 bytes

ΔDŒʒ„)(©S¢Ë}ʒÁ®Å?y®S¢O_~}©vy"(Iÿ)"y:}®ãvy`"((Kÿ)ÿ)"yθ:}®3ãvy`"(((Sÿ)ÿ)ÿ)"yĆ1.I`"((ÿÿ)(ÿÿ))":

05AB1E has no regex, so uses a brute-force approach using all valid substrings. Because of this, it's extremely slow for larger test cases.

Executes in the order (Ix)((Kx)y)(((Sx)y)z).

Try it online or verify a few more test cases.

Explanation:

Δ                        # Continue until the result no longer changes:
 D                       #  Duplicate the current string
                         #  (will use the implicit input-string in the first iteration)
  Π                     #  Take all its substrings
   ʒ                     #  Filter those substrings by:
    „)(                  #   Push ")("
       ©                 #   Store it in variable `®` (without popping)
        S                #   Convert it to a list of characters: [")","("]
         ¢               #   Count each in the substring
          Ë              #   Check that the counts are equal for both
   }ʒ                    #  After the filter: filter once more:
     Á                   #   Rotate the substring once towards the left
      ®                  #   Push string ")(" from variable `®`
       Å?                #   Check if the rotated substring starts with this
     y                   #   Push the substring again
      ®S¢                #   Count the [")","("] again
         O_              #   Check that the sum of both counts is 0
     ~                   #   Check if either of the two was truthy
    }©                   #  After the filter: store it in variable `®` (without popping)
 v                       #  Loop over each valid substring:
  y                      #   Push the substring
   "(Iÿ)"                #   Push this string, with the `ÿ` automatically filled with
                         #   the substring
  y                      #   Push the substring again
  :                      #   Replace all "(Ia)" with "a"
 }®                      #  After the loop: push the list of valid substrings again
   ã                     #  Take all pairs of valid substrings
    v                    #  Loop over these pairs:
     y`                  #   Pop and push the pair separated to the stack
       "((Kÿ)ÿ)"         #   Push this string, with the `ÿ` automatically filled again
     yθ                  #   Pop and push only the last substring of the pair: [a,b] → b
     :                   #   Replace all "((Kb)a)" with "b"
 }®                      #  After the loop: push the list of valid substrings again
   3ã                    #  Take all triplets of valid substrings this time
     v                   #  Loop each each triplet:
      y`                 #   Pop and push the triplet separated to the stack
        "(((Sÿ)ÿ)ÿ)"     #   Push this string, with the `ÿ` automatically filled again
      y                  #   Push the current triplet again
       Ć                 #   Enclose; append its own head: [a,b,c] → [a,b,c,a]
        1.I              #   Get the 0-based 1st permutation: [a,b,c,a] → [a,b,a,c]
           `             #   Pop and push the quartet separated to the stack
            "((ÿÿ)(ÿÿ))" #   Push this string, with the `ÿ` automatically filled again
      :                  #   Replace all "(((Sc)b)a)" with "((ca)(ba))"
                         # (after which the result is output implicitly)
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Haskell, 83 bytes

data T=S|K|I|T:$T
e(x:$y)=e x!e y
e x=x
I!x=x
K:$x!_=x
S:$x:$y!z=x!z!(y!z)
x!y=x:$y

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 666 616 518 483 476 bytes

Who doesn't love classy, Arthur Whitney-styled code? No regular expressions involved, only clever parsing and evaluation.

PS: Yes, obviously, a few bytes can be shaved off, but for the artistic style of the obfuscated code, I'll keep them. Also for the byte count :p. Also, this code utilizes undefined behaviour in hope that nothing will break (hopefully).

@ceilingcat insisted on golfing it down from 666 bytes, so here is the golfed version:

#define J putchar
#define H O->a
#define G H->a
#define K O->b
typedef struct x{struct x*a,*b;int q;}Y;Y*O;z=1;A(q){O=calloc(6,4);O->q=q;}h(Y*O){Y*u;O=H&&H->q==2?z=K:H&&G&&G->q==1?z=H->b:H&&G&&G->a&&!G->a->q?u=A(3),(u->a=A(3))->a=G->b,(u->b=A(3))->a=H->b,u->a->b=u->b->b=K,z=u:(O->q==3?H=h(H),K=h(K):0,O);}r(x){Y*O;x=getchar()-73;x=x+33?A(x?x!=10:2):!getchar(K=r(H=r(O=A(3))))+O;}q(Y*O){O&&J(O->q["SKI "],O->q-3||J(41,q(K),q(H),J(40)));}main(){Y*O=r();for(;z;O=h(O))z=0;q(O);}

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

sed, 89

:1;s|(I\(.\))|\1|g;t1;s|((K\(.\)).)|\1|g;t1;s|(((S\(.\))\(.\))\(.\))|((\1\3)(\2\3))|g;t1
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.