APE: An Expert System for Automatic Programming from Abstract Specifications of Data Types and Algorithms

Bartels, Ulrich; Olthoff, Walter G.; Raulefs, Peter

APE: An Expert System for Automatic Programming from Abstract Specifications of Data Types and Algorithms

Ulrich Bartels, Walter G. Olthoff, Peter Raulefs

Download BibTeX Cite

Proceedings of the Seventh International Joint Conference on Artificial Intelligence. Program Synthesis. Pages 1037-1042.

Abstract

The APE (Auto•attc Progra••tng Expert) executable and efficient prograMs fro• • algebraic speci f ications of abstract data • abstract algorithms given as conditional s ys te•s w1th ter• s bu1lt up fro• operat1on abstract data types 1nvolved. systea construct• types, •nd ter~ - rewrite-rule sy•bols of the The APE is an e•perl•ental syste• devised to develop •ethods for cod1fy1ng a rather broad extent of prograMming knowledge requ1red to construct 1•plementations of data types and at gor 1 th•s. for data type specifications, the APE ad•its hidden oper•tlons, conditi o nal a x 1o•s, and para•eter1zed data types. The APE automaticall y iMplements al9ebraic specifications of all coma o nly known data types 1n terms of clusters of lNTERLISPfunctlons . The APE constructs executable implementations of • var i ety of sorting and searching algortthMs. As an exper1nental prototype, the APE deeonstrates that • knowledge-b~sed proor•••ing paradtau prov1des a useful tool for par~lally autoaating an 1•portant phase of software developaent.

