#StackBounty: #javascript #functional-programming #language-agnostic #unification #transducer Can clojure inspired transducers be typed…

Bounty: 300

I have a purely functional transducer implementation in Javascript that supports loop-fusion and short circuiting. Please note that although I am using JS it is not a requirement for understanding the question. Only the types matter.

// ((a -> r) -> r) -> Cont r a
const Cont = k => ({run: k});

// (a -> b -> Cont b b) -> b -> [a] -> b
const foldk = f => init => xs => {
  let acc = init;

  for (let i = xs.length - 1; i >= 0; i--)
    acc = f(xs[i]) (acc).run(id);

  return acc;
};

// (a -> b) -> (b -> t b -> Cont (t b) (t b)) -> a -> t b -> Cont (t b) (t b)
const map = f => cons => x => acc =>
  Cont(k => cons(f(x)) (acc).run(k));

// (a -> Bool) -> (a -> t a -> Cont (t a) (t a)) -> a -> t a -> Cont (t a) (t a)
const filter = p => cons => x => acc =>
  Cont(k =>
    p(x)
      ? cons(x) (acc).run(k)
      : k(acc));

// (b -> c) -> (a -> b) -> a -> c
const comp = f => g => x => f(g(x));

const liftCont2 = f => x => y => Cont(k => k(f(x) (y)));
const unshift = x => xs => (xs.unshift(x), xs);
const includes = sub => s => s.includes(sub);
const len = arrayLike => arrayLike.length;
const id = x => x;

// (String -> t String -> Cont (t String) (t String))
//   -> String -> t String -> Cont (t String) (t String)
const filterO = filter(includes("o"));

// (Number -> t Number -> Cont (t Number) (t Number))
//    -> String -> t Number -> Cont (t Number) (t Number)
const mapLen = map(len);

// type error
const transducer = comp(filterO) (mapLen);

const reducer =  transducer(liftCont2(unshift));

const main = foldk(reducer) ([]) (["f", "fo", "foo", "fooo"]);

console.log(main); // [2, 3, 4] with only a single traversal

As you can see the fold works but doesn’t type check. Revealing the type error requires some manual unification:

unify `comp(filterO)`:
(b -> c) -> (a -> b) -> a -> c
(String -> t String -> Cont (t String) (t String))
  -> String -> t String -> Cont (t String) (t String)

yields

(a -> String -> t String -> Cont (t String) (t String))
  -> a -> String -> t<String> -> Cont (t String) (t String)

unify result of `comp(filterO)` with `mapLen` (contravariant):
a -> String -> t String -> Cont (t String) (t String)
(Number -> t Number -> Cont (t Number) (t Number))
  -> String -> t Number -> Cont (t Number) (t Number)

substitutes

a ~ Number -> t Number -> Cont (t Number) (t Number)

unify (covariant):
String -> t String -> Cont (t String) (t String)
String -> t Number -> Cont (t Number) (t Number)

Both terms clearly cannot be unified.

Are transducers a concept exclusive for dynamic languages and cannot be typed, did I make a mistake during unification or are my transducer types (map/filtert) just plain wrong?


Get this bounty!!!

#StackBounty: #functional-programming #scala #binary-tree Deserialize a binary breadth-first in functional programming

Bounty: 50

A while back, I answered this question on Stack Overflow that involved deserializing a binary tree breadth-first using functional programming (the question itself isn’t relevant). I’d like to make sure that I’m following functional programming principles and whether or not this is stack-safe. I’d also like to know if I can make my code more performant, less bloated, clearer, etc. If it helps, the question provides this link to explain the algorithm.

I first defined this rather simple tree type. Every child is an instance of Node, and the absence of a left or right child is denoted with Empty.

sealed trait Tree[+T]
case class Node[+T](data: T, left: Tree[T], right: Tree[T]) extends Tree[T]
case object Empty extends Tree[Nothing]

And this trait that represents a function that takes the current list of serialized items (every item is an Option, with None meaning there is no child). It consumes one or more of these items and returns the rest, along with an Either, where a Right contains a fully built tree, and a Left contains another RecFun that will later consume more items to finish building the current tree.

trait RecFun[T]
    extends (List[Option[T]] => (List[Option[T]], Either[RecFun[T], Tree[T]]))

The entry point is makeTree. First, a RecFun is made using createRec below, and the recursive helper inside makeTree starts processing the tree from there.

