Walkthrough: building a desk calculator
The dc example in examples/dc/ is a reverse-polish notation calculator
modeled on the Unix dc tool. It's a uniquely fitting example for a
stack-based language: dc itself is a stack machine, so we're building
a stack machine inside a stack machine.
It is also written the way stack code is meant to be written: no named
parameters, almost no locals, and words of a line or two that each do one
thing. This walkthrough explains how it works, section by section. Reading the
full source in examples/dc/dc.qd alongside this page is recommended.
What dc does
dc reads tokens from its input. Numbers are pushed onto a stack; letters
are operators that pop operands and push results.
$ dc
3 4 + p # 3+4, print: 7
5 d * p # 5 squared (d duplicates): 25
16 v p # square root: 4
q # quit
With -e, you can pass an expression directly:
$ dc -e "2 3 * 4 + p"
10
The calculator's stack
The calculator keeps its own stack of f64 values, separate from Quadrate's:
a fixed array of cells, and a count of how many are in use. Both are globals,
because every operator works on them:
var cells:[]f64 = [1024]f64
var depth:i64 = 0
[1024]f64 is an array of 1024 zeros. It never grows: a push onto a full
stack prints an error and is dropped.
Push, pop and friends
Every word that touches the stack is a line:
fn push(v:f64 -- ) { depth Capacity >= if { drop "dc: stack overflow" print nl } else { cells depth rot set depth 1 + -> depth } }
fn pop( -- v:f64) { depth 0 <= if { "dc: stack empty" print nl 0.0 } else { depth 1 - -> depth cells depth nth } }
fn top( -- v:f64) { cells depth 1 - nth }
fn operands( -- a:f64 b:f64) { pop pop swap }
Read push from the left, watching Quadrate's stack:
vis on the stack whenpushstarts. Afnleaves its inputs there; thev:f64in the signature only documents it.cellspushes the array:v arr.depthpushes the index of the first free cell:v arr i.rotbringsvto the top:arr i v, which is whatsettakes.depth 1 + -> depthstores the new count.->into a global is an assignment, like Forth's!.
operands pops the two values an operator works on. b comes off first,
because it was pushed last, so swap puts them back in source order: a b.
Before an operator pops anything, it checks there is something to pop:
fn enough(n:i64 -- ok:i64) { depth swap >= dup not if { "dc: stack empty" print nl } }
fn nonzero(msg:str -- ok:i64) { top 0.0 != dup if { nip } else { swap print nl } }
enough leaves a flag, and says why when it is false. nonzero looks at the
top value without popping it, so a division can refuse a zero divisor before
it has taken anything off the stack.
The operator table
The calculator proper is one switch on the first character of an operator.
Each arm is a line, and leaves 1 to say the operator is known:
fn known(c:i64 -- yes:i64) {
switch {
unicode::plus { 2 enough if { operands + push } 1 }
unicode::slash { 2 enough if { "dc: divide by zero" nonzero if { operands / push } } 1 }
unicode::v { 1 enough if { "dc: square root of negative number" nonneg if { pop math::sqrt push } } 1 }
unicode::p { 1 enough if { top print nl } 1 }
unicode::r { 2 enough if { pop pop swap push push } 1 }
// ... and the rest
_ { 0 }
}
}
2 enough if { operands + push } reads as what it does: if there are two
values, take them, add them, push the sum. Anything longer than a line gets a
word of its own:
fn modulo(a:f64 b:f64 -- r:f64) { dup2 / math::floor * - }
fn divmod(a:f64 b:f64 -- ) { dup2 / math::floor dup push * - push }
modulo is a - floor(a / b) * b: dup2 keeps a b for later, / and
math::floor make the quotient, * multiplies it by b, and - takes that
from a. divmod is the same computation, pushing the quotient on the way.
The operators implemented:
| Op | Description |
|---|---|
+, -, *, / |
Arithmetic |
% |
Remainder (float modulo) |
^ |
Exponentiation |
v |
Square root |
~ |
Divmod (pushes both quotient and remainder) |
p |
Print top without popping |
n |
Pop and print |
f |
Print the entire stack |
d |
Duplicate top |
r |
Reverse (swap) top two |
c |
Clear stack |
z |
Push stack depth |
q |
Quit |
An operator known has no arm for is reported, with its character in octal as
GNU dc does:
fn operator(op:str -- ) { dup 0 strings::char_at known if { drop } else { unimplemented } }
Parsing a token
A token is a number when it starts with a digit, or with _ or - and then a
digit. dc writes negative numbers with _, since - is subtraction:
fn digit_at(tok:str i:i64 -- yes:i64) { over len over > if { strings::char_at unicode::is_digit } else { drop2 0 } }
fn is_number(tok:str -- yes:i64) {
dup 0 digit_at if { drop 1 } else { dup len 1 > if { dup signed swap 1 digit_at and } else { drop 0 } }
}
fn token(tok:str -- ) { dup is_number if { number } else { dup len 0 > if { operator } else { drop } } }
digit_at asks whether there is a digit at position i, and answers 0
rather than reading past the end. token sends a number to number, which
parses and pushes it, and anything else to operator.
Processing a line
A line is a comment-stripped, trimmed string of tokens separated by spaces:
fn uncomment(input:str -- input:str) { dup "#" strings::index_of dup 0 >= if { 0 swap strings::substring! } else { drop } }
fn line(input:str -- ) { uncomment strings::trim " " strings::split! fn { token } each }
strings::split! makes an array of the tokens, and each runs token on
every one. Two spaces in a row make an empty token, which token drops. A file
is a list of lines: run_file reads it whole and runs line on each one of
strings::lines!.
The REPL
The interactive loop reads lines from stdin until the end of input:
fn repl() {
loop {
io::readline switch {
Ok { if { line } else { drop 0 os::exit } }
_ { drop2 1 os::exit }
}
}
}
io::readline leaves a line and a more flag. In the Ok arm the flag is on
top, so if tests it directly: while there is more, the line is run; at the
end of input the empty line is dropped and the program exits cleanly. The _
arm is a genuine read failure, and exits non-zero.
Main and flags
fn main() {
os::args flag::parse
dup "-h" "--help" flag::either if { help 0 os::exit }
dup "-V" "--version" flag::either if { version 0 os::exit }
dup "-e" flag::boolean if { dup "-e" flag::string! line 0 os::exit }
// ... --expression, -f and --file the same way
flag::destroy
repl
}
The parsed flags stay on the stack while main asks about them, each question
starting with a dup so the flags are still there for the next one.
-h/--help→ print help and exit-V/--version→ print version and exit-e EXPR/--expression EXPR→ evaluate EXPR and exit-f FILE/--file FILE→ evaluate FILE and exit- No flags → start the REPL
What this example teaches
- Words of a line: almost every function is one line, and reads as what
it does,
2 enough if { operands + push } - Inputs on the stack: a
fnleaves its inputs there, and the names in its signature are documentation - Globals for state every word shares, assigned with
->as Forth's!stores - A global holding an array, typed and checked like a local
- Dispatch on character using
switchandunicode::constants - Combinators over data:
eachover the tokens of a line and the lines of a file,timesto print the stack - Stack-based thinking at its purest: the program IS a stack machine, and the implementation mirrors that directly
This is a complete, working CLI tool in 140 lines.