From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00
	autolearn=unavailable autolearn_force=no version=3.4.4
Path: 
 eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Paul Rubin <no.email@nospam.invalid>
Newsgroups: comp.lang.ada
Subject: Re: How to get Ada to ?cross the chasm??
Date: Sun, 06 May 2018 11:38:18 -0700
Organization: A noiseless patient Spider
Message-ID: <8736z4k4th.fsf@nightsong.com>
References: <1c73f159-eae4-4ae7-a348-03964b007197@googlegroups.com>
	<slrnpdpiv9.ntv.address@is.invalid>
	<pbr3mi$leu$1@franka.jacob-sparre.dk> <87k1su7nag.fsf@nightsong.com>
	<pbtlno$3k2$1@franka.jacob-sparre.dk> <87po2la2qt.fsf@nightsong.com>
	<87in8buttb.fsf@jacob-sparre.dk> <87wowqpowu.fsf@nightsong.com>
	<16406268-83df-4564-8855-9bd0fe9caac0@googlegroups.com>
	<87o9i2pkcr.fsf@nightsong.com> <pc8l7e$km5$1@franka.jacob-sparre.dk>
	<87in88m43h.fsf@nightsong.com>
	<cd866ee8-ad4d-489e-a38b-d8e5f5d4af00@googlegroups.com>
	<87efiuope8.fsf@nightsong.com> <pcdagp$7pn$1@franka.jacob-sparre.dk>
	<87lgd1heva.fsf@nightsong.com> <pcg54t$gul$1@franka.jacob-sparre.dk>
	<87zi1gz3kl.fsf@nightsong.com> <pciqcd$ou1$1@franka.jacob-sparre.dk>
	<878t8x7k1j.fsf@nightsong.com> <fl7t0uF410rU1@mid.individual.net>
Mime-Version: 1.0
Content-Type: text/plain
Injection-Info: reader02.eternal-september.org;
 posting-host="37995cf217b8b07e8c121df0d5a3fb96";
	logging-data="1057"; mail-complaints-to="abuse@eternal-september.org";
	posting-account="U2FsdGVkX1/Jac06r1krJzDWcqTgl/F6"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.3 (gnu/linux)
Cancel-Lock: sha1:Fm/T4DZmr2onnsLKozUSTxDm79s=
	sha1:k5tSXjNlkZqQxzRHQaLDpX5vpSw=
Xref: reader02.eternal-september.org comp.lang.ada:52048
Date: 2018-05-06T11:38:18-07:00
List-Id: <comp.lang.ada>

Niklas Holsti <niklas.holsti@tidorum.invalid> writes:
> The Ada programs for satellites on which I am currently working often
> meet with such problems, and either work slower (mutual exclusion
> between readers and writers), use more memory (dual physical copies of
> the data structure) and/or pass the problem to the satellite operators
> (commands to mutate the on-board data structure are delayed or failed
> if the data structure is in use by some reader). Better solutions are
> needed.

I think the natural Ada-flavored solution is use more memory.  You're
describing a classic transactional database update which has
traditionally been implemented using shadow pages.  Basically you write
the record in two places, then commit the transaction by flipping a
pointer.

A low-tech approach if you have MMU hardware is copy-on-write.  That is
how Redis (redis.io) does disk snapshots: when you ask for one, the
process forks, so the child process shares its memory pages with the
parent.  The child process then writes its memory to disk.  If the
parent updates a page while this is happening, the MMU traps the update
and makes a new copy of the page in the parent space.

Using a functional data structure like a red-black tree is also natural,
and this is how Happstack-State (a Haskell database) works.  But I think
its performance isn't that great.

You should definitely check out the book "Purely Functional Data
Structures" by Chris Okasaki if you haven't seen it already.

Because I can't resist, here's a beautiful Haskell implementation of
red-black trees using zippers, with the RB-tree invariants guaranteed by
the type signature:

  https://gist.github.com/2660297 (based on https://redd.it/ti5il)

With newer GHC's you can put the type-level natural numbers directly
into the signature, making it even prettier.