manual.lyx

#LyX 1.6.4 created this file. For more info see http://www.lyx.org/
\lyxformat 345
\begin_document
\begin_header
\textclass article
\begin_preamble
\usepackage{tikz}
\end_preamble
\use_default_options true
\language english
\inputencoding auto
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100

\graphics default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize a4paper
\use_geometry false
\use_amsmath 1
\use_esint 1
\cite_engine basic
\use_bibtopic false
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\author "" 
\author "" 
\end_header

\begin_body

\begin_layout Title
Golisp
\end_layout

\begin_layout Standard
Golisp is a dialect of Lisp written in Go
\begin_inset Foot
status open

\begin_layout Plain Layout
http://www.golang.org/
\end_layout

\end_inset

.
 It has features in common with Scheme
\begin_inset Foot
status open

\begin_layout Plain Layout
http://www.schemers.org/
\end_layout

\end_inset

, but is much more basic.
 If you squint hard enough, it's almost compliant with Scheme standards,
 but it doesn't have continuations.
 A very simple evaluation mechanism is used, where the list structure is
 interpreted directly.
\end_layout

\begin_layout Standard
Go seems like a good language for implementing interpreters for other languages
 in.
 It has enough expressiveness to easily define the basics of a Lisp system.
 In particular, the garbage collector, the mechanism for dynamic types and
 built-in maps greatly eased development.
 Some of the built-in APIs and default behaviours are very amenable to this
 kind of system.
 They make parts of it effortless.
\end_layout

\begin_layout Standard
\begin_inset CommandInset toc
LatexCommand tableofcontents

\end_inset


\end_layout

\begin_layout Section
Programming Golisp
\end_layout

\begin_layout Standard
Golisp is written as a library, but a driver for this exists as a command-line
 program, 
\family typewriter
gli
\family default
.
 You can use this program to experiment with the language, or maybe even
 write programs for.
\end_layout

\begin_layout Subsection
Hello world
\end_layout

\begin_layout Standard
A hello world might look something like this:
\end_layout

\begin_layout LyX-Code
(display 
\begin_inset Quotes eld
\end_inset

Hello, world!
\backslash
n
\begin_inset Quotes erd
\end_inset

)
\end_layout

\begin_layout Standard
From this, we can see that strings have C-like syntax: they actually have
 the syntax of Go strings.
 Also, everything is surrounded by parentheses.
\end_layout

\begin_layout Subsection
Get started
\end_layout

\begin_layout Standard
Start the interpreter.
 You will be greeted with a prompt:
\end_layout

\begin_layout LyX-Code
>
\end_layout

\begin_layout Standard
This is asking you to type in an expression.
 You will then get the result of evaluating that expression back.
 Everything in Golisp is an expression.
\end_layout

\begin_layout Section
Embedding Golisp
\end_layout

\begin_layout Section
Base Language
\end_layout

\begin_layout Standard
The core of Golisp is based heavily on Scheme.
 The surface syntax is based on 
\emph on
s-expressions
\emph default
.
 There are a small number of 
\emph on
standard forms
\emph default
, that everything in the language can be reduced to.
 This reduction step is performed by 
\emph on
macros
\emph default
, that are defined in terms of 
\emph on
functions
\emph default
.
 The process of executing a Golisp program involves 
\emph on
evaluating
\emph default
 a series of 
\emph on
expressions
\emph default
, and typically includes 
\emph on
function application
\emph default
 as the main driver of control.
\end_layout

\begin_layout Standard
All of the emphasised terms will be discussed below.
\end_layout

\begin_layout Subsection
S-Expressions
\end_layout

\begin_layout LyX-Code
; a comment
\end_layout

\begin_layout LyX-Code
1 2.0               ; numbers (fixnum, flonum)
\end_layout

\begin_layout LyX-Code
\begin_inset Quotes eld
\end_inset

hello
\begin_inset Quotes erd
\end_inset

             ; string
\end_layout

