]]> ]]>
Править | Обсудить | История

Lisp

Русское название:
Лисп
Дата создания:
1958
Повлиял на:
Парадигма:
Типизация:
Принятые расширения файлов:
.lisp, .cl
Диалекты:
Реализации и версии (свернуть все | развернуть все):
Язык программирования

Лисп (LISP, от англ. LISt Processing — «обработка списков») — семейство языков программирования, основанных на представлении программы системой линейных списков символов, которые притом являются основной структурой данных языка. Лисп считается вторым после Fortran старейшим высокоуровневым языком программирования.

Язык Лисп был предложен Дж. Маккарти в работе в 1960 году и ориентирован на разработку программ для решения задач не численного характера. Английское название этого языка – LISP является аббревиатурой выражения LISt Processing (обработка списков) и хорошо подчеркивает основную область его применения. Понятие “список” оказалось очень емким. В виде списков удобно представлять алгебраические выражения, графы, элементы конечных групп, множества, правила вывода и многие другие сложные объекты. Списки являются наиболее гибкой формой представления информации в памяти компьютеров. Неудивительно поэтому, что удобный язык, специально предназначенный для обработки списков, быстро завоевал популярность.

После появления Лиспа различными авторами был предложен целый ряд других алгоритмических языков ориентированных на решение задач в области искусственного интеллекта. Однако это не помешало Лиспу остаться наиболее популярным языком для решения таких задач. На протяжении почти сорокалетней истории его существования появился ряд диалектов этого языка: Common LISP, Mac LISP, Inter LISP, Standard LISP и др. Различия между ними не носят принципиального характера и в основном сводятся к несколько отличающемуся набору встроенных функций и некоторой разнице в форме записи программ. Поэтому программист, научившийся работать на одном из них, без труда сможет освоить и любой другой.

Большим достоинством Лиспа является его функциональная направленность, т. е. программирование ведется с помощью функций. Причем функция понимается как правило, сопоставляющее элементам некоторого класса соответствующие элементы другого класса. Сам процесс сопоставления не оказывает никакого влияния на работу программы, важен только его результат – значение функции. Это позволяет относительно легко писать и отлаживать большие программные комплексы. Ясность программ, четкое разграничение их функций, отсутствие каверзных побочных эффектов при их выполнении является обязательными требованиями к программированию таких логически сложных задач, каковыми являются задачи искусственного интеллекта. Дисциплина в программировании становится особенно важной, когда над программой работает не один человек, а целая группа программистов.

Язык программирования Лисп предназначен в первую очередь для обработки символьной информации. Поэтому естественно, что в мире Лиспа числа играют далеко не главную роль. Основные типы данных в Лиспе называются “атом” и “точечная пара”.

Элементы синтаксиса:

Комментарий до конца строки ;
Комментарии, которые могут быть вложенными #| ... |#
Регистрозависимость нет
Регулярное выражение идентификатора переменной любая комбинация символов, не содержащая пробелов и не являющаяся числом
Регулярное выражение идентификатора функции set, setf, setq
Объявление переменной let
Равенство eq, eql
Тождественное равенство equal, equalp
Сравнение < > <= >=
Определение функции (defun f (para1 para2) ...)
Вызов функции (f a b ...)
Вызов функции без параметров (f)
Если - то (if condition ...)
Если - то - иначе (if condition trueBlock falseBlock)
Бесконечный цикл (loop do ...)
Цикл с предусловием (loop while condition do ...)
Цикл с постусловием (loop do ... until condition)
Цикл for - next для диапазона целых чисел с инкрементом на 1 (loop for i from 1 to 10 do ...)
Цикл for - next для диапазона целых чисел с декрементом на 1 (loop for i from 1 to 10 by -1 do ...)

Ссылки:

IDE/Редакторы:

Примеры:

Hello, World!:

Пример для версий Corman Common Lisp 3.0, SBCL 1.0.1, SBCL 1.0.29, clisp 2.47, gcl 2.6.6

Результат выполнения этого кода в интерактивном режиме имеет следующий вид:

Hello, World!
NIL

Первая строка содержит стандартный поток вывода, вторая — значение, возвращаемое кодом (в данном случае — его отсутствие). 

(format t "Hello, World!~%")

Факториал:

Пример для версий Corman Common Lisp 3.0, SBCL 1.0.1, SBCL 1.0.29, clisp 2.47, gcl 2.6.6

