### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Concepts of Programming Languages CS 3361

TTU

GPA 3.92

### View Full Document

## 29

## 0

## Popular in Course

## Popular in ComputerScienence

This 20 page Class Notes was uploaded by Miss Gennaro Considine on Thursday October 22, 2015. The Class Notes belongs to CS 3361 at Texas Tech University taught by Joseph Rushton in Fall. Since its upload, it has received 29 views. For similar materials see /class/226478/cs-3361-texas-tech-university in ComputerScienence at Texas Tech University.

## Similar to CS 3361 at TTU

## Popular in ComputerScienence

## Reviews for Concepts of Programming Languages

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/22/15

3361 Home page SyHabus Grade book Be prepared for a quiz over this Reading Assignment on Monday 831 Homework for Friday Sept 4 Download Dr Scheme and familiarize yourself with it Write functions 9 h and foo in Scheme which implement the following specifications 9Xv Xy v2 hXv2 Xy if Xlty yz otherwise fooX L returns X if X is a member of list L otherwise returns the empty list If you have questions about the assignment don39t hesitate to email me Be prepared for a possible pop quiz Friday Sept 4 which covers the material from Quiz 1 and this assignment Sample code from Sept 4 myMember X L returns true if X occurs in L and false otherwise define myMember X L cond empty L false equal car L X true true myMember X cdr L define foo X L if myMember X L X empty define even n eq modulo n 2 0 define evens L cond empty L empty even car L cons car L evens cdr L true evens cdr L meXp X n returns XAn if n is a nonnegative integer define mexp X n if eq n 01 X mexp X n 1 tail call optimization last call optimization define mexp2 X n meXp3 X n 0 1 define meXp3 X n c a if eq c n a meXp3 X n c 1 X a define meXp4 X n c a if lt c n meXp4 X n c 1 X a a Homework for Wednesday Sept 9 Write write the following functions in Dr Scheme with the language set to intermediate student If you have any question about how the function is supposed to behave do not hesitate to email me In any of these exercises write any helper functions you need that is it may take more than one function to get the job done Be prepared for a quiz over this assignment and the reading on the history of programming languages on Wednesday Sept 9 1 primes L if L is a list of integers primes L returns only the primes in L A number is prime if it is greater than 1 and has no factors strictly between 1 and itself For example primes list 4 8 5 3 11 16 returns list 5 3 11 First write a function prime X to test individual numbers for primality Then write a version of primes which uses 39filter39 see the docs for Dr Scheme and a recursive version which does not use filter example of filter filter positive list 2 9 3 4 returns list 9 3 2 facs L If L is a list of nonnegative integers facs L returns a list of the respective factorials of the members of L For example facs list 1 2 3 returns list 1 2 6 Write a version that is not recursive and uses 39map39 see the Dr scheme docs and a version that is recursive and does not use map example of map map add1 list 1 2 3 returns list 2 3 4 3 range m n if mgtn returns the empty list othenNise returns list m m1n For example range 3 6 returns list 3 4 5 6 4 nth n L if L is a list and n is an integer between 1 and the length of L inclusive nth n L returns the n39th member of L For example nth 2 list 10 20 30 returns 20 There may be a built in function to do this but if so it cannot be used in this problem 5 contains3 L returns true if 3 is a member of L and false otherwise For example contains3 list 1 2 returns false while contains3 list 3 4 returns true Code from Sept 9 define range m n if gt m n empty cons m range m 1 n define for L op x0 if empty L x0 op car L for cdr L op x0 define fac n for range 1 n Homework for Sept 11 6 deep3 L returns true if 3 is a member of L a member of a member of L a member of a member of a member of L etc For example deep3 list 1 2 list 1 2 3 returns true Your function should find 339s no matter how deeply they are nested 7 factors n If n is a positive integer factors n returns a list of the factors of n in ascending order For example factors 10 returns 1 2 5 0 8 while p fx This exercise illustrates how function names can be passed as arguments in Lisp which requires pointers in C If p is a function which takes one argument and returns a Boolean and f is a function which takes a single argument then while p fx returns the result of applying fto x repeatedly zero or more times until the results fails to satisfy p For example using the prime function you wrote in 1 while prime add1 2 will return 4 since if we add 1 to 2 until the result is not prime we get 4 Similarly while prime add1 10 returns 10 since 10 is not prime 9 Use the 39while39 function you write in 8 to re do your factorial function without using explicit recursion recursion is used implicitly since the 39while39 function is recursive but the factorial itself and none of its helpers besides 39while39 should not be recursive Be prepared for a cumulative quiz on Sept 11 over all of the above problems 1 9 and the reading assignment on history of programming languages Homework for Sept 16 Write each of the following as a C while loop and as a tail recursive Lisp function You may write a C for loop to warm up but it is not required Be prepared for a possible cumulative pop quiz over this and all previous assignments on Wednesday 1 Given integers m and n find the sum of all the numbers which are greater than or equal to m and less than or equal to n 2 Count the number of 239s in a list of integers Your C function should be int countZS int x int 5 where X is the base address of an array of integers and s is the highest index in the array so for example an array of three integers would have highest index 2 Your lisp function should be countZs L which returns the number of 239s in L You can assume all members of L if any are integers though L may be empty 3 Find the greatest common divisor of two nonnegative integers m and n by starting with m and counting downward until you find an integer which is a divisor of both m and n This is a slow method but it is required for this exercise 4 Find the greatest common divisor of two integers m and n by the most fastest algorithm you can find or think of As in the other exercises write your answer both as a while loop in C and a tail recursive loop in Dr Scheme Lisp solution to 1 by Charles Sandman define sum m n sums m n 0 define sums m n if lt m n sums m l n C m C Lisp solution 2 define count2s L count2ss O L define cond empty todo eq true count2ss C todo 0 car todo 2 count2ss C l cdr todo count2ss c Cdr todo Lisp solution 3 by Kyle Tengler define gcdl m n gcdhelper m n m define gcdhelper m n a if and gt a 1 not and equal modulo m a 0 equal modulo n a O gcdhelper m n a 1 an simplified gcdhelper define if and a gcdhelper m n a equal modulo m a Oequal modulo n a O gcdhelper m n a l SequenceL gcdhelper gcdhelpermna a when just to clarify m mod n O and a mod mO else gdchelpermna l Homework for Sept 21 A digit is one of the following o l 2 3 4 5 6 7 8 Note that parentheses cannot be used as symbols in Scheme thus A special character is one of the following five symbols 39 39 39lpar 39rpar 39 The underscore is the following special character 39 A letter is one of the following three symbols 39x 39y 39z A character is a digit special character or letter An identifier is a list of of digits letters and underscores beginning with a letter A numeral is a nonempty list of digits A special token is one of the following four symbols 39 39 39lpar 39rpar A token is an identifier numeral or special token Note that some tokens are lists and some are symbols Now that tokens are defined the behavior of a tokenizer is specified using the maximal munch rule Your assignment is to write a Scheme function maxmunch which is a helper to the following tokenizing function tokens s returns a list of tokens obtained from s using the maximal munch rule define tokens s cond empty 8 empty eq maxmunch s 39error 39error true cons first maxmunch s tokens second maxmunch s FOFeXanlmetokens list 3 4 39 39lpar 39X 39x 39y 39rpar shouklreturn list list 3 4 39 39lpar list 39x 39x 39y 39rparL Basicalymaxmunch s returns a two item list the first of which is the longest token that can be taken from the front of s and the second of which is the remainder of s after removing this token There will be a quiz Monday Sept 21 The first question on the quiz will be to write maxmunch This question will count half of the quiz The remaining questions will be based on the assignments on tail recursion If you have any question about the problem specification feel free to email me For testing your code it may help to know that for example 39 3 4 lpar x x y rpar is shorthand in Dr Scheme for list 3 4 39 39lpar 39x 39x 39y 39rpar Note Even with a correct maxmunch helper the above tokens function will give a runtime error if it encounters an invalid character that is something that is not a letter or special character after it finishes the first token The below version fixes this problem define tokens s cond empty 8 empty eq maxmunch s 39error list 39error true cons first maxmunch s tokens second maxmunch s Here is some test data with correct outputs the old version of tokens crashes on the second example gt tokens 39x y 2 l lpar x O O 2 l rpar 4 list list 39x 39 list 39y 2 l 39 39lpar list 39x O O 39 2 l 39rpar 39 list 4 gt tokens 39x y 2 l lpar x O O 21 rpar 4 list list 39x 39 list 39y 2 l 39 39lpar list 39x O O 39 39error Code from class Sept 30 parentkimben parentjackreese parentjudyreese malereese malezack malejack maleben femaleX maleX Closed world assumption fatherXY parentXY maleX motherXY parentXY femaleX full brotherXY fatherZX father motherZ2X mother Y xy maleX grandparentXY parentXZparentZY grandfatherXY grandparentXY maleX greatGrandParentXYz parentXZ grandparentZY cousinXY grandparentZX grandparentZY commonParentXY commonParentXY parentZX parentZY ancestorXY parentXY ancestorXY ancestorZY parentXZ Homework for Oct 2 There won39t be a quiz on Oct 2 but you should do these exercises to prepare for class Download and install the interpreter for SW1 Prolog 1 For what kinds queries if any does the above version of ancestor work For what kinds of queries if any does it fail If it does not work for all queries fix it so it works for all queries 2 write sisterXY X is a sister on 3 write grandson x Y X is a grandson on 4 write secondicousin x y X is a second cousin on google it to make sure you know what second cousins are 5 write has child togetherXY X and Y are the mother and father in no particular order of a child 6 write blood uncle xy X is an uncle of Y related by blood doesn39t include the husband ofan aunt unless he also happens to be a blood uncle Example factorialNY NO Yl NgtO K is N l factorialKZ Y is NZ This is a comment This is also a comment o 6 Another way to do factorial would be facOl facNY NgtO K is N l facKZ Y is NZ Homework for Oct 5 Write the following in Prolog 1 expXNY Y is XAN for any number X and integer N 2 sumrangeMNS S is the sum of all integers between M and N inclusive For example sumrange34Y yields Y7 sumrange108Y results in Y27 and sum range55Y results in Y5 Be prepared for a quiz on Monday covering the Prolog assignments for Oct 2 and Oct 5 Code from class Oct 5 For Wednesday Oct 7 Read Beating the Averages and The 18 Mistakes that Kill Startups by Paul Graham The first person to notify me by email to my gmail account of any error or typo in the notes from this point forward gets 1 point of extra credit added to a quiz or test grade of their choice Code from Monday39s class exp Ol expXNR NgtO NN is N l expXNNRl R is R1X expXNR NltO c is N expXCRl R is lRl srangeMNR NgtM M2 is M1 srangeM2NS R is SM srangeMMM srange MNR NltM srange NMR sumLX means X is the sum of the members of list L sum 0 sumHlTX sumTXl X is X1H productl productHlTXz productTXl X is X1H count3s0 count3s3lTN l count3sTNl N is Nll count3s lTN count3sTN genMN MgtN genMN MlR NgtM M2 is Ml genM2NR fac NR genlNX productXR Write the following in Prolog 1 myengthLN output N is the length of input list L There is a built in length predicate but it cannot be used in this problem 2 factorialsL1L2 if L1 is a list of nonnegative integers L2 is the list of respective factorials For example factorials123X results in X126 3 expsL1L2 if L1 is a list of pairs XN where X is a number and N an integer L2 returns a list of the respective XAN39s For example exps21210X results in X21024 4 A numeral is a list of digits A letter is 39x39 39y39 or 39z39 and an identifier is a list of letters and digits beginning with a letter A special token is 393939 39 3939 or 3939 A token is a numeral identifier or special token Write tokenL which succeed if L is a token For example token123 and tokenxyz5 should return true at least once while token3x should not return true There will be a quiz on Wednesday over all the Prolog exercises plus the two essays by Paul Graham Code from class Oct 7 nameX memberXfidofelixjohn nounX memberXcupcatrefrigerator quantifierxz memberxatheeverysome thX memberXchasedcaughtslappedj sentencexz appendABX nounPhraseAVeerhraseB nounPhraseX nameX nounPhraseXYz quantifierXnounY veerhraseHlTz vtpHnounPhraseT Homework for Oct 9 Extend the code above to handle one or more of the following prepositional phrases eg thecatinthehatchasedacup adjectives eg john slapped the hot cat conjunctions eg john chased felix and slapped fidojohnandfidochasedeverycup andor fidochasedfelixandfelixchasedthecup pronouns eg shecaughthim and fidoslappedher but not himcaughtshe intransitive verbs eg bob sang verbs of two different tenses with conjunctions eg bob sang and chased fido but not bob sings and chased fido 7 Anything else you like WNH 0 5 I will take volunteers on Friday to demo their Prolog grammar checkers If you come up with something you39d like to demonstrate you may email it to yourself so that you won39t have to type it in class Extra credit Write a C program which reads multiple strings of characters from a file each on a separate numbered line eg l the cat chased the cat 2 fido chased felix 3 chased chased chased and outputs a sequence of yes39s and no39s on numbered lines according to whether the corresponding input line is a correct sentence in grammar given in class Wednesday Oct 7 For example the correct output for the above input file would be 1 yes 2 yes 3 no Your program cannot contain a hard coded list of sentences generated by the grammar but other than that you may use any algorithm you like if you have a question about whether a given approach is disallowed under this rule ask If your program handles all test cases correctly then your lowest quiz grade will be replaced with a 55 More detailed instructions will be given by Friday This assignment will be due Oct 30 Further instructions The input file will consist of consecutively numbered lines starting with the number 1 Each line will consist of a number followed by a 3939 followed by one or more words each preceded by a space followed by a return The return after the last line will be followed immediately by an end of file The extra credit programs must be written in C using MS Visual Studio available on the PCs in the CS labs PE 118 and PE 119 Zip the project file so that when it is unpacked it creates a directory with your name The input file for the test cases is one directory above this directory The file is named quottestcasestxtquot Make sure that your program will run by just running the project file Homework for Oct 14 Extend your grammar checker to include correct use of the following words song of in big beautiful and or he she him her it slept and sang Assume slept may be used only as an intransitive verb but sang may be used as either a transitive or intransitive verb Transitive occurrence of sang would be as in quotshe sang the National Anthemquot or in our lexicon quotshe sang a songquot Try to get your parser to reject bona fide English syntax errors such as him sang the the but not type errors awkward sentences or semantic errors That is for example it should accept the dog and every cup sang the big big cat of a refrigerator in her Note that there will be infinitely many sentences generated by your grammar so the idea is for the software to correctly identify a list of words as either a correct sentence or not not to generate a list of all possible sentencesname x member x fido felixjohn Homework for Oct 16 Read the notes on fluents and propositions Do exercises 11 and as many of 12 as you can I will go over exercises 11 and 12 carefully in class Friday Be prepared to turn in exercises 11 and 12 on Friday though not for a grade Homework for Oct 19 Do the exercises here I will take questions on these Monday for around 10 minutes and then we will have a quiz The quiz questions will be of the form quottell whether the following triple is valid and if not give a counterexamplequot Project Due Nov 4 You should get started now on this as soon as possible There is a discussion board here for posting and discussing data generated by your program Code from Nov 4 appendHlTR appendHXR appendTX appendm ii expLLO numberL expLLO atomL expLTlT22 L is an expression with tree TlT2 and order 2 if appendABL L is the concatenation of A and B expATlM A is an expression with tree T1 and order M expBT2N B is an expression with tree T2 and order N Mlt2 Mlt2 and Nlt2 Nlt2 expLTlT2l L is an expression with tree TlT2 and order 1 appendABL L is the concatenation of A and B expATlM A is an expression with tree T1 and order M expBT2N B is an expression with tree T2 and order N Mltl Mltl and Nltl Nltl expLTO K is an expression with tree T and order 0 if stripParensLL2 L2 is L with initial and final parentheses removed and expL2T L2 is an expression with tree T of any order expLFunArgO appendF3939LTli39WJLL prefixFFun expTArg expLFunArgO append F prefixFFu quotSt3939L n stackStArg expLlambdaVE3z appendlambdaVarsExpL vasVarsV expExpEN N lt 3 vasi vasHlTHlT atomH vasTT stackLstackAABBz appendA3939BL expAAA expBBB stackLstackAAlBBz appendA3939BL expAAA stackBstacleB prefixXX memberXfgh prefixXlambdaVEz expXlambdaVE stripParensLResultz Li39lt39lResti reverseRest3939lRBody reverseRBodyResult evalEV means tree E evaluates to value V evalMM numberM evalABV evalAVl evalBV2 V is V1V2 evalABV evalAVl evalBV2 V is V1V2 Homework for Nov9 1 Add to the above code so that it can parse and evaluate the arithmetic operations written using and A has the same precedence and associativity as is division of Prolog numbers which is similar to floating point division A is exponentiation It has higher precedence than and associates right to left as opposed to the other binary infix arithmetic operations which associate left to rig ht 2 If you would like a challenge augment the code so that it evaluates lambda expressions If you can do this you are a already a pretty good Prolog programmer There will be a quiz Monday covering question 1 of this assignment Be prepared to write a grammar not Prolog code for arithmetic expressions written using A and parentheses with their usual association and precedence Be prepared to write Prolog code to evaluate the parsed expressions as in the last two clauses of the example code from class Tokenizer code classification of ascii codes letterC 97ltC Clt 123 65ltC Clt90 digitC 48ltC Clt57 specialC memberCquotlAampltgt quot whiteSpaceC memberC9lOlllZl332 acceptSCSZ in state S character C can be added to the token in progress resulting in new state 32 o0 acceptemptyCatom letterC acceptemptyCnumber digitC acceptemptyCspecial specialC acceptemptyCparen memberCquotquot acceptemptyCcomma Cquotquot acceptatomCatom letterC digitC Cquot7quot acceptnumberCnumber digitC acceptspecialCspecialz specialC validTokenState token in progress is a complete token validTokenState memberStateatomnumberspecialparencomma charsToTokenStateStackToken Token is the token obtained o0 o0 from the ascii characters TokInProgress in the appropriate State charsToTokenStateToklnProgressToken reverseToklnProgressRevStackL Statenumber gt number charsTokenRevStack atom charsTokenRevStack Tokenizing algorithm starts here oo Tail recursive automaton for tokenizing Input list is 4th argument tokenizeToksSoFarTokInProgressStateResult validTokenStatel token in progress is valid charsToTokenStateToklnProgressToken reverseToken ToksSoFarResult Happy Ending reverse error ToksSoFar Result tokenizeToksSoFarToklnProgressStateClRestResult Stateempty state is empty and whiteSpaceCl next char is White space tokenizeToksSoFarToklnProgressStateRestResult o0 o0 acceptStateCNewStatel token in progress accepts next char tokenizeToksSoFarClToklnProgressNeWStateRestResult validTokenState l token in progress is valid charsToTokenStateToklnProgressToken tokenizeTokeanoksSoFaremptyClRestResult o reverseerrorlToksSoFarResult 6 none of above 0 6 generate a list of Tokens from an Input list of ascii codes tokenizelnputTokens tokenizeemptylnputTokens Homework for Nov 11 Feel free to email me if you have any questions about what is being asked for in any of these questions 1 Modify the above tokenizer so that it accepts numeric tokens consisting of either or more digits or 1 or more digits followed by 3939 followed by 1 or more digits 2 Modify it also so that the only specialtokens it accepts are 1 z t A lt gt lt gt and 3 Write a grammar for Prolog lists written using only numbers identifiers commas and brackets You may use the symbols 39number39 and 39identifier39 as terminal symbols in your grammar For example the following are Prolog lists quotquot quot44 fooquot quot4333quot 4 Modify the evaluator so that it will evaluate parsed lambda expressions 5 challenge for those who have had or are taking automata theory As exercise 1 shows the tokenize predicates are reusable for other token sets by modifiying accept validToken and possibly charsToToken However the tokenize predicates are not reusable for every conceivable token set Give a token set for which above tokenizing algorithm consisting of the part of the code after quot Tokenizing algorithm starts herequot will not work no matter how clever we are in writing accept and validToken Homework for Nov 16 This is to refresh your Lisp and Prolog skills 1 Write a Lisp function 39catch39 which takes a list of symbols and returns the length of the longest string of consecutive identical symbols in the list For example catch list 39a 39b 39b 39c returns 2 while catch empty returns 0 2 Write 2 in Prolog catcha b b c N should result in N2 while catchN results in NO 3 Implement mergesort in Lisp for lists of integers 4 Implement mergesort in Prolog for lists of integers 5 Write a lisp function which accepts a list of symbols and returns true if the list is a palindrome and nil otherwise The function cannot use non tail recursion and nor can any of its helpers Homework for Nov 18 I have created a link to source code for an Easel interpreter The interpreter runs under SWI Prolog Here is a sample Easel program Here is a sample session following a double click of the interpreter Install SWI Prolog and make it the default program for opening pl files Save the interpreter source code as a pl file Save the Easel program as a file using any file name you like For example you might call it sampleProg ramtxt Save it in the same directory as the interpreter Double click the interpreter This loads the inerpreter and opens SWI Prolog In SWI Prolog after the prompt enter the query quotconsult39sampleProgramtxt39quot without the quotes and hit return Use an appropriate filename must in single quotes enter queries using either tr or ev If you were in class on Nov 16 and still have questions about how to enter queries to the Easel program feel free to email me U39Ilgt WNH 0 For homework for Nov 18 write the following functions in Easel 1 sum for integers M and N sumMN returns the sum of all integers k such that MltKltN 2 sumPrimes for a set S of integers sumPrimesS returns the sum of all the prime numbers which are members of S 3 subset for sets S and T subsetST is true if S is a subset of or equal to T and false otherwise For Nov 20 4 cross for sets S and T crossST returns the cross product of S and T If ngt0 an array ofsize n is a set of ordered pairs such that if Xy is a member of S then X is an integer and 1ltXltn if 1ltXltn then there is a unique y such that Xy is a member of S If A is an array of size n and 1ltiltn and iy is a member of A then y is called the i th member of A 5 makeArrayFN for a function F and nonnegative integer N makeArrayFN returns the set 1F1 2F2NFN 6 append appends arrays For example append1102201a2b 1102203a4b Write the following in Easel using only tail recursion Write an invariant for each tail recursive function you write that is typically for the helper function 7 rewrite Exercises 1 and 2 sum and sumPrimes to be tail recursive supply an invariant for each 8 countEvens If S is a set of integers countEvensS returns the number of even integers in S 9 euclidchMN if mgtngt0 euclidchMN returns the gcd of M and N computed using the Euclidean algorithm 10 addFactorsMIJ For nonnegative integers M I and J add FactorsMIJ returns the sum of all the factors of I which are greater than or equal to M and less than or equal to J 11 countPerfectIJ returns the number of perfect numbers which are greater than I and less than J 12 What is the difference between eager and lazy evaluation Does Haskell use eager or lazy evaluation Does Lisp use eager or lazy evaluation Who is Haskell named after When was Haskell invented At what university was Mercury invented Is there a Mercury compiler or are there only interpreters What is the difference between static and dynamic typing Which of the following languages are statically typed which are dynamically typed which are untyped C Haskell Lisp Prolog Mercury N H H H H H H H Okom lU39lbbd There will be a quiz on Friday over the homework for Nov 18 and 20 Here are some hints on problems 12 20 A language is typed it has more than one sort of term and these sorts are distinguished by the compiler or interpreter NOT by code written by the programmer and used for operator overloading or error detection Static typing is deployed at compile time dynamic typing at runtime Object oriented languages may use some static typing but they also use dynamic typing in case of polymorphism so the answer for C is quotbothquot If you have questions about exercises 12 20 which are not answered in your notes or by Wikipedia feel free to email me Notes for the weekend 0 6 for integers I and J countIJ simply returns the number of integers o 6 which are greater than or equal to l and less than or equal to J countlJ 0 when lgtJ countHelperlJl otherwise countHelperCJA n CJ countHelperClJAl otherwise 0 6 invariant lltCltJ and Ais the number of integers K such that IltKltC addFactorsMlJ 0 when lgtJ addHelperMlJl when lltJ amp M mod 10 addHelperMlJO otherwise addHelperMCJA A when CJ addHelperMClJACl when M mod 01 O addHelperMClJA otherwise otherwise invariant lltCltJ and A is the sum of the factors of M between I and C inclusive oo perfectN if addFactorsNlN lN countPerfectlJ 0 when lgtJ l countPerfllJ ll when IltJ l amp perfectll countPerfllJ l0 otherwise countPerfCDA A when CD countPerfClDAl when CltD amp perfectClL countPerfClDA otherwise invariant lltCltJ and A is the number of perfect numbers between I and C inclusive oo Homework for Monday Carefully study last week39s homework and the solutions above and be prepared with questions about them on Monday In addition do the following problem using tail recursion and write invariants for all the tail recursive helper functions you write 1 minFactorsMN returns the minimum number of factors of any number which is less than or equal to N and greater than or equal to M For example minFactors410 returns 2 because 7 has only 2 factors and is between 4 and 10 minFactors810 returns 3 since 9 has three factors Final project The final project is to design a new programming language To do this you will Tell what is interesting or useful about your language 1 paragraph Tell whether your language is procedural logical or functional and tell whether your language is dynamically typed statically typed or untyped or a hybrid Describe the token set of your language using a finite state automaton Describe the grammar of your language using a BNF grammar Describe in English the semantics of each construct of your language ie how it evaluates Give two pages of well documented sample code solving several problems or one big problem Each bulleted item above counts 5 points credit equal to a quiz For extra credit you may do one of the following but not both for an additional 5 points Implement your language in Prolog or any language of your choice Give the procedural semantics of your language using an abstract state machine This project is due in class on Dec 9 and counts 30 of your grade You can submit a draft to me by email at any time and I will let you know what the grade would be for the draft and what to work on to improve it You may resubmit as many times as you like to refine your project but the final draft is due Dec 9 Homework for Monday Nov 30 Write the following tail recursively in Easel with an invariant for each recursive helper 1 primeN rewrite prime using tail recursion and without using comprehension some or all 2 coprimeNM numbers are coprime if their GCD is 1 For thisjust call euclidGCD problem 9 above 3 countCoPrimesMIJ returns the number of integers which are less than J greater than I and coprime with M First write this using set comprehension and then using tail recursion Notes for Dec 7 Consider the following function definition precondition NgtO postcondition factorialN Nl factorialN factorial helperOlN factorialghelperIANz A when IN factorialihelper1lA11N otherwise invariant Oltllt Nl and All quototherwisequot is just read as a shorthand for the conjunction of the negations of all preceding guard conditions In this case quototherwisequot means notigtn The proof steps for this documented code are 1 if NgtO then OltOltN and 10l 2 if OltlltN and All and IN then ANl 3 if OltlltN and All and notlN then OltIlltN and AIlll Note there is one proof step for the initial call to the recursive function one proof step for the base case of recursion and one proof step for the recursive call If there were two recursive recursive cases there would be an additional proof step The proof step for the initial call is if ltpreconditiongt n ltinvariant with initial values substitutedgt The proof step for the base case is if ltinvariantgt and ltbase case guard conditiongt then ltpostcondition with returned expression substituted for function callgt The proof step for each recursive call is if ltinvariantgt and ltrecursive call conditionsgt then ltinvariant with arguments of recursive call substituted for corresponding arguments of the original callgt Note that if you have two different cases of recursive calls there will be a total of 4 proof steps On Friday I left out the proof steps for the initial call so be sure to put them in before you turn in your quiz The first two problems from take home quiz from the weekend is due at the end of class on Dec 7 together with Problem 3 below You may work on it in groups during class that day At the end of class turn in code invariant and proof steps for problems 1 and 2 from the quiz together with Problem 3 precondition IltJ pOStconditionisumUJ returns the sum of the integers in the closed interval 1J sumIJ sumIIJ sumCAJ A when CJ sumCl ACl J otherwise Write an invariant and proof steps for sum Note You will know your invariant is correct if your proof steps are true for all possible values of the variables in them

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.