\begin_layout LyX-Code
hello a + 2cool4u   ; symbols
\end_layout

\begin_layout LyX-Code
(a b c) [d e f]     ; lists
\end_layout

\begin_layout LyX-Code
() []               ; empty lists
\end_layout

\begin_layout LyX-Code
(1 .
 2)             ; pair
\end_layout

\begin_layout LyX-Code
(1 2 .
 3)           ; improper list
\end_layout

\begin_layout Subsection
Golisp Expressions
\end_layout

\begin_layout Subsection
Standard Forms
\end_layout

\begin_layout LyX-Code
(quote 
\emph on
datum
\emph default
)
\end_layout

\begin_layout LyX-Code
(if 
\emph on
test then else
\emph default
)
\end_layout

\begin_layout LyX-Code
(lambda 
\emph on
vars body
\emph default
 ...)
\end_layout

\begin_layout LyX-Code
(set! 
\emph on
var val
\emph default
)
\end_layout

\begin_layout LyX-Code
(define 
\emph on
var val
\emph default
)
\end_layout

\begin_layout LyX-Code
(define (
\emph on
name vars
\emph default
 ...) 
\emph on
body
\emph default
 ...)
\end_layout

\begin_layout LyX-Code
(begin 
\emph on
body
\emph default
 ...)
\end_layout

\begin_layout LyX-Code
(local-environment)
\end_layout

\begin_layout LyX-Code
(
\emph on
f args 
\emph default
...)
\end_layout

\begin_layout Standard
The standard forms essentially define the semantics of Golisp.
\end_layout

\begin_layout Description
quote withholds evaluation.
\end_layout

\begin_layout Description
if conditionally evaluates.
\end_layout

\begin_layout Description
lambda creates functions.
\end_layout

\begin_layout Description
set! modifies variables.
\end_layout

\begin_layout Description
define mutates the local environment.
\end_layout

\begin_layout Description
begin groups expressions to be evaluated sequentially.
\end_layout

\begin_layout Description
local-environment evaluates to the current environment.
 It's an experiment.
\end_layout

\begin_layout Description
function
\begin_inset space ~
\end_inset

application calls functions.
\end_layout

\begin_layout Subsubsection
Quote
\end_layout

\begin_layout LyX-Code
> (quote a)
\end_layout

\begin_layout LyX-Code
a
\end_layout

\begin_layout LyX-Code
> 'a
\end_layout

\begin_layout LyX-Code
a
\end_layout

\begin_layout LyX-Code
> ''a
\end_layout

\begin_layout LyX-Code
(quote a)
\end_layout

\begin_layout LyX-Code
> (+ 1 2)
\end_layout

\begin_layout LyX-Code
3
\end_layout

\begin_layout LyX-Code
> '(+ 1 2)
\end_layout

\begin_layout LyX-Code
(+ 1 2)
\end_layout

