Lambda the Ultimate

Feather’s lack of heap is accomplished by extending the end frame pointer for previous stack frames whose return slot uses the data of the successive frames that the end frame pointer is extended over. This elides the need for any type of garbage collection. The cost is that a bunch of dead ‘popped’ variables also get extended over, but this shouldn’t be a big problem in practice when using the techniques described next. Feather can also return closures, but that means the end frame pointer must be extended over the closed-over values, so they must be used with caution.

Non-consable return values are placed at the beginning of the next stack frame and the previous end frame pointer is extended over it.

Consable return values like lists and maps are treated with more care. When a consable value is to be returned, 8 to 32 slots are allocated at the beginning of the new stack frame, and any conses that take place on the consable return value are placed in one of those slots. (In fact, there may need to be a way to specify what the beginning slot count should be for a given function call.) Further, any conses on those conses will also be placed in one of those slots. If the return slots are finally filled, then n * 4 new slots are allocated past the last stack variable for further use, and so on. An analyzer could be hooked in at run-time to track the average and max allocations needed at each call site to eliminate most needs to do secondary (and so on) allocations for consable return values.

There may also be a special cons that allows temporary conses to be used on consable return value that are _not_ placed in the return slots. If one of these accidentally makes it into the returned cons structure, it will be wasteful due to extending the return frame end pointer over that stack variable - but will not be terminal to the program.

With these technique, I think a minimum amount of space will be wasted on dead varables, but we'll have to see for sure. Tail-call optimizations should be possible with this set up.

There will almost certainly be some restrictions on language's expressiveness due to the heaplessness, but we'll discover and work around those as we go along. For example, I'm not sure if monads will be implementable without a heap, but the syntax is there in case we can.

Some syntax -

/* multi-line comment /* nests */*/
// line comment
/// Documentation comments are done exactly the same as in F#.

// function definition syntax uses powerful mix-fixity and repetition specification
define two as 1 + 1
define double [x] as 2 * x
define [x] times [y] as x * y
define [x] *** [y] precedence 0.5 as x * x * y * y
define if [condition] then [lazy consequent] else [lazy alternate] as condition ? consequent ?? alternate // ? and ?? are the built-in ternary operator
define let ([n] be [x] *and) in [e] with (Name n, Expr e) as…
define sqrt [x] requiring x >= 0 as… // 'requiring' specifies function contract ('ensuring' might mean post-condition).

// function signatures
asFloat :: x -> y |> (Number x, Float y)
let :: ((n, x), e) -> r |> (Name n, Expr e) // function signatures only use the major word

(map)________// partial application. Same as (x, y) ~> x map y
(xs map)_____// same as x ~> xs map x
[map]________// translation to a fully curried function. Same as x ~> y ~> x map y
(f) . (g)____// function composition

() // unit
'c' // char
"string" // string
$(1, 2, 3) // list
$[1, 2, 3] // vector
${1, 2, 3} // tuple
$(("Jim", 1), ("Bob", 2)) // association list
$[["Jim", 1], ["Bob", 2]] // dictionary
${{a, b, c}} // set

double 5
2 times 3
(x + y) * z
x = 5 // equality
x : xs // cons
x | 0xff // all characters in a hex literal must be lower-case (including the 'x' separator)
true & false // and operator (non-short-circuiting version)
true && false // and operator (short-circuiting version)
set x to 5 // x is a variable (mutable)
set x to $(1..5)
set x : xs to $(1, 2, 3)
aVector !! 5 // look up 5th element
lazy 1 + 1 // use lazy evaluation. NOTE: not sure how well this will work in a heapless language…

(x, y) ~> x * x - y
steps print 1 then print 7
if 3 let x be 10 and y be 13 in x + y
$(1, 2, 3) map (+ 3) filter (isOdd) // because of white space, (+ 3) != (+3)
for x from someList and y from $(1..5) and where y isOdd then lift x * y

// recommended indentation
let
____x be 10 and
____y be 88 and
____z be 12 in
____x + y * z

// sequential expression
steps
____print 1 then
____print 7 then
____print "Hi!"

// choice expression
choose
____when x = 5 then print 22
____when x >= 5 then print 33
____when x ____else print 55

// simple match
match m
____with x : xs then x
____with ${x, x, _} then x
____else m

// multi-match
match m and n
____with x : xs and x then m
____else n

// match chain
match m
____with x : xs where x = 5 then xs
____else $()

// restricted match (makes inferred function type more specific when using a match)
match m as Int
____with 0 then 10
____with 1 then 20
____else 100

// monad comprehension
for
____x from someList and
____y from $(1..5) and
____where y isOdd then
____lift x * y

// functional types
data...________// like Haskell data
synonym..._____// like Haskell type
derivation...__// like Haskell newtype
protocol...____// like Haskell class
instance…______// like Haskell instance

----

Error handling - Uses a system similar to scheme's Condition system.

----

Literal numbers are Int by default -
5(u)b________// (U)Byte - 8-bit
5(u)s________// (U)Short - 16-bit
5(u)_________// (U)Int - 32-bit
5(u)g________// (U)Long - 64-bit
5.0__________// Float - 32-bit
5d___________// Double - 64-bit
5(u)n________// (U)NInt – Native-size integer – varies by hardware platform.

----

Function type arrows –
-> - Describes a function of inferred, unspecified, or dependent purity
=> - Describes a pure function
:> - Describes an impure function

----

Uses of semi-colon -
fn (1, 2, 3; 'a', 'b', 'c') // ; separates repeated parameters
fn2 (1, ; 'a') // ; omits optional parameters
class Thing expose attribute Age as var UInt; print 5 // ; manually ends expr scope without a newline. Note that classes aren’t in the language anymore.

----