Power sets

It all started out when a friend of mine(check him out) told me a story about someone having an interview at Google. He was live coding and asked to implement a function that computes a power set of a given set. He totaly over-engineered it and after an hour of fiddling came up with 4-liner in python. Ok. Big deal. How hard can it be? I immediately started to brainstorm a solution of my own(and Matevž helped). Paraphrased train of thought below.

So what is a power set? Say a power set of set A. It's a set of all subsets of A. It's all possible combinations of including and excluding single elements. So it's like applying filters to the original set. Wait a sec, a set of size n has 2 to the n-th power subsets. It all matches up. N-bit number are said filters. So you count from 0 to 2^n-1 you enumerate exactly all the filters and therefore all the subsets. You just calculated the power set. This took about 30sec in real time.

Another minute to sketch the implementation.
You implement set as Lists. Let's say Java is the language of choice. An
y reasonable input would be shorter than 64 elements, at least on current machinery. So long can be used as counter. And now a nested for loop to iterate over elements and appending them if counter && (1 << n). Simple.

Won't post the code since I never wrote it.

The original blogpost

This happened in a lab at Faculty for Computer and Information science. On my way home I started thinkking....what is that 4-line implementation? It can't be my algorithm, that won't fit - it just isn't that elegant. Matevž also told me who was the original author and it was someone whose blog I was subscribed to(I still am, it's pretty awesome, check it out). So I searched for the original blogpost. And found it. It wasn't four lines. And it was(as Swizec admits) wrong.

def powerset(set):
      binaries = [bin(a) for a in range(2^len(set))]
      power = []
      for yeses in binaries:
        subset = []
 yeses = str(yeses)
 for i in range(len(yeses)):
                 if yeses[i] == “1”:
          subset.append(set[i])
 power.append(subset)
      return power

But more importantly, it's essentially my algorithm. (And it didn't took him an hour, read the post, it's interesting)

And then I realised. This is ugly. Quite ugly. It may be efficient and allow for doing iteration and evaluating it lazily, but oh boy it's ugly. Can't it be done in a simpler way?

Recursive solution

So by asking how I compute a power set I obtained the imperative algorithm above.

Balanced tree (Photo credit: Wikipedia)

 Time to change the question. What is a power set? 

It's a set of leaves of a balanced binary decision tree. Every inner node represents a decision to either take or leave out the element at respective index(I assume elements are indexed). That is root node responds to first element, it's children to second element, etc. Every leaf can be computed by following the decision path.  It's a recursive structure. So the tree can be decomposed to left and right subtree and recombined. An this is repeated until you get to leaves. So a power set of A is an union of the power set of "A minus the first element" and the same power set again but with every subset added the first element. Subtrees are represented by the two powersets and the recombination by adding head element to one set of sets and then doing the union. And to stop the recursion: power set of an empty set is a set containing just an empty set. 

My attempt to formally express what I just written:

Now let's do that in code, my language of choice now is scala

def power[A](set: List[A]): List[List[A]] = set match {
    case Nil => List(Nil)
    case head::tail => power(tail) flatMap (set => List(set, head::set))
}

Yay just four lines. and the last one barely matters. But I can do even better. The same code in haskell

power [] = [[]]
power (head:tail) = power tail >>= \set ->[set, head:set]

Both code snippets don't comply exactly to the equation. I swapped in flat-map instead of union. It gets rid of repetition(but I don't know the math notation, sadly). So you apply the lambda that creates both sides of the union to your list and then flatten it to produce the same result.

This code may look a bit cryptic at first sight but once you parse the syntax you can grasp the intention much more quickly than the imperative version. At least I can. Recursion is quite nice once you get used to it.

Related articles

• Making a programming language: Part 3 - adding features
• Python and lazy evaluation
• The birth of LISP - a summary of John McCarthy's original paper
• When Is a Set Better Than an Array in Ruby?

Making a programming language: Part 3 - adding features

Table of contents, Whole project on github

So now I have a repl that can evaluate stuff like

(2+3)*(7/2-1)

Not much of a programming language - more like a calculator, and not even a good one. Lets add some features!

