The Tarpit

Third-party 'Chef'

02:59

Most languages employ left recursion in their expression parser: (a+a)+a

Some langauges employ right recursion: a+(a+a)

Is it possible to create a language based on "central recursion"? (a+a)+a+(a+a)

(a+a)+a+(a) (a)+a

my pronoun is monicareinstate

This would have no effect for + and *, and would simply force parentheses on double exponentiation. Besides, how would this work on 3 items?

Third-party 'Chef'

(a)+a+(a)...

Evaluate the sides first, and then the center?

Lyxal

03:23

CMQ: How many l.o.c would your average esolang parser have?

Third-party 'Chef'

@Lyxal 0 lines. I just start interpreting directly.

Lyxal

@Third-party'Chef' wow. Vyxal's parser is 146 l.o.c

Third-party 'Chef'

@Lyxal Have you removed left-recursion from your lex?

Lyxal

I kinda don't know

I mean, it's stack based

So that kinda doesn't apply

Because, y'know, things get applied in order of appearance

Rather than infixed.

Third-party 'Chef'

Oh, the whole stack-based thing employs left-recursion. Never mind.

I have no idea why your languages always need a parser...

If it does, then it's certainly too complex.

Lyxal

03:32

@Third-party'Chef' Because it's easier to just retrieve the values from each token

that is, when they are needed

caird coinheringaahing

13:36

@Lyxal Counting the tokeniser or not?

Third-party 'Chef'

