[HN Gopher] Writing a competitive BZip2 encoder in Ada from scra...
___________________________________________________________________
Writing a competitive BZip2 encoder in Ada from scratch in a few
days (2024)
See also part 2: https://gautiersblog.blogspot.com/2025/07/writing-
bzip2-enco...
Author : etrez
Score : 87 points
Date : 2025-07-14 02:36 UTC (3 days ago)
(HTM) web link (gautiersblog.blogspot.com)
(TXT) w3m dump (gautiersblog.blogspot.com)
| danbruc wrote:
| For those only having a quick look, the charts do not have the y
| axis start at zero, the differences are much smaller than it
| looks.
| Sesse__ wrote:
| Also, they seemingly already had a BWT lying around (which is
| seemingly not counted in "from scratch in a couple of days"),
| and there is no mention of speed.
| vintermann wrote:
| He didn't specify that the demo of BWT was in Ada, or his
| own.
| sltkr wrote:
| It seems like author means his implementation is competitive
| in terms of _compression ratio_ only, and this is achieved in
| the final Huffman encoding step.
|
| From that perspective the BWT implementation isn't very
| interesting because the BWT is deterministic, so the effect
| on compression ratio doesn't depend on which implementation
| was used.
| tombert wrote:
| I know the history of why Ada failed, but it always seemed like
| such a neat language that _shouldn 't_ have failed.
|
| It seemed like it should have been the standard for a lot of
| desktop applications for the 90's and 2000's.
| steveklabnik wrote:
| I am curious, knowing that history, why do you think that it
| shouldn't have?
|
| I have my own thoughts that I'd be happy to share, but I don't
| want to spoil your opinion with them.
|
| (This goes for basically anyone who's interested in talking
| about it, I think it's a fascinating bit of history.)
| tombert wrote:
| I just feel like it emphasized safety in a way that C
| doesn't, while still being fairly high performance. It always
| seemed like a neat language.
| steveklabnik wrote:
| Gotcha, thanks :)
|
| I wouldn't disagree with either of those things at a high
| level, but I think in practice, the details matter, and
| it's more of those details that led to the present state
| than the high level goals, which certainly were laudable.
| fsckboy wrote:
| it's not like we didn't know about safety back then, but
| computers were slow, memory was limited, compilers had to
| be small, optimization was rare, and C was screamingly
| fast.
|
| At the same time, when major compiler vendors couldn't even
| get their Ada compilers out the door in project overruns
| measured in years, Mitch Kapor's 1-2-3 was written and took
| over the spreadsheet market (dethroning the incumbent
| Visicalc) and _it was written in assembler, not even C,_
| and barely had memory to spare on user machines (memory?
| there was barely address space left to spare). The
| tradeoffs were authentic, and there was zero enthusiasm for
| Ada among programmers or entrepreneurs looking to get
| products launched. The mainframe world could have been
| different but the personal computer software market was
| exploding in a way larger systems never did.
|
| (oh and let me add, all the undefined behaviors back then
| were very clearly defined (perhaps over a small field of
| options) and extremely useful, and should have been left
| that way; shoot out a compiler warning or error if they get
| your panties in a bunch)
| MisterTea wrote:
| > I know the history of why Ada failed,
|
| Do you have sources you could point to? I once read that it's a
| great language mired by a designed by committee ecosystem. I
| really liked the language when I tinkered with it a bunch
| around 2010 but moved on after work pushed me to other
| languages like C# for GUI stuff. First language I used with
| simple built in concurrency.
| Jtsummers wrote:
| http://www.adapower.com/index.php?Command=Class&ClassID=Advo.
| ..
|
| Specifically, I think these three paragraphs near the end are
| critical:
|
| > I'm reading a great book now called Why People Believe
| Weird Things, by Micheal Shermer, in which the author
| explains what rational thinking is, and how skepticism is a
| process. Basically, people believe something because that
| want to, not because of any scientific arguments you make.
|
| > There are guys out there who dislike Ada, but they do so
| because they want to, not because of any rational analysis of
| its merits or flaws. Sometimes even their arguments are
| factually incorrect, like saying that "Ada was designed by
| committee," ignoring the fact that Jean vetoed language
| design arguments that were 12-to-1 against him. It's not
| unlike creationists who explain the "fact" that evolution
| violates the 2nd law of thermodynamics. (No, it does not, as
| any book on freshman physics will tell you.)
|
| > I've explained the reasons Ada why I think is not as
| popular as C++, and I'd like to hope that it will convince
| Ada's detractors that Ada isn't so bad after all. But as
| Robert Dewar pointed out, a person who has made an irrational
| decision probably isn't going to be swayed by rational
| arguments!
|
| That is, people aren't really rational. A choice was made to
| dislike it, it entered into the culture and to this day
| people dislike it because they think they _should_ dislike
| it. They don 't even spend 5 minutes studying it to see that
| half of what they've heard (if not more) is flat out wrong.
| In several Ada discussions on HN people claim its syntax is
| like COBOL's, for instance. Not just _similar_ in being
| keyword heavy, but practically the same. Sometimes they even
| provide Ada "examples" that won't even compile. That's the
| kind of nonsense that happens when people turn off their
| brains or refuse to turn on their brains. You see it in many
| Lisp discussions as well.
| MobiusHorizons wrote:
| That was a great read!
| Jtsummers wrote:
| https://news.ycombinator.com/item?id=7824570 - The one
| time it's been submitted that I know of. 112 comments so
| a pretty good discussion.
| ltbarcly3 wrote:
| "Am I out of touch? No it's the children who are wrong."
|
| This argument eats itself. It's just an accusation that
| people who disagree with you are irrational, and their
| arguments are in bad faith. It's not a valid argument
| because it doesn't even depend on any context or facts of
| the actual discussion which he's using it. It's the
| definition of cope.
|
| In the end, even if we can't be sure why Ada failed, it
| failed spectacularly. It had massive institutional backing
| and never made it past obscurity. I don't know exactly why
| people dislike it so much, maybe because everyone already
| knew C, C was well supported, every single OS was written
| in C, etc, so trying to bring some incompatible algol like
| language (always a popular lineage hahaha) with very sparse
| to nonexistent tooling and very theoretical advantages,
| especially considering the huge performance disadvantage at
| the time on highly constrained resources of computers at
| the time was not likely to succeed on its face.
| Jtsummers wrote:
| This claim is false (when considered in context of the
| 1980s when the first Ada spec was released):
|
| > every single OS was written in C.
|
| No, they weren't. In fact, some were written in Algol-
| like languages such as Pascal.
| ltbarcly3 wrote:
| The only exception I can think of is early versions of
| mac os, which was still primarily assembly. Even then i
| recall people went out of their way to use C despite
| needing pascal calling convention for system calls. They
| basically immediately regretted using pascal and started
| a march towards C and basically gave up on pascal before
| the powerpc.
|
| So Pascal had one mainstream OS for about 10 years, most
| of which time it was being phased out.
| Jtsummers wrote:
| > which os was written in Pascal? most were written in
| assembly in that era, you are talking about some obscure
| research or toy.
|
| Your first claim: Every OS was written in C. Your new
| claim: Most were written in assembly.
|
| Pick a position. If most were written in assembly then it
| would not have had any impact on the adoption of Ada so
| why make the original claim?
|
| I would respond to your question but you substantially
| edited your comment and removed the question. I also
| notice you removed the claim in your edit about most OSes
| being written in assembly in the 80s. Obnoxious way to
| communicate with people, altering your comments while
| they're replying so their replies look like random
| comments.
| KerrAvon wrote:
| > They basically immediately regretted using pascal and
| started a march towards C and basically gave up on pascal
| before the powerpc.
|
| Nonsense. MPW Pascal and Think Pascal were well supported
| developer tools, and a lot of third-party developer code
| was written in them during the 80's. Photoshop (1987) was
| originally written in Pascal! Apple's Pascal dialect had
| object extensions that made OOP simpler than with C or
| standard Pascal.
|
| Pascal started to leave the building circa 1991, when C++
| became viable for OOP. Even then, Metrowerks CodeWarrior
| supported native Pascal compilation for PowerPC in
| 1993/4.
| throwaway81523 wrote:
| People who didn't like C's unreliability in the 1990s
| used Java. That relegated Ada to a niche where GC wasn't
| wanted.
| pornel wrote:
| There may be lots of uninformed post-hoc rationalizations
| now, but it couldn't have _started_ with everyone
| collectively deciding to irrationally dislike Ada, and not
| even try it. I suspect it 's not even the ignorant slander
| that is the cause of Ada's unpopularity.
|
| Other languages survive being called designed by committee
| or having ugly syntax. People talk shit about C++ all the
| time. PHP is still alive despite getting so much hate.
| However, there are rational reasons why these languages are
| used, they're just more complicated than beauty of the
| language itself, and are due to complex market forces,
| ecosystems, unique capabilities, etc.
|
| I'm not qualified to answer why Ada isn't more popular, but
| an explanation implying there was nothing wrong with it,
| only everyone out of the blue decided to irrationally
| dislike it, seems shallow to me.
| eggy wrote:
| For my safety-critical automation software for a machine that
| will operate around people and overhead, I'm choosing
| Ada/SPARK2014. Its decades-long track record in high-
| integrity domains like aerospace, defense, and medical
| systems ensures reliability for applications where human
| safety is paramount. SPARK2014's formal verification tools
| mathematically prove the absence of runtime errors, aligning
| with standards like DO-178C and ISO 26262, critical for my Q3
| 2026 market deadline. While Rust is gaining traction for
| memory safety, its formal verification tools, like
| LEAN/Aeneas, are still maturing and lack the production-ready
| ecosystem of Ada/SPARK2014. Ada's clear, structured syntax
| simplifies code reviews, and its tooling generates
| certification reports familiar to regulators, streamlining
| approval processes. For my project's safety and business
| needs, Ada/SPARK2014 is the proven choice - for now. I am not
| a fan of Rust syntax or complexity, but that is somewhat
| subjective. I last dove in about 2 years ago.
| steveklabnik wrote:
| Incidentally, Rust does have an ISO 26262 qualified
| compiler, though DO-178C isn't here just yet.
| MaxBarraclough wrote:
| Doesn't Rust lack a serious language specification? How
| can compilers be certified without a definitive record of
| how the language is meant to behave?
| steveklabnik wrote:
| A language specification is not required to be qualified.
| The behavior of the compiler needs to be described.
|
| https://rust-lang.github.io/fls/
|
| This is effectively a fork of the Rust Reference, made by
| Ferrous, and laid out in a way that allowed the compiler
| to be qualified. It now lives at this URL, because it's
| being adopted by upstream as the spec.
| steveklabnik wrote:
| > Do you have sources you could point to?
|
| This report is of interest to you:
|
| https://nap.nationalacademies.org/read/5463/chapter/1#vii
|
| > It is in this context that Assistant Secretary of Defense
| (Command, Control, Communications, and Intelligence) Emmett
| Paige, Jr., requested that the National Research Council's
| Computer Science and Telecommunications Board (CSTB) review
| DOD's current programming language policy. Convened by CSTB,
| the Committee on the Past and Present Contexts for the Use of
| Ada in the Department of Defense was asked to:
|
| > * Review DOD's original (mid-1970s) goals and strategy for
| the Ada program;
|
| > * Compare and contrast the past and present environments
| for DOD software development; and
|
| > *Consider alternatives and propose a refined set of goals,
| objectives, and approaches better suited to meeting DOD's
| software needs in the face of ongoing technological change.
|
| https://www.militaryaerospace.com/communications/article/167.
| .. is an article from 1997 about this, and here's what it has
| to say:
|
| > Paige says he believes industry engineers will be more
| likely to accept the benefits of using Ada if DOD leaders
| recommend, not require, the language. Software engineers, who
| would rather choose a language based on its merits rather
| than because of a governmental mandate, historically have
| resisted the Ada mandate on principle.
|
| and
|
| > Chief complaints about Ada since it first became a
| military-wide standard in 1983 centered on the perception
| among industry software engineers that DOD officials were
| "shoving Ada down our throats."
|
| This is basically the story: The DoD tried to mandate it,
| people resisted, and made liberal use of the ability to be
| granted an exception, and so they eventually gave up.
|
| The first link contains much more nuance, some excerpts:
|
| > In decisions affecting adoption of programming languages,
| non-technical factors often dominate specific technical
| features. These factors include the broad availability of
| inexpensive compilers and related tools for a wide variety of
| computing environments, as well as the availability of texts
| and related training materials. In addition, grass-roots
| advocacy by an enthusiastic group of early users, especially
| in educational and research institutions, often has broad
| influence on adoption of programming languages. These
| advantages were largely absent when Ada was introduced in
| 1980. In contrast, C++ and Java both have achieved widespread
| acceptance and use. The strong military orientation of the
| publicity generated for Ada also may have served to alienate
| significant portions of the academic and research
| communities.
|
| > Ada has not been widely taught in colleges and
| universities, particularly compared with Pascal, C, and C++;
| until recently, even the military academies taught
| programming in languages other than Ada
|
| > Historically, compilers and other language-specific tools
| for Ada have been significantly more costly and slower in
| coming to market than those for C and C++.
|
| > Software engineers are likely to be interested in enhancing
| skills that they expect to be most valuable in the software
| engineering marketplace, which is now dominated by commercial
| opportunities. Thus, programmers have moved quickly to learn
| Java and Hypertext Markup Language (HTML; used to develop
| pages for the World Wide Web) because they see these as the
| next wave, which can carry them to new career opportunities.
| Similarly, software engineers might avoid using Ada if they
| see it as limiting their careers.
| deaddodo wrote:
| > mired by a designed by committee ecosystem
|
| Can you point to a production language today that doesn't
| have a committee leading it's development?
|
| C, C++, Rust, Javascript, Python, etc. All have committees
| leading their development. The only difference with Ada was
| that, for a long time, that committee was in the DoD (which
| has plenty of fine engineers, given it's practical
| achievements) instead of ISO/ANSI. And instead of being
| focused on general purpose, they had a clear domain they
| prioritized. That's different now, but it's hard to erase a
| few decades of heritage.
| imglorp wrote:
| Failed what? In its domain, it succeeded in its goals: a high
| reliability platform for aerospace, defense, and other mission
| critical domains. It was mandated by the US DoD for all
| software in the nineties and used in Airbus avionics and aboard
| the ISS, etc.
|
| Its syntax and concepts were considered solid and so was
| selected as the basis of the VHDL hardware description
| language, also successful in its domain.
| veqq wrote:
| > was mandated by the US DoD
|
| Vanishingly little was written in Ada as waivers were too
| easy to get.
| deaddodo wrote:
| Every former DoD engineer I've spoken to has worked pretty
| extensively in Ada. From the Phalanx, to the F-15/F-16. C++
| didn't start becoming popular in those domains until the
| mid-00s. The first fighter jet to use it extensively was
| the the F-35[1], which many of the engineers attribute to
| it's early issues[2]; not because C++ was bad, but because
| so much well-tested and hardened code had to be replaced.
|
| So, wherever these waivers were, they certainly weren't in
| those spaces.
|
| 1 - https://www.stroustrup.com/JSF-AV-rules.pdf
|
| 2 - https://www.defenseone.com/technology/2025/02/f-35-prog
| rams-...
| Jtsummers wrote:
| > because so much well-tested and hardened code had to be
| replaced.
|
| Not just software, entire systems. They built their own
| datalinks instead of aiming for compatibility with
| existing datalinks or pushing those existing datalinks to
| a newer version that could meet their needs.
|
| In principle, that should have been their first (flight
| test ready) version. Just get the planes talking to an
| existing datalink network even if they had some next gen
| datalink target. But this is also a classic DOD project
| management problem. They aim for the full system instead
| of staging out a series of iterative versions.
|
| And LM, in their infinite wisdom, hired more developers
| when they were late and ran their development in shifts.
| Because everyone knows the best way to get a late project
| back on track is to hire more people...
| tombert wrote:
| Failed in the sense that it doesn't appear to be used
| anymore.
|
| C and C++ are still used pretty frequently. I wouldn't say
| that they failed, but if someone wrote an application in Ada
| in 2025, I would find that a bit anachronistic.
| jksmith wrote:
| Forgive, but that smells of youth and recency bias. How do
| you judge lisp and k/qdb? Is C# the best language? Is Nim
| anachronistic? How would you write a desktop app using your
| exact same codebase on Win, Linux, Mac? That would be Free
| Pascal. Or maybe the desktop is now anachronistic, even
| though it still produces a richer UX.
|
| Many languages have their great qualities. Whether or not
| they're outdated is a determination full of biases. Measure
| the language choice against resources and potential
| revenue. I'd be happy to write an app in Ada to proclaim
| its advantages as a sales pitch.
| tombert wrote:
| Maybe "failed" is a strong word.
|
| I just don't see Ada used a lot anymore. This isn't a
| value judgement on it being "good" or "bad", lots of bad
| languages (like PHP) end up getting very popular, and
| lots of cool languages (like Idris) kind of languish in
| obscurity. Don't mistake me saying popularity is proper
| metric for how "good" something is.
|
| When I say "anachronistic", I don't mean it as a bad
| thing either, just that it's not used a lot anymore. I've
| literally never heard of anyone writing an Ada
| application in the last twenty years outside blogs on HN.
| thesuperbigfrog wrote:
| >> if someone wrote an application in Ada in 2025, I would
| find that a bit anachronistic.
|
| I suppose that Nvidia's use of Ada and SPARK for self-
| driving vehicles is anachronistic:
|
| https://www.eenewseurope.com/en/nvidia-drives-ada-and-
| spark-...
|
| https://nvidia.github.io/spark-
| process/process/introduction....
| jksmith wrote:
| The popularity contest.
| IshKebab wrote:
| It was held back by all of the compilers being commercial for a
| long time.
|
| Also the main advantage it has over C is safety, and nobody
| really took that seriously until recently (and it doesn't
| really have an answer for use-after-free which is a huge class
| of bugs).
| augustk wrote:
| The same thing happened to Bertrand Meyer's language Eiffel.
| myth_drannon wrote:
| Ada was getting a lot of traction in USSR (so commercial
| license prices were not a concern) and was pushed in many
| domains. My father studied it in university in the 80's. But
| with the Soviet Union collapse all those efforts fizzled.
| jksmith wrote:
| It failed because the C family is far superior - in mindshare
| and commodity dev experience. Ada may end up with a win to some
| degree if it plays to a narrative that all software needs to be
| mission-critical, no matter what the domain. Maybe in degrees,
| but that's actually true these days.
|
| I did some consulting at a major US car manufacturer, and
| helped with a coding seminar, mostly in java. A fair chunk of
| those developers struggled with a fizzbuzz exercise. All I can
| say is this: don't leave your baby in the back seat of an
| autonomous car just to get out and recharge unless you have
| consequential trust reciprocation with the manufacturer
| tantamount to shutting them down if anything tragic happened.
| Of course, even that price is too low.
| whartung wrote:
| Well that was disappointing. I was hoping to see a discussion
| about writing a zip encoder in Ada. How the language was used,
| values of the language for this kind of work. How it's easier or
| harder to do. Maybe a bunch of Ada source code.
|
| Simply as one who does not use Ada I had hoped to be a bit more
| informed about it.
| andsoitis wrote:
| Bottom of page links to the sources:
| https://github.com/zertovitch/zip-ada
| rustcleaner wrote:
| Why did Mozilla reinvent the wheel with Rust when we had
| Ada/SPARK?
| Jtsummers wrote:
| SPARK 2012 was what made SPARK viable for a broader audience.
| Earlier versions of SPARK were not really properly integrated
| into Ada (SPARK annotations were in comments). SPARK also
| restricts what is expressible to what is provable within SPARK
| (which expands over time), this has some important consequences
| for concurrency and parallelism (using the "concurrency is not
| parallelism" distinction). So it would have been hard for
| Graydon Hoare to use SPARK 2012 in 2006 when he started on
| Rust, and the limitations around concurrency in SPARK 2012
| would have been a non-starter for the objectives of Rust as
| adopted by Mozilla.
___________________________________________________________________
(page generated 2025-07-17 23:00 UTC)