Talk:Underload

From Esolang
Jump to: navigation, search

You can convert Capuirequiem programs to Underload:

~ = S
: = D
! = Z
* = C
( = [
) = ]
a = 91,WSC93,WC
^ = X
S = O

Alternate commands (which are closer to Underload functions, but it usually doesn't matter):

a = P
^ = V

I converted the Fibonaci program to show you how it works:

[91,WSC93,WC]{
[[][*]][SDXDOC}XSX}XSZSCSD[/]OX]DX

--Zzo38 03:30, 28 Nov 2006 (UTC)

That works apart from output; pathological programs like (S):^ can't be translated because they produce the wrong output. I've marked Capuirequiem as Turing-complete due to these equivalences. ais523 11:02, 28 Nov 2006 (UTC)

File extension?

First of all, I love this language! :D I'm absolutely beginner in functional programming languages but understood a few basics and managed to do a few simple programs: http://koti.mbnet.fi/yiap/index.php?page=langs&lang=Underload Definitely going to do more. So, what is the file extension of this language? I used 'unf', but I'd like to know what's the official one. --Keymaker 14:58, 28 Nov 2006 (UTC)

The spec doesn't care; I personally use .ul for Underload and .unl for Unlambda, but I don't think it matters all that much. ais523 16:28, 28 Nov 2006 (UTC)
Ok, so that's what I'll use then, too. :) --Keymaker 16:54, 28 Nov 2006 (UTC)

Unlambda functions in Underload

The page for Underload contains the "s", "k", "i" combinators of Unlambda in Underload, and I also put a "v" combinator, but they said it is useful with "c" as well. You can also convert all of the combinators code listed into Capuirequiem. Can the "c" be implemented in Capuirequiem as well if it cannot in Underload? --Zzo38 21:27, 22 Dec 2006 (UTC)