def makeTree[T](list: List[Option[T]]): Tree[T] = {
  def helper(f: RecFun[T], l: List[Option[T]]): Tree[T] =
    f(l) match {
      case (_, Right(tree)) => tree
      case (next, Left(f))  => helper(f, next)
    }

  list match {
    case Some(x) :: tail => helper(createRec(x), tail)
    case _               => Empty
  }
}

createRec takes the value of the root node of a subtree, and makes a RecFun to continue building it.

def createRec[T](data: T): RecFun[T] = {
  //No more children, so return a Right with a node whose children are Emptys
  case None :: Nil | Nil => (Nil, Right(Node(data, Empty, Empty)))
 //There's a left child, but no right child to be had, so return here too
  case Some(l) :: Nil => (Nil, Right(Node(data, Node(l, Empty, Empty), Empty)))
  case lo :: ro :: rest => //Possible left child :: possible right child :: rest of the items
    //Return the rest, and an Either depending on what lo and ro are
    (rest, (lo, ro) match {
      case (Some(l), Some(r)) =>
        //Both children exist, so wait for both of them before building the tree
        Left(waitForChildren(data, createRec(l), createRec(r)))
      case (Some(l), None) =>
        //Need to wait only for left child
        Left(waitForChild(Node(data, _, Empty), createRec(l)))
      case (None, Some(r)) =>
        //Need to wait only for right child
        Left(waitForChild(Node(data, Empty, _), createRec(r)))
      //Both children don't exist, so build tree and return right now
      case (None, None) => Right(Node(data, Empty, Empty))
    })
  }

This helper simply combines functions that build a tree where the root’s value is known, but the children are not.

//Here, both the children need to be deserialized and have their own RecFuns
def waitForChildren[T](data: T, leftF: RecFun[T], rightF: RecFun[T]): RecFun[T] =
  input => {
    //Attempt to deserialize the left child first
    val (next, res) = leftF(input)
    res match {
      //If it succeeded, use waitForChild to wait for the right child
      case Right(tree) =>
        (next, Left(waitForChild(Node(data, tree, _), rightF)))
      //Otherwise, try to deserialize the right child, then run the new left RecFun leftF2 again
      case Left(leftF2) => {
        val (next2, res2) = rightF(next)
        //Return the rest of the list, along with the new RecFun
        (next2, Left(res2 match {
          //If the right child is constructed, wait for the left child to be constructed
          case Right(tree)   => waitForChild(Node(data, _, tree), leftF2)
          //Otherwise, run leftF2 first, then the new right RecFun rightF2
          case Left(rightF2) => waitForChildren(data, leftF2, rightF2)
        }))
      }
    }
  }

Here, one child is known, and we’re just waiting for another.

/**
 * @param ctor Function that takes a child and finishes building parent tree
 * @param f    Function to construct child
 */
def waitForChild[T](ctor: Tree[T] => Node[T], f: RecFun[T]): RecFun[T] =
  input => {
    //Try deserializing the child based on the function f
    val (next, res) = f(input)
    (next, res match {
      //If it's fully built, build the parent tree by applying ctor to it
      case Right(tree)  => Right(ctor(tree))
      //Otherwise, wait for the new RecFun
      case Left(recFun) => Left(waitForChild(ctor, recFun))
    })
  }

Here is the code I used for testing:

val tree = Node(
  1,
  Node(2, Node(3, Node(5, Empty, Empty), Empty), Node(4, Empty, Empty)),
  Empty
)
val tree2 = makeTree(List(Some(1), Some(2), None, Some(3), Some(4), Some(5), None))

println(tree2)
assert(tree == tree2)

Here is a Scastie.


Get this bounty!!!

#StackBounty: #strings #functional-programming #regex #r Find if a dataset of words contains any words containing all vowel by using ex…

Bounty: 50

Take the words dataset from stringr. An R4DS exercise challenges the reader to check if there are any words in that dataset that contain every vowel. My presumably correct solution, using five calls to str_detect, was as follows:

library(stringr)
words[apply(sapply(c("a", "e", "i", "o", "u"), function(x) str_detect(words, x)), 1, all)]

Under the restriction that we must call str_detect exactly five times, once for each vowel, is there a better way to do this? The sapply seems like the right idea – it produces a 980*5 logical matrix with each row being a logical vector showing if the corresponding vowel was in the corresponding word. Collapsing it with all also seems like the right idea, but any time that I have to call apply rather than any other member of the apply family or something like Filter, I become concerned about my approach. R’s higher-order functions typically work best by column rather than by row and apply is a sign that I’ve failed to work like that.

