ebb

\   INSERTION_SORT
\ 
\   Sort INPUT into ascending order as determined by the LESS_THAN binary
\   predicate. This sorting algorithm is stable.

Let insertion_sort less_than input.
    (list.fold_left
        Func sorted elem.
            Loop left right.
                (Init `nil sorted)      \ Provides args for first iteration.

ebb

Preliminary notes on reading the following Language 84 code:

    - "Let" is used to introduce non-recursive functions.

    - "Define" is used to introduce recursive functions.

    - "For" is often used to write loops but it is actually a general binding
      construct. It is similar to the "where" keyword of other languages in
      that the value expression appears first and is followed by a binding that
      is to be in scope within the value expression.

ebb

Terminals:

    natural_number (regex: 0|[1-9][0-9]*)
    character (examples: 'a', '\'', '"', '\n')
    string (examples: "", "hello", "\treturn \"\";\n")
    ident (regex: [a-z][a-z0-9_']*|[A-Z][A-Z0-9_']*)

    Where, Let, Define, ... (a fixed finite subset of regex: [A-Z][a-z]+)

Nonterminals:

ebb

Notes on infix operators and function application in Language 84


Language 84 is an expression-oriented language with first-class functions and
immutable data.

The first thing to note is that expressions using infix operators or function
application are always parenthesized in Language 84. There are two motivations
for that choice:

ebb

(term {WHERE {binder}})

:where

:rule binder (RULE ident term | TOKENS {ident})

:where

:rule term (ident | char | '[' choice ']' | '{' choice '}' | '(' choice ')')
:rule choice (sequence {'|' sequence})

ebb

\   Binary trees benchmark from the Computer Language Benchmarks Game.
\
\   Sample run with argument 18:
\
\   Language 84:
\
\       real    0m1.542s
\       user    0m1.540s
\       sys     0m0.000s
\

ebb

Define (heap_alloc align size)
    Begin {
        Let start
            Let start (Fetch uint32 heap_top)
            In
            Cond {
            | [align > 4]
                Let c [[align / 4] - 1]
                In
                (and [start + c] (complement c))

ebb

Block
    Let config (parse_command_line)
    In
    Let {paths packages} (parse_packages config.root_path)
    In
    Let program (compile packages)
    In
    (emit config.root_path paths program)

Where

ebb

Block
    Let config
        Let {}
            Let usage "usage: 84 <program>"
            In
            When [OS.argc != 2]
                (OS.die usage)
            End
        In
        {: root_path (OS.argv 1)}

ebb

\   This program is a Rosetta Code exercise called "Floyd's triangle".
\  
\   https://rosettacode.org/wiki/Floyd's_triangle
\
\   The goal is to print out a sequence of numbers in lines of increasing
\   length and to do so in such a way that the numbers appear in aligned
\   columns.
\
\   The program takes a command-line argument that determines how many lines to
\   print.