# Lisp

## History

• Fully parenthesised Polish prefix notation - second oldest programming language after Fortran.
• Most common dialects are Common Lisp and Scheme
• Originally created as a practical mathematical notation for computer programs, but heavily used in AI research.
• All program code is written as s-expressions, or parenthesised lists.
• There is no distinction between expressions and statements - when an expression is evaluated, it produces a value which can then be embedded into other expressions
• McCarthy originally envisaged Lisp to have M-expressions, but never got round to finishing the implementation

## Introduction

A Lisp list is written with its elements separated by whitespace, surrounded by parenthesis.

`(1 2 foo)` is a list with three elements - 1, 2, foo. `Foo` would be a Lisp-specifc data type called a symbolic atom.

The empty list `()` is also represented as the special atom, `nil`. This is the only entity in Lisp which is both an atom and a list.

Expressions are written as lists, using prefix notation. The first element in the list is the name of a form, i.e. a function, operator, macro. The remainder of the lists are the arguments.

`(list, '1 '2 'foo)` evaluates to the list (1 2 foo) (The `'` in front of the arguments prevents the quoted arguments from being evaluated. Any unquoted expression are recursively evaluated before the enclosing expression is evaluated.

Arithmetic operators in Lisp are variadic, which means that they are able to take any number of arguments.

A Lisp list is a singly linked list. Each cell is called a `cons` (or a pair, in Scheme), and is composed of two pointers, called the `car` (data) and `cdr` (next cons).

A proper list is either the special `nil` symbol, or a `cons` in which the car points to a datum.

A list is nothing more than a aggregate of linked `cons`s. A variable which refers to a given list is simply a pointer to the first cons in the list, and a traversal of a list can be done by `cdr`ing down.

Lists can be created using the `list` procedure, which takes any number of arguments and returns a list of those arguments:

``````(list 1 2 'a 3)
;Output: (1 2 a 3)``````

The `cons` procedure can be used to add an element to the front of the list.

The `append` procedure appends two lists to one another. Appending two lists has asymptotic time complexity.

Two lists may have the same tail, or final sequence. May improve performance, can be undesirable as it might create untracked dependencies.

Lisp languages are frequently used with an interactive command line, which may be combined with an IDE. This cycle is known as an REPL (read evaluate print loop).

## Macros

From GNU Scheme's guide, based on R4RS: (http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Macros.html)

Have syntax `(macro-name macro-args ...)`

• `define-syntax`
• `let-syntax`
• `letrec-syntax`

## Implementations

TODO: Move these to their own files.

### Scheme (with Guile interpreter)

• Generally, use the file extension `.scm`

• `srfi-42`, a library that supports list comprehensions, isn't available in standard cygwin packages. Definitely present in guile2.0, though.

• `reduce` is a variant of fold, using the first two elements from lst, rather than one element and a given value:

reduce proc default lst

#### Guile

Guile is an implementation of the Scheme programming language, supporting the Revised language reports and the SRFIs.

Open guile interpreter in cygwin shell:

``guile``

`(quit)` exits the interpreter

To load guile with a script, use

``guile -l my_script.scm``

To print stuff, use `display`:

``(display "hi there!")``

New lines can also be added:

``(newline)``

Get the current working directory of the Guile Repl with `(getcwd)`. Amend this with `(chdir (string-append (getcwd) "/bioinformatics"))`

#### Idioms

##### Debugging

On error, use `,bt` to enter debugger. `,locals` to see current assignments

##### IO

Writing to file:

``````(define file (open-output-path file))
(display "stuff to write here" file)
(close-output-port file)``````

``````(use-modules
(ice-9 rdelim))

(define file (open-input-path file))
(munge it...))``````
##### Creating and using modules

Exports the procedure `graph` in the file

``````(define-module (proteomics spectrum)
#:export (graph))``````

Imports

##### String operations

Casting:

``(number->string 1) ; "1"``

Concatenation:

``(string-append "asd" "dsa") ; "asddsa"``

Joining a list of strings:

``(string-join `("a" "b" "c") " ") ; "a b c"``
##### Transpose a list of list (matrix)
``````(define (transpose xss)
(apply map list xss))``````
• `apply`: `apply proc arg ... arglst` takes a function, up to n args and then a list of args. It calls the function using the list as its own argument list
• `map`'s signature is `map proc arg1 arg2 ...`
• `list`'s signature is `list elem ...`

So:

``````apply proc arg ... arglst
map  list     xss

map proc  arg1    arg2   arg3 ...
list xss xss xss...``````
##### List generation

From srfi-1

Range:

``````(iota 5 1)
;; (1 2 3 4 5)``````

Fill:

``````(make-list 4 "cats")
;; ("cats" "cats" "cats" "cats")``````

Transpose:

``````(define sample-data-points `((17 0 -4)
(3 14 23)
(9 7 17)
(7 3 5)))

(define (transpose xss)
(apply map list xss))

\$4 = ((17 3 9 7) (0 14 7 3) (-4 23 17 5))
(transpose sample-data-points)``````
##### Creating a map

Probably still better to use a hash table, as association lists are linear in search time

### Higher order functions

#### For each

For mapping in order to induce side effects, use the `for-each` procedure http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Mapping-of-Lists.html

``for-each procedure list list...``

Mapping, but for side effects

### Control structures

#### Do...while

``````(do (
(i 0 (+ i 1)))
((= i 10))
(func-a 1 2)
(func-b 1 2))``````

#### cond

To avoid nesting a bunch of if statements

``(cond (clause1) (clause2) ... )``

### Simple data types

• Booleans - either true of false. `#t` for true, `#f` for false.
• Numbers either integers or floating points
• Strings - use `\n` to denote a newline

### Comparisons

• `eq?`: same object in memory.
• Use this one to compare symbols: `(= 'red 'red)`
• `eqv?`: same object in memory, or same primitive
• `equal?`: checks lists, vectors etc. for `eqv?` (Source)

#### Pairs

"A pair (sometimes called a dotted pair) is a data structure with two fields called the car and cdr fields (for historical reasons). Pairs are created by the procedure cons. The car and cdr fields are accessed by the procedures car and cdr."

Building blocks for lists in Scheme:

contains the `car` and `cdr`:

car: holds the value cdr: holds the pointer to another pair or an empty list

• created using the `cons` operator:

(cons 4 '()) ; => (4)

• The period `.` is an indication of the pair.

• Pairs can also be entered as literal values by preceding them with a single quote character.

• The first and second elements of the pair can be accessed by the procedures `car` and `cadr`, respectively.

• An improper list is a chain of pairs that doesn't end with the empty list:

(cons 4 5) ; => (4 . 5)

### Quoting

Prepending a quote (') before a list makes sure that the list is treated as data, rather than a procedure

``````'(1 2 3 4) ;=> (1 2 3 4)
'(+ 2 3 4) ;=> (+ 2 3 4)
(+ 2 3 4) ;=> 9``````

In guile, you need to use a backtick instead:

```(1 2 3) ;=> 6``

### Lists

• A list is either the empty list `()`, or a pair whose `cdr` (the second element, remember?) is a list.
• Scheme expressions are all lists.
• Get length of list with `length`
• Create a list of the same element with `make-list 3 #t`

### Strings

``(string-append str1 str2)``

Convert a string into a list of chars for iteration with `string->list str`

https://www.gnu.org/software/guile/manual/html_node/List_002fString-Conversion.html

### Characters

• starts with `#\`, e.g. `#\S` for upper case S
• `#\space` is whitespace

Conversion to string:

``(string #\a) ; "a"``

Compare characters with `char=?`

https://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Comparison-of-Characters.html

### Vectors

Similar to lists, but preceded with a hash `#`

``#(this is a vector)``

### Arrays

https://www.gnu.org/software/guile/manual/html_node/Array-Procedures.html

``(array->list arr) ; converts arr to a list``

### Procedures

First class objects in the language - refer to procedures the same way as refering to any other object, via a pointer, and a procedure name is just a variables name, i.e. a pointer to anything

Defining a procedure in Scheme is really just defining a variable and giving it an initial value that's pointing to a procedure object

``````(define(double x)
(+ x x))``````

is the same as:

``````(define double
(lamdba (x)
(+ x x)))``````

which is defining a variable called double, initialising it with the result of the second expression, which is a lambda expression

For a function that makes many arguments (variadic), use the dot operator, `.`. Example

Can also define a `rest-id` like:

``(lambda x x)``

Which can be called: `((lambda x x) 1 2 3))` to give `(1 2 3)`, which is kind of like a variadic function

#### Association lists

Used to stored data for easy retrieval. Elements are pairs - `car` of each element is called a key, and the `cdr` of each element is called the value.

#### Hash tables

Similar to an array, but indexes to the array (what are these? You haven't mentioned them) can be any type of Scheme value, not just integers.

#### Lets, defines

• Idiomatically, use `define` to add something to the REPL environment, use `let` to do stuff within a defintion (easier than writing even more lambdas)

### Clojure

Compiled into JVM bytecode

#### Functions

• Anonymous function:

(fn [who] (str "Hello, " who "!"))

• Named function:

(def hello (fn [who] (str "Hello, " who "!")))

• Full syntax:

(defn ; Start a function definition:

``````   hello                               ; name
"Gives out personalized greetings." ; a optional docstring
[who]                               ; parameters inside brackets
(str "Hello, " who "!"))            ; body``````

### Leiningen

Dependency management tool for Clojure

#### Useful commands

• `lein repl`
• `lein midje`
• `lein repl`

#### REPL

• Use `(use 'training-day)` to load up a clojure file.
• Use `(use 'training-day :reload)` to reload that file.

### Misc

• `;` denotes an inline comment, and will be indented accordingly by Emacs
• `;;` denotes a comment referring to the following line of code
• `'` is an alias for the `quote` special term
• Use `(use 'clojure.repl)` to get the `doc` function that fetches documentation for a function
• Use `(use 'clojure.repl)` to get the `doc` function that fetches documentation for a function
• Use `(user/clojuredocs min)` to see examples of that function being used (not working from lein 2.3.4 onwards - use this site instead).

## Glossary

• apply: Function that applies a list to another function
• eval: A function that takes any number of arguments
• variadic function: A function that takes any number of arguments
• SRFI: Scheme Requests for Implementation: effort to collaborate on libraries and extensions of standard Scheme

## Common Lisp

Some different terminology between CL and Scheme:

• `define`/`defvar``define`
• `funcall``apply`
• `mapcar``map`

### SBCL

Open Source Common Lisp compiler

Can install with `brew install sbcl`

Check pwd of the interpreter with `(sb-posix:get-cwd)`. See here for some others

Check cwd with `(truename ".")` Source