425 Final PDF

425 Final Study online at https://quizlet.com/_g3dp2w 1. Logic Program- Collection of facts and rules ming do not state exactly how a result is to be computed. declar- ative semantics use predicate calcul...

425 Final Study online at https://quizlet.com/_g3dp2w 1. Logic Program- Collection of facts and rules ming do not state exactly how a result is to be computed. declar- ative semantics use predicate calculus as their foundation. provides the representation and resolution provides the inferencing technique. 2. Declarative lan- Difference is how you express instructions for a computer guages vs. Im- to execute tasks. perative Lan- guges 3. Imperative Lan- Manipulating the state of a machine and you're specifying guages the order of instructions to make that happen. Manipulat- ing how variables change, how you store data in and out of memory. Focus on how a task should be performed. Specify step-by-step instructions to achieve the desired result. Use control structures like loops, conditionals, and explicit state changes. C, Java, Python, JavaScript 4. Declarative Se- The meaning of a program in terms of what it computes mantics or represents, without considering how it computes it. It focuses on the logical relationships between input and outputs, abstracting away from the computational steps or algorithms. Prolog: A program specifies facts and rules, and the se- mantics is based on what is logically entailed 5. Declarative Lanu- Focus on what result you want, without specifying how to gaes achieve it. Implicitly handled by the system. Abstract away control flow and state management. Often associated with immutability and functional programming. Rely on under- lying implementations to determine the process. HTML, Prolog 6. Predicate Calcu- Formal logic statements use symbols to represent con- lus stants and variables. Constant: Represents a fixed object 1/9  425 Final Study online at https://quizlet.com/_g3dp2w Variable: Represents different objects at different times. Formal logic combines symbols to create propositions. 7. Proposition a declarative statement that is either true or false, but not both. 8. Atomic proposi- simplest logical form tions consist of relations, often representing facts statement of a fact examples: csmajor(jake) like(bob, steak) There is no inherent meaning to the order of the atoms. bob likes steak? steak likes bob? bob is like a steak? 9. Compound form meaning from 2 or more atomic propositions. propositions Negation, Conjunction, Disjunction, Equivalence, Implica- tion 10. Quantifiers all, no, some, many 11. Horn Clauses restricted form of propositions: 1. Single atomic proposition on the left side of a proposition or 2. an empty left side (headless horn clause = fact) mammal(M) :- cat(M) A collection of literals and negative literals 12. Resolution Combining two clauses containing complementary literals Eliminating those literals to produce a new clause Repeating this process to derive conclusions or contradic- tions. (A U B) and (notA U C) The Resolvent: (B U C) 13. Prolog. Atom Basic building blocks of the language. It represents a sym- bolic constant or name that cannot be subdivided further. Used to represent constant, relations, or functors 14. Prolog. constant atom (symbolic value) or integer 2/9  425 Final Study online at https://quizlet.com/_g3dp2w 15. Prolog. term a constant, variable, or structure 16. Prolog. variable Begins with uppercase letter not bound to types by any declaration binding to values takes place during resolution these bindings are called instantiations and may be tem- porary. Being used in a quantative way. Try to find rational for the proof. 17. Prolog program consists of collection of first-order logic state- ments 18. Hypothesis An assumption, statement, or proposition made as a basis for reasoning, testing, or investigation. 19. Prolog Goals query in prolog resolution in theorem proving binds values to variables to prove the goal. ?- cat(frisky). true/false 20. Prolog Rules Used to define new predicates using those already defined by Prolog facts. 21. Prolog Facts define predicates by specifying the elements that satisfy these predicates 22. Inferencing for example, if Q is the goal, then either Q is a fact, or inferencing must find a sequence of facts and rules that lead to Q "All humans are mortal." and "Socrates is a human." Con- clusion: "Socrates is mortal" or "The sun has risen every day in the past." Conclusion: The sun will rise tomorrow." 23. Prolog Unifica- tion 3/9  425 Final Study online at https://quizlet.com/_g3dp2w When prolog rules contain variables. attempts to bind values to variables that support the proof of the goal. 24. Depth first find all support for the first clause before moving on to the next 25. Breadth search uses backtracking, ie- find one value then move to next clause, and back track as needed. 26. Forward chain- inference starts with known facts and applies rules to ing derive new facts until a goal is reached or no more rules can be applied. Data-driven approach, as reasoning begins with the avail- able data and progresses towards conclusions. 27. Backward Chain- The process of working with the clauses of a rule and ing trying to prove each one is called top-down resolution You start with the goal(the top of the rule hierarchy) and work towards the facts. 28. Functional Pro- Based on mathematical functions gramming Is the design basis for most non-imperative styles of lan- guages. - Unlike imperative languages, this paradigm does not support the concept of a state. Eliminate side effects, by eliminating variables the pro- gram can manipulate 29. Mathematic func- a mapping of one set (domain) to another set (range) tions Can have no side effects Mapping an element in the domain always results in the same element in the range. There is no concept of changing a variable value. 30. Simple Func- Often written as a function named, followed by a list of tions parameters, followed by the mapping expression. Unnamed mathematical function definitions are called lambda expressions. 4/9  425 Final Study online at https://quizlet.com/_g3dp2w 31. Higher-order takes functions as parameters or yields a function as its function or result, or both Functional form Composition: f(g(x)) 32. Mapping func- apply all tion b(x) = x*3 b(3,4,5) = (9,12,15) 33. Fundamentals of The objective of functional language design is to mimic functional lan- mathematical functions to the greatest possible extent guages Therefor, solving problems becomes a composition of functions rather than imperative commands Example: Condition evaluated loop, you use recursion for repetition The compiler handles the storage of intermediate values needed in computation instead of the programmer creat- ing variables The execution of a function always produces the *same* result when give the same parameters. - set of primitive functions - used to construct complex functions from existing func- tions - some structure(s) for representing data 34. referential trans- an expression's ability to be replaced with its value with- parency out changing the program's behavior. If an expression is referentially transparent, it means that the expression can always be substituted with its result without affecting the program's correctness. An expression can be replaced by it's result anywhere in a program the result is predictable and always the same for the same inputs There are no side effects. The evaluation depends only on the inputs and produces the same output every time. 35. Lisp: Atom numeric or symbolic. 10 or a 36. Lisp: Lists 5/9  425 Final Study online at https://quizlet.com/_g3dp2w simple _ contains only atoms as elements Neste _ contain _ as elements Stored as linked structures 37. List Functions: '(a b c) Quote(a b c) (a b c) would be function a with parameters b and c. But if you want it to be a list, then you need to quote it 38. List Functions: First element of a list car '(a b c) Only used on a list 39. List Functions: list of everything but the first value. cdr('a b c) 40. List Functions: '(a b c) Adds the first element to the list cons 'a '(b c) 41. List Functions: (a b c d) append '(a b) '(d Merges two lists c) 42. List Functions: (a b c) list 'a 'b 'c Takes the elements and builds a list out of them 43. lazy vs. strict Strict- all parameters are evaluated. Time consuming. evaluation Can't do an infinite list Lazy- only evaluates when/if their values are needed. Im- prove efficiency. 44. Abstraction a representation of an entity that includes only the most significant attributes 45. Process Abstrac- Subprograms tion allows a program to specify a task while its details are hidden. 46. Data Abstraction Modern programming languages allows us to define and collect instances of like entities into group based on common attributes 6/9  425 Final Study online at https://quizlet.com/_g3dp2w 47. Abstract Data encloses a data representation and provides subprograms Type (ADT) that represent operations on that type Queue, how we store it. operations on a stack, push, pop. float. Which bit is exponent, mantissa, how many bits. Operations (addition, multiplication) 48. Information Hid- The internal representation of the data type are hidden ing from program units using the type (private, etc) Using a stack doesn't mean I need to know how it's imple- mented Increase Reliability: localize changes to code within an object. Only have to change your values in a stack, not the stack. Localize testing. Reduces the complexity of the code to the programmer. Avoid conflict of similar names. Interfaces hide re-implementation. Behind the scenes. Promote re-use. If its a general process, we can use it for a lot of problems. stacks, queues, trees. 49. Encapsulation The declaration of the type and its operations (interface) are combined into a single syntactic unit (package, mod- ule, class) Reliability. Not touching the code. 50. Inheritance Allows us to take an existing data type and add to it or modify it without having to change the original. Any updates to the original changes this inherited version. An ADT can inherit (extend) the data and functionaity of some existing type. Re-use is facilitated Reliability is maintained 51. How Inheritance - Extending (reuse) supports Object - modifying. adding new methods. Overriding existing Oriented Pro- ones. gramming Class-level membership. Shared by all instances of the class. 52. 7/9  425 Final Study online at https://quizlet.com/_g3dp2w Single Inheri- Any entity in your inheritance chain only extends or inherits tance from one class 1 direct superclass 53. Multiple Inheri- More than one direct parent class. tance Complicated They could inherit the same values from two different par- ent objects that inherit the same thing from the superclass. They could inherit the same variable name from two differ- ent parent classes. Programmers are tempted to overuse and combine things that aren't related. Makes the system brittle or difficult to change 54. Generaliza- The further down you go in the inheritance, the more tion/Specializa- specialized the object becomes. tion 55. Terms to de- Base/derived, Parent/child, superclass/subclass scribe inheri- tance 56. Polymorphism dynamic binding of a behavior to an object Dynamic- runtime decision based on object type example: Shape superclass with subclass function draw. Foreach Shape, draw(). Then it has to decide which draw function the superclass is talking about. Interfacing languages can also have this. 57. Design Issues for 1. Exclusivity of objects. Is your language purely object OO languages oriented? Is everything an object? 2. Are subclasses treated as subtypes for type coerscion? Can a language convert subtype to the parent type, when needed, automatically? 3. Single vs multiple inheritance? 4. Allocating instances. Where are objects allocated when created? How are they managed? references on the heap and managed for us. Constructer/destructor features? 5. nest the declaration of class within other classes? 8/9  425 Final Study online at https://quizlet.com/_g3dp2w 58. What makes a - information hiding + encapsulation (ADT, object) language Object - Inheritance (Single and Multiple) Oriented? - Polymorphism 9/9