8 ms·
Tar.pl – A tar creator and extractor in ~130 lines of Prolog
- 082349872349872 4y agoDCGs are an awesome way to specify a format but a poor way to implement it?
- mark_l_watson 4y agoI agree and the code itself is awesome also. Around 30 years ago I was really into Prolog but recently I have tried getting back into it and I am having a rough go at it. I still have the old Art of Prolog book, so that might be a good reentry point.
- philjohn 4y agoI still maintain that learning Prolog 25 years ago as part of my degree (AI + Comp Sci) made me a better programmer.
- mncharity 4y ago> recently I have tried getting back into it and I am having a rough go at it Fwiw, doing problem setup and result processing in another language can avoid much pain. So prolog only where it excels, and a mainstream ecosystem for the rest. I've liked batch mode "write a prolog file, run it, read result (eg json, or wrapper-language code to eval)", but was recently thinking of trying PySwip[1]. [1] https://github.com/yuce/pyswip https://github.com/yuce/pyswip
- riesenheim 4y agoI had the same troubles until I encountered Markus Triska's modern perspective on revitalizing Prolog: https://www.metalevel.at/prolog https://www.metalevel.at/prolog. His video 'Preparing Prolog' may be the best place to (re)start: https://youtu.be/kGQNeeRp4sM https://youtu.be/kGQNeeRp4sM
- nmadden 4y agoThat's been my experience, and chimes with what the author writes at the end about performance. I remember trying to stream a few hundred MB of CSV data with Prolog a few years ago and giving up after not being able to either write or find a library that could cope with even that kind of size (which I wouldn't consider particularly big). (In the end, I managed to bulk import the data into SQLite, which took a few seconds, then used SQL instead). I should give Scryer Prolog a go to see if it is any better, and I'm by no means an expert Prolog programmer so YMMV.
- richard_todd 4y agoIt’s all mind-bending fun until the interpreter starts blowing one of its internal stacks. Then it’s hours of tedium tracing through queries looking for ways to contain the computation.
- moss2 4y agoAbsolutely marvelous.
- kartic 4y agoMakes me want to learn Prolog.
- derefr 4y agoSounds 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?
- superdisk 4y agoThe 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.
- derefr 4y agoAn 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/ 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...)
- aeneasmackenzie 4y agoI like these data description languages but most of them just have support for sequential structures and don't support offsets within the file. These are very common in file formats created for use with C or a similar language, which is most of them. It's not hard to add but it destroys the elegance of the formalism.
- TheRealPomax 4y agoWhat's the point of a comment like this when Prolog supports file seeking just fine? That's like complaining about the lack of structs in procedural languages when the post you're commenting on is a C++ post...
- aeneasmackenzie 4y agoYou can file seek in any language, but not in most file format DSLs (or this one, because it's local). The author mentions QuickBMS and thus is aware of this, but most academic format languages don't support it.
- TheRealPomax 4y agoExcept we're talking about Prolog, so we're talking about SWI-Prolog, the insanely academic flavour of this programming language. It's basically the flavour of Prolog that won the popularity contest exactly because of its academic sponsorship (by the University of Amsterdam).
- kragen 4y agoyou'll probably be interested in daedalus from galois
- rhelz 4y agoNicely done. Prolog is killer for database programming/querying and parsing/formatting. Since these are not exactly "niche" tasks, its kinda sad that prolog isn't more popular.
- optimalsolver 4y agoWouldn’t Datalog be a better alternative?
- rhelz 4y agoDatalog is great for database programming, and since it is a restricted subset of prolog, a datalog comes in every box of prolog :-)
- cmrdporcupine 4y agoAren't there significant differences in implementation between a Datalog system and Prolog running similar rules, though? Bottom-up vs top-down eval, is what I read...
- rhelz 4y agoClassically, yes, but most prolog implementations these days support a tabled search strategy as Datalog typically does.
- Avshalom 4y agoSort of. Because of it's restrictions it traditionally uses different search/resolution strategies than Prolog. And in the other direction the SLD resolution strategy Prolog traditionally uses can fail on syntactically valid Datalog (clause ordering issues). That said, the big Prolog implementations all support multiple resolution strategies although I suspect there are a lot of various optimizations Datalog squeezes out of it's restrictions that let it handle things that might not be reasonable in a given Prolog.
- 4y ago
- d33 4y agoJust curious, is .pl the standard extension for Prolog programs? Why would Perl and Prolog choose the same one, instead of one using e.g. .pg?
- davelee 4y agoA less common extension is .pro.
- Tomte 4y agoProbably because few people used both. .pro is also common for Prolog code, if you care about the extension clash.
- DonHopkins 4y agoBecause .log was taken.
- tmtvl 4y ago.pro is also used by IDL and Qt. I imagine there are few two or three letter extensions that aren't overloaded.
- civopsec 4y ago> instead of one using e.g. .pg? Why not just `.prolog`? In this day and age. (Maybe there’s some reason like “then I can’t put these source files on FAT filesystems”, I don’t know.) Java seems to do fine with it’s longer-than-three-letters `.java`.
- Avshalom 4y agoMost editors will understand .prolog, but on the other hand it's 15 years older than perl and it's not hard to teach editors to treat .pl as prolog.
- anon291 4y ago.pl is used because prolog is really old and FAT used to enforce extension limits. Not relevant nowadays, but it's stuck around.
- marbu 4y agoFrom the README: <quote>We're going to declaratively define a parser for the tar format, and once we're done, our code will not only extract .tar files, but create them as well.</quote> I recall reading about this somewhere, but haven't seen such nice real world example before. Well done.
- Avshalom 4y agoThere's a cool little bencode library that also works like that, all of 30 short lines too. https://github.com/mndrix/bencode/blob/master/prolog/bencode.pl https://github.com/mndrix/bencode/blob/master/prolog/bencode... https://en.wikipedia.org/wiki/Bencode https://en.wikipedia.org/wiki/Bencode
- zelphirkalt 4y agoI think if done right, this falls out of Prolog automatically, as you program in relations, rather than functions. Depending on which places you leave empty in a query, Prolog will work to fill in the empty places. One is probably the tar file and one is the folder being added to a tar archive, but none of the 2 is any more important than the other.
- samuell 4y agoCheck out "Production Prolog" by Michael Hendricks on YouTube, which demonstrates the same thing, at a talk at StrangeLoop: https://youtu.be/G_eYTctGZw8 https://youtu.be/G_eYTctGZw8
- dmd 4y agoThis makes me miss using Ab Initio, which in its language "DML" lets you describe (even extremely complex) record formats declaratively.
- pmarreck 4y agoNow do it in Bash. ;)
- olddustytrail 4y agoSure #!/bin/bash tar "$@" Takes the same arguments as the original!
- pmarreck 4y agowithout using `tar`
- jll29 4y agoWriting tar in PROLOG sounds "cool", a neat hack, but it is as practical as writing the Linux kernel in COBOL. Possible, perhaps, but not the best idea. It's hard enough to write things in PROLOG that _are_ ideally suited for the language - like natural language parsers (they used to be LISP or PROLOG, but these days they are all in C++ or FORTRAN wrapped in Python so no-one gets hurt; why? Because of efficiency and numeric libraries required - modern parsers for human languages implement probabilistic or neural models, no longer symbol manipulation and pattern matching). EDIT: I'm not a PROLOG hater - in fact, enjoyed reading the article (and I will read sequels on implementing "mount" in RPG3, "htop" in COMAL etc.) and my friends include some PROLOG lovers. I also find it important and stimulating to learn about another paradigm, and logical programming is an important one for many reasons. This rant is more about using it on the specific task of implementing "tar", for which it is a poor fit, as the article's PS shows.
- anon291 4y agoBinary file formats, like text formats, are simply languages, and declarative logic languages like Prolog, are excellent for parsing, as you said. Thus, it stands to reason that Prolog would be a very good fit for parsing data. That doesn't change just because the data is not ASCII-encoded.
- phyzome 4y agoThis version is also insecure, as it does not prevent file path traversal attacks.
- graymatters 4y agoRubbish. It’s attitude like that which keeps less common languages from taking off. Hidden mindset-language bias stemming from using the hammer you’re familiar with for every nail. Moreover, Prolog in particular requires a complete mindset change in order to naturally write in it. Once you reach that level - anything is possible and even not that hard to write in Prolog.
- umvi 4y ago> It's unfortunately absolutely dog slow Seems like a common chicken-egg problem of niche languages. Performance doesn't improve until lots of people are using it, but lots of people won't use it until performance improves.
- tmtvl 4y agoEh, people will happily use slow languages if they are marketed the right way. Look at Python, it has a very large following, yet it's so slow that the dog's descendants will have evolved to adapt to a marine environment by the time Python finishes running Hello World.
- jonas21 4y agoI don't get it. tar is such a simple format you could do this in like 50 lines of C. Most of that would be declaring a struct. And unlike this implementation, it would be performant.
- dagss 4y agoFirst time I see Prolog...I thougt that seeing the compiler invert a function automatically is quite impressing. I mean just being able to take only the forwards declaration and figure out the inverse is interesting in itself.
- mattkrause 4y agoThe cool thing is that it uses the same code as the reader and writer.In essence, you write one function, taking two arguments: tar(dstTarFile, srcFiles) Next you provide one of the two arguments and query Prolog to find the other: you pass in a tar file as the first argument, and it tells you what `srcFiles` would need to be to create that archive, effectively extracting it. Alternately, you pass in `srcFiles` and it tells you what the corresponding dstTarFile should be, creating an archive. Another way to think about it is that the Prolog code is not directly telling you how to read/write tar files. Instead, imagine it as a cost function that tells you how well this tar file corresponds to the uncompressed representation of those files, which you're minimizing. If you were to write it in C, the code would imperative: do this, then that, then this other thing. Consequently, the reader and writer code are totally different. For example, to process the file size, you would write functions two functions: char* uIntToOctalASCII(unsigned int sz)` and octalASCIIToUInt(char* szstr). Semantically, these are inverses[0]: octalASCIIToUInt(uIntToOctalASCII(x)) == x but the implementations have very little in common. At best, you can use one to test the other. [0] And leaks memory, but whatever....
- xdfgh1112 4y agoSimilarly if you write a sudoku solver in prolog, you automatically get a solver AND a problem generator, both for unfilled and partially filled grids.
- 4y ago
- lliamander 4y agoThe bidirectional nature of predicates is one of the cool aspects of logic programming. It is also cool that is completely transparent whether a predicate returns a single value or multiple values. It's sort of like if every function were implicitly a generator.
- luuuzeta 4y agoI took a course in college with the first half in Haskell and the second half in Prolog. Programming in Prolog felt like learning to program all over again.
- jen729w 4y agoProlog was responsible for me getting kicked out of uni! I just couldn't wrap my head round it, and I failed the exam resit. In fairness I was a shocking student and deserved it.
- ddejohn 4y agoI took a course called Principles of Programming Languages. Covered grammars, regular languages, state machines, and then had practical assignments in Haskell and Prolog. I had the exact same experience with Prolog. I loved it, but I haven't looked at it since college.
- lynx23 4y agoThanks for this link. Prolog is sort of the last language on my list of things to look at. However, I never really made it past the classic towers of hanoi example, always longing for a small self-contained example that achieves a real world goal. And here it is! Very neat showcase.
- anticensor 4y agoInitially misread it as tax.pl.