Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Symbolic Programming Midterm > Midterm 1 Definitions > Flashcards

Midterm 1 Definitions Flashcards

1
Q

abstract syntax tree (AST)

A

A tree representation of a program that is abstracted from the details of a particular programming language and its surface syntax.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

association list

A

in Lisp, a list composed of pairs of a symbolic name and associated value, used to represent variable bindings, substitutions, and data sets.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

atom

A
  1. in propositional or predicate calculus, a predicate symbol with the appropriate number of arguments. For example, MORTAL(Socrates) is an atom, where MORTAL is the predicate and Socrates is a constant term that is its argument. Also, atomic formula.
  2. in Lisp, data that is not a cons cell, such as a symbol or a number.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

backchaining

A

a proof that starts with the conclusion and searches for facts or rules that support the conclusions, recursively.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

backtrack

A

in a tree search, to move back from the node currently being examined to its parent.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

base case

A

A simple case that can be solved easily, without recursion.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

binary tree

A

A tree in which each node has at most two children.

Contents and left and right links.

Node = cons, binary links = first and rest.

E.g. arithmetic expressions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

binary search tree (BST)

A

A binary tree in which all elements less than the current element are to its left and all elements greater are to its right.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

binding

A

an association of a name with a value.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

box

A

in logic or resolution theorem proving, the empty clause; from its mathematical symbol, &box;

False, contradiction, empty.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

branching factor

A

in a search tree, the number of children of a given node. Usually, the branching factors of individual nodes will vary.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

combinatoric explosion

A

the rapid growth of the number of possibilities to be explored in a search, often exponential because it is the product of the number of possible choices at each level of the search tree.

The rapid growth of combinations of possible moves.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

combine

A

an operator that is used to combine elements in an accumulation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

conjunctive normal form (CNF)

A

a canonical form of writing predicate calculus formulas as a conjunction (AND) of clauses (disjunction (OR) of literals); used in resolution theorem proving.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

consistent

A

of a logical formula, having some interpretation that makes it true.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

constant folding

A

performing at compile time an operation whose operands are constant, giving a new constant result.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

constructive

A

proving that a formula is consistent by constructing an element that makes it true.

Constructive proof: given a theorem ∀x∃y P(x, y), prove it by constructing a y that satisfies the theorem.

During program synthesis, witnesses are constructed for existential terms. The witnesses correspond to subroutines in the SPICE library (concrete terms).

specification → theorem → proof → program

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

decidable

A

of a theorem proving or decision making task, able to be decided one way or the other (e.g., proved or disproved) within a finite time bound that can be determined from the size of the input problem. cf. undecidable.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

depth

A

depth of a tree in number of links below the root.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

depth-first search (DFS)

A

a search in which children of a node are considered (recursively) before siblings are considered

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

design pattern

A

a pattern that describes a set of similar programs.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

destructive

A

describes a function that modifies its arguments.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

eval

A

Lisp / Clojure function that evaluates an expression.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

exists

A

the logical quantifier ∃, pronounced “there exists” or “for some”.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

fixpoint

A

a value of a function where f(x) = x, i.e. applying a function such as optimization to an expression no longer can do any more.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

for all

A

the logical quantifier ∀, describing something that is true for all possible values of the quantified variable.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

functional program

A

a program in which all computation is performed by functions and there are no side-effects.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

homoiconic

A

describes a language such as Lisp where programs and data are the same.

29
Q

Horn clause

A

a logical formula that is a disjunction (OR) of literals and has at most one positive literal. Viewed as a rule, a Horn clause is a rule from a conjunction (AND) of positive literals to a single positive conclusion literal, e.g. A ∧ B ∧ C → D

Clauses that have at most one positive literal when written in Conjunctive Normal Form as a disjunction of literals.. Assumed by backward chaining.

A ∧ B → C
(A ∧ B) → C
¬(A ∧ B) ∨ C
¬A ∨ ¬B ∨ C

30
Q

identity element

A

for a given operation, an element that leaves the value unchanged. E.g., for + the identity element is 0.

31
Q

immutable

A

a data structure whose value cannot be changed once it is created.

32
Q

inconsistent

A

a logical formula that is contradictory or unsatisfiable

33
Q

inference

A

derivation of additional true statements from a given set of true statements.

34
Q

interpretation

A

an assignment of values to variables in a logical statement

35
Q

in-line

A

to expand a function as code at the point of call

36
Q

interior node

A

a node of a tree that has children

37
Q

interpreter

A

a program that reads an instruction, determines its meaning, and executes it. Lisp has an interpreter (eval) that can execute code constructed at runtime.

38
Q

invalid

A

not valid, i.e. not always true or possibly false

Not true under every possible interpretation: P.

39
Q

leaf

A

a bottom node of a tree

40
Q

linked list

A

a linear data structure where records are linked by pointers

41
Q

literal

A

a logical predicate or its negation: P or ¬P

42
Q

loop unrolling

A

converting a loop into straight-line code by repeating the code inside the loop while substituting successive values of the loop index

43
Q

macro

A

a short amount of code that expands into a large amount of in-line code.

44
Q

operand

A

a value on which an operator acts

45
Q

operator

A

an action such as + that produces new values from given values

46
Q

partial evaluation

A

to evaluate an expression in which some operands are known, e.g. x + 0 ⇒ x

47
Q

predicate

A

in predicate calculus, a symbol that is applied to zero or more arguments and is assigned values of True or False in an interpretation

a function that tests a condition and returns a value of true or false.

48
Q

propositional calculus

A

a logical representation in terms of propositional variables, each of which is true or false and has no arguments.

49
Q

quote

A

a Lisp function that returns its argument, without evaluating it

50
Q

recursion

A

a function that calls itself as a subroutine

51
Q

rewrite rule

A

a rule containing variables that tells how to rewrite a given form of expression as another form

52
Q

root

A

the top element of a tree

53
Q

SAT

A

testing whether a logical formula is satisfiable, i.e. true under some interpretation

54
Q

SAT solver

A

a program that can efficiently find solutions to problems expressed as SAT problems, e.g. WalkSAT and CHAFF.

55
Q

satisfiable

A

consistent, i.e. true for some interpretation.

56
Q

scope

A

the region of program text over which a name can be referenced.

57
Q

search

A

to try sequences of operators to attempt to find a sequence that satisfies a goal.

58
Q

side-effect

A

any effect of a function other than returning a value, such as printing or changing the value of a global variable

59
Q

specialize

A

to make a version of a generic procedure that is specialized for certain data types or constant values.

60
Q

state space search

A

a search for a sequence of operators that will transform a given starting state into some goal state. Each operator transforms a state into a different state.

61
Q

structure sharing

A

a case where two data structures share some elements.

62
Q

symbol

A

a runtime data structure that represents an algebraic or symbolic name

63
Q

tail recursion

A

a function whose value either does not involve a recursive call, or is exactly the value of a recursive call.

64
Q

term

A

in logic, an algebraic variable that represents an object in the application domain. Terms include variables, constants, and functions applied to terms.

65
Q

unsatisfiable

A

of a logical formula, false under every interpretation; inconsistent or contradictory.

66
Q

valid

A

of a logical formula, true under every interpretation.

67
Q

variable capture

A

a problem of a macro including a variable from its call in its generated code

68
Q

variable in pattern

A

a symbol that can be replaced by a corresponding part of the matched input

69
Q

well-founded ordering

A

an ordering that can be guaranteed to terminate, e.g. starting at a positive integer and counting down to 0.

Symbolic Programming Midterm (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions