lviv

lviv is a functional stack-based programming language. Or maybe it's just a fancy programmable calculator.

lviv is written in Scheme. It's possible that it will work in a bunch of different Scheme environments, but I use Gambit-C Scheme v4.6.1 for development, so I don't guarantee that it'll work in any other scheme interpreter.

lviv is an experiment in hybrid functional-stack language design. The idea was to have a very regular syntax that was 100% compatible with postfix notation without requiring a modal interpreter (i.e., no ": ... ;" stuff like in FORTH; this means that everything, including lambda, define, if, let, et cetera, uses postfix notation) and with a minimal number of special forms. The original impetus came from a paper I read about how tail call optimization happens very naturally when the machine model is stack based. Naturally, lviv supports tail call optimization.

The name comes from the city of Lviv, where Jan Lukasiewicz was born. Lukasiewicz invented prefix or "Polish" notation to simplify the syntax of sentential logic; later, Burks, Warren, and Wright (and even later Bauer and Dijkstra) proposed postfix, or "reverse Polish" notation as a good fit for stack based machines.

Examples

Let's look at some example code so you know what you're getting yourself into.

square

> (*x dup *) (*x) lambda *square define
> 5 square
25

factorial

> ((1) (*x dup 1 - *fact *) *x 0 eq? if) (*x) lambda *fact define
> 5 fact
120

fibonacci

> ((swap drop) (dup 3 roll + *x 1 - *fibHlp) *x 0 eq? if) (*x) lambda *fibHlp define
> ((0) (0 1 *x 1 - *fibHlp) *x 1 < if) (*x) lambda *fib define
> 5 fib
5
> 15 fib
610
> 25 fib
75025

We could also do this with the helper defined inside the parent environment:

> ( ((swap drop) (dup 3 roll + **x 1 - **fibHlp) **x 0 eq? if) (**x) lambda
    **fibHlp define (0) (0 1 *x 1 - **fibHlp) *x 1 < if ) (*x) lambda
  *fib define
> 25 fib
75025

Note that the x in the scope of the inner lambda needs to be double-quoted (**x) because we want its interpolation delayed until the inner lambda executes. In general, the number of stars is parenDepth-ifParenDepth if you want the variable's value, or parenDepth-ifParenDepth+1 if you want the literal name.

Accumulator

We define two functions, showA and incA, that show and increment the value of an accumulator, respectively. Note that both functions close over a private environment.

> ( (**n) () lambda (1 **n + **nref define) () lambda 
    *&n **nref define 1 **n define ) () lambda apply
  *incA define *readA define
> readA
1
> drop incA incA incA readA
4
> drop incA incA incA readA
7

Note how here we quote *&n to delay its binding until it is evaluated in the environment of the outermost lambda.

Building and running lviv

The Makefile that comes with lviv should do almost everything you need.

If you just want to run lviv, make run will run lviv with gsi. You can pass arguments by overriding the ARGS variable in your make invocation (e.g., make ARGS="foo.lviv" run), or you can just run gsi directly yourself. make runtest will run the test files in the examples directory using gsi.

The lviv target builds a self-contained lviv executable. test takes this executable and runs the tests from the examples directory. The default target, all, is equivalent to make lviv test.

The debug target invokes gsi with the lviv source files, but leaves you at the Scheme REPL rather than invoking the lviv REPL. This lets you examine the behavior of the interpreter directly.

Finally, there are the profiling targets, prof and profrun, which build the executable with profiling enabled and run this profiling executable on some dummy code, respectively.

Basics

If you've used an HP calculator, you're probably familiar with how RPN works. Expressions are entered by pushing entries onto a stack and applying operators to the stack. Operators pop a defined number of operands off the stack, perform a computation, and push the result back onto the stack. For example,

> 1
1
> 2
1
2
> +
3
> 2 *
6
> 6 * sqrt
6

Order of application

RPN operations are applied in left-to-right order: prefix and postfix notation are related by simply translating the operator from the beginning to the end of the expression. - 6 1 becomes 6 1 -, and both should equal 5. This seems somewhat logical for a calculator, since it matches our intuition for the basic noncommutative arithmetic operations.

At times, this order of operations can be clunky. Thus, any primitive or lambda can be applied in reverse by prepending it with :. Thus, 6 1 - yields 5, and 6 1 :- gives -5.

Stack operations

The contents of the stack often represent most or all of the program's state. Thus, primitive stack operations underly most higher level operations in lviv.