@cairdcoinheringaahing Probably yes. (Lyxal's gone to bed)

caird coinheringaahing

13:51

@Third-party'Chef' Parsers make everything so much easier, especially further down the line

Third-party 'Chef'

@cairdcoinheringaahing All of my languages are context-free.

So not writing a parser is the easiest way to implement these languages.

caird coinheringaahing

What are your languages again?

Third-party 'Chef'

@cairdcoinheringaahing My only non-golfing languages are tq and DIVCON.

res is a total failure, to be honest.

Actually, I've made a ton of languages on esolangs.org

(Under the name User:A)

this link covers most of my languages.

AviFS

18:58

Hey @AdHocGarfHunter!

Ad Hoc Garf Hunter

hey

AviFS

What've you been working on?

I wrote FizzBuzz for Muck and I'm super impressed with how elegant it is:

5<3<<100[>>>+<+(Fizz<<+>>)<+(Buzz<+>)<(<.>)[-]<]

The only pseudo-code in there is 'Fizz' & 'Buzz'

Those are the parts that should actually be printing Fizz/Buzz. That program will print FizzBuzz up to 100 and stop, that 100 is arbitrary. It could be up to any number or any given input

But I hard-coded 100 into that example as you can see.

Ad Hoc Garf Hunter

19:22

I'm trying to prove an iterated version of the tree only version of SB is Turing complete

AviFS

Printing 'Fizz' & 'Buzz' is also cleaner in Muck than BF, though it can never be ideal in a BF-variant:

Prepend `A<` to the code I sent earlier, and replace:

`Fizz`: `>6[+].+++.10[-]-..+<`
`Buzz`: `>>++.21[+].+++++..+<<`

And there's the complete code!

Compare A<3<5<<100[>>>+<+(Fizz<<+>>)<+(Buzz<+>)<(<.>)[-]<] to:

++++++++++[>++++++++++<-]>>++++++++++>->>>>>>>>>>-->+++++++[->++++++++
++<]>[->+>+>+>+<<<<]+++>>+++>>>++++++++[-<++++<++++<++++>>>]+++++[-<++
++<++++>>]>-->++++++[->+++++++++++<]>[->+>+>+>+<<<<]+++++>>+>++++++>++
++++>++++++++[-<++++<++++<++++>>>]++++++[-<+++<+++<+++>>>]>-->---+[-<+
]-<<[->>>+>++[-->++]-->+++[---<-->+>-[<<++[>]]>++[--+[-<+]->>[-]+++++[
---->++++]-->[->+<]>>[.>]>++]-->+++]---+[-<+]->>-[+>++++++++++<<[->+>-
[>+>>]>[+[-<+>]>+>>]<<<<<<]>>[-]>>>++++++++++<[->->+<<]>[-]>[<++++++[-
>++++++++<]>.[-]]<<++++++[-<++++++++>]<.[-]<<[-<+>]]<<<.<]

I still have to think about how to implement where it counts up to the user's input. You can hardcode any number instead of the 100 and it'll count up to that. But I need to implement another command for input, because , won't do here. Don't quote me on this, but I think I'll let ; be the cycling input. Which means you can just replace my 100 with ; to count up to users' input.

@AdHocGarfHunter Oh? Super neat! I'd still appreciate a little more explanation on how the lang works...

Ad Hoc Garf Hunter

So it's the thing I already wrote an interpreter for except you simply iterate the process until you hit an empty string.

Really I am more focused on proving it undecidable right now.

AviFS

Refresher: The user writes the program by writing a tree where each node carries an instruction. The program takes input in the form of fractions, and then the program executes the nodes the pointer runs into in sequnce from the node until the inputted fraction...

Is that so?

@AdHocGarfHunter What do you mean?

Ad Hoc Garf Hunter

What do I mean by undecidable?

AviFS

@AdHocGarfHunter Re: 'you simply iterate the process until you hit an empty string.'

Ad Hoc Garf Hunter

19:34

I don't see what is unclear there

AviFS

What process? And how can there be an empty string?

You mean an empty boolean string, which represents the root node 1?

Ad Hoc Garf Hunter

The interpreter I already sent

A lot of programs eventually output an empty string

AviFS

So you iterate the process of running through the tree until the given fraction?

Ad Hoc Garf Hunter

There is no more SB

only binary strings

AviFS

That's part of the confusion, I suppose. You said:

> I'm trying to prove an iterated version of the tree only version of SB is Turing complete

But you also said the interpreter you sent is the one you're referring to, and that never implemented SB

Ad Hoc Garf Hunter

19:42

Exactly

AviFS

@AdHocGarfHunter We're just talking about the tree-maneuvering lang with bit strings that you sent, then?

Ad Hoc Garf Hunter

Yes

AviFS

Maybe you mean the original one, though?

Because this manipulates numbers, not strings:

tio.run/…

Ad Hoc Garf Hunter

Oh yeah I forgot I did that one

Well that is obviously TC

AviFS

@AdHocGarfHunter Alright, so we're talking about the very original, which creates a new bit string every time it descends the tree. And you iterate that process until the new bit string it creates is... empty!

Ad Hoc Garf Hunter

19:47

yep

AviFS

Alright, so we're talking about:

tio.run/…

@AdHocGarfHunter In that case, you're right. I don't know why'd you call it undecidable

As far as I know, problems are undecidable (can be)

Ad Hoc Garf Hunter

Not sure what you mean

AviFS

Never heard of a language being undecidable, though. I know of the ladder thing with simple recursive and such all the way to TC

@AdHocGarfHunter You said you're trying to prove this language is undecidable

If I understood, correctly

Ad Hoc Garf Hunter

I want to show it's halting problem is undecidable

AviFS

@AdHocGarfHunter Huh?

Halting problem is always undecidable by nature

WDYM its halting problem

Ad Hoc Garf Hunter

19:52

No, regex has a decidable halting problem

AviFS

Not sure how a computing problem can be language specific....

@AdHocGarfHunter I see. So halting is proven undecidable in TC langs?

Ad Hoc Garf Hunter

yes

AviFS

@AdHocGarfHunter I imagine you just have to figure out which class of languages it belongs to then, no?

Ad Hoc Garf Hunter

There is not a finite number of language classes

AviFS

Hasn't the decidability of Halting already been proven for every class of languages?

@AdHocGarfHunter Oh? I'd only heard of the major 7, or whatever

@AdHocGarfHunter Chomsky's, I believe I'm thinking of

LOLOL, I googled 'language classes'

Can you guess what results I got?

Ad Hoc Garf Hunter

19:55

oop

Well to begin with after TC you can always make a new one by just adding a builtin to solve the last ones halting problem

AviFS

→ Modern Languages Classes at Edinburgh College

Ad Hoc Garf Hunter

For example TC + 1 is just Turing machines that also can solve TC's halting problem, and TC + 2 is just TC + 1 that can also solve TC + 1's halting problem.

AviFS

@AdHocGarfHunter I see! You mean by use of oracles!

Ad Hoc Garf Hunter

Yeah

AviFS

Then sure, I'm aware you can create infinite by added oracle after oracle ad infinitum...

Ad Hoc Garf Hunter

19:57

There are also all sorts of unimportant classes in between these things

AviFS

But are there really infinite classes that can appear in the wild?

Aka, without the addition of hypothetical, and practically impossible, oracles

Ad Hoc Garf Hunter

Without the addition of impossible oracles: yes

In the wild: not very often

AviFS

Hmmm...

Ad Hoc Garf Hunter

There are all sorts of things hanging out just below TC

AviFS

Any chance you can direct me to a source/keywords to find one

Still not having any luck communicating with Google

Ad Hoc Garf Hunter

19:59

I can't think of any

AviFS

programming language classes fails for the same reason

I just get educational courses

Ad Hoc Garf Hunter

computability class is what you want

AviFS

@AdHocGarfHunter Not nec. resources, just keywords for google

@AdHocGarfHunter Thanks!

Ad Hoc Garf Hunter

I could probably give you the example from my computability course, but I'm thinking it over carefully right now

AviFS

@AdHocGarfHunter I'm getting problem comp. classes. Not lang comp. classes

Eg. co/recursively enumerable

@AdHocGarfHunter Either way, I'm afraid the one theory course offered did not prepare me for this

Ad Hoc Garf Hunter

20:04

Automata theory

Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word automata (the plural of automaton) comes from the Greek word αὐτόματα, which means "self-making". The figure at right illustrates a finite-state machine, which belongs to a well-known type of automaton. This automaton consists of states (represented in the figure by circles) and transitions (represented by arrows). As the automaton sees a symbol of input, it makes a transition (or jump) to another stat...

AviFS

I wouldn't know the first thing about how to prove halting un/decidable for this lang

Ad Hoc Garf Hunter

Here is an example that is neither striclty above or below Turing machines:

AviFS

@AdHocGarfHunter Perhaps the Computer Science Theory SE question page/chat?

Ad Hoc Garf Hunter

Programs are numbers, the language halts if the number is a Busy Beaver number and loops indefinitely otherwise.

@AviFS For what?

AviFS

@AdHocGarfHunter To ask about its decidability, since I barely know the first thing

One semester in Compl./Compu., but that's it

Ad Hoc Garf Hunter

20:09

Oh no it shouldn't be an issue for me

I can do it.

AviFS

@AdHocGarfHunter Ah, alright!

Have you figured out how to write any slightly more interesting programs in the language?

@AdHocGarfHunter Do you have a name on the wiki so I can look at some of the langs you've designed

Ad Hoc Garf Hunter

esolangs.org/wiki/User:Wheatwizard

I have some programs of note

AviFS

@AdHocGarfHunter Thanks!!

Ad Hoc Garf Hunter

Lost is sort of my best. I have a second version that iterates and improves the idea, but I have been negligent in releasing it.

I actually have a few things I should release.

AviFS

@AdHocGarfHunter Ah, thanks

@AdHocGarfHunter Looking forward to it!!

AviFS

20:40

@AdHocGarfHunter Sort of fell down a rabbit hole from it saying you love Brain-Flak → Brain-Flak = BF + Flack Overstow → Flak Overstow

Had to share an esolang-related piece of Flak I got, though:

Else, if not you! It's true you can do this: Suppose a cluttered and base-10 centered person displays the compiler/interpreter required, and all other associated baggage whenever you want to try a different language. I highly recommend playing around with them online first to get acquainted though, and then committing if you like it.

caird coinheringaahing

22:38

Hey guys/gals, I'm testing my math parser that's included in Whispers v3, would you mind sending a few mathematical expressions to test against?

It understands the standard elementary functions, and maybe a bit more

If you aren't sure, just ask

For example, a test I currently have: sin(cos(x)+x⋅tan(x))

caird coinheringaahing

23:11

@AdHocGarfHunter Man, how is it that just the words "WheatWizard" and "PPCG" feel like a blast from the past? :/

AviFS

23:27

@cairdcoinheringaahing I'd love to actually try 'em out and get back to you!

Any chance you can put on GitHub and I'll play around

caird coinheringaahing

Yeah, I can upload the math parser. It takes a bit of getting used to tho, and doesn't simplify expressions yet

AviFS

@AdHocGarfHunter Btw, forgot to let you know. Looked at them and it's super funny because my order of interest in the languages is exactly backwards! These days, I'm just not into 2D langs. And the one I'm most interested in actually playing with/using, even though its not practical, is Wise!

Ad Hoc Garf Hunter

Wise just doesn't do much, it is not a very novel concept or anything.

AviFS

After that, I'm quite interested in Unbalanced conceptually. It strikes me as a super neat and intriguing idea. But it's not one I'd actually play around coding in myself. Though I'd be curious to see an analysis of its properties!

@AdHocGarfHunter I've looked into a fair few esolangs, and for me it's a novel idea

That one should manipulate a stack of bits, given only the standard bitwise operators, and then at the end output the number formed in binary by all the bits put together is super intriguing to me.

caird coinheringaahing

@AviFS github.com/cairdcoinheringaahing/Whispers/tree/v3

Ad Hoc Garf Hunter

23:32

Uh well that isn't wise?

AviFS

Not interested in the ASCII output with -a flag. But for number manipulation with -b, I'm quite interested

@AdHocGarfHunter ???? Yeah it is

@cairdcoinheringaahing Thanks!

Ad Hoc Garf Hunter

The items in wise are integers not bits.

caird coinheringaahing

@AviFS No problem!

AviFS

@AdHocGarfHunter ⍤⍥⍤

Whoops...

I misunderstood the whole thing then...

The fact that they were bitwise operators, it outputs the result in decimal by default, and these flags:

Options:
-h, --help show this help message and exit
-b, --binary Formats output as binary
-a, --ascii Formats output as ASCII

Made me assume otherwise...

Oh wait, bitwise and & bitwise or. That's my bad...

Still my favorite language, for a whole 'nother reason then!

But I think it's worth making what I thought it was!

It's just a stack of bits, which you manipulate with bit operators, and at the end it concatenates the whole stack and prints the corresponding binary number!

Wouldn't that be interesting?

Ad Hoc Garf Hunter

maybe

Negative numbers?

AviFS

23:38

I don't know that it could do much, but you'd have to manipulate the stack in a manner you've never had to before. A completely different way to think about it...

Eg. because the whole stack is encoded together, rather than just the top value

Ad Hoc Garf Hunter

Negative numbers could be done with a "global" flip operator.

AviFS

So instead of only worrying about what you leave on top, you'd have to line every single one in the stack just right

Ad Hoc Garf Hunter

Which flips the entire stack, including the padding

AviFS

@AdHocGarfHunter Not a bad idea!

Input would be really tricky, though...

I don't even know if it'd be possible

Ad Hoc Garf Hunter

Just take an integer as input

Ok here are some operators I propose
~ - global flip
& - and
| - or
^ - xor
- - not
[ ] - while
$ - swap
: - duplicate
x - remove bit
This still leaves us with a need to be able to reach into the stack without destroying the top.

AviFS

23:44

@cairdcoinheringaahing So far just two things noticed:

1. Factorial doesn't seem to be recognized?

caird coinheringaahing

@AviFS Hmm, it should be

Let me take a look at that

AviFS

2. Only likes function format for funcs it recognizes. Eg. sin(4)/tan(5)

caird coinheringaahing

@AviFS Yeah, it's definitely ignoring factorial :/

AviFS

This one is up to you, but it doesn't seem any more difficult to just recognize anything of that format, eg. do(52)

@cairdcoinheringaahing It imagine it might be hard because it comes after

caird coinheringaahing

@AviFS Well, it works fine with super-script numbers (for powers), so that's for sure weird

AviFS

23:47

Teach it the regex format you want for a function name, and just have it parse anything like f(6)+g(7)

Maybe that's not want you want, though

caird coinheringaahing

@AviFS sin(4)/tan(5) is working for me

Spits out

BinaryOp(left = <Prefix>UnaryOp(op = 'sin', operand = Variable(4)), op = '/', right = <Prefix>UnaryOp(op = 'tan', operand = Variable(5)))

AviFS

@cairdcoinheringaahing It does, I'm saying for any function

caird coinheringaahing

Oh right, allow for f(x) to mean an arbitrary function?

AviFS

But I'm pretty sure the error of whether or not func has been assigned should not be in the tokenizing/parsing stage. That comes later

@cairdcoinheringaahing Yeah, tokenizers/parsers shouldn't care whether it's been assigned or not

You want to be able to say f(x) = x+1 in the code and then have f(5) be parsed correctly

@AdHocGarfHunter But given that the stack will only allow bools in it, what would happen to the integer after input?

caird coinheringaahing

@AviFS For it's use in Whispers (which is why I bothered developing it), it won't have arbitrary functions, only pre-known ones

AviFS

23:50

The whole thing would be binary-ized and plopped on top? That wouldn't work because it could be it bin rep would be of unknown length and the stuff below thus hidden

caird coinheringaahing

So I think I'll leave that for now

Ad Hoc Garf Hunter

@AviFS Convert to binary and have it be the starting stack

AviFS

So if it took input, I can only imagine allowing multiple stacks

And having the input be converted and put in its own stack

@AdHocGarfHunter What about multiple inputs?

Ad Hoc Garf Hunter

Yeah sure you can do that I guess

AviFS

Eg. add two numbers

Ad Hoc Garf Hunter

23:51

@AviFS Why do you need to support multiple inputs?

AviFS

@AdHocGarfHunter Love the reluctance!

@AdHocGarfHunter Why would you need to support any input?

Ad Hoc Garf Hunter

You don't need to, but there is a clear way to do so.

AviFS

AKA What argument can you possibly make that would make it worth implementing input, but not worth implementing more than one?

@AdHocGarfHunter IMO there's a clear way to allow arbitrary

Ad Hoc Garf Hunter

Implementing one input is clear and straight forward from the current logic of the language. Multiple inputs are not.

AviFS

Although I suppose the operators might get really ugly if there were multiple

@AdHocGarfHunter Yeah, you're right

I was more thinking of allowing to ask for an input at an arbitrary stage

I guess if you only allow one input at the very beginning, it's alright

Ad Hoc Garf Hunter

23:54

Yeah sure, add an ask for a bit operator

AviFS

Lemme take a look at proposed ops

@AdHocGarfHunter ?

Sure what? And what sort of op is that

Ad Hoc Garf Hunter

Add an operator that consumes a single bit of input and puts it on the stack.

AviFS

@AdHocGarfHunter ;(

Why am I such an idiot!

And why is that such an elegant and impossibly, painfully obvious solution...

@AdHocGarfHunter Screw your other idea! In my mind that's by far the superior idea. Not just for flexibility but because it flows much better with the logic. Sort of awkward to start with a stack of unknown height IMO

Ad Hoc Garf Hunter

The height is known.

It is always infinite

Transcript for