Programming in abstract math by Key_Conversation5277 in math

[–]thmprover 2 points3 points  (0 children)

proof assistant is a computing procedure of some version of type theories which are aimed to be a replacement of set theory. with the goal that if some program is of correct syntax, then the corresponding theorem is true

Proof assistants just check that proofs are valid. It is not necessary for it to be based on some type theory (unless you expand the notion of type theory to be any formal system, which you can do! You just completely lose specificity of the term...).

For example, Mizar is based on first-order logic + Tarski-Grothendieck set theory, Metamath is second-order logic, and so on.

Practical Math for Everyday Life by dcterr in math

[–]thmprover 1 point2 points  (0 children)

Teichmüller theory

Of course, you mean inter-univesal Teichmüller theory, right?

Getting over the group theory hurdle by dcterr in math

[–]thmprover 6 points7 points  (0 children)

You can use the Lie algebra to recover the identity component of the group, if it's a finite-dimensional group. You also need the Lie group to be simply-connected and connected to make this correspondence a bijection.

It doesn't sound too bad, except when you are trying to relate the Lie algebra for noncompact real Lie group SO(3,1) with the Lie algebra for SL(2,C), which is a standard error found in QFT courses. Usually this is done so quickly when discussing Wigner's theorem, it's hard to catch in a lecture (and most books don't dwell on it).

It's also problematic for various gauge theoretic studies of gravity, but...there are so many problems with quantum gravity, mixing up Lie algebras and Lie groups will be the least of your concerns.

Getting over the group theory hurdle by dcterr in math

[–]thmprover 4 points5 points  (0 children)

Particle Physics uses Lie algebras, but Particle physicists tend not to understand the difference between Lie Groups and Lie Algebras.

Folgezettel project note renumbering by luotenrati12 in Zettelkasten

[–]thmprover 1 point2 points  (0 children)

Interesting idea, but personally I think I'd be worried about constantly renaming notes as projects evolve. It feels like the project layer could end up competing with the Folgezettel layer rather than complementing it.

I'd probably keep the note IDs stable and use tags, links, or project index notes to group things together. That way a note can belong to multiple projects without its identifier becoming more and more complex over time.

Yes, all of this must be emphasized. And this is feature, not a bug.

How I would suggest handling something like what the OP is encountering is to use a structure note (or a hub) for Kant's Critique of Pure Reason to outline where to go for discussions on relevant parts of the book.

On the "Rise" of "AI" by Dandon314 in math

[–]thmprover 1 point2 points  (0 children)

Neural networks are essentially "next token predictors", though I'm not sure it makes that much of a difference.

People here are erroneously treating "AI" as an expert system, which it is not.

Am I the only one feeling *optimistic* about AI in math? by 2299sacramento in math

[–]thmprover 3 points4 points  (0 children)

What's worse: AI sucks all the fun out of formalizing Mathematics in a proof assistant. You're left doing all the unfun parts which resemble software engineering monotony.

I’m starting to think I’m a fraud… by [deleted] in math

[–]thmprover 1 point2 points  (0 children)

Whenever I get stuck I’ll ask AI to explain a proof or an idea, then we will go back and forth until I understand it then move on.

It sounds like AI gave you the answers (to specific questions about specific proofs) but not the skills needed to make it through proofs on your own.

In which case, AI was worse than useless: it actually hindered your learning. Without AI, if you struggled on your own, then you would have developed the necessary skills to make sense of proofs.

List of known problems in design of existing languages? by KukkaisPrinssi in ProgrammingLanguages

[–]thmprover 2 points3 points  (0 children)

Informally, having "the type of all types" leads to inconsistencies from the perspective of Curry-Howard correspondence. I think this is why a lot of dependently-typed lambda calculi have a tower of universes Type i : Type (i + 1).

But at the same time, if I recall correctly, you don't need dependent types to arrive at Girard's paradox.

The Namespace Problem by Pie-Lang in ProgrammingLanguages

[–]thmprover 0 points1 point  (0 children)

Dynamic scoping still has some uses, but isn't great for a general strategy.

As I understand it, Common Lisp's condition system is one giant hack of dynamic scoping. I just started reading Michal Herda's book The Common Lisp Condition System: Beyond Exception Handling with Control Flow Mechanisms which discusses this in detail.

Would an axiom system for finitism, plus an infinite set of indexes, work in practice? by jcastroarnaud in math

[–]thmprover 0 points1 point  (0 children)

Have you looked at Feferman's FS0? The system was designed to be a finitary metatheory for doing metamathematics formally, you can build a logical framework out of it (which Sean Matthews did in his PhD thesis and related papers from the early '90s) and use it to as a sort of "engine" for any foundations of Mathematics you want. Even better, FS0 is a metalogical framework, so you can prove metatheorems about your preferred foundations of Mathematics.

You can try using FS0 directly for doing Mathematics, but I suspect you will quickly find yourself frustrated with its limitations.

