Шаг 105.
LISP и LOGO

    На этом шаге мы рассмотрим связь языков программирования LISP и LOGO.

    Попытаемся ответить на вопрос: почему С.Пейперт создал для обучения детей язык, базирующийся на языке LISP?

    Приведем несколько цитат из монографии [1]: "ЛОГО - это обозначение философии обучения с помощью расширяющейся семьи языков программирования, которые эта философия и породила. К характерным особенностям семьи языков ЛОГО относятся функциональность и рекурсия. Таким образом, в ЛОГО возможно вводить новые команды и функции, которые затем могут использоваться абсолютно так же, как элементарные команды и функции.

    ЛОГО - язык, допускающий интерпретацию. Это значит, что ЛОГО может использоваться в диалоговом режиме. Современные системы программирования на языке ЛОГО представляют собой целостные списковые структуры, т.е. они реализуют списковые языки, куда включены сами списки, списки списков и т.д...

    Примером плодотворного использования списковой структуры является представление процедур ЛОГО как списка списков, что позволяет эти процедуры создавать, модифицировать и включать в другие процедуры ЛОГО. Таким образом, ЛОГО - это не игрушка, а настоящий язык программирования, но только для детей..."[с.17-18].

    "В 1968-1969 гг. впервые группа из 12 средних по успеваемости семиклассников из смешанной школы для молодежи в Лексингтоне (штат Массачусетс) работала с ЛОГО вместо обычной школьной программы по математике на протяжении учебного года. В то время система ЛОГО не имела графического варианта. Учащиеся писали программы, позволявшие переводить с английского на диалекты, которыми пользуются проживающие в США латиноамериканские меньшинства, программы, которые позволяли играть в игры на выбор стратегии, программы по написанию стихов. Работа этих детей была первым подтверждением того, что язык ЛОГО пригоден для для учения на компьютерах детей, для которых эти устройства были внове. Однако мне хотелось убедиться, что этот язык пригоден для обучения и пятиклассников, и третьеклассников, и даже дошкольников. мне было также ясно, что если на языке ЛОГО можно учиться и в этих возрастах, то работу по тематическому программированию необходимо исключить" [с.21].

    "Название ЛОГО было выбрано для нового языка с тем, чтобы подчеркнуть, что этот язык прежде всего символический и только затем количественный" [с.208].

    Мы надеемся, что вывод о сильном сходстве языков программирования LOGO и LISP Вы сможете сделать самостоятельно после того, как просмотрите ряд примеров решения школьных задач по программированию на языках LOGO и LISP. В дальнейшем мы планируем разместить на сайте материал по языку LOGO.

    Замечание. Все примеры на LOGO разработаны для среды LOGOWriter версии 3.1.

    Пример 1. Подсчет количества символов "A" в заданном слове LST.

    a) Программа на языке LISP: 

   (DEFUN COUNT (LAMBDA (WORD)
      (COUNT_LETTER (UNPACK WORD))
   ))
   ; ------------------------------ ;
   (DEFUN COUNT_LETTER (LAMBDA (LST)
      (COND ( (NULL LST) 0)
            ( (EQ (CAR LST) A)
                 (+ 1 (COUNT_LETTER (CDR LST))) )
            (   T  (COUNT_LETTER (CDR LST)) )
      )
   ))
Текст этой функции можно взять здесь.

    b) Программа на языке LOGO (функциональный стиль программирования): 

ЭТО ПОДСЧЕТ :СЛ 
    ЕСЛИИНАЧЕ ПУСТО? :СЛ [ ВЫХОД 0]
    [
      ЕСЛИИНАЧЕ РАВНЫ? ПЕРВЫЙ :СЛ "A
      [  ВЫХОД 1 + (ПОДСЧЕТ КПРВ :СЛ)]
      [  ВЫХОД ПОДСЧЕТ КПРВ :СЛ ]
    ] 
КОНЕЦ
Текст этой функции можно взять здесь.

    Тестовый пример: 

  ПОКАЖИ ПОДСЧЕТ "ADAABC
  3

    Пример 2. Вычеркивание всех букв "A" из заданного слова LST.

    a) Программа на языке LISP: 

   (DEFUN DELETE (LAMBDA (WORD)
      (DELETE_LETTER (UNPACK WORD))
   ))
   ; ------------------------------- ;
   (DEFUN DELETE_LETTER (LAMBDA (LST)
      (COND ( (NULL LST) NIL)
            ( (EQ (CAR LST) A) (DELETE_LETTER (CDR LST)) )
            (  T  (CONS (CAR LST) (DELETE_LETTER (CDR LST))) )
      )
   ))
Текст этой функции можно взять здесь.

    b) Программа на языке LOGO (функциональный стиль программирования): 