Этот пример использует рекурсивное определение факториала, естественное для Lisp. Демонстрирует следующие особенности языка:

  • математические операторы: (- n 1) — это префиксная запись, эквивалентная инфиксной записи n-1;
  • операторы сравнения: (= n 0) возвращает T, если n равно нулю, и nil (используется как false) в противном случае;
  • условный оператор if: выражения в Lisp определяются по скобкам и могут записыватся в несколько строк;
  • определение функции с использованием defun;
  • макрос Common Lisp loop;
  • спецификации формата вывода в format: ~D соответствует целому числу, а ~% — концу строки. 
(defun factorial (n)
    (if (= n 0)
        1
        (* n (factorial (- n 1))) ) )

(loop for i from 0 to 16
    do (format t "~D! = ~D~%" i (factorial i)) )

Числа Фибоначчи:

Пример для версий Corman Common Lisp 3.0, SBCL 1.0.1, SBCL 1.0.29, clisp 2.47, gcl 2.6.6

Используется рекурсивное определение чисел Фибоначчи. Часть finally макроса loop выполняется после конца цикла. 

(defun fibonacci (n)
    (if (< n 3)
        1
        (+ (fibonacci (- n 1)) (fibonacci (- n 2))) ))

(loop for i from 1 to 16
    do (format t "~D, " (fibonacci i))
    finally (format t "...~%"))

Числа Фибоначчи:

Пример для версий Corman Common Lisp 3.0, clisp 2.47, gcl 2.6.6

Этот пример использует итеративное определение чисел Фибоначчи без запоминания, выраженное через рекурсивный вызов функции fib-iter. 

(defun fibonacci (n)
    (defun fib-iter (a b count)
        (if (zerop count)
            b
            (fib-iter (+ a b) a (- count 1))
        )
    )
    (fib-iter 1 0 n)
)

(loop for i from 1 to 16
    do (format t "~D, " (fibonacci i))
    finally (format t "...~%")
)

Факториал:

Пример для версий Corman Common Lisp 3.0, SBCL 1.0.1, SBCL 1.0.29, clisp 2.47, gcl 2.6.6

Внутренний цикл с операцией collect создает список чисел от 1 до n, после чего к нему применяется операция *. 

(loop for n from 0 to 16
   do (format t "~D! = ~D~%" n 
        (apply '* (loop for i from 1 to n 
                        collect i)) ) )

Квадратное уравнение:

Пример для версий Corman Common Lisp 3.0, SBCL 1.0.1, SBCL 1.0.29, clisp 2.47, gcl 2.6.6

Common Lisp позволяет работать с комплексными числами и выводить их на печать в формате #C(real imag). Функция write-to-string преобразует число в строку. 

