Talk:Underload

From Esolang

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)

Contents 1 File extension? 2 Unlambda functions in Underload 3 99 bottles of beer 4 Is this self-modifying? 5 Thue-Morse sequence 6 Self-interpreter 7 Church numbers

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)