Program Description Based Programming

This document describes a program description based programming library.

We refer to it as the PDBP library.

Below is the logo of the library

    //       _______         __    __        _______
    //      / ___  /\       / /\  / /\      / ___  /\
    //     / /__/ / / _____/ / / / /_/__   / /__/ / /
    //    / _____/ / / ___  / / / ___  /\ /____  / /
    //   / /\____\/ / /__/ / / / /__/ / / \___/ / /
    //  /_/ /      /______/ / /______/ /     /_/ /
    //  \_\/       \______\/  \______\/      \_\/
    //                                           v1.0
    //  Program Description Based Programming Library
    //  author        Luc Duponcheel        2017-2018

I hope you enjoy reading this document and using the PDBP library it describes.

All comments are welcome [ pdbp dot blog at gmail dot com ].

Warning

Both this document and the library it describes are

History

In 1977, John Backus was an ACM A.M. Turing Award Winner. The title of his Turing Award winning lecture was

Can programming be liberated from the von Neumann style?

A functional style and it’s algebra of programs.

This document builds upon the ideas of this influential lecture.

Introduction

When writing an introduction it is challenging to find the right balance between providing too many details or too few details. On the one hand this introduction provides (hopefully not too) many details. On the other hand this introduction omits (hopefully not too) many details. You have to use your knowlegde and imagination to make sense of it.

It is perfectly fine to first read it diagonally.

I recommend to reread it from time to time once you get more and more acqainted with the content of the rest of the document.

Introducing FP

In his Turing Award winning lecture, John Backus describes the FP programming language.

The FP programming language consists, roughly speaking, of objects, programs, forms and definitions, where

The FP forms are

Think of most forms as a program templates, programs transformed by them as program fragments, or program components, and the resulting program as composite program.

Introducing Dotty

The PDBP library is written in the Dotty programming language which will, eventually, evolve to version 3.0 of the Scala programming language.

When dealing with Dotty, we use value and object interchangeably since, in Dotty every value is an object.

Introducing trait Program

The main type class of the PDBP library is trait Program.

package pdbp.program

trait Program[>-->[- _, + _]]
    extends Function[>-->]
    with Composition[>-->]
    with Construction[>-->]
    with Condition[>-->]
    with Aggregation[>-->]

For every FP form there is a trait that is mixed-in by trait Program.

FP does not really have an Aggregation form. FP does have sequences of objects and it is possible to define FP programs that aggregate sequences of objects to an object.

Think of most members of trait Program as a program templates, programs transformed by them as program fragments, or program components, and the resulting program as composite program.

trait Program closely resembles arrows.

In 1998, John Hughes described arrows and used arrows in Haskell in Generalizing monads to arrows.

trait Program exposes a pointfree programming API for application developers.

trait Program is about program descriptions. Program descriptions are defined in terms of programming capabilities that are declared or defined as members of trait Program.

By abuse of notation, we often simply refer to program descriptions as programs. We hope that this does not lead to any confusion.

Compare this with the famous painting Ceci n’est pas une pipe of René Magritte. The painting is not a pipe, it is a pipe description.

In a way programs generalize functions.

When there is no danger of confusion

We often simply write

and

Note that we use both (zero or more) arguments (for functions) and (one) argument (for programs). The difference between arguments and argument is somewhat superfluous since, as explained later in this document, one argument can represent zero or more arguments.

Introducing trait Computation

Another important type class of the PDBP library is trait Computation.

package pdbp.computation

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.program.Program

private[pdbp] trait Computation[C[+ _]]
    extends Resulting[C]
    with Binding[C]
    with Sequencing[C]
    with Lifting[C]
    with Program[Kleisli[C]]
    with Applying[Kleisli[C]] {

      // ...

}

where

package pdbp.types.kleisli.binary

private[pdbp] object kleisliBinaryTypeConstructorType {

  private[pdbp] type Kleisli[C[+ _]] = [-Z, + Y] => Z => C[Y]

}

Note that Kleisli[C], where C is a unary type constructor, is itself a binary type constructor.

trait Computation closely resembles monads.

In 1991, Eugenio Moggi described monads in Notions of computation and monads.

In 1992, Philip Wadler used monads in Haskell in The essence of functional programming.

trait Computation is about computation descriptions. Computation descriptions are defined in terms of computational capabilities that are declared or default defined as members of trait Computation.

By abuse of notation, we often simply refer to computation descriptions as computations. We hope that this does not lead to any confusion.

trait Computation exposes a pointful programming API for library developers. All it’s capabilities are private[pdbp].

A program of type Kleisli[C] is referred to as a kleisli program. Note that we use a lower case k. A kleisli program is a function that transforms an argument to yield a computation result.

In a way computations generalize expressions.

When there is no danger of confusion

We often simply write

and

Recall that, in a way

Think of

Think of

Power of expression

In 2008, Conor McBride and Ross Paterson described applicatives (a.k.a. idioms) and used applicatives in Haskell in Applicative programming with effects.

In 2008, Sam Lindley, Philip Wadler and Jeremy Yallop compared the power of expression of monads, arrows and idioms in Idioms are oblivious, arrows are meticulous, monads are promiscuous.

Recall that both Program[Kleisli[C]] and Lifting[C] are mixed-in by trait Computation[C[+ _]].

Consider

package pdbp.program

import pdbp.types.kleisli.unary.kleisliUnaryTypeConstructorType._

import pdbp.computation.Lifting

private[pdbp] trait ProgramWithLifting[>-->[- _, + _]]
    extends Program[>-->]
    with Lifting[Kleisli[>-->]] {
    
    // ...

}    

where

package pdbp.types.kleisli.unary

private[pdbp] object kleisliUnaryTypeConstructorType {

  private[pdbp] type Kleisli[>-->[- _, + _]] = [+Y] => Unit >--> Y

}

Note that Kleisli[>-->], where >--> is a binary type constructor, is itself a unary type constructor.

Lifting[Kleisli[>-->]] is mixed-in by trait ProgramWithLifting[>-->[- _, + _]].

Lifting[Kleisli[>-->]] can be mixed-in by trait Program[>-->[- _, + _]]. Doing this leads to conflicting Lifting base types [+Y] => C[Y] and [+Y] => Unit => C[Y].

A computation of type Kleisli[>-->] is referred to as a kleisli computation. Note that, again, we use a lower case k. A kleisli computation is a program without arguments.

Recall that Applying[Kleisli[C]] is mixed-in by trait Computation[C[+ _]].

A kleisli program can be applied to an argument.

If we add the applying capability to programs then they have the same power of expression as computations

package pdbp.program

import pdbp.types.kleisli.unary.kleisliUnaryTypeConstructorType._

import pdbp.program.Program
import pdbp.program.Applying

import pdbp.computation.Resulting
import pdbp.computation.Binding

private[pdbp] trait ProgramWithApplying[>-->[- _, + _]]
    extends Program[>-->]
    with Applying[>-->]
    with Resulting[Kleisli[>-->]]
    with Binding[Kleisli[>-->]] {

  // ...

}

because the basic trait’s mixed-in by trait Computation are trait Resulting and trait Binding.

Elegance of use

Programming is not only about power of expression. It is also, and probably even more, about elegance of use.

Of course, elegance of use is a highly subjective concept.

Traditionally, the pointfree programming style has been considered to be elegant by some programmers and somewhat abstruse by other programmers. Luckily, the Dotty programming language comes to the rescue for the latter ones.

Dotty is a strongly typed, scalable programming language. It is possible to extend the language in a type safe way at the library level with internal domain specific languages.

By using a domain specific language for the domain of programs, program description based programming using the PDBP library can be done in an elegant way.

We refer to PDBP’s domain specific language for the domain of programs as PDBP’s programming DSL.

Our choice

PDBP goes for kleisli programs, offering

We promote that the interaction between pointfree application developers and pointful library developer should be as follows.

If an application developer thinks that the available pointfree programming capabilities are not sufficient for developing his application, then either a library developer should convince him that they are sufficient or, if they are not sufficent, a library developer should think of appropriate extra pointfree programming capabilities that are sufficient and implement them as a pointful computational capabilities and corresponding kleisli programming capabilities.

Foundations

So we go for pointfree programming using kleisli programs.

For foundations we refer to Kleisli categories.

Intrestingly, pointful programming using programs is also possible.

For foundations we refer to arrow calculus.

Introducing factorial program

Below is a factorial program written using PDBP’s programming DSL.

package examples.programs

import pdbp.program.Program

import pdbp.program.compositionOperator._

class Factorial[>-->[- _, + _]: Program]
    extends AtomicPrograms[>-->]()
    with HelperPrograms[>-->]() {

  import implicitly._

  val factorial: BigInt >--> BigInt =
    `if`(isZero) {
      one
    } `else` {
      `let` {
        subtractOne >-->
          factorial
      } `in` {
        multiply
      }
    }

}

val factorial is defined in class Factorial that is declared to implicitly have the programming capabilities declared in trait Program. The programming capabilities that are required for the definition of factorial are made available using

and

The atomic programs, isZero, one, subtractOne and multiply that factorial makes use of are defined in a much simpler way.

Informal description of factorial

Note, again, that factorial is a program description. Think of factorial as syntax, a language construct, of the library level PDBP programming DSL. There is no semantics, a meaning, associated with it at all.

Below is an informal description of the semantics of the program fragments of factorial

Note that

Also note that

Below is an informal description of the meaning of the program templates of the factorial program description above

Agreed, at first sight the pointfree factorial syntax above may seem a bit abstruse.

Agreed, we explained the semantics of the factorial syntax in a pointful way.

But, once you get used to program templates

and to program fragments like

you will, hopefully, start appreciating the power of expression and elegance of use of pointfree code.

Introducing factorial kleisli program

Below is a factorial kleisli program written using PDBP’s computation API.

package pdbp.examples.kleisliPrograms

import pdbp.computation.Computation

import pdbp.computation.bindingOperator._

class Factorial[C[+ _]: Computation]
    extends AtomicKleisliPrograms[C]()
    with HelperKleisliPrograms[C]() {

  val factorial: BigInt `=>C` BigInt = { z =>
    isZero(z) bind { b =>
      if (b) {
        one(z)
      } else {
        subtractOne(z) bind { y =>
          factorial(y) bind { x =>
            multiply((y, x))
          }
        }
      }
    }
  }

}

The code above is provided for illustration purposes only. It is not the intention to write pointful application code like this.

Besides, there is an error in the factorial definition above. Did you spot it?

Here is a correct factorial definition

  val factorial: BigInt `=>C` BigInt = { z =>
    isZero(z) bind { b =>
      if (b) {
        one(z)
      } else {
        subtractOne(z) bind { y =>
          factorial(y) bind { x =>
            multiply((z, x))
          }
        }
      }
    }
  }

The point we want to make is that pointful programming, because it is more complex than pointfree programming, is inherently more difficult. Human brains can only deal with a limited amount of complexity.

val factorial is defined in class Factorial that is declared to implicitly have the computational capabilities declared in trait Computation. The computational capabilities that are required for the definition of factorial are made available using

The atomic kleisli programs, isZero, one, subtractOne and multiply that factorial makes use of are defined in a much simpler way.

Main programs

Recall that programs have type Z >--> Y for types Z and Y.

For example: factorial has type BigInt >--> BigInt.

If

then

We also simply refer to

We also refer to

Programs are design artifacts that, among others, are combined using composition

Services are architectural artifacts that are combined using I/O

There is a tendency to keep both programs and services relatively small.

Relatively small services are often referred to as microservices.

Keeping programs relatively small is often referred to as

This quote is introduced by Erik Meijer. Erik Meijer is so famous that he does not need an introduction. I was very lucky to be able to do research with him, on monads and related stuff, at the Univeristy of Utrecht back in the ninetees.

Keeping services relatively small is often referred to as

This quote is inspired by the Unix philosophy.

FP versus PDBP

There are important differences between FP and PDBP.

Exploiting the flexibility that comes with those differences is the most important theme of the PDBP library.

Heteregeneous versus homogeneous

Programs are defined as members of classes that are declared to implicitly have the programming capabilities declared in trait Program. Those capabilities can be made available using import implicitly._. Many programming capabilities come with an operator equivalent that can be made available by import as well.

Programming with PDBP is a lot about implicitly passing around programming capabilities.

Syntax of programs

Semantics of programs

Agreed, the statements above may seem daunting at first sight, but they will become more familiar later in this document.

Let’s rephrase the statements

Strictly speaking, since trait ProgramMeaning is not a type class, the object’s that extend trait ProgramMeaning do not need to be implicit object’s, however, it is convenient that they are.

Note that factorial is a recursive PDBP program (factorial uses factorial).

It can be given both a stack based meaning and a, tail recursive, heap based meaning.

We also refer to changing the meaning of program descriptions as changing program semantics.

Extra programming capabilities

Extra programming capabilities can be added such as

Note that Program already has basic control handling capabilities (the ones of Condition).

We also refer to adding programming capabilities as extending programming syntax

I/O

Programming capabilities can be added related to

A program description involving I/O can, for example, be given

Reading and writing capabilities are, more or less, declared as

  trait Reading[Z, >-->[- _, + _]] {
    // ...

    def read: Unit >--> Z

    // ...
  }

and

  trait Writing[W: Writable, >-->[- _, + _]] {
    // ...

    def write[Y]: Y >--> Unit
  
    // ...
  }

A correct definition of Reading and Writing is described later in this document.

Note that read is a producer program and write is a consumer program. So, if program is a program of type Z >--> Y, then read >--> program >--> write[Y] is a main program.

Syntactically, read and write describe reading and writing effects in a pure way. They come into play when defining main program descriptions.

Semantically, read and write may execute reading and writing effects in an impure way. They come into play when, eventually, running main program descriptions.

Goal of the PDBP library

The goal of the PDBP library is to illustrate that program description based programming using a pointfree style in Dotty is

Summary

For some of you this introduction may have touched upon a lot of frightening stuff.

Here is the good news.

To finish, we claim that

Hopefully, the statements above sound exiting to both programmers with and programmers without a background in computer science.

Syntax of Program Descriptions

Warning

From now on this document contains a lot of code. When reading it in sequential order, you will often be confronted with code that has not been explained yet. Do not worry, the code is explained immediately below it.

Describing trait Program

Consider

package pdbp.program

trait Program[>-->[- _, + _]]
    extends Function[>-->]
    with Composition[>-->]
    with Construction[>-->]
    with Condition[>-->]
    with Aggregation[>-->]

where

trait Function[>-->[- _, + _]]

trait Composition[>-->[- _, + _]]

trait Construction[>-->[- _, + _]]

trait Condition[>-->[- _, + _]]

trait Aggregation[>-->[- _, + _]]

belong to the same package pdbp.program.

trait Program is a type class that is explained later in this document. trait Program declares and defines by default the programming capabilities of program descriptions.

We often write program instead of program description.

trait Function, trait Composition, trait Construction and trait Condition are explained later in this section. trait Aggregation is explained later in this document.

Note that we are a bit sloppy by not showing [>-->[- _, + _]].

The programming capabilities of Function, Composition and Construction correspond to arrows.

A program is an object of type Z >--> Y, where

We write

We write

At the usage site the parameter is given an argument and a result is returned.

We also write that a program transforms an argument to yield a result or that a program transforms an argument to a result.

Variance

Note that >--> is declared to be

This variance property of >--> is related to two principles that are known as

Describing trait Function

Consider

package pdbp.program

// ...

trait Function[>-->[- _, + _]] {

  def function[Z, Y]: (Z => Y) => Z >--> Y

  // ...

}

Think of function(`z=>y`) as a program that is a pure function `z=>y`. It is supposed to do nothing else than transforming an argument z of type Z to yield a result y == `z=>y`(z) of type Y.

For generic functions, we use mixed alphabetic and symbolic names within backticks, like `z=>y` to, hopefully, improve readability.

We agree that this is a somewhat unusual naming convention. We know programers who love it, we know programmers who hate it.

Let’s explain the reason of this naming convention with some examples that are special cases of Theorems for free!, as explained by Philip Wadler.

We use synonyms like `y=>y`, `x=>x`, etc. by need, when types Y, X, etc. are involved.

We could have used names identity, leftProjection, rightProjection swap and functionApplication. Sometimes we would simply run out of meaningful simple generic names.

For example, how would you name the unique generic function of type (Z && Y && X & WW) => W && X for all Z, Y, X, and W?

The main benefit of generic backtick names comes when trying to understand the type of expressions.

Note that, in a way, the argument binding expression is the most elegant one since it can, conveniently, be read from left to right.

By the way, argument binding, equivalent with function application, can be defined using an implicit class as follows

object bindingOperator {

  implicit class BindingOperator[Z](z: Z) {

    def bind[Y](`z=>y`: Z => Y) = `z=>y` apply z

  }

}

When dealing with more complex expressions, having nested sub-expressions, the usefulness of generic backtick names becomes even more apparent.

Let’s define some pure functions.

package pdbp.program

// ...

import pdbp.utils.functionUtils._

// ...

trait Function[>-->[- _, + _]] {

  // ...

  def `z>-->z`[Z]: Z >--> Z =
    function(`z=>z`) 

  // ...   
  
} 

We defined `z>-->z` in terms of function and `z=>z` where

is the function you expect.

package pdbp.utils

object functionUtils {

  def `z=>z`[Z]: Z => Z = { z =>
    z
  }

  // ...

} 

For programs, we use generic backtick names like `z>-->y` to, hopefully, improve readability.

You may have doubts about the usefulness of a trivial program like`z>-->z`.
It turns out that, when defining composite programs, obtained by substituting program component arguments for program component parameters of program templates, using `z>-->z` for one or more of those program component arguments results in interesting composite programs of their own. Naturally, those composite programs have simpler types than the fully generic ones.

In what follows we also refer to programs function(`z=>y`), that, essentially, are pure functions, as atomic programs. It is up to you to define the granularity of atomic programs.

factorial as function

Recall the definition of factorial

  val factorial: BigInt >--> BigInt =
    `if`(isZero) {
      one
    } `else` {
      `let` {
        subtractOne >-->
          factorial
      } `in` {
        multiply
      }
    }

Below is another definition of factorial.

package examples.programs

import examples.utils.functionUtils._

import pdbp.program.Function

class FactorialAsFunction[>-->[- _, + _]: Function] {

  import implicitly._

  val factorialFunction: BigInt => BigInt = { i =>
    if (isZeroFunction(i)) {
      oneFunction(i)
    } else {
      multiplyFunction(i, (subtractOneFunction andThen factorialFunction)(i))
    }
  }

  val factorial: BigInt >--> BigInt = function(factorialFunction)

}

where

package examples.utils

import pdbp.types.product.productType._

object functionUtils {

  val isZeroFunction: BigInt => Boolean = { i =>
    i == 0
  }

  val subtractOneFunction: BigInt => BigInt = { i =>
    i - 1
  }

  val multiplyFunction: (BigInt && BigInt) => BigInt = { (i, j) =>
    i * j
  }

  def oneFunction[Z]: Z => BigInt = { z =>
    1
  } 

  // ...

}

where

package pdbp.types.product

object productType {

  type &&[+Z, +Y] = Tuple2[Z, Y]

}

Since the atomic program function(factorialFunction) is maximally coarse-grained this gives us essentially no flexibility to give a meaning to factorial.

Describing trait Composition

Consider

package pdbp.program

trait Composition[>-->[- _, + _]] {

  def seqCompose[Z, Y, X](`z>-->y`: Z >--> Y, `y>-->x`: => Y >--> X): Z >--> X

}

Think of seqCompose as a program template and of `z>-->y` and `y>-->x` as program fragment parameters (a.k.a. program component parameters or simply program parameters). Once those program fragment parameters have been given program fragment arguments (a.k.a. program component arguments or simply program arguments) we obtain a composite program.

seqCompose(`z>-->y`, `y>-->x`) is the sequential composition of `z>-->y` and `y>-->x`.

If the program `z>-->y` transforms an argument of type Z to yield a result of type Y, then that result serves as an argument for the subsequent program `y>-->x` which transforms it to yield a result of type X.

Note that `y>-->x` is a call-by-name parameter. If program `z>-->y` fails to yield a result, then program `y>-->x` is not used.

Consider

package pdbp.program

object compositionOperator {

  implicit class CompositionOperator[>-->[- _, + _]: Composition, -Z, +Y](
      `z>-->y`: Z >--> Y) {

    import implicitly._

    def >-->[X](`y>-->x`: => Y >--> X) = {
      seqCompose(`z>-->y`, `y>-->x`)
    }

  }

}

The binary type constructor >--> is declared to implicitly have the programming capability seqCompose that is declared in the type class trait Composition. The operator >--> is defined in terms of this programming capability.

The definition of the member >--> uses implicitly, an abbreviation of implicitly[Composition[>-->]], that is available as an evidence having the seqCompose capability of Composition. Instead of using import implicitly._ and seqCompose we can also use implicitly.seqCompose.

/* ... */ >--> /* ... */ is a first example where Dotty comes to the rescue to spice pointfree programming with some domain specific language flavor.

It should not come as a surprise that

Describing trait Construction

Consider

package pdbp.program

import pdbp.types.product.productType._

trait Construction[>-->[- _, + _]] {
  this: Function[>-->] & Composition[>-->] =>

  def product[Z, Y, X](`z>-->y`: Z >--> Y,
                       `z>-->x`: => Z >--> X): Z >--> (Y && X) =
    product(`z>-->y`, `z>-->x`, `(y&&x)>-->(y&&x)`)

  def product[Z, Y, X, W](`z>-->y`: Z >--> Y,
                          `z>-->x`: => Z >--> X,
                          `(y&&x)>-->w`: => (Y && X) >--> W): Z >--> W =
    seqCompose(product(`z>-->y`, `z>-->x`), `(y&&x)>-->w`)

  def and[Z, X, Y, W](`z>-->x`: Z >--> X,
                      `y>-->w`: => Y >--> W): (Z && Y) >--> (X && W) =
    product(seqCompose(`(z&&y)>-->z`, `z>-->x`), seqCompose(`(z&&y)>-->y`, `y>-->w`))

  def left[Z, X, Y](`z>-->x`: Z >--> X): (Z && Y) >--> (X && Y) =
    and(`z>-->x`, `y>-->y`)

  def right[Z, W, Y](`y>-->w`: Y >--> W): (Z && Y) >--> (Z && W) =
    and(`z>-->z`, `y>-->w`) 

  def `let`[Z, Y, X](`z>-->y`: Z >--> Y): In[Z, Y, X] =
    new In[Z, Y, X] {
      def `in`(`(z&&y)>-->x`: => (Z && Y) >--> X): Z >--> X =
        seqCompose(product(`z>-->z`, `z>-->y`), `(z&&y)>-->x`)
    }

  trait In[Z, Y, X] {
    def `in`(`(z&&y)>-->x`: => (Z && Y) >--> X): Z >--> X
  }

}

where

are the programs you expect.

package pdbp.program

// ...

import pdbp.types.product.productType._

// ...

import pdbp.utils.productUtils._

// ...

trait Function[>-->[- _, + _]] {

  // ...

  def `(y&&x)>-->(y&&x)`[Y, X]: (Y && X) >--> (Y && X) =
    function(`(y&&x)=>(y&&x)`)

  def `(z&&y)>-->z`[Z, Y]: (Z && Y) >--> Z =
    function(`(z&&y)=>z`)

  def `(z&&y)>-->y`[Z, Y]: (Z && Y) >--> Y =
    function(`(z&&y)=>y`)

  def `y>-->y`[Y]: Y >--> Y =
    function(`y=>y`)

  // ...

}

where

package pdbp.utils

import pdbp.types.product.productType._

object productUtils {

  // ...

  def `(y&&x)=>(y&&x)`[Y, X]: (Y && X) => (Y && X) = { `y&&x` =>
    `y&&x`
  }

  def `(z&&y)=>z`[Z, Y]: (Z && Y) => Z = { (z, _) =>
    z
  }

  def `(z&&y)=>y`[Z, Y]: (Z && Y) => Y = { (_, y) =>
    y
  }

  def `y=>y`[Y]: Y => Y = { y =>
    y
  }  

  // ...

}

Think of product as a program template and of `z>-->y` and `z>-->x` as program parameters. Once those program parameters have been given program arguments we obtain a composite program.

product(`z>-->y`, `z>-->x`) yields a result constructed from the results yielded by `z>-->y` and `z>-->x`.

If the program `z>-->y` transforms an argument of type Z to yield a result of type Y, and the program `z>-->y` transforms that argument to yield a result of type Y, then the program product(`z>-->y`, `z>-->x`) transforms that argument to yield a result of type Y && X.

Many arguments resp. results

Programs are objects of type Z >--> Y.

It may look as if programs can have only one argument resp. result.

This is the way the PDBP library deals with zero arguments resp. results.

This is the way the PDBP library deals with two arguments resp. results.

The PDBP library deals with many arguments resp. results using nested tuples

Note that && associates to the left, so, for example, the triple type Z && Y && X is the same type as the nested tuple type (Z && Y) && X.

Describing trait Construction continued

trait Construction has three other members

The main difference between `let` { /* ... */ } `in` { /* ... */ } and /* ... */ >--> /* ... */ is that the former does not loose the original argument of type Z while the letter does.

