Complement

Seggan

02:21

ok this is messing with me too much, parser lib here i come

actually wait i think i can do this

Ginger

16:23

how should we do outputting of infinite sets? like for the program that "counts up forever" by printing every natural number to stdout

the issue is that sets aren't sorted

and I don't think people will accept SortedSet(1, 2, 3, ...) as output :p

@Seggan

Seggan

@Ginger well we kinda have no choice but to make them sorted

and print infinitely counting up

Ginger

we can't, radvylf will have our heads

Seggan

what other choice do we have?

Ginger

we can, however, make a builtin to "sort" sets

so turn the set of all natural numbers into {1, {2, {3, {...}}}}

but even then we have a problem with representing the result

because the program doesn't say "print all the numbers", it says "print this infinite set"

so how tf does the interpreter represent that

Seggan

@Ginger then print it infinitely

@RadvylfPrograms your input?

Ginger

16:49

@Seggan hurry up with that interpreter already I found a challenge which Complement is the ideal language for

it even beats Vyxal (admittedly only by one byte but that's still a victory)

Seggan

im still writing the parser

i think i got a way to do it without a lib

Ginger

17:11

what's the complement of the empty set?

user

The universe

Ginger

I meant in Complement

what the hell is the program supposed to output if I try to print that

user

The set of all sets (not including the complement of the empty set)? lmao

Ginger

how do I represent the set of all sets

user

4

Q: Notation for the set of all sets

I know that it doesn't make sense mathematically (Russell's paradox), but is there any nice way or notation to express the set of all sets? Edit: I want the set to contain itself, even though it might break some definition.

Ginger

17:50

@user so just V

user

I don't see how the notation matters, anyhow

Ginger

eh

user

You just need to be list all sets

Ginger

it's an implementation detail; I'm just the SYN_TAX guy

user

ZFC gives you axioms that basically tell you how to construct every set, right?

Ginger

17:52

idk

lemme tell ya something: I am not a set theorist, I have never done anything relating to set theory, this whole idea came from a book on logic I bought at Barnes & Noble

user

Same lol, I need to learn more about sets before talking about it

Ginger

that's it

→ 26 messages moved to Off-Topic TNB

and there we go

now as I was saying: Is the Euler Field Manifold Hypergroup isomorphic to a Gödel-Klein Meta-Algebreic ε<0 Quasimonoid Conjection under Sondheim Calculus?

or is the question ill-formed?

Radvylf Programs

19:01

@Seggan BigInts

@Ginger They aren't ordered, doesn't mean it's impossible to assign tnem an order to print them

I think we'd just internally store infinite sets with a particular ordering (it's impossible not to) and use that for printing

Seggan

^

@RadvylfPrograms that exists? noice

Radvylf Programs

@Ginger How do you...not?

Just an infinite iterator of all of the sets

@Seggan It's a library, num::bigint::BigInt

Alternatively num_bigint::BigInt if you just want to download the bigint part

Seggan

mm so i have to add a dep?

Radvylf Programs

Yeah

Seggan

nice

mind sanity checking out the parser branch for me?

Radvylf Programs

19:05

Alternatively, we could store ints as sets at all times, but that'd be kinda inefficient

Seggan

ure the best rustacean of us

Radvylf Programs

Can we not have exponentiation please

It makes things way more complicated

Well, I guess with ints it's probably fine

Why is Implies there but not the double arrow

Seggan

because i forgot

Radvylf Programs

What about xor, xor's missing

Seggan

woops

Radvylf Programs

19:08

We need unary -

Seggan

btw what i meant abt "sanity check" was the actual code, not the features :P

Radvylf Programs

Putting each struct in its own file is very un-rust-like

Seggan

its kinda gonna be weird tho: parsing::parser::AstNode or whatever

Radvylf Programs

The AstNode should go in the parser's file unless you plan to make it absolutely giant later on

Seggan

oh wait cant you make multiple namespaces in a single file?

Radvylf Programs

19:09

Yeah it should just be parsing::AstNode, parsing::parse(), etc.

Seggan

thats not what i meant but ok

Radvylf Programs

