Hacker News Reader

Comment by derefr | Hacker News Reader

Sounds exotic at first glance, but how different is this from the Erlang implementation of tar parsing? I.e. how much of this is relying on Prolog-specific features, vs. how much is just succinct head-clause pattern matching?

View on HN

The unique part is that you get encoding and decoding for free when just describing the spec. It is essentially just succinct head-clause matching though.

An idiomatic Erlang/Elixir implementation of validation for a binary format would also give you decoding for free — see e.g. https://zohaib.me/binary-pattern-matching-in-elixir/. So I guess it's the encoding part that's unique to how Prolog works.

Which makes sense; my understanding is that in Prolog, insofar as a function encodingOf(A, B) is defined by using A and B on either side of a bind expression to equate B as the encoding of A, if encodingOf(A, knownEnc) would act as a parser for knownEnc, then encodingOf(knownDec, B) would act as an encoder for knownDec — essentially swapping the question "what would this parse to" given an encoded binary, for "what would parse to this" given a decoded term.

Erlang can't do exactly that — a given variable's "bound-ness" is determined during compilation, and head-clause variables can't be indeterminately bound — but if it could, then you would indeed get an encoder for the same format "for free", since binary-pattern matching in Erlang becomes a binary-building expression depending on whether the variables in the expression are bound or unbound.

(Now I'm curious how hard it would be to add indeterminately-bound compile-time function polymorphism to Erlang — i.e. generating bytecode for the powerset of bound-ness-es of the variables in the head clause, only where at least one generates valid bytecode, probably name-mangled with a bitfield suffix of said bound-ness-es; and then being able to bind function parameters from such functions as new output variables in expressions, where the call sites also generate a call to the equivalent mangled name. The usefulness of this would probably be pretty small, without the other aspects of Prolog, but you never know...)

GP talks about getting encoding and decoding together by implementing the spec once. In Erlang/Elixir you can only get one at a time because you can't do the equivalent of this:

  some_predicate(<concrete values>, Decoded). % decoder
  some_predicate(Encoded, <concrete values>). % encoder
  some_predicate(<concrete values>, <concrete values>). % validator

But in Prolog, that's what many predicates permit as a baseline. In Erlang, yes, a validator is, or can be, a parser/decoder. But it's not an encoder which still needs to be a separate function (or set of functions) to describe movement in the other direction.

This is fantastic bite-sized example of exactly what makes Prolog and other logic languages so different to program in and will probably become my go-to example for introducing what's so special about Prolog to programmers with backgrounds in other programming languages who are looking for examples that involve "real-world" programming tasks.

To go even further, how much is it different from C# or C++? There you'd just declare the appropriate structs and bitcast.

That works okay only for fixed-sized structs that don't require any transformation of their members-- otherwise you'll need to write a traditional parser.

It is there in Prolog version too. Search for "FileSize" on the page.

What I mean is that if you need to parse a format that has variable-sized structures, you can't just memcpy them into a struct because structs have a fixed size. Additionally sometimes you need to parse a value into a more tractable representation, for example those octal ASCII strings in the tar format, which requires some additional processing that isn't possible with loading/serializing a struct.

Which is also there in the Prolog code.

Sorry, isn't that undefined behaviour?

Not in C# for sure. Not a C++ expert, but I believe reinterpret_cast behavior is defined too.

You can have it as part of unsafe code, hence why the bytecode verifier won't validate Assemblies with unsafe code.

https://learn.microsoft.com/en-us/dotnet/csharp/language-ref...

I believe verifier is fine with unsafe code.

Also not sure what does it have to do with defined/undefined behavior. Even if it is not verifiable, the behavior is still defined.

Reply on news.ycombinator.com