78b) Barstow~ O.R. E•per1ence wtth a reftne•ent paradig• 1n a knowledge-based auto•at1c progra•aing syste•. Proc. AJSB /G I-Conference on Arttfictal Intelligence 1978.
Bibel, w. Synta•-directed, seaantics-supported pro- gram synthesis. Proc. 4th Workshop on Auto•atic Deduction (Austin, Te•as>, 1979.
BierMann~ A.w.~ O.R. S•ith. The hierarchical synthesis of LJSP-progra•s. Proc . IFIP 77 (1977) ' 41-45
Ok
Oav1s, R., I.King. An overview of production sys- terts in Elcock~ H1chte (Eds.) "ach1ne Representa- tion of Knowledge. Horwood Wyl1e, 1977.
EH
Ehrig, H. Algebraic theory of para•etertzed spect- flcations with require•ents. Proc. 6th CAAP~ Genova 1981~ Springer-Verlag (tn press>.
BOa] Eige•eier, H., Ch.Knabe, P. Raulefs, k.Tra•er. Auto•at1c i•ple•entation of algebraic speciftc•- ttons of abstract data types. P1emo sn:I-BN-79 (Nov.79)~ Univ. Bonn, Inst. f. ln- for~atlk III and Proc. AISB -80 Conf. on Arttfict•l Intelligence.
EigeMeier~ H., Ch.Knabe~ P.Rautefs. k.Tra•er. An e•pert systeM for autoMatic cod1ng of abstract dat• type specif;cations. Proc. 10th Annual GI-Conf.~ Springer lnforeatik- Fachberlchte 33,1980, pp . 431-441.
Green, C.C. The design of the PSI prograa synthettl syste•. Proc. 2nd Conf . on Software Engineering (Sen Francisco, CAl, 1976.
Hornung, G.~ P . R•ulefs. Tereinal •Lgebra see•nttca and retracttons for abstract data types. Proc. 7th JCALP, 1980. Springer LNCS, Vol.85, pp. 31D-3Z3
Hornung, G., P.Raulefs. Initial and ter•tnel algebra se•antics of para•eter1zed abstract d•t• type specificattons with inequalities . Proc. 6th CAAP, Genova 1981, Spr1nger-verl•o (tn press).
Kant, E. Eff1ctency constderattons 1n progreaetng syntheSIS: a knowledge-based appro•ch. (KN 73]
Knuth, D.E. The Art of Co•puter Progr•••tng. Vol.3, Addlson-Wesley, 1973
Manna, z., R. Waldtnger. synthe1i1 : Dr•••• •> Pro- gra•s. IEEE-TSE , ~ (1979)294-3Z7.

References were extracted automatically from the PDF and may contain errors.

Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.

1. Final Re·arks and Conclusions.

7.1 Interactjve Syste· Development and Theorv ForMation. The development of the APE has been evoluttonary, dr1ven by con Sidertng ·ore and More e·amples~ and feeding the progra··ing knowledge necessary to taplement the e·amples 1nto the produc tion bases . To support codify1ng and 1ncorporat1ng prograaatng knowledge~ APE has an extens1ve 1nteract1ve user interface. Thts interf·ce helps a user to find out why APE failed, coding new rules and exper1aent1ng with them~ a11d finally changing ·eta-rules and the production control un1t after Inserting new rules tnto the production bases. The usertnterface 1s e·trealy 1111portant for up!Jradtng the product ton bases: whenever a new porttort of program·tng knowledge has been fed to APE~ tt t1 usually 1n order to condense rules 1nto fewer and ·ore general rules. Rule eandens·tion actually contributes to the foraatton of a theory of progra··tna · , and we expect such a theory to eventually evolve from our 1nvestigat1on.

7 . 2. Accomplishment~. Previous systeMs start at · ·uch ·ore concrete level of data structures such as sets, collections, etc., and IMple·cnt the· at the so·ewhat ·ore "concrete· level of lists. arrays~ etc . APE generates code fro· represent~tton free ·xto·attz~tions of all structures ~revtous systems could t~plement, and 1n add1t1on succeeded for ~bout 70 other aM1o·at1zat1ons. APE generates clusters of rout1nes which aay be autually recurstve. P··evtous syste·s could not Introduce recurs tons.

?~~~££essful Parad~. Consid~ring the a·ount of work whiCh has been 1nve~ted 1n 1ts development so far~ the APE ts st1ll 10 1ls Infancy. Oeaonstratcd accompltsh·ents and e·peri ments have shown that w1th 1ncorporat1ng adU1t1onal progra· etng knowledge, the APE wtll beco· c a powerful tool in software develop·ent. G1ven the li·iled success of the progra· synthesis paradtgas (e.g. [Bl 79], [OS 77], (HW 79]) after · decade of work~ we cla1· that the kno~ledge-based progra··tng paradigm supported by the APE IS the only approach which ts l1kely to provide tools for substant1ally automat1ng phases of til e 1ndustr1al software development cycle. Ir1 fact~ we thtnk that program synthes1s and krlowledge-biiSCd progr·amm1ng co·ple ~ent each ott1er : Program synthes1s (aS 1n [Ul 79), [HW 79]) should produce abstrac t algor1thms from non-algorith~ic speci fi cat ions . lllen~ a system such as ours br1ngs 1n the expertise to produce eff 1c1ent vrograms .

~eferences

( ADJ 76) Goguen, J.A., J.W. Thatcher~ F.G . Wagner. An Int tlal Algebra Approach to the Spec1ftcat1on, Cor rectness and J~ple·entat1on of Abstract Data Types . IB" Resoarch Rept . RC-6487 C1976l.

[ADJ 80]. Ehrig, H.~ H .- J .k reowskl~ J.W . Thatcher, E.G. Wagner, J.B. \Jright. Par·alfteterlzed Dati Types tn Algebratc Spec1f1cat1on Languages. Proc. 7th JCALP, 1980. Springer LNCS, Vol.85, pp. 157-168

[BAR 78·] Barstow, O.R. Autoeatic construction of algortthel and data structures usrng a knowledge-base of pro gra··lng rules . Ropt. STAN-CS-77-641(77), Stanford U.
[BAR 78b) Barstow~ O.R. E·per1ence wtth a reftne·ent paradig· 1n a knowledge-based auto·at1c progra·aing syste·. Proc. AJSB/G I-Conference on Arttfictal Intelligence 1978.
[81 79] Bibel, w. Synta·-directed, seaantics-supported pro gram synthesis. Proc. 4th Workshop on Auto·atic Deduction (Austin, Te·as>, 1979.
[BS 77] BierMann~ A.w.~ O.R. S·ith. The hierarchical synthesis of LJSP-progra·s. Proc . IFIP 77 (1977) ' 41-45
[Ok 77] Oav1s, R., I.King. An overview of production sys

terts in Elcock~ H1chte (Eds.) "ach1ne Representa tion of Knowledge. Horwood Wyl1e, 1977.

[EH 81) Ehrig, H. Algebraic theory of para·etertzed spect flcations with require·ents. Proc. 6th CAAP~ Genova 1981~ Springer-Verlag (tn press>.
[EKRT BOa] Eige·eier, H., Ch.Knabe, P. Raulefs, k.Tra·er. Auto·at1c i·ple·entation of algebraic speciftc· ttons of abstract data types. P1emo sn:I-BN-79 (Nov.79)~ Univ. Bonn, Inst. f. ln for~atlk III and Proc. AISB - 80 Conf. on Arttfict·l Intelligence.
[EKTR 8Db] EigeMeier~ H., Ch.Knabe~ P.Rautefs. k.Tra·er. An e·pert systeM for autoMatic cod1ng of abstract dat· type specif;cations. Proc. 10th Annual �I-Conf.~ Springer lnforeatik Fachberlchte 33,1980, pp . 431-441.
[GR 76] Green, C.C. The design of the PSI prograa synthettl syste·. Proc. 2nd Conf . on Software Engineering (Sen Francisco, CAl, 1976.
[HR 80] Hornung, �.~ P. R·ulefs. Tereinal ·Lgebra see·nttca and retracttons for abstract data types. Proc. 7th JCALP, 1980. Springer LNCS, Vol.85, pp. 31D-3Z3
[HR 81] Hornung, G., P.Raulefs. Initial and ter·tnel algebra se·antics of para·eter1zed abstract d·t· type specificattons with inequalities . Proc. 6th CAAP, Genova 1981, Spr1nger-verl·o (tn press).
[KA 79] Kant, E. Eff1ctency constderattons 1n progreaetng syntheSIS: a knowledge-based appro·ch. Tech. Rept. STAN-CS-79- 755, Co111p . ScL Oept,. Stanford Univ.
(KN 73] Knuth, D.E. The Art of Co·puter Progr···tng. Vol.3, Addlson-Wesley, 1973
Manna, z., R. Waldtnger. synthe1i1 : Dr···· ·> Pro gra·s. IEEE-TSE , ~ (1979)294-3Z7.

Ulrich Bartels, Walter G. Olthoff, and Peter Raulefs. 1981. APE: An Expert System for Automatic Programming from Abstract Specifications of Data Types and Algorithms. In Proceedings of the Seventh International Joint Conference on Artificial Intelligence, IJCAI-81. IJCAI, 1037–1042. https://ijcai.org/proceedings/1981/198

@inproceedings{ijcai1981p198,
  title     = {APE: An Expert System for Automatic Programming from Abstract Specifications of Data Types and Algorithms},
  author    = {Bartels, Ulrich and Olthoff, Walter G. and Raulefs, Peter},
  booktitle = {Proceedings of the Seventh International Joint Conference on
               Artificial Intelligence, {IJCAI-81}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Patrick J. Hayes},
  pages     = {1037--1042},
  year      = {1981},
  month     = {8},
  note      = {Program Synthesis},
  url       = {https://ijcai.org/proceedings/1981/198},
}

TY  - CPAPER
TI  - APE: An Expert System for Automatic Programming from Abstract Specifications of Data Types and Algorithms
AU  - Bartels, Ulrich
AU  - Olthoff, Walter G.
AU  - Raulefs, Peter
T2  - Proceedings of the Seventh International Joint Conference on Artificial Intelligence, IJCAI-81
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1981
SP  - 1037
EP  - 1042
UR  - https://ijcai.org/proceedings/1981/198
ER  -

[1] 78b) Barstow~ O.R. E•per1ence wtth a reftne•ent paradig• 1n a knowledge-based auto•at1c progra•aing syste•. Proc. AJSB /G I-Conference on Arttfictal Intelligence 1978.

[2] Bibel, w. Synta•-directed, seaantics-supported pro- gram synthesis. Proc. 4th Workshop on Auto•atic Deduction (Austin, Te•as>, 1979.

[3] BierMann~ A.w.~ O.R. S•ith. The hierarchical synthesis of LJSP-progra•s. Proc . IFIP 77 (1977) ' 41-45

[4] Ok

[5] Oav1s, R., I.King. An overview of production sys- terts in Elcock~ H1chte (Eds.) "ach1ne Representa- tion of Knowledge. Horwood Wyl1e, 1977.

[6] EH

[7] Ehrig, H. Algebraic theory of para•etertzed spect- flcations with require•ents. Proc. 6th CAAP~ Genova 1981~ Springer-Verlag (tn press>.

[8] BOa] Eige•eier, H., Ch.Knabe, P. Raulefs, k.Tra•er. Auto•at1c i•ple•entation of algebraic speciftc•- ttons of abstract data types. P1emo sn:I-BN-79 (Nov.79)~ Univ. Bonn, Inst. f. ln- for~atlk III and Proc. AISB -80 Conf. on Arttfict•l Intelligence.

[9] EigeMeier~ H., Ch.Knabe~ P.Rautefs. k.Tra•er. An e•pert systeM for autoMatic cod1ng of abstract dat• type specif;cations. Proc. 10th Annual GI-Conf.~ Springer lnforeatik- Fachberlchte 33,1980, pp . 431-441.

[10] Green, C.C. The design of the PSI prograa synthettl syste•. Proc. 2nd Conf . on Software Engineering (Sen Francisco, CAl, 1976.

[11] Hornung, G.~ P . R•ulefs. Tereinal •Lgebra see•nttca and retracttons for abstract data types. Proc. 7th JCALP, 1980. Springer LNCS, Vol.85, pp. 31D-3Z3

[12] Hornung, G., P.Raulefs. Initial and ter•tnel algebra se•antics of para•eter1zed abstract d•t• type specificattons with inequalities . Proc. 6th CAAP, Genova 1981, Spr1nger-verl•o (tn press).

[13] Kant, E. Eff1ctency constderattons 1n progreaetng syntheSIS: a knowledge-based appro•ch. (KN 73]

[14] Knuth, D.E. The Art of Co•puter Progr•••tng. Vol.3, Addlson-Wesley, 1973

[15] Manna, z., R. Waldtnger. synthe1i1 : Dr•••• •> Pro- gra•s. IEEE-TSE , ~ (1979)294-3Z7.