Suggestions from either base R or the Tidyverse will be accepted. My primary reason for asking this question is that I have a strong feeling that the apply could have been avoided, perhaps by construction the logical matrix differently.


Get this bounty!!!

#StackBounty: #haskell #functional-programming Tic Tac Toe (Haskell)

Bounty: 50

I implemented tic-tac-toe in Haskell. I’m trying to incorporate suggestions from my last question (which mostly revolved around algorithmic logic) while trying something new – IO logic.

What kind of improvements could I make to this program? Am I being too tricky anywhere? Are there some built-in library functions that I could use to simplify the logic?

Model.hs

module Model (doTurn, getWinner, initialState, isVacant, State(..), Board, Player(..), Winner(..)) where
import Data.List (transpose)
import Safe (atMay)
import Data.Maybe (isJust, isNothing, catMaybes)
import Control.Monad (join)

data Player = X | O deriving (Eq)

data Winner = XWins | OWins | CatScratch

type Board = [[Maybe Player]]

data State = State
  {
    boardState :: Board,
    turnState :: Player
  }

opponentOf :: Player -> Player
opponentOf X = O
opponentOf O = X

diagonal :: [[a]] -> [a]
diagonal board =
  catMaybes $ zipWith atMay board [0..]

replaceAt :: (a -> a) -> Int -> [a] -> [a]
replaceAt updateFn index array =
  case splitAt index array of
    (left, val:right) -> left ++ [updateFn val] ++ right
    _ -> array

isVacant :: (Int, Int) -> Board -> Bool
isVacant (x, y) board =
  isNothing $ join $ (`atMay` x) =<< (`atMay` y) board

placeInBoard :: (Int, Int) -> Maybe Player -> Board -> Board
placeInBoard (x, y) =
  (`replaceAt` y) . (`replaceAt` x) . const

isPlayerWinner :: Player -> Board -> Bool
isPlayerWinner player board =
  (any . all) (Just player ==) $
    board ++
    transpose board ++
    map diagonal [board, transpose board]

isCatScratch :: Board -> Bool
isCatScratch =
  (all . all) isJust

getWinner :: Board -> Maybe Winner
getWinner board
  | isPlayerWinner X board = Just XWins
  | isPlayerWinner O board = Just OWins
  | isCatScratch board = Just CatScratch
  | otherwise = Nothing

doTurn :: State -> (Int, Int) -> State
doTurn state coord =
  State {
    boardState = placeInBoard coord (Just $ turnState state) (boardState state),
    turnState = opponentOf (turnState state)
  }

initialState :: Player -> State
initialState firstPlayer =
  State {
    boardState = replicate 3 (replicate 3 Nothing),
    turnState = firstPlayer
  }

View.hs

module View (renderBoard, currentPlayerText, parseAsCoord, winnerText) where
import Data.List (intercalate, intersperse)
import Data.Char (toUpper)
import Model (Board, Player(X, O), Winner(XWins, OWins, CatScratch))

surround :: a -> [a] -> [a]
surround value array = [value] ++ intersperse value array ++ [value]

renderCell :: Maybe Player -> String
renderCell (Just X) = "X"
renderCell (Just O) = "O"
renderCell Nothing = " "

renderBoard :: Board -> String
renderBoard =
  let
    header  = "   A     B     C  "
    divider = " -----+-----+-----"
    padding = "      |     |     "
    renderRow :: Int -> [Maybe Player] -> String
    renderRow n = intercalate "" . (++) [show n] . surround "  " . intersperse "|" . map renderCell
  in
    unlines . (++) [header] . surround padding . intersperse divider . zipWith renderRow [1..]

parseAsCoord :: String -> Maybe (Int, Int)
parseAsCoord [number, letter] =
  let
    maybeX = case toUpper letter of { 'A' -> Just 0; 'B' -> Just 1; 'C' -> Just 2; _ -> Nothing }
    maybeY = case number of { '1' -> Just 0; '2' -> Just 1; '3' -> Just 2; _ -> Nothing }
  in case (maybeX, maybeY) of
    (Just x, Just y) -> Just (x, y)
    _ -> Nothing
parseAsCoord _ = Nothing

currentPlayerText :: Player -> String
currentPlayerText X = "It's X's turn"
currentPlayerText O = "It's O's turn"

winnerText :: Winner -> String
winnerText XWins = "X Wins!"
winnerText OWins = "O Wins!"
winnerText CatScratch = "Cat Scratch!"

Main.hs