Note that

Note that the definitions are left biased. Their first parameter is a by-value parameter. Their second parameter is a by-name parameter.

`let` { /* ... */ } `in` { /* ... */ } is a second example where Dotty comes to the rescue to spice pointfree programming with some domain specific language flavor.

trait Construction has two other member

Consider

object constructionOperators {

  implicit class ConstructionOperators[>-->[- _, + _]: Construction, -Z, +Y](
      `z>-->y`: Z >--> Y) {

    import implicitly._   

    def &[ZZ <: Z, X](`zz>-->x`: => ZZ >--> X) =
      product(`z>-->y`, `zz>-->x`)

    def &&[X, W](`x>-->w`: => X >--> W) =
      and(`z>-->y`, `x>-->w`)

  }

}

The type constructor >--> is declared to implicitly have the programming capabilities product and and that are declared or default defined in the type class trait Construction. The operators & and && are defined in terms of those programming capabilities.

The definitions use implicitly, an abbreviation of implicitly[Construction[>-->]], that is available as an evidence having the product and and capabilities of Construction.

/* ... */ & /* ... */ and /* ... */ && /* ... */ are a third and fourth example where Dotty comes to the rescue to spice pointfree programming with some domain specific language flavor.

It should not come as a surprise that

About the power of expression of `let` { ... } `in` { ... }

product[Z, Y, X] can be defined in terms of `let` { ... } `in` { ... }.

package pdbp.examples

import pdbp.types.product.productType._

import pdbp.utils.productUtils._

import pdbp.program.Function
import pdbp.program.Composition
import pdbp.program.Construction

import pdbp.program.compositionOperator._

trait ProductInTermsOfLetAndIn[
    >-->[- _, + _]: Function: Composition: Construction] {

  val implicitFunction = implicitly[Function[>-->]]
  val implicitConstruction = implicitly[Construction[>-->]]

  import implicitFunction._
  import implicitConstruction._

  def product[Z, Y, X](`z>-->y`: Z >--> Y,
                       `z>-->x`: => Z >--> X): Z >--> (Y && X) =
    `let` {
      `z>-->y`
    } `in` {
      `let` {
        `(z&&y)>-->z` >--> `z>-->x`
      } `in` {
        `(z&&y&&x)>-->(y&&x)`
      }
    }

}

where

is the program you expect.

package pdbp.program

// ...

trait Function[>-->[- _, + _]] {

  // ...

  def `(z&&y&&x)>-->(y&&x)`[Z, Y, X]: (Z && Y && X) >--> (Y && X) =
    function(`(z&&y&&x)=>(y&&x)`)    

  // ...

}

where

package pdbp.utils

// ...

object productUtils {

  // ...

  def `(z&&y&&x)=>(y&&x)`[Z, Y, X]: (Z && Y && X) => (Y && X) = {
    case ((_, y), x) => (y, x)
  }

  // ...

}

The definition of product is an example of a recurring theme of the PDBP library.

Defining a program as an application developer, or programming capability as a library developer, often boils down to a “getting the types right” puzzle.

Often there is only one meaningful way to get them right. Let’s have a look at some of the details of the typing puzzle for this definition.

The outer `let` creates, using `z>-->y`, a new argument of type Y for the outer `in` which, as a consequence, has an argument of type Z && Y available, representing two arguments, one of type Z and one of type Y.

The inner `let` of the outer `in` creates, using `(z&&y)>-->z` >--> `z>-->x`, the composition of `(z&&y)>-->z` and `z>-->x`, a new argument of type X for the inner `in` of the outer `in` which, as a consequence, has an argument of type Z && Y && X available, representing three arguments, one of type Z, one of type Y, and one of type X.

The inner `in` in the outer `in` simply gets rid of the original argument of type Z using `(z&&y&&x)>-->(y&&x)`.

Note that generic backtick names, hopefully, help to understand the typing puzzle.

For example

One challenge that comes with pointfree programming is getting the necessary arguments out of all available arguments. The program `(z&&y&&x)>-->(y&&x)` above gets a y and an x out of a z, a y and an x.

One way to deal with this challenge is to keep programs, and therefore, the arguments and results that come with them, relatively small. After all, small program components can be combined to obtain larger composite programs by substituting them into program templates.

Describing trait Condition

Consider

package pdbp.program

import pdbp.types.product.productType._
import pdbp.types.sum.sumType._

import pdbp.utils.productUtils._
import pdbp.utils.sumUtils._

trait Condition[>-->[- _, + _]] {
  this: Function[>-->] & Composition[>-->] & Construction[>-->] =>

  def sum[Z, Y, X](`y>-->z`: => Y >--> Z,
                   `x>-->z`: => X >--> Z): (Y || X) >--> Z =
    sum(`(y||x)>-->(y||x)`, `y>-->z`, `x>-->z`)

  def sum[Z, Y, X, W](`w>-->(y||x)`: W >--> (Y || X),
                      `y>-->z`: => Y >--> Z,
                      `x>-->z`: => X >--> Z): W >--> Z =
    seqCompose(`w>-->(y||x)`, sum(`y>-->z`, `x>-->z`))

  def or[Z, X, Y, W](`x>-->z`: => X >--> Z,
                     `w>-->y`: => W >--> Y): (X || W) >--> (Z || Y) =
    sum(seqCompose(`x>-->z`, `z>-->(z||y)`), seqCompose(`w>-->y`, `y>-->(z||y)`))

  def `if`[W, Z](`w>-->b`: W >--> Boolean): Apply[W, Z] =
    new Apply[W, Z] {
      override def apply(`w>-t->z`: => W >--> Z): Else[W, Z] =
        new Else[W, Z] {
          override def `else`(`w>-f->z`: => W >--> Z): W >--> Z =
            sum(`let`(`w>-->b`) `in` `(w&&b)>-->(w||w)`, `w>-t->z`, `w>-f->z`)
        }
    }

  trait Apply[W, Z] {
    def apply(`w>-t->z`: => W >--> Z): Else[W, Z]
  }

  trait Else[W, Z] {
    def `else`(`w>-f->z`: => W >--> Z): W >--> Z
  }

}

where

package pdbp.types.sum

object sumType {

  case class Left[+Z](z: Z)

  case class Right[+Y](y: Y)

  type ||[+Z, +Y] = Left[Z] | Right[Y]

}

and where

are the programs you expect.

Agreed, `(w&&b)>-->(w||w)` is one of the two programs you expect. It is the one where true corresponds to Left and false corresponds to Right.

package pdbp.program

// ...

import pdbp.types.sum.sumType._

// ...

import pdbp.utils.sumUtils._
import pdbp.utils.productAndSumUtils._

trait Function[>-->[- _, + _]] {

  // ...

  def `(y||x)>-->(y||x)`[Y, X]: (Y || X) >--> (Y || X) =
    function(`(y||x)=>(y||x)`)

  def `z>-->(z||y)`[Z, Y]: Z >--> (Z || Y) =
    function(`z=>(z||y)`)

  def `y>-->(z||y)`[Z, Y]: Y >--> (Z || Y) =
    function(`y=>(z||y)`)

  def `(w&&b)>-->(w||w)`[W]: (W && Boolean) >--> (W || W) =
    function(`(w&&b)=>(w||w)`)

  // ...

}

where

package pdbp.utils

import pdbp.types.sum.sumType._

object sumUtils {

  // ...

  def `(y||x)=>(y||x)`[Y, X]: (Y || X) => (Y || X) = { `y||x` =>
    `y||x`
  }

  def `z=>(z||y)`[Z, Y]: Z => (Z || Y) = { z =>
    Left(z)
  }

  def `y=>(z||y)`[Z, Y]: Y => (Z || Y) = { y =>
    Right(y)
  }

  // ...

}

and where

package pdbp.utils

import pdbp.types.product.productType._
import pdbp.types.sum.sumType._

object productAndSumUtils {

  def foldBoolean[Z](tz: => Z, fz: => Z): Boolean => Z = {
    case true  => tz
    case false => fz
  }

  def `(w&&b)=>(w||w)`[W]: (W && Boolean) => (W || W) = { (w, b) =>
    foldBoolean[W || W](Left(w), Right(w))(b)
  }

}

Think of sum as a program template and of `y>-->z` and `x>-->z` as program parameters. Once those program parameters have been given program arguments we obtain a composite program.

sum(`y>-->z`, `x>-->z`) uses a “left or right” condition to let either `y>-->z` or `x>-->z` take over control.

Describing trait Condition continued

trait Condition has three other members

Note that

`if`(/* ... */) { /* ... */ } `else` { /* ... */ } is a fifth example where Dotty comes to the rescue to spice pointfree programming with some domain specific language flavor.

About the power of expression of `if`(...) { ... } `else` { ... }

sum[Z, Y, X] can be defined in terms of `if`(...) { ... } `else` { ... }.

package pdbp.examples

import pdbp.types.sum.sumType._

import pdbp.utils.sumUtils._

import pdbp.program.Function
import pdbp.program.Composition
import pdbp.program.Condition

import pdbp.program.compositionOperator._

trait SumInTermsOfIfAndElse[>-->[- _, + _]: Function: Composition: Condition] {
  val implicitFunction = implicitly[Function[>-->]]
  val implicitCondition = implicitly[Condition[>-->]]

  import implicitFunction._
  import implicitCondition._

  def sum[Z, Y, X](`y>-->z`: => Y >--> Z,
                   `x>-->z`: => X >--> Z): (Y || X) >--> Z =
    `if`(`(y||x)>-->b`) {
      `(y||x)>-->y` >--> `y>-->z`
    } `else` {
      `(y||x)>-->x` >--> `x>-->z`
    }

}

where

are the programs you expect.

Agreed, `(y||x)>-->b` is one of the two programs you expect. It is the one where true corresponds to Left and false corresponds to Right.

package pdbp.program

// ...

trait Function[>-->[- _, + _]] {

  // ...

  def `(y||x)>-->y`[Y, X]: (Y || X) >--> Y =
    function(`(y||x)=>y`)

  def `(y||x)>-->x`[Y, X]: (Y || X) >--> X =
    function(`(y||x)=>x`)    

  def `(y||x)>-->b`[Y, X]: (Y || X) >--> Boolean =
    function(`(y||x)=>b`)

  // ...

}

where

package pdbp.utils

// ...

object sumUtils {

  // ...

  def foldSum[Z, Y, X](`y=>z`: => Y => Z, `x=>z`: => X => Z): (Y || X) => Z = {
    case Left(y) =>
      `y=>z`(y)
    case Right(x) =>
      `x=>z`(x)
  }

  def `(y||x)=>y`[Y, X]: (Y || X) => Y =
    foldSum[Y, Y, X](y => y, _ => ???)

  def `(y||x)=>x`[Y, X]: (Y || X) => X =
    foldSum[X, Y, X](_ => ???, x => x)  

  def `(y||x)=>b`[Y, X]: (Y || X) => Boolean =
    foldSum[Boolean, Y, X](_ => true, _ => false)
    
}

Note that, again, generic backtick names, hopefully, help to understand the typing puzzle. For example

factorial revisited

Below is, again, the full code for factorial.

package examples.programs

import pdbp.program.Program

import pdbp.program.compositionOperator._

class Factorial[>-->[- _, + _]: Program]
    extends AtomicPrograms[>-->]()
    with HelperPrograms[>-->]() {

  import implicitly._

  val factorial: BigInt >--> BigInt =
    `if`(isZero) {
      one
    } `else` {
      `let` {
        subtractOne >-->
          factorial
      } `in` {
        multiply
      }
    }

}

where

package examples.programs

import pdbp.types.product.productType._

import pdbp.program.Function

trait AtomicPrograms[>-->[- _, + _]: Function] extends HelperPrograms[>-->] {

  val isZero: BigInt >--> Boolean =
    isZeroHelper

  val subtractOne: BigInt >--> BigInt =
    subtractOneHelper

  val multiply: (BigInt && BigInt) >--> BigInt =
    multiplyHelper

  def one[Z]: Z >--> BigInt =
    oneHelper

  // ...  

}

and

package examples.programs

import pdbp.types.product.productType._

import pdbp.program.Function

import examples.utils.functionUtils._

trait HelperPrograms[>-->[- _, + _]: Function] {

  import implicitly._

  val isZeroHelper: BigInt >--> Boolean =
    function(isZeroFunction)

  val subtractOneHelper: BigInt >--> BigInt =
    function(subtractOneFunction)

  val multiplyHelper: (BigInt && BigInt) >--> BigInt =
    function(multiplyFunction)

  def oneHelper[Z]: Z >--> BigInt =
    function(oneFunction)

  // ...  

}

Since the atomic programs, isZero, one, subtractOne and multiply used by factorial are maximally fine-grained this gives us a lot of flexibility to give a meaning to factorial.

factorial top-down

Below is top-down code for factorial

package examples.programs

import pdbp.program.Program

class FactorialTopDown[>-->[- _, + _]: Program]
    extends AtomicPrograms[>-->]()
    with HelperPrograms[>-->]() {

  import implicitly._

  import pdbp.program.compositionOperator._

  val factorial: BigInt >--> BigInt =
    `if`(isZero) {
      one
    } `else` {
      factorialOfNonZero
    }

  val factorialOfNonZero: BigInt >--> BigInt =
    `let` {
      subtractOneAndThenFactorial
    } `in` {
      multiply
    }

  val subtractOneAndThenFactorial: BigInt >--> BigInt =
    subtractOne >-->
      factorial

}

factorial above uses

factorialOfNonZero above uses

subtractOneAndThenFactorial above uses

Describing mainFactorial

Consider

package examples.mainPrograms

import pdbp.program.Program

import pdbp.program.compositionOperator._

import examples.programs.Factorial

trait MainFactorial[>-->[- _, + _]: Program] {

  private object factorialObject extends Factorial[>-->]

  import factorialObject.factorial

  val producer: Unit >--> BigInt

  val consumer: BigInt >--> Unit

  lazy val mainFactorial: Unit >--> Unit =
    producer >-->
      factorial >-->
      consumer

}

trait MainFactorial defines lazy val mainFactorial using abstract members producer and consumer. mainFactorial is a program of type Unit >--> Unit. Programs of type Unit >--> Unit are referred to as main programs.

Note that mainFactorial is a main program description. It is a PDBP library level syntactic construct.

Describing trait Computation

Describing trait Computation

Consider

package pdbp.computation

import pdbp.types.kleisli.kleisliBinaryTypeConstructorType.Kleisli

import pdbp.program.Program

import pdbp.program.Applying

private[pdbp] trait Computation[C[+ _]]
    extends Resulting[C]
    with Binding[C]
    with Lifting[C]
    with Sequencing[C]
    with Program[Kleisli[C]]
    with Applying[Kleisli[C]] {

  // ...

}

where

private[pdbp] trait Resulting[C]

private[pdbp] trait Binding[C]

private[pdbp] trait Lifting[C]

private[pdbp] trait Sequencing[C]

belong to the same package pdbp.computation.

and where

package pdbp.types.kleisli

private[pdbp] object kleisliBinaryTypeConstructorType {

  private[pdbp] type Kleisli[C[+ _]] = [-Z, + Y] => Z => C[Y]

}

trait Computation is a type class that is explained later in this document. trait Computation declares or defines by default the computational capabilities of computation descriptions.

We often write computation instead of computation description.

Note that we are a bit sloppy by not showing [C[+ _]].

trait Resulting, trait Binding and trait Lifting are explained later in this section. trait Sequencing, related to trait Aggregation, is explained later in this document. trait Applying is explained later in this document.

Note that, again, we are a bit sloppy by not showing [C] and Kleisli[C].

The computational capabilities of Resulting and Binding correspond to monads.

A computation is an object of type C[Z], where

We write

We write

We also write that a computation yields a result or that a computation has a result.

PDBP library users versus PDBP library developers

Note that all computational capabilities are defined as private [pdbp].

We do not want to expose the pointful computational capabilies to the users of the PDBP library. We only expose pointfree programming capabilities to the users of the PDBP library. It is convenient to have pointful computational capabilies available for the developers of the PDBP library. It is also simpler (not necessarily easier, though) to define object’s that extend Computation, since Computation has less declared capabilities to define than Program.

Variance

Note that C is

This variance property of C is related to two principles that are known as

Describing trait Resulting

Consider

package pdbp.computation

private[pdbp] trait Resulting[C[+ _]] {

  private[pdbp] def result[Z]: Z => C[Z]

}

Think of result(ez) as a computation that is a pure expression ez. Executing it is supposed to do nothing else than evaluating the expression ez to a yield a result of type Z.

In what follows we also refer to computations result(ez), that, essentially, are pure expression, as atomic computations. It is up to you to define the granularity of atomic computations.

Describing trait Binding

Consider

package pdbp.computation

private[pdbp] trait Binding[C[+ _]] {

  private[pdbp] def bind[Z, Y](cz: C[Z], `z=>cy`: => Z => C[Y]): C[Y]

}

Think of `z=>cy` as a computation execution continuation or, simply, computation continuation, and of cz as a computation fragment or computation component or, simply, sub-computation).

If we start executing the sub-computation cz, then, once its result has been bound to the computation continuation z=>cy, we can continue executing the composite computation bind(cz, `z=>cy`).

If the sub-computation cz yields a result of type Z, then that result serves as an argument for the computation continuation z=>cy, which transforms it to a computation that yields a result of type Y.

Consider

package pdbp.computation

private[pdbp] object bindingOperator {

  implicit class bindingOperator[C[+ _] : Binding, -Z, ZZ <: Z](czz: C[ZZ]) {

    private[pdbp] def bind[Y](`zz=>cy`: ZZ => C[Y]): C[Y] =
      implicitly.bind(czz, `zz=>cy`)
  }

}

Warning about the next sections describing kleisli programs

The idea behind PDBP is to promote pointfree programming. The computation examples described in the next sections use pointful programming and are only provided for illustration purposes.

Note that the package of the examples is pdbp.examples.

sumOfSquares as kleisli program

Below is the code for sumOfSquares.

package pdbp.examples.kleisliPrograms

import pdbp.types.product.productType._

import pdbp.computation.Computation

import pdbp.computation.bindingOperator._

import pdbp.types.product.productType._

import pdbp.computation.Computation

import pdbp.computation.bindingOperator._

class SumOfSquares[C[+ _]: Computation]
    extends AtomicKleisliPrograms[C]()
    with HelperKleisliPrograms[C]() {

  import implicitly._

  private type `=>C` = [-Z, +Y] => Z => C[Y]

  val sumOfSquares: (Double && Double) `=>C` Double = { (z, y) =>
    square(z) bind { zSquare =>
      square(y) bind { ySquare =>
        sum(zSquare, ySquare) bind { zSquare_plus_ySquare =>
          result(zSquare_plus_ySquare)
        }
      }
    }
  }

}

where

package pdbp.examples.kleisliPrograms
package pdbp.examples.kleisliPrograms

import pdbp.types.product.productType._

import pdbp.computation.Resulting

trait AtomicKleisliPrograms[C[+ _]: Resulting]
    extends HelperKleisliPrograms[C] {

  val square: Double `=>C` Double = squareHelper

  val sum: (Double && Double) `=>C` Double = sumHelper

  // ...

}

where

package pdbp.examples.kleisliPrograms

import pdbp.types.product.productType._

import pdbp.computation.Resulting

import pdbp.examples.utils.functionUtils._

trait HelperKleisliPrograms[C[+ _]: Resulting] {

  import implicitly._

  type `=>C` = [-Z, +Y] => Z => C[Y]

  val squareHelper: Double `=>C` Double = squareFunction andThen result

  val sumHelper: (Double && Double) `=>C` Double = sumFunction andThen result

  // ...

}

where

package pdbp.examples.utils.functionUtils._

object functionUtils {

  val squareFunction: Double => Double = { z =>
    z * z
  }

  val sumFunction: Double && Double => Double = { (z, y) =>
    z + y
  } 

  // ... 

}

Since the atomic kleisli programs square and sum used by sumOfSquares are maximally fine-grained this gives us a lot of flexibility to give a meaning to sumOfSquares.

sumOfSquares as expression

Below is other code for sumOfSquares.

package pdbp.examples.kleisliPrograms

import pdbp.types.product.productType._

import pdbp.computation.Resulting

import pdbp.examples.utils.functionUtils._

class SumOfSquaresAsExpression[C[+ _]: Resulting] {

  import implicitly._

  private type `=>C` = [-Z, +Y] => Z => C[Y]

  val sumOfSquaresFunction: Double && Double => Double = { (z, y) =>
    sumFunction(squareFunction(z), squareFunction(y))
  }

  val sumOfSquares: (Double && Double) `=>C` Double =
    sumOfSquaresFunction andThen result

}

Since the atomic kleisli program sumOfSquares is maximally coarse-grained this gives us almost no flexibility to give a meaning to sumOfSquares.

factorial as kleisli program

Below is the code for factorial.

package pdbp.examples.kleisliPrograms

import pdbp.computation.Computation

class Factorial[C[+ _]: Computation]
    extends AtomicKleisliPrograms[C]()
    with HelperKleisliPrograms[C]() {

  import pdbp.computation.bindingOperator._

  val factorial: BigInt `=>C` BigInt = { z =>
    isZero(z) bind { b =>
      if (b) {
        one(z)
      } else {
        subtractOne(z) bind { y =>
          factorial(y) bind { x =>
            multiply((z, x))
          }
        }
      }
    }
  }

}

where

package pdbp.examples.kleisliPrograms

import pdbp.computation.Computation

import pdbp.computation.bindingOperator._

class Factorial[C[+ _]: Computation]
    extends AtomicKleisliPrograms[C]()
    with HelperKleisliPrograms[C]() {

  val factorial: BigInt `=>C` BigInt = { z =>
    isZero(z) bind { b =>
      if (b) {
        one(z)
      } else {
        subtractOne(z) bind { y =>
          factorial(y) bind { x =>
            multiply((z, x))
          }
        }
      }
    }
  }

}

where

package pdbp.examples.kleisliPrograms

// ...

trait AtomicKleisliPrograms[C[+ _]: Resulting]
    extends HelperKleisliPrograms[C] {

  // ...  

  val isZero: BigInt `=>C` Boolean = isZeroHelper

  val subtractOne: BigInt `=>C` BigInt = subtractOneHelper

  val multiply: (BigInt && BigInt) `=>C` BigInt = multiplyHelper

  def one[Z]: Z `=>C` BigInt = oneHelper

}

where

package pdbp.examples.kleisliPrograms

// ...

trait HelperKleisliPrograms[C[+ _]: Resulting] {

  // ...

  val isZeroHelper: BigInt `=>C` Boolean = isZeroFunction andThen result

  val subtractOneHelper
    : BigInt `=>C` BigInt = subtractOneFunction andThen result

  val multiplyHelper
    : (BigInt && BigInt) `=>C` BigInt = multiplyFunction andThen result

  def oneHelper[Z]: Z `=>C` BigInt = oneFunction andThen result

}

where

package pdbp.examples.utils.functionUtils._

// ...

object functionUtils {

  // ...

  val isZeroFunction: BigInt => Boolean = { i =>
    i == 0
  }

  val subtractOneFunction: BigInt => BigInt = { i =>
    i - 1
  }

  val multiplyFunction: (BigInt && BigInt) => BigInt = { (i, j) =>
    i * j
  }

  def oneFunction[Z]: Z => BigInt = { z =>
    1
  }

}

Since the atomic kleisli programs , isZero and subtractOne, multiply and one used by factorial are maximally fine-grained this gives us a lot of flexibility to give a meaning to factorial.

main kleisli programs

Recall that kleisli programs have type Z => C[Y], or Z `=>C` Y, using an appropriate type synonym, for types Z and Y.

For example: sumOfSquares has type (Double && Double) `=>C` Double.

If

kleisliProducer is a producer kleisli program of type Unit `=>C` Z, kleisliProgram is a kleisli program of type Z `=>C` Y, kleisliConsumer is a consumer kleisli program of type Y `=>C` Unit, then

{ u => kleisliProducer(u) bind { z => kleisliProgram(z) bind { y => kleisliConsumer(y) } } } is a main kleisli program of type Unit `=>C` Unit.

We also simply refer to

Note that the code for a main kleisli program is more complex (and, as a consequence, imho, less elegant) than the code for a main program.

Describing mainSumOfSquares

Consider

package pdbp.examples.mainKleisliPrograms

import pdbp.types.product.productType._

import pdbp.computation.Computation

import pdbp.examples.kleisliPrograms.SumOfSquares

trait MainSumOfSquares[C[+ _]: Computation] {

  import pdbp.computation.bindingOperator._

  private object sumOfSquaresObject extends SumOfSquares[C]

  import sumOfSquaresObject.sumOfSquares

  type `=>C` = [-Z, +Y] => Z => C[Y]

  val producer: Unit `=>C` (Double && Double)

  val consumer: Double `=>C` Unit

  lazy val mainSumOfSquares: Unit `=>C` Unit = { u =>
    producer(u) bind { (z, y) =>
      sumOfSquares(z, y) bind { x =>
        consumer(x)
      }
    }
  }

}

trait MainSumOfSquares defines lazy val mainSumOfSquares using abstract members producer and consumer.

Describing mainFactorial

Consider

package pdbp.examples.mainKleisliPrograms