You can keep AstNode in its own file if you want and pub use it, but it doesn't really feel necessary

Seggan

i like the one thing/file method bc then your files are cleaner and less scrolling is needed

Radvylf Programs

Why is the token enum in the lexer file then

Seggan

because its closely tied to the lexer

Radvylf Programs

19:11

And why is Operator in a file called parsing.rs

@Seggan And the AST is closely tied to parser, no?

Seggan

true. i originally had a very messy struct/trait system in there before i realized enums do it better

@RadvylfPrograms because its pretty much shared across all submodules of parsing

ok i admit it im bad at rust's module system

Radvylf Programs

I'd put it in its own file, not in parsing.rs

@Seggan It's really confusing yeah

Very powerful, but confusing

You can basically map practically any structure file-wise to practically any structure module-wise

Seggan

so u saying mush the entire parsing module into one file?

Radvylf Programs

what no

I'm saying put the Operator enum in its own file

It's big enough it makes sense to keep it separate

Seggan

yeah but what abt this

im a bit confused as to what to put together and what to separate

Radvylf Programs

19:26

@Seggan As in just pub use them in parsing.rs

Seggan

what does pub use do

merges it with the current module?

Radvylf Programs

Yeah. Like, pub use thing::function in parsing.rs means you can do parsing::function()

Seggan

mm

Radvylf Programs

So, I think it's time for us to start discussing how exactly we're gonna implement this

Constraint-based stuff can be pretty tricky

Also, one really big question: Undefined behavior

The vast majority of possible programs will have many, typically infinitely many, valid outputs

Ginger

ok so

Radvylf Programs

19:37

E.g., x % 2 = 0; x ∈ O

Ginger

while yall write the language interpreter, I will contribute by making a website for writing Complement programs with Blockly

like mathblocks on steroids

we can use it to prototype the syntax

Seggan

@RadvylfPrograms print every even number

Radvylf Programs

I thought we only printed one of the valid outputs

Ginger

hmmm

Seggan

i have an idea how to implement this but i dont have time rn to explain

Ginger

19:38

I'm... not sure what that program would do

Radvylf Programs

It would be undefined behavior

It would print any set containing at least one even number

Probably {0}

Seggan

^^

Radvylf Programs

One possibility: We could start with O being an iterator over the set of all sets, then repeatedly "filter" it (lazily), then take the first item

Ginger

I think that should be an error along the lines of "not specific enough"

lemme explain

Radvylf Programs

Then we also have to determine if there's more than one possible output

No nontrivial program would halt

Ginger

19:41

correct syntax for that would probably be ∃x∈N((x%2=0)∧(x∈O))

Seggan

@RadvylfPrograms my idea is that all statements add a constraint to a variable. i.e. x % 2 = 0 constrains x to even. then on the output we simply filter the numbers by the constraints on the var

Ginger

that way the interpreter knows that x has to be a natural number

Radvylf Programs

@Seggan Yeah, but it's easier said than done to turn a set of constraints into a result. That's what we need to discuss how to do.

Seggan

filter all numbers?

if there is a < or smth filter all numbers up to x

Radvylf Programs

@Ginger Yeah but that's something different

Nobody said x had to be a natural number in my program

@Seggan What about sets

Ginger

19:43

@RadvylfPrograms which is why that'd be an error; the interpreter has no clue what you want

Radvylf Programs

x is a number

Seggan

@RadvylfPrograms but we constrained it to integers

Radvylf Programs

It knows x is a number because x % 2 can only be 0 if x is a number

Since % isn't meaningful on a non-number

@Seggan Yeah but it could be nonpositive

Ginger

but then we'd have to add code for figuring out types

which feels... hard

Radvylf Programs

And figuring out everything else doesn't?

Ginger

19:45

fine, hardER

Radvylf Programs

I don't think you understand how impossible of a task we're about to embark on

Ginger

oh I do

Seggan

@Ginger types are simply constraints inferred from others. i.e. if x is in the set of all numbers, x is a number

Ginger

I've been lying awake trying to figure out how tf this could work

Seggan

@RadvylfPrograms we can do the simpler version of it, cant we?

Ginger

19:46

