Lisp

Table of Contents

References

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 conss. 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 cdring 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

Scheme Resources

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"))

When loading guile, certain libraries are loaded by default.

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)

Reading from file:

(use-modules
  ;;for read-line
  (ice-9 rdelim))

(define file (open-input-path file))
(let ((line (read-line 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[0] xss[1] xss[2]...
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

Clojure Resources

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

This content has been automatically generated. For feedback or errata, please email eddie at xiaodi.li.