import System.IO (hFlush, stdout)
import System.Random (randomIO)
import Model (initialState, doTurn, getWinner, isVacant, Player(X, O), State(boardState, turnState))
import View (renderBoard, currentPlayerText, parseAsCoord, winnerText)

prompt :: String -> IO String
prompt msg = do
  putStr msg >> hFlush stdout
  getLine

promptForVacantCoord :: State -> IO (Int, Int)
promptForVacantCoord state = do
  userInput <- prompt "Pick a spot (e.g. 2B): "
  case parseAsCoord userInput of
    Just coord | isVacant coord (boardState state) -> return coord
    _ -> putStrLn "Invalid input" >> promptForVacantCoord state

step :: State -> IO ()
step state = do
  putStrLn ""
  putStrLn $ renderBoard $ boardState state
  case getWinner (boardState state) of
    Just winner -> putStrLn (winnerText winner)
    Nothing -> do
      putStrLn $ currentPlayerText (turnState state)
      coord <- promptForVacantCoord state
      step $ doTurn state coord

main :: IO ()
main =
  let
    playerFromBool True = X
    playerFromBool False = O
  in
    step . initialState . playerFromBool =<< randomIO


Get this bounty!!!

#StackBounty: #javascript #object-oriented #game #functional-programming #2048 JavaScript OOD: 2048

Bounty: 50

I wrote a 2048 game in JavaScript with an object-oriented paradigm. The game board is presented with a two-dimensional array and each tile holds an integer.

Here is the implementation:

class Game {
  SIZE = 4
  constructor() {
    this.board = Array.from({ length: this.SIZE * this.SIZE }, () => 0).reduce(
      (arrays, curr) => {
        const lastArray = arrays[arrays.length - 1]
        if (lastArray.length < this.SIZE) lastArray.push(curr)
        else arrays.push([curr])
        return arrays
      },
      [[]]
    )
    this.isWin = false
    this._init()
  }

  _init() {
    const pickedTiles = this._randomlyPick(2)
    for (const [row, col] of pickedTiles) {
      this.board[row][col] = Game.generateTile()
    }
  }

  static generateTile() {
    if (Math.random() > 0.5) return 2
    return 4
  }

  _getEmptyTiles() {
    const emptyTiles = []
    for (let row = 0; row < this.SIZE; row++) {
      for (let col = 0; col < this.SIZE; col++) {
        if (this.board[row][col] === 0) emptyTiles.push([col, row])
      }
    }
    return emptyTiles
  }

  _randomlyPick(numOfItems) {
    const emptyTiles = this._getEmptyTiles()
    for (let i = 0; i < numOfItems; i++) {
      const toSwap = i + Math.floor(Math.random() * (emptyTiles.length - i))
      ;[emptyTiles[i], emptyTiles[toSwap]] = [emptyTiles[toSwap], emptyTiles[i]]
    }
    return emptyTiles.slice(0, numOfItems)
  }

  spawn() {
    // randomly spawn empty tiles with 2 or 4
    const [emtpyTile] = this._randomlyPick(1)
    this.board[emtpyTile[0]][emtpyTile[1]] = Game.generateTile()
  }

  play(dir) {
    if (this.canPlay()) {
      switch (dir) {
        case Game.moveUp:
          this._mergeUp()
          break
        case Game.moveRight:
          this._mergeRight()
          break
        case Game.moveLeft:
          this._mergeLeft()
          break
        case Game.moveDown:
          this._mergeDown()
          break
      }
      this.spawn()

      return true
    }
    return false
  }
  checkIsWin() {
    return this.isWin
  }

  static peek(array) {
    return array[array.length - 1]
  }

  static zip(arrays) {
    const result = []
    for (let i = 0; i < arrays[0].length; ++i) {
      result.push(arrays.map((array) => array[i]))
    }
    return result
  }

  _mergeRowRight(sparseRow) {
    const row = sparseRow.filter((x) => x !== 0)
    const result = []
    while (row.length) {
      let value = row.pop()
      if (Game.peek(row) === value) value += row.pop()
      result.unshift(value)
    }

    while (result.length < 4) result.unshift(0)
    return result
  }

  _mergeRowLeft(row) {
    return this._mergeRowRight([...row].reverse()).reverse()
  }

  _mergeUp() {
    this.board = Game.zip(Game.zip(this.board).map(row => this._mergeRowLeft(row)))
  }
  _mergeDown() {
    this.board = Game.zip(Game.zip(this.board).map(row => this._mergeRight(row)))
  }

  _mergeRight() {
    this.board = this.board.map((row) => this._mergeRowRight(row))
  }
  _mergeLeft() {
    this.board = this.board.map((row) => this._mergeRowLeft(row))
  }

