Don’t Repeat Yourself when Computing Relations

Posted on August 14, 2022 Written by

To say that I am "gobsmacked" is an understatement! The s(CASP) language fulfills a 40-year-old dream for a computer language that adheres to the "Don’t repeat yourself" philosophy.

s(CASP) was described in 2003 by Joaquin Arias, Manuel Carro, Elmer Salazar, Kyle Marple, and Andgopal Gupta. Constraint Answer Set Programming without Grounding. Here is a recent tutorial published for the language A Short Tutorial on s(CASP), a Goal-directed Execution of Constraint Answer Set Programs. And has been recently implemented in both Caio and SWI-PROLOG. And here is a recent review article s(CASP) + SWI-Prolog = 🔥.

Write your first s(CASP) program using the s(CASP) profile at https://swish.swi-prolog.org.

In this article I’ll describe by way of example, the kind of language that I have been looking for and show a small aspect of what s(CASP) can do that other languages can’t.

Forty years ago, in my undergraduate days, I was introduced to the logic programming language "Prolog". The premise of the language is that a Prolog program captures facts and rules and that Prolog ‘figures out’ how to order the computations required to answer a query. This Prolog Family Relationships example shows how Prolog doesn’t have a preferred direction of computation. The arguments are symmetric with regards to what is known and what is unknown.

As shown above, if we provide one argument Prolog will compute the other, or if we provide the "other", Prolog will compute the "one".

Dream Computer Language

My dream computer language has, at least, the following capabilities:

  • Capture data and computable relationships between data independent of the questions (or queries) that the programmer is currently aware of (unlike procedural languages but like DBMSs do for data)
  • Enter information once. For both data and computable relationships and allow any missing data to be computed. Another way of expressing this is that the language handles known and unknown arguments symmetrically, is indifferent to which arguments are known and which are unknown, creating a computation to find the missing arguments (as Prolog does for the computed relationship mother() and as SQL does for data)

Problem

I soon discovered that Prolog doesn’t keep up its indifference to the direction of computation for long. As soon as mathematical calculations are added to Prolog the paradigm of order-independent facts and rules stops working. Consider the GST in Prolog example Prolog program to calculate a 10% GST (or VAT).

As you can see from the above example, the Prolog language will only find a solution for one direction of computation. While the definition contains enough information to compute both directions to, and from Price, Prolog is unable to do so.

How does s(CASP) compare?

s(CASP) captures the pricingwithgst rule in a similar way to Prolog, but has a ‘super power’ it treats all the arguments to the rule symmetrically and therefore handles the GST example perfectly!

The s(CASP) program contains exactly the same information in the Prolog program and shows the symmetry of handling arguments that I have dreamed of!

Application

A programming language that allows the capturing of a computed relationship (GST being a trivial example) and then doesn’t care which arguments to the relationship are known and which are unknown can reduce the cost of building and maintaining digital models to be used for various purposes.

Following on from the GST example, it is almost certain that the code behind Australia’s GST Calculator web app contains two copies of the computed relationship between Price, GST, and Price exGST, one for each direction of calculation. If s(CASP) was behind the app then the computed relationship would be entered just once as a rule, and the two directions of computation would just be two different queries with different knowns and unknowns. s(CASP) would sequence a computation to find the missing values.

Filed Under: Functional Programming, Other

Composable Recursive Relational Queries

Posted on December 11, 2021 Written by

Your input and feedback on this article are welcome on github.com/DavidPratten/sql-fp

Hierarchical and graph data may be transformed with relational queries that are recursive, iterative, and fixed-point. These are available in SQL through the recursive Common Table Expression (CTE):

WITH RECURSIVE ...

This article argues that SQL’s CTE machinery is a distraction from the core idea of a recursive query and a hinderance to composition of queries. We propose a simpler SQL form which is equally declarative, expressive and composes nicely:

SELECT ... UNION SELECT ... FROM UNION

In addition, we explore how this form may be translated into Morel, a descendent of ML with relational queries.

Let’s begin by introducing a motivating example

Transitive Closure of a Tree

If we have a tree

Example Tree

This can be represented in a relation as:

idparent_id
11
21
31
42
52
65
75

The transitive closure of the tree is:

Transitive Closure of the Tree with depth shown on the edges

And this may be represented by the following relation.

idparent_idlevel
110
220
330
440
550
660
770
211
311
421
521
651
751
412
512
622
722
613
713

Recursive CTE query

Using the Sqlite CTE form here is the query that computes the Transitive Closure given the Tree.

/* WITH RECURSIVE transitive closure of a tree (SQLITE)
   n.b. Tree's root node convention is id = parent_id
*/
with items (id, parent_id) as (
    select 1 id, 1 parent_id
    union
    select 2, 1
    union
    select 3, 1
    union
    select 4, 2
    union
    select 5, 2
    union
    select 6, 5
    union
    select 7, 5
),
     transitive_closure (id, root_id, level) as (
         select id, id, 0
            from items
         union
         select items1.id, tcitems.root_id, tcitems.level + 1
            from transitive_closure tcitems
            inner join items items1 on
                items1.parent_id = tcitems.id and
                items1.id <> items1.parent_id
     )
select * from transitive_closure;

