Divisió de polinomis amb Emacs Lisp

Per passar l’estona es poden fer moltes coses: llegir un llibre, escoltar música, veure la tele o escriure programes, entre moltes d’altres.

Per circumstàncies diverses, aquests darrers temps he pogut dedicar moltes estones a escriure programes i, un cop escrits, he pensat que els puc aprofitar per fer-ne un post al bloc de tecnologia.

En aquesta ocasió, es tracta d’un programa que fa la divisió entre dos polinomis. Al programa se li entrega una llista amb els coeficients numèrics del numerador (amb zero per als coeficients nuls) i una llista amb els del denominador. Cal que el grau del polinomi del numerador sigui major o igual que el del denominador.

Amb aquestes condicions, només cal aplicar el conegut algorisme de divisió de polinomis. Un exemple il·lustra el procediment:

Donats e numerador i denominador:

 N: x^3 + -12*x^2 + -42
 D: x + -3

La resposta és:

 Q: x^2 + -9*x + -27
 R: -123

Vet aquí el procediment. Cada parell és (coeficient, grau):

    (1,3)  (-12,2)  (0,1)  (-42,0) | (1,1) (-3,0) 
   -(1,3)   -(-3,2)                  (1,2)(-9,1) (-27,0)
    -------------
       0    (-9,2)   (0,1)  
           -(-9,2) -(27,1)
    ----------------------
                0  (-27,1) (-42,0)
                  -(-27,1) -(81,0) 
    ------------------------------
                        0  (-123,0)

Un exemple numèric diferent (aquí només indico el coeficients):

 6   5   4  3   2   1     | 1  2 3
-6 -12 -18                  6 -7 0 24
----------
    -7 -14  3   2   1
     7  14 21
---------------------
           24   2   1
            0   0   0
---------------------
           24   2   1
          -24 -48 -72
---------------------
              -46 -71

Es tracta d’implementar l’algorisme anterior. A manca d’alguna altre cosa, aquest cop he fet servir Emacs Lisp, el llenguatge d’extensió que porta incorporat l’Emacs. Al tractar-se d’un algorisme essencialment recursiu resulta senzill d’implementar amb un dialecte de Lisp com l’Emacs Lisp.

Bé, doncs és això:

(progn
  (setq coefs (list))
  (setq rest (list))

  (defun show-poly (poly)
    (if (>= (length poly) 1)
	(progn
	  (setq exponent (1- (length poly)))
	  (insert (format "(%s*(x^%d))" (car poly) exponent))
	  (if (> exponent 0)
	      (progn
		(insert "+")
		(show-poly (cdr poly)))))))

  (defun get-quotient (num den)
    (setq lnum (length num))
    (setq lden (length den))
    (setq quotient (list))

    (setq high-coef-num (car num))
    (setq high-coef-denom (car den))
    (setq coef (/ high-coef-num high-coef-denom))

    (dotimes (i lden)
      (setq quotient (append quotient (list (- (nth i num) 
                                      (* coef (nth i den)))))))
    (dotimes (i (- lnum lden))
      (setq quotient (append quotient (list (nth (+ lden i) num)))))

    (newline)
    (insert "Last rest: ")
    (show-poly quotient)
    (newline)
    (cons coef quotient))

  (defun divide (numerator denominator)
    (setq lnum (length numerator))
    (setq lden (length denominator))
    
    (if (>= lnum lden)   
	(progn 
          (setq pair (get-quotient numerator denominator))
          (setq coefs (append coefs (list (car pair))))
          (divide (cdr (cdr pair)) denominator))))

  ;; main
  (newline)
  (newline)
  (insert "Polynomial division")
  (newline)
  (setq num '(1 2 1))
  (setq den '(1 1))
  (newline)
  (insert "divide")
  (newline)
  (show-poly num)
  (newline)
  (insert "by")
  (newline)
  (show-poly den)
  (newline)
  (divide num den)
  (newline)
  (insert "Quotient: ")
  (show-poly coefs)
  (newline))

Per a executar el programa copieu el codi anterior a un buffer de l’Emacs i executeu-lo amb C-x C-e (la seqüència control-x control-m).

El programa calcularà la divisió del polinomi x² + 2x + 1 per x + 1, resultat x + 1 i rest 0. Per a provar amb altres polinomis n’hi ha prou de canviar el parell de línies

  (setq num '(1 2 1))
  (setq den '(1 1))

El codi també està al meu GitHub

I, per acabar, encara que aquests dies han donat per algun altre joc amb Python que segurament també publicaré, espero que els propers posts siguin una mica més sucosos (en cartera: programació funcional amb javascript i underscore.js. A veure quan cau!).

60 anys de Lisp. Old rockers never die.

El programador no neix. Es fa.

La formació d’un bon programador passa per diverses etapes. En la etapa inicial hom aprèn un llenguatge. Normalment un llenguatge d’iniciació. Un llenguatge d’iniciació serveix, més que res, per comprendre conceptes de programació.  I no és tan important el seu rendiment o la seva aplicació en problemes reals.

Avui, per exemple, es fa servir, a nivell de ESO i secundària, el llenguatge Scratch (un fantàstic i versàtil entorn d’aprenentatge) com a llenguatge d’iniciació.

A nivells més avançats, hi ha més varietat. Sobretot als EUA es fa servir molt -com a llenguatge d’iniciació per a universitaris, repeteixo- el Lisp, en alguna de les seves encarnacions: Scheme, Racket, CLisp

Lisp és proper al llenguatge matemàtic, té una sintaxi mínima i no imposa gaires restriccions en quant a paradigmes de programació, tot plegat el fa molt versàtil per a presentar conceptes informàtics. Alguns dels millors i més influents manuals de programació fan servir el Lisp. Cal llegir al menys una vegada en la vida el llibre porpra: Structure and Interpretation of Computer Programs.

Potser sorprenentment, el Lisp es un llenguatge que es troba amb  facilitat a entorns productius Unix. Guile (Scheme), un altre dialecte de Lisp, és el llenguatge d’extensió oficial de les aplicacions GNU (un llenguatge d’extensió és, per entendre’ns, un llenguatge de macros). També es pot trobar Lisp sent part indestriable i indissoluble de l’Emacs, l’editor de texts més versàtil mai creat. Emacs, en ell mateix, està en molt bona part programat amb Emacs Lisp. La forma d’estendre Emacs és, evidentment, amb l’Emacs Lisp. La presència universal d’Emacs posa el Lisp allà on hi hagi un Emacs instal·lat.

Lisp (inventat per John McCarthy entre 1956 i 1958) és el segon llenguatge informàtic més antic encara en servei (el més antic, encara en servei, és Fortran. La primera especificació de Fortran va ser escrita per IBM a  1954). Aquesta timeline de la wiki us pot ajudar a situar-lo en el temps.

Estem parlant, doncs,  d’un llenguatge informàtic amb 60 anys d’història. Es diu de pressa. En termes informàtics tant de temps equival al pas  de vàries eres geològiques.

Però el millor del cas és que l’evolució del Lisp continua: és relativament senzill programar un interpret de Lisp i això fa que es puguin trobar dialectes per a multitud de plataformes. Concretament, per a la JVM en aquests moment hi ha una versió de Lisp que destaca sobre les altres: Clojure.

Clojure és un dialecte de Lisp que funciona sobre la JVM. Tot i que no imposa el paradigma, presenta una orientació envers la Programació Funcional (FP) [i Clojure FP ]. Val a dir que és possible fer FP, en general, amb dialectes comuns de Lisp.

Com a punt molt fort, es relaciona de forma senzilla amb la JVM, de forma que té accés a la infinitat de llibreries i frameworks de Java i, a l’hora, és senzill des de Java  invocar Clojure, o fer servir des de Java les classes desenvolupades amb Clojure.

Més enllà de la curiositat de portar Lisp a la JVM, sembla que Clojure està fent-se, poc a poc, això sí, amb una part de mercat en l’anàlisi de dades (on a hores d’ara dominen R i Python amb Pandas, sense comptar amb el clàssic SQL, o l’omnipresent Java).

Però, tornant al principi, en la formació d’un programador el primer pas acostuma a ser algun llenguatge d’iniciació que ràpidament es complementa amb l’aprenentatge de llenguatges més utilitzats professionalment i amb llenguatges de paradigmes diferents.

La programació amb diferents paradigmes dona una visió completa al programador. Li obre la ment. L’habilita per enfocar els problemes des de punts de vista diferents. Per això, un bon programador ho és de forma independent als llenguatges que conegui , tot i que, evidentment, el més probable i el més recomanable és que tingui alguns llenguatges preferents  que domini. I també que aquestes preferències vagin canviant amb el pas del temps. El bon programador és poliglot, i sempre té un ull posat en els nous llenguatges i paradigmes que van apareixent.

Dins la caixa d’eines del programador hom pot trobar, doncs,  diferents llenguatges per a diferents propòsits. Alguns llenguatges seran molt demandats professionalment, i altres, no tant, o gens ni mica. Però en l’arsenal mental del programador, aquesta varietat expressiva és riquesa i versatilitat.

Per acabar, l’objectiu del post d’avui era redescobrir Lisp i perquè crec que pot tenir interès dedicar un temps a aquest llenguatge. Com usuari que sóc d’Emacs (Emacs Lisp) i d’eines GNU (Guile i Scheme), Lisp té un caràcter pràctic. Com programador Java i que ha treballat més o menys amb anàlisi de dades, Clojure també em crida l’atenció.

La paraula clau és poliglotisme. Us deixo un enllaç: http://hyperpolyglot.org/. Es tracta d’un lloc web que ofereix taules de comparació entre llenguatges més o menys afins. En concret, us proposo fer un cop d’ull a aquestes taules:

Llenguatges d’Scripting : Node.js, PHP, Python i Ruby. [full 1]i [full 2].

Llenguatges d’anàlisi numèric i estadístic: MATLAB (i Octave), R, NumPy i Julia. [full 1] i [full 2].

Comparació entre dialectes de Lisp: Common Lisp, Racket (Scheme), Clojure, Emacs Lisp .