(defun quadratic-roots-2 (A B C)
  (cond ((= A 0) (string "Not a quadratic equation."))
    (t
    (let ((D (- (* B B) (* 4 A C))))
      (cond ((= D 0) (concatenate 'string "x = " (write-to-string (/ (+ (- B) (sqrt D)) (* 2 A)))))
        (t
        (concatenate 'string (concatenate 'string "x1 = " (write-to-string (/ (+ (- B) (sqrt D)) (* 2 A))))
                             (concatenate 'string "~%x2 = " (write-to-string (/ (- (- B) (sqrt D)) (* 2 A)))))))))))

(let ((A (read))
     (B (read))
     (C (read)))
(format t (quadratic-roots-2 A B C)))

CamelCase:

Пример для версий Corman Common Lisp 3.0, SBCL 1.0.1, SBCL 1.0.29, clisp 2.47 
(defun camel-case (s)
  (remove #\Space 
          (string-capitalize
           (substitute #\Space nil s :key #'alpha-char-p))))

(princ (camel-case (read-line)))

Hello, World!:

Пример для версий JScheme 7.2, MIT/GNU Scheme 7.7.9, guile 1.8.5

Вывод строки на печать — побочный эффект выполнения этой команды. В зависимости от выбранной реализации, команда вернет либо выведенный текст, либо Unspecified return value. 

(write "Hello, World!")

Hello, World!:

Пример для версий Clojure 1.0.0, Clojure 1.1.0 
(printf "Hello, World!")

Факториал:

Пример для версий Clojure 1.0.0, Clojure 1.1.0

Используется рекурсивное определение факториала. Функция range с одним аргументом генерирует список чисел от 0 включительно до этого числа исключительно. str — функция конкатенации строк. Функция dec эквивалентна (- x 1). doseq — цикл for в Clojure. 

(defn factorial [x]
  (if (< x 2)
    1
    (* x (factorial (dec x)))))

(doseq [i (range 17)]
  (println (str (str i "! = ") (factorial i))))

Факториал:

Пример для версий Clojure 1.0.0, Clojure 1.1.0

Для вычисления факториала числа создается интервал чисел от 2 до этого числа, и вычисляется произведение этих чисел (функция apply). 

(doseq [i (range 17)]
  (println (str (str i "! = ") (apply * (range 2 (inc i))))))

Числа Фибоначчи:

Пример для версий Clojure 1.0.0, Clojure 1.1.0

Используется рекурсивное вычисление чисел Фибоначчи. 

(defn fibonacci [x]
  (if (< x 2)
    x
    (+ (fibonacci (- x 1)) (fibonacci (- x 2)) )))

(doseq [i (range 1 17)]
  (print (str (fibonacci i) ", ")))
(println "...")

Факториал:

Пример для версий JScheme 7.2, MIT/GNU Scheme 7.7.9, guile 1.8.5

Используется рекурсивное определение факториала. Отметим, что GNU Guile и MIT/GNU Scheme выводит правильный результат, а в JScheme возникает переполнение, и факториалы с 13! вычисляются неправильно. 

(define (factorial x)
  (if (< x 2)
    1
    (* x (factorial (- x 1)))))

(do ((i 0 (+ i 1)))
  ((> i 16))
    (display (string-append (number->string i) "! = "))
    (display (number->string (factorial i)))
    (newline))

Числа Фибоначчи:

Пример для версий JScheme 7.2, MIT/GNU Scheme 7.7.9, guile 1.8.5

Используется рекурсивное определение чисел Фибоначчи. 

(define (fibonacci x)
  (if (< x 2)
    x
    (+ (fibonacci (- x 1)) (fibonacci (- x 2)))))

(do ((i 1 (+ i 1)))
  ((> i 16))
    (display (string-append (number->string (fibonacci i)) ", ")))
(display "...")
(newline)

Квадратное уравнение:

Пример для версий Clojure 1.0.0, Clojure 1.1.0 
(defn solve-quadratic [a b c]
  (if (= a 0)
    "Not a quadratic equation."
    (let [D (- (* b b) (* 4 a c))
          k1 (- 0 b)
          k2 (* 2 a)]
         (if (= D 0)
            (str "x = " (/ k1 k2))
            (if (> D 0)
                (let [k3 (Math/sqrt D)]
                     (str (str "x1 = " (/ (+ k1 k3) k2) (str "\nx2 = " (/ (- k1 k3) k2)))))
                (let [k3 (/ (Math/sqrt (- 0 D)) k2)]
                     (str (str (str (str "x1 = (" (/ k1 k2)) (str ", " k3)) ")\nx2 = (") (str (str (/ k1 k2) ", ") (str (- 0 k3) ")") ))
                ))))))

(import '(java.util Scanner))
(def scan (Scanner. *in*))
(def a (.nextInt scan))
(def b (.nextInt scan))
(def c (.nextInt scan))
(println (solve-quadratic a b c))

Квадратное уравнение:

Пример для версий guile 1.8.5

Конструкция begin используется для того, чтобы выполнить несколько команд подряд. 

(define A (read))
(define B (read))
(define C (read))
(define D (- (* B B) (* 4 A C)))
(if (= A 0)
  (display "Not a quadratic equation.")
  (begin
   (define k1 (/ B -2 A))
   (define k2 (/ (sqrt (abs D)) 2 A))
   (if (= D 0)
    (begin (display "x = ") (display k1))
    (if (> D 0)
      (begin (display "x1 = ") (display (+ k1 k2)) (newline) (display "x2 = ") (display (- k1 k2)))
      (begin (display "x1 = (") (display k1) (display ", ") (display k2) (display ")") (newline)
             (display "x2 = (") (display k1) (display ", ") (display (- k2)) (display ")"))))))

CamelCase:

Пример для версий guile 1.8.5

В этом примере показана работа с регулярными выражениями из модуля regex. Первые две строки подключают нужные модули. Третья — читает строку из входных данных командой read-line (модуль rdelim) — в отличие от read, она читает все символы до конца строки, а не до первого пробела — и переводит ее в нижний регистр.

Четвертая команда находит все последовательности букв нижнего регистра в строке. Для каждой такой последовательности она заменяет ее на результат применения к ней некоторой функции (привязанной с помощью lambda). В данном случае это функция string-titlecase, переводящая первый символ строки в верхний регистр.

Наконец, пятая команда удаляет из строки все символы, не являющиеся буквами. 

(use-modules (ice-9 regex))
(use-modules (ice-9 rdelim))
(define text (string-downcase (read-line)))
(define text (regexp-substitute/global #f "[a-z]+"  text 'pre (lambda (m) (string-titlecase (match:substring m))) 'post))
(define text (regexp-substitute/global #f "[^a-zA-Z]+"  text 'pre 'post))
(display text)

Комментарии

]]>

blog comments powered by Disqus

]]>

Работа программистам