  canPlay() {
    const dirs = [
      [0, 1],
      [1, 0],
      [-1, 0],
      [0, -1],
    ]
    const visited = new Set()
    for (let row = 0; row < this.SIZE; row++) {
      for (let col = 0; col < this.SIZE; col++) {
        if (visited.has([row, col].toString())) continue
        const tile = this.board[row][col]
        if (tile === 2048) {
          this.isWin = true
          return false
        }
        if (tile === 0) return true
        for (const [dx, dy] of dirs) {
          if (this.board[row + dx]?.[col + dy] === tile) return true
        }
        visited.add([row, col].toString())
      }
    }
    return false
  }
}

Game.moveUp = Symbol('moveUp')
Game.moveDown = Symbol('moveUp')
Game.moveLeft = Symbol('moveUp')
Game.moveRight = Symbol('moveUp')

const game = new Game()
console.log(game.board);
game.play(Game.moveUp)
console.log(game.board);
game.play(Game.moveRight)
console.log(game.board);

Any feedback is welcomed. Specifically, I would like to know:

  1. Is it idiomatic in OO to use static methods to store util functions such as zip to flip the board along its diagonal?
  2. Is there a better way to structure the class? I feel like I am not doing a great job at dividing some of the logic of different actions.
  3. Is there any specific design pattern that I can use to improve the class?
  4. Lastly, I am using symbol to present the direction of the move the user can make and attach them as the instance variable to the class. Again I am not sure if this is idiomatic in OO since I am kinda new to this paradigm.


Get this bounty!!!

#StackBounty: #functional-programming #constraint-satisfaction #static-analysis Constraint based analysis: understanding the program $[…

Bounty: 50

I am currently studying the textbook Principles of Program Analysis by Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Chapter 1.4 Constraint Based Analysis says the following:

1.4 Constraint Based Analysis
The purpose of Control Flow Analysis is to determine information about what "elementary blocks" may lead to what other "elementary blocks". This information is immediately available for the $mathrm{While}$ language unlike what is the case for more advanced imperative, functional and object-oriented languages. Often Control Flow Analysis is expressed as a Constraint Based Analysis as will be illustrated in this section.
Consider the following functional program:

let f = fn x => x 1;
    g = fn y => y + 2;
    h = fn z => z + 3
in (f g) + (f h)

It defines a higher-order function f with formal parameter x and body x 1; then it defines two functions g and h that are given as actual parameters to f in the body of the let-construct. Semantically, x will be bound to each of these two functions in turn so both g and h will be applied to 1 and the result of the computation will be the value $7$.
An application of f will transfer control to the body of f, i.e. to x 1, and this application of x will transfer control to the body of x. The problem is that we cannot immediately point to the body of x: we need to know what parameters f will be called with. This is exactly the information that the Control Flow Analysis gives us:
$$text{For each function application, which functions may be applied.}$$
As is typical of functional languages, the labelling scheme used would seem to have a very different character than the one employed for imperative languages because the "elementary blocks" may be nested. We shall therefore label all subexpressions as in the following simple program that will be used to illustrate the analysis.
Example 1.2 Consider the program:
$$[[ text{fn} x => [x]^1]^2 [ text{fn} y => [y]^3]^4]^5$$
It calls the identity function $text{fn} x => x$ on the argument $text{fn} y => y$ and clearly evaluates to $text{fn} y => y$ itself (omitting all $[ dots ]^mathscr{l}$).

We shall now be interested in associating information with the labels themselves, rather than with the entries and exits of the labels – thereby we exploit the fact that there are no side-effects in out simple functional language. The Control Flow Analysis will be specified by a pair $(hat{C}, hat{rho})$ of functions where $hat{C}(mathscr{l})$ is supposed to contain the values that the subexpression (or "elementary block") labelled $mathscr{l}$ may evaluate to and $hat{rho}(x)$ contain the values that the variable $x$ can be bound to.

