Type inference in the Icon programming language

TypeInferenceintheIconProgrammingLanguage*KennethWalkerandRalphE.GriswoldTR93-32aMarch12,1996DepartmentofComputerScienceTheUniversityofArizonaTucson,Arizona85721*ThisworkwassupportedbytheNationalScienceFoundationunderGrantsDCR-8502015andCCR-8901573.TypeInferenceintheIconProgrammingLanguage1.IntroductionProgramminglanguagesthatdonothaveastrongcompile-timetypesystempresentavarietyofproblemsduringprogramexecution.Ontheotherhand,strongcompile-timetypecheckingprecludesseveralvaluableprogramminglanguagefeatures,suchaspolymorphousproceduresthatcanperformoperationsonvaluesofseveraldifferenttypes.Intheabsenceofcompile-timetypechecking,iftypesarenotcheckedduringprogramexecution,errorsmayoccurthataredifficulttodiagnose,locate,andcorrect.Run-timetypecheckingisexpensive,however,andinthemostgeneralcaseitmustbedonerepeatedly.Evenintheabsenceoffeaturesthatenforcestrongcompile-timetypechecking,acompilermaybeabletoinferthetypesactuallyusedandhencebeabletoavoidmuchoftherun-timetypecheckingthatotherwisewouldbenecessary.TheIconprogramminglanguagepresentsaninterestingcaseinthisregard.InIcon,therearenotypedeclarationsandnotypesassociatedwithvariables.Instead,typeisapropertyofavalue.Theoriginal,interpretiveimplementationofIconperformsrigorousrun-timetypecheckingandincurssignificantoverheadasaresult[1].AnewoptimizingcompilerforIcon,ontheotherhand,hasatypeinferencingsystemthatiseffectiveindeterminingtypeusageandineliminatingmuchoftherun-timetypecheckingthatotherwisewouldberequired[2].ThisreportdescribesthefeaturesofIconthataresignificantfortypeinference,howthetypeinferencingsysteminthecompilerworks,itsimplementation,itscomplexity,andtheimprovementinexecutionspeedthatresultsfromtypeinference.2.TheIconProgrammingLanguageIconisahigh-level,general-purposeprogramminglanguage[3].Itisanexpression-basedprocedurallanguagewithalargerepertoireofoperationsforprocessingstringsandstructures.Icon’sdatastructuresandhowtheyareusedposeachallengeindesigninganeffectivetypeinferencesystemforthelanguage.Backtrackingalsoposesachallenge.WhileotherprogramminglanguagessuchasProlog[4]utilizebacktracking,typeinferencingsystemsforthoselanguagesarequitedifferentfromonesuitableforIcon.ThemainfeaturesofIconthatarerelevanttotypeinferencingare:gTherearenotypedeclarations.Variablesarenottypedandavariablecanhaveavalueofanytype.Values,ontheotherhand,containtypeidentification.Differenttypescanbeassignedtoavariableatdifferenttimes.Allvariableshaveaspecialnullvalueinitially.gSomeexpressionsarepolymorphous,performingdifferentoperationsdependingonthetypesoftheiroperands.Typecheckingisperformedontheoperandsofoperationsthataretypesensitive.Exceptinafeweasilyrecognizedcases,assignmenttoavariableisinsensitivetothetypeofthevalueassigned.Inappropriatetypesfortheoperandsofoperationsarecoercedtoappropriateonesifpossible;otherwiseerrorterminationoccurs.gSomeexpressions,calledgenerators,canproduceasequenceofvaluesthroughasuspension/resumptionevaluationmechanism.Goal-directedevaluationcausescontrolbacktrackingandtheresumptionofsuspendedgenerators.Theresultsproducedbyageneratorneednotallbeofthesametype.gTheevaluationofanexpressionmayproduceavalue(success)ornotproduceanyvalueatall(failure).Ifevaluationofanoperandexpressionfails,theoperationisnotperformed.-1-gProceduresarefirst-classvalues.Procedureparametersarenottyped;theargumentsofprocedurescanhavedifferentvaluesatdifferenttimes.Thevaluereturnedbyaprocedureneednotalwayshavethesametype.gStructuresarecreatedduringprogramexecution.Thesizeofastructuremaygroworshrinkafteritiscreated.Structurevaluesarepointers.Structurescanbe‘‘recursive’’,containingpointerstootherstructuresandtothemselves.Suchrecursivestructuresprecludeafinitetypesystemthatincludescomponenttypes.Structurescanbeheterogeneous,containingvaluesofdifferenttypes.BecauseofthefreedomIconofferstomixandchangethetypesofvaluesassignedtovariablesandcontainedinstructures,itmightseemthattypeusageinIconprogramswouldbehopelesslyconfusedandhencepreventeffectiveuseoftypeinference.Fortunately,thisisnotthecase.AnempiricalstudyusingthetypeinferencesystemdescribedherewasconductedonalargenumberofIconprogramswrittenbymanydifferentauthorsforawidevarietyofapplications.Theresults,whichareconservative,showarangeoftypeconsistencyfromabout60to100%,withanaverageofabout80%.Thatis,ontheaverage,theoperandsofabout80%oftheoperatorsintheseprogramsalwayshavethesametype.ThisdegreeoftypeconsistencyispartlyanaturalconsequenceoftheprogrammingprocessinIconandpartlyareflectionofgenerallygoodprogrammingstyle.WhileitispossibletowriteanIconprogramwithnotypeconsistencyatall,suchprogramsappearnottooccurinpractice.Alowdegreeoftypeconsistencyisnotnecessarilyanindicationofpoorprogrammingstyle.Itmayoccurforaverygoodreason,suchastheuseofpolymorphousprocedures.SomeexamplesmayhelpinunderstandinghowthefeatureslistedaboveaffecttypeusageinIcon.Considertheexpressionsline:=read()write(trim(line))Theexpressionread()failsifthereisnodatatoread.Ifthishappens,theassignmenttolineisnotperformedanditretainsitsformervalue.Consequently,thevalueoflinea