import pdbp.computation.Computation

import pdbp.examples.kleisliPrograms.Factorial

trait MainFactorial[C[+ _]: Computation] {

  import pdbp.computation.bindingOperator._

  private object factorialObject extends Factorial[C]

  import factorialObject.factorial

  type `=>C` = [-Z, +Y] => Z => C[Y]

  val producer: Unit `=>C` BigInt

  val consumer: BigInt `=>C` Unit

  lazy val mainFactorial: Unit `=>C` Unit = { u =>
    producer(u) bind { z =>
      factorial(z) bind { y =>
        consumer(y)
      }
    }
  }

}

trait MainFactorial defines lazy val mainFactorial using abstract members producer and consumer.

Describing trait Lifting

The members result and bind are the basic members of trait Computation. It turns out that there are many other useful members that can be defined using them.

Consider

package pdbp.computation

private[pdbp] trait Lifting[C[+ _]]
    extends ObjectLifting[C]
    with FunctionLifting[C]
    with OperatorLifting[C]

where

private[pdbp] trait ObjectLifting[C]

private[pdbp] trait FunctionLifting[C]

private[pdbp] trait OperatorLifting[C]

belong to the same package pdbp.computation.

trait Lifting is a type class that is explained later in this section. trait Lifting declares the lifting capabilities of computations.

Note that we are a bit sloppy by not showing [C[+ _]].

The lifting capabilities of Lifting correspond to applicatives (a.k.a. idioms).

trait ObjectLifting, trait FunctionLifting and trait OperatorLifting are explained later in this section.

Note that, again, we are a bit sloppy by not showing [C].

Describing trait ObjectLifting

Consider

package pdbp.computation

private[pdbp] trait ObjectLifting[C[+ _]] {

  private[pdbp] def liftObject[Z](z: Z): C[Z] =
    lift0(z)

  private[pdbp] def lift0[Z]: Z => C[Z] =
    liftObject

}

liftObject and it’s alias lift0 are members that lift an object z of type Z to a computation of type C[Z] with result z. The 0 in lift0 stands for lifting zero parameters.

Describing trait FunctionLifting

Consider

package pdbp.computation

private[pdbp] trait FunctionLifting[C[+ _]] {

  private[pdbp] def liftFunction[Z, Y](`z=>y`: Z => Y): C[Z] => C[Y] =
    lift1(`z=>y`)

  private[pdbp] def lift1[Z, Y]: (Z => Y) => C[Z] => C[Y] =
    lift1

}

liftFunction and it’s alias lift1 are members that lift an object-level function to a computation-level function. The 1 in lift1 stands for lifting one parameter.

Describing trait OperatorLifting

Consider

import pdbp.types.product.productType._

private[pdbp] trait OperatorLifting[C[+ _]] {

  private[pdbp] def liftOperator[Z, Y, X](
      `(z&&y)=>x`: (Z && Y) => X): (C[Z] && C[Y]) => C[X] =
    lift2(`(z&&y)=>x`)

  private[pdbp] def lift2[Z, Y, X]: ((Z && Y) => X) => (C[Z] && C[Y]) => C[X] =
    liftOperator

}

liftOperator and it’s alias lift2 are members that lift an object-level operator to a computation-level operator. The 2 in lift2 stands for lifting two parameters.

Describing trait Lifting revisited

Consider

package pdbp.computation

import pdbp.types.product.productType._

import pdbp.utils.productUtils._

private[pdbp] trait Lifting[C[+ _]]
    extends ObjectLifting[C]
    with FunctionLifting[C]
    with OperatorLifting[C] {

  private[pdbp] def lift3[Z, Y, X, W]
    : ((Z && Y && X) => W) => (C[Z] && C[Y] && C[X]) => C[W] =
    `((z&&y)&&x)=>w` =>
      `((cz&&cy)=>c(z&&y)))=>((cz&&cy)&&cx)=>c(z&&y)&&cx`(
        lift2(`(z&&y)=>(z&&y)`)) andThen lift2(`((z&&y)&&x)=>w`)

  // and so on ...

  private[pdbp] def liftedAnd[Z, Y]: (C[Z] && C[Y]) => C[Z && Y] =
    liftOperator(`(z&&y)=>(z&&y)`)

  private[pdbp] def liftedApply[Z, Y]: (C[Z => Y] && C[Z]) => C[Y] =
    liftOperator(`((z=>y)&&z)=>y`)

  private[pdbp] override def lift1[Z, Y]: (Z => Y) => C[Z] => C[Y] = {
    `z=>y` => cz =>
      lift2(`((z=>y)&&z)=>y`)(lift0(`z=>y`), cz)

  }

}

Lifting does not stop with objects (lift0), unary functions (lift1) and binary functions (lift2). It is possible to define lift3, for lifting ternary functions and so on … .

where

is the program you expect.

package pdbp.utils

// ...

object productUtils {

  // ...

  def `((cz&&cy)=>c(z&&y)))=>((cz&&cy)&&cx)=>c(z&&y)&&cx`[C[+ _], Z, Y, X]
    : (((C[Z] && C[Y]) => C[Z && Y])) => (
        C[Z] && C[Y] && C[X]) => C[Z && Y] && C[X] = {
    `(cz&&cy)=>c(z&&y)` => (`cz&&cy`, cx) =>
      (`(cz&&cy)=>c(z&&y)`(`cz&&cy`), cx)
  }

  // ...     

}

Lifting comes with some other interesting computational capabilities.

where

is the function you expect.

package pdbp.utils

// ...

object productUtils {

  // ...

  def `(z&&y)=>(z&&y)`[Z, Y]: (Z && Y) => (Z && Y) = { `z&&y` =>
    `z&&y`
  }

  // ...      

}

where

is the function you expect.

package pdbp.utils

// ...

object productUtils {

  // ...

  def `((z=>y)&&z)=>y`[Z, Y]: ((Z => Y) && Z) => Y = { (`z=>y`, z) =>
    `z=>y`(z)
  }

  // ...     

}

Note that lift1 can be defined in terms of lift0 and lift2.

You may argue why we go for arrows (cfr. Program) instead of applicatives (cfr. Lifting). Arrows occupy the sweet spot between monads and applcatives as far as power of expression and elegance of use is concerned.

Arrows naturally promote pointfree, composition based programming. Agreed, applicatives can also be programmed in a pointfree, composition based way.

Arrows can use an elegant Dotty programming DSL.

Anyway, applicatives provide less power of expression for application developers.

Defining lifting capabilities in terms of computational capabilities

The lifting capabilities lift0, lift1, lift2, lift3, … , can be defined in terms of the computational capabilities bind and result.

package pdbp.computation

import pdbp.types.product.productType._

// ...

private[pdbp] trait Computation[C[+ _]]
    extends Resulting[C]
    with Binding[C]
    with Lifting[C]
    with Sequencing[C]
    with Program[Kleisli[C]] 
    with Applying[Kleisli[C]] {

  override private[pdbp] def lift0[Z]: Z => C[Z] =
    result

  override private[pdbp] def lift1[Z, Y]: (Z => Y) => C[Z] => C[Y] = `z=>y` => {
    case cz =>
      bind(cz, z => result(`z=>y`(z)))
  }

  override private[pdbp] def lift2[Z, Y, X]
    : ((Z && Y) => X) => (C[Z] && C[Y]) => C[X] = `(z&&y)=>x` => {
    case (cz, cy) =>
      bind(cz, z => bind(cy, y => result(`(z&&y)=>x`(z, y))))
  }

  override private[pdbp] def lift3[Z, Y, X, W]
    : ((Z && Y && X) => W) => (C[Z] && C[Y] && C[X]) => C[W] =
    `(z&&y&&x)=>w` => {
      case ((cz, cy), cx) =>
        bind(
          cz,
          z => bind(cy, y => bind(cx, x => result(`(z&&y&&x)=>w`((z, y), x)))))
    }

  // and so on ...

  // ...

}  

Note that result and bind really provide a lot of, agreed, pointful, power of expression for library developers. Note that the definitions of lift0, lift1, lift2, lift3, … naturally read from left to right.

Finally, note that it suffices to define lift0 and lift2 in terms of result and bind but we define lift1 and lift3 anyway.

Defining programming capabilities in terms of computational capabilities.

The programming capabilities function, seqCompose, product and sum can be defined in terms of the computational capabilities bind and result.

package pdbp.computation

// ...

import pdbp.types.sum.sumType._

import pdbp.utils.sumUtils._

// ...

private[pdbp] trait Computation[C[+ _]]
    extends Resulting[C]
    with Binding[C]
    with Lifting[C]
    with Sequencing[C]
    with Program[Kleisli[C]] 
    with Applying[Kleisli[C]] {

  // ...    

  private type `=>C` = Kleisli[C]

  override def function[Z, Y]: (Z => Y) => Z `=>C` Y = { `z=>y` => z =>
    result(`z=>y`(z))
  }

  override def seqCompose[Z, Y, X](`z=>cy`: Z `=>C` Y,
                                `y=>cx`: => Y `=>C` X): Z `=>C` X = { z =>
    bind(`z=>cy`(z), `y=>cx`)
  }

  override def product[Z, Y, X](`z=>cy`: Z `=>C` Y,
                                `z=>cx`: => Z `=>C` X): Z `=>C` (Y && X) = {
    z =>
      bind(`z=>cy`(z), y => bind(`z=>cx`(z), x => result(y, x)))
  }

  override def sum[Z, Y, X](`y=>cz`: => Y `=>C` Z,
                            `x=>cz`: => X `=>C` Z): (Y || X) `=>C` Z =
    foldSum(`y=>cz`, `x=>cz`)

}

Again, note that bind and result really provide a lot of, agreed, pointful, power of expression for library developers. Also, note that the definitions of function, seqCompose and product naturally read from left to right.

Defining computational capabilities in terms of programming and applying capabilities

Describing trait Applying

Consider

package pdbp.program

import pdbp.types.product.productType._

private[pdbp] trait Applying[>-->[- _, + _]] {

  private[pdbp] def apply[Z, Y]: (Z && (Z >--> Y)) >--> Y

}

Think of apply as a program that applies a program of type Z >--> Y to an argument of type Z. It transforms the argument of type Z to yield a result of type Y.

Augmenting computational capabilities with the applying capability

Computational capabilities can, trivially, be augmented with the applying capability.

package pdbp.computation

// ...

private[pdbp] trait Computation[C[+ _]]
    extends Resulting[C]
    with Binding[C]
    with Lifting[C]
    with Sequencing[C]
    with Program[Kleisli[C]] 
    with Applying[Kleisli[C]] {

  // ...

  override private[pdbp] def apply[Z, Y]: (Z && (Z `=>C` Y)) `=>C` Y = {
    (z, `z=>cy`) =>
      `z=>cy`(z)
  }   

}

After all, kleisli programs are functions.

Introducing type Kleisli for unary type constructors

Consider

package pdbp.types.kleisli

object kleisliUnaryTypeConstructorType {

  type Kleisli[>-->[- _, + _]] = [+Y] => Unit >--> Y

}

A computation of type Kleisli[>-->] is referred to as a kleisli computation. Think of it as a program without arguments.

The computational capabilities result and bind can be defined in terms the of the programming capabilities function, seqCompose, and product together with the applying capability apply.

package pdbp.program

import pdbp.program.Program
import pdbp.program.Applying

import pdbp.computation.Resulting
import pdbp.computation.Binding

import pdbp.types.kleisli.kleisliUnaryTypeConstructorType._

private[pdbp] trait ProgramWithApplying[>-->[- _, + _]]
    extends Program[>-->]
    with Applying[>-->]
    with Resulting[Kleisli[>-->]]
    with Binding[Kleisli[>-->]] {

  private type C = Kleisli[>-->]

  override private[pdbp] def result[Z]: Z => C[Z] =
    `z=>(u>-->z)`

  override private[pdbp] def bind[Z, Y](cz: C[Z], `z=>cy`: => Z => C[Y]): C[Y] =
    seqCompose(cz, seqCompose(product(`z>-->u`, function(`z=>cy`)), apply))

}

where

are the programs you expect.

package pdbp.program

// ...

trait Function[>-->[- _, + _]] {

  // ...

  def `z>-->u`[Z]: Z >--> Unit =
    function(`z=>u`)  

  def `z=>(y>-->z)`[Z, Y]: Z => (Y >--> Z) = { z =>
    function(`z=>(y=>z)`(z))
  }

  def `z=>(u>-->z)`[Z]: Z => (Unit >--> Z) =
    `z=>(y>-->z)`[Z, Unit]  

  // ...

}  

where

package pdbp.utils

object functionUtils {

  // ...

  def `z=>u`[Z]: Z => Unit = { z =>
    ()
  }

  def `z=>(y=>z)`[Z, Y]: Z => Y => Z = { z => y =>
    z
  }

}

Semantics of Program Descriptions

Programs are defined as members of classes that are declared to implicitly have the declared or default defined programming capabilities of trait Program[>-->[- _, + _]].

Think of programs as programming domain specific, library language level, syntactic constructs.

We also refer to programs as PDBP programming DSL syntactic constructs.

We also refer to programs as syntactic program descriptions.

There is no semantics associated with them.

Program Implementations

Below are the first steps towards associating semantics with syntactic program descriptions.

We refer to an implicit object that is defined as above as an implicit program object.

We refer to a program that is implemented as above as a program implementation.

We refer to a main program that is implemented as above as a main program implementation.

Note that defining the computational capabilities of type class trait Computation[C[+ _]] in implicit object’s that extends trait trait Computation[C[+ _]] also defines the programming capabilities of trait Program[Kleisli[C]].

We also refer to an implicit object that is defined as above as an implicit computation object or implicit kleisli program object.

We also refer to a kleisli program that is implemented as above as a kleisli program implementation.

Dependency Injection

Program implementations depend on implicit program objects use what we refer to as implicit dependency injection by import.

Implicit dependency injection by import is a very common design pattern for type clases.

Describing active implicit program

The first computation implicit object (and corresponding kleisli program implicit object) one can probably think of is the active program one defined below

package pdbp.program.active

import pdbp.types.active.activeTypes._

import pdbp.utils.functionUtils._

import pdbp.program.Program

import pdbp.computation.Computation

object implicits {

  implicit object program extends Computation[Active] with Program[`=>A`] {

    override private[pdbp] def result[Z]: Z => Active[Z] = `z=>az`

    override private[pdbp] def bind[Z, Y](
        az: Active[Z],
        `z=>ay`: => (Z => Active[Y])): Active[Y] =
      `z=>ay`(az)

  }

}

where the types Active and `=>A` are defined as follows

package pdbp.types.active

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

object activeTypes {

  type Active[+Z] = Z

  type `=>A` = Kleisli[Active]

}

and where

is the program you expect

package pdbp.utils

import pdbp.types.active.activeTypes._

object functionUtils {

  // ...

  def `z=>az`[Z]: Z => Active[Z] = { z =>
    z
  }

}

Note that we use active as opposed to reactive. We explain reactive later in this document.

Also note that the package name refers to how (active) and the object name refers to what (programming capabilities).

For the program implicit program object above we could already go ahead and run programs.

For other implicit program objects we may need more machinery.

Natural transformations

Note that >-->[- _, + _] resp. C[+ _] are binary resp. unary type constructors.

Such type constructors can be transformed using natural transformations.

Natural binary type constructor transformations

Consider

package pdbp.naturalTransformation.binary

trait `~B~>`[`>-F->`[- _, + _], `>-T->`[- _, + _]] {

  def apply[Z, Y]: Z `>-F->` Y => Z `>-T->` Y

}

trait `~B~>` defines natural binary type constructor transformations. F stands for from, T stands for to, and B stands for binary.

Natural unary type constructor transformations

Consider

package pdbp.naturalTransformation.unary

private[pdbp] trait `~U~>`[F[+ _], T[+ _]]
    /* ... */ {
  `f~u~t1` =>

  private[pdbp] def apply[Z](fz: F[Z]): T[Z]

  type T1 = T

  private[pdbp] def andThen[T2[+ _]](`t1~u~t2`: T1 `~U~>` T2): F `~U~>` T2 =
    new {
      override private[pdbp] def apply[Z](fz: F[Z]): T2[Z] =
        `t1~u~t2`(`f~u~t1`(fz))
    }

  // ...

}

trait `~U~>` defines natural unary type constructor transformations. F stands for from, T stands for to, and U stands for unary.

Natural unary type constructor transformations are similar to functions

The difference with functions is that they work at the unary type constructor level instead of at the type level.

Defining natural binary type constructor transformations in terms of natural unary type constructor transformations

For kleisli binary type constructor types, natural binary type constructor transformations can be defined in terms of natural unary type constructor transformations.

package pdbp.naturalTransformation.unary

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.naturalTransformation.binary.`~B~>`

private[pdbp] trait `~U~>`[F[+ _], T[+ _]]
    extends `~B~>`[Kleisli[F], Kleisli[T]] {
  `f~u~t1` =>

  // ...

  private type `=>F` = Kleisli[F]

  private type `=>T` = Kleisli[T]

  override def apply[Z, Y]: Z `=>F` Y => Z `=>T` Y = { `z=>fy` =>
    `z=>fy` andThen apply
  }

}

Describing ProgramMeaning

package pdbp.program.meaning

import pdbp.program.Program

import pdbp.naturalTransformation.binary.`~B~>`

private[pdbp] trait ProgramMeaning[
    `>-P->`[- _, + _]: Program, `>-M->`[- _, + _]: Program] {

  private[pdbp] lazy val binaryTransformation: `>-P->` `~B~>` `>-M->`

  lazy val meaning: `>-P->` `~B~>` `>-M->` = binaryTransformation

}

trait ProgramMeaning has one public member, meaning that is a natural binary type constructor transformation that is an alias for a private[pdbp] member, binaryTransformation.

We refer to the meaning member of trait ProgramMeaning as program meaning.

We refer to a program that is a program meaning meaning(program) of a program program as a meaning program.

Describing ComputationMeaning

package pdbp.computation.meaning

// ...

import pdbp.natural.transformation.unary.`~U~>`

import pdbp.computation.Computation

// ...

private[pdbp] trait ComputationMeaning[C[+ _]: Computation, M[+ _]: Computation]
    extends ProgramMeaning[Kleisli[C], Kleisli[M]] {

  private[pdbp] lazy val unaryTransformation: C `~U~>` M

  // ...

}

trait ComputationMeaning has one private[pdbp] member, unaryTransformation. that is a natural unary type constructor transformation.

We refer to the unaryTransformation member of trait ComputationMeaning as computation meaning.

We refer to a computation that is a computation meaning unaryTransformation(computation) of a computation computation as a meaning computation.

Defining program meanings in terms of computation meanings

For kleisli programs, program meanings can be defined in terms of computation meanings.

We refer to program meanings of kleisli programs as kleisli program meanings.

package pdbp.computation.meaning

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.naturalTransformation.binary.`~B~>`
import pdbp.naturalTransformation.unary.`~U~>`

import pdbp.program.meaning.ProgramMeaning

import pdbp.computation.Computation

private[pdbp] trait ComputationMeaning[C[+ _]: Computation, M[+ _]: Computation]
    extends ProgramMeaning[Kleisli[C], Kleisli[M]] {

  // ...

  private type `=>C` = Kleisli[C]

  private type `=>M` = Kleisli[M]

  private[pdbp] override lazy val binaryTransformation: `=>C` `~B~>` `=>M` =
    unaryTransformation

}

Describing IdentityMeaning

The simplest generic computation meaning is IdentityMeaning below

package pdbp.computation.meaning

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.naturalTransformation.unary.`~U~>`

import pdbp.computation.Computation

private[pdbp] trait IdentityComputationMeaning[C[+ _]: Computation]
    extends ComputationMeaning[C, C] {

  override private[pdbp] lazy val unaryTransformation: C `~U~>` C = new {
    override private[pdbp] def apply[Z](cz: C[Z]): C[Z] = {
      cz
    }
  }

}

Program implementation meanings

Below are the next steps towards associating semantics with syntactic program descriptions.

We refer to a program implementation that is transformed using a program meaning as a program implementation meaning.

We refer to a main program implementation that is transformed using a program meaning as a main program implementation meaning.

Although. since trait ProgramMeaning is not a type class, it is not necessary to define implicit object’s it is convenient to do so.

Describing identity meaning of Active

The first computation meaning implicit object (and corresponding kleisli program meaning implicit object) is the identity meaning of Active defined below

package pdbp.program.meaning.active.ofActive

import pdbp.types.active.activeTypes._

import pdbp.program.active.implicits.program

import pdbp.program.meaning.ProgramMeaning

import pdbp.computation.meaning.ComputationMeaning

import pdbp.computation.meaning.IdentityComputationMeaning

object implicits {

  implicit object identity
      extends IdentityComputationMeaning[Active]()
      with ComputationMeaning[Active, Active]()
      with ProgramMeaning[`=>A`, `=>A`]()

}

Note that the package name reflects the usage of active rather than the object name.

Running a main program implementation meaning

Below is the last step towards associating semantics with syntactic program descriptions.

The definition of run is very specific. We do not define a common trait.

Describing active.run

Consider

package pdbp.run

object active {

  val run: (Unit => Unit) => Unit = { `u=>u`=>
    `u=>u`(())
  } 

  // ... 

}

run can be used to run the identity main program implementation meaning of a main program implementation that uses implicit dependency injection of program.

Running mainFactorial using active program, identity.meaning, and run, and using effectfulReadIntFromConsole and effectfulWriteFactorialOfIntToConsole

Consider

package examples.main.active.effectfulReadingAndWriting

import pdbp.types.active.activeTypes._

import pdbp.program.active.implicits.program

import examples.mainPrograms.MainFactorial

object FactorialMain extends MainFactorial[`=>A`]() {

  import examples.utils.EffectfulUtils

  private val effectfulUtils = new EffectfulUtils[`=>A`]

  import effectfulUtils._

  override val producer = effectfulReadIntFromConsole

  override val consumer = effectfulWriteFactorialOfIntToConsole

  def main(args: Array[String]): Unit = {

    import pdbp.program.meaning.active.ofActive.implicits.identity.meaning

    import pdbp.run.active.run

    run(meaning(mainFactorial))

  }

}

where

package examples.utils

import pdbp.program.Program

class EffectfulUtils[>-->[- _, + _]: Program] 
    extends pdbp.program.utils.EffectfulUtils[>-->] {

  lazy val effectfulReadIntFromConsole: Unit >--> BigInt =
    effectfulReadIntFromConsoleWithMessage("please type an integer")

  lazy val effectfulWriteFactorialOfIntToConsole: BigInt >--> Unit =
    effectfulWriteLineToConsoleWithMessage(
      "the factorial value of the integer is")

  // ...    
}    

where

package pdbp.program.utils

import pdbp.program.Program

import pdbp.utils.effectfulFunctionUtils._

class EffectfulUtils[>-->[- _, + _]: Program] {

  import implicitly._

  def effectfulReadIntFromConsoleWithMessage(
      message: String): Unit >--> BigInt =
    function(effectfulReadIntFromConsoleWithMessageFunction(message))

  def effectfulWriteLineToConsoleWithMessage[Y](
      message: String): Y >--> Unit =
    function(effectfulWriteLineToConsoleWithMessageFunction(message))

  // ...    

}

where

package pdbp.utils

import scala.io.StdIn.readInt


object effectfulFunctionUtils {
 
  def effectfulReadIntFromConsoleWithMessageFunction(message: String): Unit => BigInt = {
    _ =>
      println(s"$message")
      BigInt(readInt())
  }

  // ...

  def effectfulWriteLineToConsoleWithMessageFunction[Y](message: String): Y => Unit = { y =>
    println(s"$message\n$y")
  }

  // ...

}

Here are some details of FactorialMain

Note that there is a lot of import flexibility involved.

Agreed, for run there is not really a lot of flexibility since the main program implementation meaning defines it’s type.

Let’s try factorial with 10.

[info] Running examples.main.active.effectfulReadingAndWriting.FactorialMain
please type an integer
10
the factorial value of the integer is
3628800

Let’s try factorial with 100.

[info] Running examples.main.active.effectfulReadingAndWriting.FactorialMain
please type an integer
100
the factorial value of the integer is
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Let’s try factorial with 1000.

[info] Running examples.main.active.effectfulReadingAndWriting.FactorialMain
please type an integer
1000
[error] (run-main-0) java.lang.StackOverflowError
java.lang.StackOverflowError
...

We have a problem.

The semantic meaning of the syntactic factorial program description uses the stack and is not stack safe.

The good news is that the semantic meaning of the syntactic factorial program description can be replaced by a stack safe one that uses the heap.

We have another problem.

We promised to use function only for pure (a.k.a. as effectfree) functions.

The good news is that both effectfulReadIntFromConsole and effectfulWriteFactorialOfIntToConsole can be replaced by read and write.

Running mainSumOfSquares using active program, identity.meaning and run, and using effectfulReadIntFromConsole and effectfulWriteFactorialOfIntToConsole

Consider

package pdbp.examples.main.active.effectfulReadingAndWriting

import pdbp.types.active.activeTypes._

import pdbp.program.active.implicits.program

import pdbp.examples.mainKleisliPrograms.MainSumOfSquares

