20Emedding Prolog In Haskell

Proceedingsofthe1999HaskellWorkshopErikMeijer(editor)UU-CS-1999-28FridayOctober9th,1999,Paris,FranceProceedingsofthe1999HaskellWorkshopUU-CS-1999-28ErikMeijer(editor)FridayOctober1st,1999,Paris,France1999HaskellWorkshopThepurposeoftheworkshopistodiscussexperiencewithHaskell,andpossiblefuturedevelopmentsofthelanguage.Thelivelydiscussionsatthe1997HaskellWorkshopinAmsterdamaboutthefutureofHaskellledtothedenitionofHaskell’98,givingHaskellthestabilitythathassofarbeenlacking.TheroadaheadtoHaskell-2hasmanyopportuni-tiesfordevelopingandenhancingHaskellinnewandexcitingways.ThethirdHaskellworkshoppresentssixpapersonthedesign,implementation,anduseofHaskell.TheprogramcommitteeconsistedofKoenClaessen(Chalmers)ByronCook(OGI)GregoryHager(TheJohnsHopkinsUniversity)GrahamHutton(Nottingham)AlexanderJacobson(shop.com)FergusHenderson(Melbourne)SigbjornFinne(Glasgow)ErikMeijer(Utrecht){chairColinRunciman(York)PhilipWadler(BellLabs,LucentTechnologies)TheHaskellWorkshopwasheldinconjuctionwithPLI’99andwassponsoredbyINRIA,CNRS,MicrosoftResearch,TrustedLogic,FranceTelecom,andtheFrenchMinisteredel’EducationNationaledelaRechercheetdelaTechnology.AdditionalsponsoringwasreceivedbytheUniversityResearchProgramsgroupofMicrosoftResearchCambridgefortheJakeproject.ThegoalofJakeistodevelopasetofPerlandTclfreeconferencemanagementtoolscompletelyprogrammedinHaskell.ErikMeijerSeptember1999WorkshopProgram8:30-9:30PLIInvitedtalkMobilityintheJoin-CalculusGeorgesGonthier(INRIARocquencourt,France)9:45-10:45Session1TypingHaskellInHaskellMarkJones(OregonGraduateInstitute,USA)Haskelllibrarytemplateeort(10minuteslot)AndyGill(OregonGraduateInstitute,USA)10:45-11:15Coeebreak11:15-12:45Session2EmbeddingProloginHaskellSilvijaSeresandMikeSpivey(OxfordUniversity,UK)LogicalAbstractionsinHaskellNancyA.Day,JohnLaunchburyandJeLewis(OregonGraduateInstitute,USA)12:45-14:30Lunch14:30-16:00Session3TheSyntacticalSubtletiesofHaskell(InvitedTalk)SimonMarlow(MicrosoftResearchCambridge,UK)LightweightExtensibleRecordsforHaskellMarkJones(OregonGraduateInstitute,USA)andSimonPeytonJones(Mi-crosoftResearchCambridge,UK)16:00-16:30Teatime16:30-18:00Session4AGenericProgrammingExtensionforHaskellRalfHinze(BonnUniversity,Germany)RestrictedDatatypesinHaskellJohnHughes(ChalmersUniversity,Sweden)18:00-18:30Session5Dependenttypes:Doingwithoutthem(10minuteslot)DanielFridlender(BRICS,Denmark)andMiaIndrika(ChalmersUniversity,Sweden)ThefutureofHaskell(Open-mikesession)TypingHaskellInHaskellMarkJones(OregonGraduateInstitute,USA)TypingHaskellinHa[e-mail]n:September1,1999AbstractHaskellbenetsfromasophisticatedtypesystem,butim-plementors,programmers,andresearcherssuerbecauseithasnoformaldescription.Toremedythisshortcoming,wepresentaHaskellprogramthatimplementsaHaskelltype-checker,thusprovidingamathematicallyrigorousspecica-tioninanotationthatisfamiliartoHaskellusers.WeexpectthisprogramtollaseriousgapincurrentdescriptionsofHaskell,bothasastartingpointfordiscussionsaboutex-istingfeaturesofthetypesystem,andasaplatformfromwhichtoexplorenewproposals.1IntroductionHaskell1benetsfromoneofthemostsophisticatedtypesystemsofanywidelyusedprogramminglanguage.Unfor-tunately,italsosuersbecausethereisnoformalspecica-tionofwhatthetypesystemshouldbe.Asaresult:ItishardforHaskellimplementorstobesurethattheircompilersandinterpretersacceptthesameprogramsasotherimplementations.TheinformalspecicationintheHaskellreport[10]leavestoomuchroomforconfusionandmisinterpretation.Thisleadstogenuinediscrepanciesbetweenimplementations,asmanysub-scriberstotheHaskellmailinglistwillhaveseen.ItishardforHaskellprogrammerstounderstandthedetailsofthetypesystem,andtoappreciatewhysomeprogramsareacceptedwhenothersarenot.For-malpresentationsofmostaspectsofthetypesystemareavailableintheresearchliterature,butoftenab-stractonspecicfeaturesthatareHaskell-like,butnotHaskell-exact,anddonotdescribethecompletetypesystem.Moreover,thesepapersoftenusedisparateandunfamiliartechnicalnotationandconceptsthatmaybehardforsomeHaskellprogrammerstounderstand.ItishardforHaskellresearcherstoexplorenewtypesystemextensions,oreventostudyusabilityissuesthatarisewiththepresenttypesystemsuchasthesearchforbettertypeerrordiagnostics.Workintheseareasrequiresaclearunderstandingofthetypesystemand,ideally,aplatformonwhichtobuildandexperiment1Throughout,weuse‘Haskell’asanabbreviationfor‘Haskell98’.withprototypeimplementations.TheexistingHaskellimplementationsarenotsuitableforthis(andwerenotintendedtobe):thenutsandboltsofatypesystemareeasilyobscuredbytheuseofspecicdatastructuresandoptimizations,orbytheneedtointegratesmoothlywithotherpartsofanimplementation.ThispaperpresentsaformaldescriptionoftheHaskelltypesystemusingthenotationofHaskellitselfasaspecicationlanguage.Indeed,thesourcecodeforthispaperisitselfanexecutableHaskellprogramthatispassedthroughacustompreprocessorandthenthroughLATEXtoobtainthetypesetversion.ThetypecheckerisavailableinsourceformontheInternetat