ЭТО ВЫЧЕРКИВАНИЕ :СЛ 
    ЕСЛИИНАЧЕ ПУСТО? :СЛ [ ВЫХОД "]
    [
      ЕСЛИИНАЧЕ РАВНЫ? ПЕРВЫЙ :СЛ "A
      [  ВЫХОД ВЫЧЕРКИВАНИЕ КПРВ :СЛ ]
      [  ВЫХОД (СЛОВО ПРВ :СЛ ВЫЧЕРКИВАНИЕ КПРВ :СЛ) ]
    ] 
КОНЕЦ
Текст этой функции можно взять здесь.

    Тестовый пример: 

  ПОКАЖИ ВЫЧЕРКИВАНИЕ "ADAABC
  DBC

    Пример 3. Замена всех букв "A" из слова LST на букву "B".

    a) Программа на языке LISP: 

   (DEFUN REPLACE (LAMBDA (WORD)
      (REPLACE_A_B (UNPACK WORD))
   ))
   ; ---------------------------- ;
   (DEFUN REPLACE_A_B (LAMBDA (LST)
      (COND ( (NULL LST) NIL)
            ( (EQ (CAR LST) A) (CONS B (REPLACE_A_B (CDR LST))) )
            (  T  (CONS (CAR LST) (REPLACE_A_B (CDR LST))) )
      )
   ))
Текст этой функции можно взять здесь.

    b) Программа на языке LOGO (функциональный стиль программирования): 

ЭТО ЗАМЕНА :СЛ
    ЕСЛИИНАЧЕ ПУСТО? :СЛ [ ВЫХОД "]
    [
      ЕСЛИИНАЧЕ РАВНЫ? ПЕРВЫЙ :СЛ "А
       [ВЫХОД (СЛОВО "Б ЗАМЕНА КПРВ :СЛ) ]
       [ВЫХОД (СЛОВО ПРВ :СЛ ЗАМЕНА КПРВ :СЛ) ]
    ]
KOHEЦ
Текст этой функции можно взять здесь.

    Тестовый пример: 

  ПОКАЖИ ЗАМЕНА "ADAABC
  BDBBBC

    Пример 4. Обращение заданного списка LST.

    a) Программа на языке LISP: 

   (DEFUN REVERSE1 (LAMBDA (LST)
   ; Функция обращает список LST на самом первом уровне ;
      (COND ( (NULL LST) NIL )
            (  T  (APPEND (REVERSE1 (CDR LST)) (LIST (CAR LST))) )
      )
   ))
   ; ----------------------- ;
   (DEFUN APPEND (LAMBDA (X Y)
   ; Функция APPEND возвращает список, состоящий из элементов ;
   ;              списка X, добавленных к списку Y            ;
      (COND ( (NULL X) Y )
            ( T (CONS (CAR X) (APPEND (CDR X) Y)) )
      )
   ))
Текст этой функции можно взять здесь.

    b) Программа на языке LOGO (функциональный стиль программирования): 

ЭТО ОБРАЩЕНИЕ :СЛ
    ЕСЛИИНАЧЕ ПУСТО? :СЛ [ ВЫХОД :СЛ]
    [ВЫХОД (СЛОВО ОБРАЩЕНИЕ КПРВ :СЛ ПЕРВЫЙ :СЛ) ]
KOHEЦ
Текст этой функции можно взять здесь.

    Тестовый пример: 

  ПОКАЖИ ОБРАЩЕНИЕ [1 2 3]
  [3 2 1]

    Пример 5. Определить наибольший элемент одноуровневого числового списка LST.

    a) Программа на языке LISP: 

   (DEFUN MAXIM (LAMBDA (LST)
      (COND ( (NULL LST) NIL )
            ( (EQ (LENGTH LST) 1)  (CAR LST) )
            (   T  (MAX2 (CAR LST) (MAXIM (CDR LST))) )
      )
   ))
   ; --------------------- ;
   (DEFUN MAX2 (LAMBDA (X Y)
      (( (> X Y) X )
                 Y )
   ))
Текст этой функции можно взять здесь.

    b) Программа на языке LOGO (функциональный стиль программирования): 

ЭТО MAXIM :LST
    ЕСЛИИНАЧЕ ПУСТО? :LST [ ВЫХОД "]
    [
      ЕСЛИИНАЧЕ РАВНЫ? СКОЛЬКО :LST 1
        [ ВЫХОД ПЕРВЫЙ :LST]
        [ ВЫХОД MAX2 ПЕРВЫЙ :LST MAXIM КПРВ :LST]
    ]
КОНЕЦ
ЭТО MAX2 :X :Y
    ЕСЛИИНАЧЕ :X > :Y [ ВЫХОД :X ]
    [ ВЫХОД :Y ]
КОНЕЦ
Текст этой функции можно взять здесь.

    Тестовый пример: 

  ПОКАЖИ MAX [1 3 2]
  3

    Пример 6. Определить, возрастают ли элементы списка целых чисел.

    a) Программа на языке LISP: 

   (DEFUN ERASEP (LAMBDA (LST)
      (COND ( (NULL LST) T )
            ( (EQ (LENGTH LST) 1) T )
            ( (< (CAR LST) (CADR LST))
                (ERASEP (CDR LST)) )
            (  T  NIL )
      )
   ))
