Программа - это маленькое дерево

Введение

Пример написания простой программы на Лиспе, ищущей самое маленькое слово, с замечаниями по ходу процесса. Программа пишется как лабораторная работа.

Выполнять будем в среде LispBox, я буду приводить текст сессии вместо скриншота, для простоты.

UPD 2016-12-03: эта задача гораздо проще и красивее решается циклом loop, как показано здесь: джентельменский минимум к экзамену по Лиспу

Программа

Наша цель - разбить строку на слова, затем как-то пройти через все слова и выбрать из них наименьшее. Так как Лисп - язык редкий, гуглить мы не будем, потому что всё равно не поймём найденного решения и не сможем его сдать :-).

Разбить строку s на слова можно либо с помощью рекурсивной функции, либо циклом. Я попробую вариант с циклом loop, поскольку (loop c across s ...) сразу мне даёт переменную c, пробегающую все буковки по одной.

Поехали:

CL-USER> (setf s "sdf sdfasf sadfsdfaserf sf")

"sdf sdfasf sadfsdfaserf sf"
CL-USER> s
"sdf sdfasf sadfsdfaserf sf"
CL-USER> (loop for c across s collect c)
;Compiler warnings :
;   In an anonymous lambda form: Undeclared free variable S
(#\s #\d #\f #\  #\s #\d #\f #\a #\s #\f #\  #\s #\a #\d #\f #\s #\d #\f #\a #\s #\e #\r #\f #\  #\s #\f)

Буквы в виде списка мы получили. 

Теперь берём учебник (а ещё лучше - нормальный справочник) по языку, открываем главу по циклу loop, и начинаем смотреть, какие возможности в нём есть. Я ищу common Lisp reference manual и цапаю учебник "Common Lisp the Language, 2nd Edition".

Читаю главу 26 сверху вниз и пробую кирпичики, которые мне могут пригодиться.

Первым делом пробую условный оператор на поиск разделителя:

CL-USER> (loop for c across s if (eq c #\ ) collect c)
;Compiler warnings :
;   In an anonymous lambda form: Undeclared free variable S
(#\  #\  #\ )
Работает: я выхватил свои три разделителя в список. 

Теперь пробую добавить свой оператор do для обработки разделителей:

CL-USER> (loop for c across s if (eq c #\ ) do (print c))
;Compiler warnings :
;   In an anonymous lambda form: Undeclared free variable S
#\ 
#\ 
#\ 
NIL

Очень хочется заполучить позицию разделителя, поэтому я добавляю ещё одну переменную цикла, растущую с нуля.
 Переменных цикла можно добавлять много, как показывает простой пример, взятый отсюда:

;;; Collect every name and the kids in one list by using 
;;; COLLECT and APPEND. 
(loop for name in '(fred sue alice joe june) 
      for kids in '((bob ken) () () (kris sunshine) ()) 
      collect name 
      append kids) 
   => (FRED BOB KEN SUE ALICE JOE KRIS SUNSHINE JUNE)

У меня получается простая конструкция:

CL-USER> (loop
            for c across s  
            for pos from 0
            if (eq c #\ ) do (print (list c pos)))
;Compiler warnings :
;   In an anonymous lambda form: Undeclared free variable S
(#\  3)
(#\  10)
(#\  23)
NIL

Здорово: получается и сканировать строку, и одновременно сохранять позицию разделителя. 

Идём дальше - заводим переменную для длины слова, пусть она тоже растёт автоматически, но на разделителе сбрасывается в ноль:

CL-USER> s
"sdf sdfasf sadfsdfaserf sf"
CL-USER> (loop
        for c across s
        for pos from 0
        for len from 0
        if (eq c #\ ) do
          (print (list c pos len))
          (setf len 0))
;Compiler warnings :
;   In an anonymous lambda form: Undeclared free variable S
(#\  3 3)
(#\  10 7)
(#\  23 13)
NIL

Видно, что в длине слова неявно учитывается пробел (разделитель), который идёт в копилку длины последующего слова. Поправляем это недоразумение:

CL-USER> (loop
        for c across s
        for pos from 0
        for len from 0
        if (eq c #\ ) do
          (print (list c pos len))
          (setf len -1))
;Compiler warnings :
;   In an anonymous lambda form: Undeclared free variable S
(#\  3 3)
(#\  10 6)
(#\  23 12)
NIL

Слова теперь правильной длины, хотя последнее из них не обсчитывается совсем - в конце строки нет разделителя. Исправляем этот недочёт, просто добавив в конец ещё один пробел:

CL-USER> (loop
        for c across (concatenate 'string s " ")
        for pos from 0
        for len from 0
        if (eq c #\ ) do
          (print (list c pos len))
          (setf len -1))
;Compiler warnings :
;   In an anonymous lambda form: Undeclared free variable S
(#\  3 3)
(#\  10 6)
(#\  23 12)
(#\  26 2)
NIL

Этот приём - подкручивание граничных ячеек для того, чтобы алгоритм для внутренних элементов без переделок учитывал граничные условия, называется сквозным счётом. Можно было бы последнее слово обрабатывать отдельно в блоке finally, но тогда был бы дублирующийся код, что не всем приятно.

Теперь проверяем, меньше ли длина нашего нового слова некоего  текущего минимума. Если так, запоминаем новый минимум:
CL-USER> (loop with min = (length s)
           for c across (concatenate 'string s " ")
           for pos from 0
           for len from 0
           if (eq c #\ ) do
              (if (< len min)
                  (progn (setf min len)
                         (print "New min is set")
                         (print min)))
              (print (list c pos len))
              (setf len -1))
;Compiler warnings :
;   In an anonymous lambda form: Undeclared free variable S (2 references)
"New min is set"
3
(#\  3 3)
(#\  10 6)
(#\  23 12)
"New min is set"
2
(#\  26 2)
NIL

Половина нового кода - радостные вопли и печать неимоверных достижений, в финальной версии всё уйдёт, конечно. Главное, что пока всё шевелится, как надо (тьфу-тьфу-тьфу).

Идём дальше - запоминаем длину самого маленького слова, и выводим её как результат цикла вместе с позицией:
CL-USER> (loop
            with min = (length s)
            with min_right_pos = (length s)
            for c across (concatenate 'string s " ")
            for pos from 0
            for len from 0
            if (eq c #\ ) do
              (if (< len min)
                  (progn (setf min len)
                         (setf min_right_pos pos)
                         (print "New min is set")
                         (print min)))
              (print (list c pos len))
              (setf len -1)
            finally (return (list min min_right_pos)))
;Compiler warnings :
;   In an anonymous lambda form: Undeclared free variable S (3 references)
"New min is set"
3
(#\  3 3)
(#\  10 6)
(#\  23 12)
"New min is set"
2
(#\  26 2)
(2 26)

Супер! Теперь нам осталось только вырезать подстроку по известным длине и положению правой границы:
CL-USER> (loop
            with min = (length s)
            with min_right_pos = (length s)
            for c across (concatenate 'string s " ")
            for pos from 0
            for len from 0
            if (eq c #\ ) do
              (if (< len min)
                  (progn (setf min len)
                  (setf min_right_pos pos)
                  (print "New min is set")
                  (print min)))
              (print (list c pos len))
              (setf len -1)
            finally (return (subseq s (- min_right_pos min) min_right_pos)))
;Compiler warnings :
;   In an anonymous lambda form: Undeclared free variable S (4 references)
"New min is set"
3
(#\  3 3)
(#\  10 6)
(#\  23 12)
"New min is set"
2
(#\  26 2)
"sf"

Готово.

Осталось или стереть все диагностические принты, или перенести их содержимое в комментарии. Лучше всего стереть принты и переименовать мутные переменные:
CL-USER> (loop
            with min_word_len = (length s)
            with min_right_pos = (length s)
            for c across (concatenate 'string s " ")
            for pos from 0
            for len from 0
            if (eq c #\ ) do
              (if (< len min_word_len)
                  (progn (setf min_word_len len)
                         (setf min_right_pos pos)))
              (setf len -1)
            finally (return (subseq s (- min_right_pos min_word_len) min_right_pos)))
;Compiler warnings :
;   In an anonymous lambda form: Undeclared free variable S (4 references)
"sf"

Получилось короче, но радости не сильно много ;-).

Варим кофе и смотрим в окно до тех пор, пока оно не забулькает, и только тогда возвращаемся к коду. Пишем чуть короче:
CL-USER> (loop
            with l = 0 and r = (length s) and min = (length s)
            for c across (concatenate 'string s " ")
            for pos from 0
            for len from 0
            if (eq c #\ ) do
              (if (< len min)
                  (progn (setf r pos)
                         (setf l (- r len))
                         (setf min len)))
              (setf len -1)
            finally (return (subseq s l r)))

;Compiler warnings :
;   In an anonymous lambda form: Undeclared free variable S (4 references)
"sf"
Мы перешли от пары переменных (правая-граница длина) к паре (левая-граница правая-граница). Какой вариант лучше, будет видно на следующее утро :-)

Заключение и анализ

Замечания к коду и процессу написания:

1. Я делал цикл по строке, потому что такой вариант использует встроенные в Лисп функции работы с начинкой строки. Такой вариант, как правило, быстрее, чем ручное выделение буковок и их анализ. Для скриптовых языков разница в скорости может достигать сотен и тысяч раз (по крайней мере на моём опыте с Питоном, Octave и MatLab-ом).
2. Программа для меня - маленькое дерево.
   Посмотрите на итоговый ответ o_O. Нельзя сразу родить такой скрипт, если ты только учишься, или если программа больше, чем вместимость твоей головы. Гораздо проще писать её слой за слоем.
3. Программируйте сами, потому что готовые примеры не учат декомпозиции задачи на доступные шаги (слои), на каждом из которых вы завершаете ступеньку, на которую уже можно опереться.
4. Работа с учебником в сотни раз продуктивнее гугла, если вы не можете ещё поставить вопрос "как сделать" в терминах языка (как сделать конкатенацию строк в лиспе, как вырезать подстроку, ...). Если ýчитесь - читайте книги.

Удачи всем!