"c" is traditionally very hard to implement; it isn't a combinator but a flow-control operator. There are problems involved such as making a copy of the entire stack and emptying the stack (because the entire stack needs to be saved in the continuation). You also need to save the program as well as the stack, and most functional languages don't have a way to access the text of the running program. As for the other Unlambda operator, "d" isn't a combinator at all (just like "c") and has semantics that actually modify the action of the program (because `d`.xi doesn't output anything because the `.xi is never evaluated). ais523 16:56, 23 Dec 2006 (UTC)
Capuirequiem does happen to have function to make a copy of the stack and to access the text of the running program! The V command also deletes the previous text of the program and replace with a string, and X execute a subroutine in a string, but otherwise X and V usually act like the same when applied to a string. When W command is applied to a string it saves the state to the global-stack (which is a extra stack) and acts similarly to the backtracking INTERCAL. If you can do "d" then maybe the part directly after "d" belong in brackets and then after it apply then it will execute that part as well. --Zzo38 01:11, 24 Dec 2006 (UTC)
This page is a good one if you're interested in the "c" command (known as 'call/cc': [1]). ais523 13:08, 30 Dec 2006 (UTC)

99 bottles of beer

Hi, I just thought to inform that I've written '99 bottles of beer' program in Underload. I got the idea how to do it about two weeks ago or so, but there were various small bugs along the way, but finally it's completed. Here: http://koti.mbnet.fi/~yiap/programs/underload/99.ul

I've also updated my quine, which looks like this now:

(a(:^)*S):^

--Keymaker 21:23, 3 Jan 2007 (UTC)

Just a note here to let Keymaker know I'm impressed. (BTW, when I ran that it left a stray ()() on the stack; that's valid, but it might be neater to pop it at the end.) --ais523 10:33, 8 Jan 2007 (UTC)
Thanks! :) Actually the state of memory in the end is two cells -- a completely empty cell "" and the empty beer-count "()()". I could've removed them both, but my philosophy is that the state of memory doesn't matter when the program terminates, and thus I seldom clean the memory or zero it or anything like that, as there is no need to do so. --Keymaker 13:53, 8 Jan 2007 (UTC)

Is this self-modifying?

Should Underload be categorized self-modifying too? I'm a bit unsure what suffices and what doesn't. However, for example this program:

(:)(^)*:a~*^

creates another program, "(:^):^", and starts running it. And that program can't be found within the initial program string in its final form, only two characters of it, ':' and '^', and it's assembled out of those (and using some instructions such as 'a'). So, does this suffice for a self-modifying language? --Keymaker 08:32, 17 August 2007 (UTC)

It's about as self-modifying as Muriel is; neither currently has the category. I think it's probably just a matter of terminology; I suppose the original program doesn't change, it just makes copies of itself which are different. (For instance, ECMAScript (apparently the official name for JavaScript) has an 'eval' instruction, but isn't normally considered to be self-modifying.) --ais523 16:47, 20 August 2007 (UTC)
I would propose "Self-Extending" as the term under which to categorize Underload and Muriel. fwiw, the original concept for SMITH was also limited to self-extension, but I didn't have that clearly in mind when I named and implemented it and, when I did see the distinction later, I didn't want to rename it SEITH. :) --Chris Pressey 16:59, 13 December 2010 (UTC)

Thue-Morse sequence

Inspired by ais523's 1cnis, I thought I could try the T-M sequence in another language of his, well, Underload. The program is quite short and uses a neat (in my opinion) trick. 0 is represented as ":^" and 1 as "~:^" in the memory, and to avoid unnecessary looping, the stack entry consisting of those is placed in the program and it executes pieces of code that are stored in the stack. The two pieces are used to print the current sequence and to build the next one. This got me inspired to a new language idea, as well... Oh, and I just thought to mention this because someone (ais, hopefully) might like to see this program and if I don't tell about it here the chances are close to 0 that anyone ever sees it. Here: http://koti.mbnet.fi/yiap/programs/underload/thumor.ul --Keymaker 22:27, 20 November 2007 (UTC)

That looks impressive, although I can't quite figure out how it works. Here's an Underload program I've been working on in the meantime (with (commented-out)! line breaks added to fit it onto the screen better):
()(~:()~()~(((a(:^)*a(!!!!!!!!!^)~*^):^))~^a(((*)~a*^(((((1)S!^)((1)S!!^))~^)(!(((2)S!^)((2)S!!^))~^)(!!(((3)S!^)((3)S!!^))~^)(
)!(!!!(((4)S!^)((4)S!!^))~^)(!!!!(((5)S!^)((5)S!!^))~^)(!!!!!(((6)S!^)((6)S!!^))~^)(!!!!!!(((7)S!^)((7)S!!^))~^)(!!!!!!!(((8)S!^)(
)!((8)S!!^))~^)(!!!!!!!!(((9)S!^)((9)S!!^))~^)(!!!!!!!!!(((0)S!^)(!^))~^((a(:^)*a(!!!!!!!!!^)~*^):^)))~a(:^)*~^):^)~*^^^!^!^!^!^!(
)!^!!!!!!!!!!!!()~((0)S!)~^^(:)~*(*)*( )S~:^):^
This program counts in base 10; the method I use to divide/modulus by 10 isn't one I've seen before in any language, and also involves storing code in the stack. The program as written can handle numbers up to 6 decimal digits; it's trivial to modify it to handle bignums, but the easiest way to do this would be to set the number of decimal digits to look at to be equal to the number itself, thus causing the program to be very inefficient. I'm beginning to really like the way that various things can be written in Underload; all the elegance of functional programming is there, but you can also do crazy things with the stack that don't make sense in most languages. --ais523 10:48, 21 November 2007 (UTC)
Wow, nice! Although I have no idea how it works, and trying to figure how others' esoprograms work is so (time) consuming that I never do it. :D But the dividing part sounds interesting, even if I don't have any idea how it's done in this particular program. Making a program like that in Underload has been my objective too, but I never got around starting one yet. One day I'll try making one that can count without bounds. Good work. Oh, and agree, I love this language, it's crazy, it's one of my favourites! --Keymaker 19:36, 22 November 2007 (UTC)

Self-interpreter

The article calls '()^' a self-interpreter, but surely it isn't, as a self-interpreter never merely passes control to the program it's interpreting (nor to a copy of it, which amounts to the same thing). This would be analogous, in combinator logic, say, to calling an identity combinator I a "self-interpreter" merely because I C -> C -> ... --r.e.s. (Talk) 21:49, 7 January 2008 (UTC)

That self-interpreter is by cheating, sort of like writing eval(prompt("")) in JavaScript. I don't really think it counts; a proper self-interpreter would be more along the lines of writing the program to be interpreted in Church numerals and then interpreting that. It's a fine line, though; would an interpreter that translated the Church numerals back into the program and then called ^ count, for instance? --ais523 13:30, 8 January 2008 (UTC)
Ah, my bad. I honestly didn't think about it, this idea of passing control is obvious now, but quite new to me. I was thinking along the lines that if the data gets run, it's interpreted. :) Anyways, how would one convert the Underload program to Church numerals? (I have no idea about those.) And would some other encoding be ok (probably would)? And what would it be if my Underload-interpreter-in-brainfuck was modified to have the program we want to execute directly in the memory without the interpreter reading it from user, and that brainfuck program was then converted to Underload with ais523's brainfuck-to-Underload program. Would that suffice? --Keymaker 14:37, 8 January 2008 (UTC)
It seems that I haven't mentioned how Church numerals work in Underload here yet: it actually comes out simpler than in many other languages:
0 (!())
1 ()
2 (:*)
3 (::**)
4 (:::***)
5 (::::****)
and so on. The basic idea is that applying a Church numeral to a function gives a repeated application of the function the right number of times; so 4(f)(x) is f(f(f(f(x)))). In Underload, this is achieved simply by repeating the string that represents the function the right number of times. (With this definition, * does multiplication and ^ does exponentiation, although you sometimes get synonyms for the numbers rather than the numbers themselves.) It's the basic data structure that I use in Underload for representing numbers, booleans and basically everything people use ints for in C. My BF-to-Underload translator uses two self-expanding stacks of Church numerals to represent the tape, so it could take Church numeral input easily. (I'm not sure if I've posted it online anywhere, but just testing it there are some obvious bugs in it, so it needs more tinkering...) --ais523 18:40, 8 January 2008 (UTC)
OK, think I fixed the bugs, and that it works now. The HTML source code is online at http://pastebin.ca/847012; it basically just works by substituting each Brainfuck command with a particular sequence of Underload commands, complicated only by the need to dump an ASCII table into the program at the start. (Characters that Underload can't emit or are outside the printable range are printed as question marks, unfortunately including parens.) --ais523 18:48, 8 January 2008 (UTC)
Oh, it seems that I forgot the </body> and </html> at the end (I encapsulated it in a hurry), but most browsers should be able to work it anyway. It could be easily translated into some other programming language. --ais523 18:50, 8 January 2008 (UTC)

As for what counts as a legal self-interpreter, apparently ehird` on freenode is working on an Underload to C compiler. They told me that the restriction to prevent cheating that came out naturally from the code was "any data read in can't be run directly". --ais523 22:31, 9 January 2008 (UTC)

