User:PkmnQ/Alternate Universe Underload

From Esolang
Jump to navigation Jump to search
This is still a work in progress. It may be changed in the future.

This is an exploration of what would change if Underload had its ~ command was replaced with a different command, which will be represented with _.

Command

_ : (x) (y) — y (x)
Similar to ^, the top element is popped from the stack and run as part of the program, however the new topmost element is ignored until the command ends.

(For those familiar with Forth, Factor, etc., if ~ is swap, _ is dip.)

Translating between Underload and Alternate Universe Underload

~ in Alternate Universe Underload is simply a_ Expressing _ in Underload can be done with ~a*^.

Examples

Fibonacci sequence

(()(*))((:^:S*a(^a(!)_)_*)_(/)S:^):^

Unlambda to Alternate Universe Underload

Alternate Universe Underload minimization

  • ^ is no longer necessary, since _ also allows for control flow. In fact, either ^ or _ can be implemented using the other:
^ = ()a__! or (())__!
_ = a(!(a(!)))a*:*^!a*^a(*)**a:*^!a*^ or a((!(a(!))))*:*^!a*^a(*)**a:*^!a*^
  • Removing ! is mostly the same as in regular Underload:
{(x)}    = ({x})a_ or (({x}))_
{xy...z} = {x}{y}...{z}
{x}      = (x)_ for all x made up of _:*S
{!}      = * or if you want nicely formatted junk, a_a* or (a)_*
{a}      = (aa(_)*)_ or (a(a_)*)_
{^}      = a_^
Call the whole program as (){P}.
  • ^ can also be easily removed from the above:
{^} = a_(()a___) or a_((())___)

Something that only uses :!()_

Removal of ! from :!()_ programs

Giving the running program an argument is no longer a problem unlike for :()^, since _ serves that purpose. The transformation used will have these properties:

  • (()){P} behaves equivalently to the null program, i.e. {P} deletes the (()) from the stack with no other effect.
  • ({A1})...({An})((())_){P} behaves equivalently to (A1)...(An)P.

One useful construction is this: 

<P|Q> = (()(P)(_Q)(_)())_____(())___
(())<P|Q> = (())(()(P)(_Q)(_)())_____(())___
          = ()(P)(_Q)(_)()(())____(())___
          = ()(P)(_Q)(_)()()___(())___
          = ()(P)(_Q)(_)_(())___
          = ()(P)_(_Q)(())___
          = P()(_Q)(())___
          = P()()(_Q)__
          = P()_Q()_
          = PQ
((())_)<P|Q> = ((())_)(()(P)(_Q)(_)())_____(())___
             = ()(P)(_Q)(_)()((())_)____(())___
             = ()(P)(_Q)(_)(())_()___(())___
             = ()(P)(_Q)()(_)()___(())___
             = ()(P)(_Q)()(_)__(())___
             = ()(P)(_Q)_()_(())___
             = ()_Q(P)(())___
             = Q()(P)__
             = QP()_
             = QP

The transformation also assumes the program always has at least one element on the stack (there is no way to delete a singular stack element using only _), which can be accomplished by prepending () to a program that never underflows the stack. The transformation rules are: 

{}    = (()())_____
{PQ}  = :({P})_{Q}
{:}   =
{!}   =
{(P)} = (({P}))_{:}((())())___
{_}   =

"Lambda" terms and abstraction elimination

The only change to the conversion rules is that this rule: 

[(x)-(A)(x)] = :[(x)-(A)]~

Changes to this: 

[(x)-A(x)] = :[(x)-(A)]_

There may be more optimizations that can be made specifically for Alternate Universe Underload (e.g. currently [(x)-Ax] becomes :[(x)-((A))]_*^ when :[(x)-(A)]_^ is shorter), but the above is the smallest change that is needed to make the conversion work.

Retrieved from "https://esolangs.org/w/index.php?title=User:PkmnQ/Alternate_Universe_Underload&oldid=144033"