Focusing in on the CTE let’s analyse its parts

  • A language closure (WITH). (Note this is a different concept than transitive closure.)
  • A name
  • Core Queries and Union
  • Final query.

As it turns out 3/4 of this structure may be dropped without loss.

SQL – SELECT … UNION SELECT … FROM UNION

We propose simplifying SQL by dropping the name, the closure and the final query and simplifying the composable recursive relational query down to: 

select id, id root_id, 0 level 
    from items
union
select items1.id, tcitems.root_id, tcitems.level + 1
    from union tcitems
        inner join items items1 on items1.parent_id = tcitems.id 
        and items1.id <> items1.parent_id

This form:

SELECT ... UNION SELECT ... FROM UNION

SELECTs the fixed-point result of the UNION without the overhead of a name (repeated three times), the closure and the final query.

This demonstrates that CTE machinery is not required to express recursive fixed point relational queries.

The simplified recursive relational query is orthogonal to all constructs in SQL and is composable:

  • if it is desired to hide some of the columns included in the recursive query, then the simplified recursive query can be wrapped in an outer SELECT, and
  • if the simplified recursive query needs to be consumed by more than one query then it can be
    • wrapped in a CTE, or
    • wrapped in a VIEW.

Multi-UNION Queries

There do need to be disambiguation rules if there are multiple UNIONs in scope. However, this is true whatever the linguistic form. See for example the multi-UNION rules for Sqlite. All non-recursive UNION sub-queries are constrained to be first, and all recursive sub-queries follow. And each recursive sub-query is presented with all generated rows from every other subquery in the UNION.

Composability

To be fair, the CTE variant of recursive queries is composable and SELECT FROM (WITH RECURSIVE …. SELECT …) works (at least in Sqlite). However, the ergonomics are poor, requiring the developer to build a mental model that includes a linguistic closure, a temporary local name, and a SELECT to pop back out of the closure. Here is the equivalent composable CTE-based query (Sqlite) with the required extra machinery in bold.

select * from (
    with _unionfixedpoint (id, root_id, level) as (
        select id, id root_id, 0 level 
            from items
        union
        select items1.id, tcitems.root_id, tcitems.level + 1
            from _unionfixedpoint tcitems
                inner join items items1 on items1.parent_id = tcitems.id 
                and items1.id <> items1.parent_id)
    select * from _unionfixedpoint
);

Application for other languages

The simplification of the recursive relational query to its essence is designed to improve developer experience and also points to a pattern for incorporating recursive queries into another language Morel.

Morel – from … union … from … in query

Having separated the idea of a recursive relational query from the CTE machinery, it becomes straight forward to propose the analog for a future release of Morel: 

(from item in items 
    yield {id = item.id, root_id=item.id, level=0})
union
(from tcitem in query,
    item1 in items
    where item1.parent_id = tcitem.id and item1.id != item1.parent_id
    yield {id = item1.id, root_id=tcitem.root_id, level=tcitem.level+1});

The form

in query

is proposed for Morel, because ‘in union’ is too specific. Morel’s roadmap includes consideration for other UNION-like operators including unnamed lambdas.

Filed Under: Functional Programming, Other

Aligning Real Estate Agent’s interests with those of the Vendor

Posted on August 15, 2021 Written by

The interests of property sellers (vendors) and the interests of their real estate agent can be better aligned. Firstly, this article shows how the “x% on sale price” commission model fails to reward agents for the effort required to find the highest paying buyer for a property and leads to agents overquoting the expected property price. And secondly this article, proposes a “Shared Outcomes Commission Rates” model that more closely aligns the interests of the agent, with those of the seller. You can try it out here.

x% on sale price commission model

The “x% on sale price” commission model rewards the agent with a percentage (for example 2.5%) of the sale price. If the property sells for $1M then the agent’s commission would be $25K.

This commission model doesn’t reward the effort required by an agent to find the buyer who will pay a higher price. Let’s say that to sell the property at the expected sale price of $1M it takes an effort. If the agent doubled their efforts (or worked twice as smartly) to find the best buyer, would we expect the sale price to double to $2M? Hardly! It might sell for $1.1M or $1.2M or more depending on the context. This means that the doubly hard working (or doubly smart working) agent is at best rewarded +10% or +20% in their commission from the sale. The effect of this commission structure is that the smart agent will do just enough to attract a reasonable purchase offer and move on to the next sale.

As well, the “x% on sale price” commission model leads to conditions where an agent can raise the vendor’s expectations of the achievable sale price for the purpose of securing the agency for the property. The vendor’s interests are in a higher sale price, and the “x% on sale price” commission model means that even if the agent is only able to deliver an ‘average’ rather than ‘excellent’ result, the agent’s commission may only decrease by a small margin.

Let’s explore the root of these issues.

The bulk of the reward is for hardly any effort

If the vendor was willing to accept 80% of their property’s value it will sell itself. Why is it a promising idea to base 80% of an agent’s expected reward on just the fact that the vendor signed up with this particular agent?

Before moving on to more detail, please be assured that I am not trying to argue that agent commissions are too high or too low. Just that agent effort is not being rewarded where it delivers value.

My main question is this “Can we structure commissions so that the extra agency effort required to achieve a 110% or 120% sale price are rewarded properly?”

Rewarding agent effort

