heap.plus

# This is a program in (the current version of) PLUS.
# Commentary begins with a hash-mark and extend to the end of the line.
# (I know I said PLUS should be "literate". The design is not finished yet.)

# Every program begins with the keyword "program" and an arbitrary name.
# (The name has a purpose, but this program doesn't use it.)

program arrayHeap

# This program demonstrates a "heap" data structure, which is a container
# of bounded capacity, capable of inserting and removing elements in time
# proportional to log(size), and which always returns the minimal element
# (or maximal element, if so configured). For more information see the
# Wikipedia entry. (Just recall I'm writing as of a min-heap.)

# The syntax for "generic" types will look familiar to Java programmers.
# (Formally, Heap is polymorphic in one parameter.) The last field in the
# "Heap" record is a first-class function. The type annotation establishes
# that it must be a function from pairs-of-E to a 'bool'. Lastly, the
# annotation on field 'heap' is a concise way to refer to an array of E.

record Heap<E> is
    heap: [E]
    size: int
    less: function(E E) -> bool
end
# I'm not sure if I like the "end" token. I might rather rely on indentation,
# the way Python does. I'm already using end-of-line as a syntax feature, as
# you may infer from the definition above.

# In a bow to the venerable Pascal, which was also designed as a teaching
# language, I've adopted its explicit (even verbose) keywords to declare
# functions and procedures. But PLUS has type inference, so there are only
# minimal type annotations in the procedure signature. For example, the type
# of 'e' is completely inferred. And although "Heap" requires a parameter,
# the programmer need not supply it explicitly. Unlike Java, PLUS does the
# sensible thing and infers the remainder of the type. Indeed, you can only
# introduce explicit formal type-parameters in record definitions.

procedure insert(h:Heap; e) is
    if h.size < len(h.heap) then
        insertAt(h, e, h.size)
        h.size := h.size + 1
    else print("FAIL!!! We have no exception handling yet.\n")
end;

# Unlike Pascal, you don't have to declare things "forward". PLUS trusts that
# you'll get around to defining everything you use. (You can even overload
# procedure/function names, within certain Turning-complete bounds.)

# Yes, that's a semicolon at the end of the procedure. Looking ahead, you can
# see that the "end" closing a control structure's statement block has no
# semicolon. This deliberate asymetry is there to help you find the problem
# in case your brackets ever misalign, which has been the cause of annoying
# troubles in my own programming past. On the other hand, I think Visual
# BASIC takes the concept way overboard with "end if", "end while", etc.
# Perhaps a better solution would be to repeat the identifier instead of
# the keyword. Above, that would look like "end insert;"

# Eventually, I hope to get the compiler smart enough to perform constant
# folding and automatic inlining. Therefore, I'm going to completely ignore
# calling overhead for small functions and just use them where they make
# things more clear.

# Arrays are indexed beginning from zero, and I'd like to make use of that
# first cell to hold the first element of the heap. I give below a function
# to calculate the index of the parent node of any given child node.

# Two concepts here:
  # First, you can write single-line functions (or procedures).
  # Second, the "return" statement is spelled "->" (arrow).

function parent(kid) is -> (kid-1) div 2

# From an algorithmic perspective, you'll see I've approached the problem of
# heap insertion without swapping. Instead, I consider that there is a hole
# in the heap at some point. I can slide the hole around by assigning the
# contents of a neighbor into the hole. (The fact that said neighbor still
# holds some value becomes irrelevant; that's where the hole moves to.)

procedure insertAt(h:Heap; entry, k) is
    # Assume the given location 'k' represents a hole in the heap.
    while k > 0 do
        p := parent(k)
        if call(h.less, entry, h.heap[p]) then
            h.heap[k] := h.heap[p]
            k := p
        else break
    end
    h.heap[k] := entry
end;

# Above, the only surprise might be the use of "call". It's a special form
# that just happens to look like a function. Other languages call it "apply".
# This isn't necessarily the final form of this kind of thing. I want some
# kind of explicit syntax to create a reference to a function itself, as
# distinct from the result of calling said function. For now, that's not
# implemented per-se, but you can use lambda expressions to achieve the same
# end at a slight loss in conciseness.

# You'll also notice the "break" statement. It works the same as you're used
# to. You can also label your loops if you need to break out of a nest.
# What Java calls "continue" is spelled "next" in PLUS.

# This next function shows that the arrow statement doesn't jump to the
# end of the function the way "return" does in most other languages.
# Algorithmicaly, the heap property guarantees that the smallest element
# is at index zero. So we just return what's there. But that means there
# is another "hole" in the heap. We'll solve that problem separately.

function remove(h:Heap) is
    if h.size <= 0 then print ("FAIL!!! we have no \"maybe\".\n")
    -> h.heap[0]
    bubbleOut(h)
end;

# The conventional algorithm moves the last element of the heap to the
# front (thus breaking the heap property) and then requires two comparisons
# and one swap per heap rank to bubble the element back out to where it
# belongs - usually the last rank again.

# My approach with a "hole" is a bit different, but it should be rather
# faster on average to remove an element. It first blithely bubbles the
# hole all the way out to the last rank of the heap, deciding the hole's
# path with a single comparison and assignment per rank: the lesser child
# fills the hole. Finally, unless the hole wound up at the very end of the
# heap, fetch the last element and insert it (properly!) into the hole.

