Thanks for the memoization - Simple function caching with Prolog

λ June 24, 2020
Tags: swi, prolog, memoization

I show you how Prolog makes caching of previously executed, possibly resource hungry, computations an absolute doddle. The technique is portable across languages.

I am currently in the process of writing a version “2.0” of a transpiler / translator project I started a long time ago. The official site is here. For the record, that site is 99.742% FELT code and a tiny amount of PHP bootstrap code. But that’s another article.

What -is- Memoisation ?

In a nutshell it’s the process of recording a previous result to a function / calculation so that the next time that call is issued with the same set of inputs that the same answer is returned.

The relevant Wikipedia page has a longer but as usual more concise interpretation.

In computing, memoization or memoisation is an optimisation technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again

Should I do it ?

It depends really. As always with software it’s a matter of weighing up the costs; saving results in RAM or in some external cache like Redis et al. obviously takes time and resource, it’s just a case of how much. If you were doing some kind of computationally heavy data-science work for example, you might want to consider it as it could help a lot.

My Use Case: Generating variable names

I am currently well into creating a transpiler system, I am currently working on the “C” language as that has a lot of requirements above and beyond the simpler dynamically typed languages. I allow pretty much any character as part of a variable name which means that all of these are legal in my system, the left is the input the right is the “cleansed” name:

fileName          fileName
file-name         file_name
file_name         file_name
to$String         to_dlr_String
->string          __gt_string
@convert          _at_convert
mad^Var-N@m3      mad_up_Var_N_at_m3

You can see the general approach. This works for most languages I’ve played around with. However, the process of translating the string is something that will happen over and over again and being one for not wasting time on repetition, I decided to have a go at implementing a system such that for any given input, I check to see if I did it before. Imagine this; a source file with a hundred references to a really mental variable name full of odd characters will do the same code one hundred times. Here’s the actual code that does it, with annotiations on the right that aren’t part of the real code…

:- dynamic cleansed_for/2.    % tells compiler cleansed_for/2 can be
                              % modified at run-time in the database
cleanse(In, Out) :-
    cleansed_for(In, Out),    % have we done it before ?
    !.                        % Yes!! Look no further...
                              % if it fails, Prolog backtracking will
                              % call the next cleanse/2 before failing.
cleanse(In, Out) :-
    string_codes(In, Chars),           % convert String to a list of codes
    maplist(cleanse_, Chars, Final),   % apply cleanse_ to every char
    flatten(Final, FinalChars),        % flatten any composites
    string_codes(Out, FinalChars),     % convert back to a String object
    asserta((cleansed_for(In,Out))).   % **Update database with new result.**

I won’t show the any more code for reasons of clarity and brevity. The first two predicates are the entry point, a string in and one back out. The first predicate attempts to execute the predicate cleansed_for with the value of In but this will fail. If it did work, then the next line, the !, (called a cut) tells Prolog that we’ve found an answer we are committed to and that it can abandon any further searching.

If however it did fail (it will on the first use of a new In string), then we come to the second implementation of the predicate, this converts the input (a String instance, a compact representation of a string as opposed to a list-of-code) to a list of codes which makes for easy processing, we then use maplist to apply the predicate cleanse_ to every character in the string and finally convert it back to a String into the Out variable.

How’s it doing it ?

The final line is the secret sauce, the asserta predicate is a system one, it literally asserts its argument into the running Prolog database as a new fact that can be checked. Over time for example we might end up with these facts being written, persistent for the current session only, with respect to the previous naming examples already seen:

cleansed_for("fileName",     "fileName").
cleansed_for("file-name",    "file_name").
cleansed_for("file_name",    "file_name").
cleansed_for("to$String",    "to_dlr_String").
cleansed_for("->string",     "__gt_string").
cleansed_for("@convert",     "_at_convert").
cleansed_for("mad^Var-N@m3", "mad_up_Var_N_at_m3").

This is where we set up the condition for success the next time we call cleanse with the same value for In. Normally its considered not good to dynamically add (assert) and retract facts like this for logical programming reasons…but…it’s perfectly valid and SWI Prolog makes use of this technique all over the place for allowing you to hook into the actual SWI run-time, printing messages etc etc. It’s a very powerful technique and as usual, that comes with great responsibility.

Summary

Memoization is a really old technique and one that is often overlooked. It works because any function can be replaced by a look up table. However, if the arguments are complex you may need to perform some kind of hashing function as the memoization key, again you would have to consider the efficiency of the hashing algorithm etc etc.

Here are some links for further reading on the technique across different eco-systems.

JavaScript

https://scotch.io/tutorials/understanding-memoization-in-javascript

https://flaviocopes.com/javascript-memoization/

PHP
https://github.com/traderinteractive/memoize-php

C# (https://www.dotnetperls.com/memoization)[https://www.dotnetperls.com/memoization]

Happy hacking!

Comments