A “sale within some time period for 80% sale price” can be achieved with minimal agency effort. Let’s imagine a commission structure that promised the agent a minimal reward for that outcome and instead shifts commission to reward the effort required for more than the minimal outcome.

Moving the sale price from 80% of expectation to 100% will be possible at some level of agency effort and for double the agency effort the sale price might be moved from 100% of expectation to 110% or 120%. It would be good if that extra agency effort were rewarded by a commensurate increase in commission.

Another desirable feature of such a pricing structure is that the agent will be reluctant to recommend that a property be sold below the expected price, because their commission would fall away rapidly. A 10% fall in price might mean that the vendor gets 90% of the value of the property but the agent only gets 50% of their expected commission.

Agent motivation to fairly represent the expected sale price

Under the “x% on sale price” commission model, an agent can use a 10-20% over-estimation of the sale price to secure a listing and thereby gain the uncontested 80% of the commission.

A vendor is likely to prefer a commission structure would act in such a way that an agent’s failure to achieve the estimated sale price would result in a significant reduction in commission. Under this situation, an agent’s desire to overquote to secure the business would be balanced by their assessment of their ability to deliver the estimated sale price.

Tiered Commission Rate approach

One existing approach to addressing these concerns is tiered commission rates. For example, Open Agent Australia’s 2018 article on “Why we like tiered commission rates.” clearly outlines the challenge and proposes a tiered approach to commissions that addresses them.

However, in practice, it is not easy to set up tiered commission rates. Setting up tiering requires making dozens of inter-locking choices:

  1. how many tiers should we use,
  2. at what point should our tiers start and finish,
  3. how much should we increase the commission at each tier?
  4. And finally once it is setup, how do we communicate the impact on the agent and vendor of these decisions.

The Shared Outcome Commission Rates approach below vastly simplifies this down to just four decisions. Let’s see how it works.

Shared Outcome Commission Rates

The “Shared Outcome Commission Rates” structure described below is an original contribution by the author. If anyone is aware of this proposal being previously described, I would be happy to add citations to the earlier authors’ works.

A Shared Outcome Commission Rates structure aligns the interests of the vendor and the agent. Here is how is an illustration of how it works. We make four decisions to create the Shared Outcomes Commission Rates Structure

  1. Base Sale Price. Property is estimated to sell for (example) $1M based information available in the marketplace.
  2. Commission payable on Base Sale Price. (example) 2.2%
  3. Estimated Sale Price if agent doubles effort (or works doubly smart). (example) $1.1M
  4. Maximum incremental commission on additional sale price. Never more that (example) 25c in the dollar of increased sale price.

Using these four decisions Chart 1 shows a commission model that shares the outcomes between the vendor and agent in proportion to the outcomes/ effort.

Chart 1. Shared Outcome Commission Rates
2.2% at $1M, 4.4% at $1.1M, Max Inc 25%

As you can see from Chart 1. above, a sale price 10% higher will attract double the commission and a sale price 10% worse, will attract a 50% commission of just 1.1%

The straight-line part on the right-hand side of the commission curve is caused by the decision to never allocate more than 25c in any dollar towards commissions.

Try it yourself

A Shared Outcomes Commission Rates calculator is here: https://davidpratten.com/sharedoutcomescommissionrates

Adjusting for market conditions

By way of comparison, if the market uncertainties were higher and a ten percent improvement could just occur by chance but a 20% improvement on the sale price is expected to require double the agent effort then the following Shared Outcomes Commission Rates structure might be more suitable.

Chart 2. Shared Outcome Commission Rates
2.2% at $1M, 4.4% at $1.2M, Max Inc 25%

Under this scenario, while the agent has a slower increase in commissions on the upside, it now takes a full 20% fall in sale price to halve the commission payable to the agent.

Impact of Shared Outcome Commission Rates

The author believes that the proposed “Shared Outcomes Commission Rates”, will positively align the interests of vendors and real estate agents.

  • Agents are rewarded in proportion to their efforts when delivering superior outcomes. And not rewarded for over-estimating the sale price.
  • And vendors are no longer paying 80% of the commission just because they signed up with an agent.

Win – Win.

Try it out … https://davidpratten.com/sharedoutcomescommissionrates

Filed Under: Other

Table Valued Constrained Functions (TVCF) – Constraint Programming and SQL

Posted on March 22, 2021 Written by

I propose seamless integration of solvers into SQL via Table Valued Constrained Functions (TVCF). By "seamless", I mean that the SQL programmer would have to ask the query planner if a constraint solver was invoked to complete the query.

A few years ago, I sketched the design of an ideal logic and constraint-based language "Parasat". In this article I describe a SQL language extension with similar goals which is also inspired by Picat.

Motivating Example

At university I was surprised, and disappointed, by the distance between the predicates of mathematical logic and those of Prolog. For example the Prolog interpreter was unable to give the answers

X=-4, Y= -3 and X=3 and Y=4

to the simultaneous equations x+1-y = 0 and x^2+y^2-25 = 0 expressed in Prolog as this predicate:

simultaneous(X,Y) :- plus(X, 1, Y),times(X,X,XSquared),times(Y,Y,YSquared),
    plus(XSquared,YSquared, XSquaredPlusYSquared),equals(XSquaredPlusYSquared,25)

Here is another way forward by extending SQL’s Table Valued Functions (TVF) to include constraints passed into the function by the query planner.