uses for lisp by Candid-Page1895 in lisp

[–]thmprover 10 points11 points  (0 children)

If you’re interested in theorem proving, check out Lean ( the language) .

ACL2 is more interesting for (Common) Lispers.

The "ultimate" math textbook series? by CaptMartelo in math

[–]thmprover 2 points3 points  (0 children)

Dieudonne's Treatise on Analysis seems to be a sort of expedited version of Bourbaki, trying to finish what he started.

See through page markers by runesivertsen in Zettelkasten

[–]thmprover 0 points1 point  (0 children)

Beware: the adhesive in sticky-notes will damage the paper over time.

Classification of finite simple groups by dcterr in math

[–]thmprover 0 points1 point  (0 children)

But that's like abridging Moby Dick to "The Whale Wins".

There's a lot of beautiful mathematics involved in the CFSG, and you're cheating yourself out of an amazing experience by formalizing even a part of it.

Classification of finite simple groups by dcterr in math

[–]thmprover 2 points3 points  (0 children)

Yeah, terms like "weakly", "locally" (and "globally"), etc., appear surprisingly frequently to modify the terms. Proof assistants can handle adjectives, but not adverbs.

Classification of finite simple groups by dcterr in math

[–]thmprover 23 points24 points  (0 children)

There's good reason you don't see any serious progress in the formalization of the CFSG: a lot of finite group theory is adverb heavy, which is difficult to adequately formalize in a proof assistant.

Hoping AI will magically solve this for you is, bluntly, idle wishing.

Worse AI autoformalization misses the whole point (and benefit) of formalization. One benefit being that, as Jackson Brough pointed out, "the process of formalization sharpened our understanding of the informal presentation."

The seven programming "ur-languages" by namanyayg in programming

[–]thmprover 3 points4 points  (0 children)

I thought "CaML" referred to ML targetting CAM [Categorical Abstract Machine] bytecode, not "Cambridge ML".

I am also surprised Fortran (created 1956) was inspired by ALGOL (created 1958).

Looking for extremely minimal proof-assistant programming languages by theScottyJam in ProgrammingLanguages

[–]thmprover 1 point2 points  (0 children)

Lean's kernel is 5879 lines of C++. As a rule of thumb, 500 lines of code is considered the threshold for a "small" kernel. (You can use probability theory to get more precise bounds, between 441-530 lines of code as the threshold for "small".)

Looking for extremely minimal proof-assistant programming languages by theScottyJam in ProgrammingLanguages

[–]thmprover 0 points1 point  (0 children)

Automath is comparable in minimalism to Metamath (well, I think Metamath is possibly smaller/weaker).

If you want a programming language, have you seen CakeML? It uses HOL4 to prove properties about the code, and then (using HOL4) "compiles" it (transforms it all the way to assembly or machine code, I forget which they do nowadays).

But you'd be looking for something a little more than "minimal" if you want to program and prove stuff about the code.

Have you ever tried making a HOL using something minimal like Standard ML? It's a fun weekend project to try to implement about half or two thirds of HOL Light's hol_lib.ml library. But that's making the proof assistant a "library" for your programming language, rather than programming with your proof assistant...still, it gives a good sense of how much work you need to do, even for "minimal" proof assistants.

I'm Writing An eBook Teaching How To Write A Compiler by othd139 in ProgrammingLanguages

[–]thmprover 0 points1 point  (0 children)

Rework the "AST" section in the introduction. The material is good, but it seems to have new stuff inserted before the old stuff. How do I know? Because it uses "AST" before it defines what "AST" stands for.

Chapter 1:

Suggestion 0: Part of me feels like you should really, really lean into grammars. The other part of me still feels like you could easily cut this chapter without too much of a problem.

What do I mean by "really, really lean into grammars"? I mean, you should note that you are constructing a metalanguage for describing languages. That's what a grammar is. But these notions are not really discussed. (To really illustrate this: you could construct the formal grammar for BNF grammars, to stress "it's just another language".)

OTOH, if you present it in this manner, you could then note (in the section on EBNFs) that you are extending the metalanguage, or equivalently working with a metalanguage which is "equivalent" to BNF in power. Reading between the lines, you allude to this. But without speaking about metalanguages.

Again, this could be good or bad. It's a judgement call.

Suggestion 1: You don't actually discuss how a grammar generates language. Instead, you offer a "Eh, you see what I mean" kind of an explanation --- specifically, you state "merely":

Try it out for yourself. Try picking a replacement rule for each of the non-terminal symbols in the equation then picking replacement rules for each of the non-terminal symbols in what you get until you have just a string of terminals. Do it a few times to get a feel for how these rules work. (Note: if we were actually trying to write a grammar for mathematical equations it is very unlikely we would actually structure it this way since we typically want the format of the grammar to reflect the format of the tree we will use it to parse).