The constraint system. One way to specify the Control Flow Analysis then is by means of a collection of constraints and we shall illustrate this for the program of Example 1.2. There are three classes of constraints. One class of constraints relate the values of function abstractions to their labels:
$${ text{fn} x => [x]^1 } subseteq hat{C}(2) \ { text{fn} y => [y]^3 } subseteq hat{C}(4)$$
These constraints state that a function abstraction evaluates to a closure containing the abstraction itself. So the general pattern is that an occurrence of $[text{fn} x => e]^mathscr{l}$ in the program gives rise to a constraint ${ text{fn} x => e } subseteq hat{C}(mathscr{l})$.
The second class of constraints relate the values of variables to their labels:
$$hat{rho}(x) subseteq hat{C}(1) \ hat{rho}(y) subseteq hat{C}(3)$$
The constraints state that a variable always evaluates to its value. So for each occurrence of $[x]^mathscr{l}$ in the program we will have a constraint $hat{rho}(x) subseteq hat{C}(mathscr{l})$.
The third class of constraints concerns function application: for each application point $[e_1 e_2]^mathscr{l}$, and for each possible function $[text{fn} x => e]^{mathscr{l}^prime}$ that could be called at this point, we will have: (i) a constraint expressing that the formal parameter of the function is bound to the actual parameter at the application point, and (ii) a constraint expressing that the result obtained by evaluating the body of the function is a possible result of the application.
Our example program has just one application $[[dots]^2[dots]^4]^5$, but there are two candidates for the function, i.e. $hat{C}(2)$ is a subset of the set ${ text{fn} x => [x]^1, text{fn} y => [y]^3 }$. If the function $text{fn} x => [x]^1$ is applied then the two constraints are $hat{C}(4) subseteq hat{rho}(x)$ and $hat{C}(1) subseteq hat{C}(5)$. We express this as conditional constraints:
$${ text{fn} x => [x]^1 } subseteq hat{C}(2) Rightarrow hat{C}(4) subseteq hat{rho}(x) \ { text{fn} x => [x]^1 } subseteq hat{C}(2) Rightarrow hat{C}(1) subseteq hat{C}(5)$$
Alternatively, the function being applied could be $text{fn} y => [y]^3$ and the corresponding conditional constraints are:
$${ text{fn} y => [y]^3 } subseteq hat{C}(2) Rightarrow hat{C}(4) subseteq hat{rho}(y) \ { text{fn} y => [y]^3 } subseteq hat{C}(2) Rightarrow hat{C}(3) subseteq hat{C}(5)$$
The least solution. As in Section 1.3 we shall be interested in the least solution to this set of constraints: the smaller the sets of values given by $hat{C}$ and $hat{rho}$, the more precise the analysis is in predicting which function are applied. In Exercise 1.2 we show that the following choice of $hat{C}$ and $hat{rho}$ gives a solution to the above constraints:
$$hat{C}(1) = { text{fn} y => [y]^3 } \ hat{C}(2) = { text{fn} x => [x]^1 } \ hat{C}(3) = emptyset \ hat{C}(4) = { text{fn} y => [y]^3 } \ hat{C}(5) = { text{fn} y => [y]^3 } \ hat{rho}(x) = { text{fn} y => [y]^3 } \ hat{rho}(y) = emptyset$$
Among other things this tells us that the function abstraction $text{fn} y => y$ is never applied (since $hat{rho}(y) = emptyset$) and that the program may only evaluate to the function abstraction $text{fn} y => y$ (since $hat{C}(5) = { text{fn} y => [y]^3 }$).
Note the similarities between the constraint based approaches to Data Flow Analysis and Constraint Based Analysis: in both cases the syntactic structure of the program gives rise to a set of constraints whose least solution is desired. The main difference is that the constraints for the Constraint Based Analysis have a more complex structure than those for the Data Flow Analysis.

I am confused by this part:

Among other things this tells us that the function abstraction $text{fn} y => y$ is never applied (since $hat{rho}(y) = emptyset$) and that the program may only evaluate to the function abstraction $text{fn} y => y$ (since $hat{C}(5) = { text{fn} y => [y]^3 }$).

I thought that I understood the program $[[ text{fn} x => [x]^1]^2 [ text{fn} y => [y]^3]^4]^5$. However, this part seems contradictory: it first says that $text{fn} y => y$ is never applied, and it then immediately says that the program may only evaluate to the function abstraction $text{fn} y => y$. Furthermore, I don’t understand why, as stated above, "$text{fn} y => y$ is never applied (since $hat{rho}(y) = emptyset$)", and nor do I understand why "the program may only evaluate to the function abstraction $text{fn} y => y$ (since $hat{C}(5) = { text{fn} y => [y]^3 }$)". For instance, if, as stated above, $hat{rho}(y)$ contains the values that the variable $y$ can be bound to, then why is this the empty set (in other words, why can $y$ in the program not be bound to any values)?

I skipped to exercise 1.2 to see if I could gather any additional information:

