this post was submitted on 11 Apr 2024
13 points (93.3% liked)
Programming Languages
1177 readers
1 users here now
Hello!
This is the current Lemmy equivalent of https://www.reddit.com/r/ProgrammingLanguages/.
The content and rules are the same here as they are over there. Taken directly from the /r/ProgrammingLanguages overview:
This community is dedicated to the theory, design and implementation of programming languages.
Be nice to each other. Flame wars and rants are not welcomed. Please also put some effort into your post.
This isn't the right place to ask questions such as "What language should I use for X", "what language should I learn", and "what's your favorite language". Such questions should be posted in /c/learn_programming or /c/programming.
This is the right place for posts like the following:
- "Check out this new language I've been working on!"
- "Here's a blog post on how I implemented static type checking into this compiler"
- "I want to write a compiler, where do I start?"
- "How does the Java compiler work? How does it handle forward declarations/imports/targeting multiple platforms/?"
- "How should I test my compiler? How are other compilers and interpreters like gcc, Java, and python tested?"
- "What are the pros/cons of ?"
- "Compare and contrast vs. "
- "Confused about the semantics of this language"
- "Proceedings from PLDI / OOPSLA / ICFP / "
See /r/ProgrammingLanguages for specific examples
Related online communities
- ProgLangDesign.net
- /r/ProgrammingLanguages Discord
- Lamdda the Ultimate
- Language Design Stack Exchange
founded 1 year ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
Yes, I know some of those words. Could you repeat that for those that aren't mathematicians or in the know?
Anti Commercial-AI license
As you already figured out the types are sets with a certain number of elements.
Two types are isomorphic if you can write a function that converts all elements of the first one into the elements of the second one and a function which does the reverse. You can then use this as the equality.
The types with the same number of elements are isomorphic, i.e True | False = Left | Right. For example, you can write a function that converts True to Left, False to Right, and a function that does the reverse.
Therefore you essentially only need types 0, 1, 2, 3, ..., where type 0 has 0 elements, type 1 has 1 element, etc. and all others are isomorphic to one of these.
Let's use (*) for the product and (+) for the sum, and letters for generic types. Then you can essentially manipulate types as natural numbers (the same laws hold, associativity, commutativity, identity elements, distributivity).
For example:
2 = 1 + 1 can be interpreted as Bool = True | False
2 * 1 = 2 can be interpreted as (Bool, Unit) = Bool
2 * x = x + x can be interpreted as (Bool, x) = This of x | That of x
o(x) = x + 1 can be interpreted as Option x = Some of x | None
l(x) = o(x * l(x)) = x * l(x) + 1 can be interpreted as List x = Option (x, List x)
l(x) = x * l(x) + 1 = x * (x * l(x) + 1) + 1 = x * x * l(x) + x + 1 = x * x * (l(x) + 1) + x + 1 = x * x * l(x) + x * x + x + 1 so a list is either empty, has 1 element or 2 elements, ... (if you keep substituting)
For the expression problem, read this paper: doi:10.1007/BFb0019443