HNHacker News
TopNewBestAskShowJobs

k_g_b_

66 karma · joined June 29, 2022

submissionscomments
k_g_b_··on Ten Years of JMAP
IMAP has a concept of flags/keywords (https://datatracker.ietf.org/doc/html/rfc9051 2.3.2) and there's a whole bunch of servers and clients that support using it in a similar way as labels - Thunderbird, Zimbra, dovecot, etc.

It's not a feature originally built for labelling like Gmail, so it has a few complexities ("Servers MAY permit the client to define new keywords") and enough clients (especially mobile) that don't support it - but they could just like Thunderbird or some webmail clients.

I've used it basically exactly like Gmail labels for years on TB on desktop.

k_g_b_··on Nominal for Storing, Structural for Manipulating
I think you're confusing nominal with static and structural with dynamic. This might be because there's few instances of more powerful static structural types implemented in common programming languages - OCaml's polymorphic variants, Typescript (partially dynamic). Very common structural types available in many statically typed programming languages are tuples.

The compiler can still know and optimize the data layout of any static structural type and tuples certainly are optimized in e.g. Rust. However, the flexibility of other structural types like polymorphic variants or set-theoretic types like unions mean that the data layout also needs to be more flexible and that comes with some overhead e.g. vs a nominal sum type (like in ML, Rust enums, etc) or struct/record.

Missing data layout optimizations comes mostly due to necessary uniform representation of dynamic types - the same as for nominal types - e.g. through runtime polymorphism language features as OCaml has by default, virtual methods or Rust's trait objects. Whether a structural type system allows such dynamic features (e.g. OCaml's row polymorphism) or not is a design question - I think there's still plenty of use for structural types in a language with only compile time polymorphism (monomorphization).

See also deredede's comment https://news.ycombinator.com/item?id=42191956

k_g_b_··on Jank development update – Moving to LLVM IR
Guile seems to prepare to switch to https://github.com/wingo/whippet - a GC C library that can wrap Boehm/BDW but also provides more (and less) advanced GC options. Should be a good option for Jank and similar projects as well - especially if they already use BDW.
k_g_b_··on Restic: Backups done right
Agreed on no crashing/issues. I always use the provided Borg "single binary" https://borgbackup.readthedocs.io/en/latest/installation.htm... that unpacks everything into /tmp and naturally is larger than the restic binary. That isn't an issue on my systems.

Restic has no unencrypted mode for reasons - you must use an empty password and additional flag instead. If your backups will already be encrypted in other ways you'll still pay encryption overhead.

k_g_b_··on The Essence of Compiling with Continuations (1993) [pdf]
The problem with typing continuations -in my opinion - stems from the fact that nearly all discussion of continuation starts from a functional context/view/programming language and often also in an untyped language/formalism.

Additionally, CPS ends with "style" suggesting that it's fully expressible in the original programming language. But if we truly type it after a style transformation we need to introduce polymorphism everywhere, see e.g. the first example for Haskell on https://en.m.wikipedia.org/wiki/Continuation-passing_style

If we use CPS as an IR, typing the continuations as functions is wrong and unnecessary - a continuation does not return anything and more precise: it does not return. This means it's type is constructed just from it's argument type(s). In an IR we can simply add constructs for continuations and their types.

