Finding ambiguities in context-free grammars

expression = number | sum
sum = expression + expression

$ cfg-checker example.cfg
....
Found a sentential form with two different derivations:

  expression + expression + expression

Derivation 1:

  0: expression
  1: sum
  2: expression + expression
  3: expression + sum
  4: expression + expression + expression

Derivation 2:

  0: expression
  1: sum
  2: expression + expression
  3: sum + expression
  4: expression + expression + expression

Decomposing a string into its elements

import Data.Char (isLetter, toLower)
import Data.Function.Memoize (memoFix)
import Data.List (intercalate, isPrefixOf)
import System.Environment (getArgs)

elements = [ "H"  , "He" , "Li" , "Be" , "B"  , "C"  , "N"  , "O"  , "F"
           , "Ne" , "Na" , "Mg" , "Al" , "Si" , "P"  , "S"  , "Cl" , "Ar"
           , "K"  , "Ca" , "Sc" , "Ti" , "V"  , "Cr" , "Mn" , "Fe" , "Co"
           , "Ni" , "Cu" , "Zn" , "Ga" , "Ge" , "As" , "Se" , "Br" , "Kr"
           , "Rb" , "Sr" , "Y"  , "Zr" , "Nb" , "Mo" , "Tc" , "Ru" , "Rh"
           , "Pd" , "Ag" , "Cd" , "In" , "Sn" , "Sb" , "Te" , "I"  , "Xe"
           , "Cs" , "Ba" , "La" , "Ce" , "Pr" , "Nd" , "Pm" , "Sm" , "Eu"
           , "Gd" , "Tb" , "Dy" , "Ho" , "Er" , "Tm" , "Yb" , "Lu" , "Hf"
           , "Ta" , "W"  , "Re" , "Os" , "Ir" , "Pt" , "Au" , "Hg" , "Tl"
           , "Pb" , "Bi" , "Po" , "At" , "Rn" , "Fr" , "Ra" , "Ac" , "Th"
           , "Pa" , "U"  , "Np" , "Pu" , "Am" , "Cm" , "Bk" , "Cf" , "Es"
           , "Fm" , "Md" , "No" , "Lr" , "Rf" , "Db" , "Sg" , "Bh" , "Hs"
           , "Mt" , "Ds" , "Rg" , "Cn" , "Uut", "Uuq", "Uup", "Uuh", "Uus"
           , "Uuo" ]

elementize = memoFix (\fn str ->
  if null str
    then return []
    else do element <- filterPrefixes elements str
            soln <- fn $ drop (length element) str
            return $ element : soln)
  where toLowerStr = map toLower
        filterPrefixes prefixes str = filter
          (\x -> isPrefixOf (toLowerStr x) (toLowerStr str))
          prefixes

main = do args <- getArgs
          putStrLn $ intercalate"\n"  $ map (intercalate " ")
            (elementize $ filter isLetter $ concat args)

$ ./elementizer hi esther
H I Es Th Er

1. No N Re P Re Se N Ta Ti O Na Li Sm
2. N O N Re P Re Se N Ta Ti O Na Li Sm
3. No N Re P Re Se N Ta Ti O N Al I Sm
4. N O N Re P Re Se N Ta Ti O N Al I Sm

The Di Vergent Code

Prologue

Chapter 1

CARNEGIE MELLON UNIVERSITY
proudly presents
an evening with Robert Langdon
Professor of Symbolic Systems, Stanford University

Chapter 2

Welcome to the Lambda Oracle, version 1.0.0.
Copyright © 1936. The Church of Alonzo.
Enter terms at the prompt.
$

Chapter 3

Welcome to the Lambda Oracle, version 1.0.0.
Copyright © 1936. The Church of Alonzo.
Enter terms at the prompt.
$ λx. x
Result: λx. x

$ (λx. x) λx. x
Result: λx. x

$ λf. λx. f x
Result: λf. λx. f x

Chapter 4

$ (λx. x x) λx. x x
(λx. x x) λx. x x
(λx. x x) λx. x x
(λx. x x) λx. x x
(λx. x x) λx. x x
...

Chapter 5

Chapter 6

(λx. x x) λx. x x

λf. (λx. f (x x)) (λx. f (x x))

(λf. (λx. f (x x)) (λx. f (x x))) g
= (λx. g (x x)) (λx. g (x x))
= g ((λx. g (x x)) (λx. g (x x)))

Y λf. λn. 1 if n == 0 else n * f (n - 1) end

Chapter 7

Formalizing dynamic scoping

Lexical vs. dynamic scoping

(function(x) {
  return (function(x) {
    return function() {
      return x;
    };
  })('lexical')();
})('dynamic')

((lambda (x)
  (funcall ((lambda (x)
    (lambda ()
      x
    )
  ) "lexical"))
) "dynamic")

The lambda calculus

Syntax

• Variable: \( x \)
• Abstraction: \( \lambda x . t \) (where \( t \) extends as far right as possible)
• Application: \( t_1 \: t_2 \) (left-associative)

Semantics

Example

Semantics for dynamic scoping

Example

Conclusion

Higher-rank and higher-kinded types

Background: what is parametric polymorphism?

String chooseString(String head, String tail) {
  if (Math.random() < 0.5) {
    return head;
  } else {
    return tail;
  }
}

<T> T chooseValue(T head, T tail) {
  if (Math.random() < 0.5) {
    return head;
  } else {
    return tail;
  }
}

Higher-rank types

String chooseStringWeird(
  <T> BiFunction<T, T, T> randomChoice,
  String head,
  String tail
) {
  if (randomChoice(true, false)) {
    return randomChoice(head, tail);
  } else {
    return randomChoice(tail, head);
  }
}

String bestEditor() {
  return chooseStringWeird(chooseValue, "emacs", "vim");
}

Higher-kinded types

Stack<String> names;

class GraphSearch<T> {
  T<Node> frontier;
}

GraphSearch<Stack> depthFirstSearch;
GraphSearch<Queue> breadthFirstSearch;

Conclusion

Footnotes