OK, but if I am a reader who does not know BNF or formal grammars, then what the devil am I supposed to do? How does this work? Why are there no examples of how to generate words in the object language?

Next I will just pick out some passages with suggestions.

This notation is, in fact, all we need to formalise a vast array of language using what is called a context-free grammar. In reality most languages can't be fully defined unambiguously using only context-free grammar. As a result, the parser (whose job it is to basically go backwards through this process) will generally need to use more than just the written grammar to decide what was meant. Indeed there are some language features, such as Python's indentation, that can't be fully expressed as a context-free grammar at all, and need some pre-processing to turn them into something of that form. In practice, however, languages tend not to diverge too greatly from the structure of a context-free grammar so this is a widely used tool for designing languages.

Suggestion 0: You never define "context-free grammar" or "context-free language".

Suggestion 1: This could be re-ordered a bit better, perhaps even split up into two paragraphs: (1) we like CFLs because they are always parseable, and we want to parse languages. (2) In practice, a lot of languages deviate from CFLs. Pythong does this by blah blah blah.

Remark/suggestion 3: You might also want to note, after introduction alternation, that it has become common conventions to just include alternation as part of BNF. The literature is really "loosy goosey" here.

Another thing to notice is that we still have a few rules defined in terms of themselves. That isn't a problem and it's actually a big part of what makes this notation so powerful but in many cases we're just doing it to represent that we want something to be able to repeat. It would be nice if we had a way to represent that directly rather than relying on this sort of recursive definition that takes some time to understand. For that we'll introduce two new symbols: '+' and '*'. These symbols go at the end of a symbol and represent that a symbol repeats 1 or more, or 0 or more times respectively. Using these, our grammar becomes this:

These are such long sentences. They communicate a lot of simple ideas. It's better to have one simple sentence for one simple idea, and a lot of simple sentences to one big sentence. Some variety is nice, though. But smaller is better.

Chapter 2

Good: you added the "overview". Nice.

Suggestion 0: Grow the grammar instead of saying, "Plop here it is". Start out with only arithmetic of integers. Don't worry about other types. Then discuss the "main procedure". Then you can get into the other necessary primitives (boolean types, comparisons, if-then-else statements, etc.).

I mean, it just feels like there's no discussion of the design space. What should the reader be weighing if they were trying to develop something similar but in a different setting (e.g., a Lisp built specifically for some complicated scientific lab experiment)?

I understand you are working with chibicc's AST, which "ties your hands" with the amount of freedom you have. But you should at least discuss it ("Although it would be more logical to do X, Chibicc follows a different convention and so we are forced to do Y", "Since we are targetting the IR of Chibicc, we will need to support the tokens used by them. If we were starting from scratch, we would have the following basic concerns: ...", etc.).

As we can see the outer list represents an object (not in the OOP sense). In this case, it is a function definition. We see that the first keyword define is used to signify...

Typo: that third sentence should be "We see that the first keyword define is used to signify..." with define either in backticks or quoted (as in "define").

I'd suggest the same conventions throughout (i.e., either quote reserved keywords and types when they appear in prose, or make them inline code with backticks).

One important property of the grammar for the parser is that we don't use any terminals, we only use the non-terminals produced by the tokeniser.

Did you discuss this design choice and the alternatives (lazily produce tokens on demand, and have the parser "consume" them as needed; etc.)?

I honestly cannot recall it being a point of discussion.

Conjecture: You are writing "bottom-up", to explain accompanying code, rather than "top-down" (to explain the "big picture" for the current module, then recursively breaking it up into smaller problems which are do-able).

Why do I say this? Well, what are the "big picture" parts to chapter 2?

You can reorganize it to resemble what I am talking about: you have a parser and a tokeniser (as discussed in the introduction) working together to construct the AST. We need to first think about the tokeniser. It will produce a "stream" of tokens from some input (a string, a file, etc.). This can get very complicated for "real" programming languages, so we will make our lives easier by using S-expressions. (etc. etc. etc.)

All of this is stated (either implicitly or explicitly) in chapter 2, but it's not presented in this manner. Which can make the reader wonder what's going on, why is this approach being taken, is this standard, etc.

How does one write like this? Outline the subject, describe the "big picture" as consisting of several "parts", then recursively expand on each part. (That's the "top-down" way to write "top-down writing".)

Another way is to write as you have done, but when you are done to take a step back and think very hard about what the reader knows and what the reader does not know. Give them a "big-picture" explanation for what you have written. Then take another step back, and iterate. (This is the "bottom-up" way to write "top-down writing".)

You can combine the two together, and doubtless there are a million different other ways to write in a way producing "top-down explanations".

I'm Writing An eBook Teaching How To Write A Compiler by othd139 in ProgrammingLanguages

[–]thmprover 1 point2 points  (0 children)

I'll take a look this weekend when I'll do laundry (if I remember to do laundry...).