Текст этой функции можно взять здесь.

    b) Программа на языке LOGO (функциональный стиль программирования): 

ЭТО МОН :СП
    ЕСЛИИНАЧЕ ПУСТО? :СП [ ВЫХОД "ИСТИНА ]
      [ ЕСЛИИНАЧЕ РАВНЫ? (СКОЛЬКО :СП) 1 [ ВЫХОД "ИСТИНА ]
         [ ЕСЛИИНАЧЕ (ПЕРВЫЙ :СП) < (ПЕРВЫЙ КПРВ :СП)
             [ ВЫХОД МОН КПРВ :СП ]
             [ ВЫХОД "ЛОЖЬ ]
         ]
      ]
КОНЕЦ
Текст этой функции можно взять здесь.

    Тестовые примеры: 

  ПОКАЖИ МОН [1 3 2]
  ЛОЖЬ
  ПОКАЖИ МОН [1 2 3]
  ИСТИНА

    Пример 7. Сортировка числового списка по возрастанию методом простого обмена.

    b) Программа на языке LOGO (функциональный стиль программирования): 

   ЭTO ПPИMEP:LST
      ЕСЛИ УПОРЯДОЧЕН :LST
         [ВЫДАЙ :LST]
         [ВЫДАЙ ПРИМЕР СОРТИРОВКА :LST ]
   KOHEЦ
   ЭTO СOPTИPOBKA:LST
      ЕСЛИ ПУСТО? :LST
         [ВЫДАЙ [] ]
         [ЕСЛИ РАВНО? СКОЛЬКО :LST 1
             [ВЫДАЙ :LST]
             [ЕСЛИ (ПЕРВЫЙ :LST) > (ПЕРВЫЙ БЕЗПЕРВОГО :LST)
                 [ВЫДАЙ ОБЬЕДИНИ
                          (ПЕРВЫЙ БЕЗПЕРВОГО :LST)
                          (СОРТИРОВКА ОБЬЕДИНИ (ПЕРВЫЙ :LST)
                                       (БЕЗПЕРВОГО БЕЗПЕРВОГО :LST ))]
                 [ВЫДАЙ ОБЬЕДИНИ (ПЕРВЫЙ :LST)
                                 (СОРТИРОВКА БЕЗПЕРВОГО :LST)]
             ]
         ]
   KOHEЦ
   ЭTO УПOPЯДOЧEH:LST
      ЕСЛИ ПУСТО? :LST
         [ВЫДАЙ "ИСТИНА ]
         [ЕСЛИ РАВНО? (СКОЛЬКО :LST) 1
             [ВЫДАЙ "ИСТИНА ]
             [ЕСЛИ (ПЕРВЫЙ :LST) > (ПЕРВЫЙ БЕЗПЕРВОГО :LST)
                 [ВЫДАЙ "ЛОЖЬ ]
                 [ВЫДАЙ УПОРЯДОЧЕН БЕЗПЕРВОГО :LST]
             ]
         ]
   KOHEЦ
Текст этой библиотеки можно взять здесь.

    Пример 8. Сортировка числового списка по возрастанию методом линейной вставки [2].

    b) Программа на языке LOGO (функциональный стиль программирования): 

ЭТО СОРТИРОВКА :L
   ЕСЛИИНАЧЕ ПУСТО? :L
    [ ВЫХОД :L ]
    [ ВЫХОД ВСТАВКА
              ПЕРВЫЙ :L
              СОРТИРОВКА КПРВ :L
    ]
КОНЕЦ
ЭТО ВСТАВКА :A :L
   ЕСЛИИНАЧЕ ПУСТО? :L  
     [ ВЫХОД ВНСП :A :L]
     [ ЕСЛИИНАЧЕ :A < ПЕРВЫЙ :L
         [ ВЫХОД ВНСП :A :L]
         [ ВЫХОД ВНСП ПЕРВЫЙ :L ВСТАВКА :A КПРВ :L  ]
     ]
КОНЕЦ
ЭТО РАССТАВ :NEW :L
   ЕСЛИИНАЧЕ ПУСТО? :NEW
     [ ВЫХОД :L]
     [ ВСТАВКА ПЕРВЫЙ :NEW РАССТАВ КПРВ :NEW :L ]
КОНЕЦ
Текст этой библиотеки можно взять здесь.

   

(1) Пейперт С. Переворот в сознании: дети, компьютеры и плодотворные идеи.: Пер. с англ. / Под ред. А. В. Беляевой, В.В.Леонаса. - М.: Педагогика, 1989. - 224 с.
(2) Лоpин Г. Соpтиpовка и системы соpтиpовки. - М.: Hаука, 1983. - 384 с.

    На следующем шага мы рассмотрим взаимосвязь языков LISP и PROLOG.




Предыдущий шаг Содержание Следующий шаг