Church numbers

O, now I know how church numbers works. I was writing it on the paper and I figure out how increment, add, decrement, convert to normal form, etc is:

  • Increment = ((:?*)) = ((:)~*(*)*)
  • Zero = (!()) and if you do increment (:!()*) then the (:!) cancels and (()*) cancels to make () which is correct answer = 1
  • Add = (Inc ? ^) = (Inc ~^^) = (((:)~*(*)*)~^^)

--Zzo38 01:42, 25 January 2008 (UTC)

Yes. Also, times is * and exponentiation is ^; that's where those symbols come from, by the way. --ais523 13:01, 25 January 2008 (UTC)

Here's the grammar for Underload numerals:

    = 1
xy  = x * y
:z* = z + 1

So, for example, ::*:*::*::***::*:**:** = (1 + 1) * (1 + 1) * (1 + (1 + 1) * (1 + (1 + 1))) * (1 + ((1 + 1) * (1 + 1))) * (1 + 1) + 1 = 2 * 2 * (1 + 2 * 3) * (1 + 2 * 2) * 2 + 1 = 4 * 7 * 2 * 5 + 1 = 281. Challenger5 (talk) 20:54, 20 December 2016 (UTC)

Tracing the ~ replacement code

This isn't anything special, just the stack tracing of the

aa((!((aa)(!))))*:*^!**^a*^a*aa*(*:*^!**^)*^

code from the article. Initially I've placed data "A", "B" (B topmost) in the stack. Each line shows the state of the stack after what was executed (shown after ';'). I'm really impressed by this Oerjan's code.