Constants

Like pi, e and such. I have to change the grammar to match identifiers to.

Now I have

private def factor: Parser[Expression] = number | ("(" ~> expr <~ ")")

And I change that to

private def factor: Parser[Expression] = value | parenExpr 

private def value: Parser[Expression] = number | identifier

private def identifier: Parser[Identifier] = "[a-zA-Z]\\w*".r ^^ {
  s => Identifier(s)
}

and I also added a new token type

case class Identifier(id: String) extends Expression

and enabled this in evaluator

case Identifier(name) => {
  StdLib(name) match {
    case Some(v: Double) => v
  case _ => throw new SemanticError(name + " not found")
  }
}

StdLib is just a map object. I went the python way - variables(and constants) are entries in a global dictionary. Just a decision I made whil implementing this. As I said, I don't have a plan, I don't know what I'm doing and I don't know how stuff is done. How hard can it be?! (Top Gear anyone?)

Exponentiation

Another math feature. It's more of a test for myself to see if I understand grammars. Especially how to make a grammar not left-recursive. Because apparently such grammars don't work with RDP. I turned out I don't understand grammars.

private def exponent: Parser[Expression] = (value | parenExpr) ~ "^" ~ (value | parenExpr) ^^ {
  case a ~ "^" ~ b => Exponent(a,b)
}

private def factor: Parser[Expression] = (value ||| exponent) | parenExpr

The ||| operator is an ugly hack. It tries both sides and returns the longer match. By the time I was writing this I didn't know that order is importat. If I just wrote exponent | value it would have worked, because expoenent would match a value anyway and then failed on missing ^.

Token and evaluation(uses math.pow) for this are quite trivial.

Function calls

case class ExpList(lst: List[Expression]) extends Expression
case class FunctionCall(name: Identifier, args: ExpList) extends Expression

Simple: function call is a name and list of expressions to evaluate for arguments(wrapped because even an expression list is an expression):

Parser:

private def arglist: Parser[ExpList] = "(" ~> list <~ ")"

private def functionCall: Parser[FunctionCall] = identifier ~ arglist ^^ {
  case id ~ args => FunctionCall(id, args)
}

private def value: Parser[Expression] = number | (identifier ||| functionCall)

Again, I was having trouble - parser just didn't work and resorted to |||. functionCall should come before identifier.