but the payoff if we get it right will be monumental

Radvylf Programs

Wait what will ∃ even do

Ginger

@RadvylfPrograms it means "there exists"

Radvylf Programs

But statements already mean that

Ginger

it'd probably be used for variable assignment? not sure

Radvylf Programs

Since the interpreter's job is to make it exist :p

∃x∈N((x%2=0)∧(x∈O)) is the same as x ∈ N; x % 2 = 0; x ∈ O

Seggan

19:47

@RadvylfPrograms i thought abt that too :P

Ginger

@RadvylfPrograms fair enough, but I think we should still add it so hardcore set theorists will feel more comfortable with the syntax

Radvylf Programs

Cool

We can just make it syntax sugar I guess

Ginger

exactly

Radvylf Programs

Or: we could make it like let/var

When you use an identifier/set name, it searches for the tightest-scoped ∃ expression, or defaults to the global scope otherwise

So if you want to shadow x in a lower scope, ∃ makes it unambiguous that you're declaring a new one

Ginger

you've got "set theory" and then you've got "set theory (Complement/set theory)"

Seggan

21:29

ok so ive finally implemented operator precedence, and its dead simple

im surprised it took me a day to figure it out

i simply search for the rightmost operator with the lowest precedence and recursively parse each side

Ginger

lol

Seggan

the resulting ast is already in the required form

Seggan

22:34

parens work

Seggan

23:02

should ² be an operator?

Radvylf Programs

I don't think so

Even if we include exponentiation, which I'd still advise against, having ² and maybe ³ special cased would be weird

Seggan

why not exponentation

also github.com/ComplementLang/Complement/pull/2

Radvylf Programs

@Seggan Because efficiently reversing the core arithmetic operations is hard enough

Seggan

theres nth root docs.rs/num-bigint/0.4.3/num_bigint/…

Radvylf Programs

This is about constraints tho, not roots

Seggan

23:08

yeah but the reverse of a power is a root

its easy enough to reverse

Radvylf Programs

If I tell you a number modulo 5 is 4, the same number mod 6 is 2, you can turn that into a single constraint

@Seggan Not what I mean by reverse

@RadvylfPrograms As soon as you add power in, that's no longer possible

With addition and multiplication and stuff, it's still pretty easy

Seggan

@RadvylfPrograms why not?

Radvylf Programs

Because there's no patterns

Give me a perfect cube that, modulo 1338, is 345

I don't think (I may be wrong) that there's a good way to get a list of those without trying every 1338th number

Seggan

fair point

ill remove it

Radvylf Programs

Correct me if I'm wrong but I believe I'm the only person here who has implemented a constraint-based equation solver

@Seggan I was actually going to say before I sent that message, I may have changed my mind

Wait no I haven't

I just realized

The problem isn't fixed exponents

It's when you have two unknowns

Seggan

23:12

@RadvylfPrograms you have?

Radvylf Programs

Yep, about a year ago

At one in the morning

Seggan

@RadvylfPrograms then we implement a system of equations :P

@RadvylfPrograms link?

Radvylf Programs

It's not public and I probably could not find it if I tried

Seggan

aww

Radvylf Programs

@Seggan You joke, but Complement will be a fully featured equation solver for integers

Given that applying constraints to see what a variable is is exactly what solving an equation is

Seggan

23:14

yeah lol

Complement might actually be useful outside the world of esolangs

lets not get too far ahead of ourselves tho

Radvylf Programs

Probably not though, since it will be far far less optimized than something purpose-built for it like SymPy

Seggan

so if yall want to review that pr so i can begin work on sets would be nice

Radvylf Programs

@Seggan Actually...it might not be a bad idea. It'd be optimized to x * x anyway, and would make some stuff look prettier

What's the syntax for filtering a set again

It's set-builder, right?

Seggan

@Seggan (thats an exaggeration, git allows me to start now :P)

@RadvylfPrograms i think

Radvylf Programs

Trying to write out how I'd solve for the roots of a polynomial with Complement

{x | x² - 4x - 8 = 0}

(This is why | for remainder would have been a bad idea :p)

Seggan

23:19

