# Handling missing data

Real world data is often faulty. Noisy data and missing data are common problems that applications must deal with sensibly. In this blog post, we focus on how to handle missing data. The solution we described can also be used to handle noisy data.

As an example, assume our raw data is the set of facts that describe the Addams family in the family example included in the Logtalk distribution:

male(gomez).
male(pubert).
male(pugsley).

female(morticia).
female(wednesday).

parent(gomez, pubert).
parent(gomez, pugsley).
parent(gomez, wednesday).
parent(morticia, pubert).
parent(morticia, pugsley).
parent(morticia, wednesday).


The missing data in this case is the parents of Morticia and Gomez (plus the parents of their parents, and …). The first step in a data processing application is the data acquisition. This can be as simple as reading the data or apply some transformation to facilitate later processing. For our purpose, assume that we want to convert the data to the following representation:

% parents(Child, Father, Mother)


For the Addams children, the facts are straight-forward:

parents(pubert, gomez, morticia).
parents(pugsley, gomez, morticia).
parents(wednesday, gomez, morticia).


But how to represent the missing parents of Morticia and Gomez? Should we use placeholder values like “Jane Doe” and “John Doe”? Should we throw an error or print a warning for the missing data? Should we skip and discard it? For all but the simplest cases, we want to minimize the coupling between data acquisition and data processing. I.e. we don’t want to make any hard choices during data acquisition that may constrain data processing. Therefore, we need to represent the missing data in a way that allows any later data processing to decide how to deal with it. Logtalk provides an expecteds library that allows convenient representation of the missing data:

parents(Person, ExpectedFather, ExpectedMother) :-
% enumerate the persons in the family database
(   male(Person)
;   female(Person)
),
% construct expected terms that either hold the parent name or error information
expected::from_goal((parent(Father,Person), male(Father)), Father, missing_father, ExpectedFather),
expected::from_goal((parent(Mother,Person), female(Mother)), Mother, missing_mother, ExpectedMother).


The expected::from_goal(Goal, Value, Error, Expected) predicate constructs an expected term by calling Goal that binds Value on success. Otherwise, it returns an expected term with the unexpected goal error or failure represented by the Error argument. I.e. an expected term can be seen as an opaque compound term that either holds a value or an error explaining why the value is missing. Effectively, expected terms allows us to defer any error handling during the data acquisition step to the data processing steps where the data is actually used.

How are expected terms used during data processing? Let’s consider two scenarios. In the first one, we want to print the names of all persons and their parents with the names of missing parents replaced by either john doe or jane doe:

print :-
forall(
(   parents(Person, ExpectedFather, ExpectedMother),
% replace missing father or mother with hypothetical names
expected(ExpectedFather)::or_else(Father, 'john doe'),
expected(ExpectedMother)::or_else(Mother, 'jane doe')
),
print(Person, Father, Mother)
).


The expected(Expected)::or_else(Value, Default) predicate binds Value to the expected value when present. Otherwise, it binds Value to the provided Default. Calling the print/0 predicate will output:

gomez
father: john doe
mother: jane doe

pubert
father: gomez
mother: morticia

pugsley
father: gomez
mother: morticia

morticia
father: john doe
mother: jane doe

wednesday
father: gomez
mother: morticia


In the second data processing scenario, we want to print only the parent records that are complete. Thus, we need to skip all records where the mother and/or the father are unknown:

print_complete :-
forall(
(   data_acquisition::parents(Person, ExpectedFather, ExpectedMother),
% fail if the father or the mother are unknown
expected(ExpectedFather)::or_else_fail(Father),
expected(ExpectedMother)::or_else_fail(Mother)
),
print(Person, Father, Mother)
).


The expected(Expected)::or_else_fail(Value) binds Value to the to the expected value when present and fails otherwise. The output of this predicate will be:

pubert
father: gomez
mother: morticia

pugsley
father: gomez
mother: morticia

wednesday
father: gomez
mother: morticia


As we illustrated in these two simple scenarios, each processing step can individually and independently decide on how to handle missing that.

Our Addams family example uses a single data acquisition step and multiple but parallel processing steps. A different but also common scenario is a sequence of processing steps. In this case, the handling of missing data in one step is passed to the next step. Assume a children image processing application that applies the following sequence of filters:

1. Crop to cat
3. Make eyes sparkle
4. Make smaller

The missing data in this could be no cat in the original raw image. But there might be also a cat in the image with no visible head or with eyes closed. For the sake of argument, assume the following possible filter failures and their representation:

• No cat in the image; who let the cat out: missing_cat
• Cat trashed the bow tie; no funny business: bow_tie_failure
• Cat with eyes closed; no sparkling eyes: eyes_closed
• Cat enjoys lasagna; not the path to get smaller: wants_to_grow
• It is a sunny day; no rain for making rainbows: sunny_day

Testing for exceptions at each step would result in ugly code full of conditionals masking what is essentially a simple sequence of steps. But expected terms can also be used to represent something that is missing from a previous step, not just from the initial data acquisition step:

process_image(Image, Final) :-
% encapsulate the "image" in an expected term
expected::of_expected(Image, Final0),
% apply a sequence of image filters
crop_to_cat(Final0, Final1),
make_eyes_sparkle(Final2, Final3),
make_smaller(Final3, Final4),
% either return the final image or throw any exception
% that happened while applying one of the filters
expected(Final5)::or_else_throw(Final).