A lambda \x:Nat.5 has type Nat -> Nat, or in one non-infix syntax: ΠNat.Nat (https://en.m.wikipedia.org/wiki/Lambda_cube). A continuation c with argument Nat simply has type `Cont Nat` a type constructor taking the argument type.

A `Cont Nat` isn't something you would see in a CPS IR, because it's mostly useless: it's type describes a computation that takes an argument and then diverges. The only place such a continuation has, would be as the single `exit` continuation of the program provided to the main entry point of the program. More useful is e.g. a `Cont (Nat, Cont Bool)` and this brings us the "passing" part of CPS.

Some like to use the syntax `Nat -> !` and that highlights the non-returning nature, but I think this is again too confusing in the context of functional programming - just leave out the `->`.

See also https://okmij.org/ftp/continuations/undelimited.html and note that it argues that the untyped call/cc operator might be the origin of the confusion: it represents the captured continuation as a function and a continuation also has an application operation like a function, but it's semantics are different.

As far as I can tell, there's very few formal treatments of continuations that don't start from the lambda calculus. The only two papers I've found are on the Continuation Calculus (https://arxiv.org/abs/1309.1257, https://arxiv.org/abs/1409.3313) with no other follow up.

k_g_b_··on Show HN: Flyde – an open-source visual programming language
What is code in a text editor if not a legible 2D planar representation of the "real code"? The real difference between text and a graph of definition-use edges and nodes is that the text representation does not have any intrinsic information on the real code's structure and does not display definition-use edges - at least by default. Most code editors provide some way (via LSP/etc) to display the edges however - usually as a list of the other end of the edge in a dialog/window/similar separate from the code. Given that some textual representation (e.g. variable names) of source and target is possible, a graph-displaying editor can just "abbreviate" an edge (or: make it implicit) by using the other end of the edge. If a graph editor makes all edges implicit by a certain strategy of using names/whitespace/parentheses/etc, the result would be a text representation a text editor displays. The main issue is not in difference of display, but in the mode of editing: a text editor allows much more partial input that violates the structure a graph is expected to have: malformed definitions of programming constructs that are neither a node nor an edge in the graph. A graph editor must either allow such partial input in some way (e.g. enter temporary textual representation, transform into group) or use a different input model that doesn't allow such unrepresentable input, e.g. using mostly mouse, or an editing keyboard language like Vim's objects & verbs. On the other hand a text editor requires you to agree on a formatting style with your colleagues and running autoformatters, looking past useless formatty diffs in code review, fixing syntax errors, dangling else,...
k_g_b_··on Using enums to represent state in Rust
Well, you might use a different custom named type than Either, but sum types only give you basically that meaning - you can't enforce the invariants we want. You could use other type mechanisms of your language (e.g. type classes or dependent types) to embed some form of set theoretic types and hopefully leak less of your abstraction (needing "bookkeeping" to keep the invariants) or deal with restricted forms (the type violating some of the invariants we want in some situations).

The examples above or Either<A,A> could result from polymorpic functions that would return a set of types that the function is abstracting about, something like: pickRandom<S,T> : S, T -> S|T. With Either<S,T> you would get pickRandom<A,A> a1 a2 : Either<A,A> (requiring cleanup if you want the invariants I wrote about), with set theoretic types you'd get A. If you have pickRandom<A|B, B|C> x y you would get nested Either's or just A|B|C respectively.

Either is a Monad and so Haskell and others allow us to hide a bunch of complexity of reducing nestings by using abstractions and custom magic syntax (do notation) built for them - but the underlying complexity of the type and necessary mental model remains. Monad transformers become a necessity because you already needed the Monad magic for the cleanup, but you also have another Monad you care much more about then Either (like IO), see e.g the answer here https://stackoverflow.com/questions/67617871/reduce-nestedne... Note that this isn't talking about nested Either's, just the nested syntax for handling them without using it as a Monad and do notation, with actual nested Either's you'd need to do more cleanup.

k_g_b_··on Using enums to represent state in Rust
> Position problem can be handled beautifully by variants based on row polymorphism, such as in OCaml or PureScript. There you can access the fields not by their position but by a key, like keys in objects in JS, meaning that they don't have to be ordered at all. It's like an inverse of a struct: in a struct all fields/keys are guaranteed to exist, but in a variant only one of them exists. Due to row polymorphism they can also be extensible. You can even "handle" a particular field/key and remove it from the type but keep all the other ones and delay handling them.

Exactly. OCaml's polymorpic variants implement a subset of set theoretic types for specifically defined types - see also this ICFP'16 paper https://dl.acm.org/doi/abs/10.1145/2951913.2951928

For languages with more first-class/principles set-theoretic types see the Ceylon type system (sadly dead and archived at Eclipse ceylon-lang.org) or TypeScript (though they obviously also have to deal with JS which makes everything more messy than necessary).

With "Flattening" I mean applying the usual laws of set theory for simplified types: Either<Either<A,B>,A>> is doesn't express our intent for a function return or parameter type if we don't care about the position of A, just whether it is an A, the same with Either<A, Either<A,B>>>/etc, so we'd want all nested variations normalized to Either<A,B>. But we also don't care about the difference between Either<A,B> and Either<B,A> - normalizing this is already not easy without metaprogramming/type reflection. At this point it ceases to have any significant relationship to the original Either type. If we'd use it still to signify A|B and would actively need to call normalizing functions to keep our types clean and simple in this way, that adds non-semantic (regarding the intent of our code) noise to our code or we need to hide the complexity by using more abstract tools like e.g. monad transformers. If instead the language already provided these types, this complexity caused by embedding set theory inside the language doesn't leak into our code and our intent can be expressed more clearly in types without "bookkeeping" artifacts. This is only exacerbated when going to higher arities of sets/Either.

k_g_b_··on Using enums to represent state in Rust
Because your code might not need to care about the position you insert your A or B (left/right for Either), you also might not care whether it's an (encoding as) Either<A,B> or SomeoneElsesEither<A,B> and you also don't want to have to deal with flattening nested Either's as in the example.

These types are also called "set-theoretic" types as A|B means exactly the set of all values that can be typed as A or typed as B - note that this also induces a whole subtyping rule by set inclusion and this is in contrast to sum types where a value typed Either<A,B> can never be typed A or B - to move between them you need to apply extractors/match/constructors/(not sure of standard type theory nomenclature).

Implementation of these union types might still need additional tags and construction/matching/extraction underneath, but from a programming perspective there's less complexity as compared to involving an additional named type Either (or EitherOf3 and EitherOf4 and ...) and manually implementing set-theoretic laws.

k_g_b_··on Using enums to represent state in Rust
Ceylon had a really neat type system - sadly it didn't take off. However before that these types in particular were a feature of OCaml: https://v2.ocaml.org/manual/polyvariant.html There they're called Polymorphic Variants. Note also the implementation efficiency concerns on that page - given that Rust is a systems language, defaulting to the current sum types instead of set-theoretic unions was a reasonable choice. Having the option to use them natively and without macros (there's some crates) would be nice still when aware of the additional performance overhead.
k_g_b_··on Tell HN: The dragon compiler book (2nd edition) is a great book
I've worked on a research project using LLVM as a backend but with it's own SSA implementation at the chair of Sebastian Hack. One of his well known scientific contributions was on optimal register allocation with SSA. The chair also published http://dx.doi.org/10.1007/978-3-642-37051-9_6 a very good and easy way to do SSA construction directly from the AST without computing dominance frontiers.

You should probably start on the Wikipedia page for SSA, which - since the dragon book doesn't teach what SSA actually is, is a reasonable starting point https://en.m.wikipedia.org/wiki/Static_single-assignment_for... Note that even though it provides many examples and other comparisons it not once mentions 3AC (and vice versa actually). Under Benefits you can find links to various optimizations some of whose pages reference what SSA helps with. None of them have much if anything to do with 3AC.

That the CMU simply copies an example straight from the book and provides no further explanation and maybe even doesn't mention PHIs (?) doesn't speak for that course at all. Especially if you take a look at the list of compilers that do use SSA on Wikipedia and note that pretty much all major programming language implementations use SSA.

Of course you can lower an AST to SSA that looks like the example (except the example is so rudimentary it's still missing the very necessary PHI functions) and you can even make it have 3AC form and still exploit the SSA properties in optimizations. It's just that the properties and the SSA form still have no real relation except that both modify your list of instructions and claiming that there's one that's somehow meaningful or that 3AC gives you anything that SSA does is at best grossly misleading by a textbook.

k_g_b_··on Tell HN: The dragon compiler book (2nd edition) is a great book
That's exactly what I mean with superficially similar. Sure, you can transform a non-3AC SSA IR into three address code or transform a 3AC IR into SSA form - as you have done in your example. However, you will need an SSA transformation/construction algorithm to do the latter, which is not that simple or straightforward, especially if you want to be somewhat optimal with placing the PHIs. You can also try to apply your existing analyses and program optimizations on the 3AC SSA - chances are high though that you'll have to adapt them to correctly handle PHIs however. If you simply treat them as a unanalyzed function calls you will likely suffer from a huge loss in analysis precision and optimization opportunities.

On the other hand, if you write your analyses and transformations with SSA form as a precondition, you can reduce complexity because SSA form is referentially transparent, giving you a lot of things like use-def chains, dead code analysis, etc for more or less free.

This is what people mean when they say that SSA is essential for modern compiler construction. That quote from the book is reductionist to the maximum possible extent and put's it in the direct comparison with 3AC, to which it only has the relation that both are transformations of IR instructions the result of both have nothing in common.

The example is misleading because it displays the SSA IR also in 3AC - which is unnecessary - and it completely omits PHIs without which SSA properties simply do not hold and for which no 3AC correlation exists at all - they are not representable. In fact, control flow can easily be built such that a PHI has any amount of operands - e.g. a switch which might need significant additional code transformation to be representable as 3AC.

k_g_b_··on Tell HN: The dragon compiler book (2nd edition) is a great book
3AC/TAC is something fundamentally different than SSA. Sure, both somehow superficially constrain how you write variable assignment statements - if your intermediate representation contains such things and is a list of instructions. 3AC means that your "instructions" have <=3 operands, SSA means each "syntactic" variable is assigned at most once, that is: they are not a variable anymore. In fact, SSA transformation makes an imperative program referentially transparent (excluding any loads/stores from/to memory) and thus makes it a pure functional program (excluding memory). You can see a program in SSA form simply as a functional program where each basic block is a (nested) function and each PHI is a parameter of the function. SSA as a list of instructions/statements as in 3AC is a red herring and doesn't have any relation to why it's used in compilers/for static analysis. SSA is not a variant of 3AC, also because SSA transformation of 3AC requires the same algorithms as SSA transformation of any other common imperative IR does.

In fact SSA makes no constraints on the number of operands in an instruction/operation what so ever.

k_g_b_··on Forebruary is a wall calendar that you do not need to replace every year (2013)
I'm using a aCalendar+ on Android and the monthly view has continuous scrolling, though given the constraints of a phone screen I only get 6 weeks displayed at once.
← PreviousPage 2 of 2