quick rust q: copilot suggests i implement 'static on my trait, how do i implement a lifetime on a trait??

Radvylf Programs

What trait? I doubt you need 'static for it

@Seggan You just require it the same way you would for trait inheritance

Seggan

yeah inheritance is what i mean

pub trait Set: Clone + Default + Eq + 'static {

Radvylf Programs

Sets are going to need to be recursive dyn Iterators, those can get really hairy so I'd recommend not trying that yet lol

Seggan

no this is just a general interface for sets, i.e. a cover for the set of outputs and lazy sets and whatnot

@RadvylfPrograms well thats kinda the next thing on the list :P

unless i should start implementing the solving of arithmetic constraints

Radvylf Programs

Okay actually it's simpler than I remember

Code example from an unrelated project:

pub trait CloneIterator: Iterator {
    fn clone_box(&self) -> Box<dyn CloneIterator<Item = Self::Item>>;
}

impl<T> CloneIterator for T
where
    T: 'static + Iterator + Clone
{
    #[inline]
    fn clone_box(&self) -> Box<dyn CloneIterator<Item = Self::Item>> {
        Box::new(self.clone())
    }
}

pub struct Ripr {
    top: Option<Rational>,
    data: Box<dyn CloneIterator<Item = Rational>>
}

impl Iterator for Ripr {
    type Item = Rational;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {

Seggan

23:23

yeah i think ill leave that to you (or the future me)

ill start on arithmetic

Radvylf Programs

How are you going to do it

Like, what's the interface going to be

Seggan

for sets?

Radvylf Programs

No for applying the constraints

Seggan

i dont get what ure asking

Radvylf Programs

Like, what will what you're writing actually be doing

There's multiple ways you could go about it and multiple things you could input or return to do it

Seggan

23:25

perform reduction of the constants, mark variables with constraints

Radvylf Programs

Ohhh

I thought you meant actually applying the constraints

Which is gonna be a whole thing

Seggan

well marking == applying :P

Radvylf Programs

We're using words differently then

Seggan

basically rn im just trying to figure out the narrowest range of values a variable can fit

Radvylf Programs

By "applying constraints" I mean actually solving for the final value. Like, constraining the set of all numbers to the possible final results.

Which we're probably going to want a pretty flexible optimizer for, and a lot of planning upfront

Seggan

23:28

ok maybe not that deep in, im assuming a one variable environment here

something a 6th grader can solve or soish

Radvylf Programs

One thing to consider is that we want to be able to detect as many no-solutions situations as possible

Since any we can't catch up-front are an infinite loop

E.g., O = 2; O < 1

If we just did the naive "filter an infinite list" that would be an infinite loop since it would never find an item that passes the filter

Seggan

yeah ive got some plans in mind for that

Radvylf Programs

I'm thinking a web-style thing, like they do for code optimizers

We just have a big list of rules which say what structure they apply to (e.g., an = and a </> on the same variable), and we repeatedly go down the list until we find a rule that matches, then do it again and again, until no more rules match

Seggan

hmm i dont seem to be getting it

Radvylf Programs

Well there's going to be probably hundreds of optimizations or possible no-solution cases we'll need to handle

To take the raw set of contraints and sanity check them + optimize them for brute forcing

Seggan

23:35

ok i think i better do some reading before i actually do this

Radvylf Programs

E.g., if x = 1 is one of the constraints, we don't need to brute force x. If x > 2; x <= 3 is one of the constraints, we don't need to brute force x. What if x E {y | y² -2y + 1 = 0} is a constraint? We don't need to brute force x, but that's going to be a really complicated optimization we may or may not be able to implement.

Seggan

i mean simply substituting a variable we know is a set predicate is pretty simple

ok wait never mind

i read it wrong

Radvylf Programs

The architecture is going to need to look something like this:

1. We convert the AST into a set of contraints on variables
2. We repeatedly perform optimizations, merging constraints where possible and searching for contradictions
3. We brute force the unsolved variables

3

This is basically going to be prolog and sympy combined with extra glue in the middle. Hope y'all packed lunches.

Seggan

ok before i start on this ima write an equation solver for 1 var

Transcript for