object SumOfSquaresMain
    extends MainSumOfSquares[Active]() {

  import pdbp.examples.utils.EffectfulUtils

  private val effectfulUtils = new EffectfulUtils[Active]()

  import effectfulUtils._

  override val producer = effectfulReadTwoDoublesFromConsole

  override val consumer = effectfulWriteSumOfSquaresOfTwoDoublesConsole

  def main(args: Array[String]): Unit = {

    import pdbp.program.meaning.active.ofActive.implicits.identity.meaning

    import pdbp.run.active.run

    run(meaning(mainSumOfSquares))

  }

}

where

package pdbp.examples.utils

import pdbp.types.product.productType._

import pdbp.computation.Resulting

class EffectfulUtils[C[+ _]: Resulting]
    extends pdbp.computation.utils.EffectfulUtils[C]() {

  // ...

  val effectfulReadTwoDoublesFromConsole: Unit `=>C` (Double && Double) =
    effectfulReadTwoDoublesFromConsoleWithMessage("please type a double")

  // ...

  val effectfulWriteSumOfSquaresOfTwoDoublesConsole: Double `=>C` Unit =
    effectfulWriteLineToConsoleWithMessage(
      "the sum of the squares of the doubles is")

}

where

package pdbp.computation.utils

import pdbp.types.product.productType._

import pdbp.utils.effectfulFunctionUtils._

import pdbp.computation.Resulting

trait EffectfulUtils[C[+ _]: Resulting] {

  import implicitly._

  type `=>C` = [-Z, +Y] => Z => C[Y]

  // ...

  def effectfulReadTwoDoublesFromConsoleWithMessage(
      message: String): Unit `=>C` (Double && Double) = { _ =>
    result(effectfulReadTwoDoublesFromConsoleWithMessageFunction(message)(()))
  }

  // ...

}

where

package pdbp.utils

import scala.io.StdIn.readInt
import scala.io.StdIn.readDouble

import pdbp.types.product.productType._

import pdbp.utils.actorUtils._

object effectfulFunctionUtils {
 
  // ...

  def effectfulReadTwoDoublesFromConsoleWithMessageFunction(
      message: String): Unit => (Double && Double) = { _ =>
    println(s"$message")
    val d1 = readDouble()
    println(s"$message")
    val d2 = readDouble()
    (d1, d2)
  }

  // ...

}

Let’s try sumOfSquares with 3.0 and 4.0.

[info] Running pdbp.examples.main.active.effectfulReadingAndWriting.SumOfSquaresMain
please type a double
3.0
please type a double
4.0
the sum of the squares of the doubles is
25.0

Running factorial using active program, identity.meaning and run, and using effectfulReadIntFromConsole and effectfulWriteFactorialOfIntToConsole

Consider

package pdbp.examples.main.active.effectfulReadingAndWriting

import pdbp.types.active.activeTypes._

import pdbp.program.active.implicits.program

import pdbp.examples.mainKleisliPrograms.MainFactorial

object FactorialMain
    extends MainFactorial[Active]() {

  import pdbp.examples.utils.EffectfulUtils

  private val effectfulUtils = new EffectfulUtils[Active]()

  import effectfulUtils._

  override val producer = effectfulReadIntFromConsole

  override val consumer = effectfulWriteFactorialOfIntToConsole

  def main(args: Array[String]): Unit = {

    import pdbp.program.meaning.active.ofActive.implicits.identity.meaning

    import pdbp.run.active.run

    run(meaning(mainFactorial))

  }

}

where

package pdbp.examples.utils

// ...

class EffectfulUtils[C[+ _]: Resulting]
    extends pdbp.computation.utils.EffectfulUtils[C]() {

  val effectfulReadIntFromConsole: Unit `=>C` BigInt =
    effectfulReadIntFromConsoleWithMessage("please type an integer")

  // ...

  val effectfulWriteFactorialOfIntToConsole: BigInt `=>C` Unit =
    effectfulWriteLineToConsoleWithMessage(
      "the factorial value of the integer is")

  // ...

}

where

package pdbp.computation.utils

// ...

trait EffectfulUtils[C[+ _]: Resulting] {

  // ...

  def effectfulReadIntFromConsoleWithMessage(
      message: String): Unit `=>C` BigInt = { _ =>
    result(effectfulReadIntFromConsoleWithMessageFunction(message)(()))
  }

  // ...

}

where

package pdbp.utils

import scala.io.StdIn.readInt
import scala.io.StdIn.readDouble

import pdbp.types.product.productType._

import pdbp.utils.actorUtils._

object effectfulFunctionUtils {
 
  def effectfulReadIntFromConsoleWithMessageFunction(message: String): Unit => BigInt = {
    _ =>
      println(s"$message")
      BigInt(readInt())
  }

  // ...

}

Let’s try factorial with 10.

[info] Running pdbp.examples.main.active.effectfulReadingAndWriting.FactorialMain
please type an integer
10
the factorial value of the integer is
3628800

Describing ComputationTransformation

If we want to change program semantics or extend programming syntax, then we need more machinery. We think that it is convenient to use computation transformations for doing that.

Computation transformations are defined using natural unary type constructor transformations as follows

package pdbp.computation.transformation

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.naturalTransformation.unary.`~U~>`

import pdbp.program.Program

import pdbp.computation.Computation

private[pdbp] trait ComputationTransformation[F[+ _]: Computation, T[+ _]]
    extends Computation[T]
    with Program[Kleisli[T]] {

  private[pdbp] val transform: F `~U~>` T

  override private[pdbp] def result[Z]: Z => T[Z] = { z =>
    transform(implicitly.result(z))
  }

}

Computation transformations closely resemble monad transformers.

Monad transformers were introduced in Monad Transformers and Modular Interpreters.

I have contributed to monad transformers myself by combining them with catamorpisms in Using Catamorphisms, Subtypes and Monad Transformers for Writing Modular Functional Interpreters.

Note that trait ComputationTransformation comes with a default definition for result.

Also note that the default definition of result used implicitly.

Recall that trait Computation is a type class.

trait ComputationTransformation declares, using F[+ _]: Computation, to implicitly have the computational capabilites of the to be transformed computation F available.

implicitly, an abbreviation of implicitly[Computation[F]], is an evidence of those capabilities.

Describing FreeTransformation

The first computation transformation that we describe is trait FreeTransformation. We use it to change the semantics of factorial from stack unsafe to stack safe.

package pdbp.computation.transformation.free

import FreeTransformation._

import pdbp.types.kleisli.kleisliBinaryTypeConstructorType._

import pdbp.program.Program

import pdbp.computation.Computation

import pdbp.natural.transformation.unary.`~U~>`

import pdbp.computation.transformation.ComputationTransformation

private[pdbp] trait FreeTransformation[C[+ _]: Computation]
    extends ComputationTransformation[C, FreeTransformed[C]] {

  private type FTC = FreeTransformed[C]

  override private[pdbp] val transform: C `~U~>` FTC = new {
    override private[pdbp] def apply[Z](cz: C[Z]): FTC[Z] =
      Transform(cz)
  }

  override private[pdbp] def result[Z]: Z => FTC[Z] = { z =>
    Result(z)
  }

  override private[pdbp] def bind[Z, Y](
      ftcz: FTC[Z],
      `z=>ftcy`: => (Z => FTC[Y])): FTC[Y] =
    Bind(ftcz, `z=>ftcy`)

}

where

private[pdbp] object FreeTransformation {

  sealed trait Free[C[+ _], +Z]

  final case class Transform[C[+ _], +Z](cz: C[Z]) extends Free[C, Z]
  final case class Result[C[+ _], +Z](z: Z) extends Free[C, Z]
  final case class Bind[C[+ _], -Z, ZZ <: Z, +Y](fczz: Free[C, ZZ],
                                                 `z=>fcy`: Z => Free[C, Y])
      extends Free[C, Y]

  private[pdbp] type FreeTransformed[C[+ _]] = [+Z] => Free[C, Z]

}

trait Free is an abstract data type that either is a

corresponding to the members

of trait Computation.

or is a

corresponding to the member

of trait ComputationTransformation,

trait FreeTransformation transforms

The definitions of transform, result and bind are trivial. They construct a data structure on the heap.

Think of Free[C, Z] as a free data type wrapped around C as described in Data types a la carte.

The data structures built using Result and Bind are suspended computational capabilities of type Free[C, Z].

The data structure built using Transform wraps the computational capabilities of a computation cz of type C[Z] by transforming them to suspended computational capabilities of type Free[C, Z].

The data Free[C, Z] data structure built using Transform, Result and Bind is a free implementation of the computational capabilities result and bind of trait Computation[FreeTransformed[C]] together with a free wrapped implementation of the computational capabilities result and bind of Computation[C]. In a way it is the most free implementation one can think of because there are no constraints involved.

Anyway, Free[C, Z] is an implementation, it is not a description. Some implementation choice has been taken, abeit the one to build a data structure that suspends all constraint realated decisions to be taken.

Describing active freeProgram

The next computation implicit object (and corresponding kleisli program implicit object) is the active freeProgram one defined below

package pdbp.program.active.free

import pdbp.types.active.activeTypes._
import pdbp.types.active.free.freeActiveTypes._ 

import pdbp.program.Program

import pdbp.program.active.implicits.program

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.free.FreeTransformation

object implicits { 

  implicit object freeProgram
      extends Computation[FreeActive]
      with Program[`=>FA`]
      with ComputationTransformation[Active, FreeActive]()
      with FreeTransformation[Active]()

}

where the types FreeActive and `=>FA` are defined as follows

package pdbp.types.active.free

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._
import pdbp.types.active.activeTypes._

import pdbp.computation.transformation.free.FreeTransformation._

object freeActiveTypes {

  type FreeActive = FreeTransformed[Active]

  type `=>FA` = Kleisli[FreeActive]

}

Describing ImplicitComputationMeaningTransformation

Recall that trait Computation is a type class, and computation transformations make use of implicit computational capabilities of to be transformed computations.

trait ComputationMeaning is not a type class, but we want to transform computation meanings in a way that is similar to the way we transform computations.

We could use a trait with an implicit parameter of type ComputationMeaning. Instead we use an implicit function that transforms an implicit parameter of type ComputationMeaning.

Groundbraking work by Martin Odersky, Simplicity, introduces implicit functions.

Implicit functions replace boilerplate repetition of implicit parameters by an implicitly available global value, implicitly. You may argue that this is going back to the past since, for years, using globals has been considered to be harmful. In fact, instead it is going back to the future since the global value implicitly is only available in a context where the type system can infer that it is available.

Implicit function types are types like other ones. It is convenient to define a type alias for them as follows

package pdbp.types

object implicitFunctionType {

  type `I=>`[-Z, +Y] = implicit Z => Y

}

Consider

package pdbp.computation.meaning.transformation

import pdbp.types.implicitFunctionType.`I=>`

import pdbp.naturalTransformation.unary.`~U~>`

import pdbp.computation.Computation

import pdbp.computation.meaning.ComputationMeaning

private[pdbp] trait ImplicitComputationMeaningTransformation[
    C[+ _]: Computation,
    M[+ _]: Computation,
    TC[+ _]: Computation,
    TM[+ _]: Computation]
    extends (ComputationMeaning[C, M] `I=>` ComputationMeaning[TC, TM])
    with ComputationMeaning[TC, TM] {

  private[pdbp] implicit lazy val implicitComputationMeaning: ComputationMeaning[C, M]

  override private[pdbp] lazy val unaryTransformation: TC `~U~>` TM =
    this(implicitly).unaryTransformation

}

trait ImplicitComputationMeaningTransformation declares a implicit lazy val of type ComputationMeaning[C, M]. The availability of this implicit val (lazy does not matter here) allows us to use implicitly, an abbreviation of implicitly[ComputationMeaning[C, M]] to define unaryTransformation of type TC `~U~>` TM in terms of unaryTransformation of type C `~U~>` M. Note that we could use implicitComputationMeaning as well. For the type system it does not matter.

Describing tail recursive folding ComputationMeaningTransformation of FreeTransformed

A computation meaning transformation that transforms a computation meaning to a free transformed computation meaning is the tail recursive folding one below

package pdbp.computation.meaning.ofFree.tailrecFolding

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.naturalTransformation.unary.`~U~>`

import pdbp.program.meaning.ProgramMeaning

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.free.FreeTransformation
import pdbp.computation.transformation.free.FreeTransformation._

import pdbp.computation.meaning.ComputationMeaning
import pdbp.computation.meaning.transformation.ImplicitComputationMeaningTransformation

private[pdbp] trait ComputationMeaningTransformation[
    C[+ _]: Computation, M[+ _]: Computation]
    extends ImplicitComputationMeaningTransformation[C,
                                                     M,
                                                     FreeTransformed[C],
                                                     M] {

  private type FTC = FreeTransformed[C]

  override def apply(implicit computationMeaning: ComputationMeaning[C, M])
    : ComputationMeaning[FTC, M] = {

    import computationMeaning.{unaryTransformation => `c~u~>m`}  

    val implicitComputation = implicitly[Computation[M]]

    import implicitComputation.{result => resultM, bind => bindM}

    implicit object freeComputation
        extends FreeTransformation[C]()
        with ComputationTransformation[C, FTC]()

    object tailrecFoldingComputationMeaning
        extends ComputationMeaning[FTC, M]()
        with ProgramMeaning[Kleisli[FTC], Kleisli[M]]() {

      override private[pdbp] lazy val unaryTransformation: FTC `~U~>` M =
        new {
          @annotation.tailrec
          override private[pdbp] def apply[Z](ftcz: FTC[Z]): M[Z] = ftcz match {
            case Transform(cz) =>
              `c~u~>m`(cz)
            case Result(z) =>
              resultM(z)
            case Bind(Transform(cy), y2ftcz) =>
              bindM(`c~u~>m`(cy), { y =>
                apply(y2ftcz(y))
              })
            case Bind(Result(y), y2ftcz) =>
              apply(y2ftcz(y))
            case Bind(Bind(ftcx, x2ftcy), y2ftcz) =>
              apply(Bind(ftcx, { x =>
                Bind(x2ftcy(x), y2ftcz)
              }))              
            case any =>
              sys.error(
                s"Impossible, since, 'apply' eliminates the case for $any")
          }
        }

    }

    tailrecFoldingComputationMeaning

  }

}

Note that, for pattern matching, we use names like y2ftcz instead of `y=>ftcz`.

Also note that the package name refers to how (tail recursive folding) and the what (of free transformed).

The method apply that defines unaryTransformation of tailrecFoldingComputationMeaning is a tail recursive folding of a computation of type FTC[Z], a free data structure wrapping a computation of type C[Z], to a meaning computation of type M[Z].

Note that the last case for Bind uses an associativity law of bind. The left associated Bind’s are folded to right associated Bind’s.

Describing tailrecFolding meaning ofFree active

The next computation meaning implicit object (and corresponding kleisli program meaning implicit object) is the tail recursive folding of free transformed active defined below

package pdbp.program.meaning.active.ofFree

import pdbp.types.active.activeTypes._
import pdbp.types.active.free.freeActiveTypes._

import pdbp.naturalTransformation.unary.`~U~>`

import pdbp.program.meaning.ProgramMeaning

import pdbp.computation.meaning.ComputationMeaning

import pdbp.computation.meaning.transformation.ImplicitComputationMeaningTransformation

import pdbp.program.active.implicits.program
import pdbp.program.active.free.implicits.freeProgram

import pdbp.program.meaning.active.ofActive.implicits.identity
import pdbp.computation.meaning.ofFree.tailrecFolding.ComputationMeaningTransformation

object implicits {

  implicit object tailrecFolding
      extends ComputationMeaningTransformation[Active, Active]()
      with ImplicitComputationMeaningTransformation[Active,
                                                    Active,
                                                    FreeActive,
                                                    Active]()
      with ComputationMeaning[FreeActive, Active]()
      with ProgramMeaning[`=>FA`, `=>A`]() {

    override private[pdbp] implicit lazy val implicitComputationMeaning
      : ComputationMeaning[Active, Active] =
      identity

  }

}

Note that the package name refers to what (active of free) and the object name refers to how (tail recursive folding).

Running mainFactorial using active freeProgram, tailrecFolding.meaning and run, and using effectfulReadIntFromConsole and effectfulWriteFactorialOfIntToConsole

Consider

package examples.main.active.tailrecursive.effectfulReadingAndWriting

import pdbp.types.active.activeTypes._
import pdbp.types.active.free.freeActiveTypes._

import pdbp.program.active.free.implicits.freeProgram

import examples.mainPrograms.MainFactorial

object FactorialMain extends MainFactorial[`=>FA`]() {

  import examples.utils.EffectfulUtils

  private val effectfulUtils = new EffectfulUtils[`=>FA`]

  import effectfulUtils._

  override val producer = effectfulReadIntFromConsole

  override val consumer = effectfulWriteFactorialOfIntToConsole

  def main(args: Array[String]): Unit = {

    import pdbp.program.meaning.active.ofFree.implicits.tailrecFolding.meaning

    import pdbp.run.active.run

    run(meaning(mainFactorial))

  }

}

Note that we only changed

Let’s try factorial with 1000.

[info] Running examples.main.active.free.effectfulReadingAndWriting.FactorialMain
please type an integer
1000
the factorial value of the integer is
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

We do not have a stack overflow problem any more since we are using the heap instead.

When, agreed, in an effectful way, we println(s"Result($y)") every time we unfold a Bind(Result(y), y2ftcz) we can see what is going on when unfolding.

Let’s try factorial with 3.

[info] Running examples.main.active.tailrecursive.effectfulReadingAndWriting.FactorialMain
please type an integer
3
Result(3)
Result(3)
Result(false)
Result((3,false))
Result(Right(3))
Result(3)
Result(2)
Result(2)
Result(false)
Result((2,false))
Result(Right(2))
Result(2)
Result(1)
Result(1)
Result(false)
Result((1,false))
Result(Right(1))
Result(1)
Result(0)
Result(0)
Result(true)
Result((0,true))
Result(Left(0))
Result(1)
Result((1,1))
Result(1)
Result((2,1))
Result(2)
Result((3,2))
Result(6)
the factorial value of the integer is
6

Describing Reading

Introduction

In the section describing Program and the section describing Computation we presented the basic programming and computation capabilities.

In this section, describing Reading, we introduce the first extra programming capability: reading.

We already used effectful input reading using producers of type Unit >--> Z together with effectful output writing using consumers of type Y >--> Unit to turn programs of type Z >--> Y into main programs of type Unit >--> Unit.

In this section we describe effectfree input reading of type Unit >--> R and, more generally, effectfree reading of type Z >--> R.

Think, for example, of the effectfree reading capability of this section as being able to

Describing Reading

Consider

package pdbp.program.reading

import pdbp.program.Function
import pdbp.program.Composition

trait Reading[R, >-->[- _, + _]] {
  this: Function[>-->] & Composition[>-->] =>

  private[pdbp] val `u>-->r`: Unit >--> R = read[Unit]

  private[pdbp] def `z>-->r`[Z]: Z >--> R =
    seqCompose(`z>-->u`, `u>-->r`)

  def read[Z]: Z >--> R = `z>-->r`

}

Think of `u>-->r` as a program without arguments that yields result of type R. We also say that `u>-->r` is a program that, out of nothing, produces a result of type R.

Think of `z>-->r` as a program that transforms an argument of type Z to a yield result of type R. We also say that `z>-->r` is a program that, out of anything, produces a result of type R.

We also simply say that `u>-->r` and `z>-->r` read a value of type R.

Note that `z>-->u` and `z>-->r` are private[pdbp].

Since we are defining a public programming API, it is convenient to define an public alias read for `z>-->r`.

Describing ReadingTransformation

The next computation transformation that we describe is trait ReadingTransformation We used it to add the reading capability to program descriptions.

In his POPL article, Martin Odersky argues that implicit functions can be used to replace the reader monad (cfr. our reading capability of program descriptions).

Since our goal is to provide an explicit programming DSL we add reading as an explicit programming capability taking advantage of implicit functions to greatly simplify the definitions of trait ReadingTransformation and optimize their performance.

Our explicit, globally available, reading capability read closely corresponds to the implicit, globally available value implicitly.

You may argue: why using an explicit read member if using an implicitly available implicitly value works as well.

Frankly, we do not have a fully satisfying answer. The best one we can think of is that we prefer to be syntactically explicit and semantically implicit.

Describing ReadingTransformation

Consider

package pdbp.computation.transformation.reading

import ReadingTransformation._

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.naturalTransformation.unary.`~U~>`

import pdbp.program.reading.Reading

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation

private[pdbp] trait ReadingTransformation[R, C[+ _]: Computation]
    extends ComputationTransformation[C, ReadingTransformed[R, C]]
    with Reading[R, Kleisli[ReadingTransformed[R, C]]] {

  private type RTC = ReadingTransformed[R, C]
  private type `=>RTC` = Kleisli[RTC]

  import implicitly.{result => resultC}
  import implicitly.{bind => bindC}

  override private[pdbp] val transform: C `~U~>` RTC = new {
    override private[pdbp] def apply[Z](cz: C[Z]): RTC[Z] = {
      cz
    }
  }

  override private[pdbp] def bind[Z, Y](rtcz: RTC[Z],
                                        `z>=rtcy`: => (Z => RTC[Y])): RTC[Y] = {
    bindC(rtcz, { z =>
      `z>=rtcy`(z)
    })
  }

  private[pdbp] override val `u>-->r`: Unit `=>RTC` R = { _ =>
    resultC(implicitly)
  }

}

where

package pdbp.computation.transformation.reading

import pdbp.types.implicitFunctionType.`I=>`

private[pdbp] object ReadingTransformation {

  type ReadingTransformed[R, C[+ _]] = [+Z] => R `I=>` C[Z]

}

The types RTC and `=>RTC`, defined using `I=>`, indicate that the an implicitly available global value implicitly[R] is available. In fact, in `u>-->r` we use it as implicitly (not to be confused with the other implicitly standing for implicitly[Computation[C]]).

You may wonder how on earth it is possible that the definitions above are so simple. The magic of implicit function types is that the compiler can turn value types into implicit function types whenever it expects them to be.

Describing active intReadingProgram

The next computation implicit object (and corresponding kleisli program implicit object) is the active intReadingProgram one defined below

package pdbp.program.active.reading.int

import pdbp.types.active.activeTypes._
import pdbp.types.active.reading.readingActiveTypes._

import pdbp.program.Program
import pdbp.program.reading.Reading

import pdbp.program.active.reading.ReadingProgram

import pdbp.program.active.implicits.program

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.reading.ReadingTransformation

object implicits {

  implicit object intReadingProgram
      extends ReadingProgram[BigInt]()
      with Computation[ReadingActive[BigInt]]()
      with Program[`=>RA`[BigInt]]()
      with Reading[BigInt, `=>RA`[BigInt]]()
      with ComputationTransformation[Active, ReadingActive[BigInt]]()
      with ReadingTransformation[BigInt, Active]()

}

where

package pdbp.program.active.reading

import pdbp.types.active.activeTypes._
import pdbp.types.active.reading.readingActiveTypes._

import pdbp.program.Program
import pdbp.program.reading.Reading

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.reading.ReadingTransformation

private[pdbp] trait ReadingProgram[R]
    extends Computation[ReadingActive[R]]
    with Program[`=>RA`[R]]
    with Reading[R, `=>RA`[R]]
    with ComputationTransformation[Active, ReadingActive[R]]
    with ReadingTransformation[R, Active]

where the types ReadingActive and `=>RA` are defined as follows

package pdbp.types.active.reading

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.types.active.activeTypes._

import pdbp.computation.transformation.reading.ReadingTransformation._

object readingActiveTypes {

  type ReadingActive[R] = ReadingTransformed[R, Active]

  type `=>RA`[R] = Kleisli[ReadingActive[R]]   

}

Note that, since there is a type parameter R involved, we first define a generic trait with type parameter R and next a corresponding implicit object type argument BigInt.

Describing implicit value reading ComputationMeaningTransformation of ReadingTransformed

A computation meaning transformation that transforms a computation meaning to a reading transformed computation meaning is the implicit value reading one below

package pdbp.computation.meaning.ofReading.implicitValueReading

import pdbp.types.implicitFunctionType.`I=>`
import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.naturalTransformation.unary.`~U~>`

import pdbp.program.meaning.ProgramMeaning

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.reading.ReadingTransformation
import pdbp.computation.transformation.reading.ReadingTransformation._

import pdbp.computation.meaning.ComputationMeaning
import pdbp.computation.meaning.transformation.ImplicitComputationMeaningTransformation

private[pdbp] trait ComputationMeaningTransformation[
    R, C[+ _]: Computation, M[+ _]: Computation]
    extends ImplicitComputationMeaningTransformation[
      C,
      M,
      ReadingTransformed[R, C],
      ReadingTransformed[R, M]] {

  private type RTC = ReadingTransformed[R, C]
  private type RTM = ReadingTransformed[R, M]

  override def apply(implicit computationMeaning: ComputationMeaning[C, M])
    : ComputationMeaning[RTC, RTM] = {

    import computationMeaning.{unaryTransformation => `c~u~>m`}  

    implicit object readingComputation
        extends ReadingTransformation[R, C]()
        with ComputationTransformation[C, RTC]()

    implicit object readingComputationMeaning
        extends ReadingTransformation[R, M]()
        with ComputationTransformation[M, RTM]()

    object implicitValueReadingComputationMeaning
        extends ComputationMeaning[RTC, RTM]()
        with ProgramMeaning[Kleisli[RTC], Kleisli[RTM]]() {

      override private[pdbp] lazy val unaryTransformation: RTC `~U~>` RTM =
        new {
          override private[pdbp] def apply[Z](rtcz: RTC[Z]): RTM[Z] =
            `c~u~>m`(rtcz(implicitly))
        }                                 

    }

    implicitValueReadingComputationMeaning

  }

}