A (B) ;a
A ((B)) ; a
A ((B)) (!((aa)(!))) ; ((!((aa)(!))))
A ((B))(!((aa)(!))) ; *
A ((B))(!((aa)(!))) ((B))(!((aa)(!))) ; :
A ((B))(!((aa)(!)))((B))(!((aa)(!))) ; *
A ; ^
A (B) ; ((B))
A (B) !((aa)(!)) ; (!((aa)(!)))
A (B) !((aa)(!)) (B) ; ((B))
A (B) !((aa)(!)) (B) !((aa)(!)) ; (!((aa)(!)))
A (B) !((aa)(!)) (B) ; !
A (B) !((aa)(!))(B) ; *
A (B)!((aa)(!))(B) ; *
A ; ^
A B ; (B)
A ; !
A (aa)(!) ; ((aa)(!))
A (aa)(!) B ; (B)
A (aa)(!) (B) ; a
A (aa)(!)(B) ; *
A ; ^
A aa ; (aa)
A aa ! ; (!)
A aa ! B ; (B)
A aa ! (B) ; a
A aa !(B) ; *
A aa (!(B)) ; a
A aa ((!(B))) ; a
A aa((!(B))) ; *
A aa((!(B))) *:*^!**^ ; (*:*^!**^)
A aa((!(B)))*:*^!**^ ; *
A ; ^
(A) ; a
((A)) ; a
((A)) (!(B)) ; ((!(B)))
((A))(!(B)) ; *
((A))(!(B)) ((A))(!(B)) ; :
((A))(!(B))((A))(!(B)) ; *
 ; ^
(A) ; ((A))
(A) !(B) ; (!(B))
(A) !(B) (A) ; ((A))
(A) !(B) (A) !(B) ; (!(B))
(A) !(B) (A) ; !
(A) !(B)(A) ; *
(A)!(B)(A) ; *
 ; ^
A ; (A)
 ; !
B ; (B)
B A ; (A)

--Keymaker 12:39, 19 February 2011 (UTC)

It may be easier to understand if you recognize what the pattern aa((!(X)))*:*^!**^ does in there (twice). :) --Ørjan 18:34, 19 February 2011 (UTC)

List operators

There are ways to make LISP-style cons lists:

()aa~a~*		new ()-terminated cons cell (item -- list)
~a*			cons (list head -- newlist)
^!			car (list -- head)
^~!			cdr (list -- tail)
(^~!)~^^^!		n-th element of list (list index -- elem)

And a few other assorted functions:

(((:)~*(*)*))~*^^	add (m n -- (m+n))
((0)((1)((2)((3)((4)((5)((6)((7)((8)((9)(())))))))))))~(^~!)~^^^!	pop Church number from 0-9, push ASCII digit (n -- string)

These cons lists could also work for switch/case. Ian 05:01, 12 March 2011 (UTC)

I think your cons should be a~a*. How do you test for an empty list in this scheme? --Ørjan 10:49, 12 March 2011 (UTC)

Why the reserved characters?

It says in the description that []<>" are reserved characters and must be quoted. Why is this? They have no use in the spec that I can see, and so could just be treated normally, or am I missing something? —Maharba 04:03, 11 June 2011 (UTC)

There are no reserved ch███cters. —e████ 04:1█, 11 ████ 201█ (U█C)
No but really, they're because they were used for something in Overload, the now-abandoned language that Underload is a tarpit of (and that, I think, inspired Underlambda, which now exists happily as ignored ais vapourware). —ehird 04:17, 11 June 2011 (UTC)
The only current reason is to make writing interpreters written in other esolangs easier. Historically, it was for compatibility with Overload, a never-finished esolang of which Underload is a tarpit version. --ais523 04:16, 11 June 2011 (UTC)
Can you describe what they are used for in Overload? (And other things about Overload?) --Zzo38 18:21, 16 June 2011 (UTC)
Overload used [ and ] as a way to write pointers and pointer targets in source code. I forget the exact syntax; one of them was an identifier in square brackets, I'm not 100% sure on what the other one was. You could mutate pointers by using the aAdD instructions, which moved them in certain directions (these were overloaded to perform analogous list operations; a survived to Underload, A was an inverse operation that took the head of a list, d was basically ()~* if used on a list rather than a pointer, and D took the tail of a list). Also, trying to execute a pointer did a goto operation. --ais523 17:42, 22 May 2015 (UTC)
Um ()~* is a NOP afaict... --Ørjan (talk) 09:14, 23 May 2015 (UTC)
Whoops! I meant (())~*. --ais523 17:24, 24 May 2015 (UTC)