Solving this simultaneous equation with SQL-92

This particular simultaneous equation can be solved using an ordinary garden variety SQL-92 SELECT query. Given two relations, one each for the simultaneous equations:

CREATE TABLE XPlusZEqualsY (X,Z,Y);
CREATE TABLE XSquaredPlusYSquaredEqualsZ(X,Y,Z);

populated with select rows as follows:

XPlusZEqualsY

X Z Y
-5 1 -4
-4 1 -3
-3 2 -1
-3 1 -2
2 1 3
3 1 4
4 3 7

XSquaredPlusYSquaredEqualsZ

X Y Z
-4 -3 25
-1 -1 1
0 0 0
3 4 25

The following SQL-92 SELECT query will solve the simultaneous equation:

SELECT
  r1.X,
  r1.Y
FROM
  XPlusZEqualsY r1
  INNER JOIN XSquaredPlusYSquaredEqualsZ r2 ON r1.X = r2.X AND r1.Y = r2.Y
WHERE r1.Z = 1 and r2.Z = 25;

However, this is not a useful technique. This SELECT query only works when, out of the infinite rows that could be in the relations, the specific rows that make the simultaneous equation true happen to be pre-loaded.

Can Table Valued Functions (TVF) be used to provide a generic solution?

No, is the short answer. What are TVFs and why can’t they provide a solution?

Table Valued Functions (TVF) are defined in the SQL standard and implemented in widely-used databases.

a table function returns a (relational) table comprising zero or more rows, each row with one or more columns. See wikipedia User Defined Functions

TVFs are implemented in a variety of databases for example: SQLite, PostgreSQL, and MS SQL.

TVFs can’t provide a general solution the simultaneous equation problem. The example above will illustrate this. If we replace the tables above with TVFs and pass the two TVFs some parameters:

Q: What parameters(?) would we pass them to ensure that the TVFs generated the correct rows to be selected against?

SELECT
  r1.X,
  r1.Y
FROM
  XPlusZEqualsY(?) r1
  INNER JOIN XSquaredPlusYSquaredEqualsZ(?) r2 ON r1.X = r2.X AND r1.Y = r2.Y
WHERE r1.Z = 5 and r2.Z = 25;

A: There aren’t any (non-magical) parameters that can achieve this.

Table Valued Constrained Functions (TVCF)

As defined in this article, TVCFs are like TVFs in that they are:

  • Functions
  • that return 0 or more rows of 1 or more columns

In addition, however, TVCFs:

  • have a fixed and typed column-set, like an ordinary table or view
  • are read-only (no UPDATE or DELETE FROM),
  • may delegate back to the query planner the task of generating the next value by invoking a solver
  • are possibly non-deterministic
  • appear in SQL code as just their name like a table or a view (i.e. without parameters)
  • are lazily evaluated
  • are defined in a language which can be compiled into a form usable by solvers. We know this is feasible because the language Picat has this property.
  • parameters to the TVCF are provided by context e.g. constraints provided by ON and WHERE clauses

When a TVCF is referenced in a query:

  • if the contextually provided constraints provide all the information required to generate the next row the function returns the next row to the query engine.
  • otherwise the TVCF invariant is compiled by the query planner and with the known constraints is passed as input into a solver. The query planner seamlessly consumes the solver output and continues with the query.

What is a solver?

A solver accepts constraints specified in some language and provides solutions using one or more techniques. A good introduction to solvers may be found:

TVCFs Example

Here is the XPlusZEqualsY table from our example coded as a TVCF using a pythonic idiom:

CREATE FUNCTION XPlusZEqualsY 
    (X float|[constraint,..], 
    Z float|[constraint,..], 
    Y float|[constraint,..])
RETURNS TABLE
AS
INVARIANT: X+Z-Y=0
IF X, Z, and Y are float:
    /* All parameters are provided */
    IF INVARIANT(X,Z,Y):
        RETURN (X,Z,Y)
    ELSE:
        RETURN(EMPTY_ROW())
/* Two out of three parameters */
IF X and Z are float:
    RETURN (X, Z, X+Z)
ELIF X and Y are float:
    RETURN (X, Y-X, Y)
ELIF Z and Y are float:
    RETURN (Z-Y, Y, Z)
ELSE:
    /* less than two parameters */
    DELEGATE INVARIANT,X,Z,Y
;

This function has:

  • named input parameters of X, Z, and Y which are either floats or a list of constraints on the value of the parameter.
  • named result columns of X, Z and Y which are always floats.

The INVARIANT line captures the intent of the relation in a form:

  • usable as a true/false predicate, and
  • compilable to a form usable by a solver.

Let’s walk through the flow of the function

The behaviour of the function (copied at right) depends on what is provided by the query planner based on the context.

All parameters are provided. As would be the case in this example:

SELECT 1 FROM XPlusZEqualsY 
    WHERE X=1 AND Z=2 AND Z=3;

In this case, the provided row is returned if the invariant is true otherwise there is no matching value in the relation and the empty row is returned.

Two out of three parameters are provided. As would be the case in this example:

SELECT Z FROM XPlusZEqualsY 
    WHERE X=1 AND Y=2;

In this case the missing value is computed and the three values are returned as a row.