Note that unaryTransformation of implicitValueReadingComputationMeaning uses rtcz(implicitly) to read the implicit value.

Describing implicitIntReading meaning ofIntReading active

The next computation meaning implicit object (and corresponding kleisli program meaning implicit object) is the reading implicit int of int reading transformed active implicitIntReading one defined below

package pdbp.program.meaning.active.ofIntReading

import pdbp.types.active.activeTypes._
import pdbp.types.active.reading.readingActiveTypes._

import pdbp.naturalTransformation.unary.`~U~>`

import pdbp.program.active.implicits.program
import pdbp.program.active.reading.int.implicits.intReadingProgram

import pdbp.program.meaning.ProgramMeaning
import pdbp.program.meaning.active.ofActive.implicits.identity

import pdbp.computation.meaning.ComputationMeaning
import pdbp.computation.meaning.ofReading.ComputationMeaningTransformation
import pdbp.computation.meaning.transformation.ImplicitComputationMeaningTransformation

object implicits {

  implicit object implicitIntReading
      extends ComputationMeaningTransformation[BigInt, Active, Active]()
      with ImplicitComputationMeaningTransformation[Active,
                                                    Active,
                                                    ReadingActive[BigInt],
                                                    ReadingActive[BigInt]]()
      with ComputationMeaning[ReadingActive[BigInt], ReadingActive[BigInt]]()
      with ProgramMeaning[`=>RA`[BigInt], `=>RA`[BigInt]]() {

    override private[pdbp] implicit lazy val implicitComputationMeaning
      : ComputationMeaning[Active, Active] =
      identity

  }

}

Describing active.reading.run

package pdbp.run

object active {

  // ...

  import pdbp.types.implicitFunctionType._

  object reading {

    def run[R]: (Unit => (R `I=>` Unit)) => R `I=>` Unit = { `u=>(ri=>u)`=>
      `u=>(ri=>u)`(())
    }    

  }  

}

Running mainFactorial using active intReadingProgram, implicitIntReading.meaning and reading.run, and using read and effectfulWriteFactorialOfIntReadToConsole

Consider

package examples.main.active.reading.int.effectfulWriting

import pdbp.types.active.reading.readingActiveTypes._

import pdbp.program.active.reading.int.implicits.intReadingProgram

import examples.mainPrograms.MainFactorial

object FactorialOfReadMain extends MainFactorial[`=>RA`[BigInt]]() {

  import examples.utils.EffectfulUtils

  private val effectfulUtils = new EffectfulUtils[`=>RA`[BigInt]]

  import effectfulUtils._

  override val producer = intReadingProgram.read

  override val consumer = effectfulWriteFactorialOfIntReadConsole

  def main(args: Array[String]): Unit = {

    import examples.utils.implicits.intEffectfullyReadFromConsole

    import pdbp.program.meaning.active.ofIntReading.implicits.implicitIntReading.meaning

    import pdbp.run.active.reading.run

    run(meaning(mainFactorial))

  }

}

Note that we only changed

intEffectfullyReadFromConsole implements, effectful, the BigInt that is, effectfree, declared to implicitly be read by read.

package examples.utils

// ...

import pdbp.utils.effectfulReadUtils._

// ...

object implicits {

  // effectful

  implicit lazy val intEffectfullyReadFromConsole: BigInt =
    intEffectfullyReadFromConsoleWithMessage("please type an integer to read")

  // ...

}

where

package pdbp.utils

import pdbp.utils.effectfulFunctionUtils._

object effectfulReadUtils {

  def intEffectfullyReadFromConsoleWithMessage(message: String): BigInt =
    effectfulReadIntFromConsoleWithMessageFunction(message)(()) 

}

and where

package examples.utils

import pdbp.program.Program

class EffectfulUtils[>-->[- _, + _]: Program] {

  // ...

  lazy val effectfulWriteFactorialOfIntReadToConsole: BigInt >--> Unit =
    effectfulWriteLineToConsoleWithMessage(
      "the factorial value of the integer read is")

}

For being able to run mainFactorial, we have to define the implicit BigInt of ReadingTransformed. We can postpone defining this to the body of main and we can simply do this by importing intEffectfullyReadFromConsole.

Note that

Let’s try factorial with 10.

[info] Running examples.main.active.reading.int.effectfulWriting.FactorialOfIntReadMain
please type an integer to read
10
the factorial value of the integer read is
3628800

Note that we use read as a producer at the beginning of a program.

Describing FactorialMultipliedByIntRead

We can use read in the middle of a program.

Consider

package examples.programs.reading.int

import pdbp.program.Program
import pdbp.program.reading.Reading
import pdbp.program.compositionOperator._
import pdbp.program.constructionOperators._

import examples.programs.Factorial

class FactorialMultipliedByIntRead[
    >-->[- _, + _]: Program
                  : [>-->[- _, + _]] => Reading[BigInt, >-->]]
    extends Factorial[>-->] {

  private val implicitProgram = implicitly[Program[>-->]]

  import implicitProgram._

  private val implicitIntReading = implicitly[Reading[BigInt, >-->]]

  import implicitIntReading._

  val factorialMultipliedByIntRead: BigInt >--> BigInt =
    (factorial & read) >--> multiply

}

Note that

Also note that

Describing mainFactorialMultipliedByIntRead

Consider

package examples.mainPrograms.reading.int

import pdbp.program.Program
import pdbp.program.reading.Reading
import pdbp.program.compositionOperator._

import examples.programs.reading.int.FactorialMultipliedByIntRead

trait MainFactorialMultipliedByIntRead[
    >-->[- _, + _]: Program
                  : [>-->[- _, + _]] => Reading[BigInt, >-->]] {

  private object factorialMultipliedByIntReadObject
      extends FactorialMultipliedByIntRead[>-->]

  import factorialMultipliedByIntReadObject.factorialMultipliedByIntRead

  val producer: Unit >--> BigInt

  val consumer: BigInt >--> Unit

  lazy val mainFactorialMultipliedByIntRead: Unit >--> Unit =
    producer >-->
      factorialMultipliedByIntRead >-->
      consumer

}

trait MainFactorialMultipliedByIntRead defines lazy val mainFactorialMultipliedByIntRead using abstract members producer and consumer.

Running mainFactorialMultipliedByIntRead using active intReadingProgram, implicitIntReading.meaning and reading.run, and using effectfulReadIntFromConsole and effectfulWriteFactorialOfIntReadToConsole

Consider

package examples.main.active.reading.int.effectfulReadingAndWriting
import pdbp.types.active.reading.readingActiveTypes._

import pdbp.program.active.reading.int.implicits.intReadingProgram

import examples.mainPrograms.reading.int.MainFactorialMultipliedByIntRead

object FactorialMultipliedByReadMain
    extends MainFactorialMultipliedByIntRead[`=>RA`[BigInt]]() {

  import examples.utils.EffectfulUtils

  private val effectfulUtils = new EffectfulUtils[`=>RA`[BigInt]]

  import effectfulUtils._

  override val producer = effectfulReadIntFromConsole

  override val consumer =
    effectfulWriteFactorialOfIntMultipliedByIntReadToConsole

  def main(args: Array[String]): Unit = {

    import examples.utils.implicits.intEffectfullyReadFromConsole

    import pdbp.program.meaning.active.ofIntReading.implicits.implicitIntReading.meaning

    import pdbp.run.active.reading.run

    run(meaning(mainFactorialMultipliedByIntRead))

  }

}

where

trait EffectfulUtils[>-->[- _, + _]: Function] {

  // ...

  lazy val effectfulWriteFactorialOfIntMultipliedByIntReadToConsole
    : BigInt >--> Unit =
    effectfulWriteLineToConsoleWithMessage(
      "the factorial value of the integer multiplied by the integer read is")

}

Let’s try factorialMultipliedByIntRead with 10 and let’s read 2 as multiplier.

[info] Running examples.main.active.reading.int.effectfulReadingAndWriting.FactorialMultipliedByIntReadMain
please type an integer
10
please type an integer to read
2
the factorial value of the integer multiplied by the integer read is
7257600

Note that factorialMultipliedByIntRead uses an effectful producer.

Describing FactorialOfArgumentReadMultipliedByMultiplierRead

We can use read both as a producer at the beginning of a program and in the middle of a program.

Consider

package examples.types.factorialArgumentAndMultiplier

import pdbp.types.product.productType._

import examples.programs.Factorial

object factorialArgumentAndMultiplierType {

  type FactorialArgumentAndMultiplier = BigInt && BigInt

} 

FactorialArgumentAndMultiplier is a type alias for two integers. The first one is a factorial argument and the second one is a multiplier.

Consider

package examples.programs.reading.factorialArgumentAndMultiplier

import pdbp.types.product.productType._

import pdbp.program.Program
import pdbp.program.reading.Reading
import pdbp.program.compositionOperator._
import pdbp.program.constructionOperators._

import examples.types.factorialArgumentAndMultiplier.factorialArgumentAndMultiplierType.FactorialArgumentAndMultiplier

import examples.programs.Factorial

class FactorialOfArgumentReadMultipliedByMultiplierRead[
    >-->[- _, + _]: Program
                  : [>-->[- _, + _]] => Reading[FactorialArgumentAndMultiplier, >-->]]
    extends Factorial[>-->] {

  private val implicitProgram = implicitly[Program[>-->]]

  import implicitProgram._

  private val implicitIntReading =
    implicitly[Reading[FactorialArgumentAndMultiplier, >-->]]

  import implicitIntReading._

  val readFactorialArgument = read >--> function { (factorialArgument, _) =>
    factorialArgument
  }

  private val readMultiplier = read >--> function { (_, multiplier) =>
    multiplier
  }

  val factorialOfArgumentReadMultipliedByMultiplierRead: BigInt >--> BigInt =
    (factorial & readMultiplier) >--> multiply

}

Note that we define two reading programs readFactorialArgument and readMultiplier.

Describing mainFactorialOfArgumentReadMultipliedByMultiplierRead

Consider

package examples.mainPrograms.reading.factorialArgumentAndMultiplier

import pdbp.types.product.productType._

import pdbp.program.Program
import pdbp.program.reading.Reading
import pdbp.program.compositionOperator._

import examples.types.factorialArgumentAndMultiplier.factorialArgumentAndMultiplierType.FactorialArgumentAndMultiplier

import examples.programs.reading.factorialArgumentAndMultiplier.FactorialOfArgumentReadMultipliedByMultiplierRead

trait MainFactorialOfArgumentReadMultipliedByMultiplierRead[
    >-->[- _, + _]: Program
                  : [>-->[- _, + _]] => Reading[FactorialArgumentAndMultiplier, >-->]] {

  private[examples] object factorialOfArgumentReadMultipliedByMultiplierReadObject
      extends FactorialOfArgumentReadMultipliedByMultiplierRead[>-->]

  import factorialOfArgumentReadMultipliedByMultiplierReadObject.factorialOfArgumentReadMultipliedByMultiplierRead
  
  val producer: Unit >--> BigInt

  val consumer: BigInt >--> Unit

  lazy val mainFactorialOfArgumentReadMultipliedByMultiplierRead: Unit >--> Unit =
    producer >-->
      factorialOfArgumentReadMultipliedByMultiplierRead >-->
      consumer

}

trait MainFactorialOfArgumentReadMultipliedByMultiplierRead defines lazy val mainFactorialOfArgumentReadMultipliedByMultiplierRead using abstract members producer and consumer.

Running mainFactorialOfArgumentReadMultipliedByMultiplierRead using active twoIntsReadingProgram, readingTwoImplicitInts.meaning and reading.run, and using readFactorialArgument and effectfulWriteFactorialOfArgumentReadMultipliedByMultiplierReadToConsole

Consider

package examples.main.active.reading.factorialArgumentAndMultiplier.effectfulWriting

import pdbp.types.product.productType._
import pdbp.types.active.reading.readingActiveTypes._

import pdbp.program.active.reading.twoInts.implicits.twoIntsReadingProgram

import examples.types.factorialArgumentAndMultiplier.factorialArgumentAndMultiplierType.FactorialArgumentAndMultiplier

import examples.programs.reading.factorialArgumentAndMultiplier.FactorialOfArgumentReadMultipliedByMultiplierRead

import examples.mainPrograms.reading.factorialArgumentAndMultiplier.MainFactorialOfArgumentReadMultipliedByMultiplierRead

object FactorialOfArgumentReadMultipliedByMultiplierReadMain
    extends MainFactorialOfArgumentReadMultipliedByMultiplierRead[
      `=>RA`[FactorialArgumentAndMultiplier]]() {

  import examples.utils.EffectfulUtils

  private val effectfulUtils =
    new EffectfulUtils[`=>RA`[FactorialArgumentAndMultiplier]]

  import effectfulUtils._

  override val producer =
    factorialOfArgumentReadMultipliedByMultiplierReadObject.readFactorialArgument

  override val consumer =
    effectfulWriteFactorialOfArgumentReadMultipliedByMultiplierReadToConsole

  def main(args: Array[String]): Unit = {

    import examples.utils.implicits.factorialArgumentAndMultiplierEffectfullyReadFromConsole

    import pdbp.program.meaning.active.ofTwoIntsReading.implicits.readingTwoImplicitInts.meaning

    import pdbp.run.active.reading.run

    run(meaning(mainFactorialOfArgumentReadMultipliedByMultiplierRead))

  }

}

where

package pdbp.program.active.reading.twoInts

import pdbp.types.product.productType._
import pdbp.types.active.activeTypes._
import pdbp.types.active.reading.readingActiveTypes._

import pdbp.program.Program
import pdbp.program.reading.Reading

import pdbp.program.active.reading.ReadingProgram

import pdbp.program.active.implicits.program

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.reading.ReadingTransformation

object implicits {

  implicit object twoIntsReadingProgram
      extends ReadingProgram[BigInt && BigInt]()
      with Computation[ReadingActive[BigInt && BigInt]]()
      with Program[`=>RA`[BigInt && BigInt]]()
      with Reading[BigInt && BigInt, `=>RA`[BigInt && BigInt]]()
      with ComputationTransformation[Active, ReadingActive[BigInt && BigInt]]()
      with ReadingTransformation[BigInt && BigInt, Active]()

}

and

package pdbp.program.meaning.active.ofTwoIntsReading

import pdbp.types.product.productType._
import pdbp.types.active.activeTypes._
import pdbp.types.active.reading.readingActiveTypes._

import pdbp.naturalTransformation.unary.`~U~>`

import pdbp.program.active.implicits.program
import pdbp.program.active.reading.twoInts.implicits.twoIntsReadingProgram

import pdbp.program.meaning.ProgramMeaning
import pdbp.program.meaning.active.ofActive.implicits.identity

import pdbp.computation.meaning.ComputationMeaning
import pdbp.computation.meaning.ofReading.readingImplicit.ComputationMeaningTransformation
import pdbp.computation.meaning.transformation.ImplicitComputationMeaningTransformation

object implicits {

  implicit object readingTwoImplicitInts
      extends ComputationMeaningTransformation[BigInt && BigInt,
                                               Active,
                                               Active]()
      with ImplicitComputationMeaningTransformation[
        Active,
        Active,
        ReadingActive[BigInt && BigInt],
        ReadingActive[BigInt && BigInt]]()
      with ComputationMeaning[ReadingActive[BigInt && BigInt],
                              ReadingActive[BigInt && BigInt]]()
      with ProgramMeaning[`=>RA`[BigInt && BigInt], `=>RA`[BigInt && BigInt]]() {

    override private[pdbp] implicit lazy val implicitComputationMeaning
      : ComputationMeaning[Active, Active] =
      identity

  }

}

and where

trait EffectfulUtils[>-->[- _, + _]: Function] {

  // ...

  lazy val effectfulWriteFactorialOfArgumentReadMultipliedByMultiplierReadToConsole
    : BigInt >--> Unit =
    effectfulWriteLineToConsoleWithMessage(
      "the factorial value of the argument read multiplied by the multiplier read is")

  // ...    

}

Let’s try factorialOfArgumentReadMultipliedByMultiplierRead reading factorial argument 10 and reading 2 as multiplier.

[info] Running examples.main.active.reading.factorialArgumentAndMultiplier.effectfulWriting.FactorialOfArgumentReadMultipliedByMultiplierReadMain
please type a factorial argument
10
please type a multiplier
2
the factorial value of the argument read multiplied by the multiplier read is
7257600

Describing Writing

Introduction

In sections Program and Computation we presented the basic programming and computation capabilities.

In this section, Writing, we introduce the next extra programming capability: writing.

We already used effectful input reading using producers of type Unit >--> Z together with a effectful output writing using consumers of type Y >--> Unit to turn programs of type Z >--> Y into main programs of type Unit >--> Unit.

In this section we describe effectfree output writing of type W >--> Unit and, more generally, effectfree writing of type Z >--> Unit.

Think, for example, of the effectfree writing capability of this section as being able to

Describing Writing

Consider

package pdbp.program.writing

import pdbp.types.implicitFunctionType._
import pdbp.types.product.productType._

import pdbp.utils.infoUtils._

import pdbp.writable.Writable

import pdbp.program.Function
import pdbp.program.Composition
import pdbp.program.Construction

trait Writing[W: Writable, >-->[- _, + _]] {
  this: Function[>-->] & Composition[>-->] & Construction[>-->] =>

  private[pdbp] val `w>-->u`: W >--> Unit = `z>-w->u`(identity)

  private[pdbp] def `z>-w->u`[Z]: (Z => W) `I=>` Z >--> Unit =
    seqCompose(function(implicitly), `w>-->u`)

  def write[Z]: (Z => W) `I=>` Z >--> Unit =
    `z>-w->u`

  private def writing[Z, Y, X](
      `(z&&y)=>x`: ((Z && Y) => X)): (Z >--> Y) => ((X => W) `I=>` Z >--> Y) = {
    `z>-->y` =>
      val `(z&&y)>-->x` = function(`(z&&y)=>x`)
      val `z>-->(x&&y)` =
        `let` {
          `z>-->y`
        } `in` {
          `let` {
            `(z&&y)>-->x`
          } `in` {
            `(z&&y&&x)>-->(x&&y)`
          }
        }
      seqCompose(seqCompose(`z>-->(x&&y)`, left(`z>-w->u`)), `(u&&y)>-->y`)
  }

  // ...

}

Writable is described later in this section.

Think of `w>-->u` as a program that writes a writable value of type W.

Think of `z>-w->u` as a program that writes a value of type Z that can implicitly be converted (using a function of type Z => W) to a Writable of type W.

Note that `w>-->u` and `z>-w->u` are private[pdbp].

Since we are defining a public programming API, it is also convenient to define a public alias write for `z>-w->u`.

Moreover we define a private capability writing.

Think of ` writing((z&&y)=>x)(z>–>y) as the program z>–>y that also writes a value of type X that is yielded by transforming z>–>y's argument of type Z and z>–>y's result of type Y to a result of type X`.

How to use writing is described later in this section.

Describing Writable

Consider

package pdbp.writable

import pdbp.types.const.constType._

import pdbp.utils.functionUtils._

import pdbp.computation.Lifting

trait Writable[W]
    extends Startable[W]
    with Appendable[W]
    with Lifting[Const[W]]

where

package pdbp.writable

import pdbp.types.const.constType._

import pdbp.computation.ObjectLifting

private[pdbp] trait Startable[W] extends ObjectLifting[Const[W]] {

  private[pdbp] val start: W

  override private[pdbp] def liftObject[Z](z: Z): W = start

}

and

package pdbp.writable

import pdbp.types.product.productType._

import pdbp.types.const.constType._

import pdbp.utils.productUtils._

import pdbp.computation.OperatorLifting

private[pdbp] trait Appendable[W] extends OperatorLifting[Const[W]] {

  private[pdbp] val append: W && W => W

  override private[pdbp] def liftOperator[Z, Y, X](
      `(z&&y)=>x`: (Z && Y) => X): (W && W) => W = append

}

The relationship with Lifting is defined in terms of the type Const below

package pdbp.types.const

object constType {

  type Const[X] = [+Z] => X

}

trait Writable corresponds to monoids.

Describing Writing continued

Consider

package pdbp.program.writing

import pdbp.types.implicitFunctionType._

trait Writing[W: Writable, >-->[- _, + _]] {
  this: Function[>-->] & Composition[>-->] & Construction[>-->] =>

  // ...

  def writingInfo[Z, Y](
      what: (Z && Y) => String): (Z >--> Y) => ((Info => W) `I=>` Z >--> Y) =
    writing {
      case (z, y) => Info(System.nanoTime(), Thread.currentThread.getId , what(z, y))
    }

}

where

package pdbp.utils

// ...

object infoUtils {

  case class Info(when: Long, who: Long, what: String) {

    override def toString =
      s"[INFO] when $when who $who what $what\n"

  }

  // ...

}

Think of writingInfo(methodName)(z>–>y) as the program z>-->y that also writes when, who and what related information. The what related information is yielded by transforming z>-->y’s argument of type Z and z>-->y’s result of type Y to a meaningful string.

Below is an example of what this information may look like

where when is System.nanoTime()and who is Thread.currentThread.getId().

Describing WritingTransformation

The next computation transformation that we describe is trait WritingTransformation that is used to add the writing capability to program descriptions.

package pdbp.computation.transformation.writing

import WritingTransformation._

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.writable.Writable

import pdbp.naturalTransformation.unary.`~U~>`

import pdbp.program.Program
import pdbp.program.writing.Writing

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation

private[pdbp] trait WritingTransformation[W: Writable, C[+ _]: Computation]
    extends ComputationTransformation[C, WritingTransformed[W, C]]
    with Writing[W, Kleisli[WritingTransformed[W, C]]] {

  private type WTC = WritingTransformed[W, C]
  private type `=>WTC` = Kleisli[WTC]

  private val implicitComputation = implicitly[Computation[C]]

  import implicitComputation.{bind => bindC}
  import implicitComputation.{result => resultC}

  private val implicitWritable = implicitly[Writable[W]]

  import implicitWritable._

  override private[pdbp] val transform: C `~U~>` WTC = new {
    override private[pdbp] def apply[Z](cz: C[Z]): WTC[Z] =
      bindC(cz, { z =>
        resultC((start, z))
      })
  }

  override private[pdbp] def bind[Z, Y](wtcz: WTC[Z],
                                        `z=>wtcy`: => (Z => WTC[Y])): WTC[Y] =
    bindC(wtcz, { (leftW, z) =>
      bindC(`z=>wtcy`(z), { (rightW, y) =>
        resultC(append(leftW, rightW), y)
      })
    })

  private[pdbp] override val `w>-->u`: W `=>WTC` Unit = { w =>
    resultC((w, ()))
  }

}

where

import pdbp.types.product.productType._

private[pdbp] object WritingTransformation { 

  type WritingTransformed[W, C[+ _]] = [+Z] => C[W && Z]

}

Describing active toConsoleWritingProgram

The next computation implicit object (and corresponding kleisli program implicit object) is the active toConsoleWritingProgram one defined below

package pdbp.program.active.writing.toConsole

import pdbp.types.toConsole.ToConsole
import pdbp.types.active.activeTypes._
import pdbp.types.active.writing.writingActiveTypes._

import pdbp.writable.toConsole.implicits.toConsoleWritable

import pdbp.program.Program

import pdbp.program.writing.Writing

import pdbp.program.active.writing.WritingProgram
import pdbp.program.active.implicits.program

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.writing.WritingTransformation

object implicits {

  implicit object toConsoleWritingProgram
      extends WritingProgram[ToConsole]()
      with Computation[WritingActive[ToConsole]]()
      with Program[`=>WA`[ToConsole]]()
      with Writing[ToConsole, `=>WA`[ToConsole]]()
      with ComputationTransformation[Active, WritingActive[ToConsole]]()
      with WritingTransformation[ToConsole, Active]()

}

where

package pdbp.types.toConsole

case class ToConsole(effect: Unit => Unit)

and where

package pdbp.program.active.writing

import pdbp.types.active.activeTypes._
import pdbp.types.active.writing.writingActiveTypes._

import pdbp.writable.Writable

import pdbp.program.Program
import pdbp.program.writing.Writing

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.writing.WritingTransformation

private[pdbp] trait WritingProgram[W: Writable]
    extends Computation[WritingActive[W]]
    with Program[`=>WA`[W]]
    with Writing[W, `=>WA`[W]]
    with ComputationTransformation[Active, WritingActive[W]]
    with WritingTransformation[W, Active]

where the types WritingActive and `=>WA` are defined as follows

package pdbp.types.active.writing

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._
import pdbp.types.active.activeTypes._

import pdbp.computation.transformation.writing.WritingTransformation._