The idea is that each processing step takes as input an expected term and outputs an expected term. At this point, of course, you’re screaming “DCGs!”:

process_image(Image, Final) :-
% encapsulate the "image" in an expected term
expected::of_expected(Image, Final0),
% apply a sequence of image filters
phrase(process, Final0, Final1),
% either return the final image or throw any exception
% that happened while applying one of the filters
expected(Final1)::or_else_throw(Final).

process -->
crop_to_cat,
make_eyes_sparkle,
make_smaller,


Either way, each processing step, i.e. each filter looks into the input expected term and, if a value is present, does its task. If the value is missing, that it simply passes the expected term to the next step. But if for some reason a value is present but the task cannot be completed, it outputs an expected term with that reason as the cause of the failure: Using as example the first two filters:

crop_to_cat -->
call(apply_filter(cropped, missing_cat)).

call(apply_filter(with_bow_tie, bow_tie_failure)).

...


As this is just an example, we simplify our code by assuming that the same apply_filter/4 predicate could be used by all the filters. Moreover, just for the sake of a demo output, we use the random::maybe(Probability) predicate to decide between filter success or failure:

apply_filter(Filter, Error, In, Out) :-
Filtered =.. [Filter, Value],
expected(In)::flat_map(
{Filtered,Error}/[Value,Expected]>>(expected::from_goal(maybe(0.9), Filtered, Error, Expected)),
Out
).


The expected(Expected)::flat_map(Closure, NewExpected) predicate either simply returns the expected term if it contains an unexpected error (thus passing it along the sequence of calls) or applies a closure to the expected value and the resulting expected term. Here we use a lambda expression to call the from_goal/4 constructor, which takes as arguments a goal whose success or failure/error dictates if we wrap an expected value, Filtered, or an unexpected error, Error. Given the use of a random number generator, the output would be something like:

% call cascade::process_image/2 repeatedly to trigger the random errors:

Final = with_rainbow(smaller(sparkling_eyes(with_bow_tie(cropped(image))))).

uncaught exception: missing_cat

Final = with_rainbow(smaller(sparkling_eyes(with_bow_tie(cropped(image))))).

uncaught exception: eyes_closed

Final = with_rainbow(smaller(sparkling_eyes(with_bow_tie(cropped(image))))).

Final = with_rainbow(smaller(sparkling_eyes(with_bow_tie(cropped(image))))).

uncaught exception: sunny_day


But is there any advantage in this case to use expected terms instead of simply calling the sequence of filters from a catch/3 or setup_call_cleanup/3 goal and having all filters throw exceptions? Using exceptions for control flow is not good practice, specially for declarative languages. Exceptions are also relatively costly. Is easy, of course, to convert an exception into a failure if necessary but at that point we are already paying the declarative and computational price of using exceptions.

Assume we are processing a large set of images, triggering a significant number of filter failures. Using expected terms, until the last goal in the body of our process_image/2 predicate, there are no exceptions being throw. We could simply change the last goal to:

process_image(Image, Final) :-
...,
expected(Final1)::or_else_fail(Final).


I.e. simply fail if one of the filters failed and move to the next image in our processing pipeline. In this alternative, no exceptions are ever generated.

Another possible advantage of using expected terms instead of a catch/3 or similar wrapper is that each step have the chance to fix a failure in a previous step. But using exceptions results in aborting the sequence of steps and jumping out to the exception handler with no chance of locally recovering from a step failure and continuing to the next step.

Using expected terms also allows us to handle both step errors and failures uniformly and simplify attaching explanations to failures as an unexpected result is just a wrapped term. Using a catch/3 or setup_call_cleanup/3 solution, a step that fails gives no explanation to the cause of the failure. We could workaround this issue by forcing the use of exceptions to represent any failures but this is far from ideal if the individual steps can be used in other contexts where a failure is a preferred outcome.

Yet another possible advantage of expected terms is easier composition of groups of processing steps. A failure or error can be simply passed from a group of steps to another group of steps. We can choose, for exemple, to handle exceptional events at a sigle place at the end of the processing pipeline. If, in alternative, each group of steps is wrapped by a catch/3 or setup_call_cleanup/3 goal, we easily end up with multiple exception handlers, often nested, and worrying if we forgot to handle a particular exception or if we captured an exception that should have been passed to an outer handler.

### Final notes

The use of expected terms give clear advantages in some cases, such as in the family example, and possible advantages in other cases, such as in the cats example. In the later case, consider carefully the inherent cost of using expected terms (specially if wrapping built-in and library predicates to convert variable bindings) and the desired semantics for handling exceptional events (notably, the need for failure explanations and fail fast versus passing the exceptional event along the processing pipeline).

The expecteds library provides other useful predicates for constructing and handling expected terms. The use of the expected/1 parametric object enables static binding to be used for all calls to the predicates that operate on expected terms for the best performance.

### Resources

The Logtalk distribution includes the full source code of the examples used in this blog post: missing_data and cascade.

Scott Wlaschin blog post and presentation on Railway Oriented Programming.