Evaluating this is more interesting. I decided to make functions be values too for obvious reasons -> higher order functions(I'm into functional programming, remember?). So function values must be stored in same "namespace". StdLib(the only "namespace") required to become of type Map[String,Any]. I will have to do pattern matching anyway since this will be dynamic-typed language. (Yes this is a plan, I think it's easier to implement. Static typing ftw, but that's next project). And I needed a type for function values to pattern match on - I went with Any=>Any and sending in List(arg0,arg1,...) doing more pattern matching inside the function. Will be slow but hey...dynamic typing!

from evaluator

case FunctionCall(name, args) => {
  StdLib(name.id) match {
    case Some(f: FunctionVarArg) => f.apply(apply(args))
    case None => throw new ScratSemanticError("function " + name + "not found")
  }
}

and and example function in StdLib

type FunctionVarArg = Any => Any

lazy val ln: FunctionVarArg = {
  case (d: Double) :: Nil => math.log(d)
  case other => throw ScratInvalidTypeError("expected single double but got " + other)
}

Conclusion

As clearly illustrated above, not planning your grammar results in constant changes in many places. So if you're doing something serious just make the whole fricking grammar on a whiteboard beforehand. Seriously. 

Anyway..now I still only have a calculator, but a much more powerful one. I can write expressions like

e^pi
ln(10+2)
1+2*3/4^5-log(e)

But that's nearly not enough. I want to be Touring-complete an ideally to be able to compile/interpret itself.

next: Hello World(strings, printing and interpreter)

Related articles

• Why I don't use a Parser Generator
• Parsers! How do they work?
• Keeping multiple programming languages straight
• How to Pick a Programming Language
• The Most Pressed Keys in Various Programming Languages

Making a programming language: Part 2 - something that kinda works

Table of contents, Whole project on github, relevant version on github

In the Part 1 I posted a working repl(read-eval-print-loop) for simple math expressions but I kinda cheated and only explained how I built the AST.

AST elements

Just scala case classes

sealed trait Expression
case class Number(n: Double) extends Expression
case class Add(left: Expression, right: Expression) extends Expression
case class Subtract(left: Expression, right: Expression) extends Expression
case class Multiply(left: Expression, right: Expression) extends Expression
case class Divide(left: Expression, right: Expression) extends Expression

Parser combinators revisited

I use power of scala library to cheat a bit and do lexing and parsing in one step.

Basic parser combinators from scala api documentation, everything you need to define productions in your grammar.

p1 ~ p2 // sequencing: must match p1 followed by p2
p1 | p2 // alternation: must match either p1 or p2, with preference given to p1
p1.?    // optionality: may match p1 or not
p1.*    // repetition: matches any number of repetitions of p1

However, to transform the matched string to an AST you need something more

private def number: Parser[Expression] = """\d+\.?\d*""".r ^^ {
  s => Number(s.toDouble)
}

Firstly, in the RegexParser class is an implicit conversion from Regex to Parser. So I could write

private def number: Parser[String] = """\d+\.?\d*""".r

Notice the type annotation. Inferred type would be Regex, since this function is private I can still have implicit conversion, but I rather have all parsers be of type Parser[_].

The ^^ part is an action combinator - a map function. But as ^^ is only available on Parser instances my regex has already been implicitly converted. So in my lambda I already know(scala can infer) the type of s to be String.

One last example

private def term: Parser[Expression] = factor ~ rep(("*" | "/") ~ factor) ^^ {
      case head ~ tail => {
        var tree: Expression = head
        tail.foreach {
          case "*" ~ e => tree = Multiply(tree, e)
          case "/" ~ e => tree = Divide(tree, e)
        }
        tree
      }
    }

Function rep is also from Parsers class matches any number of repetitions(including 0). Here's the type signature

def rep[T](p: ⇒ Parser[T]): Parser[List[T]]

The catch here is that ~ returns a single parser that matches both sides, but fortunately it can be pattern matched to extract both sides. And I can even use meaningful names since I am in fact matching a head with an optional tail.
Inside the case statement I used more imperative style to build a tree, nothing fancy here. Folding was a bit awkward in this case for me(maybe I'm just incompetent) so I went with a for each loop.

Apply the same pattern to +/- part and you have yourself a tree.

Oh, yeah...and the top parser function. A bit changed from last time, to yield useful error messages

def apply(s: String): List[Expression] = parseAll(expr, s) match {
    case Success(tree, _) => Right(tree)
    case NoSuccess(msg, _) => Left(msg)
}

Evaluator

Now what I promised in previous post - evaluation. At first I planned on compiling the code for JVM but I just wanted to see some results first so I decided to do a simple interpreter, no compiling whatsoever - for now.

My first approach was to modify the Expression

sealed trait Expression{
    def eval(): Double  
}

and implement this on all case classes hardcoding the double type and coupling AST representation and evaluation together. Yikes. Granted, it worked, but what an ugly way to do it.

So I did a hard reset(always use git folks! or something similar) and went about doing a standalone evaluator. Since scala's pattern matching skills are awesome and I'm already using case classes why not just do that.

object Evaluator {

    import Tokens._

    def apply(e: Expression): Double = e match {
      case Number(n) => n
      case Add(l, r) => apply(l) + apply(r)
      case Subtract(l, r) => apply(l) - apply(r)
      case Multiply(l, r) => apply(l) * apply(r)
      case Divide(l, r) => apply(l) / apply(r)
    }
  }

This is all the code. Just pattern matching and recursion. But yes, still hardcoded double as the data-type. Looking back, not a great decision...but hey I got something working and this is fun.


next time: Adding features(contsnts, exponents, function calls)

Related articles

• Ambiguous grammar? Could the grammar be parsed by SLR parser?
• ANTLR and traits