object writingActiveTypes {

  type WritingActive[W] = WritingTransformed[W, Active]

  type `=>WA`[W] = Kleisli[WritingActive[W]]

}

Note that, since there is a type parameter W involved, we first define a trait and second a corresponding implicit object for ToConsole.

Note that we still have to show that ToConsole satisfies the Writable requirements

Describing toConsoleWritable

package pdbp.writable.toConsole

import pdbp.types.product.productType._
import pdbp.types.toConsole.ToConsole

import pdbp.writable.Writable

object implicits {

  implicit object toConsoleWritable extends Writable[ToConsole] {

    override private[pdbp] val start: ToConsole =
      ToConsole { _ =>
        ()
      }

    override private[pdbp] val append: ToConsole && ToConsole => ToConsole = {
      (leftTc, rightTc) =>
        ToConsole { _ =>
          leftTc.effect(())
          rightTc.effect(())
        }
    }

  }

}

ToConsole satisfies the Writable requirements by starting with no effects at all and by appending effects by sequentially executing them.

Describing to console effect executing ComputationMeaningTransformation of WritingTransformed

A computation meaning transformation that transforms a computation meaning to a writng to toConsole transformed computation meaning is the to console effect executing one below

package pdbp.computation.meaning.ofWriting.toConsoleEffectExecuting

import pdbp.types.implicitFunctionType.`I=>`
import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._
import pdbp.types.toConsole.ToConsole

import pdbp.naturalTransformation.unary.`~U~>`

import pdbp.writable.toConsole.implicits.toConsoleWritable

import pdbp.program.writing.Writing

import pdbp.program.meaning.ProgramMeaning

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.writing.WritingTransformation
import pdbp.computation.transformation.writing.WritingTransformation._

import pdbp.computation.meaning.ComputationMeaning

import pdbp.computation.meaning.transformation.ImplicitComputationMeaningTransformation

private[pdbp] trait ComputationMeaningTransformation[
    C[+ _]: Computation, M[+ _]: Computation]
    extends ImplicitComputationMeaningTransformation[
      C,
      M,
      WritingTransformed[ToConsole, C],
      M] {       

  private type WTC = WritingTransformed[ToConsole, C]

  override def apply(implicit computationMeaning: ComputationMeaning[C, M])
    : ComputationMeaning[WTC, M] = {

    import computationMeaning.{unaryTransformation => `c~u~>m`}  

    val implicitComputation = implicitly[Computation[C]]

    import implicitComputation.{result => resultC, bind => bindC}

    implicit object writingComputation
        extends WritingTransformation[ToConsole, C]()
        with ComputationTransformation[C, WTC]()
        with Writing[ToConsole, Kleisli[WTC]]()

    object toConsoleEffectExecutingComputationMeaning
        extends ComputationMeaning[WTC, M]()
        with ProgramMeaning[Kleisli[WTC], Kleisli[M]]() {

      override private[pdbp] lazy val unaryTransformation: WTC `~U~>` M =
        new {
          override private[pdbp] def apply[Z](wtcz: WTC[Z]): M[Z] =
            `c~u~>m`(bindC(wtcz, {
              case (ToConsole(effect), z) =>
                effect(())
                resultC(z)
            }))
        }

    }

    toConsoleEffectExecutingComputationMeaning

  } 

}

Note that this computation meaning transformation is specific for ToConsole.

Note that unaryTransformation of toConsoleEffectExecutingComputationMeaning uses effect(()) to execute the to console effect.

Describing toConsoleEffectExecuting meaning ofToConsoleWriting active

The next computation meaning implicit object (and corresponding kleisli program meaning implicit object) is the toConsole effect executing of toConsole writing transformed active one defined below

package pdbp.program.meaning.active.ofToConsoleWriting

import pdbp.types.toConsole.ToConsole

import pdbp.types.active.activeTypes._
import pdbp.types.active.writing.writingActiveTypes._

import pdbp.program.meaning.ProgramMeaning

import pdbp.computation.meaning.ComputationMeaning

import pdbp.computation.meaning.writing.toConsoleEffectExecuting.WritingTransformedMeaning

import pdbp.program.active.implicits.program
import pdbp.program.active.writing.toConsole.implicits.toConsoleWritingProgram

object implicits {

  import pdbp.program.meaning.active.ofActive.implicits.identity

  implicit object toConsoleEffectExecuting
      extends WritingTransformedMeaning[Active, Active]()
      with ComputationMeaning[WritingActive[ToConsole], Active]()
      with ProgramMeaning[`=>WA`[ToConsole], `=>A`]()

}

Running mainFactorial using active toConsoleWritingProgram, toConsoleEffectExecuting.meaning and run, and using effectfulReadIntFromConsole and write

Consider

package examples.main.active.writing.toConsole.effectfulReading

import pdbp.types.toConsole.ToConsole
import pdbp.types.active.writing.writingActiveTypes._

import pdbp.program.active.writing.toConsole.implicits.toConsoleWritingProgram

import examples.mainPrograms.MainFactorial

object FactorialWrittenMain extends MainFactorial[`=>WA`[ToConsole]]() {

  import examples.utils.EffectfulUtils

  private val effectfulFunctionUtils = new EffectfulUtils[`=>WA`[ToConsole]]

  import effectfulFunctionUtils._

  override val producer = effectfulReadIntFromConsole

  import examples.utils.implicits.convertFactorialOfIntToToConsole

  override val consumer = toConsoleWritingProgram.write

  def main(args: Array[String]): Unit = {

    import pdbp.program.meaning.active.ofToConsoleWriting.implicits.toConsoleEffectExecuting.meaning

    import pdbp.run.active.run

    run(meaning(mainFactorial))

  }
}

where

package examples.utils

// ...

import pdbp.utils.toConsoleUtils._

object implicits {

  // ...

  // effectfree toConsole related

  implicit lazy val convertFactorialOfIntToToConsole: BigInt => ToConsole =
    lineToToConsoleWithMessage(
      "the factorial value of the integer is"
    )
  
  // ...

}    

where

package pdbp.utils

import pdbp.types.toConsole.ToConsole

import pdbp.utils.effectfulFunctionUtils._

object toConsoleUtils {

  def lineToToConsoleWithMessage[Z](
      message: String): Z => ToConsole = { z =>
    ToConsole({ _ =>
      effectfulWriteLineToConsoleWithMessageFunction(message)(z)
    })
  }

  // ...

}  