Nontrivial program with ():^

The article discusses how the ():^ subset of Underload is Turing-complete. With the article's help, I made this program:

((/)S:()()((#)S^^(^:)()(^)()()()(^^^:^))):^^:^

It prints /#/##/###/####... --(this comment by 67.71.1.139 at 22:55, 30 October 2011 UTC; please sign your comments with ~~~~)

Good work. :) --Keymaker 05:43, 31 October 2011 (UTC)

Simulating two stacks

Lets say that < pops item from top of the stack to another stack and > pushes it back. There must be matching number of <'s and >'s in program and inside stack elements. With this followin conversion table can be created:

start of program  ()
<                 (
>                 )~a*^

so program

~<:>~

converts to this

()~(:)~a*^

and program

():<~:<~:>~>

becomes

():(~:(~:)~a*^~)~a*^

--EzoLang (talk) 20:05, 15 June 2012 (UTC)

I don't see the reason for the start of program (). You can probably avoid the matching requirement by using a conversion that assumes the other stack is kept on top of the first, similar to the conversion described for removing ! from the program. Lessee (and now you do need the start of program ()):
start of program   ()
<                  a~a~*
>                  ^
~                  (~)~a*^
:                  (:)~a*^
!                  ~!
*                  (*)~a*^
(                  (
)                  )~
a                  ~a(~)*~
S                  ~S
^                  ~^
(Whoops, I think this reveals a bug for the a case in the ! removal.) --Ørjan (talk) 21:21, 15 June 2012 (UTC)
Yeah. You are right. In my conversion it was unnecessary. --EzoLang (talk) 21:54, 15 June 2012 (UTC)

Altrnate way of converting "lambda" expressions to underload

So for this I created my own expressions which I call DIP expressions because they work like Joe's DIP operator. Following tables should make it possible to convert "lambda" expressions to underload another way. DIP expressions are form {A} which means that A will be run with topmost stack element ignored.

                Conversion to DIP expressions
[(x)-A(x)]      = {A}
        When A does not contain (x)
[XY-A]          = [Y-[X-A]]
(xy)            = (x)(y)*
((x))           = (x)a
{A(x)B}         = {A}(x)~{B}
        where A and B must be valid DIP expressions
[(x)-A(x)B]     = [(x)-A}:{B]
        When (x) is not between { and }
[(x)-A]         = [(x)-A(x)]!

A and B can be empty


                Optimization (after conversion to DIP expressions)
{}              =
:{A}!           = A


                Conversion to underload
{AB}            = ~AB
{A}             = ~A~
{X}             = (X)~a*^

A must have stack effect (x) -- (x) and B must have stack effect (x) --


                Optimization (during conversion to underload)
~~              =
:~              = :

--(this comment by EzoLang at 17:27, 5 July 2012‎ UTC; please sign your comments with ~~~~)

Input extension

I have an idea for an extension of Underload that allows for user input. (as the title says)

If an "i" is encountered in the program, it is replaced with a string from user input. The only characters allowed in the input are the typical Underload commands, unless the characters are inside parentheses or the v is inside parentheses.

i.e. Cat program:

(End any input with "I" (lowercase))S((i)S:^):^

Poolala (talk) 00:48, 5 November 2013 (UTC)

I figured out a way to do input in Betaload. It basically involves building up a character/replacement table, and then scans through the input and replaces characters with the associated value in the table. Challenger5 (talk) 23:49, 12 February 2017 (UTC)

Capuirequiem program Quine

[D91,WSC93,WCOO]D91,WSC93,WCOO

--(this comment by Esowiki201529A at 00:25, 31 May 2015‎ UTC; please sign your comments with ~~~~)

Underload to Gibberish

~ gb
: eu
! ev
* ec
( [
) ]
a e91a9m1agtbec91a9m3agtec
^ fc
S eq

--(this comment by Esowiki201529A at 01:57, 8 June 2015‎ UTC; please sign your comments with ~~~~)

Quine

[eue91a9m1agtbec91a9m3agteceqeo]eue91a9m1agtbec91a9m3agteceqeo

--(this comment by Esowiki201529A at 02:01, 8 June 2015‎ UTC; please sign your comments with ~~~~)

Infinite loop

[eufc]eufc

--(this comment by Esowiki201529A at 02:06, 8 June 2015‎ UTC; please sign your comments with ~~~~)

Partial Recursive Functions

Though it was already shown that Underload is Turing-complete via simulation of a Turing machine in the article, when I think of Turing-completeness in a functional language, I usually think of partial recursive functions. To that end, I attempted to construct partial recursive functions in Underload.

First off, I used the Church Numerals in Underload to represent numbers, and since the only way to decode a number is to run it (with ^), any sequence with the same effect as a certain number is considered equivalent to that number. The numbers in this case are all nonnegative integers.

Secondly, the calling convention I decided to use was, for a function:

f(x1,x2,...,xn) = y

Convert it into an Underload program string, UL(f) such that if the stack is:

<top>(xn)...(x2)(x1)

Then the string UL(f) will finish computation with the stack looking like:

<top>(y)

Using the lambda notation from the article: UL(f) = [(x1)(x2)...(xn) - (y)]. Since popping from an empty stack is an error, this has the advantage that anything on the stack under the arguments will be untouched.

Now, partial recursive functions are a class of functions produced by including certain simple base functions, then using constructions to build new functions out of old ones. The base functions, with their Underload strings are:

Zero function:

z() = 0    # no arguments
(!())

Successor function:

N(x) = x+1
(:)~*(*)*

Projection functions: (function family, depending on numbers n,m)

P{n,m}(x1,x2,...,xn) = xm
[!]{n-m} ( [!]{m-1} )~a*^

Where [string]{n} means repeat the string n times, and spacing has been added for readability.

There are three constructions. Function composition is a little more formal than you may be used to, from f,g1,g2,...,gm, a new function is defined as:

h(x1,x2,...,xn) = f(g1(x1,x2,...,xn),...,gm(x1,x2,...,xn))

The important point is that the same n arguments are fed to all the inner functions. This was tricky in Underload. Eventually, I settled on combining all the arguments together into one stack item, so it could be copied by : for all of the inner functions. To do that, I defined this macro:

Combine{0} := ()
Combine{n} := [(]{n-1} a [)~aa*^*]{n-1}

Using that, the composition above would be:

Combine{n} [:]{m-1} ^UL(g1) a ~*^UL(g2) ... Combine{m-1} ~*^UL(gm) UL(f)

Another construction, primitive recursion, take two functions f,g which take different numbers of arguments and define a new function:

h(x1,x2,...,xn,0) = g(x1,x2,...,xn)
h(x1,x2,...,xn,y) = f(x1,x2,...,xn,y,h(x1,x2,...,xn,y-1))

To construct this in Underload required executing y then running f y times.

:[(~]{n} a [)~aa*^*]{n} ~(:)~^^:^(a*^ UL(f) )([!]{n})~a*~a*^^~^! UL(g) ~^

The last construction is mu-recursion. Given a function f, a new function is given by:

h(x1,x2,...,xn) = z  if  f(x1,x2,...,xn,z) = 0
                    and f(x1,x2,...,xn,i) >= 0 for i < z

This required a function to test for zero:

TestIfZero(n) = 1 if n=0, else 0
TestIfZero := :a~(:)~^^:^(a*^!!(!()))()~a*~a*^^~^!()~^

And an if-then-else macro built from that function:

IfZero{then, else} := (then)~(!else)~TestIfZero(!)~^^^

Then mu-recursion of f is:

(!()) Combine{n+1} : (~ IfZero{!^P{n+1,n+1}, ~ ^UL(N) Combine{n+1} ^ UL(f) ~:^})~^ UL(f) ~:^

Where N is the Successor function above. Using these base functions and constructions, any partial recursive function can be built in Underload, showing its Turing-completeness. --Weux082690 (talk) 22:33, 27 July 2016 (UTC)