<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Gavin Mendel Gleason on Medium]]></title>
        <description><![CDATA[Stories by Gavin Mendel Gleason on Medium]]></description>
        <link>https://medium.com/@gavin_68371?source=rss-af55715b33a0------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*YhR0slOOpp5xKoMgpQv9IQ.jpeg</url>
            <title>Stories by Gavin Mendel Gleason on Medium</title>
            <link>https://medium.com/@gavin_68371?source=rss-af55715b33a0------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 06:02:29 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@gavin_68371/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Building a Logic Programming Ecosystem]]></title>
            <link>https://medium.com/@gavin_68371/building-a-logic-programming-ecosystem-4811622574da?source=rss-af55715b33a0------2</link>
            <guid isPermaLink="false">https://medium.com/p/4811622574da</guid>
            <category><![CDATA[logic-programming]]></category>
            <category><![CDATA[virtual-machine]]></category>
            <category><![CDATA[prolog]]></category>
            <dc:creator><![CDATA[Gavin Mendel Gleason]]></dc:creator>
            <pubDate>Fri, 01 May 2020 18:56:00 GMT</pubDate>
            <atom:updated>2020-05-01T18:56:00.866Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*IVnhj181No06Yn56lFMTww.jpeg" /></figure><p>While the functional programming community has had a big influence on the design of new languages and language libraries, the logic programming community has languished in obscurity for a generation. The original promise of logic programming with the advent of prolog in the 1970s has produced fruit which has largely rotted on the vine. Logic programming is largely the domain of academic teaching staff, who often dislike the language as much as their students. It is seen as an oddity which might yield some insights, but has no bearing on real world programming.</p><p>Many detractors have contended that this is a consequence of the weakness of the paradigm: that prolog demonstrated that the logical features of the language are necessarily so contorted under use of cut, that you may as well use a functional programming language anyhow if you care about performance, and surely you can just use back-tracking in a library if necessary.</p><p>This is, in my opinion, a terrible shame. The promise of logic programming has not been realised for contingent reasons that really have little to do with the paradigm itself. Prolog was too early to hit the wave of scripting languages that sprung up in the wake of Perl, and too wedded to military industrial complex funds to learn how to build a niche in industry outside of some very researchy tasks. While people used to complain that Prolog is slow, languages like Python which are now completely pervasive are ludirously slow — but are used to drive other processes from a high level.</p><p>The promise of logic programming is so great that it can’t languish forever in obscurity. There are wide-open opportunities for the exploitation of declarative power. Not least of these is the possibility of parallel programming which is much more natural to control via a declarative approach. Perhaps not in a completely automated style, but with primitives which have a semantically straightforward meaning to the logic programmer.</p><p>But even closer to hand are the opportunities of constraint logic programming. <a href="https://www.metalevel.at/prolog/clpz">Constraint logics</a> provide us with tools to reason easily about <em>domains</em> such as the integers, or booleans, in such a way that we can specify a number of knowns or givens, and have the system, in a completely automatic way, yield us with the results.</p><p>If you’re trying to solve one of these constraint problems manually, you’ll probably get it wrong, and if you don’t, you’ll get the answer slowly, even if you’re writing it in C++. The techniques used to solve these problems rapidly are subtle and best left to a library.</p><p>And it is in logic programming languages that we can integrate such libraries most straightforwardly and with the least pain to the user. For this reason alone, I predict that we will see a rise in the use of logic programming in the next decades.</p><p>I am an avid and happy user of SWIPL prolog who uses prolog commercially in an open source project — <a href="https://terminusdb.com/">TerminusDB</a>. Yet despite my faith in logic programming I don’t see the confluence of factors which would be necessary to create a vibrant logic programming community going into the next decade. There is a route forward for logic programming languages, and we’re not taking it (yet).</p><p>What is it that we need?</p><p><strong>Worse is Better</strong></p><p>The promise of greater expressive power, purity of specification, and coherence of design is not sufficient to propel logic programming (or anything else) into the limelight. Vitally important is to develop the right kind of ecosystem. One of the things we’ve learned from the history of programming languages is that “worse is better”. Essentially, virality has less to do with beautiful consistency and more to do with finding quick and dirty vectors.</p><p>First I think we should commend those heros who have been doing the hard work to make this happen already, everyone who has worked on package managers and libraries to create the ecosystem we currently have. There are too many to list here, but I do value this work greatly: Well done!</p><p>I want it to be clear that I’m not having a go at the hard efforts already expended, but rather trying to figure out how we can do better.</p><p>So what would those vectors be for a logic programming language?</p><p>First I think it’s wise to think about what hasn’t worked. I’ve watched in the lisp community and the functional programming community more generally, as people have invented slight variants of this or that lisp saying that X was the killer feature needed to get broad adoption. Sometimes that is more trendiness, somtimes greater purity, but always it seems to lead to lots of effort and little adoption.</p><p>But there are some outliers. One lisp variant: <a href="https://clojure.org/">Clojure</a> is, I think, particularly relevant. It has managed to create quite a community whilst scores of lisps have died in obscurity. Why? Because it is a symbiot (which I guesss sounds better than parasite) on the Java platform. It learned the lesson of worse is better.</p><p>Writing a functional language on the JVM is a hassle (I’ve worked with some of the problems a bit in a former life), but writing a logic programming language on the JVM is probably insane. So while this represents an important lesson, we probably can’t crib it directly.</p><p><strong>The LogicVM</strong></p><p>However, languages like B-Prolog demonstrate that you can produce a VM that could be a useful target of a host of different logic programming languages. Could we not produce a LogicVM (LVM) design that was simple enough, but suitable enough to use not just for prolog, but for targetting constraints, co-routines and other prolog adjacent languages? Perhaps we could find a language suitable for targetting things such as Twelf, LambdaProlog, and CHR?</p><p>Having a core-LVM could enable a large number of experiments in LVM design to occur essentially in much looser coupling to the development of host environments. Prologs could target an LVM intermediate language which could then be written to a byte format, simplifying the process of designing new logic languages on the LVM. The LVM itself could, as the JVM did, benefit from experimentation in performance by optimisation, by changing approach — or for instance, developing a JIT. These optimisations could include things like instruction-fusion etc. in a pre-pass on the intermediate language, various choices of garbage collection strategy etc. LVMs could even be written from the ground up in different languages.</p><p>We could expose new instructions from the VM over time, allowing hosts to take advantage of these new targets to speed-up execution of known types, co-routining or constraint propagation or other such activities that might benefit from additional information.</p><p>Of course VM designers will press back with their own concerns, as they did in the JVM, leading to a healthy dialectic. I imagine questions of parallelisation strategy would be enormous open questions, but really they should be fought on the LVM design playing field primarily. And not as a choice between “prologs”.</p><p>Creating a more open VM would also facilitate the adoption of better extensions as well. Library writers would potentially have access to something low-level which could help to avoid some of the awkwardness that can present itself when you’re trying to talk at a lower level. This could be useful in everything from typing extensions to constraint logic.</p><p>From this VM we could flower a variety of libraries which fill in things like: Basic Prolog, extended Prologs and variations, A shared library which works across these various prologs. All of the types of benefits that people have witnessed from the JVM.</p><p><strong>The next decade</strong></p><p>I think the next decade should be the one in which declarative languages thrive. But we’ve got a small user community, and an even smaller developer community. That means we have to use our resources carefully to leverage our position. I am absolutely ecstatic about new developments like <a href="https://github.com/mthom/scryer-prolog">Scryer Prolog</a>, but looking at the structure I wonder if we couldn’t make this more about having a Rust VM, and less about having a new prolog. I recognise that there are some deep differences (for instance in the treatment of strings). Perhaps someone from the Scryer developer team could weigh in with a clearer vision.</p><p>Irrespective of the technicalities, the precise strategy is of less of concern than the general thrust. The thrust should be on virality, reducing the amount of unnecessary duplication of effort, and the increase in speed and functionality being less of a monolithic choice. I’m open to other opinions, but I think we should at least debate the question on the plausibility of representing an alternative potentially <em>viral</em> proposal.</p><p>The time for logic programming has definitely come, but only if we make it so.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4811622574da" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Type and mode checking in prolog (part 2): mavis]]></title>
            <link>https://medium.com/terminusdb/type-and-mode-checking-in-prolog-part-2-mavis-23334935d30e?source=rss-af55715b33a0------2</link>
            <guid isPermaLink="false">https://medium.com/p/23334935d30e</guid>
            <category><![CDATA[type-theory]]></category>
            <category><![CDATA[prolog]]></category>
            <category><![CDATA[determinism]]></category>
            <dc:creator><![CDATA[Gavin Mendel Gleason]]></dc:creator>
            <pubDate>Thu, 08 Aug 2019 15:44:01 GMT</pubDate>
            <atom:updated>2019-08-11T15:48:42.847Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Kd0HuHjwbp5c7OFtDXorOQ.jpeg" /><figcaption>Order within the chaos</figcaption></figure><p>As we discussed in Part 1 of this short series on types in prolog, prolog has a rather graceful but silent method of reacting to a certain bugs. The exploitation of non-determinism can be extremely handy for searching spaces, but sometimes we just didn’t mean what we wrote, and instead of silent failure we would like to see an error.</p><p>One way around this problem which we presented in <a href="https://medium.com/@gavin_68371/type-and-mode-checking-in-prolog-part-1-type-check-b0e7975dc80b">Part 1</a> was to use Hindley-Milner type (HM) checking to statically discover where we have variables which have a different type than we expect.</p><p>We’re going to take a different tack in this article and use dynamic type and mode checking with mavis. HM is great, but it wasn’t really written for prolog but for functional languages, and so doesn’t take any account of <em>modes</em>. It can also be a bit restrictive and heavy weight when modifying already existing code. We could of course dial it up, by introducing dependent types, but we’re not going to go there in this series (though how cool would this be?!).</p><p>With <a href="https://github.com/GavinMendelGleason/mavis">Mavis</a> we get to specify both modes and quite complex types in a gradual fashion, adding them as necessary. The downside is that type checking happens only at run-time and is not statically checked. Unfortunately this means we only catch bugs during testing or deployment, but at least we catch them!</p><p>I’ve used both techniques in production code and find them both useful, but currently Mavis is more fully featured and more flexible and so I’ve done most development with it.</p><p>What is a mode? Prolog is a language of predicates, and we can think of any given substitution of variables as being either true or false at a predicate. But often times what we are actually doing when programming in prolog is taking what we know about some bound variables, in order to find other ones which would also satisfy the predicate. And very often we mean a predicate to only search for bindings given some set of already instantiated variables.</p><p>Take for instance the following programme:</p><pre>/**<br> * zip(+A:list(any),+B:list(any),-C:list(any)) is det.<br> * zip(-A:list(any),-B:list(any),+C:list(any)) is det.<br> * <br> * Zip two lists into a list of pairs (or unzip, in the other two <br> * modes)<br> */<br>zip([A|RestA],[B|RestB],[(A-B)|Zip]) :-<br>  zip(RestA,RestB,Zip).<br>zip([],[],[]).</pre><p>The benefit of this declaration is obvious from the results of querying for the following goal:</p><pre>?- zip([1,2,3],a,C).</pre><pre>ERROR: Unhandled exception: The term a is not in the domain list(any)</pre><p>We have effectively stopped zip from silently failing in the event of passing nonsense arguments. But what do all of these complicated mode descriptions mean?</p><p>There are two mode-lines given for the above programme. We use a preceding ‘+’ to denote required arguments and ‘-’ to denote supplied arguments. If an argument is required (‘+’), it must be bound at the time the predicate is called. If it is supplied (‘-’), it can be bound or not, but we will guarantee that we supply a binding if it is unbound.</p><p>In fact binding time status is a bit more complicated than this. It’s quite possible to have a ‘skeleton’ which has unbound variables inside of a defined term. For instance, you can obtain such a skeleton of a list with the goal:</p><pre>?- length(L,3).</pre><pre>L = [_6186, _6192, _6198].</pre><p>Is this `+`? Mavis interprets it as bound if it is compatible with the type declaration. To require a completely defined input you can use `++`. In the future we want to include more specific user-defined designations modeling ourselves after those given in Mercury.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/775/1*5uS0w_e1LZ9T1ozQc8v1og.png" /></figure><p>The final part of the mode describes the amount of determinism that the predicate is expected to have. Zip above is considered to be ‘det’ which means in all the modes that are described, and subject to its inputs being well typed, it will return precisely one substitution. The different determinism qualifiers are listed in the mavis documentation as follows:</p><ul><li>failure: 0 solutions</li><li>semidet: 0 or 1 solution</li><li>det: 1 solution</li><li>multi: more than one solution</li><li>nondet: Any number of solutions including 0</li></ul><p>There are <em>allowable</em> modes which are <em>covered</em> by the above given modes to make things a little more confusing. For instance, I can call zip with the following two different goals, both of which are accepted as legitimate and do not yield errors.</p><pre>?- zip([1,2,3],[4,5,6],[1–4, 2–5, 3–6]).</pre><pre>true.</pre><pre>?- zip([1,2,3],[4,5,6],[1–4, 2–5, 3–7]).</pre><pre>false.</pre><p>In the first case we supplied all of the arguments. This is <em>more</em> informative than any of the modes given, and consequently causes the determinsm to be <em>demoted.</em> We shift from being ‘det’ to being ‘semidet’. This demotion is taken care of for us automatically by mavis.</p><p>We can also run the query <em>backwards</em>, since we have supplied the appropriate mode line above. This is the main reason we might want to specify multiple mode lines.</p><pre>?- zip(A,B,[1–4, 2–5, 3–6]).</pre><pre>A = [1, 2, 3],<br>B = [4, 5, 6].</pre><p>Mavis is really useful for finding bugs in production code during testing. I’ve recovered a large number of confusions, especially in the case of errors in my own thinking regards the determinism of various predicates. This can in turn have huge impacts on performance, since uncontrolled and unintended non-determinism can have surprisingly large impacts on speed.</p><p>There are however a number of things I’m unhappy with and I would like to see improved. I’ll list them out here as a sort of wish-list for mavis in the future.</p><ul><li>There should be a good deal more that is done statically. Many of the mode and type declarations give plenty of information to yield compile time errors.</li><li>With a bit more declarative work we could even reordered queries automatically to produce much more desirable outcomes for specific modes — and in some cases we could even improve the termination behaviour!</li><li>The types should <em>at least</em> give us the flexibility of Hindley-Milner type declarations with free type variables which can be used repeatedly. This would give us a much more pleasing and specific type for ‘zip’.</li><li>Someday in the not too distant future it would be nice to see dependent types making their way in. For the dynamic case, as we currently have with mavis, this shouldn’t even be too terribly hard to implement in a hacky sort of way!</li></ul><p>You can check out the lastest Mavis source here: <a href="https://github.com/GavinMendelGleason/mavis">https://github.com/GavinMendelGleason/mavis</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=23334935d30e" width="1" height="1" alt=""><hr><p><a href="https://medium.com/terminusdb/type-and-mode-checking-in-prolog-part-2-mavis-23334935d30e">Type and mode checking in prolog (part 2): mavis</a> was originally published in <a href="https://medium.com/terminusdb">TerminusDB Community</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Prolog meta-interpretation for syntax checking]]></title>
            <link>https://medium.com/terminusdb/prolog-meta-interpretation-for-syntax-checking-563934466ebf?source=rss-af55715b33a0------2</link>
            <guid isPermaLink="false">https://medium.com/p/563934466ebf</guid>
            <category><![CDATA[logic-programming]]></category>
            <category><![CDATA[type-theory]]></category>
            <category><![CDATA[functional-programming]]></category>
            <category><![CDATA[prolog]]></category>
            <dc:creator><![CDATA[Gavin Mendel Gleason]]></dc:creator>
            <pubDate>Tue, 11 Jun 2019 13:56:42 GMT</pubDate>
            <atom:updated>2019-08-11T15:48:53.131Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/943/1*AxldXLz7wODMBrT4mAKQWg.png" /></figure><p>Prolog is a fantastic toolkit for developing Domain Specific Languages (DSLs). Lexing and parsing are a breeze with the use of Declarative Clause Grammars (DCGs), and writing a interpreter or compiler is an essentially rule-based transformation problem anyhow.</p><p>But before we set about interpreting or compiling an expression, we need to know that a term, represented as an abstract syntax tree (AST) is well formed.</p><p>Writing a predicate which admits only those terms which conform to a given syntax is likewise very convenient in prolog. For instance, if we wanted to write down a predicate that checks the well-formedness of integer bearing lists, we might write it as follows:</p><pre>isa_int_list([]).<br>isa_int_list([H|T]) :-<br>    isa_integer(H),<br>    isa_int_list(T).</pre><p>When we undertake to use this predicate, we can certainly tell if a (already ground) list is well-formed. However, if it is <em>not</em> well formed, we are not given an enormous amount of feedback. We are instead entreated to the singularly uninformative result:</p><pre>?- isa_int_list([1,2,x]).<br>false.</pre><p>Well, we know it’s not an integer list, and given that we have an incredibly simple syntax, we can spot right away with the naked eye, the problem with the term. However, if the term is large, and the syntax is complex, returning <strong>false</strong> will not necessarily enlighten us to the source of the problem.</p><p>In the past I’ve dealt with this problem by writing relatively complicated syntax checkers, which throw errors when terms are known to be ill-formed, or keep track of failures to report to the top level.</p><p>This unfortunately defeats the clear expressive rule based qualities of the above code which neatly captures what we mean when we say that we have a list of integers. It both complicates the code, and increases the probability that you’ll not even express the intended conditions in the predicate.</p><p><strong>Enter the metainterpreter</strong></p><p>This is where metainterpretation comes to the rescue. Metainterpretation is a strategy for implementing custom interpretation of terms in prolog, using the fact that prolog is <a href="https://en.wikipedia.org/wiki/Homoiconicity">homoiconic</a> and we can easily appropriate functionality from the host system. For an overview of metainterpretation, it’s worth reading <a href="https://www.metalevel.at/markus.jpg">Markus Triska</a>’s examples <a href="https://www.metalevel.at/acomip/">here</a>, or looking at the relevant section in <a href="https://mitpress.mit.edu/books/art-prolog-second-edition">The Art of Prolog</a>.</p><p>Instead of writing a new predicate, we can reuse our predicate coupled with a metainterpreter which assumes a number of things about the predicate in question. We demand that the predicate be deterministic, i.e. it succeed in assigning the term to our accepted class in precisely one way. This is similar to the constraint that most type systems use to simplify checking and inference. We also demand that it draw from a relatively small number of primitive predicates and avoid cuts or other impurities.</p><p>You can look at the code here: <a href="https://github.com/GavinMendelGleason/typo">https://github.com/GavinMendelGleason/typo</a></p><p>Our metainterpreter will then execute the predicate, bit by bit, and return <strong>none</strong> in the event that there is no error, and <strong>just</strong>(Error) in the case that something has gone wrong. The Error will carry with it all the information about <em>all</em> failed approaches to accepting the term. With this in hand, we can either look at the full failure tree, or we can use the quite effective heuristic, that the deepest failure is likely to be the one that almost succeeded. We can do this by calling <strong>deepest</strong>/2 to give us back the longest error stack. We can then print this stack with <strong>write_stack</strong>/1.</p><p>So what happens when we try our initial example with our metainterpreter?</p><pre>-? metainterpret(isa_int_list([1,2,x]), ME), <br>   (   ME = just(E) <br>   -&gt;  deepest(E,S), write_stack(S)<br>   ;   true).</pre><pre>x is not an integer<br>Left conjuct fails: isa_integer(x)<br>No successful clause for predicate isa_int_list([x])<br>Right conjuct fails: isa_int_list([x])<br>No successful clause for predicate isa_int_list([2,x])<br>Right conjuct fails: isa_int_list([2,x])<br>No successful clause for predicate isa_int_list([1,2,x])</pre><p>Instead of false, we’ve found the most likely cause of failure, and the entire path up the syntax tree which resulted in the cascading failure!</p><p>Of course the reporting can be done differently, and the heuristic might vary with different uses, but I’ve found this an effective way of describing what has gone wrong. I’ve even found a bug in production code which was exposed when applying the metainterpreter as it tracked down an inadvertent non-determinism!</p><p>The take-away lesson for me was that sometimes its better to write a simple metainterpreter than it is to complicate your code. DSLs in prolog are easy to write and you can even write DSLs to help you write your DSLs.</p><p>Sometimes meta is betta!</p><p>Acknowledgments to Douglas R. Miles, who helped me sort out module manipulation issues.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=563934466ebf" width="1" height="1" alt=""><hr><p><a href="https://medium.com/terminusdb/prolog-meta-interpretation-for-syntax-checking-563934466ebf">Prolog meta-interpretation for syntax checking</a> was originally published in <a href="https://medium.com/terminusdb">TerminusDB Community</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Type and mode checking in prolog (part 1): type_check]]></title>
            <link>https://medium.com/terminusdb/type-and-mode-checking-in-prolog-part-1-type-check-b0e7975dc80b?source=rss-af55715b33a0------2</link>
            <guid isPermaLink="false">https://medium.com/p/b0e7975dc80b</guid>
            <category><![CDATA[type-theory]]></category>
            <category><![CDATA[prolog]]></category>
            <dc:creator><![CDATA[Gavin Mendel Gleason]]></dc:creator>
            <pubDate>Fri, 07 Jun 2019 15:07:06 GMT</pubDate>
            <atom:updated>2019-08-11T15:48:02.016Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*7HfZqnLrBUZpOwSkPWu8rA.png" /><figcaption>Hindley-Milner for a simple functional language</figcaption></figure><p>When it comes to languages for rule processing, prolog has them all beat. It has so many exciting features that make it incredibly flexible, among them:</p><ul><li>backtracking: we can try several strategies to solve a problem, and roll back if one doesn’t work. This also give us generators and testors using the same framework, enabling guess and check approaches to algorithms.</li><li>homoiconicity: which enables incredible metalogical madness including term and goal expansion and simplifying the writing of meta-interpreters.</li><li>DCGs (Declarative Clause Grammars): regexps are great, but when your language isn’t regular, DCGs give us one of the nicest ways to parse input around.</li></ul><p>Yet when trying to write large software packages in anger for industrial purposes, there are some unfortunate warts that tend to plague this otherwise beautiful language. I’ve compiled a fairly long mental list, but right now I want to talk about two of these awkward elements and what to do about them.</p><p>When you write a predicate in prolog, you can often make a very efficient choice between clauses in the predicate by carefully choosing terms which enable us to discriminate between the clauses we would like to “fire”.</p><pre>p(term_a) :- write(term_a).<br>p(term_b) :- write(term_b).</pre><p>When we invoke <strong>p</strong>(<strong>term_a</strong>) we are graciously treated to the expected printout. And perhaps even better we, with a prolog such as swipl, we don’t even end up with any remaining choice-points due to the indexing of the argument, making our choice efficient as well.</p><p>However, in large scale projects, it can happen that we call <strong>p</strong>/1 with something quite unexpected, perhaps with term_c, due either to a typo, or a thought-o. Prolog’s method of dealing with this is to silently fail — and since failure in prolog is a normal course of events, the result can lead to irritating bug-searches which take quite a while to narrow the problem to its source.</p><p>Of course what we want for <strong>p</strong>/1 is to correctly <em>type</em> it. That is, we want to be able to add some additional information to p about the domain of its arguments such that we can dynamically, or even better, statically, determine that they are not of the required variety.</p><h3>Hindley Milner and type_check</h3><p>Enter <a href="https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system">Hindley-Milner</a> (HM), a type system which allows us to write down just the sort of thing we’re concerned about when we call <strong>p</strong>/1. HM has a great number of advantages, allowing both inference of types in many cases, and the ability to write down our types in a nice algebraic fashion. It also includes many extensions which might be convenient in the case of prolog.</p><p>So how does HM work? Thanks to the work of Tom Schrijvers et al. we can try it out with the swipl package ‘<a href="http://www.swi-prolog.org/pack/list?p=type_check">type-check</a>’. For our p above we can now write the following:</p><pre>:- use_module(library(type_check)).</pre><pre>:- type term ---&gt; term_a ; term_b.</pre><pre>:- pred p(term).<br>p(term_a) :- write(term_a).<br>p(term_b) :- write(term_b).</pre><p>Here we add a type ‘term’ which is term_a, or (represented by the ‘<strong>;</strong>’) a term_b. We can now declare the arguments of our predicate p with a ‘pred’ declaration.</p><p>Now when we load our file, ‘type_check’ will attempt to find any type errors present in the code.</p><p>The first result of loading this file is the following message:</p><pre>% TYPE WARNING: call to unknown predicate `write(term_a)&#39;<br>%     Possible Fixes: - add type annotation `::&#39; to call<br>%                     - replace with call to other predicate<br>... :-<br>    &#39;HERE&#39;(write(term_a)).<br>% TYPE WARNING: call to unknown predicate `write(term_b)&#39;<br>%     Possible Fixes: - add type annotation `::&#39; to call<br>%                     - replace with call to other predicate<br>... :-<br>    &#39;HERE&#39;(write(term_b)).<br>%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%<br>% Type checking for module `first_blog&#39; done:<br>% found type errors in 0 out of 2 clauses.<br>% Well-typed code can&#39;t go wrong!<br>%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%</pre><p>Essentially our type-checker is telling us that it doesn’t know anything about <strong>write</strong>/1. Unfortunately the majority of standard ISO prolog is unknown to type-check. To really make it work properly for building software <em>in the large</em> we would need to add type annotations to our library. However, we have three different work-arounds provided by ‘type-check’.</p><p>The first two work-arounds I’ll demonstrate in tandem.</p><pre>:- pred p(term).<br>p(term_a) :- write(term_a) :: write(any).<br>p(term_b) :- write(term_b) :&lt; write(any).</pre><p>Here we add type <em>annotations</em> to the code to inform the type checker that it can assume the type of the arguments of <strong>write</strong>/1 to be of type ‘any’. Both of these annotations appear to achieve the same outcome, however the former adds an additional wrapper to the call, ensuring that the arguments are <em>actually</em> of the appropriate type dynamically. The second is nothing more than a “trust-me” style hint to the type checker.</p><p>Similarly we can build up a database of trust-me style hints using the following syntax:</p><pre>:- trust_pred write(any).</pre><p>We can imagine how this could be extended to much of the standard library, for instance:</p><pre>:- trust_pred append(list(T),list(T),list(T)).</pre><p>This establishes that any call with append is to be treated as though it takes a list of some unknown type, another list of that same unknown type, and returns an output list of that type.</p><p>Given we have used one of these methods to properly type our predicate p, we can look at what type_check reports when we utilise <strong>p</strong> wrongly.</p><pre>:- use_module(library(type_check)).</pre><pre>:- type term ---&gt; term_a ; term_b.</pre><pre>:- pred p(term).<br>p(term_a) :- write(term_a) :: write(any).<br>p(term_b) :- write(term_b) :: write(any).</pre><pre>:- pred q.<br>q :- p(term_c).</pre><p>The predicate <strong>q</strong>/0 is where we have inserted our buggy call. And indeed, type_check reports:</p><pre>TYPE ERROR: expected type `unknown_type&#39; for term `term_c&#39;<br>            inferred type `term&#39;<br> in goal:<br>   p(term_c)<br> in clause:<br>q :-<br>    &#39;HERE&#39;(p(term_c)).</pre><p>Well, type_check has shown us our error, and we can now correct our bug at compile time rather than having to wait until we see the error in production.</p><h3>Typing in the real world</h3><p>This is really great, but there are some caveats. The type_check library really needs to have a few kinks ironed out for it to work in industrial practice.</p><p>The first thing is that the full standard library needs to be given appropriate typing in a library, so that you don’t have to constantly run around typing everything. And in order to do this, type_check needs to be made module aware, which it currently is not. Module-awareness adds a good deal of complexity as well — how do we import types for instance?</p><p>Second, the addition of dynamic checks at boundaries is absolutely fantastic, and precisely the right way to ease a language like prolog into using static typing disciplines. However, <em>when</em> should we apply these type checks? This leads us to the question of <em>mode</em> checking. We will look at dynamic type checking and dynamic mode checking in the next article on <em>mavis</em>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b0e7975dc80b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/terminusdb/type-and-mode-checking-in-prolog-part-1-type-check-b0e7975dc80b">Type and mode checking in prolog (part 1): type_check</a> was originally published in <a href="https://medium.com/terminusdb">TerminusDB Community</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>