ubik / 02a5277 docs / patterns.txt

Tree @02a5277 (Download .tar.gz)

patterns.txt @02a5277raw · history · blame

Conditional blocks in Ubik =============================================
Haldean Brown                                      First draft: May 2016
                                                  Last updated: Jun 2016

Status: In progress
    - Ensure that pattern matches are exhaustive (waiting on type
      inference in order to determine which type is being matched on).


Conditional blocks (cond-blocks) are the base of all control flow in
Ubik; all other statements with conditional behavior are implemented in
terms of cond-blocks. Cond-blocks can take two forms: pattern-matching
blocks and predicate blocks. Pattern matching blocks are like
switch-case statements on steroids; they allow you to match an object to
a set of patterns, and are the operation that give ADTs their expressive
power. Predicate blocks are more similar to the cond macro in Common
Lisp; they take a series of predicates along with the value of the
cond-block expression should each predicate be true.

In order to maintain the totality of the functions at play, each
cond-block is required to handle all possible cases of input. For
pattern blocks, this means that either all cases for the appropriate
type must be handled, and for predicate blocks, it means that there must
be a predicate involved which provably evalutes to true, always.

Cond-blocks are all expressed as curly-brace-enclosed blocks of case
statements; each case statement has a head and a tail, where the head is
that which may or may not evaluate to true or match the expression, and
the tail is the value of the block should the head evaluate to true.

For example, here is what a simple pattern matching block looks like; in
this example, Pair is a type with only one constructor, so only one
pattern is required to match all possible inputs:

        : fst
            ^ Pair a b -> a
            = \p -> ? p {
                . Pair x y => x

Patterns are restricted to unpacking Algebraic Data Types (ADTs).
Another syntactic example, this time with an ADT with two constructors:

        ^ Shape
            = Circle Vec2 Number
            = Rect Vec2 Vec2

        : shape-name
            ^ Shape -> String
            = \x -> ? x {
                . Circle center * => concat "circle " (humanize center)
                . Rect lo hi => "rectangle"

For pattern blocks, the ? operator takes an expression and the block of
case statements. The heads are evaluated in turn; if the head evaluates
to true, the tail of the case statement is executed and nothing after it

Predicate blocks look very similar; they are only missing the expression
to evaluate:

        : is-more-than-10
            = num -> ? {
                . num > 10 => "yes"
                . => "no"

A note on the use of the member operator; without it, the grammar is
unfortunately either whitespace-dependent (no-go) or ambiguous; it would
be otherwise impossible to differentiate this:

        ? { a => b c
            d => e }

From this:

        ? { a => b
            c d => e }

As the member operator cannot appear at the head of an expression, it
disambiguates thw two cases.

When generating code, the following case statement:

        ? {
            . eq num 10 => "yes"
            . => "no"

Becomes the following graph:

        1: const 10
        2: load native://eq
        3: apply 2 1
        4: const "yes"
        5: cond 3 4 6
        6: const "no"

And the following:

        ? x {
            . A fst => fst
            . B fst snd => snd

Becomes the following pseudocode:

        ? {
            ubik-adt-ctor-matches? "A" x => {
                : fst = ubik-adt-get 0 x
                ! fst
            ubik-adt-ctor-matches? "B" x => {
                : fst = ubik-adt-get 0 x
                : snd = ubik-adt-get 1 x
                ! snd

Which is then code-generated in the same manner as the previous example.