[HN Gopher] Algebraic Data Types for C99
___________________________________________________________________
Algebraic Data Types for C99
Author : bondant
Score : 286 points
Date : 2024-05-09 11:31 UTC (11 hours ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| naasking wrote:
| Definitely looks nicer and probably works better than my older
| attempt [1], but uses 8x more code and depends on the awesome but
| kinda scary Metalang9 macro toolkit. I think libsum is a good
| intro if you want to see how algebraic data types work
| underneath.
|
| [1] https://github.com/naasking/libsum
| Hirrolot wrote:
| I have a star on your repository, so it seems I was looking
| into it while designing Datatype99 :)
| cryptonector wrote:
| GH stars kinda function as a bookmark system, except I never
| go looking at what all I've starred, so it's more of an
| optimistic bookmark system.
|
| I only sometimes use it as a "I would recommend this repo" --
| how can one do that anyways, given that the repo could morph
| into something one would no longer recommend?
| different_base wrote:
| One of the crimes of modern imperative programming languages is
| not having ADTs (except maybe Rust) built-in. It is such a basic
| mental model of how humans think and solve problems. But instead
| we got inheritance and enums which are practically very
| primitive.
| skywal_l wrote:
| Zig is a modern imperative programming language with ADTs:
| https://ziglang.org/documentation/master/#Tagged-union
| madeofpalk wrote:
| Also Typescript
| https://www.typescriptlang.org/docs/handbook/2/everyday-
| type...
| fanf2 wrote:
| Union types are not the same as sum types.
| dtech wrote:
| TS narrows union types cases based on conditionals like
| "if" (called discriminated unions in the docs in the
| past), and supports exhaustiveness checks. How do they
| differ in functionality from sum types?
| mpawelski wrote:
| Supports exhaustiveness checks only if you explicitly
| opt-in it (by coding to pattern where you use helper
| function that accepts `never` type). "Dicriminated Unions
| Type"/"Sum Types" feels very hacky there, at least
| syntax-wise, because it is constraint by being "JS +
| types" language. It's remarkable what Typescript can do,
| but having native Discriminated Unions in JS (hence in TS
| too) would be much more ergonomic and powerful.
| nyssos wrote:
| Sum types are _disjoint_ unions. This `T` has three cases
| L = { tag: "a", payload: string } | { tag: "b", payload:
| number } R = { tag: "b", payload: number } | {
| tag: "c", payload: boolean } T = L | R
|
| whereas a proper sum type `L + R` would have four.
| brabel wrote:
| Isn't that a completely useless distinction?
|
| For all purposes and intents, the "b" type in L and R
| should be treated the same, no? What do you gain by not
| doing that??
| hexane360 wrote:
| This often comes up when writing a function which returns
| a wrapper over a generic type (like Option<T>). If your
| Option type is T | null, then there's no way to
| distinguish between a null returned by the function or a
| null that is part of T.
|
| As a concrete example, consider a map with a method
| get(key: K) -> Option<V>. How do you tell the difference
| between a missing key and a key which contains `null` as
| a value?
| brabel wrote:
| This is trivial to model by making your type `T | null |
| Missing`.
| efnx wrote:
| Maybe trivial to "work around" but there is a difference,
| ay?
|
| With this type you would have to check/match an extra
| case!
|
| The type you use there also takes more memory than
| Option<T> or Maybe<T>. So it has some other downsides.
| epolanski wrote:
| Or just using Option since you would have Some<null> or
| None in that case.
| epolanski wrote:
| `T | null` is equivalent to T. You can assign null to
| `T`>
|
| It's like saying `string | "foo"` it is simply `string`
| due to subtyping.
| Twisol wrote:
| No, it isn't "completely useless".
|
| If you have a function that will normally return a
| string, but can sometimes fail due to reasons, you may
| wish to yield an error message in the latter case. So
| you're going to be returning a string, or a string.
|
| It's not what the content of the data is; it's how you're
| supposed to interpret it. You have two cases, success and
| failure, and control will flow differently depending on
| _that_ , not based strictly on the type of data at hand.
| We just model those cases in a type.
| akavi wrote:
| As you've demonstrated, you can always _construct_ sum
| types in typescript with the use of explicit
| discriminants: T = {tag: "L", payload:
| L} | {tag: "R", payload: R}
|
| The real issue is typescript doesn't have pattern-
| matching, which make operating on these sum types
| inelegant
| chem83 wrote:
| F# too. And Elm. But I get your point.
| chongli wrote:
| While this is a step up from C, it is still a long way from
| the full power and generality of algebraic data types. The
| key word here is algebraic. In a language with ADTs, such as
| Haskell, you can pattern match on an arbitrarily complex
| types, not just the outermost tag. A contrived example (from
| [1]): contrived :: ([a], Char, (Int,
| Float), String, Bool) -> Bool contrived ([], 'b',
| (1, 2.0), "hi", True) = False
|
| To achieve a result like this using Zig's switch syntax would
| seem to involve a huge amount of boilerplate code and nested
| switch statements.
|
| [1] https://www.haskell.org/tutorial/patterns.html
| Hirrolot wrote:
| This is more of syntax sugar than power and generality,
| since nested pattern matching can be mechanically
| translated into "top-level" matching (e.g., see [1] and
| [2]).
|
| [1] L. Augustsson. Compiling Pattern Matching. In
| Functional Programming Languages and Computer Architecture,
| pages 368- 381, 1985.
|
| [2] P. Wadler. Efficient Compilation of Pattern Matching.
| In S.L. Peyton Jones, editor, The Implementation of
| Functional Programming Languages, pages 78-103. Prentice
| Hall, 1987.
| chongli wrote:
| This argument is the most common fallacy I see in
| programming language discussions. I might as well give it
| a name right here: "Turing equivalence fallacy" or
| perhaps "syntax sugar fallacy."
|
| All Turing Complete programming languages are Turing
| equivalent to one another. Programs written in one
| language can be mechanically transformed into those
| written in another. This is irrelevant to the discussion
| of programming languages. The whole point of creating
| different programming languages is to explore different
| ways to express the same program!
| Hirrolot wrote:
| In programming language design, we tend to distinguish
| between global and local analysis. While type checking
| and elaboration is an example of global analysis,
| desugaring is inherently local to some piece of code.
| Therefore, "power" or "expressiveness" usually mean that
| something cannot be syntactically "expanded"; e.g., while
| type classes elaborate into explicit dictionaries, they
| still require information from the type checker, and
| therefore considered a "real" feature of a programming
| language. On the other hand, nested pattern matching can
| be formulated as local syntax transformation, and
| therefore it doesn't bring anything fundamentally new to
| the type system or dynamic semantics.
|
| There's also a great talk on the matter [1], if somebody
| is interested in formalities.
|
| [1] https://www.youtube.com/watch?v=43XaZEn2aLc
| mitt_romney_12 wrote:
| You're approaching this from a PL design standpoint where
| the distinction is important, but from a user perspective
| it doesn't matter if it's just "syntax sugar" or if it's
| a super complicated to implement all that matters is
| whether the feature is available or not.
| Hirrolot wrote:
| Typing features affect the way we design APIs. Libraries
| written in languages with type classes and without them
| can have completely different designs. If nested pattern
| matching is not available, this will not affect the APIs,
| only the function bodies -- because desugaring is local
| by definition.
| chongli wrote:
| That doesn't matter in practice. If two programming
| languages have the same underlying feature but one has
| syntactic sugar to make it very easy to use and the other
| does not (so is quite cumbersome to use) then you'll find
| that the library ecosystem for the former language will
| see the feature in widespread use whereas the ecosystem
| of the latter will tend to shun the feature.
|
| This is one of the social factors of programming language
| design and it's one of the main reasons successful
| programming languages work so hard to establish a
| coherent philosophy and a set of best practices or idioms
| within the language. For similar reasons, I believe this
| is why "anything goes" languages such as LISP have
| struggled to gain widespread adoption: with no philosophy
| every programmer becomes an island unto themselves.
| Hirrolot wrote:
| Yes, features that are easy to use will be more often
| used, while inconvenient features will be less used. I
| don't quite see any controversy with my comment.
| chongli wrote:
| The point is that in both cases the underlying feature is
| present, so APIs will be compatible. However, the lack of
| syntactic sugar in the one case will make any API that
| uses the feature cumbersome to use in that language, so
| in practice it will be avoided.
| tialaramex wrote:
| Abstractly this is true, but software development is a
| human practice, so it matters not what's technically
| possible but what people actually do.
|
| That's why the _most important_ difference between C++
| and Rust isn 't some technicality even though the
| technical differences are huge, it's _cultural_. Rust has
| a Safety Culture and everything else is subservient to
| that difference.
|
| Sugar matters, Rust's familiar looking loops are just
| sugar, it only "really" has a single way to do loops, the
| loop construct, an infinite loop you can break out of.
| But despite that, people deliberately write the other
| loops - and the linter strongly recommends that they
| write them, because the programs aren't just for machines
| to compile, they're for other humans to read, and a while
| let loop is an intuitive thing to read for example, so is
| the traditional for-each style iterator loop.
| gpderetta wrote:
| > Turing equivalence fallacy
|
| Better known as the Turing Tar Pit.
| OskarS wrote:
| Of course the syntax sugar is a good thing if it makes it
| easier to write the code, but if the question is about
| "expressive power of the type system", it's not really
| relevant: Zig's type system can properly express a sum
| type. In addition: pattern matching is orthogonal to ADT,
| you can have pattern matching in both languages with and
| without algebraic types. Neither one implies the other.
| anon-3988 wrote:
| > Zig's type system can properly express a sum type.
|
| Surely any Turing complete PL can express a sum type? I
| can't imagine a language that can support products but
| not sums.
| Tainnor wrote:
| Turing completeness has nothing to do with static type
| checking. Dynamically typed PLs can't express any type
| (except Any) yet are still Turing complete.
| xdavidliu wrote:
| syntax sugar IS power. also if the mechanical
| transformation is nontrivial, then so is the power of the
| sugar
| bunderbunder wrote:
| This is where I like to cite Dijstra's "Go To Statement
| Considered Harmful".
|
| What a lot of people miss about that paper is that he
| wasn't _just_ talking about goto statements. He was also
| making a more general observation about how more powerful
| and general programming language features are not
| necessarily desirable, because they tend to adversely
| impact developer productivity.
|
| The reason I, as a user, prefer structured control flow
| statements over goto is not that I believe they are
| powerful. It's precisely because they are _less_
| powerful. The resulting constraints on how the program
| can be structured make it easier for me to read and
| reason about existing code. That makes maintaining code
| easier. It also makes optimization and static analysis
| easier. And it makes writing tests easier, too.
|
| I have similar feelings about ADTs. The reason I prefer
| them to other ways of doing composite data types is not
| that I think they're more powerful. It's that they create
| constraints that tend to reduce the semantic complexity
| of the domain models people create in programming
| languages that use them. And that makes my job easier.
|
| The corollary to that, though, is that I'm not actually
| all that hype about adding ADTs to existing languages.
| For reasons that are similar to how the mere availability
| of structured, reentrant function calls is small
| consolation in a codebase that's already riddled with
| goto statements. The real win doesn't come from using
| ADTs, it comes from not having to worry about all those
| other confusing overpowered things that aren't ADTs.
| ajross wrote:
| That's exactly where I am. Pattern matched sum types
| "feel great" to code in to an expert because they are a
| concise and reasonably tight way to express the otherwise
| boring "enumerate over possibilities" code.
|
| But _they 're hard to read_ for anyone who isn't an
| expert on not just the language but the type in question
| (c.f. Rust's Option() idioms all looks like line noise to
| newbies, etc...). And that's a bad trade.
|
| In essence, this stuff is just Perl all over again. It's
| a language feature that prioritizes concision over
| comprehension. And I say that as someone who really likes
| coding in perl. But "people" don't like perl, and the
| community moved on, and the reasons are... the same
| reason that uptake in ADTs is lagging where the experts
| want it to be.
| bunderbunder wrote:
| You've got to distinguish syntax from semantics, though.
| I agree, it's easy to turn a big semantic win into a net
| readability loss if you choose to represent it with an
| overly terse syntax that promotes code golf.
| ajross wrote:
| Compilers are really smart. It's easy enough in the
| modern world to demand that a "type" field be checked
| against all enumerants, preserving the "semantic win". A
| plain old C switch statement with gcc -Wall will do this
| today, in fact.
| jerf wrote:
| Pattern matching on the "top level branch" of the ADT,
| whatever you call it, is pretty darned useful.
|
| Pattern matching on the next level down is a power tool
| to be used with care.
|
| Having used some pattern matching languages for quite
| some time, I find anything much deeper than that is a
| code smell at best and pathological at worst. Pattern
| matching creates coupling proportional to the
| depth/complexity/precision of the pattern match. The top-
| level coupling is often unavoidable; if you're pattern
| matching at all, you certainly care which "branch" you
| are on and there is likely no refactoring that away. But
| the danger rises rapidly the deeper in you go. It's just
| so easy to pattern match on a third-level part of the
| complex object when you really ought to be wrapping that
| behind a function somewhere, possibly itself emitting a
| sum type value.
|
| ... but if all you really _need_ is that "top level"
| match, a lot of pattern matching syntax and features are
| not really necessary (if not positively dangerous).
| ajross wrote:
| > Pattern matching on the "top level branch" of the ADT,
| whatever you call it, is pretty darned useful. Pattern
| matching on the next level down is a power tool to be
| used with care.
|
| Which is _exactly_ how Perl apologia arguments went.
| thesz wrote:
| I once explored the Epigram dependently typed programming
| language. It used to preclude many types of free form
| pattern matches, due to heavy dependence on structured
| editor (you speciy a type, it generates pattern matching,
| you cannot change the structure), so it was almost
| completely unuseable for many, many tasks.
|
| So, while you are formally right, the need of shortcuts
| in pattern matching is undeniable to me.
| tombert wrote:
| Yeah, when I first learned Haskell a million years ago, and
| Erlang slightly less than a million years ago, the pattern
| matching was so plainly obviously the "correct" way to do
| things; it just felt like it was exactly how I thought about
| problems, and all the constructs with if/switch/enums had been
| an attempt to force my brain thinking into something that
| executes.
|
| It honestly does annoy me that a lot of mainstream languages
| still haven't really adopted ADTs; when Java 8 added a lot of
| (well-needed) new syntax, it felt like that was an ideal
| opportunity to add ADTs and pattern matching (though I'm sure
| that was easier said than done).
| kaashif wrote:
| > when Java 8 added a lot of (well-needed) new syntax, it
| felt like that was an ideal opportunity to add ADTs and
| pattern matching
|
| Well at least Java does now (as of Java 21) have pattern
| matching (including nested record destructuring) and sealed
| classes, which let you have decent sum types.
|
| The one issue is that everything is nullable, but that's a
| wider Java issue.
| tombert wrote:
| Yeah, but the annoying part of Java is that people stick
| with old versions for a long time. Java 21 looks pretty
| great but most companies are still using Java 17, or even
| Java 11 still.
| cess11 wrote:
| Some have even older Java versions in 'prod'. 6 is still
| alive in some places out there, because management
| refuses to pay for either upgrade, replacement or
| dismantling.
|
| I have a mid-sized application I built on 17 that's used
| to deliver a particular project, really looking forward
| to finish the project so I get to move to 21 and refactor
| it with these new features and make it more general.
| tombert wrote:
| Oof, I didn't know that anyone still used Java 6
| anywhere. I have to think that it's a potential security
| nightmare at this point isn't it?
| Tainnor wrote:
| It is. We run an old version of our application on Java
| 6. Apparently multiple people have tried to upgrade it in
| the past but it proved too difficult because it's using a
| bunch of completely obsolete technology with little
| available documentation that seems to randomly break when
| you upgrade even minor things.
|
| The plan has been to gradually replace it with the new
| version of the software (which runs on Java 17),
| unfortunately this plan has been ongoing for 10 years and
| it's not gonna be done anytime soon.
|
| Such are the sad realities of working on legacy code
| sometimes.
| cess11 wrote:
| Absolutely, so you try to seal it in hermetically, only
| talk to it over a special message bus or something.
|
| Sometimes the upgrade path from 6 onwards isn't as nice
| as it usually is from 8 up, especially if you built with
| some old undead libraries that require an heroic effort
| to understand well enough to reimplement. Takes a very
| special organisation to divert some person-years to pull
| it off, and as some middle or other manager it's highly
| unlikely to catch you a new, better job even if it goes
| well.
| tombert wrote:
| It makes me sad, but I totally understand _why_ someone
| would stay with Java 6, for the same reason that there 's
| still COBOL stuff hanging around: the stuff "works" as
| is, upgrading is expensive, and some business person
| decided that the cost of the upgrade isn't worth it for
| the value they'd receive.
|
| I do worry that there's "Y2K-esque" bugs hiding in Java 6
| programs somewhere. I don't think java.util.date uses 32
| bit integers for time so the 2038 problem probably won't
| be an issue, but I do wonder if there's other stuff
| hiding.
| cess11 wrote:
| There might be some limit or bug like that in Java 6, but
| I think time stuff has been backported, so it'd likely be
| something else. I don't know enough about the JVM
| internals to speculate on whether the old ones were
| simpler and less likely to be defective, or not.
|
| By now most types of issues ought to have popped up
| though, since it was so widely used for such a long time.
| jjice wrote:
| I've never written Swift, but it seems like they have it too
| https://docs.swift.org/swift-book/documentation/the-swift-pr...
|
| I also would love a future where ADTs are more common in
| imperative languages
| odyssey7 wrote:
| Swift "enumerations" are _very_ nice.
| zozbot234 wrote:
| Pascal has had variant records since the 1970s.
| adrian_b wrote:
| But Pascal's variant records (1970-11) had very ugly design
| errors in comparison with the unions of Algol 68 (1968-12),
| which made them either useless or annoying for most
| applicatons.
|
| Niklaus Wirth is well known as a critic of Algol 68 (before
| the design of Algol 68 was finalized), but in the case of his
| variant records he has completely failed to create something
| competitive.
| pjmlp wrote:
| Given where Algol 68 ended up, I would say Wirth was quite
| right.
| adrian_b wrote:
| Algol 68 was a failure mainly due to its inappropriate
| documentation, not due to the quality of the language.
|
| It included many innovations that appeared again in other
| programming languages only decades later.
|
| Niklaus Wirth was a good teacher and writer and the
| success of his languages is due mostly to his books and
| due to his languages being used for teaching in many
| universities, not due to their technical qualities.
| peoplefromibiza wrote:
| > not due to their technical qualities
|
| AFAIK Pascal is C and Algol 68 is C++
|
| people used Pascal because the compiler was blazing fast,
| it was easier to implement and learn and the features it
| lacked against Algol did not really matter most of the
| time (at the time)
|
| More features doesn't automatically means "better"
|
| Also Pascal had quite strong technical qualities, not
| very common among other contemporary languages
|
| edit: can I ask the reason for the downvote? I would
| really like to hear an opinion on what Pascal did wrong,
| having used it extensively in the late 80s until the end
| of the 90s and why my comment was awarded with a negative
| score.
| adrian_b wrote:
| Extended variants of Pascal, like Turbo Pascal, should
| not be confused with the Pascal language as designed by
| Niklaus Wirth.
|
| Wirth's Pascal was a language designed for the purpose of
| teaching programming and it was adequate for that, but it
| was completely inappropriate for any serious work.
|
| It had no means for writing big programs that must be
| divided into multiple source files and it had a lot of
| design errors, like including the size of an array in its
| data type (which made impossible the writing of any
| linear algebra library) or the way of handling the
| variant records (which was insecure and verbose).
|
| The well known paper "Why Pascal Is Not My Favorite
| Programming Language" by Brian W. Kernighan contains
| valid arguments against Pascal (against Wirth's Pascal,
| there have been many extended Pascals, especially
| following Turbo Pascal, which have corrected some of the
| most egregious defects of the original Pascal).
| pjmlp wrote:
| People keep playing this tired song, while clearly
| ignoring that until ISO C89, even C was full of dialects,
| a mix of K&R C and whatever the compiler writer felt
| like, filled with tons of Assembly.
|
| Small-C, RatC,....
|
| Additionally forgetting that Modula-2 came out in 1978,
| as means the sort out all those issues, a language
| designed for systems programming, instead of the "Python"
| from 1970, designed for teaching.
|
| With features that C is yet to have, 50 years later,
| while HN is hypping for having them in a C like syntax
| delivered in a Zig package.
| peoplefromibiza wrote:
| I know that paper and personally I think some of the
| critiques are actually qualities of pascal, making it,
| while certainly not a completely refined language, a more
| modern language than C
|
| - no escape (AKA no casting): good!
|
| - no default clause in case: good idea, not so good
| implementation (undefined behaviour)
|
| - no break outside for loops: inconvenient, but that's
| how FP works. it is still debated today if breaking loops
| is considered a good or a bad practice
|
| - no separated compilation: I will quote Kernighan on
| this _Theoretically, there is no need for separate
| compilation - if one 's compiler is very fast_ Pascal
| compiler was fast, maybe not _very_ fast, but speed was
| one of the primary goals for Wirth.
|
| many other issues were similar in other languages and in
| C
|
| Pascal had obviously its faults, but every language back
| then had some
|
| Pascal was simple enough to make it easy to compile and
| implement. That's what Wirth thaught, he's the author of
| _Compiler Construction_ after all, it wasn 't like
| learning Python today as a data scientist
|
| make the language more complex (and more
| useful/interesting) and you're stuck with a very slow or
| very buggy compiler that very few people would know how
| to implement
|
| I think there's a reason why we had Turbo Pascal and not
| Turbo Algol 68
| pjmlp wrote:
| I beg to differ, after Modula-2 and Object Pascal (Apple
| designed it with Wirth's feedback).
|
| Most of his languages ended up losing, because they
| weren't being shipped with a free beer OS, coupled with a
| free beer compiler.
| cryptonector wrote:
| Algol 68 may have been a failure because it was ahead of
| its time, which meant it was hard to write a compiler for
| it. For example, Algol 68 had closures (apparently Knuth
| snuck them in).
| mzs wrote:
| Doesn't look too bad particually the _match_ tagged version
| last: MyType= (Scalar4, Real4,
| NullTerminatedStringC); MyUntaggedRecType=
| RECORD CASE MyType OF Scalar4: (longC:
| ARRAY[1..150] OF longint); Real4: (floatC:
| ARRAY[1..150] OF real); END;
| MyTaggedRecType= RECORD CASE tag:
| MyType OF Scalar4: (longC: ARRAY[1..150] OF
| longint); Real4: (floatC: ARRAY[1..150] OF
| real); END; ... { set
| all to 0.0 without running through the MC68881 } FOR
| j := 1 TO 150 DO longC[j]:= 0; ...
| CASE tag OF Scalar4: percentReal = longC[1];
| floatC: percentReal = floatC[1]*100; ELSE
| percentReal = 0.0/0.0;
|
| edit: don't have a pascal compiler handy, but that's the
| idea
| adrian_b wrote:
| Moreover, they have already been proposed by John McCarthy in
| October 1964, 60 years ago, for inclusion in the successor of
| ALGOL 60, which makes even more weird the lack of widespread
| support.
|
| (And in fact Algol 68 had a better implementation than most
| later languages, but Algol 68 was missing completely any
| documentation suitable for newbies, like tutorials and
| programming examples, while not being promoted by any hardware
| vendor, like IBM or DEC, so it was doomed.)
| floxy wrote:
| >The more I ponder the principles of language design, and the
| techniques which put them into practice, the more is my
| amazement and admiration of ALGOL 60. Here is a language so
| far ahead of its time, that it was not only an improvement on
| its predecessors, but also on nearly all its successors.
|
| https://web.eecs.umich.edu/~bchandra/courses/papers/Hoare_Hi.
| ..
| debo_ wrote:
| ADT feels like an unfortunately acronym-collision with
| "Abstract data types."
| pjmlp wrote:
| Yep, people that eventually buy a Modula-2 ADT book, when
| hunting old stuff, are in for a surprise. :)
| debo_ wrote:
| It's a term that is commonly used in computer science
| education to refer to any data type independent of its
| concrete implementation (so, basically, its interface.) I
| don't think it's just restricted to Modula-2?
| pjmlp wrote:
| Indeed, however CLU and Modula-2 were the ones used
| mostly for practical teaching purposes, until ML became
| widespread enough for ADT to gain yet another meaning.
| jghn wrote:
| More often than not, when I say ADT to someone outside of the
| FP world, they assume I mean abstract data type.
| bee_rider wrote:
| Or the company that sells the security stickers, for
| houses.
| Verdex wrote:
| NAND is a universal circuit primitive because it can be used to
| create all of the other circuit primitives. But if you think
| about it, this is more of an argument of manufacturing than it
| is in comprehensibility. Only needing to manufacture NAND is
| easy, but if you could only create your circuit this way, then
| you would have an unmaintainable mess.
|
| You can do the same thing with boolean logic and just have not-
| and, but thankfully we have and, or, not, xor. Similarly, you
| don't need greater-than-or-equal because you can just write 'x
| > y || x == y'.
|
| Comprehension is linked to how closely you can express the idea
| of what you're doing in the object language that you have to
| look at. It might be convenient to compile everything down to
| SK combinators so that your optimizer and evaluator can be
| simpler, but people should never look at that level (at least
| not until you suspect a compiler defect).
|
| So we get to object oriented programming. Where our data
| expression has an AND property (a class has an INT field AND a
| STRING field), an existential property (interfaces: there
| exists some object with these methods), and inheritance (a
| truly bizarre feature where we duck tape subtyping to a method
| and field grouping mechanism with a bunch of hooks).
|
| With interfaces and inheritance you can simulate both a
| universal property (generic) and an OR property. But because
| it's not a direct expression, we leave this giant gap for what
| people intended to happen to diverge from what actually
| happens. Especially after time passes, defects are found, and
| requirements change. [For example, when using interfaces to
| simulate an OR property, there really isn't any mechanism to
| let everyone know that this construct is closed. So if
| something erroneously gets added, you won't know to check the
| entire code base. And if requirement change and you need to add
| a new case, then you have to check the entire code base.
| Completeness checking of ADTs give you this for free in your
| pattern matches.]
|
| Too many non-trivial architectural messes that I've encountered
| in my career have been due to either someone trying to solve
| all of their problems with interfaces or the same with
| inheritance* when a simple OR data structure would have made
| everything simple, clear, and correct.
|
| [*] - Inheritance being more problematic when someone tries to
| create a non-trivially sized category hierarchy, which ruins
| the day when requirements change and suddenly the tree needs to
| be reorganized but doing so would invalidate entire swaths of
| the code base already accepting types with a different assumed
| (and undocumented) hierarchal tree structure. Thankfully most
| people have gotten the memo and switched to interfaces.
| taeric wrote:
| I'm curious on supporting evidence for it being a basic mental
| model of how humans think? That sounds like a fairly strong
| claim.
| Verdex wrote:
| I'm a huge proponent of ADTs being a more comprehensible way
| to write code than some of the alternatives. But I do have to
| agree with you that there isn't really evidence that this is
| a basic mental model.
|
| However
|
| What we do see is a bunch of mathematical disciplines that
| end up creating properties like: AND, OR, Universal,
| Existential, Implication, (and a few others). They end up in
| places like: set theory, type theory, category theory,
| various logics, lattice theory, etc.
|
| Now, maybe they're only copying one another and this is more
| of a memetic phenomena. Or maybe they've hit upon something
| that's important for human comprehensibility.
|
| That would be the 'evidence' of the positive effect of ADTs
| (scare quotes because it might just be math memes and not
| fundamental). But we can also think about what I feel is
| legit evidence for the negative effect of lacking ADTs.
|
| Consider what happens if instead of having the standard
| boolean logic operators and, or, not, xor, we only have the
| universal not-and operator. Now a straightforward statement
| like: A && B || C becomes (((A !& B) !& (A !& B)) !& ((A !&
| B) !& (A !& B))) !& (B !& B) [I think...]. It's more
| complicated to tell what's actually supposed to be going on
| AND the '&&' simulation can get intertwined with the '||'
| simulation. The result being that requirements changes or
| defect fixes end up modifying the object level expression in
| a way where there is no longer any mapping back to standard
| boolean logic. Comprehensibility approaches zero.
|
| And we've seen this happen with interfaces and inheritance
| being used to implement what would otherwise be a relatively
| simple OR property (with the added benefit that pattern
| matching ADTs often comes with totality checking; not
| something you can do with interfaces which can always have
| another instance even up to and including objects loaded at
| runtime).
| taeric wrote:
| Appearing in symbolic reasoning tools we have invented
| doesn't really support them being how brains work, though?
| This is akin to saying that gears are how nature works
| because gears are everywhere in how we build things. I
| could maybe buy that with "friction" being a fundamental
| thing, but feels like a stretch for the other.
|
| Now, I should add that I did not mean my question to be a
| criticism of them! I'm genuinely curious on evidence that
| they are a basic building block. Feels save to say they are
| a good building block, and those aren't the same thing.
|
| As an easy example for them not being basic building
| blocks, I can't remember ever seeing anything like them in
| any assembly instructions for things. Put together a
| batting net for the kids. Lots of instructions, but nothing
| algebraic, in this sense. Looking at recipes for food.
| Nothing algebraic, really? Maybe I can squint and see some,
| but it would be hard. Exercise plans? Music lessons?
| Playbooks for a sport?
|
| Again, though, I /do not/ intend this as a criticism of
| them. Genuinely curious on any investigation into them.
| humzashahid98 wrote:
| I think you're right to point out that it's too strong a
| claim to say that sum types are a basic building block of
| thought, although I believe they are very useful in
| coding regardless of that claim.
|
| There is the still the ongoing debate about how much
| human perception and human reason are shaped by cultural
| forces vs. universal forces (where the latter asserts
| humans reason in the same/similar ways).
|
| There's evidence that certain optical illusions don't
| work across cultures for example (I seem to remember
| those in Western countries have a tendency to mentally
| group things in rectangular boxes). The exact balance
| between cultural and universal forces isn't known and I
| doubt we could say anything about sum types in that
| regard.
| naasking wrote:
| Verdex's explanation is detailed but too long IMO. The short
| version is that ADTs/sum types formally correspond to the OR-
| logical connective, and records/product types formally
| correspond to AND-logical connective. I think you'd be hard-
| pressed to argue that people don't think in terms of "X AND Y
| OR Z". These are core primitives of any kind of reasoning.
| taeric wrote:
| I can easily argue that people don't think in terms of
| boolean logic. For one, the evidence seems as strong that
| people generally think backwards from the answer far more
| than they do forwards from the ingredients. This is often
| why new things are so long to be discovered. It isn't that
| people couldn't have gotten there, but they didn't know to
| go for it.
|
| For two, addition is a wildly disparate thing everywhere we
| use it. We like to joke that computers made that hard, but
| literally half of intro chemistry is learning how to get
| thing to add together in a meaningful way, no? Balancing a
| chemical equation is a thing.
| naasking wrote:
| > For one, the evidence seems as strong that people
| generally think backwards from the answer far more than
| they do forwards from the ingredients.
|
| Logic doesn't really have a direction, it works backwards
| or forwards. Even if you're solving a system "backwards",
| whatever that means, you still have to satisfy all of the
| necessary AND and OR constraints for a solution to be
| valid, so you're effectively still building ADTs or
| records just using a different evaluation order.
| taeric wrote:
| And this logic is how folks convince themselves that ball
| players are doing trigonometry when playing. It is just
| wrong.
|
| You can /model/ it that way. But you are making a
| symbolic model to justify how a solution is reached.
|
| Now, it can be frustrating to consider that this model
| could produce an agent that is better at the ball game
| than the players. But it is silly to think that means you
| have mirrored them.
| mgaunard wrote:
| C has always had them, it's called union.
|
| In practice you need to couple it with an enum, and your
| visitation mechanism is a switch statement. But C doesn't
| impose that on you and lets you do it as you see fit.
| duped wrote:
| You're confusing semantics for implementation. The point of
| union and discriminated union _types_ (not what C calls
| union) is to enable compiler checked pattern matching, which
| tagged enums in C plus a switch statement do not get you.
| estebank wrote:
| Tagged unions + pattern matching is what gp wants. You can
| always encode whatever model you want using any programming
| language, but language features/ergonomics matter.
| coldtea wrote:
| > _C has always had them, it 's called union_
|
| It also has all the features of Haskell, since you can
| implement a Haskell compiler in C.
| naasking wrote:
| That you can _sort of_ simulate the _skeleton_ of algebraic
| data types does not mean that C has algebraic data types. The
| whole point of the _algebra_ part is that the syntax has a
| compositional semantics which is completely absent in C,
| unless you go to great lengths as with this macro header.
| bmoxb wrote:
| That is not a proper alternative to real pattern matching.
| anon-3988 wrote:
| lol this is like saying C doesn't need structs, you can just
| declare the variables with a common prefix separately! See
| ma, product types!
| grumpyprole wrote:
| Yep, or C doesn't need arrays just use pointers! And C
| doesn't need strings, just use a pointer to the first byte
| and assume it's ASCII!
| CraigJPerry wrote:
| >> not having ADTs (except maybe Rust) built-in
|
| Most of the common languages today have product types.
|
| Java[1], Rust, Haskell, etc. have sum types.
|
| I think it gets a bit more escoteric beyond that though - i
| don't doubt that there's probably some haskell extension for
| quotient types[2] or some other category theory high-jinx.
|
| Most languages have ADTs built in.
|
| [1] https://blogs.oracle.com/javamagazine/post/inside-the-
| langua... [2] https://en.wikipedia.org/wiki/Quotient_type
| speed_spread wrote:
| Java sum types work but still need a bit of syntax sugar on
| the declaration side, IMHO.
| nextaccountic wrote:
| Does Java sealed classes enable something like an exhaustive
| pattern matching? (A form of pattern matching that will fail
| at compile time if you add a new class that extends the
| sealed class)
| thewakalix wrote:
| > The intent is to introduce a more-advanced construction
| called pattern matching in a later release.
| brabel wrote:
| You read that in a blog post from 2019.
|
| Java has had comprehensive pattern matching since Java
| 21, like one year ago (current Java version is 22).
|
| I posted an answer to the same parent comment with the C
| example written in Java...
|
| You can read more about it here:
| https://www.baeldung.com/java-lts-21-new-features
| brabel wrote:
| Yes, since Java 21.
|
| Example: sealed interface BinaryTree {
| record Leaf(int value) implements BinaryTree {}
| record Node(BinaryTree lhs, BinaryTree
| rhs, int value) implements BinaryTree
| {} } public class Hello {
| static int sum(BinaryTree tree) { return switch
| (tree) { case BinaryTree.Leaf(var value) ->
| value; case BinaryTree.Node(var lhs, var rhs,
| var value) -> sum(lhs) + value + sum(rhs); };
| } public static void main(String...
| args) { var tree = new BinaryTree.Node(
| new BinaryTree.Leaf(1),
| new BinaryTree.Node(
| new BinaryTree.Leaf(2),
| new BinaryTree.Leaf(3),
| 4), 5);
| System.out.println(tree);
| System.out.println("Sum: " + sum(tree)); }
| }
|
| If you added a new subtype to BinaryTree you would need to
| fix the switch.
|
| EDIT: I didn't handle the `null` case above... so it would
| be a NullPointerException if someone passed null...
| apparently, Java decided to make handling `null` optional.
| More information: https://www.baeldung.com/java-lts-21-new-
| features
| nextaccountic wrote:
| Okay that's better than I expected!
| davidalayachew wrote:
| It absolutely does. Here is a (modified) snippet of my Java
| code from yesterday. final boolean
| hasUncollectedSecret = switch (each)
| { case Wall() ->
| false; case Goal() -> false;
| case Player p -> false; case
| BasicCell(Underneath(_, var collectible), _)
| -> switch (collectible)
| { case
| NONE, KEY -> false; case SECRET ->
| true; };
| case Lock() -> false; };
| thewakalix wrote:
| Java doesn't have pattern-matching yet. Haskell is not an
| imperative language.
| j2kun wrote:
| Your examples, on the TIOBE index, are #4, #18, and #28.
| https://www.tiobe.com/tiobe-index/
| CraigJPerry wrote:
| Product types are one kind of algebraic data type, only 5
| languages from that TIOBE page don't have them so most
| common langs have ADTs
| dannymi wrote:
| When you have natural numbers and a multiplication
| operation (product) would you say that those form an
| algebra? (ADT means algebraic data type)
| LegionMammal978 wrote:
| Java's sealed classes are still somewhat more limited than
| Rust's or Haskell's sum types, in that each instance of the
| superclass holds a fixed variant (i.e., subclass), so you
| can't change the variant without creating a new instance.
| Clearly, this limitation is necessary for references to stay
| intact, but I've personally ran into this issue when trying
| to represent a sum type in an ORM.
| munificent wrote:
| _> so you can 't change the variant without creating a new
| instance. _
|
| Isn't that true of ADTs in all languages? I can't think of
| a single language with ADTs that lets you change the
| tag/variant of an existing value.
| LegionMammal978 wrote:
| In Rust [0]: #[derive(Debug)] pub
| enum Example { Foo(i32), Bar(&'static
| str), } let mut ex: Example =
| Example::Foo(42); println!("{ex:?}"); // Foo(42)
| let ex_ref: &mut Example = &mut ex; *ex_ref =
| Example::Bar("hello"); println!("{ex:?}"); //
| Bar("hello")
|
| Given a mutable reference to a value of enum type, you
| can replace it with another variant. Or you can swap it
| out with any other value of the same type, even if the
| variants are different. This is most commonly used for
| Option<T>, where you can insert or remove the contained
| value as long as you have a reference.
|
| The limitation here is that for as long as the mutable
| reference is live, no other code can access the value. So
| when you do change the variant, you can't have any other
| references sitting around that point to the removed
| subfields.
|
| [0] https://play.rust-
| lang.org/?version=stable&mode=debug&editio...
| munificent wrote:
| This doesn't have anything to do with ADTs. It's because
| Rust has both in-place variables and references. You
| aren't changing the variant of an existing ADT, you're
| replacing the entire ADT value with a new one. That
| replacement is visible in multiple places because the
| language allows you to take references to variables (the
| `&mut ex` expression).
|
| You can accomplish the same thing in C and C++ because
| they also have in-place value semantics and allow you to
| take the address of any variable. You can't do that in
| Java only because Java doesn't let you take references to
| variables.
| brabel wrote:
| I don't really think it's useful to do that though?? Can
| you give an example?
|
| By the way, I would claim Java's sum types are less limited
| than Rust because in Rust, variants don't have their own
| type. The consequence is that you can't have functions that
| only accept some variant, as far as I know (I remember
| having this problem once), or add "methods" only to one
| variant... while in Java, because variants are just normal
| types, you can do both, and doing that is pretty damn
| useful.
| LegionMammal978 wrote:
| > I don't really think it's useful to do that though??
| Can you give an example?
|
| For an exercise, I had to write a system with Admins and
| Customers, with the ability to upgrade a Customer into an
| Admin, or vice versa.
|
| My thought was to put them as two subclasses under a User
| superclass, so that I could put them under a single Users
| table, and not have to link and unlink things over the
| conversion. Hibernate ORM supports storing subclasses by
| adding an implicit discriminator field.
|
| However, its object model specifies that a single row
| always corresponds to a particular instance, so it has no
| support for changing the subclass of a row. Ultimately, I
| ended up with a hacky solution of creating a new record
| with the primary key copied over.
|
| > By the way, I would claim Java's sum types are less
| limited than Rust because in Rust, variants don't have
| their own type. The consequence is that you can't have
| functions that only accept some variant, as far as I know
| (I remember having this problem once), or add "methods"
| only to one variant... while in Java, because variants
| are just normal types, you can do both, and doing that is
| pretty damn useful.
|
| At least in Rust, you can simulate this pretty trivially
| by having each variant store a struct value with all the
| data and methods you want. See proc_macro::TokenTree [0]
| for an example of this. Of course, it's not ideal in how
| verbose it is (though not much worse than Java!), but it
| can be workable on the consumer's side if you add some
| extra From impls.
|
| [0] https://doc.rust-
| lang.org/proc_macro/enum.TokenTree.html
| brabel wrote:
| Please don't forget Dart!
|
| https://medium.com/dartlang/dart-3-1-a-retrospective-on-
| func...
| ajross wrote:
| > [Algebraic Data Types are] such a basic mental model of how
| humans think and solve problems
|
| I think that's actually wrong for "Sum types". Product types,
| sure. The idea of storing a bunch of fields in a single thing
| matches the way we've been organizing information since we
| started writing things down.
|
| But I genuinely don't think I've seen an attempt at a
| sum/union/enumerant/whatever syntax in a programming language
| that wasn't horrifyingly confusing.
|
| Where by extension: class-based inheritance is actually pretty
| simple to understand. The classic "IS-A" relationship isn't as
| simple as "fields in a struct", but it's not hard to understand
| (c.f. all the animal analogies), and the syntax for expressing
| it is pretty clean in most languages.
|
| Is it the "best" way to solve a problem? Maybe not. Neither are
| ADT sum types. But I think there's a major baby-in-the-
| bathwater problem with trying to be different. I really don't
| think, for the case of typical coders writing typical code,
| that ADTs are bringing as much to the table as the experts
| think.
| Alifatisk wrote:
| Isn't ADT abbreviation for Abstract Data Type? Or does it
| depend in context nowadays?
| rowanG077 wrote:
| Context. It means algebraic data type here.
| Jaxan wrote:
| You answered your own question: it depends and the context
| and is confusing imo. Both are very common in compsci
| Tainnor wrote:
| > except maybe Rust
|
| Swift, Kotlin and Scala all have had ADTs for a while, even
| Java has it now.
| thesz wrote:
| "Haskell is the best imperative language," (C) various software
| engineers.
|
| Also, algebraic data types can be seen as hierarchy consisting
| of abstract base class and several final children classes. So
| it is an inheritance model, just restricted one.
| epolanski wrote:
| May not be built in but many mainstream languages such as
| typescript have libraries or the tools to easily implement
| them.
| linkdd wrote:
| This is the work of a wizard.
|
| I've known C for almost 20 years, and never would I have thought
| the macro system was powerful enough to allow such black magic.
|
| This is awesome!
| lupire wrote:
| ADTs are mostly string replacement on generic structs and
| unions, plus tagging on the union. It's not a complicated use
| of macros.
| clnhlzmn wrote:
| You might also be interested in metalang99 by the same author.
| jacoblambda wrote:
| Yeah xmacros (the style of macro use) are pretty fancy.
| "Classically" they are used for creating and accessing type
| safe generics or for reducing boilerplate for hardware register
| and interrupt definitions.
|
| They are kind of cursed but at their core they are actually
| incredibly simple and a reliable tool for reducing cognitive
| complexity and boilerplate in C based projects.
| cl91 wrote:
| > I've known C for almost 20 years
|
| The author is only 19 years old. I feel really dumb now.
| tombert wrote:
| Interesting.
|
| Algebraic Data Types are almost always one of the things I miss
| when I use imperative languages. I have to do Java at work, and
| while I've kind of come around on Java and I don't think it's
| quite as bad as I have accused it of being, there's been several
| dozen instances of "man I wish Java had F#'s discriminated
| unions".
|
| Obviously I'm aware that you can spoof it with a variety of
| techniques, and often enums are enough for what you need, but
| most of those techniques lack the flexibility and terseness of
| proper ADTs; if nothing else those techniques don't have the sexy
| pattern matching that you get with a functional language.
|
| This C extension looks pretty sweet since it appears to have the
| pattern matching I want; I'll see if I can use it for my Arduino
| projects.
| AlecBG wrote:
| Sealed interfaces in java 21 allow pattern matching
| tombert wrote:
| Yeah I know, we just don't use Java 21 at work yet. I'm super
| excited for that update, and it actually looks like we will
| be transitioning to that by the end of the year, but I
| haven't had a chance to play with it just yet.
|
| I do find it a little annoying that it's taken so long for
| Java to get a feature that, in my opinion, was so clearly
| useful; it feels like they were about a decade later on this
| than they should have been, but I'll take whatever victories
| I can get.
| brabel wrote:
| If you can enable preview features, you can use pattern
| matching since Java 17 (though the final syntax in Java 21
| was slightly changed - still you may want to use preview
| features, it's mostly fine in Java as they tend to change
| very little, and when you do upgrade, the compiler will
| tell you where you need to update your code).
| lupire wrote:
| Kotlin is JVM compatible and has ADTs.
|
| Java has https://github.com/functionaljava/functionaljava
|
| which is unsupported but stable.
| tombert wrote:
| Sure, and Scala has had ADTs since its inception as well I
| think, and that's also JVM. It's not ADTs, but Clojure does
| have some level of pattern matching/destructuring as well.
|
| It wasn't that I though that the JVM was incapable of doing
| something like an ADT, just that vanilla Java didn't support
| it. While it's easy to say that "companies should just use
| Kotlin", that's a bit of a big ordeal if you already have a
| 15 year old codebase that's written in Java.
|
| I've heard of but never used the Functional Java library,
| though it'd be a tough sell to get my work to let me import a
| library that hasn't been updated in two years.
| Tainnor wrote:
| > that's a bit of a big ordeal if you already have a 15
| year old codebase that's written in Java.
|
| JetBrains has prioritised compatibility with Java and it
| shows. Of course, there are some gotchas (such as
| nullability or checked exceptions which don't exist in
| Kotlin), but you can really mix Kotlin and Java code
| relatively freely.
| brabel wrote:
| Java 21's pattern matching (you don't need functionaljava,
| and shouldn't really use that unless you're really into FP)
| is kind of nicer than Kotlin's, because you can automatically
| "destruct" records in your matches.
|
| For Java, see https://www.baeldung.com/java-lts-21-new-
| features
|
| Kotlin's: https://www.baeldung.com/kotlin/when
|
| Make up your own mind.
| estebank wrote:
| Everyone who _hasn 't_ used ADTs and pattern matching doesn't
| get what the big deal is all about. Everyone who _is_ used to
| ADTs and pattern matching doesn 't get what the big deal is all
| about, until they have to work in a language that doesn't have
| them. And everyone who _just_ found out about them can 't shut
| up about them being the best thing since sliced bread.
|
| :)
| im3w1l wrote:
| I have mainly used them in Rust. They are nice I suppose, but
| nothing mindblowing.
|
| To me it feels very similar to an interface (trait)
| implemented by a bunch of classes (structs). I have multiple
| times wondered which of those two approaches would be better
| in a given situation, often wanting some aspects of both.
|
| Being able to exhaustively pattern match is nice. But being
| able to define my classes in different places is also nice.
| And being able to define methods on the classes is nice. And
| defining a function that will only accept particular variant
| is nice.
|
| From my perspective a discriminant vs a vtable pointer is a
| boring implementation detail the compiler should just figure
| out for me based on what would be more optimal in a given
| situation.
| estebank wrote:
| Enums are closed sets and trait objects are open sets. They
| _are_ conceptually related concepts, but the language puts
| syntactic distance between the two, and I don 't think it
| should.
|
| There are lots of open design questions for every feature
| you propose, but all of them have been discussed and have
| higher or lower chance of making it into the language.
| im3w1l wrote:
| That's kind of greek to me, but shouldn't promising the
| compiler that my set is closed unlock more features
| instead of taking features away?
| estebank wrote:
| I'm not sure I understand your point, but I'll elaborate
| on ways that we could "homogenize" the two features:
|
| ---
|
| We could add implicit enums to impl Trait, so that you
| could return different types from a function:
| fn foo() -> enum impl Display { if rand() >
| 0.5 { "str" } else {
| 42 } }
|
| which would let you get around the problem of returning a
| type erased object for a Trait that isn't object safe:
| trait Trait { const C: i32 = 0; }
| impl Trait for i32 {} impl Trait for &'static str
| {} fn foo() -> Box<dyn Trait> { if
| true { Box::new("") } else {
| Box::new(42) } }
| error[E0038]: the trait `Trait` cannot be made into an
| object --> f500.rs:6:17 | 6 |
| fn foo() -> Box<dyn Trait> { |
| ^^^^^^^^^ `Trait` cannot be made into an object
| | note: for a trait to be "object safe" it needs
| to allow building a vtable to allow the call to be
| resolvable dynamically; for more information visit
| <https://doc.rust-
| lang.org/reference/items/traits.html#object-safety>
| --> f500.rs:2:11 | 1 | trait Trait {
| | ----- this trait cannot be made into an object...
| 2 | const C: i32 = 0; | ^
| ...because it contains this associated `const`
| = help: consider moving `C` to another trait =
| help: the following types implement the trait, consider
| defining an enum where each variant holds one of these
| types, implementing `Trait` for this new enum and using
| it instead: &'static str
| i32
|
| ---
|
| Relax object safety rules, like making all assoc consts
| implicitly `where Self: Sized`.
|
| ---
|
| We could make enum variants types on their own right,
| allowing you to write fn foo() ->
| Result<i32, i32>::Ok { Ok(42) } let Ok(val)
| = foo();
|
| There's some work on this, under the umbrella of
| "patterns in types". For now the only supported part of
| it is specifying a value range for integers, but will
| likely grow to support arbitrary patterns.
|
| ---
|
| Having a way to express `impl Trait for Enum {}` when
| every `Enum` variant already implement `Trait` without
| having to write the whole `impl`.
|
| ---
|
| Anonymous enums: fn foo() -> Foo | Bar
| | Baz
|
| ---
|
| Being able to match on Box<dyn Any> or anonymous enums
| match foo() { x: Foo => ..., x:
| Bar => ..., _ => ..., }
|
| ---
|
| Stop needing to create a new struct type in order to box
| a single variant enum Foo {
| Bar(Box<struct { a: i32, b: i32 }>), }
|
| ---
|
| These are of the top of my head, there are many things
| that you can do to make trait objects and enums feel
| closer than they do today, to make changing the way your
| code works a "gradient" instead of a "jump". My go-to
| example for this is: if you have a type where every field
| is Debug, you can derive it. As soon as you add one field
| that isn't Debug, you have to implement the whole impl
| for your type. That's a "jump". If we had default values
| for structs you could still use the derive by specifying
| a default value in the definition. That makes the
| syntactic change "distance" be as far as the conceptual
| change "distance".
| im3w1l wrote:
| A trait is a collection of variants that may or may not
| have unknown members. An enum is a collection of variants
| that may not have unknown implementations. So enums are
| in some sense a subset of traits. Hence every property of
| traits is also a property of enums. Does that make sense?
|
| Those suggestion of your look interesting, but I haven't
| thought them through enough to have an opinion.
| bmoxb wrote:
| You might be interested in taking a look at OCaml's
| extensible sum types which may straddle the line in the way
| you're describing.
| naasking wrote:
| > I have multiple times wondered which of those two
| approaches would be better in a given situation, often
| wanting some aspects of both.
|
| ADTs are closed to extension with new cases but open to
| extension with new functions, eg. anytime you want to add
| new cases, you have to update all functions that depend on
| the ADT, but you can add as many functions for that ADT as
| you like with no issues.
|
| Traits are open to extension with new cases but closed to
| extension with new functions, eg. you can add as many impl
| as you like with no issues (new cases), but if you want to
| add a new function to the trait you have to update all impl
| to support it.
|
| They are logical duals, and the problem of designing
| systems that are open to extension in both cases and
| functions is known as the expression problem:
|
| https://en.wikipedia.org/wiki/Expression_problem
| im3w1l wrote:
| I want more syntax sugar for my ADTs that mirror what
| traits have. I don't need that kind of double
| extensibility.
| amluto wrote:
| I suppose this is a genuine dichotomy, but I feel like
| it's missing a more critical difference: ADTs cleanly
| represent _data_ , even when nothing can be, or needs to
| be, extended from outside.
|
| For example, a result is a success value or an error. A
| stock order is a market order or a limit order, and
| _nothing else_ , at least until someone updates the spec
| and recompiles the code. Situations like this happen _all
| the time_. I don't want to extend a result to include
| gizmos in addition to success value or errors, nor do I
| generally want to extend the set of functions that
| operate on a certain sort of result. But I very, very
| frequently want to represent values with a specific,
| simple schema, and ADTs fit the bill. A bunch of structs
| /classes, interfaces/traits and getters/setters _can_ do
| this, but the result would look like the worst
| stereotypes of enterprise Java code to accomplish what a
| language with nice ADTs can do with basically no
| boilerplate.
| beltsazar wrote:
| > To me it feels very similar to an interface (trait)
| implemented by a bunch of classes (structs)
|
| Then you might not fully grok sum types yet.
|
| > From my perspective a discriminant vs a vtable pointer is
| a boring implementation detail the compiler should just
| figure out for me based on what would be more optimal in a
| given situation.
|
| Disagree. It's a design choice that should be decided by
| the programmers. There's a tradeoff--choosing which should
| be easier: adding a new variant or adding a new
| function/method. It's called the Expression Problem:
| https://wiki.c2.com/?ExpressionProblem
| acchow wrote:
| I'm in the latter camp (from Ocaml) and now using Go. Go
| feels clunky and awkward.
| jackling wrote:
| Could you not get most of the benefits of ADTs using structs +
| unions + enums? I've used the pattern where I had a union of
| several types and an enum to differentiate which one to pick.
| Something like std::variant seems to work a bit like a sum type.
|
| The only issue is you can't do a clean switch statement that
| matches on the specific value of a field, but nested switch
| statements aren't that messy.
| acuozzo wrote:
| Yes, and you can also get many of the benefits of OOP with
| convention and discipline, but doing so requires you to
| frequently get down in the weeds since, e.g., vtables must be
| dealt with manually.
|
| The trouble with this approach is that there's a lot of mental
| overhead in dotting all of your i's and crossing all of your
| t's. It's draining, so you start to, e.g., shoehorn additional
| functionality into existing classes instead of making new ones.
|
| You eventually wind up perceiving the abstraction as costly
| which lessons your use of it at the expense of producing a more
| elegant solution to the problem(s) you're solving.
|
| tl,dr? The ability to just state "Darmok and Jalad at Tanagra"
| is transformative when the alternative is telling an entire
| story every time you want to reference a complex idea.
| mattgreenrocks wrote:
| I generally don't mind C++ for most code when it's absolutely
| necessary, but I'm not a huge fan of std::variant. Using
| std::visit to exhaustively match all cases feels hacky. It
| really would benefit from being a first-class language feature.
| It's more impactful to a lot of day-to-day code than other
| things they've worked on, such as coroutines.
| TheBicPen wrote:
| The 4th example at
| https://en.cppreference.com/w/cpp/utility/variant/visit that
| uses a class template makes the feature a bit nicer, but
| still not as ergonomic as something like Rust.
| naasking wrote:
| > Could you not get most of the benefits of ADTs using structs
| + unions + enums?
|
| The modelling aspects can be simulated, yes, but that's barely
| half of the benefits of ADTs. Pattern matching is a big
| ergonomic benefit.
| cryptonector wrote:
| TFA gets pattern matching.
|
| The critical thing is that the compiler (or macro system)
| needs to check that you've checked all the alternatives.
| cryptonector wrote:
| The absolutely critical thing is to have checked every
| alternative when dealing with a sum type value. This is hard to
| do with macros, though not impossible (basically you'd need a
| macro to start a matching context and which introduces a
| variable in which to keep track of all the alternatives
| checked, then you need to arrange for the end of the matching
| context to check that all alternatives were checked).
| samatman wrote:
| Let's say you have a C program to write, and you really want
| exhaustive pattern matching on the tags of unions (which is what
| Datatype99 provides: "Put simply, Datatype99 is just a syntax
| sugar over tagged unions").
|
| Let's say further that you already know Rust exists, and aren't
| going to use it for reasons that anyone writing a C program
| already knows.
|
| At least consider Zig. Here's a little something I wrote in Zig
| two days ago: /// Adjust a label-bearing OpCode
| by `l`. No-op if no label. pub fn adjust(self: *OpCode,
| l: i16) void { switch (self.*) {
| inline else => |*op| { const PayType =
| @TypeOf(op.*); if (PayType != void and
| @hasField(PayType, "l")) { op.*.l += l;
| } }, } }
|
| This uses comptime (inline else) to generate all branches of a
| switch statement over a tagged union, and add an offset to
| members of that union which have an "l" field. You can vary the
| nature of the branches on any comptime-available type info, which
| is a lot, and all the conditions are compile-time, each branch of
| the switch has only the logic needed to handle that variant.
|
| "But my program is already in C, I just need it for one file"
| right. Try Zig. You might like it.
| pajko wrote:
| Seems like Nim can be useful too, plus it compiles to C.
|
| https://gist.github.com/unclechu/eb37cc81e80afbbb5e74990b62e...
| brabel wrote:
| In Nim, ADTs are painful still (as your example clearly
| shows), but they are working on adding proper ADTs to the
| language (I can't find where I read that, but I am sure I
| did!).
| samatman wrote:
| I've been a Nim respecter for many years, it's slept on in
| general as a language.
|
| The difference here is that Nim compiles to C and you can
| turn the garbage collector off: Zig _compiles C_ and there 's
| no garbage collector. That means the entire standard library
| is available when generating object code. It's also trivial
| to opt-in to the C ABI on a fine-grained basis, by defining a
| function or struct with the extern keyword.
|
| I believe this is still fairly current about the difficulties
| of building Nim dylibs for C programs:
| https://peterme.net/dynamic-libraries-in-nim.html
|
| I expect Nim will stabilize about where D has: it will have a
| dialect of the language which, with relatively painless
| accommodations, is able to produce object code which speaks C
| ABI. Zig is different. The language is relentlessly focused
| on providing a better alternative to C while occupying the
| same niche, and a lot of design time has been spent on making
| it practical to take an existing C program and start writing
| the new parts of it in Zig.
|
| It's a good language, Nim, and getting better. I'd recommend
| it for someone who is considering Go, for example.
| otikik wrote:
| What a madlad. Kudos for implementing this.
| KerrAvon wrote:
| Anyone considering using this should be strongly looking at using
| Swift or Rust instead. You can build almost any given language
| idea using the C macro preprocessor, but that doesn't mean it's a
| good idea to ship production code using it.
|
| The worst codebases to inherit as a maintenance programmer are
| the ones where people got clever with the C preprocessor.
| Impossible to debug and impossible to maintain.
| mingodad wrote:
| There is also https://melt.cs.umn.edu/ that has an extension that
| add templates and algebraic data types to C :
| https://github.com/melt-umn/ableC-template-algebraic-data-ty...
| WhereIsTheTruth wrote:
| Tagged Union is a must have in a programming language
| modeless wrote:
| > PLEASE, do not use top-level break/continue inside statements
| provided to of and ifLet; use goto labels instead.
|
| Seems like a pretty big footgun. But otherwise, very cool.
| linkdd wrote:
| goto is a footgun only if you use it to move from function to
| function, which btw was what "goto considered harmful" was
| about. That practice has disappeared, and now goto, within a
| function, is pretty harmless and quite identical to
| break/continue in fact.
| modeless wrote:
| Goto isn't the footgun. The footgun is if you use
| break/continue by accident then some unspecified bad thing
| will happen, silently I'm guessing.
| zzo38computer wrote:
| Using goto instead isn't a problem, but knowing not to use
| break/continue inside of such blocks is something that you will
| have to be aware of.
|
| I had written a immediate mode UI out of macros, and this
| reminded me of that although in my case it is not a problem,
| although some blocks are ones that you can use "break". For
| example, you can use "break" to exit out of a win_form block
| ("goto" also works), while a win_command block does not capture
| "break" so using break (or goto) inside of a win_command block
| will break out of whatever block the win_command is in
| (probably a win_form block; for example, this would commonly be
| used in the case of a "Cancel" button).
___________________________________________________________________
(page generated 2024-05-09 23:00 UTC)