\begin_layout LyX-Code
> (eval '(+ 1 2) (root-environment))
\end_layout

\begin_layout LyX-Code
3
\end_layout

\begin_layout Subsubsection
If
\end_layout

\begin_layout Subsubsection
Lambda
\end_layout

\begin_layout Subsubsection
Set!
\end_layout

\begin_layout Subsubsection
Define
\end_layout

\begin_layout LyX-Code
> (define a 1)
\end_layout

\begin_layout LyX-Code
> a
\end_layout

\begin_layout LyX-Code
1
\end_layout

\begin_layout LyX-Code
> (begin (define a 2) a)
\end_layout

\begin_layout LyX-Code
2
\end_layout

\begin_layout LyX-Code
> a
\end_layout

\begin_layout LyX-Code
2
\end_layout

\begin_layout LyX-Code
> ((lambda () (define a 3) a))
\end_layout

\begin_layout LyX-Code
3
\end_layout

\begin_layout LyX-Code
> a
\end_layout

\begin_layout LyX-Code
2
\end_layout

\begin_layout LyX-Code

\end_layout

\begin_layout LyX-Code

\end_layout

\begin_layout Subsubsection
Begin
\end_layout

\begin_layout Subsubsection
Function Application
\end_layout

\begin_layout LyX-Code

\end_layout

\begin_layout Subsection
Functions
\end_layout

\begin_layout Standard
The core implementation of Golisp, variable management aside, is concerned
 primarily with functions and their application.
 Functions are first-class values and obey lexical scoping rules.
 Functions are properly tail recursive.
 That is, if the last thing a function does is call another function, the
 callee takes the stack frame of the caller.
 This is implemented with a trampoline.
 It only works for functions defined in Golisp; primitives do not benefit
 from this.
\end_layout

\begin_layout Subsubsection
Lambda Expressions
\end_layout

\begin_layout LyX-Code
(lambda 
\emph on
vars body 
\emph default
...)
\end_layout

\begin_layout Subsubsection
Define Statements
\end_layout

\begin_layout LyX-Code
(define (
\emph on
name args 
\emph default
...) 
\emph on
body 
\emph default
...)
\end_layout

\begin_layout LyX-Code
=>
\end_layout

\begin_layout LyX-Code
(define 
\emph on
name 
\emph default
(lambda (
\emph on
args 
\emph default
...) 
\emph on
body 
\emph default
...))
\end_layout

\begin_layout Standard
This can be carried on indefinitely.
 So,
\end_layout

\begin_layout LyX-Code
(define (list .
 xs) xs)
\end_layout

\begin_layout LyX-Code
=> (define list (lambda xs xs))
\end_layout

\begin_layout LyX-Code
(define ((const x) .
 _) x)
\end_layout

\begin_layout LyX-Code
=> (define (const x) (lambda _ x))
\end_layout

\begin_layout LyX-Code
=> (define const (lambda (x) (lambda _ x)))
\end_layout

\begin_layout Subsubsection
Primitives
\end_layout

\begin_layout Standard
Primitives are Golisp functions that are implemented in Go.
 They have the following type signature.
\end_layout

\begin_layout LyX-Code
type Primitive func(args Any) Any
\end_layout

\begin_layout Standard
They provide functionality that is either impossible or very costly to do
 in Golisp.
 This revolves around access to wider system resources and communication
 with them, but also includes things like number manipulation, manipulating
 collections, and so on.
\end_layout

\begin_layout Subsubsection
Application
\end_layout

\begin_layout Standard
The 
\family typewriter
Function
\family default
 interface, that all Golisp functions implement, has one method on it, 
\family typewriter
Apply(Any) Any
\family default
.
 Calling this method will apply the function.
 To call a function from Golisp, place it add the head of a list, with the
 arguments forming the tail.
\end_layout

\begin_layout LyX-Code
> (+ 1 2)
\end_layout

\begin_layout LyX-Code
3
\end_layout

\begin_layout LyX-Code
> (+ (* 3 4) 7)
\end_layout

\begin_layout LyX-Code
19
\end_layout

\begin_layout Standard
There is also a facility for passing a list directly into the arguments
 from Golisp.
\end_layout

\begin_layout LyX-Code
> (apply + '(1 2 3))
\end_layout

\begin_layout LyX-Code
6
\end_layout

\begin_layout LyX-Code
> (apply + 1 '(2 3))
\end_layout

\begin_layout LyX-Code
6
\end_layout

\begin_layout Subsection
Environments
\end_layout

\begin_layout LyX-Code
> (= (local-environment) (root-environment))
\end_layout

\begin_layout LyX-Code
#t
\end_layout

\begin_layout LyX-Code
> ((lambda () (= (local-environment) (root-environment))))
\end_layout

\begin_layout LyX-Code
#f
\end_layout

\begin_layout LyX-Code
> (begin (= (local-environment) (root-environment)))
\end_layout

\begin_layout LyX-Code
#t
\end_layout

\begin_layout Subsection
Evaluation
\end_layout

\begin_layout Subsection
Macros
\end_layout

\begin_layout Section
Library
\end_layout

\begin_layout Subsection
Numbers
\end_layout

\begin_layout Subsection
Strings
\end_layout

\begin_layout Standard
Selecting from, concatenating, searching and converting strings.
 Golisp strings are Go strings underneath, and so behave in similar ways:
 UTF8 encoded, immutable, and so on.
 Converting a string into a vector or list transforms the string into a
 sequence of Unicode codepoints represented as fixnums.
\end_layout

\begin_layout LyX-Code
(string-ref 
\emph on
s idx
\emph default
)
\end_layout

\begin_layout LyX-Code
(string-length 
\emph on
s
\emph default
)
\end_layout

\begin_layout LyX-Code
(string-append 
\emph on
a b
\emph default
)
\end_layout

\begin_layout LyX-Code
(substring 
\emph on
s from to
\emph default
)
\end_layout

\begin_layout LyX-Code
(string-fold 
\emph on
f acc s
\emph default
)
\end_layout

\begin_layout LyX-Code
(string->list 
\emph on
s
\emph default
)
\end_layout

\begin_layout LyX-Code
(string->vector 
\emph on
s
\emph default
)
\end_layout

\begin_layout LyX-Code
(string->symbol 
\emph on
s
\emph default
)
\end_layout

\begin_layout LyX-Code
(string->number 
\emph on
s
\emph default
)
\end_layout

\begin_layout Subsection
Lists
\end_layout

\begin_layout Standard
A 
\emph on
pair
\emph default
 is a container for two objects, the 
\emph on
car
\emph default
 and the 
\emph on
cdr
\emph default
.
 A list is either the 
\emph on
empty list
\emph default
, or a pair with a list as the cdr.
 Lists in Golisp are immutable.
\end_layout

\begin_layout Subsubsection
Primitive Functions
\end_layout

\begin_layout LyX-Code
(cons 
\emph on
a d
\emph default
)
\end_layout

\begin_layout LyX-Code
(car 
\emph on
p
\emph default
)
\end_layout

\begin_layout LyX-Code
(cdr 
\emph on
p
\emph default
)
\end_layout

\begin_layout Subsubsection
General Manipulations
\end_layout

\begin_layout LyX-Code
(list 
\emph on
xs
\emph default
 ...)
\end_layout

\begin_layout LyX-Code
(length 
\emph on
l
\emph default
)
\end_layout

\begin_layout LyX-Code
(reverse 
\emph on
l
\emph default
)
\end_layout

\begin_layout LyX-Code
(append 
\emph on
ls ...
\emph default
)
\end_layout

\begin_layout LyX-Code
(zip 
\emph on
ls ...
\emph default
)
\end_layout

\begin_layout Subsubsection
Predicates
\end_layout

\begin_layout LyX-Code
(pair? 
\emph on
p
\emph default
)
\end_layout

\begin_layout LyX-Code
(null? 
\emph on
x
\emph default
)
\end_layout

\begin_layout LyX-Code
(list? 
\emph on
l
\emph default
)
\end_layout

\begin_layout LyX-Code
(list=? 
\emph on
a b
\emph default
)
\end_layout

\begin_layout LyX-Code
(proper-list? 
\emph on
l
\emph default
)
\end_layout

\begin_layout LyX-Code
(improper-list? 
\emph on
l
\emph default
)
\end_layout

\begin_layout LyX-Code
(circular-list? 
\emph on
l
\emph default
)
\end_layout

\begin_layout Subsubsection
Selection
\end_layout

\begin_layout LyX-Code
(caar 
\emph on
p
\emph default
) ...
 (cddddr 
\emph on
p
\emph default
)
\end_layout

\begin_layout LyX-Code
(list-ref 
\emph on
l idx
\emph default
)
\end_layout

\begin_layout LyX-Code
(list-tail
\emph on
 l idx
\emph default
)
\end_layout

\begin_layout LyX-Code
(list-head 
\emph on
l idx
\emph default
)
\end_layout

\begin_layout LyX-Code
(filter 
\emph on
f l
\emph default
)
\end_layout

\begin_layout Subsubsection
Traversal
\end_layout

\begin_layout LyX-Code
(map 
\emph on
f ls ...
\emph default
)
\end_layout

\begin_layout LyX-Code
(for-each 
\emph on
f ls ...
\emph default
)
\end_layout

\begin_layout LyX-Code
(fold 
\emph on
f acc l
\emph default
)
\end_layout

\begin_layout Subsubsection
Conversion
\end_layout

\begin_layout LyX-Code
(list->vector 
\emph on
l
\emph default
)
\end_layout

\begin_layout LyX-Code
(list->string 
\emph on
l
\emph default
)
\end_layout

\begin_layout Subsection
Vectors
\end_layout

\begin_layout Standard
Vectors are equivalent to Go's arrays or slices.
\end_layout

\begin_layout LyX-Code
(vector 
\emph on
xs
\emph default
 ...)
\end_layout

\begin_layout LyX-Code
(make-vector 
\emph on
size fill
\emph default
)
\end_layout

\begin_layout LyX-Code
(vector-ref 
\emph on
v idx
\emph default
)
\end_layout

\begin_layout LyX-Code
(vector-set! 
\emph on
v idx val
\emph default
)
\end_layout

\begin_layout LyX-Code
(vector-slice 
\emph on
v from to
\emph default
)
\end_layout

\begin_layout LyX-Code
(vector->list 
\emph on
v
\emph default
)
\end_layout

\begin_layout LyX-Code
(vector->string 
\emph on
v
\emph default
)
\end_layout

\begin_layout Subsection
Control
\end_layout

\begin_layout Section
The Interpreter
\end_layout

\begin_layout Standard
The Golisp interpreter is a Go type.
 Many of the mechanisms for interacting with a Golisp system involve communicati
ng with this object.
\end_layout

\begin_layout Subsection
Scopes and Environments
\end_layout

\begin_layout LyX-Code
type Any interface{}
\end_layout

\begin_layout LyX-Code

\end_layout

\begin_layout LyX-Code
type Symbol string
\end_layout

\begin_layout LyX-Code

\end_layout

\begin_layout LyX-Code
type Environment map[Symbol] Any 
\end_layout

\begin_layout LyX-Code

\end_layout

\begin_layout LyX-Code
type Scope struct {
\end_layout

\begin_layout LyX-Code
	env Environment
\end_layout

\begin_layout LyX-Code
	parent *Scope
\end_layout

\begin_layout LyX-Code
}
\end_layout

\begin_layout Standard
An environment provides a mapping from Symbols to arbitrary objects.
 A scope strings environments together and co-ordinates evaluation.
 Therefore most of the more interesting methods are on the Scope type:
\end_layout

\begin_layout LyX-Code
func New() *Scope
\end_layout

\begin_layout LyX-Code
func NewScope(parent *Scope) *Scope
\end_layout

\begin_layout LyX-Code
func (self *Scope) Eval(x Any) Any
\end_layout

\begin_layout LyX-Code
func (self *Scope) EvalString(x string) Any
\end_layout

\begin_layout LyX-Code
func (self *Scope) Expand(x Any) Any
\end_layout

\begin_layout LyX-Code
func (self *Scope) Bind(env Environment)
\end_layout

\begin_layout LyX-Code
func (self *Scope) Lookup(x string) Any
\end_layout

\begin_layout LyX-Code
func (self *Scope) Load(path string) os.Error
\end_layout

\begin_layout LyX-Code
func (self *Scope) Repl(in io.Reader, out io.Writer)
\end_layout

\begin_layout Subsubsection
New, NewScope
\end_layout

\begin_layout Standard
New creates a new interpreter.
 This is seeded with a default set of primitives, as well as loading a prelude.
 NewScope creates a scope that can refer to a parent scope.
 You probably won't need to use this unless you're pulling some funny business.
\end_layout

\begin_layout Subsubsection
Eval, EvalString
\end_layout

\begin_layout Standard
Evaluate an expression in the given scope.
 The expression can be either encoded as a string, or as the corresponding
 internal representation.
\end_layout

\begin_layout Subsubsection
Expand
\end_layout

\begin_layout Standard
Take an expression, and perform macro expansion on it, returning the result
 of that process.
\end_layout

\begin_layout Subsubsection
Bind, Lookup
\end_layout

\begin_layout Standard
Bind takes an environment and merges its contents with the scope in question.
 Lookup allows for the retrieval of symbols bound in the current scope.
\end_layout

\begin_layout Subsubsection
Load, Repl
\end_layout

\begin_layout Standard
High-level control of the interpreter.
 Load evaluates the contents of a file in the current scope.
 Repl connects to a reader and writer (typically stdin and stdout respectively)
 and reads lines in, evaluates them and then prints them, until EOF.
 Your basic interpreter loop.
\end_layout

\begin_layout Section
Errors
\end_layout

\begin_layout Standard
Go raised some consternation from some quarters when it was revealed because
 it lacked exceptions.
 It may surprise those who made such statements that the author of this
 document is somewhat embarassed to reveal that Golisp currently handles
 errors in much the same way as exceptions.
 This is because a much more powerful notion, one that encompasses exceptions,
 breaks, continues and immediate returns, coroutines and whatever else the
 clever hacker can imagine, exists in Scheme.
\end_layout

\begin_layout Standard
Errors are objects that are treated specially by the runtime.
 All of the internals of the interpreter will ferry an error object up the
 call chain.
 Primitives must handle error objects explicitly, in much the same way as
 errors in Go are normally handled.
 
\family typewriter
Failed(x)
\family default
 will return true if 
\family typewriter
x
\family default
 is an error object.
 The obvious thing to do with error objects is to return them immediately;
 Golisp provides mechanisms for handling errors within the language.
 This is your basic try-catch mechanism.
 Full continuations may appear at some point; until then, this special case
 is most pressing.
\end_layout

\begin_layout Subsection
Emission
\end_layout

\begin_layout LyX-Code
(throw 
\emph on
kind
\emph default
 
\emph on
msg
\emph default
)
\end_layout

\begin_layout LyX-Code
(error 
\emph on
msg
\emph default
)
\end_layout

\begin_layout LyX-Code
(type-error 
\emph on
type x
\emph default
)
\end_layout

\begin_layout Standard
Signal different kinds of error.
\end_layout

\begin_layout Subsection
Reception
\end_layout

\begin_layout LyX-Code
(catch 
\emph on
thk hnd
\emph default
)
\end_layout

\begin_layout Standard
Call thk, and if it results in an error, call hnd with the properties of
 the error.
 If an error was raised, catch evaluates to the result of 
\family typewriter
hnd
\family default
, otherwise it evaluates to the result of 
\family typewriter
thk
\family default
.
 An error may be signalled in 
\family typewriter
hnd
\family default
, at which point another handler further up the chain is invoked.
 The handler for 
\family typewriter
load
\family default
 stops and rethrows the error object; it is up to the programmer to handle
 abnormal termination.
 The REPL installs a handler that simply prints the error and carries on.
\end_layout

\begin_layout LyX-Code
> (/ 1 0)
\end_layout

\begin_layout LyX-Code
error: division by zero
\end_layout

\begin_layout LyX-Code
> (catch (lambda () (/ 1 0)) (lambda (kind msg) msg))
\end_layout

\begin_layout LyX-Code
\begin_inset Quotes eld
\end_inset

division by zero
\begin_inset Quotes erd
\end_inset


\end_layout

\begin_layout LyX-Code
> (catch (lambda () (/ 1 0)) (lambda (kind msg) (throw kind msg)))
\end_layout

\begin_layout LyX-Code
error: division by zero
\end_layout

\begin_layout LyX-Code
>
\end_layout

\end_body
\end_document