There are no explicit "push" and "pop" operations; values are pushed as they're entered, and popped as needed for function application.

swap

Swap the 0th and 1st entry in the stack.

> 1 2
1
2
> swap
2
1

drop, <n> dropN, clear

drop removes the 0th element from the stack. dropN pops the 0th entry off the stack, and then drops that number of remaining entries. clear drops all entries from the stack.

> 1
1
> drop
> 1 3 2
1
3
2
> dropN
> 

<n> roll, <n> unroll

roll and unroll pop the 0th element off the stack and perform a circular shift upwards (roll) or downwards (unroll) involving n elements.

> 1 2 3 4 5 6
1
2
3
4
5
6
> 3 roll
1
2
3
5
6
4
> unroll
1
6
2
3
5

dup, <n> dupN

dup pushes a copy of the 0th element onto the stack. dupN pops the 0th argument off the stack, and pushes copies of the top n elements onto the stack.

> 1 2 3 dup
1
2
3
3
> 3 dupN
1
2
3
3
2
3
3

over, <n> pick

pick pops the 0th element off the stack, then pushes a copy of the nth element onto the stack. over is equivalent to 2 pick.

> 1 2 3
1
2
3
> over
1
2
3
2
> 2 pick
1
2
3
2
3

depth

Pushes the depth of the stack prior to the depth operation onto the stack.

> 0
0
> depth
0
1
> 2 dropN depth
0

<bool> swapIf, <bool> swapUnless, <bool> dropIf, <bool> dropUnless

swapIf pops the 0th element off the stack, and then performs a swap if that element was #t. swapUnless does the same for #f. dropIf and dropUnless behave similarly. Note that these operations only accept the boolean values #t or #f; other values result in a type error.

> 1 2 #t swapIf drop
2
> clear
> 1 2 #f swapUnless -
-1

nop

Does nothing. It is useful for operations that conditionally modify the stack.

env

Shows the current environment. It can be useful for debugging.

stk

Print the current stack. This is useful during batch execution.

Mathematical operations

All mathematical functions available in Scheme can be bound as primitives in lviv. These should be bound in the prelude when I get around to it :)

Functional syntax

lviv syntax will be somewhat familiar to LISP programmers.

Lists

Formally, a list is defined either as the empty list (nil or ()), or as the result of the cons operation on an element and a list. An element is anything that can be a stack entry.

car and cdr produce the element and the trailing list, respectively. uncons pops a list off the stack and pushes on the cdr, then the car.

(a (b c) d)-like syntax can be used to create a list directly.

> nil
()
> 1 :cons
(1)
> 2 :cons
(2 1)
> (3 4) append
(2 1 3 4)
> uncons
(1 3 4)
2
> :cons
(2 1 3 4)
> cdr
(1 3 4)
> car
1

Tuples

Tuples in lviv can also be constructed using cons. A tuple is simply an unterminated list.

> *a *b cons
(a . b)
> *a *b cons cons
((a . b) a . b)
> (*c *d . (*e . *f))
((a . b) a . b)
(c d e . f)

Environment bindings

<val> <identifier> define

define binds the identifier in the 0th position on the stack with the value in the 1st. If the identifier is a static symbol (&foo), the binding is placed in the attached environment. Otherwise, the binding is placed in the current environment.

Identifiers can contain alphanumerics or any of ! $ % & * + - . / : < = > ? @ ^ _ ~, but must begin with a character that cannot begin a number and is not otherwise reserved (i.e., any valid character other than . + - & * !).

When a bound variable is placed on the stack, it is immediately replaced by its value. To invoke the identifier and force delayed binding, the & or * sigil can be used. The & sigil indicates that the variable is statically bound when pushed on the stack, whereas the * prefix simply places the identifier on the stack, leaving its binding to an environment until evaluation.

> 1 *z define
> 2 z
2
1
> -
1
> (&z +) cons thunk
#<thunk ( 1 &z(env#2) #<primitive +> )>
> 2 *z define
#<thunk ( 1 &z + )>
> apply
3
> (*z &z +) (*z) lambda apply
5

<identifier> undef, <identifier> undefLocal

undef is used to delete a binding from the environment. If the identifier is a static variable, the binding is searched starting in the attached environment and removed if found. Otherwise, the search begins in the current environment.

Note that undef will search from the present environment level all the way up to the top. To prevent the search from extending into the parent of the starting search environment, use `undefLoc