Exercise 1.2 Show that the solution displayed for the Control Flow Analysis in Section 1.4 is a solution. Also show that it is in fact the least solution. (Hint: Consider the demands on $hat{C}(2)$, $hat{C}(4)$, $hat{rho}(x)$, $hat{C}(1)$ and $hat{C}(5)$.)

However, this doesn’t really help me make sense of this. For instance, in the above excerpt, the authors said that ${ text{fn} y => [y]^3 } subseteq hat{C}(4)$, which makes sense when you look at the program $[[ text{fn} x => [x]^1]^2 [ text{fn} y => [y]^3]^4]^5$; but, for equality, we also require that $hat{C}(4) subseteq { text{fn} y => [y]^3 }$, and it isn’t clear to me how one concludes this.


Get this bounty!!!

#StackBounty: #functional-programming #category-theory What is the category theory interpretation of higher order abstract syntax?

Bounty: 50

Suppose you have a simple sort of lambda calculus abstract syntax tree. The fine details don’t really matter.

data T = Unit | Void | T :*: T | T :+: T | T :-> T | I

data Term x a where
  Var :: x -> Term x x
  Int :: Int -> Term x I
  Add :: Term x I -> Term x I -> Term x I
  Apply :: Term x (a :-> b) -> Term x a -> Term x b
  Lambda :: (x -> Term x b) -> Term x (a :-> b)

lam :: (Term x a -> Term x b) -> Term x (a :-> b)
lam f = Lambda (x -> f (Var x))

newtype Program a = Program (forall x. Term x a)

How is this sort of structure to be interpreted according to category theory?

I understand that closed cartesian categories are supposed to capture the notion of the lambda calculus and have written more than one compiler from such a higher order abstract syntax abstract syntax tree to closed cartesian categories myself but still don’t really "get" what higher order abstract syntax is supposed to mean in terms of category theory.

lam doesn’t really seem to be a sort of functor to me. If lam was some functor operation wouldn’t we want a type sort of like lam :: (a -> b) -> Term x (F a :-> F b) orlam :: (Term x a -> Term x b) -> Term x (F a :-> F b) for some sort of F.

I thought this sort of thing might be related to the Yoneda embedding and tried explicitly thinking of the free variable parameter as an environment argument and Lam as a category not just a AST.

data T = Unit | Void | T :*: T | T :+: T | T :-> T | I

data Lam env result where
  Id :: Lam a a
  (:.:) :: Lam b c -> Lam a b -> Lam a c

  Coin :: Lam env Unit
  Left :: Lam a (a :+: b)
  Right :: Lam b (a :+: b)
  Fanout :: Lam env a -> Lam env b -> Lam env (a :*: b)
  Curry :: Lam (b :*: a) c -> Lam a (b :-> c)
  Absurd :: Lam Void r
  First :: Lam (a :*: b) a
  Second :: Lam (a :*: b) b
  Fanin :: Lam a r -> Lam b r -> Lam (a :+: b) r
  Uncurry :: Lam a (b :-> c) -> Lam (b :*: a) c

  -- Some extra stuff
  Int :: Int -> Lam env I
  Add :: Lam env I -> Lam env I -> Lam env I

newtype Program a = Program (forall env. Term env a)

But I didn’t really find the Yoneda embedding to simplify things much.

yo :: (forall env. Lam env a -> Lam env b) -> Lam a b
yo f = f Id

I don’t have a problem figuring out how to compile one representation to another but I just don’t understand what higher order abstract syntax is supposed to mean.

And to be clearer I’m not just looking for what higher order abstract means for Cartesian closed categories but what it means for any sort of language whether it be about some sort of affine language or is some sort of relational Prolog sort of thing.


Get this bounty!!!

#StackBounty: #type-theory #lambda-calculus #functional-programming #category-theory Creating a large tuple from smaller tuples via a m…

Bounty: 50

Suppose I have a term $a :alpha$ of the Simply-Typed Lambda Calculus (in the following, $alpha, beta, gamma$ stand for arbitrary types) and I want to lift it to a term

$lambda x_{beta}. ;(x, , a)$

I could use a function $lambda z_{alpha}, x. ;(x,, z)$.

Suppose we then form $(b, a) : beta times alpha$, by applying $lambda x_{beta}. ;(x, , a)$ to $,b_{beta}$.

We might want to add $c$ to the beginning of this to form $(c, b, a) : gamma times beta times alpha$. We could do this (here $pi_1$ and $pi_2$ are projections)) by having a function $lambda z’_{beta times alpha}, z. ,(z,, pi_1 z’,, pi_2 z’)$. And again, we could cook up a function to form $(d,, c,, b,, a)$ and $(e,,d,, c,, b,, a)$ (so on and so forth).