One or fewer parameters are provided. As in our example above (copied here for convenience):

SELECT
  r1.X,
  r1.Y
FROM
      XPlusZEqualsY r1
  INNER JOIN 
      XSquaredPlusYSquaredEqualsZ r2 
  ON r1.X = r2.X AND r1.Y = r2.Y
WHERE r1.Z = 1 and r2.Z = 25;

Here we have Z constrained to be 1 but X and Y are merely constrained not specified. In this case, the invariant with the parameters are delegated back to the query planner to compile and submit to a heuristically chosen solver.

CREATE FUNCTION XPlusZEqualsY 
    (X float|[constraint,..], 
    Z float|[constraint,..], 
    Y float|[constraint,..])
RETURNS TABLE
AS
INVARIANT: X+Z-Y=0
IF X, Z, and Y are float:
    /* All parameters are provided */
    IF INVARIANT(X,Z,Y):
        RETURN (X,Z,Y)
    ELSE:
        RETURN(EMPTY_ROW())
/* Two out of three parameters */
IF X and Z are float:
    RETURN (X, Z, X+Z)
ELIF X and Y are float:
    RETURN (X, Y-X, Y)
ELIF Z and Y are float:
    RETURN (Z-Y, Y, Z)
ELSE:
    /* less than two parameters */
    DELEGATE INVARIANT,X,Z,Y
;

Summary Pitch

SQL query writers are specifying constraints all the time, by using Table Valued Constrained Functions (TVCF) they gain access to the power of solvers with zero learning friction. Those responsible for writing SQL query planners are already using solver toolkits to solve other database challenges and are well placed to incorporate them into the heart of the relational model.

Filed Under: Other Tagged:

I just found three bugs in SQLite!

Posted on December 23, 2020 Written by

SQLite is the most widely used and arguably the most rigorously tested database in the world.

Today, the developers confirmed that valid queries that I created for the Rosella Model project exposed not one, not two, but three bugs hiding in the code.

I really can’t remember the last time a single query found 2 bugs, let alone 3. Quote source

Reflecting on the spirit of my work, one of the developers said

For years, I’ve been giving talks that encourage developers to embrace the power of the SQL query language – to move beyond simple SELECT and INSERT statements mixed with a pile of procedural code and instead write complex queries that give the answer directly. I often use some of the queries generated by Fossil as examples, pointing out how a few lines (or a few dozen lines) of SQL can replace thousands and thousands of lines of procedural code. Doing so reduces the number of bugs (which are roughly proportional to the number of lines of code) and also often result in faster solutions as well. But you, sir, have taken this idea to a whole new level. Quote source

I’m happy to claim bragging rights!

Filed Under: Other

Applied Category Theory

Posted on October 7, 2019 Written by

Recently I reached out to Simon Willerton about applying Category Theory to Project Management models, here is the response.

Putting Project Management models on a sound footing.

Hi Simon,

Thanks for your article on the Project Management Schedule Network as a category. Category theory may have a broader role in putting project management models on a sound footing.

If we include the Work Breakdown Stucture into the model, a central issue is maintaining coherence between the Schedule Network view (as discussed in your article above) and the Work Breakdown Structure view of the same activity.

… schedule activities participate in both the WBS tree structure (“leaf” nodes under the work packages) and in the schedule network (network nodes). The schedule activities are the “atoms” from which both the WBS tree structure and the schedule network are built. This means that the WBS and schedule network are maps of the same territory, and should, therefore be coherent. However, this observation is at wide variance to the experience of many project managers. Keys for Agile Co-Evolution of the WBS and Schedule Network: The “Schedule Network 100 Percent” Rule and the “Add and Prune Dependencies” Algorithm David Pratten, PMP – February 5, 2016

The initial step of converting the WBS to a Coherent Schedule Network looks like a functor: WBS to Coherent Schedule Network Functor

My intuition is that sequencing by adding dependencies and pruning while preserving coherence with the WBS is also a functor but I am less certain of that. Add Dependencies and preserve coherence with WBS

Ken Scrambler’s Lambda Jam 2019 – Applied Category Theory talk has inspired.

Are you aware of work going on in applying category theory to project management modelling?

David

Posted by: David Pratten on September 1, 2019 11:18 AM | Permalink | Reply to this

Re: Putting Project Management models on a sound footing.

Apologies for my rather tardy response, David. This certainly looks interesting, although I am quite ignorant of the vast majority of project management notions.

I don’t know of any work going on applying category theory to project management modelling at the moment. I know that a couple of (applied) category theorists have expressed interest in this to me, but I think they are working on various other things at the moment, as am I. My hope is to think seriously about this in a year or two when I’ve managed to get other projects off my plate.

Posted by: Simon Willerton on October 6, 2019 10:03 PM | Permalink | Reply to this
Filed Under: Other, Project Management

A relational language – Parasat

Posted on March 18, 2019 Written by

I am impressed by the logic language Picat and a recent presentation by Peter Alvaro “Three Things I Wish I Knew When I Started Designing Languages“.

Update 3: November 2022. The language MiniZinc turns out to fulfill the goals of Parasat language. Among its many features the one that stands out when comparing with the goal of Parasat is that MiniZinc adopts relational semantics in the sense that I pointed to below. For the details see the 2009 paper The Proper Treatment of Undefinedness in Constraint Languages by Stuckey and Frisch and the 2013 MiniZinc with Functions by Stuckey and Tack.

