less_retarded_wiki

main page, file list (621), source, all in md+txt+html+pdf, commit RSS feed, report abuse, stats, random article, consoomer version

Lisp

{ I'm not a Lisper, let me know if something I claim here is wrong. ~drummyfish }

WIP

Lisp (for "list processing") constitutes a family of minimalist programming languages, such as Common Lisp, Scheme or Clojure, which all descend from an old (1960, by John McCarthy) language called LISP. Given the big number of different Lisp languages (called Lisp dialects) that have spawned from the original LISP along the way (in a fashion similar to Linux distros, just among programming languages), it's hard to make general statements about all of them, but as a high altitude overview let's state this much: Lisp languages are based on functional paradigm and lambda calculus (though not strictly enforcing functional programming, side effects of functions are still allowed as well as imperative and other paradigms), they're high level (but simple), very dynamic and flexible, dynamically typed, usually interpreted (or compiled to bytecode, though some also compile to native code), garbage collected, use a prefix notation with brackets (e.g. (+ 1 2) instead of 1 + 2) and are quite elegant and minimalist -- many hackers consider (some form of) Lisp to be the pinnacle of beauty and minimalism; in this Lisp competes mainly with Forth, another extremely minimalist language. While Forth wins on some fronts, mainly that of performance and being a better fit for typical hardware, Lisp is the more mathematically elegant language, it IS the mathematician's wet dream -- Alan Kay went as far as calling it the "Maxwell’s Equations of software" once he saw it could be described on a single page. I.e., unlike Forth, Lisp is normally not among the fastest languages (for example Emacs is in great part written in Lisp but has to rely on C core for performance critical parts) -- likely due to the overhead of dynamic typing and high abstraction (e.g. arbitrarily precise numbers, garbage collection etc.) -- but it has to be said Lisp can run exceptionally fast on special hardware that is made to run Lisp -- in fact there used to be such machines, called Lisp Machines, however they fell out of popularity. Lisp is infamous for employing an excessive number of brackets -- for this Lisp programmers are usually sensitive about proper code formatting. Lisp is often used as a scripting language for extensions, e.g. in Emacs or GIMP.

Lisps typically employ strict evaluation (i.e. they evaluate all function parameters whether they're needed or not, just like the "mainstream imperative languages" rather than purely functional ones) -- this is probably because purely functional paradigm isn't enforced, imperative constructs are supported (though often discouraged). This takes away a bit of elegance because now there have to exist so called special forms, i.e. constructs that look like functions (they use the same syntax) but are exception from how normal functions behave -- for example while normal functions always have all their parameters evaluated, if branch is a special form that only evaluates a certain branch, depending on condition (consider e.g. (if #t (display "yes") (display "no")); evaluating all arguments would lead to executing both branches). Strictly functional languages like Haskell don't suffer from this, however it seems like Lisp kind of masterfully break this rule to allow a bit more practicality, it just found a nice balance of imposing rules but removing limitations.

Part of the Lisp philosophy/paradigm is that program and data are represented in the same way, i.e. that there is little distinction between code and data: both are just lists or, in Lisp terms, so called S-expressions (symbolic expressions, basically the bracketed expressions in which the first symbol is understood to be the operator/function and the rest are its arguments). This allows for example dynamically constructing a program and executing it at runtime.

Lisps also have various systems of macros that allow to extend the language on-the-go (similarly to Forth), i.e. it is possible to create even new control structures etc.

Lisp is high level but minimalist, a rare beast to witness, an unusual combination to see at least nowadays, but not a bad combination -- high level languages are not necessarily evil, it's just that bloat is evil and high level usually implies bloat. However Lisp manages to stay nice -- the language is defined in very abstract ways, treating values in memory as abstract entities rather than sequences of bits, not bothering the programmer with memory management etc. -- this is subsequently usually optimized under the hood by compilers/interpreters to a more machine friendly code, however the programmer doesn't have to care, it's enough he knows the abstract behavior. Of course there are penalties for this, ignoring what's going on behind the curtains always comes for a price, but Lisp makes this choice willingly and implements it so as to gain the advantages of high level while minimizing the penalties -- for example the language is designed so that it can be implemented in a minimalist way. So basically we could call Lisp a high level language done right.

How do the Lisp dialects differ? Potentially in many different ways: some focus on pragmatism, some on minimalism, some add their own extensions and features, some modify the language itself while some just provide extra libraries, some just put more emphasis on different things (e.g. PicoLisp is more datacentric), some try to support more paradigms such as OOP, some just try to do things differently than others. For example let's examine Common Lisp versus Scheme: Common Lisp is more "bloated", has a big standard library, Scheme is more minimalist, enforces tail recursion to be optimized (and so more encourages functional programming) and mostly doesn't specify order of argument evaluation, Common Lisp evaluates arguments from left to right and supports dynamic scope while Scheme only supports lexical scope, and so on and so forth. From someone coming from the world of C -- where C is simply C -- this world may invoke a cultural shock and information overload: there are different Lisp dialects, each with different standards, each with different implementation. But ultimately there is richness, evolution and a great deal of choice in it. Some of the most notable List dialects include:

Details (Scheme Lisp)

From now on we'll be talking about Scheme Lisp. This is because it's the most minimalist of the big Lisp languages, so it's of the biggest interest to us. Furthermore there are several standards of Scheme, most notable are probably the ones called Revised Report^N on the Algorithmic Language Scheme where N is integer, which is shortened to rNrs. It seems like the most classic one is r5rs from 1998, which is the one we will adopt here.

As said, basically every construct in Lisp has the form (f a1 a2 a3 ...) where f is a function (e.g. +, sin or myFunction) and a1, a2 etc. are arguments, which themselves are either of the same format or represent some atomic value, such as a number (e.g. 123) or string (e.g. "hello"). So what in C we would write as myVariable = myFunction(1,2,strLen("abc")) in Lisp we write like (set! myVariable (myFunction 1 2 (strLen "abc"))). This format applies also to control structures, macros and so on.

How to: there are many Scheme implementations, for example scm, mit-scheme or Guile. We'll choose scm here. To run a Scheme source code from a file just do: scm -f source.scm.

As for data types: Scheme (and Lisp in general) is dynamically typed, i.e. values have data types but variables don't -- it is possible to assign any value to any variable and type checking happens at run time. All variables can be seen as pointers to a general object type (which carries information about its type). Data types in scheme include:

Here is a small cheatsheet:

Example: here is our standardized divisor tree program written in Scheme:

;;; returns the divisor tree string
(define (divisorTreeStr x)
  (define divs (cons 0 1)) ; divisors (a, b)

  (do                      ; find two closest divisors
    ((i 2 (+ i 1)))
    ((or (> i (/ x 2)) (>= (car divs) (cdr divs))))
    (if (zero? (remainder x i))
      (set! divs (cons i (/ x i)))))

  (string-append
    "("
    (if (zero? (car divs))
      ""
      (string-append (divisorTreeStr (car divs)) " "))
    (number->string x)
    (if (zero? (car divs))
      ""
      (string-append " " (divisorTreeStr (cdr divs))))
    ")"))

(define inVal 0)

(define (mainLoop) ; main loop, read values from the user
  (define inVal 0)
  (display "Enter a number: ")
  (set! inVal (read))

  (if (not (and (integer? inVal) (>= inVal 0)))
    #f
    (begin
      (display (string-append (divisorTreeStr inVal) "\n"))
      (mainLoop))))

(mainLoop)

And here is fizzbuzz:

(define (divisible a b)
  (zero? (remainder a b)))

(define (fizzBuzz from to)
  (if (divisible from 3)
    (display "Fizz"))

  (if (divisible from 5)
    (display "Buzz"))

  (if (not (or (divisible from 3) (divisible from 5)))
    (display from))

  (if (< from to)
    (begin
      (display ", ")
      (fizzBuzz (1+ from) to))))

(fizzBuzz 1 100)
(display "\n")

TODO: the basic two-function definition of Lisp


Powered by nothing. All content available under CC0 1.0 (public domain). Send comments and corrections to drummyfish at disroot dot org.