The Third Stack

« first day (102 days earlier) ← previous day next day → last day (1140 days later) »

Wheat Wizard

17:33

Q: Tips for Programming, Understanding and Golfing in Brain-Flak

Some users (myself, DJMcMayhem, and 1000000000) are very experienced in the mysterious ways of Brain-Flak. So I thought it a good idea to set up this question as a way to share our knowledge with the community and lower the bar of entry to this language "designed to be painful to use". And perha...

tips

3 hours later…

PhiNotPi

20:24

I'm working on the tree-based autogolfer now.

Wheat Wizard

@PhiNotPi Cool could we see it/ help?

PhiNotPi

What I want to do is have it automatically find some simplification rules... but for right now I'm just adding stuff by hand.

Wheat Wizard

What do you mean by automatically?

are you implementing some type of neural net?

PhiNotPi

I haven't added any form of automation yet, but what I'm thinking of doing is a decent amount of brute-forcing for local tree manipulations.

Once I make a significant list of local manipulations, those manipulations can be applied recursively to the syntax tree.

Wheat Wizard

For brute forcing how are you going to verify that two programs are the same?

@PhiNotPi have you checked out this question?

Q: Golf a Brain-Flak Integer

Integers are tedious to represent in Brain-Flak. There are 8 operators: () Evaluates to 1, but does not push anything on any stack [] Evaluates to an indeterminate value for the purposes of this question {} Removes the top of the stack and evaluates to it <> Switches to or ba...

stack metagolf brain-flak

PhiNotPi

20:34

I want to try something similar to lambda expressions for expressions that don't use the {n} or [] commands.

As in... determine the arity of the expression (number of values on each stack it uses) and then figure out if they represent the same mathematical operation.

I could use either random samples (if two snippets produce the same results for x different inputs, then assume they are the same) or do some more complicated automated theorem proving.

DJMcMayhem

I think using the "arity of a snippet" (height of the stack affected) is it a pretty good idea

You could do negative for popping and positive for pushing. Or maybe a range if it includes both

Wheat Wizard

@PhiNotPi I would recommend the theorem proving. If optimization errors snowball so if you make one small mistake it will become a large problem later down the line. I use theorem proving for my optimizer and I think it worked out quite fine.

PhiNotPi

It will have to include both... I'll basically have to create a "stack" object that, instead of numbers, holds expressions.

Wheat Wizard

Seems like that might work quite nicely

You are going to have to write almost an entire new interpreter to do this

Actually this might fail for low or empty stacks

PhiNotPi

That's easy though... the issue is that I don't really know how to easily prove that two expressions are equivalent. It might be easy if the expressions only involve addition/subtraction (which I think they might).

What do you mean?

Wheat Wizard

20:48

Take for instance ({}) it pushes zero when the stack is empty but other wise does nothing

PhiNotPi

They way I will have it, is that each time it pops from an empty stack, it returns an expression with a new variable.

Wheat Wizard

But often times you cannot know if the stack is empty

PhiNotPi

Hmm... yeah that might fail.

Wheat Wizard

I ran into the same problem with my optimizer

PhiNotPi

Are there ways to identify that kind of behavior?

That might not even affect my method of detecting equivalence.

Assuming that I avoid the [] and {n} commands.

For example... a blank program would have and arity of 0/0->0/0, while ({}) would have an arity of 1/0->1/0

Having the same arity is a requirement of equivalence, and two snippets with the same arity that are equivalent when there's stuff on the stack should still be equivalent when the stack is empty.

@WheatWizard what do you think of that solution? ^

MegaTom

21:08

I just golfed 2 bytes off the multiplication program (from the github wiki). dose this look valid? ({}<>)({<({}[()])><>({})<>}{}<><{}>)

(note: that is the positive only one.)

Wheat Wizard

@MegaTom Wow looks good

@PhiNotPi How does the output arity work?

PhiNotPi

input arity means how deeply in the stack the snippet read. If output arity = input arity, the stack is unchanged. If output arity is greater, the stack grew, etc.

Wheat Wizard

shouldn't ({}) be 1/0 -> 1/0?

PhiNotPi

it is

Wheat Wizard

oh I misread my bad

@PhiNotPi I can't see anything wrong with it. However I would prove this first If I were you.

1000000000

21:31

@PhiNotPi WheatWizard and I have had a lot of discussions concerning golfing ({}) and indeed even when its value is not used it is important to treat it differently from the empty program as it can affect a stack height check on the entire opposite side of the program. On the other hand those instances are rare and not being able to reduce a ({}) can drastically reduce the power of an optimizer. There pros and cons to this issue that need to be considered.

PhiNotPi

22:04

I'll continue working on this later tonight.

I'm basically writing a new interpreter now.

DJMcMayhem

What language is it in?

PhiNotPi

Java

« first day (102 days earlier) ← previous day next day → last day (1140 days later) »

all rooms