Update 2: William Byrd (@webyrd) the author of miniKanren recommended that I use the faster-miniKanren implementation for exploring relational programming.  He also recommended this paper: A unified approach to solving seven programming problems (functional pearl) Here is a quote from the paper that illuminates the intent of the Parasat language described below, but using miniKanren terminology: “These interpreters are written as relations in the constraint logic programming language miniKanren. Each interpreter relates two arguments: an expression expr to be evaluated, and the value val to which expr evaluates. These arguments may be only partially complete, containing logic variables representing unknown parts. Our miniKanren implementation will use constraint solving and search to fill in the logic variables with expressions and values consistent with the semantics of Racket. By placing logic variables representing unknowns in different positions within the expr and val arguments we can express a wide range of interesting queries, which provides the flexibility needed to solve the variety of challenges we pose.”

Update 1: Feedback on the Picat Google Group drew attention to the similarities with the ideas in this article with the motivation and goals of miniKanren.

I learned Prolog while at university in the early 80’s and its been refreshing to learn Picat, a language that builds on the Prolog tradition and Datalog, a simplification of Prolog.

At university I was surprised, and disappointed, by the distance between the predicates of mathematical logic and those of Prolog. For example the Prolog interpreter was unable to give the answer

X=1.454545, Y= 4.9090909

to the simultaneous equations 3x + 4y=24 and 5x + 3y=22 expressed in Prolog as this predicate:

simultaneous(X,Y) :- times(3,X,ThreeX),times(4,Y,FourY), plus(ThreeX,
FourY, PlusThreeXFourY),equals(PlusThreeXFourY,24), 
times(5,X,FiveX),times(3,Y,ThreeY), plus(FiveX, ThreeY,
PlusFourXThreeY),equals( PlusFourXThreeY ,22)

With the advances made by Picat, I am inspired to rekindle my dream of an ‘ideal’ predicate-based language. Lets call this language Parasat.

Parasat (Kazakh language) means intellect or understanding.

glosb.com definition, google translate definition

Assumed knowledge. This post assumes that the reader has a basic familiarity with Prolog, Datalog and Picat programming languages and with predicates, logic programming and constraint programming.

