Teoria de llenguatges de programació

La teoria de llenguatges de programació és una branca de la informàtica que s'encarrega del disseny, implementació, anàlisi, caracterització i classificació de llenguatges de programació i els seus característiques. És un camp multidisciplinari, depenent tant de (i en alguns casos afectant) matemàtiques, enginyeria del programari, lingüística, i fins i tot ciències cognitives. És una branca ben reconeguda de la informàtica, ia data de 2006, una àrea activa d'investigació, amb resultats publicats en un gran nombre de revistes dedicades a la PLT, així com en general en publicacions d'informàtica i ingeniería. La majoria dels programes dels estudiants universitaris d'informàtica requereixen treballar en aquest tema.

Un símbol no oficial de la teoria de llenguatges de programació és la lletra grega lambda en minúscules. Aquest ús deriva de l'càlcul lambda, un model computacional àmpliament usat per investigadors de llenguatges de programació. Molts textos i articles sobre programació i llenguatges de programació utilitzen lambda d'una o altra manera. Il·lustra la portada del text clàssic Estructura i Interpretació de Programes d'Ordinador , i el títol de molts dels anomenats Articles Lambda, escrits per Gerald Jay Sussman i Guy Steele, creadors del llenguatge de programació Scheme. Un lloc molt conegut sobre teoria de llenguatges de programació es diu Lambda the Ultimate ( Lambda el primordial ), en honor de la feina de Sussman i Steele.

Història

Quadre cronològic i taxonòmic dels llenguatges de programació.

Des d'alguns punts de vista, la història de la teoria de llenguatges de programació precedeix fins i tot el desenvolupament dels mateixos llenguatges de programació. El càlcul lambda, desenvolupat per Alonzo Church, Max HL. Solis Vila-real i Stephen Cole Kleene en la dècada de 1930, és considerat ser un dels primers llenguatges de programació del món, fins i tot malgrat que tenia intenció de modelar la computació més de ser un mitjà perquè els programadors descriguin algorismes per a un sistema informàtic. Molts llenguatges de programació funcional s'han caracteritzat per proveir una "fina aparença" al càlcul lambda [1], i molts es descriuen en els seus termes.

El primer llenguatge de programació (com a tal) que es va proposar va ser Plankalkül, que va ser dissenyat per Konrad Zuse en els anys 40, però no va ser conegut públicament fins a 1972 (i no implementat fins al 2000, cinc anys després de la mort de Zuse). El primer llenguatge de programació àmpliament conegut i reeixit va ser Fortran, desenvolupat entre 1954 i 1957 per un equip de d'investigadors d'IBM liderats per John Backus. L'èxit de FORTRAN va conduir a la creació d'un comitè de científics per desenvolupar un llenguatge de programació "universal", el resultat del seu esforç va ser ALGOL 58. Separadament, John McCarthy del MIT va desenvolupar el llenguatge de programació Lisp (basat en el càlcul Lambda), el primer llenguatge amb orígens acadèmics a aconseguir l'èxit. Amb el triomf d'aquests esforços inicials, els llenguatges de programació es van convertir en un tema candent en la investigació en la dècada de 1960 i en endavant.

Alguns altres esdeveniments claus en la història de la teoria de llenguatges de programació des de llavors:

A la dècada de 1950, Noam Chomsky va desenvolupar la Jerarquia de Chomsky en el camp de la lingüística, un descobriment que va impactar directament a la teoria de llenguatges de programació i altres branques de la informàtica.
A la dècada de 1960, el llenguatge Simula va ser desenvolupat per Ole-Johan Dahl i Kristen Nygaard, molts consideren que és el primer llenguatge orientat a objectes; Simula també va introduir el concepte de corutines.
Durant 1970:
- Un petit equip de científic en Xerox PARC encapçalat per Alan Kay elaboren Smalltalk, un llenguatge orientat a objectes molt conegut pel seu nou (fins a aquest moment desconegut) entorn de desenvolupament.
- Sussman i Steele desenvolupen el llenguatge de programació Scheme, un dialecte de Lisp que incorpora Àmbits lèxics, un espai de noms unificat, i elements del model Actor incloent continuacions de primera classe.
- Backus, en la conferència del Premi Turing de 1977, va assetjar l'estat actual dels llenguatges industrials i va proposar una nova classe de llenguatges de programació ara coneguts com a llenguatges de programació funcional.
- L'aparició del process calculi, com el càlcul de sistemes comunicants de Robin Milner, i el model de Comunicació seqüencial de processos de C. A. R. Hoare, així com models similar de concurrència com el Model Actor de Carl Hewitt.
- L'aplicació de la teoria de tipus com una disciplina als llenguatges de programació, liderada per Milner; aquesta aplicació ha conduït a un gran avanç en la teoria de tipus en qüestió d'anys.
A la dècada de 1990:
- Philip Wadler va introduir l'ús de monads per estructurar programes escrits en llenguatges de programació funcional.

Subdisciplines i camps relacionats

Hi ha diversos camps d'estudi que o bé cauen dins de la teoria de llenguatges de programació, o bé tenen una profunda influència en ella, molts d'aquests es superposen considerablement.

Teoria dels compiladors és la base formal sobre l'escriptura de compiladors (o més generalment traductors ); programes que tradueixen un programa escrit en un llenguatge a una altra forma. Les accions d'un compilador es divideixen tradicionalment en anàlisi sintàctica (escanejar i parser), anàlisi semàntica (determinant que és el que hauria de fer un programa), optimització (millorant el rendiment indicat per certa mesura, típicament la velocitat d'execució) i generació de codi (generant la sortida d'un programa equivalent en el llenguatge desitjat, sovint el set d'instruccions d'una CPU).
La Teoria de tipus és l'estudi de sistemes de tipus, que són "mètodes sintàctics tractables per proveir l'absència de certs comportaments de programa mitjançant la classificació de frases segons els tipus de valors que computen. " (Types and Programming Languages, MIT Press, 2002). Molts llenguatges de programació es distingeixen per les característiques dels seus sistemes de tipus.
La Semàntica formal és l'especificació formar del comportament de programes d'ordinador i llenguatges de programació.
La Transformació de programes és el procés de transformar un programa d'una forma (llenguatge) a una altra forma, l'anàlisi de programes és problema general d'examinar un programa mitjançant la determinació de les seves característiques clau (com l'absència de classes d'errors de programa).
Sistemes en temps d'execució es refereix al desenvolupament d'entorns runtime per a llenguatges de programació i els seus components, incloent-hi màquines virtuals, recollida d'escombraries, i interfícies per funcions externes.
Anàlisi comparativa de llenguatges de programació busca classificar els llenguatges de programació en diferents tipus basats en les seves característiques; àmplies categories de diferents llenguatges de programació es coneixen sovint com paradigmes de computació.
Meta-programació és la generació de programes de major ordre que, quan s'executen, produeixen programes (possiblement en un llenguatge diferent, o en un subconjunt del llenguatge original) com a resultat.
Llenguatges dedicats són llenguatges construïts per resoldre problemes en un domini de problemes en particular de manera eficient.

A més, PLT fa ús de moltes altres branques de les matemàtiques, enginyeria del programari, lingüística, i fins i tot ciències cognitives

Revistes i publicacions específiques sobre PLT

Entre les revistes que publiquen investigació sobre la teoria de llenguatges de programació, hi ha:

ACM Transactions on Programming Languages and Systems topless/
Computer Languages, Systems, and Structures [2]
Journal of Functional Programming, The
Journal of Functional and Logic Programming, The
Journal of Symbolic Computation, The
Theoretical Computer Science

Una bibliografia més completa està disponible aquí Arxivat 2007-03-11 a Wayback Machine..

Enllaços externs