I could do things in the way above; however, I wondered whether there was a way of doing this kind of operation via an applicative or a monad. Then I could (ideally) use the operations of the monad or applicative, to lift term $a$ (perhaps into $lambda x.,(x, , a)$, and then form these tuples $(b, a), (c, b, a), (d, c, b, a)$, etc, by the operations of the monad or applicative.

If you know a way of doing this I would be very interested.


Get this bounty!!!

#StackBounty: #functional-programming #rust #move-semantics #referential-transparency What do move semantics imply for referential tran…

Bounty: 50

I’m trying to work out how move semantics affect referential transparency.

Referential transparency (RT) allows us to replace any expression with its result without changing the meaning of the program (paraphrased from Functional Programming in Scala). For example, I can replace 1 + 1 anywhere in my program with 2, and nothing should change. This Python program is referentially transparent:

@dataclass
class Bucket:
    things: List[str]

leaves = ["leaves"]

def bucket_with_sand(things: List[str]) -> Bucket:
    return Bucket(things + ["sand"])

bucket_with_sand(leaves)  # can be replaced with Bucket(["leaves", "sand"]) with no change to the program

whereas this function alters leaves and so replacing the function call with its result doesn’t mean the same thing. It’s no longer referentially transparent:

def bucket_with_sand(things: List[str]) -> Bucket:
    things += ["sand"]
    return Bucket(things)

In a language with move semantics like Rust’s, we can avoid this problem by moving leaves (and relying on the fact that Vec is non-Copy):

struct Bucket {
    things: Vec<&str>,
}

let leaves = vec!["leaves"];

fn bucket_with_sand(things: Vec<&str>) -> Bucket {
    things.push("sand");
    Bucket { things }
}

bucket_with_sand(leaves); // mutates `things`
// doesn't matter that `things` has been mutated here as it's now out of scope

This appears to be referentially transparent again. Is this correct? Do such moves relax conventional constraints on RT design? Or are moves not referentially transparent? I’m particularly interested to know if there are there broader implications on RT that I’ve not seen.


Get this bounty!!!

#StackBounty: #python #functional-programming #asynchronous Write a wrapper to REST API with asyncio

Bounty: 100

I want understand how to correctly structure a functional asyncio-based program.

The code below wraps two external APIs to provide the client a simple send_weather() function. Its structure reflects my current understanding of ansynchronous programming and the very little I’ve grasped of functional programming.

import asyncio
from functools import partial

import aiohttp


SUCCESSFUL_PUSH = {'deleted': True}  # Value specific to fake push service


async def _post(headers, url, data):
    async with aiohttp.ClientSession(headers=headers) as session:
        async with session.post(url, json=data, verify_ssl=False) as response:
            return await response.json()


async def _get(headers, url):
    async with aiohttp.ClientSession(headers=headers) as session:
        async with session.get(url, verify_ssl=False) as response:
            return await response.json()


def make_comms(headers):
    get = partial(_get, headers)
    post = partial(_post, headers)
    return get, post


async def _notify(post, message, user):
    url = f"https://api.keen.io/dev/null?user={user}"  # Fake push service
    return await post(url, message)


async def _find_city(get, city):
    url = f"https://www.metaweather.com/api/location/search?query={city}"
    obj_list = await get(url)
    if obj_list:
        return obj_list[0]
    return None


async def _city_weather(get, city_id):
    url = f"https://www.metaweather.com/api/location/{city_id}"
    return await get(url)


async def _send_weather(get, post, city, user):
    city_data = await _find_city(get, city)
    if city_data is None:
        print("Could not find city")
        return
    forecast_data = await _city_weather(get, city_data["woeid"])
    weather = forecast_data["consolidated_weather"][0]["weather_state_name"]
    message = f"Current weather in {city}: {weather}"
    reply = await _notify(post, {"message": message}, user)
    if reply == SUCCESSFUL_PUSH:
        print(f"Current weather in {city}: {weather}")
    else:
        print(f"Push notification to {user} failed: {reply}")


def init(get, post):
    return partial(_send_weather, get, post)


if __name__ == "__main__":
    HEADERS = {"Content-Type": "application/json"}
    get, post = make_comms(HEADERS)
    send_weather = init(get, post)
    asyncio.run(send_weather("Glasgow", "Bob"))

How to structure an asynchronous functional program?


Get this bounty!!!