Jump to...
-
Off-line partial evaluator...
- Benchamark list
Example: dbspec
[ Original program ] [ Annotated program ] [ Specialized program ] [ Runtimes ]
This program was designed by us, to demonstrate the usefulness of specialization in a database problem related to.
Dababase contains two tables, the first is the employee table, its records contains next fields: key (integer), name, category of the employee, personal code and position. The category is a foreign key. The second table has following structure: key (data constructor) that represents a category of employee and an amount that means the pay per hour for an employee of that category.
The program calculates the payment of an employee based on his category (which give us his pay per hour) and on the number of hours labored.
-- Extracting a fragment of one program and deleting queries from a database
data Nat = Z | S Nat
data Categories = A | B | C | D
--expression for specialization
main emp hrs = nominaC A emp hrs
-- employees table , record=(key, name, category, id, position)
recE :: Int -> (String, Categories, String, String)
recE 1 = ("Juan Perez" ,A,"JP72/07/11H","Engineer")
recE 2 = ("Pedro Ruiz" ,A,"PR78/12/22H","Technic")
recE 3 = ("Juan Leon" ,C,"JL77/06/18H","Medical")
recE 4 = ("Luisa Calderon" ,B,"LC45/11/10M","Worker")
recE 5 = ("Uc May" ,B,"UM66/07/19H","Worker")
recE 6 = ("Caltzontzin" ,A,"CA76/05/08H","Engineer")
recE 7 = ("Tariacuri" ,C,"TA81/02/04M","Warehouseman")
recE 8 = ("Tzintzuntzan" ,D,"TZ80/01/23H","Guard")
recE 9 = ("Churintzio" ,C,"CD60/10/26H","Manager")
recE 10 = ("Carapan" ,C,"CA63/01/01H","Engineer")
recE 11 = ("Ana Perez" ,A,"AN72/07/17H","Engineer")
recE 12 = ("Jorge Ruiz" ,A,"JR78/12/12H","Technic")
recE 13 = ("David Leon" ,C,"DL77/08/17H","Medical")
recE 14 = ("Maria Calderon" ,B,"MC74/11/18M","Worker")
recE 15 = ("Uc Chulim" ,B,"UC66/06/29H","Worker")
recE 16 = ("Uxmal" ,A,"UX74/04/18H","Engineer")
recE 17 = ("Tajin" ,C,"TA01/09/30M","Warehouseman")
recE 18 = ("Tzitzio" ,D,"TZ85/01/13H","Guard")
recE 19 = ("Tlazazalca" ,C,"TL60/12/16H","Manager")
recE 20 = ("Cuauhtemoc" ,C,"CU65/01/11H","Engineer")
recE 21 = ("Tlaloc" ,A,"TL72/07/21H","Engineer")
recE 22 = ("Lauro Ruiz" ,A,"LR78/10/12H","Technic")
recE 23 = ("Manuel Leon" ,C,"ML77/08/28H","Medical")
recE 24 = ("Tarcicio C" ,B,"TA45/12/20M","Worker")
recE 25 = ("Tzurumucuaro" ,B,"TZ66/12/29H","Worker")
recE 26 = ("Puruandiro" ,A,"PU77/02/23H","Engineer")
recE 27 = ("Huandacareo" ,C,"HU81/03/14M","Warehouseman")
recE 28 = ("Cuitzeo" ,D,"CU70/06/13H","Guard")
recE 29 = ("Patzcuaro" ,C,"PA60/11/06H","Manager")
recE 30 = ("Tzitzimeo" ,C,"TZ67/05/21H","Engineer")
recE 31 = ("Carapan" ,A,"CA72/06/01H","Engineer")
recE 32 = ("Uruapan" ,A,"UR78/10/02H","Technic")
recE 33 = ("Coahuayanan" ,C,"CO77/09/28H","Medical")
recE 34 = ("Ecuandureo" ,B,"EX85/10/20M","Worker")
recE 35 = ("Cheran" ,B,"CH66/08/29H","Worker")
recE 36 = ("Charo" ,A,"CH78/04/18H","Engineer")
recE 37 = ("Zacapu" ,C,"ZA81/06/24M","Warehouseman")
recE 38 = ("Chilchota" ,D,"CH80/02/23H","Guard")
recE 39 = ("Tangamandapio" ,C,"TA66/11/06H","Manager")
recE 40 = ("Huaniqueo" ,C,"HU63/06/11H","Engineer")
recE 41 = ("Jiquilpan" ,A,"JI62/03/21H","Engineer")
recE 42 = ("Copandaro" ,A,"CO78/10/22H","Technic")
recE 43 = ("Chupicuaro" ,C,"CH76/04/19H","Medical")
recE 44 = ("Purepero" ,B,"PU46/12/01M","Worker")
recE 45 = ("Aramutarillo" ,B,"AR66/05/29H","Worker")
recE 46 = ("Paracho" ,A,"PA76/08/18H","Engineer")
recE 47 = ("Zinapecuaro" ,C,"ZI81/04/14M","Warehouseman")
recE 48 = ("Angamacutiro" ,D,"AN80/06/03H","Guard")
recE 49 = ("Cueramaro" ,C,"CU60/11/16H","Manager")
recE 50 = ("Tocumbo" ,C,"TO63/10/11H","Engineer")
-- categories table, record = (category, pay per hour)
recC:: Categories -> Nat
recC A = (S(S(S(S(S(S(S(S(S(S Z))))))))))
recC B = (S(S(S(S(S(S(S(S(S(S(S(S(S(S(S Z)))))))))))))))
recC C = (S(S(S(S(S(S(S(S(S(S(S(S(S(S(S(S(S(S(S(S Z))))))))))))))))))))
recC D = (S(S(S(S(S(S(S(S Z))))))))
nominaG ::Int -> Nat -> Nat
nominaG emp hours = calcSal (getCatE (recE emp)) (recC (getCatE (recE emp))) hours
nominaC ::Categories->Int -> Nat -> Nat
nominaC x emp hours = calcSal x (recC (getCatE (recE emp))) hours
calcSal :: Categories -> Nat -> Nat -> Nat
calcSal A pph hours = add (S(S(S(S Z)))) (mult pph hours)
calcSal B pph hours = mult pph hours
calcSal C pph hours = mult pph hours
calcSal D pph hours = add (S(S(S(S(S(S Z)))))) (mult pph hours)
getCatE::(String, Categories, String, String)->Categories
getCatE (_ , c, _, _) = c
--arithmetic expressions
mult Z _ = Z
mult (S x) y = add y (mult x y)
add Z y = y
add (S n) y = S (add n y)
-- identity function for generalization
GEN x = x
--------------------------------------------------------
-- Auxiliary tools not for specialization
s2n Z = 0
s2n (S n)= 1 + (s2n n)
n2s x = if x==0 then Z else S(n2s (x-1))
Given a category nominaC calculates the payment by means of a search of the corresponding pay per hour for that category.
The goal of the specialization is reduce the table access and reach the extraction of a fragment of the program that is related to that category specifically. In other words is possible to generate one program for each category, without need of access the table of categories.
The program annotated in order to ensure a finite specialization process is this..
-- Extracting a fragment of one program and deleting queries from a database
data Nat = Z | S Nat
data Categories = A | B | C | D
--expression for specialization
main emp hrs = nominaC A emp hrs
-- employees table , record=(key, name, category, id, position)
recE :: Int -> (String, Categories, String, String)
recE 1 = ("Juan Perez" ,A,"JP72/07/11H","Engineer")
recE 2 = ("Pedro Ruiz" ,A,"PR78/12/22H","Technic")
recE 3 = ("Juan Leon" ,C,"JL77/06/18H","Medical")
recE 4 = ("Luisa Calderon" ,B,"LC45/11/10M","Worker")
recE 5 = ("Uc May" ,B,"UM66/07/19H","Worker")
recE 6 = ("Caltzontzin" ,A,"CA76/05/08H","Engineer")
recE 7 = ("Tariacuri" ,C,"TA81/02/04M","Warehouseman")
recE 8 = ("Tzintzuntzan" ,D,"TZ80/01/23H","Guard")
recE 9 = ("Churintzio" ,C,"CD60/10/26H","Manager")
recE 10 = ("Carapan" ,C,"CA63/01/01H","Engineer")
recE 11 = ("Ana Perez" ,A,"AN72/07/17H","Engineer")
recE 12 = ("Jorge Ruiz" ,A,"JR78/12/12H","Technic")
recE 13 = ("David Leon" ,C,"DL77/08/17H","Medical")
recE 14 = ("Maria Calderon" ,B,"MC74/11/18M","Worker")
recE 15 = ("Uc Chulim" ,B,"UC66/06/29H","Worker")
recE 16 = ("Uxmal" ,A,"UX74/04/18H","Engineer")
recE 17 = ("Tajin" ,C,"TA01/09/30M","Warehouseman")
recE 18 = ("Tzitzio" ,D,"TZ85/01/13H","Guard")
recE 19 = ("Tlazazalca" ,C,"TL60/12/16H","Manager")
recE 20 = ("Cuauhtemoc" ,C,"CU65/01/11H","Engineer")
recE 21 = ("Tlaloc" ,A,"TL72/07/21H","Engineer")
recE 22 = ("Lauro Ruiz" ,A,"LR78/10/12H","Technic")
recE 23 = ("Manuel Leon" ,C,"ML77/08/28H","Medical")
recE 24 = ("Tarcicio C" ,B,"TA45/12/20M","Worker")
recE 25 = ("Tzurumucuaro" ,B,"TZ66/12/29H","Worker")
recE 26 = ("Puruandiro" ,A,"PU77/02/23H","Engineer")
recE 27 = ("Huandacareo" ,C,"HU81/03/14M","Warehouseman")
recE 28 = ("Cuitzeo" ,D,"CU70/06/13H","Guard")
recE 29 = ("Patzcuaro" ,C,"PA60/11/06H","Manager")
recE 30 = ("Tzitzimeo" ,C,"TZ67/05/21H","Engineer")
recE 31 = ("Carapan" ,A,"CA72/06/01H","Engineer")
recE 32 = ("Uruapan" ,A,"UR78/10/02H","Technic")
recE 33 = ("Coahuayanan" ,C,"CO77/09/28H","Medical")
recE 34 = ("Ecuandureo" ,B,"EX85/10/20M","Worker")
recE 35 = ("Cheran" ,B,"CH66/08/29H","Worker")
recE 36 = ("Charo" ,A,"CH78/04/18H","Engineer")
recE 37 = ("Zacapu" ,C,"ZA81/06/24M","Warehouseman")
recE 38 = ("Chilchota" ,D,"CH80/02/23H","Guard")
recE 39 = ("Tangamandapio" ,C,"TA66/11/06H","Manager")
recE 40 = ("Huaniqueo" ,C,"HU63/06/11H","Engineer")
recE 41 = ("Jiquilpan" ,A,"JI62/03/21H","Engineer")
recE 42 = ("Copandaro" ,A,"CO78/10/22H","Technic")
recE 43 = ("Chupicuaro" ,C,"CH76/04/19H","Medical")
recE 44 = ("Purepero" ,B,"PU46/12/01M","Worker")
recE 45 = ("Aramutarillo" ,B,"AR66/05/29H","Worker")
recE 46 = ("Paracho" ,A,"PA76/08/18H","Engineer")
recE 47 = ("Zinapecuaro" ,C,"ZI81/04/14M","Warehouseman")
recE 48 = ("Angamacutiro" ,D,"AN80/06/03H","Guard")
recE 49 = ("Cueramaro" ,C,"CU60/11/16H","Manager")
recE 50 = ("Tocumbo" ,C,"TO63/10/11H","Engineer")
-- categories table, record = (category, pay per hour)
recC:: Categories -> Nat
recC A = (S(S(S(S(S(S(S(S(S(S Z))))))))))
recC B = (S(S(S(S(S(S(S(S(S(S(S(S(S(S(S Z)))))))))))))))
recC C = (S(S(S(S(S(S(S(S(S(S(S(S(S(S(S(S(S(S(S(S Z))))))))))))))))))))
recC D = (S(S(S(S(S(S(S(S Z))))))))
nominaG ::Int -> Nat -> Nat
nominaG emp hours = calcSal (getCatE (recE emp)) (recC (getCatE (recE emp))) hours
nominaC ::Categories->Int -> Nat -> Nat
nominaC x emp hours = calcSal x (recC (getCatE (recE emp))) hours
calcSal :: Categories -> Nat -> Nat -> Nat
calcSal A pph hours = add (S(S(S(S Z)))) (GEN (mult pph hours))
calcSal B pph hours = mult pph hours
calcSal C pph hours = mult pph hours
calcSal D pph hours = add (S(S(S(S(S(S Z)))))) (GEN (mult pph hours))
getCatE::(String, Categories, String, String)->Categories
getCatE (_ , c, _, _) = c
--arithmetic expressions
mult Z _ = Z
mult (S x) y = add y (GEN (mult x y))
add Z y = y
add (S n) y = S (add n y)
-- identity function for generalization
GEN x = x
--------------------------------------------------------
-- Auxiliary tools not for specialization
s2n Z = 0
s2n (S n)= 1 + (s2n n)
n2s x = if x==0 then Z else S(n2s (x-1))
Specialized program
[ go top ]
In PAKCS, and once loaded OffPeval, run mix "examples/bdspec", you can load and show the specialized program as follows.
prelude> :l bdnomina_pe
Compiling './bdnomina_pe.fcy' into Prolog program 'bdnomina_pe.pl'...
bdnomina_pe(module: bdnomina)> :show
No source program file available, generating source from FlatCurry...
-- Program file: bdnomina_pe
module bdnomina(Nat(Z,S),Categories(A,B,C,D),recE,recC,nominaG,nominaC,calcSal,getCatE,
mult,add,GEN,s2n,n2s,main,add_pe1,mult_pe2,add_pe3,mult_pe4,mult_pe6,mult_pe14,
mult_pe19) where
data Nat = Z | S Nat
data Categories = A | B | C | D
main :: c -> b -> a
main v0 v1 = add_pe1 (mult_pe2 v0 v1)
add_pe1 :: b -> a
add_pe1 v7 = S (S (S (S v7)))
mult_pe2 :: c -> b -> a
mult_pe2 eval flex
mult_pe2 1 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 2 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 3 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 4 v1 = add_pe3 v1 (mult_pe19 v1)
mult_pe2 5 v1 = add_pe3 v1 (mult_pe19 v1)
mult_pe2 6 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 7 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 8 v1 = add_pe3 v1 (mult_pe6 v1)
mult_pe2 9 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 10 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 11 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 12 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 13 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 14 v1 = add_pe3 v1 (mult_pe19 v1)
mult_pe2 15 v1 = add_pe3 v1 (mult_pe19 v1)
mult_pe2 16 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 17 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 18 v1 = add_pe3 v1 (mult_pe6 v1)
mult_pe2 19 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 20 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 21 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 22 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 23 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 24 v1 = add_pe3 v1 (mult_pe19 v1)
mult_pe2 25 v1 = add_pe3 v1 (mult_pe19 v1)
mult_pe2 26 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 27 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 28 v1 = add_pe3 v1 (mult_pe6 v1)
mult_pe2 29 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 30 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 31 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 32 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 33 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 34 v1 = add_pe3 v1 (mult_pe19 v1)
mult_pe2 35 v1 = add_pe3 v1 (mult_pe19 v1)
mult_pe2 36 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 37 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 38 v1 = add_pe3 v1 (mult_pe6 v1)
mult_pe2 39 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 40 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 41 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 42 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 43 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 44 v1 = add_pe3 v1 (mult_pe19 v1)
mult_pe2 45 v1 = add_pe3 v1 (mult_pe19 v1)
mult_pe2 46 v1 = add_pe3 v1 (mult_pe4 v1)
mult_pe2 47 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 48 v1 = add_pe3 v1 (mult_pe6 v1)
mult_pe2 49 v1 = add_pe3 v1 (mult_pe14 v1)
mult_pe2 50 v1 = add_pe3 v1 (mult_pe14 v1)
add_pe3 :: c -> b -> a
add_pe3 eval flex
add_pe3 Z v17 = v17
add_pe3 (S v1504) v17 = S (add_pe3 v1504 v17)
mult_pe4 :: b -> a
mult_pe4 v1 = add_pe3 v1 (add_pe3 v1 (mult_pe6 v1))
mult_pe6 :: b -> a
mult_pe6 v1 = add_pe3 v1 (add_pe3 v1 (add_pe3 v1 (add_pe3 v1 (add_pe3 v1 (add_pe3 v1 (add_pe3 v1 Z))))))
mult_pe14 :: b -> a
mult_pe14 v1 = add_pe3 v1 (add_pe3 v1 (add_pe3 v1 (add_pe3 v1 (add_pe3 v1 (mult_pe19 v1)))))
mult_pe19 :: b -> a
mult_pe19 v1 = add_pe3 v1 (add_pe3 v1 (add_pe3 v1 (add_pe3 v1 (add_pe3 v1 (mult_pe4 v1)))))
-- end of module bdnomina_pe
Here we show only the fragment partially evaluated, let us note that the query for access to the categories table (records as recC), to get the payment per hour, has disappeared and the table employees too. Employees table has now only the function call for calculate the payment for this employee. The problem of access a database has been reduced and the fragment required for the calculation has been retrieved.
| program | original runtime average | specialized runtime average | speed up |
|
bdspec |
[ go to top ]