# The code below illustrates the use of nested procedures and functions.
# They have access to the variables defined in the enclosing scope, just
# like in Pascal or Lisp. It also shows that single-line while-loops do
# not require the "end" keyword.

procedure bubbleOut(h:Heap) is

    var hole k1 k2
    
    procedure moveHole(x) is
        h.heap[hole] := h.heap[x]
        hole:=x; k1:=x*2+1; k2:=k1+1
    end;
    
    function left() is -> call(h.less, h.heap[k1], h.heap[k2])
    
    # The last "complete parent" is when both children are
    # still in the heap. Thus, the termination condition given.
    
    hole := 0; k1 := 1; k2 := 2
    while k2 < h.size do moveHole(left() ? k1 : k2)
    
    # The "hole" is now either in the last rank, or else on the
    # (zero or one possible) parent of only one child.
    # Move the hole to the very last element of the heap.
    
    last := h.size - 1
    if k1 = last then
        # The hole is that half-parent, so move its only child
        # (which is the end of the heap) to fill the hole.
        h.heap[hole] := h.heap[last]
    else if hole < last then
        # The condition test avoids a pathology when the hole lands
        # at the (old) end of the heap.
        insertAt(h, h.heap[last], hole)
    end
    
    # Finally, shrink the heap by "forgetting" the hole at the end.
    h.size := last
    
end;

# The assignment operator is defined for four kinds of targets:
   # array elements,
   # record fields,
   # local computed-constants, and
   # actual variables.

# Those last two may require some explanation.

# The "var" keyword declares a variable which can change value within its
# scope, and which is visible from nested subroutines. Presently, parameters
# are also treated as variables.

# Assignment to any other name introduces a local computed constant. Its
# scope from the point of assignment to the end of the enclosing "block".
# A "block" is either a routine body, a loop body, or the consequences of
# a conditional statement.

# Notice that you may group a sequence of assignments one one line of code
# by separating them with the semicolon. "break" and "next" may also appear
# after a semicolon.

# The "var" keyword currently has three problems:
### You may supply type annotations, but cannot provide initial values.
### Using the initial garbage will almost certainly crash the interpreter.
### Right now all the declarations have to come before any actual code.

# On the plus side, you may mix variable, type, and function declarations
# in any order.

# Here's how to write a type-constrained variable declaration:
var i : int
# I mentioned "local constants". In the case of reference types, the
# reference is constant but the object referred to may change. (We consider
# strings, numbers, booleans, functions, and enums to be value types.)

# With that in mind, below is how to create a "Heap" instance:

maxSize := 32
myHeap := new Heap(
    heap: array(maxSize),
    size: 0,
    less: \a b(a<b)
)
# You may fill in the fields in any order.
# End-of-line is not significant between parentheses.

####   Lambda Abstraction:

# Take a look at the value given to "myHeap.less". It is a lambda
# abstraction in two parameters (namely 'a' and 'b'). The parentheses are
# mandatory, and delimit the expression. It represents an anonymous function
# nested into the current scope and treated as a first-class value. What's
# more, it has access to local "computed constants".

# If a single parenthetical expression isn't enough power, you may instead
# write any arbitrary line of code between curly braces. For example, this
# could have been written as \ a b { -> a < b }

#### Arrays:

# There are two ways to construct arrays. One is by calling a function.
# The other is with syntax. [a, b, c] is a three-element array.

# As it happens, there are a few overloaded built-in functions for making
# arrays with sensible initial values. The first few take the size of the
# array as a parameter, and they return whatever kind of array you need.
# This is type inference at work again: if you need an array of integers,
# you'll get an array of all zero. Strings? All the empty string. Etc.

# This form of overloading resolves entirely at compile time. And if the
# compiler can't figure out what you need, then you'll get an error message.
# Not to worry; a few well-placed type annotations should fix it.

# The other array-creation function isn't implemented yet. But the idea
# is to call a function with the index to generate the initial values of
# the array.

# And right now there's a small problem: you can't make an array of Heaps!
# The reason is that, as defined, Heap cannot be nil, but the default value
# for a reference type is "nil". So it won't type-check. Of course, you could
# certainly make a linked list of Heaps. But that's another subject for
# another time.

####

# Now it's time to write a main program to drive this beast.
# My plan is to insert all the letters of the alphabet, in the order they
# appear on a QWERTY keyboard, into the heap. I'll print as I go, and when
# done I'll print a line feed (which the JVM will map to CRLF on windows.)
# Once that's done, I will then read (and print) everything back out of the
# heap until it is empty again. If all goes well, the second line will be in
# alphabetical order!

# PLUS presently has no distinct "character" type. I'm not sure if they're
# really necessary in a high-level language anyway. Although it does
# distingush integer from (double-precision) floating-point math...

# I do intend that there should be something like TCL's "for" construct.
# However, up until now I have kept the language slim so that I can focus on
# the essentials instead of debugging context-free grammar specifications.
# Therefore, you get to read another while-loop.

inputs := "qwertyuiopasdfghjklzxcvbnm"
i:=0
while i<len(inputs) do
    char := mid(inputs, i, 1)
    print(char)
    insert(myHeap, char)
    i := i + 1
end
print("\n")

while myHeap.size > 0 do print(remove(myHeap))
print("\n")
end.

# Note the period after that last "end". That's the end of the program, just
# like in PASCAL. No code of any kind can come afterward, except comments.
# And a semicolon is not expected. Maybe that will turn out to be a pain.
# Maybe not. It's hard to say.