To a first approximation, Parasat is Picat with:

  • all predicates required to be bi-directional (unless a parameter is constrained as “Free”
  • all syntactic forms mapped back to predicates
  • the constraint solver folded back into the predicate-based core of the language

Parasat has the following three high level features:

  1. Predicates are reversible and encapsulate the relation among all parameters. All predicate parameters are both input and output
  2. Everything is a predicate, irrespective of surface form. In other words, all language features are syntactic sugar for predicates. This includes type declarations, formulas, relations, functions and constraints,
  3. “plug and play” search strategies. Solutions are found by heuristically and transparently applying a “plug and play” range of predicate satisfaction, predicate decomposition and search strategies including pattern matching, unification with backtracking and constraint solving.

At the present time Parasat is an idea for a language. This article sketches out these three language features.

Predicates are reversible.

Parasat’s reversible predicates encapsulate the relation among predicate parameters. This enables the unification of otherwise diverse functions. For example in Parasat, powers, logarithms and roots are all unified in this predicate:

pow(X,Y,XpowY): if X,Y, and XpowY are instantiated, returns true if
 X**Y==XpowY, false otherwise. If one of the variables is not instantiated
 then it is instantiated to the missing value.  If two or more of the parameters are not instantiated then the instantiation of the free parameters is delegated to the constraint solver.

More specific predicates may be defined using “<=>”, which reads as “may be mutually defined as”. These derived predicates are also reversible. 

 exp(X,eraisedtothepowerX) <=> pow(X=e, Y=X, XpowY=eraisedtothepowerX)
 sqrt(X,SqrtX) <=> pow(X=SqrtX ,Y=2,XpowY=X)
 sqr(X,SqrX) <=> pow(X=X, Y=2, XpowY=SqrX)
 log(X,LogtothebaseeofX) <=> pow(X=e, Y=LogtothebaseeofX, XpowY=X)
 log(B,X, LogtothebaseBofX) <=> pow(X=B, Y=LogtothebaseBofX,XpowY=X)
 log10(X,Logtothebase10ofX) <=> pow(X=10,Y=Logtothebase10ofX,XpowY=X)
 log2(X,Logtothebase2ofX) <=> pow(X=2,Y=Logtothebase2ofX,XpowY=X)

As you can see from the examples above, Parasat uses named parameters.

Naturally, in the same way addition and subtraction may be unified by the addedto/3 predicate.

addedto(X,Y,XaddedtoY): if X,Y, and XaddedtoY are instantiated, returns
true if X+Y==XaddedtoY, false otherwise. If one of the parameters is not
instantiated then it is instantiated to the missing value.  If two or more of the parameters are not instantiated then the instantiation of the free parameters is delegated to the constraint solver.

And multiplication and division, as times/3.

times(X,Y,XtimesY): if X,Y, and XtimesY are instantiated, returns true if
X*Y==XtimesY, false otherwise. If one of the  parameters is not instantiated then it is instantiated to the missing value. If two or more
of the parameters are not instantiated then the instantiation of the free
parameters is delegated to the constraint solver.

And binding and equality testing can be unified, as 

equals(X,Y): if X and Y are instantiated returns true if X==Y, false
otherwise. If one of the values is not instantiated then it is bound to the
same value as the other one. If neither X nor Y are instantiated then instantiation of the free parameters is delegated to the constraint solver.

Everything is a predicate

Parasat unifies infix notation, functions, constraints, and predicates. This can be illustrated by the following equivalent forms of the times(X,Y,XtimesY) predicate:

XtimesY = times(X,Y)
X = times(XtimesY,Y)
Y = times(X,XtimesY)
X,Y = times(XtimesY)
XtimesY,X,Y = times()

and with the following definitions added:

A / B <=>  times(XtimesY=A,Y=B)
A * B <=> times(X=A,Y=B)

the times(X,Y,XtimesY) predicate acquires the following additional equivalent forms:

Y = XtimesY / X
XtimesY = X * Y

“plug and play” search strategies

Parasat’s transparent application of different search strategies is illustrated by comparison of the Picat “Send More Money” program:

 %  PICAT SEND+MORE=MONEY
import cp.
sendmory => 
    Vars = [S,E,N,D,M,O,R,Y], % generate variables
    Vars :: 0..9,
    all_different(Vars), % generate constraints
    S #!= 0,
    M #!= 0,
    1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E 
        #= 10000*M + 1000*O + 100*N + 10*E + Y,
    solve(Vars), %  search
    writeln(Vars).

with the equivalent Parasat program: 

 %  PARASAT SEND+MORE=MONEY 
 sendmory(S:S,E:E,N:N,D:D,M:M,O:O,R:R,Y:Y) & writeln(S,E,N,D,M,O,R,Y).   
 sendmory(S,E,N,D,M,O,R,Y) <=> 
 type(Var:S, Domain:1..9) &
 type(Var:E, Domain:0..9) &
 type(Var:N, Domain:0..9) &
 type(Var:D, Domain:0..9) &
 type(Var:M, Domain:1..9) &
 type(Var:O, Domain:0..9) &
 type(Var:R, Domain:0..9) &
 type(Var:Y, Domain:0..9) &
 all_different(Set:[S,E,N,D,M,O,R,Y]) &
 1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E 
   = 10000*M + 1000*O + 100*N + 10*E + Y.

Parasat does not require an explicit “solve” instruction because the all_different predicate delegates finding missing values to the constraint solver. It transparently satisfies the sendmory() predicate using constraint programming to find the solution: [9,5,6,7,1,0,8,2] .

Note that in Parasat:

1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E 
   = 10000*M + 1000*O + 100*N + 10*E + Y

is syntactic sugar for:

 times(X:M, Y:1000,   XtimesY:T1) &  
     times(X:O, Y:100, XtimesY:T2) &  
     times(X:R, Y:10, XtimesY:T3) &  
     addedto(X:T1, Y:T2, XaddedtoY:T4) &  
     addedto(X:T3, Y:T4, XaddedtoY:T5) &  
     addedto(X:E, Y:T5, XaddedtoY:T6) &  
     times(X:S, Y:1000, XtimesY:T7) &  
     times(X:E, Y:100, XtimesY:T8) &  
     addedto(X:T7, Y:T8, XaddedtoY:T9) &  
     times(X:N, Y:10, XtimesY:T10) &  
     addedto(X:T9, Y:T10, XaddedtoY:T11) &  
     addedto(X:D, Y:T11, XaddedtoY:T12) &  
     addedto(X:T6, Y:T12, XaddedtoY:T13) &  
     times(X:M, Y:10000, XtimesY:T14) &  
     times(X:O, Y:1000, XtimesY:T15) &  
     addedto(X:T14, Y:T15, XaddedtoY:T16) &  
     times(X:N, Y:100, XtimesY:T17) &  
     addedto(X:T16, Y:T17, XaddedtoY:T18) &  
     times(X:E, Y:10, XtimesY:T19) &  
     addedto(X:T18, Y:T19, XaddedtoY:T20) &  
     addedto(X:Y, Y:T20, XaddedtoY:T21) &  
     equals(X:T13, Y:T21)

Conclusion

This brief sketch captures key ideas for an ideal predicate language “Parasat”. Your feedback is welcome in the comments below.

Filed Under: Other

Underwater Running Demos

Posted on January 7, 2017 Written by

Underwater running on sand in deep water provides high resistance aerobic exercise. (No weights or other equipment required.) Here are a couple of videos showing the technique.

https://www.youtube.com/watch?v=Vuvyo2M6rT8?rel=0

https://www.youtube.com/watch?v=DDG0TTvHEEw?rel=0

Filed Under: Other, Underwater Running

Expected % Complete MS Project Custom Column

Posted on August 9, 2014 Written by

I attended Angela Chellas’ MS Project Advanced workshop today (excellent course) and there was a question about how to figure out what % complete that a task should be if it was on track.  Based on elapsed time, the Expected % Complete for tasks and summary items may be calculated using a MS Project Custom Field.

[expand title=”Text of the formula – to paste in.”]

Int(
  IIf([Current Date]>=[Start]
     ,IIf([Current Date]<=[Finish],
        IIf([Duration]>0,
           ProjDateDiff([Start],[Current Date])/[Duration]*100
           ,IIf([Current Date]>=[Start],100,0))
        ,100)
     ,0)
)

[/expand]

 

You create the custom column like this.

customcol2

Filed Under: MS Project, Other, Project Management

Portable Bank Account Numbers

Posted on July 1, 2014 Written by

As you are probably aware, the Australian telecommunications regulator mandated mobile phone number portability which eliminated a major source of ‘lock-in’ previously available to phone companies.

Today banks enjoy a very similar source of lock-in – the lack of portability of bank account numbers. Changing from one bank to another s requires the re-establishment of receipt and payment methods with employers, customers and service suppliers. The hassle and effort here works in the banks’ favour by increasing the cost of moving from one bank to another.

I imagine a future in which I can switch banks without disturbing any of my other financial relationships! When I accept funds or pay someone I use a number that is owned by me, not my bank. If I change banks, the number comes with me.

We enjoy this opportunity with our mobile phone communications – anyone else interested in having the same opportunity with our money?

Filed Under: Ideas, Other

Finding “my place” in Australia

Posted on October 27, 2011 Written by

It has been almost eighteen months since posting to this blog and two years since I returned to Australia with my family in late December 2009. I joined Wesley Mission as a Project Manager and Business Analyst in May 2010.  Project managing an upgrade of  core business systems in Wesley Mission’s hospitals at Ashfield and Kogarah continues to stimulate and challenge with many opportunities to learn and develop new skills.

Filed Under: Other

Australian Radio Streaming URLs

Posted on May 18, 2010 Written by

I have just started using the Chrome Radio Player and search as I may, I was unable to find a single source for the streaming urls of Australian radio stations. I have found them and here is the result of my research. You can plug these URLs into your streaming player. — Enjoy

Filed Under: Other Tagged: ,

Golf Zero

Posted on March 20, 2010 Written by

Some keen golfers face a time when they can enjoy a walk around a golf course, but are not able to swing a golf club like they used to. A golfer’s swing could be interrupted due to injury, sickness or due to natural aging processes.

Should an inability to swing stop a golfer from enjoying the course? No. “Golf Zero” could be an answer. Here is an idea. Let “Golf Zero” be a zero swing game of golf that uses a small compressed air powered cannon to fire a golf ball when on the fairway, and a curved pipe for putting.

The fairway cannon fits onto a golf buggy in place of a bag of golf clubs and the Golf Zero golfer controls it using a wirelessly linked iPhone App that includes the course layout. The golfer chooses which stick to emulate, either an iron or wood plus a variable swing.

On the putting green, the golfer drops a golf ball down a curved pipe that is pointed towards the flag.

The combination of a small air powered cannon on the fairway and a curved pipe on the green may provide a way for golfers who have lost their swing to stay the course!

Filed Under: Other Tagged: ,

Lifetime Postal Address

Posted on February 16, 2010 Written by

I would like a Lifetime Postal Address (LPA) that I could give to the 50+ organisations that send me items in the post. I would be happy to pay Australia Post $100 per year for the opportunity to never have to change my postal address – ever.

Given the mobility of the Australian popupation, this is a marketing opportunity for Australia Post. Australian PO Box holders can get a similar service today by a/ renting a PO Box and then b/ paying for redirection. The LPA simplifies and streamlines the service.

Here is a few more details on how this could work.

  • Subscribers update their actual delivery addresses, as often as necessary, at a secure website run by Australia Post
  • LPA’s are globally unique
  • LPA’s could be formed like airline booking references 6 alphanumeric digits.
  • The last character in an LPA is a check-character that ensures that different LPAs always differ by more than one character
  • If a LPA subscriber let their subscription lapse, then their mail is “Returned to Sender LPA not active”
  • Once allocated, LPA’s are only returned to the available pool 20 years after they have lapsed.
  • LPA subscribers could be offered discounts on bundled PO Box rental

Addendum. The Lifetime Addressing Inc. was formed in 1998 to promote this idea.

Filed Under: Other

Working Commute by Rail

Posted on February 15, 2010 Written by

I visited Thirlmere yesterday – the centre of Steam Engines in NSW. I didn’t get to ride on any of the engines, but did meet half a dozen people who commute daily to the Sydney CBD to work. This is a two hour commute – in both directions. One person leaves home at 5:30am each day to be at work on time!

Four hours a day commuting? Is there a way of integrating the commute time into the working day? For many commuters the rail journey is for relaxation, reflection, study and sleep because it is on top of a regular work day. However a different pattern is possible, one that decreases the length of the work back towards 8 to 9 hours.

How about a “hot desking” rail service that runs from the fringes of Sydney arriving in the city at 8am, 10am and midday and then a return service leaving at 1pm, 3pm, and 5pm? Staff clock on when then join the train, work for up to two hours on the journey in, spend four to five hours in the city office for face to face interactions, and then work up to a further two hours on the train on the way home.

“Hot Desk” Rail carriages could be fitted out with:

  • individual chairs
  • high-speed WiFi internet
  • pull out/ pull down writing desk
  • half height privacy dividers between chairs

Organisations which are based in the CBD lease seats in the “Hot Desking” service for their staff and schedule face to face meetings into the core times between 10am and 2pm.

Filed Under: Other Tagged:
Next Page »