For being able to run mainFactorial, we have to define the implicit BigInt => ToConsole of write to convert a ``Bigint to ToConsole. We can postpone defining this to the body of FactorialConsoleWrittenMain and we can simply do this by importing implicit lazy val convertFactorialOfIntToToConsole`.

Note that we cannot postpone to the body of main since write depends on it.

Let’s try running factorial with 10.

[info] Running examples.main.active.writing.toConsole.effectfulReading.FactorialConsoleWrittenMain
please type an integer
10
the factorial value of the integer is
3628800

Describing active intReadingToConsoleWritingProgram

The next computation implicit object (and corresponding kleisli program implicit object) is the active intReadingToConsoleWritingProgram one defined below

package pdbp.program.active.writing.toConsole.reading.int

import pdbp.types.active.activeTypes._
import pdbp.types.active.writing.writingActiveTypes._
import pdbp.types.active.writing.reading.readingWritingActiveTypes._
import pdbp.types.toConsole.ToConsole

import pdbp.writable.toConsole.implicits.toConsoleWritable

import pdbp.program.Program

import pdbp.program.reading.Reading

import pdbp.program.writing.Writing

import pdbp.program.active.writing.reading.ReadingWritingProgram

import pdbp.program.active.writing.toConsole.implicits.toConsoleWritingProgram

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.reading.ReadingTransformation

import pdbp.computation.transformation.writing.reading.ReadingWritingTransformation

object implicits {

  implicit object intReadingToConsoleWritingProgram
      extends ReadingWritingProgram[BigInt, ToConsole]()
      with Computation[ReadingWritingActive[BigInt, ToConsole]]()
      with Program[`=>RWA`[BigInt, ToConsole]]()
      with Reading[BigInt, `=>RWA`[BigInt, ToConsole]]()
      with Writing[ToConsole, `=>RWA`[BigInt, ToConsole]]()
      with ComputationTransformation[
        WritingActive[ToConsole],
        ReadingWritingActive[BigInt, ToConsole]]()
      with ReadingTransformation[BigInt, WritingActive[ToConsole]]()
      with ReadingWritingTransformation[BigInt,
                                            ToConsole,
                                            WritingActive[ToConsole]]()
}

where

package pdbp.program.active.writing.reading

import pdbp.types.active.writing.writingActiveTypes._
import pdbp.types.active.writing.reading.readingWritingActiveTypes._

import pdbp.writable.Writable

import pdbp.program.Program
import pdbp.program.reading.Reading
import pdbp.program.writing.Writing

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.writing.reading.ReadingWritingTransformation

private[pdbp] trait ReadingWritingProgram[R, W: Writable]
    extends Computation[ReadingWritingActive[R, W]]
    with Program[`=>RWA`[R, W]]
    with Reading[R, `=>RWA`[R, W]]
    with Writing[W, `=>RWA`[R, W]]
    with ComputationTransformation[WritingActive[W],
                                   ReadingWritingActive[R, W]]
    with ReadingWritingTransformation[R, W, WritingActive[W]]

where the types ReadingWritingActive and `=>RWA` are defined as follows

package pdbp.types.active.writing.reading

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._
import pdbp.types.active.writing.writingActiveTypes._

import pdbp.computation.transformation.reading.ReadingTransformation._

object readingWritingActiveTypes {

  type ReadingWritingActive[R, W] = ReadingTransformed[R, WritingActive[W]]

  type `=>RWA`[R, W] = Kleisli[ReadingWritingActive[R, W]]

}

and where

package pdbp.computation.transformation.writing.reading

import pdbp.types.implicitFunctionType._
import pdbp.types.product.productType._
import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.writable.Writable

import pdbp.program.writing.Writing

import pdbp.computation.Computation

import pdbp.computation.transformation.reading.ReadingTransformation
import pdbp.computation.transformation.reading.ReadingTransformation._

private[pdbp] trait ReadingWritingTransformation[
    R, W: Writable, 
    C[+ _]: Computation
          : [C[+ _]] => Writing[W, Kleisli[C]]]
    extends ReadingTransformation[R, C]
    with Writing[W, Kleisli[ReadingTransformed[R, C]]] {

  private val implicitWriting: Writing[W, Kleisli[C]] =
    implicitly[Writing[W, Kleisli[C]]]

  private type RTC = ReadingTransformed[R, C]

  private type `=>RTC` = Kleisli[RTC]

  override private[pdbp] val `w>-->u`: W `=>RTC` Unit = { w =>
    implicitWriting.`w>-->u`(w)
  }

}

Describing toConsoleEffectExecutingImplicitIntReading meaning ofIntReadingToConsoleWriting active

The next computation meaning implicit object (and corresponding kleisli program meaning implicit object) is the console effect executing of int reading to console writing active one defined below

package pdbp.program.meaning.active.ofIntReadingToConsoleWriting

import pdbp.types.toConsole.ToConsole

import pdbp.types.active.activeTypes._
import pdbp.types.active.reading.readingActiveTypes._
import pdbp.types.active.writing.writingActiveTypes._
import pdbp.types.active.writing.reading.readingWritingActiveTypes._

import pdbp.naturalTransformation.unary.`~U~>`

import pdbp.program.meaning.ProgramMeaning

import pdbp.computation.meaning.ComputationMeaning

import pdbp.computation.meaning.transformation.ImplicitComputationMeaningTransformation

import pdbp.computation.meaning.ofReading.readingImplicit.ComputationMeaningTransformation

import pdbp.program.active.implicits.program
import pdbp.program.active.writing.toConsole.implicits.toConsoleWritingProgram
import pdbp.program.active.writing.toConsole.reading.int.implicits.intReadingToConsoleWritingProgram

import pdbp.program.active.reading.int.implicits.intReadingProgram

import pdbp.program.meaning.active.ofActive.implicits.identity

import pdbp.program.meaning.active.ofToConsoleWriting.implicits.toConsoleEffectExecuting

object implicits {

  implicit object toConsoleEffectExecutingImplicitIntReading
      extends ComputationMeaningTransformation[BigInt,
                                        WritingActive[ToConsole],
                                        Active]()
      with ImplicitComputationMeaningTransformation[WritingActive[ToConsole], Active, ReadingWritingActive[BigInt, ToConsole], ReadingActive[BigInt]]()                                  
      with ComputationMeaning[ReadingWritingActive[BigInt, ToConsole],
                              ReadingActive[BigInt]]()
      with ProgramMeaning[`=>RWA`[BigInt, ToConsole], `=>RA`[BigInt]]() {

  override private[pdbp] implicit lazy val implicitComputationMeaning = 
    toConsoleEffectExecuting
 
  }

}

Running mainFactorial using active intReadingToConsoleWritingProgram, toConsoleEffectExecutingImplicitIntReading.meaning and reading.run, and using read and write

Consider

package examples.main.active.writing.toConsole.reading.int

import pdbp.types.toConsole.ToConsole
import pdbp.types.active.writing.reading.readingWritingActiveTypes._

import pdbp.program.active.writing.toConsole.reading.int.implicits.intReadingToConsoleWritingProgram

import examples.mainPrograms.MainFactorial

object FactorialOfReadWrittenMain
    extends MainFactorial[`=>RWA`[BigInt, ToConsole]]() {

  override val producer = intReadingToConsoleWritingProgram.read

  import examples.utils.implicits.convertFactorialOfIntReadToToConsole

  override val consumer = intReadingToConsoleWritingProgram.write

  def main(args: Array[String]): Unit = {

    import examples.utils.implicits.intEffectfullyReadFromConsole

    import pdbp.program.meaning.active.ofIntReadingToConsoleWriting.implicits.toConsoleEffectExecutingImplicitIntReading.meaning

    import pdbp.run.active.reading.run

    run(meaning(mainFactorial))

  }
  
}

where convertFactorialOfIntReadToToConsole implements, effectfree, the conversion function of type BigInt => ToConsole that is implicitly read by by write.

package examples.utils

// ...

import pdbp.types.toConsole.ToConsole

// ...

import pdbp.utils.toConsoleUtils._

object implicits {
  
  // ...

  implicit lazy val convertFactorialOfIntReadToToConsole
    : BigInt => ToConsole =
    lineToToConsoleWithMessage(
      "the factorial value of the integer read is

  // ...

}      

where

package pdbp.utils

import pdbp.types.toConsole.ToConsole

import pdbp.utils.effectfulFunctionUtils._

object toConsoleUtils {

  def lineToToConsoleWithMessage[Z](
      message: String): Z => ToConsole = { z =>
    ToConsole({ _ =>
      effectfulWriteLineToConsoleWithMessageFunction(message)(z)
    })
  }

  // ... 

}

For being able to run mainFactorial, we have to define the implicit BigInt => ToConsole of write. We can postpone defining this to the body of FactorialOfReadWrittenMain and we can simply do this by importing implicit lazy val convertFactorialOfIntReadToToConsole.

Note that we cannot postpone to the body of main since write depends on it.

Let’s try factorial with 10.

[info] Running examples.main.active.writing.toConsole.reading.int.FactorialOfReadWrittenMain
please type an integer to read
10
the factorial value of the integer read is
3628800

Let’s try factorial with 100.

[info] Running examples.main.active.writing.toConsole.reading.int.FactorialOfReadWrittenMain
please type an integer
100
the factorial value of the integer is
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Note that we use write as a consumer at the end of a program.

Describing ProgramInfoWritingFactorial

We can use write in the middle of a program.

Consider

package examples.programs.writing

import pdbp.types.implicitFunctionType._

import pdbp.utils.infoUtils._

import pdbp.writable.Writable

import pdbp.program.Program
import pdbp.program.writing.Writing

import pdbp.program.compositionOperator._

import examples.programs.HelperPrograms

class ProgramInfoWritingFactorial[
    W: Writable,
    >-->[- _, + _]: Program
                  : [>-->[- _, + _]] => Writing[W, >-->]]
    extends ProgramInfoWritingAtomicPrograms[W, >-->]() 
    with HelperPrograms[>-->]() {

  private val implicitProgram = implicitly[Program[>-->]]

  private val implicitWriting = implicitly[Writing[W, >-->]]

  import implicitProgram._

  val programInfoWritingFactorial: (Info => W) `I=>` BigInt >--> BigInt =
    programInfo("factorial") {
      `if`(isZero) {
        one
      } `else` {
        `let` {
          subtractOne >-->
            programInfoWritingFactorial
        } `in` {
          multiply
        }
      }
    }

}

where

package examples.programs.writing

import pdbp.types.implicitFunctionType._
import pdbp.types.product.productType._

import pdbp.utils.infoUtils._

import pdbp.writable.Writable

import pdbp.program.Function
import pdbp.program.writing.Writing

import examples.programs.HelperPrograms

trait ProgramInfoWritingAtomicPrograms[
    W: Writable, 
    >-->[- _, + _]: Function
                  : [>-->[- _, + _]] => Writing[W, >-->]]
    extends HelperPrograms[>-->] {

  private val implicitFunction = implicitly[Function[>-->]]

  private val implicitWriting = implicitly[Writing[W, >-->]]

  import implicitFunction._

  import implicitWriting._

  private[examples] def programInfo[Z, Y](
      programName: String): (Z >--> Y) => ((Info => W) `I=>` Z >--> Y) =
    writingInfo { (z, y) => 
      s"$programName($z) => $y"
    } 

  val isZero: (Info => W) `I=>` BigInt >--> Boolean =
    programInfo("isZero") {
      isZeroHelper
    }

  val subtractOne: (Info => W) `I=>` BigInt >--> BigInt =
    programInfo("subtractOne") {
      subtractOneHelper
    }

  val multiply: (Info => W) `I=>` (BigInt && BigInt) >--> BigInt =
    programInfo("multiply") {
      multiplyHelper
    }

  def one[Z]: (Info => W) `I=>` Z >--> BigInt =
    programInfo("one") {
      oneHelper
    }

  // ...

}

Note that we define programInfo in terms of writingInfo which, itself, is, indirectly, defined in terms of `z>-w->u`, a synonym of write.

Describing mainProgramInfoWritingFactorial

Consider

import pdbp.types.implicitFunctionType._

import pdbp.utils.infoUtils._

import pdbp.writable.Writable

import pdbp.program.Program
import pdbp.program.writing.Writing

import pdbp.program.compositionOperator._

import examples.programs.writing.ProgramInfoWritingFactorial

trait MainProgramInfoWritingFactorial[
    W: Writable,
    >-->[- _, + _]: Program
                  : [>-->[- _, + _]] => Writing[W, >-->]] {

  private object programInfoWritingFactorialObject extends ProgramInfoWritingFactorial[W, >-->]

  import programInfoWritingFactorialObject.programInfoWritingFactorial

  val producer: Unit >--> BigInt

  val consumer: BigInt >--> Unit

  lazy val mainProgramInfoWritingFactorial: (Info => W) `I=>` Unit >--> Unit = {
    producer >-->
    programInfoWritingFactorial >-->
      consumer
  }

}

trait MainProgramInfoWritingFactorial defines lazy val mainProgramInfoWritingFactorial using abstract members producer and consumer.

Running mainProgramInfoWritingFactorial using active intReadingToConsoleWritingProgram, toConsoleEffectExecutingImplicitIntReading.meaning and reading.run, and using read and write

Consider

package examples.main.active.writing.toConsole.reading.int

import pdbp.types.toConsole.ToConsole
import pdbp.types.active.reading.readingActiveTypes._
import pdbp.types.active.writing.reading.readingWritingActiveTypes._

import pdbp.writable.toConsole.implicits.toConsoleWritable

import pdbp.program.active.writing.toConsole.reading.int.implicits.intReadingToConsoleWritingProgram

import examples.mainPrograms.writing.MainProgramInfoWritingFactorial

object FactorialOfReadProgramInfoWritingWrittenMain
    extends MainProgramInfoWritingFactorial[ToConsole, `=>RWA`[BigInt, ToConsole]]() {

  override val producer = intReadingToConsoleWritingProgram.read

  import examples.utils.implicits.convertFactorialOfIntReadToToConsole

  override val consumer = intReadingToConsoleWritingProgram.write

  def main(args: Array[String]): Unit = {

    import examples.utils.implicits.intEffectfullyReadFromConsole

    import examples.utils.implicits.convertInfoToToConsole

    import pdbp.program.meaning.active.ofIntReadingToConsoleWriting.implicits.toConsoleEffectExecutingImplicitIntReading.meaning

    import pdbp.run.active.reading.run

    run(meaning(mainProgramInfoWritingFactorial))

  }

}

where convertInfoToToConsole implements, effectfree, the conversion of type Info => ToConsole that is implicitly read by by info.

package examples.utils

// ...

import pdbp.utils.infoUtils._

// ...

import pdbp.types.toConsole.ToConsole

// ...


object implicits {
  
  // ...

  implicit lazy val convertInfoToToConsole: Info => ToConsole =
    infoToToConsole

  // ...

}      

where

package pdbp.utils

import pdbp.types.toConsole.ToConsole

import pdbp.utils.effectfulFunctionUtils._

object infoUtils {

  // ...

  def infoToToConsole[Z]: Info => ToConsole = { info =>
    ToConsole({ _ =>
      effectfulWriteToConsoleWithMessageFunction("")(info.toString)
    })
  }

}

For being able to run mainProgramInfoWritingFactorial, we have to define the implicit Info => ToConsole of programInfo. We can postpone defining this to the body of main and we can simply do this by importing implicit lazy val convertInfoToToConsole.

Let’s try mainProgramInfoWritingFactorial with 10.

[info] Running examples.main.active.writing.toConsole.reading.int.FactorialOfReadProgramInfoWritingWrittenMain
please type an integer to read
10
[INFO] when 10955835403039 who 611 what isZero(10) => false
[INFO] when 10955846199127 who 611 what subtractOne(10) => 9
[INFO] when 10955846748060 who 611 what isZero(9) => false
[INFO] when 10955847249617 who 611 what subtractOne(9) => 8
[INFO] when 10955847772962 who 611 what isZero(8) => false
[INFO] when 10955848258402 who 611 what subtractOne(8) => 7
[INFO] when 10955848858670 who 611 what isZero(7) => false
[INFO] when 10955849426093 who 611 what subtractOne(7) => 6
[INFO] when 10955849986137 who 611 what isZero(6) => false
[INFO] when 10955850648273 who 611 what subtractOne(6) => 5
[INFO] when 10955851180620 who 611 what isZero(5) => false
[INFO] when 10955851726277 who 611 what subtractOne(5) => 4
[INFO] when 10955852280942 who 611 what isZero(4) => false
[INFO] when 10955852772915 who 611 what subtractOne(4) => 3
[INFO] when 10955853278214 who 611 what isZero(3) => false
[INFO] when 10955853760907 who 611 what subtractOne(3) => 2
[INFO] when 10955854261740 who 611 what isZero(2) => false
[INFO] when 10955854753202 who 611 what subtractOne(2) => 1
[INFO] when 10955855355199 who 611 what isZero(1) => false
[INFO] when 10955855885986 who 611 what subtractOne(1) => 0
[INFO] when 10955856387714 who 611 what isZero(0) => true
[INFO] when 10955857574365 who 611 what one(0) => 1
[INFO] when 10955857914629 who 611 what factorial(0) => 1
[INFO] when 10955858380583 who 611 what multiply((1,1)) => 1
[INFO] when 10955858754606 who 611 what factorial(1) => 1
[INFO] when 10955859197491 who 611 what multiply((2,1)) => 2
[INFO] when 10955859555028 who 611 what factorial(2) => 2
[INFO] when 10955859970976 who 611 what multiply((3,2)) => 6
[INFO] when 10955860332409 who 611 what factorial(3) => 6
[INFO] when 10955860759521 who 611 what multiply((4,6)) => 24
[INFO] when 10955861128005 who 611 what factorial(4) => 24
[INFO] when 10955861569733 who 611 what multiply((5,24)) => 120
[INFO] when 10955861907178 who 611 what factorial(5) => 120
[INFO] when 10955862373133 who 611 what multiply((6,120)) => 720
[INFO] when 10955862719819 who 611 what factorial(6) => 720
[INFO] when 10955863190180 who 611 what multiply((7,720)) => 5040
[INFO] when 10955863568641 who 611 what factorial(7) => 5040
[INFO] when 10955863997724 who 611 what multiply((8,5040)) => 40320
[INFO] when 10955864361910 who 611 what factorial(8) => 40320
[INFO] when 10955864818112 who 611 what multiply((9,40320)) => 362880
[INFO] when 10955865154133 who 611 what factorial(9) => 362880
[INFO] when 10955865604672 who 611 what multiply((10,362880)) => 3628800
[INFO] when 10955865941398 who 611 what factorial(10) => 3628800
the factorial value of the integer read is
3628800

Stack safety and pure I/O

In the previous sections we have been faced with two problems

and we solved both problems separately using program transformers and program meanings.

In this section we solve both problems together.

In a way, solving impure I/0 is also solving two problems: impure reading and impure writing. We solved the two problems separately but we also solved the two problems together by composing program transformers and program meanings.

Program transformers and program meanings can also be composed to solve the stack unsafety and impure I/O problems together.

Describing FreeReadingWritingTransformation

Consider

package pdbp.computation.transformation.writing.reading.free

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.program.reading.Reading

import pdbp.writable.Writable

import pdbp.program.writing.Writing

import pdbp.computation.Computation

import pdbp.computation.transformation.free.FreeTransformation

import pdbp.computation.transformation.free.FreeTransformation._

private[pdbp] trait FreeReadingWritingTransformation[
    R, W: Writable, 
    C[+ _]: Computation
          : [C[+ _]] => Reading[R, Kleisli[C]]
          : [C[+ _]] => Writing[W, Kleisli[C]]]
    extends FreeTransformation[C]
    with Reading[R, Kleisli[FreeTransformed[C]]]
    with Writing[W, Kleisli[FreeTransformed[C]]] {

  private val implicitReading: Reading[R, Kleisli[C]] =
    implicitly[Reading[R, Kleisli[C]]]

  private val implicitWriting: Writing[W, Kleisli[C]] =
    implicitly[Writing[W, Kleisli[C]]]

  private type FTC = FreeTransformed[C]

  private type `=>FTC` = Kleisli[FTC]

  override private[pdbp] val `u>-->r`: Unit `=>FTC` R = { u =>
    Transform(implicitReading.`u>-->r`(u))
  }  

  override private[pdbp] val `w>-->u`: W `=>FTC` Unit = { w =>
    Transform(implicitWriting.`w>-->u`(w))
  }

}

The implementations of `u>-->r` and `w>-->u` are simple. They wrap the implicitly available ones in a Transform.

###Describing FreeReadingWritingProgram

Consider

package pdbp.program.active.writing.reading.free

import pdbp.types.active.writing.reading.readingWritingActiveTypes._

import pdbp.types.active.writing.reading.free.freeReadingWritingActiveTypes._

import pdbp.writable.Writable

import pdbp.program.Program

import pdbp.program.reading.Reading

import pdbp.program.writing.Writing

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation

import pdbp.computation.transformation.writing.reading.free.FreeReadingWritingTransformation

private[pdbp] trait FreeReadingWritingProgram[R, W: Writable]
    extends Computation[FreeReadingWritingActive[R, W]]
    with Program[`=>FRWA`[R, W]]
    with Reading[R, `=>FRWA`[R, W]]
    with Writing[W, `=>FRWA`[R, W]]
    with ComputationTransformation[ReadingWritingActive[R, W],
                                   FreeReadingWritingActive[R, W]]
    with FreeReadingWritingTransformation[R, W, ReadingWritingActive[R, W]]

where the types FreeReadingWritingActive and `=>FRWA` are defined below

package pdbp.types.active.writing.reading.free

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.types.active.writing.reading.readingWritingActiveTypes._

import pdbp.computation.transformation.free.FreeTransformation._

object freeReadingWritingActiveTypes {

  type FreeReadingWritingActive[R, W] =
    FreeTransformed[ReadingWritingActive[R, W]]

  type `=>FRWA`[R, W] = Kleisli[FreeReadingWritingActive[R, W]]

}

###Describing freeIntReadingConsoleWritingProgram

package pdbp.program.active.writing.toConsole.reading.int.free

import pdbp.types.toConsole.ToConsole

import pdbp.types.active.writing.reading.readingWritingActiveTypes._
import pdbp.types.active.writing.reading.free.freeReadingWritingActiveTypes._

import pdbp.program.Program
import pdbp.program.reading.Reading
import pdbp.program.writing.Writing

import pdbp.writable.toConsole.implicits.toConsoleWritable

import pdbp.program.active.writing.reading.free.FreeReadingWritingProgram
import pdbp.program.active.writing.toConsole.reading.int.implicits.intReadingToConsoleWritingProgram

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.free.FreeTransformation

import pdbp.computation.transformation.writing.reading.free.FreeReadingWritingTransformation

object implicits {

  implicit object freeIntReadingToConsoleWritingProgram
      extends FreeReadingWritingProgram[BigInt, ToConsole]()
      with Computation[FreeReadingWritingActive[BigInt, ToConsole]]()
      with Program[`=>FRWA`[BigInt, ToConsole]]()
      with Reading[BigInt, `=>FRWA`[BigInt, ToConsole]]()
      with Writing[ToConsole, `=>FRWA`[BigInt, ToConsole]]()
      with ComputationTransformation[
        ReadingWritingActive[BigInt, ToConsole],
        FreeReadingWritingActive[BigInt, ToConsole]]()
      with FreeTransformation[ReadingWritingActive[BigInt, ToConsole]]()
      with FreeReadingWritingTransformation[
        BigInt,
        ToConsole,
        ReadingWritingActive[BigInt, ToConsole]]()

}

Describing tailrecFoldingToConsoleEffectExecutingImplicitIntReading meaning ofFreeIntReadingToConsoleWriting active

package pdbp.program.meaning.active.ofFreeIntReadingToConsoleWriting

import pdbp.types.toConsole.ToConsole

import pdbp.types.active.reading.readingActiveTypes._
import pdbp.types.active.writing.reading.readingWritingActiveTypes._
import pdbp.types.active.writing.reading.free.freeReadingWritingActiveTypes._

import pdbp.program.meaning.ProgramMeaning

import pdbp.computation.meaning.ComputationMeaning

import pdbp.program.active.reading.int.implicits.intReadingProgram
import pdbp.program.active.writing.toConsole.reading.int.implicits.intReadingToConsoleWritingProgram
import pdbp.program.active.writing.toConsole.reading.int.free.implicits.freeIntReadingToConsoleWritingProgram

import pdbp.computation.meaning.transformation.ImplicitComputationMeaningTransformation

import pdbp.computation.meaning.ofFree.tailrecFolding.ComputationMeaningTransformation
import pdbp.program.meaning.active.ofIntReadingToConsoleWriting.implicits.toConsoleEffectExecutingImplicitIntReading

object implicits {

  implicit object tailrecFoldingToConsoleEffectExecutingImplicitIntReading
      extends ComputationMeaningTransformation[
        ReadingWritingActive[BigInt, ToConsole],
        ReadingActive[BigInt]]()
      with ImplicitComputationMeaningTransformation[
        ReadingWritingActive[BigInt, ToConsole],
        ReadingActive[BigInt],
        FreeReadingWritingActive[BigInt, ToConsole],
        ReadingActive[BigInt]]()
      with ComputationMeaning[FreeReadingWritingActive[BigInt, ToConsole],
                              ReadingActive[BigInt]]()
      with ProgramMeaning[`=>FRWA`[BigInt, ToConsole], `=>RA`[BigInt]]() {

    override private[pdbp] implicit lazy val implicitComputationMeaning =
      toConsoleEffectExecutingImplicitIntReading

  }

}

Running mainFactorial using active freeIntReadingToConsoleWritingProgram, tailrecFoldingToConsoleEffectExecutingImplicitIntReading.meaning and reading.run, and using read and write

Consider

package examples.main.active.writing.toConsole.reading.int.free

import pdbp.types.toConsole.ToConsole

import pdbp.types.active.writing.reading.free.freeReadingWritingActiveTypes._

import pdbp.program.active.writing.toConsole.reading.int.free.implicits.freeIntReadingToConsoleWritingProgram

import examples.mainPrograms.MainFactorial

object FactorialOfReadWrittenMain
    extends MainFactorial[`=>FRWA`[BigInt, ToConsole]]() {

  override val producer = freeIntReadingToConsoleWritingProgram.read

  import examples.utils.implicits.convertFactorialOfIntReadToToConsole

  override val consumer = freeIntReadingToConsoleWritingProgram.write

  def main(args: Array[String]): Unit = {

    import examples.utils.implicits.intEffectfullyReadFromConsole

    import pdbp.program.meaning.active.ofFreeIntReadingToConsoleWriting.implicits.tailrecFoldingToConsoleEffectExecutingImplicitIntReading.meaning

    import pdbp.run.active.reading.run

    run(meaning(mainFactorial))

  }

}

Let’s try factorial with 1000.

[info] Running examples.main.active.writing.toConsole.reading.int.free.FactorialOfReadWrittenMain
please type an integer to read
1000
the factorial value of the integer read is
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Great, the two problems, stack unsafety and impure I/O are both solved.

Running mainProgramInfoWritingFactorial using active freeIntReadingToConsoleWritingProgram, tailrecFoldingToConsoleEffectExecutingImplicitIntReading.meaning and reading.run, and using read and write

Consider

package examples.main.active.writing.toConsole.reading.int.free

import pdbp.types.toConsole.ToConsole
import pdbp.types.active.reading.readingActiveTypes._
import pdbp.types.active.writing.reading.free.freeReadingWritingActiveTypes._

import pdbp.writable.toConsole.implicits.toConsoleWritable

import pdbp.program.active.writing.toConsole.reading.int.free.implicits.freeIntReadingToConsoleWritingProgram

import examples.mainPrograms.writing.MainProgramInfoWritingFactorial

object FactorialOfReadProgramInfoWritingWrittenMain
    extends MainProgramInfoWritingFactorial[ToConsole, `=>FRWA`[BigInt, ToConsole]]() {

  override val producer = freeIntReadingToConsoleWritingProgram.read

  import examples.utils.implicits.convertFactorialOfIntReadToToConsole

  override val consumer = freeIntReadingToConsoleWritingProgram.write

  def main(args: Array[String]): Unit = {

    import examples.utils.implicits.intEffectfullyReadFromConsole

    import examples.utils.implicits.convertInfoToToConsole

    import pdbp.program.meaning.active.ofFreeIntReadingToConsoleWriting.implicits.tailrecFoldingToConsoleEffectExecutingImplicitIntReading.meaning

    import pdbp.run.active.reading.run

    run(meaning(mainProgramInfoWritingFactorial))

  }
  
}

Let’s try programInfoWritingFactorial with 10.

[info] Running examples.main.active.writing.toConsole.reading.int.free.FactorialOfReadProgramInfoWritingWrittenMain
please type an integer to read
10
[INFO] when 7478040215171 who 97 what isZero(10) => false
[INFO] when 7478047352947 who 97 what subtractOne(10) => 9
[INFO] when 7478047658661 who 97 what isZero(9) => false
[INFO] when 7478048031028 who 97 what subtractOne(9) => 8
[INFO] when 7478048279297 who 97 what isZero(8) => false
[INFO] when 7478048668117 who 97 what subtractOne(8) => 7
[INFO] when 7478048944987 who 97 what isZero(7) => false
[INFO] when 7478049294742 who 97 what subtractOne(7) => 6
[INFO] when 7478049552209 who 97 what isZero(6) => false
[INFO] when 7478049933088 who 97 what subtractOne(6) => 5
[INFO] when 7478050188554 who 97 what isZero(5) => false
[INFO] when 7478050515306 who 97 what subtractOne(5) => 4
[INFO] when 7478050807621 who 97 what isZero(4) => false
[INFO] when 7478051079175 who 97 what subtractOne(4) => 3
[INFO] when 7478051334493 who 97 what isZero(3) => false
[INFO] when 7478051587647 who 97 what subtractOne(3) => 2
[INFO] when 7478051820651 who 97 what isZero(2) => false
[INFO] when 7478052067966 who 97 what subtractOne(2) => 1
[INFO] when 7478052291596 who 97 what isZero(1) => false
[INFO] when 7478052517168 who 97 what subtractOne(1) => 0
[INFO] when 7478052710241 who 97 what isZero(0) => true
[INFO] when 7478053512993 who 97 what one(0) => 1
[INFO] when 7478053622525 who 97 what factorial(0) => 1
[INFO] when 7478053798129 who 97 what multiply((1,1)) => 1
[INFO] when 7478053917707 who 97 what factorial(1) => 1
[INFO] when 7478054036677 who 97 what multiply((2,1)) => 2
[INFO] when 7478054132744 who 97 what factorial(2) => 2
[INFO] when 7478054253951 who 97 what multiply((3,2)) => 6
[INFO] when 7478054370977 who 97 what factorial(3) => 6
[INFO] when 7478054491050 who 97 what multiply((4,6)) => 24
[INFO] when 7478054582760 who 97 what factorial(4) => 24
[INFO] when 7478054704672 who 97 what multiply((5,24)) => 120
[INFO] when 7478054794619 who 97 what factorial(5) => 120
[INFO] when 7478054918409 who 97 what multiply((6,120)) => 720
[INFO] when 7478055009383 who 97 what factorial(6) => 720
[INFO] when 7478055123105 who 97 what multiply((7,720)) => 5040
[INFO] when 7478055227692 who 97 what factorial(7) => 5040
[INFO] when 7478055335555 who 97 what multiply((8,5040)) => 40320
[INFO] when 7478055411803 who 97 what factorial(8) => 40320
[INFO] when 7478055520017 who 97 what multiply((9,40320)) => 362880
[INFO] when 7478055597672 who 97 what factorial(9) => 362880
[INFO] when 7478055700628 who 97 what multiply((10,362880)) => 3628800
[INFO] when 7478055779044 who 97 what factorial(10) => 3628800
the factorial value of the integer read is
3628800

Describing LatencyHandling

Introduction

In sections Program and Computation we presented the basic programming and computation capabilities.

In sections Reading and Writing we presented two extra programming capabilities, reading and writing.

In section FreeTransformation we presented no extra programming capabilities, but we presented tail recursion instead.

In this section, LatencyHandling, we introduce the next extra programming capability: latency handling.

We will deal with lantency handling by going reactive.

Describing LatencyHandling

Consider

import pdbp.types.product.productType._

import pdbp.program.Function
import pdbp.program.Composition

trait LatencyHandling[>-->[- _, + _]] {
  this: Function[>-->] & Composition[>-->] =>

  def parProduct[Z, Y, X](`z>-->y`: Z >--> Y,
                          `z>-->x`: Z >--> X): Z >--> (Y && X) =
    parProduct(`z>-->y`, `z>-->x`, `(y&&x)>-->(y&&x)`)

  def parProduct[Z, Y, X, W](`z>-->y`: Z >--> Y,
                             `z>-->x`: Z >--> X,
                             `(y&&x)>-->w`: => (Y && X) >--> W): Z >--> W =
    seqCompose(function(z => (z, z)),
               seqCompose(parCompose(`z>-->y`, `z>-->x`), `(y&&x)>-->w`))

  def parCompose[Z, X, Y, W](`z>-->x`: Z >--> X,
                             `y>-->w`: Y >--> W): (Z && Y) >--> (X && W) =
    parProduct(seqCompose(`(z&&y)>-->z`, `z>-->x`),
               seqCompose(`(z&&y)>-->y`, `y>-->w`))

  def async[Z, Y](`z>-->y`: Z >--> Y): Z >--> Y =
    seqCompose(seqCompose(`z>-->z&&u`, parCompose(`z>-->y`, `u>-->u`)),
               `(y&&u)>-->y`)

}

where

are the programs you expect

trait Function[>-->[- _, + _]] {
  
  // ...

  val `u>-->u`: Unit >--> Unit =
    function(`u=>u`)

   def `(y&&u)>-->y`[Y]: (Y && Unit) >--> Y =
    function(`(y&&u)=>y`)

   def `z>-->z&&u`[Z]: Z >--> (Z && Unit) =
    function(`z=>z&&u`)      

  // ...

}

where

object functionUtils {

 // ...

  val `u=>u`: Unit => Unit = { _ =>
    ()
  }

  // ...

}

and

object functionUtils {

 // ...

  def `(y&&u)=>y`[Y]: (Y && Unit) => Y = { (y, _) =>
    y
  } 

  def `z=>z&&u`[Z]: Z => Z && Unit = { z =>
    (z, ())
  }

  // ...

}

parProduct(`z>-->y`, `z>-->x`) yields a result constructed in parallel, from the results yielded by z>-->y and z>-->x.

trait LatencyHandling has three other members

parCompose(`z>-->y`, `y>-->x`) is the parallel composition of z>-->y and y>-->x.

async(`z>-->y`) is an asynchronous version of z>-->y.

Note that

Consider

object latencyHandlingOperators {

  implicit class LatencyHandlingOperators[>-->[- _, + _]: LatencyHandling, -Z,
  +Y](`z>-->y`: Z >--> Y) {

    import implicitly._

    def |&|[ZZ <: Z, X](`zz>-->x`: ZZ >--> X) =
      parProduct(`z>-->y`, `zz>-->x`)

    def |&&|[X, W](`x>-->w`: X >--> W) =
      parCompose(`z>-->y`, `x>-->w`)

  }

}

Describing LatencyHandlingTransformation

There are many ways to deal with latency handling.

The way we deal with it is by going reactive.

Consider

package pdbp.computation.transformation.reactive

import LatencyHandlingTransformation._

import akka.actor.{ActorSystem, Actor, ActorRef, Props}

import pdbp.types.product.productType._
import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.utils.actorUtils._

import pdbp.naturalTransformation.unary.`~U~>`

import pdbp.program.Program
import pdbp.program.latencyHandling.LatencyHandling

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation

private[pdbp] trait LatencyHandlingTransformation[C[+ _]: Computation]
    extends ComputationTransformation[C, ReactiveTransformed[C]]
    with LatencyHandling[Kleisli[ReactiveTransformed[C]]] {

  private type RTC = ReactiveTransformed[C]

  import implicitly.{result => resultC}
  import implicitly.{bind => bindC}

  override private[pdbp] val transform: C `~U~>` RTC = new {
    override private[pdbp] def apply[Z](cz: C[Z]): RTC[Z] = { `cz=>u` =>
      `cz=>u`(cz)
    }
  }

  override private[pdbp] def bind[Z, Y](rtcz: RTC[Z],
                                        `z=>rtcy`: => (Z => RTC[Y])): RTC[Y] = {
    `cy=>u` =>
      rtcz { cz =>
        bindC(cz, { z =>
          resultC(`z=>rtcy`(z)(`cy=>u`))
        })
      }
  }

  case object React

  override def parCompose[Z, X, Y, W](
      `z=>rtcx`: Z => RTC[X],
      `y=>rtcw`: Y => RTC[W]): (Z && Y) => RTC[X && W] = {
    (z, y) => `c(x,w)=>u` =>
      val mainActor = actorSystem.actorOf(
        props = Props(new Actor {
          private val `option[x]&&option[w]=>receive`
            : (Option[X] && Option[W]) => Receive = {
            case (optionX, optionW) => {
              case Left(any) =>
                val x: X = any.asInstanceOf[X]
                optionW match {
                  case Some(w) =>
                    `c(x,w)=>u`(resultC((x, w)))
                    context.stop(self)
                  case None =>
                    context.become(
                      `option[x]&&option[w]=>receive`((Some(x), None)))
                }
              case Right(any) =>
                val w = any.asInstanceOf[W]
                optionX match {
                  case Some(x) =>
                    `c(x,w)=>u`(resultC((x, w)))
                    context.stop(self)
                  case None =>
                    context.become(
                      `option[x]&&option[w]=>receive`((None, Some(w))))
                }
            }
          }

          override def receive: Receive =
            `option[x]&&option[w]=>receive`((None, None))

        })
      )

      val leftActor = actorSystem.actorOf(props = Props(new Actor {
        override def receive: Receive = {
          case React =>
            val `(cx=>u)=>u`: (C[X] => Unit) => Unit = `z=>rtcx`(z)
            `(cx=>u)=>u` { cx =>
              bindC(cx, { x =>
                resultC(mainActor ! Left(x))
              })
            }
            context.stop(self)
        }
      }))

      val rightActor = actorSystem.actorOf(props = Props(new Actor {
        override def receive: Receive = {
          case React =>
            val `(cw=>u)=>u`: (C[W] => Unit) => Unit = `y=>rtcw`(y)
            `(cw=>u)=>u` { cw =>
              bindC(cw, { w =>
                resultC(mainActor ! Right(w))
              })
            }
            context.stop(self)
        }
      }))

      leftActor ! React

      rightActor ! React

  }

  case class Result[Y](y: Y)

  override def async[Z, Y](`z=>rtcy`: Z => RTC[Y]): Z => RTC[Y] = {
    z => `cy=>u` =>
      val mainActor = actorSystem.actorOf(
        props = Props(new Actor {
          private val `option[y]=>receive`: Option[Y] => Receive = { optionY =>
            {
              case Result(any) =>
                val y: Y = any.asInstanceOf[Y]
                `cy=>u`(resultC(y))
                context.stop(self)
            }
          }

          override def receive: Receive =
            `option[y]=>receive`(None)

        })
      )

      val actor = actorSystem.actorOf(props = Props(new Actor {
        override def receive: Receive = {
          case React =>
            val `(cy=>u)=>u`: (C[Y] => Unit) => Unit = `z=>rtcy`(z)
            `(cy=>u)=>u` { cy =>
              bindC(cy, { y =>
                resultC(mainActor ! Result(y))
              })
            }
            context.stop(self)
        }
      }))

      actor ! React

  }

}

where

package pdbp.computation.transformation.reactive

private[pdbp] object LatencyHandlingTransformation {

  private[pdbp] type ReactiveTransformed = [C[+ _]] => [+Z] => (C[Z] => Unit) => Unit

}

and where

package pdbp.utils

import akka.actor.ActorSystem

object actorUtils {

  val actorSystem: ActorSystem = ActorSystem("PDBP")

}

The definition of parCompose makes use of an actor, mainActor, and two extra actors, leftActor and rightActor.

mainActor receives either a Left(x) message sent by leftActor or a Right(w) message sent by rightActor. The order in which they are received is not important: mainActor changes it’s behavior accordingly. When both messages are received, it’s callback handler handles the callback `c(x,w)=>u` by calling it with resultC((x, w)).

leftActor resp. rightActor receive a React message. their callback handlers `(cx=>u)=>u` resp. `(cw=>u)=>u` handle callbacks that, given cx resp cw, send Left(x) resp. Right(w) to mainActor, where x resp. w is the result of computation cx resp. cw.

The definition of async is similar, but simpler, since only one extra actor, actor, is involved.

Describing reactive latencyHandlingProgram

The next computation implicit object (and corresponding kleisli program implicit object) is the reactive latencyHandlingProgram one defined below

package pdbp.program.reactive

import pdbp.types.active.activeTypes._
import pdbp.types.reactive.reactiveTypes._

import pdbp.program.Program
import pdbp.program.latencyHandling.LatencyHandling

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.reactive.LatencyHandlingTransformation

import pdbp.program.active.implicits.program

object implicits {

  implicit object latencyHandlingProgram
      extends Computation[Reactive]
      with Program[`=>R`]
      with LatencyHandling[`=>R`]
      with ComputationTransformation[Active, Reactive]()
      with LatencyHandlingTransformation[Active]()

}

where the types Reactive and `=>R` are defined as follows

package pdbp.types.reactive

import pdbp.types.active.activeTypes._

import pdbp.types.kleisli.kleisliBinaryTypeConstructorType._

import pdbp.computation.transformation.reactive.LatencyHandlingTransformation._

object reactiveTypes {

  type Reactive = ReactiveTransformed[Active]

  type `=>R` = Kleisli[Reactive]

}

Describing identity meaning of Reactive

The next computation meaning (and corresponding kleisli program meaning) is the identity meaning of Reactive one defined below

package pdbp.program.meaning.ofReactive.reactive

import pdbp.types.reactive.reactiveTypes._

import pdbp.program.reactive.implicits.latencyHandlingProgram

import pdbp.program.meaning.ProgramMeaning

import pdbp.computation.meaning.ComputationMeaning

import pdbp.computation.meaning.IdentityMeaning

object implicits {

  implicit object identity
      extends IdentityMeaning[Reactive]()
      with ComputationMeaning[Reactive, Reactive]()
      with ProgramMeaning[`=>R`, `=>R`]()

}

Again, note that the package name reflects the usage of reactive rather than the object name.

Describing reactive.run

Consider

package pdbp.run

object reactive {

  val run: (Unit => (Unit => Unit) => Unit) => Unit = { `u=>ru`=>
    val `(u=>u)=>u`: (Unit => Unit) => Unit = `u=>ru`(())
    `(u=>u)=>u`(identity)
  } 

  // ... 

}

Running mainFactorial using reactive latencyHandlingProgram, identity.meaning and run, and using effectfulReadIntFromConsole and effectfulWriteFactorialOfIntToConsole

Consider

package examples.main.reactive.effectfulReadingAndWriting

import pdbp.types.active.activeTypes._
import pdbp.types.reactive.reactiveTypes._

import pdbp.program.reactive.implicits.latencyHandlingProgram

import examples.mainPrograms.MainFactorial

object FactorialMain extends MainFactorial[`=>R`]() {

  import examples.utils.EffectfulUtils

  private val effectfulFunctionUtils = new EffectfulUtils[`=>R`]

  import effectfulFunctionUtils._

  override val producer = effectfulReadIntFromConsole

  override val consumer = effectfulWriteFactorialOfIntToConsole

  def main(args: Array[String]): Unit = {

    import pdbp.program.meaning.reactive.ofReactive.implicits.identity.meaning

    import pdbp.run.reactive.run

    run(meaning(mainFactorial)) 

  }

}

Note that, for now, we do not make use of any latency handling capabilities.

Let’s try factorial with 10.

[info] Running examples.main.reactive.effectfulReadingAndWriting.FactorialMain
please type an integer
10
the factorial value of the integer is
3628800

Let’s try factorial with 100.

[info] Running examples.main.reactive.effectfulReadingAndWriting.FactorialMain
please type an integer
100
[error] (run-main-0) java.lang.StackOverflowError
java.lang.StackOverflowError

Describing LatencyHandlingFactorial

One way of dealing with the stack overflow when running mainFactorial using reactive latencyHandlingProgram, identity.meaning and run, is to use the latency handling feature async.

Consider

package examples.programs.latencyHandling

import pdbp.program.Program
import pdbp.program.latencyHandling.LatencyHandling
import pdbp.program.compositionOperator._

import examples.programs.AtomicPrograms

import examples.programs.HelperPrograms

class AsyncFactorial[>-->[- _, + _]: Program: LatencyHandling]
    extends AtomicPrograms[>-->]()
    with HelperPrograms[>-->]() {

  private val implicitProgram = implicitly[Program[>-->]]

  import implicitProgram._

  private val implicitLatencyHandling = implicitly[LatencyHandling[>-->]]

  import implicitLatencyHandling._

  val asyncFactorial: BigInt >--> BigInt =
    `if`(isZero) {
      one
    } `else` {
      `let` {
        subtractOne >-->
          async(asyncFactorial)
      } `in` {
        multiply
      }
    }

}

The difference between factorial and latencyHandlingFactorial is that the latter one makes use of itself in an asynchronous way. The point we want to make is that async can be used whererever we want.

Describing MainAsyncFactorial

Consider

package examples.mainPrograms.latencyHandling

import pdbp.program.Program
import pdbp.program.latencyHandling.LatencyHandling
import pdbp.program.compositionOperator._

import examples.programs.latencyHandling.AsyncFactorial

trait MainAsyncFactorial[>-->[- _, + _]: Program: LatencyHandling] {

  private object asyncFactorialObject extends AsyncFactorial[>-->]

  import asyncFactorialObject.asyncFactorial

  val producer: Unit >--> BigInt
  val consumer: BigInt >--> Unit

  lazy val mainAsyncFactorial: Unit >--> Unit =
    producer >-->
      asyncFactorial >-->
      consumer

}

The difference between mainFactorial and mainAsyncFactorial is that the latter one makes use asyncFactorial.

Running mainAsyncFactorial using reactive latencyHandlingProgram, identity.meaning and run, and using effectfulReadIntFromConsole and effectfulWriteFactorialOfIntToConsole

Consider

package examples.main.reactive.effectfulReadingAndWriting

import pdbp.types.active.activeTypes._
import pdbp.types.reactive.reactiveTypes._

import pdbp.program.reactive.implicits.latencyHandlingProgram

import examples.mainPrograms.latencyHandling.MainAsyncFactorial

object AsyncFactorialMain
    extends MainAsyncFactorial[`=>R`]() {

  import examples.utils.EffectfulUtils

  private val effectfulFunctionUtils = new EffectfulUtils[`=>R`]

  import effectfulFunctionUtils._

  override val producer = effectfulReadIntFromConsole

  override val consumer =
    actorTerminatingEffectfulWriteAsyncFactorialOfIntToConsole

  def main(args: Array[String]): Unit = {

    import pdbp.program.meaning.reactive.ofReactive.implicits.identity.meaning

    import pdbp.run.reactive.run

    run(meaning(mainAsyncFactorial))

  }

}

The difference between FactorialMain and AsyncFactorialMain is that the latter one makes use mainAsyncFactorial.

Note that we use an actor termminating consumer.

package examples.utils

// ...
class EffectfulUtils[>-->[- _, + _]: Program]
    extends pdbp.program.utils.EffectfulUtils[>-->] {

  // ...

  lazy val actorTerminatingEffectfulWriteAsyncFactorialOfIntToConsole
    : BigInt >--> Unit =
    actorTerminatingEffectfulWriteLineToConsoleWithMessage(
      "the reactive factorial value of the integer is")

  // ...

}

where

package pdbp.program.utils

// ...

class EffectfulUtils[>-->[- _, + _]: Program] {

  // ...

  def actorTerminatingEffectfulWriteLineToConsoleWithMessage[Y](
      message: String): Y >--> Unit =
    function(actorTerminatingEffectfulWriteLineToConsoleWithMessageFunction(message))     

}

where

package pdbp.utils

// ...

import pdbp.utils.actorUtils._

object effectfulFunctionUtils {

  // ...

  def actorTerminatingEffectfulWriteLineToConsoleWithMessageFunction[Y](
      message: String): Y => Unit = { y =>
    println(s"$message\n$y")
    actorSystem.terminate()
  }

}

Let’s try asyncFactorial with 1000.

[info] Running examples.main.reactive.effectfulReadingAndWriting.AsyncFactorialMain
please type an integer
1000
the reactive factorial value of the integer is
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

When, agreed, in a somewhat effectful way, we println(s"${Thread.currentThread.getId}") every time a new actor receive’s a React in async we can see better what is going on.

Let’s try asyncFactorial with 10.

[info] Running examples.main.reactive.effectfulReadingAndWriting.AsyncFactorialMain
please type an integer
10
173
175
176
175
172
176
175
172
175
172
the reactive factorial value of the integer is
3628800

Running mainFactorial using reactive freeProgram, tailrecFolding.meaning and run, and using effectfulReadIntFromConsole and effectfulWriteFactorialOfIntToConsole

An other way of dealing with the stack overflow when running mainFactorial using latencyHandlingProgram and identity meaning is to use tail recursion.

Consider

package examples.main.reactive.tailrecursive.effectfulReadingAndWriting

import pdbp.types.reactive.reactiveTypes._
import pdbp.types.reactive.free.freeReactiveTypes._

import pdbp.program.reactive.free.implicits.freeProgram

import examples.mainPrograms.MainFactorial

object FactorialMain extends MainFactorial[`=>FR`]() {

  import examples.utils.EffectfulUtils

  private val effectfulFunctionUtils = new EffectfulUtils[`=>FR`]

  import effectfulFunctionUtils._

  override val producer = effectfulReadIntFromConsole

  override val consumer = effectfulWriteFactorialOfIntToConsole

  def main(args: Array[String]): Unit = {

    import pdbp.program.meaning.reactive.ofFree.implicits.tailrecFolding.meaning

    import pdbp.run.reactive._

    run(meaning(mainFactorial))

  }

}

where

package pdbp.program.reactive.free

import pdbp.types.reactive.reactiveTypes._
import pdbp.types.reactive.free.freeReactiveTypes._

import pdbp.program.Program

import pdbp.program.reactive.implicits.latencyHandlingProgram

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.free.FreeTransformation

object implicits {

  implicit object freeProgram
      extends Computation[FreeReactive]
      with Program[`=>FR`]
      with ComputationTransformation[Reactive, FreeReactive]()
      with FreeTransformation[Reactive]()

}

and

package pdbp.program.reactive.free

import pdbp.types.reactive.reactiveTypes._
import pdbp.types.reactive.free.freeReactiveTypes._

import pdbp.program.Program

import pdbp.program.reactive.implicits.latencyHandlingProgram

import pdbp.computation.Computation

import pdbp.computation.transformation.ComputationTransformation
import pdbp.computation.transformation.free.FreeTransformation

object implicits {

  implicit object freeProgram
      extends Computation[FreeReactive]
      with Program[`=>FR`]
      with ComputationTransformation[Reactive, FreeReactive]()
      with FreeTransformation[Reactive]()

}

where

package pdbp.types.reactive.free

import pdbp.types.kleisli.binary.kleisliBinaryTypeConstructorType._

import pdbp.types.reactive.reactiveTypes._

import pdbp.computation.transformation.free.FreeTransformation._

object freeReactiveTypes {

  type FreeReactive = FreeTransformed[Reactive]

  type `=>FR` = Kleisli[FreeReactive]

}

Let’s try factorial with 1000.

[info] Running examples.main.reactive.tailrecursive.effectfulReadingAndWriting.FactorialMain
please type an integer
1000
the factorial value of the integer is
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

When, agreed, in a somewhat effectful way, we println(s"Bind(Result($y), ...)") every time we unfold a Bind(Result(y), ...) we can see better what is going on.

Let’s try factorial with 5.

[info] Running examples.main.reactive.tailrecursive.effectfulReadingAndWriting.FactorialMain
please type an integer
5
Bind(Result(5), ...)
Bind(Result(5), ...)
Bind(Result(false), ...)
Bind(Result((5,false)), ...)
Bind(Result(Right(5)), ...)
Bind(Result(5), ...)
Bind(Result(4), ...)
Bind(Result(4), ...)
Bind(Result(false), ...)
Bind(Result((4,false)), ...)
Bind(Result(Right(4)), ...)
Bind(Result(4), ...)
Bind(Result(3), ...)
Bind(Result(3), ...)
Bind(Result(false), ...)
Bind(Result((3,false)), ...)
Bind(Result(Right(3)), ...)
Bind(Result(3), ...)
Bind(Result(2), ...)
Bind(Result(2), ...)
Bind(Result(false), ...)
Bind(Result((2,false)), ...)
Bind(Result(Right(2)), ...)
Bind(Result(2), ...)
Bind(Result(1), ...)
Bind(Result(1), ...)
Bind(Result(false), ...)
Bind(Result((1,false)), ...)
Bind(Result(Right(1)), ...)
Bind(Result(1), ...)
Bind(Result(0), ...)
Bind(Result(0), ...)
Bind(Result(true), ...)
Bind(Result((0,true)), ...)
Bind(Result(Left(0)), ...)
Bind(Result(1), ...)
Bind(Result((1,1)), ...)
Bind(Result(1), ...)
Bind(Result((2,1)), ...)
Bind(Result(2), ...)
Bind(Result((3,2)), ...)
Bind(Result(6), ...)
Bind(Result((4,6)), ...)
Bind(Result(24), ...)
Bind(Result((5,24)), ...)
Bind(Result(120), ...)
the factorial value of the integer is
120

Describing fibonacci

So far we have mainly been illustrating the PDBP library using program factorial. Let’s use another program, fibonacci.

package examples.programs

import pdbp.program.Program

import pdbp.program.compositionOperator._

import pdbp.program.constructionOperators._

class Fibonacci[>-->[- _, + _]: Program]
    extends AtomicPrograms[>-->]()
    with HelperPrograms[>-->]() {

  import implicitly._

  val fibonacci: BigInt >--> BigInt =
    `if`(isZero) {
      zero
    } `else` {
      `if`(isOne) {
        one
      } `else` {
        (subtractOne & subtractTwo) >-->
          (fibonacci && fibonacci) >-->
          add
      }
    }

}

where

package examples.programs

// ...
trait AtomicPrograms[>-->[- _, + _]: Function] extends HelperPrograms[>-->] {

  // ...

  val isOne: BigInt >--> Boolean =
    isOneHelper

  def zero[Z]: Z >--> BigInt =
    zeroHelper

  val subtractTwo: BigInt >--> BigInt =
    subtractTwoHelper

  val add: (BigInt && BigInt) >--> BigInt =
    addHelper

}

where

package examples.programs

// ...

trait HelperPrograms[>-->[- _, + _]: Function] {

  import implicitly._

  // ...

  val isOneHelper: BigInt >--> Boolean =
    function(isOneFunction)

  def zeroHelper[Z]: Z >--> BigInt =
    function(zeroFunction)

  val subtractTwoHelper: BigInt >--> BigInt =
    function(subtractTwoFunction)

  val addHelper: (BigInt && BigInt) >--> BigInt =
    function(addFunction)

}

and where

package examples.utils

// ...

object functionUtils {

  // ...

  val isOneFunction: BigInt => Boolean = { i =>
    i == 1
  }

  def zeroFunction[Z]: Z => BigInt = { z =>
    0
  }

  val subtractTwoFunction: BigInt => BigInt = { i =>
    i - 2
  }

  val addFunction: (BigInt && BigInt) => BigInt = { (i, j) =>
    i + j
  }

}

Describing mainFibonacci

Consider

package examples.mainPrograms

import pdbp.program.Program
import pdbp.program.compositionOperator._
import pdbp.program.constructionOperators._

trait MainFibonacci[>-->[- _, + _]: Program] {

  private object fibonacciObject extends Fibonacci[>-->]

  import fibonacciObject.fibonacci

  val producer: Unit >--> BigInt

  val consumer: BigInt >--> Unit

  lazy val mainFibonacci: Unit >--> Unit =
    producer >-->
      fibonacci >-->
      consumer

}

trait MainFibonacci defines lazy val mainFibonacci using abstract members producer and consumer.

Running mainFibonacci using active intReadingToConsoleWritingProgram, toConsoleEffectExecutingImplicitIntReading.meaning and reading.run, and using read and write

Consider

package examples.main.active.writing.toConsole.reading.int

import pdbp.types.toConsole.ToConsole
import pdbp.types.active.reading.readingActiveTypes._
import pdbp.types.active.writing.reading.readingWritingActiveTypes._

import pdbp.program.active.writing.toConsole.reading.int.implicits.intReadingToConsoleWritingProgram

import examples.mainPrograms.MainFibonacci

object FibonacciOfReadWrittenMain
    extends MainFibonacci[`=>RWA`[BigInt, ToConsole]]() {

  override val producer = intReadingToConsoleWritingProgram.read

  import examples.utils.implicits.convertFibonacciOfIntReadToToConsole

  override val consumer = intReadingToConsoleWritingProgram.write

  def main(args: Array[String]): Unit = {

    import examples.utils.implicits.intEffectfullyReadFromConsole

    import pdbp.program.meaning.active.ofIntReadingToConsoleWriting.implicits.toConsoleEffectExecutingImplicitIntReading.meaning

    import pdbp.run.active.reading.run

    run(meaning(mainFibonacci))

  }
  
}

Let’s try fibonacci with 10

[info] Running examples.main.active.writing.toConsole.reading.int.FibonacciOfReadWrittenMain
please type an integer to read
10
the fibonacci value of the integer read is
55

Let’s try fibonacci with 10

[info] Running examples.main.active.writing.toConsole.reading.int.FibonacciOfReadWrittenMain
please type an integer to read
10
the fibonacci value of the integer read is
55

Let’s try fibonacci with 20

[info] Running examples.main.active.writing.toConsole.reading.int.FibonacciOfReadWrittenMain
please type an integer to read
20
the fibonacci value of the integer read is
6765

Let’s try fibonacci with 30

[info] Running examples.main.active.writing.toConsole.reading.int.FibonacciOfReadWrittenMain
please type an integer to read
30
the fibonacci value of the integer read is
832040

Let’s try fibonacci with 40

[info] Running examples.main.active.writing.toConsole.reading.int.FibonacciOfReadWrittenMain
please type an integer to read
40

We have a problem here. For ‘30’ this takes a very long time, and for 40 this takes an unacceptable long time. On second thought this is normal because fibonacci calls itself way too many times.

Let’s run programInfoWritingFibonacci, defined in a similar way as programInfoWritingFactorial, with 5

package examples.programs.writing

import pdbp.types.implicitFunctionType._
import pdbp.types.product.productType._

import pdbp.writable.Writable

import pdbp.program.Program
import pdbp.program.writing.Writing
import pdbp.program.compositionOperator._
import pdbp.program.constructionOperators._

import examples.programs.HelperPrograms

import pdbp.utils.infoUtils._

class ProgramInfoWritingFibonacci[
    W: Writable,
    >-->[- _, + _]: Program
                  : [>-->[- _, + _]] => Writing[W, >-->]]
    extends ProgramInfoWritingAtomicPrograms[W, >-->]() 
    with HelperPrograms[>-->]() {

  private val implicitProgram = implicitly[Program[>-->]]

  private val implicitWriting = implicitly[Writing[W, >-->]]

  import implicitProgram._

  val programInfoWritingFibonacci: (Info => W) `I=>` BigInt >--> BigInt =
    programInfo("fibonacci") {
      `if`(isZero) {
        zero
      } `else` {
        `if`(isOne) {
          one
        } `else` {
          (subtractOne & subtractTwo) >-->
            (programInfoWritingFibonacci && programInfoWritingFibonacci) >-->
            add
        }
      }
    }

}
[info] Running examples.main.active.writing.toConsole.reading.int.FibonacciOfReadProgramInfoWritingWrittenMain
please type an integer to read
5
[INFO] when 2206037946153 who 153 what isZero(5) => false
[INFO] when 2206072743527 who 153 what isOne(5) => false
[INFO] when 2206076917037 who 153 what subtractOne(5) => 4
[INFO] when 2206077930154 who 153 what subtractTwo(5) => 3
[INFO] when 2206079554088 who 153 what isZero(4) => false
[INFO] when 2206080713032 who 153 what isOne(4) => false
[INFO] when 2206081728888 who 153 what subtractOne(4) => 3
[INFO] when 2206082614932 who 153 what subtractTwo(4) => 2
[INFO] when 2206083858609 who 153 what isZero(3) => false
[INFO] when 2206084966397 who 153 what isOne(3) => false
[INFO] when 2206085752837 who 153 what subtractOne(3) => 2
[INFO] when 2206086407133 who 153 what subtractTwo(3) => 1
[INFO] when 2206087312578 who 153 what isZero(2) => false
[INFO] when 2206088114947 who 153 what isOne(2) => false
[INFO] when 2206089025481 who 153 what subtractOne(2) => 1
[INFO] when 2206089610948 who 153 what subtractTwo(2) => 0
[INFO] when 2206090382471 who 153 what isZero(1) => false
[INFO] when 2206091099806 who 153 what isOne(1) => true
[INFO] when 2206092663748 who 153 what one(1) => 1
[INFO] when 2206093135408 who 153 what fibonacci(1) => 1
[INFO] when 2206093840719 who 153 what isZero(0) => true
[INFO] when 2206094600624 who 153 what zero(0) => 0
[INFO] when 2206094959264 who 153 what fibonacci(0) => 0
[INFO] when 2206095426085 who 153 what add((1,0)) => 1
[INFO] when 2206095851310 who 153 what fibonacci(2) => 1
[INFO] when 2206096373775 who 153 what isZero(1) => false
[INFO] when 2206096905531 who 153 what isOne(1) => true
[INFO] when 2206097326403 who 153 what one(1) => 1
[INFO] when 2206097631155 who 153 what fibonacci(1) => 1
[INFO] when 2206098107534 who 153 what add((1,1)) => 2
[INFO] when 2206098402827 who 153 what fibonacci(3) => 2
[INFO] when 2206098862561 who 153 what isZero(2) => false
[INFO] when 2206099257157 who 153 what isOne(2) => false
[INFO] when 2206099676493 who 153 what subtractOne(2) => 1
[INFO] when 2206100045841 who 153 what subtractTwo(2) => 0
[INFO] when 2206100535853 who 153 what isZero(1) => false
[INFO] when 2206100931040 who 153 what isOne(1) => true
[INFO] when 2206101246685 who 153 what one(1) => 1
[INFO] when 2206101482310 who 153 what fibonacci(1) => 1
[INFO] when 2206101898066 who 153 what isZero(0) => true
[INFO] when 2206102161443 who 153 what zero(0) => 0
[INFO] when 2206102350101 who 153 what fibonacci(0) => 0
[INFO] when 2206102645094 who 153 what add((1,0)) => 1
[INFO] when 2206102847772 who 153 what fibonacci(2) => 1
[INFO] when 2206103110253 who 153 what add((2,1)) => 3
[INFO] when 2206103320987 who 153 what fibonacci(4) => 3
[INFO] when 2206103610837 who 153 what isZero(3) => false
[INFO] when 2206103889474 who 153 what isOne(3) => false
[INFO] when 2206104163483 who 153 what subtractOne(3) => 2
[INFO] when 2206104379689 who 153 what subtractTwo(3) => 1
[INFO] when 2206104666687 who 153 what isZero(2) => false
[INFO] when 2206104947880 who 153 what isOne(2) => false
[INFO] when 2206105172615 who 153 what subtractOne(2) => 1
[INFO] when 2206105554148 who 153 what subtractTwo(2) => 0
[INFO] when 2206105833456 who 153 what isZero(1) => false
[INFO] when 2206106074167 who 153 what isOne(1) => true
[INFO] when 2206106257244 who 153 what one(1) => 1
[INFO] when 2206106406316 who 153 what fibonacci(1) => 1
[INFO] when 2206106647926 who 153 what isZero(0) => true
[INFO] when 2206106815998 who 153 what zero(0) => 0
[INFO] when 2206106937451 who 153 what fibonacci(0) => 0
[INFO] when 2206107114458 who 153 what add((1,0)) => 1
[INFO] when 2206107263882 who 153 what fibonacci(2) => 1
[INFO] when 2206107476145 who 153 what isZero(1) => false
[INFO] when 2206107685176 who 153 what isOne(1) => true
[INFO] when 2206107837610 who 153 what one(1) => 1
[INFO] when 2206107953305 who 153 what fibonacci(1) => 1
[INFO] when 2206108110232 who 153 what add((1,1)) => 2
[INFO] when 2206108229966 who 153 what fibonacci(3) => 2
[INFO] when 2206108379729 who 153 what add((3,2)) => 5
[INFO] when 2206108501615 who 153 what fibonacci(5) => 5
the fibonacci value of the integer read is
5

Using tail recursion won’t solve the problem.

The problem can be solved by redefining fibonacci using the standard optimization technique. It is perfectly possible to do this using the PDBP programming DSL.

Instead, for illustrating purposes only, we redefine fibonacci using the parallel latency handling operators |&| and |&&| instead of the sequential construction operators & and &&.

Describing ParallelFibonacci

asyncFactorial uses itself, once, in an asynchronous way.

parallelFibonacci below uses itself, in a parallel way.

package examples.programs.latencyHandling

import pdbp.program.Program
import pdbp.program.latencyHandling.LatencyHandling

import examples.programs.AtomicPrograms
import examples.programs.HelperPrograms

class ParallelFibonacci[>-->[- _, + _]: Program: LatencyHandling]
    extends AtomicPrograms[>-->]()
    with HelperPrograms[>-->]() {

  private val implicitProgram = implicitly[Program[>-->]]

  import implicitProgram._

  import pdbp.program.compositionOperator._

  import pdbp.program.latencyHandling.latencyHandlingOperators._

  val parallelFibonacci: BigInt >--> BigInt =
    `if`(isZero) {
      zero
    } `else` {
      `if`(isOne) {
        one
      } `else` {
        (subtractOne |&| subtractTwo) >-->
          (parallelFibonacci |&&| parallelFibonacci) >-->
          add
      }
    }

}

Describing MainParallelFibonacci

Consider

package examples.mainPrograms.latencyHandling

import pdbp.program.Program
import pdbp.program.latencyHandling.LatencyHandling
import pdbp.program.compositionOperator._

import examples.programs.latencyHandling.ParallelFibonacci

trait MainParallelFibonacci[>-->[- _, + _]: Program: LatencyHandling] {

  private object parallelFibonacciObject extends ParallelFibonacci[>-->]

  import parallelFibonacciObject.parallelFibonacci

  val producer: Unit >--> BigInt
  val consumer: BigInt >--> Unit

  lazy val mainParallelFibonacci: Unit >--> Unit =
    producer >-->
      parallelFibonacci >-->
      consumer

}

Running mainParallelFibonacci using reactive latencyHandlingProgram, identity.meaning and run, and using effectfulReadIntFromConsole and actorTerminatingEffectfulWriteParallelFibonacciOfIntToConsole

Consider

package examples.main.reactive.effectfulReadingAndWriting

import pdbp.types.active.activeTypes._
import pdbp.types.reactive.reactiveTypes._

import pdbp.program.reactive.implicits.latencyHandlingProgram

import examples.mainPrograms.latencyHandling.MainParallelFibonacci

object ParallelFibonacciMain extends MainParallelFibonacci[`=>R`]() {

  import examples.utils.EffectfulUtils

  private val effectfulFunctionUtils = new EffectfulUtils[`=>R`]

  import effectfulFunctionUtils._

  override val producer = effectfulReadIntFromConsole

  override val consumer =
    actorTerminatingEffectfulWriteParallelFibonacciOfIntToConsole

  def main(args: Array[String]): Unit = {

    import pdbp.program.meaning.reactive.ofReactive.implicits.identity.meaning

    import pdbp.run.reactive.run

    run(meaning(mainParallelFibonacci))

  }

}

Let’s try parallelFibonacci with 4.

[info] Running examples.main.reactive.effectfulReadingAndWriting.ParallelFibonacciMain
please type an integer
4
the reactive fibonacci value of the integer is
3

When, agreed, in a somewhat effectful way, we println(s"left ${Thread.currentThread.getId}") every time a new leftActor receive’s a React and we println(s"right ${Thread.currentThread.getId}") every time a new leftActor receive’s a React in parCompose we can see better what is going on.

[info] Running examples.main.reactive.effectfulReadingAndWriting.ParallelFibonacciMain
please type an integer
4
right 246
left  247
left  248
right 246
left  251
left  246
right 247
right 247
left  254
right 251
left  255
right 248
left  248
right 248
left  246
right 248
the reactive fibonacci value of the integer is
3

TODO info writing fibonacci

TODO asysnc info writing tail recursive factorial