CSC 244/444, Fall 2023 LISP PROBLEM SET 1 DUE: 5:00 pm, Monday, Oct. 2/23 • Use LOCAL variables within functions (e.g., introduced by 'let') except for truly global parameters (such as a hash table) that multiple functions need to access. • Unless stated otherwise, include type checking in your functions; i.e., if the user gives an argument which is not of the specified type or form of the corresponding parameter, your function should return **ERROR**. (More generally one might print more specific error messages.) PREPARING FOR BUILDING BLOCK STRUCTURES ``````````````````````````````````````` Preamble ```````` The "Blocks World", where an AI system builds structures with children's blocks on a table is a long-standing experimental domain in AI, e.g., going back to Terry Winograd's "SHRDLU" (a name based on letter frequencies) in 1968-71 (e.g., low-res demo, https://www.youtube.com/watch?v=bo4RvYJYOzI). Georgiy Platonov and Ben Kane, in our CSC department, experimented in a physical blocks world, focusing on question answering about spatial relations (e.g., "Which blocks are to the left of a red block?"), as well as about past situations, and enabling structural concept learning, etc. The Blocks World domain is interesting from a reasoning and planning perspective, because it involves precisely the kinds of problems for which current LLMs fail miserably. However, neural-net-based systems specifically designed for virtual Blocks World problems have been built successfully. Once suitable data structures and models of possible moves and relationships in such a virtual domain have been engineered, a DNN can be "let loose", experimenting with millions of moves and configurations, thereby learning what moves lead to what configurations. But one feels that with more reasoning power and spatial conceptualization, success should not depend on such massive experimentation. We will be working towards the ability to create block structures in a 2-D Blocks World, given descriptions of those structures. In Lisp1 we'll do some preliminary programming to enable this. Here is an example of a block structure (call it a "springboard"): _____ _________________ | | | (CUBE A) (CUBE B) | D | H | (CUBE C) (CUBE D) |_____|_________________| (BAR G) (BAR H) | | | | (VERTICAL G) | | | C | (HORIZONTAL H) | | |_____| (ON G *TABLE*) | | | | (ON A *TABLE*) | G | | B | (NEAR A G); "A is one unit to the right | | |_____| of G; valid only for blocks on *TABLE* | | | | (ON B A) | | | A | (ON C B), *TABLE*____|_____|_____|_____|_______(ON H C); This is "symmetrical"-ON For now, assume that we have exactly 6 unit "cubes", {A, B, C, D, E, F} and 2 "bars" {G, H} of length 3. Our eventual aim (not yet in this assignment!) will be to specify how structures like the one above can be built step by step, one block at a time. For the example this might be: 1. (TURN-VERTICAL G); applicable to horizontal bars 2. (PUT-ON G *TABLE*) 3. (PUT-NEAR A G); Assume this means "put A on *TABLE*, 1 unit right of G" 4. (PUT-ON B A) 4. (PUT-ON C B) 6. (PUT-ON D G) 7. (PUT-ON H C); for horizontal H, this means "put the middle of H on C". (PUT-NEAR X Y) -- "put X one unit to the right of Y" (i.e, Y_X) will require Y to be already on the table, and X to not be in use as yet. This action will be one of only 2 ways of placing blocks on the table in definite relative positions. The second way will be (PUT-NEXT-TO X Y), which again requires Y to already be on the table, and X to not be in use as yet; its result will be (NEXT-TO X Y), meaning that that X & Y are on the table, and X is adjacent to Y on the right of Y, i.e., YX. (Even though (NEAR X Y) and (NEXT-TO X Y) entail that X, Y are on the table, we still specify (ON X *TABLE*), (ON Y *TABLE*) explicitly.) Note that we'll also allow bar-on-cube (or bar-on-bar) placements like (PUT-ON-1 H C), i.e., put bar H on C so that its center of gravity is shifted 1 unit leftward from the center of gravity of C; Result (for a valid action): (ON-1 H C); (PUT-ON-2 H C), i.e., put bar H on C so that its center of gravity is shifted 2 units leftward from the center of gravity of C; ("legal" only if another support for H is already in place); Result (for a valid action): (ON-2 H C); (PUT-ON+1 H C), i.e., put bar H on C so that its center of gravity is shifted 1 unit right from the center of gravity of C; Result (for a valid action): (ON+1 H C); (PUT-ON+2 H C), i.e., put bar H on C so that its center of gravity is shifted 2 units right from the center of gravity of C; ("legal" only if another support for H is already in place). Result (for a valid action): (ON+1 H C); PUT-ON-1 and PUT-ON+1 will also be usable for placing a cube or vertical bar on the leftmost 3rd or rightmost 3rd of a horizontal bar (while, as noted, (PUT-ON C H) for a cube or vertical bar C and horizontal bar H means "symmetrical" placement, i.e., center of gravity over center of gravity). GOAL STRUCTURE DESCRIPTIONS ```````````````````````````` Goal structure descriptions won't specify named blocks, but rather will just use distinct variables for distinct blocks. For example, replacing A, B, C, D, G, H in the above example respectively with "question-mark variables" ?X1, ?X2, ?X3, ?X4, ?Y1, ?Y2, and putting all of this in a list, would give a goal structure description like ((CUBE ?X1) (CUBE ?X2) (CUBE ?X3) (CUBE ?X4) (BAR ?Y1) (BAR ?Y2) (VERTICAL ?Y1) (HORIZONTAL ?Y2) (ON ?Y1 *TABLE*) (ON ?X1 *TABLE*) (NEAR ?X1 ?Y1) (ON ?X2 ?X1) (ON ?X3 ?X2) (ON ?X4 ?Y1) (ON ?Y2 ?X3)); Both descriptions of specific block configurations (not involving variables) and goal structure descriptions (using variables instead of constants) will specify all POSITIVE facts involving the predicates used in the description, and treat whatever is not positively asserted as being false. For instance, in the example, (CUBE G), (HORIZONTAL G), (ON B *TABLE*), (VERTICAL B), (ON H G), (NEAR B G), and (NEXT-TO H D) are false because they are not explicitly asserted. (Remember that we require blocks to be on the table for the NEAR or NEXT-TO relations to hold.) (This is called a "Closed World Assumption" because we're assuming that we have complete knowledge of all positive facts that involve the predicates used in a description.) HOWEVER, we may be able to INFER relations that use predicates not appearing originally, like (SUPPORTS X Y), (ABOVE X Y), or (NEAR1 X Y) (where the last might mean "1 unit apart", without requiring X, Y to be on the table). BTW, Assuming complete goal specifications is a great simplification of Blocks World problems typically solved in AI, which would allow PARTIAL*specification of goal configurations, and more block types, and other properties like colors, etc.; again see the Winograd video. CODING `````` 0. Assume that we can supply a global list *BLOCKS* of form (( ) ( ) ...), e.g., ((CUBE A) (CUBE B) ... (BAR G) (BAR H) (HORIZONTAL G) (HORIZONTAL H)), which lists all the blocks available to us and their type (cube or bar) and for bars, their orientation (bars can be horizontal or vertical -- but they always start out as horizontal). TASKS 1 AND 2 IN THE FOLLOWING AREN'T ACTUALLY ESSENTIAL IN THIS ASSIGNMENT, BUT THEY ARE AN IMPORTANT EXERCISE FOR KNOWLEDGE MAINTENANCE IN GENERAL. THEY'LL BE USED ONLY TRIVIALLY HERE IF AT ALL, BUT PERHAPS LISP2 OR LISP3 WILL MAKE SIGNIFICANT USE OF THEM. 1. Make a global hash table *FACTS-HT*, and store the facts in the *BLOCKS* list in that table. Begin by defining a function (defun store-fact (fact ht) ...), which stores any single input fact (such as (CUBE A), (ON B *TABLE*), (NEAR A B), etc.) in the given hash table), in two different ways; namely, it uses two different keys, one of which is the predicate name, while the other is the complete predication. For example, (store-fact '(ON A B) *FACTS-HT*)) would store the fact (ON A B) in *FACTS-HT* both under key 'ON' and under key '(ON A B)'. Note that in order to be able to use non-atomic keys in *FACTS-HT*, you'll have to use :test #'equal in the argument list of make-hash-table. Note that since any number of facts can use the same predicate, you should add elements to the hash table in such a way that they form a list when using the predicate alone as key. For example, retrieval from *FACTS-HT* using key HORIZONTAL might yield a list like ((HORIZONTAL G) (HORIZONTAL H)); You can guard against duplication of list elements by using the Common Lisp function 'remove-duplicates' (in general, with :test #'equal). However, when using the entire predication as a key, just store T in the hash table (telling us that the fact which hashes to that hash-table location is true). Also define a function (defun remove-fact (fact ht) ...), which will again require using the two keys, and removing 'fact' from the list reached via the predicate, while setting the T entry, reached via the entire fact, to NIL. COMMENT: Hash tables like *FACTS-HT* are often convenient ways to store both permanent facts, and for describing a current situation in a changing world. For this we generally need a function like the above for removing elements as well, not just storing them; but it's not clear yet whether we'll need this capability for our Blocks World tasks. 2. Having defined the above function for storing a single fact, you should then define (defun store-facts (facts ht) ...) where the arguments are a list of facts and a hash table. This will be trivial -- use a mapping function rather than a loop or recursion. For later problem solving, you'll be storing the facts in the *BLOCKS* list in table *FACTS-HT*, as its initial contents, describing the start situation. We will assume that initially there are no true facts, in terms of the predicates we are currently restricting ourselves to, other than those in the *BLOCKS* list. It's as if the blocks are off in a supply box, ready to be used but not yet in use on the table. As already mentioned, we also assume that bars always start off HORIZONTAL ("lying in the box"), but remember that they can be turned VERTICAL. Demonstrate the correctness of store-facts, showing that retrieval using predications as keys, for some sample lists of facts that you stored in *FACTS-HT* -- say, at least those in the sample configuration in the preamble, and maybe more. Then also demonstrate the correctness of remove-fact, by showing that after such a removal, the two hash keys for the removed key yield NIL. [Well, for the predicate key, we want (find (gethash ht)) to yield nil, i.e., we can't find the deleted fact in the list of facts returned for the predicate key.] 3. Define a function (defun find-required-blocks (goal-descr) ...) that can be applied to a goal structure description and generates a list of variable bindings such as ((?X1 A) (?X2 B) (?X3 C) ... etc.); this should pair each variable in the structural description with some block picked from those given on the *BLOCKS* list, where those blocks are chosen to meet type (cube vs bar) requirements specified in the description. (Note that orientation (vertical vs horizontal) is irrelevant because we're assuming that at the start bars are always horizontal, and this can be changed.) To implement this function you'll probably maintain a record of what blocks have already been assigned, in the process of creating the output. You may also find it helpful to start by creating a list of distinct variable names occurring in the structural description. For each type specification, like (CUBE ?X), use the *FACTS-HT* to find candidates (even though there's little gained here compared to using the *BLOCKS* list directly, given the small domain size). Exclude block names already assigned, and otherwise pick arbitrarily from the candidates of that type. If there are no unassigned candidates, report an error (e.g., "**Not enough cubes available for the goal structure description"). Remember to avoid duplication of block names in the output list. Concerning keeping track of assigned blocks, you could put them on a list, and for speedy checking, also temporarily give the block names a property 'assigned' (with value T) on their property list. In that case, remember to reset the property to NIL once the program terminates (either with an error message or a successful output). You can do this by running through the list of assigned blocks. Mind you, structural descriptions won't be very complex here so you could somewhat less efficiently always scan the list of assigned block names when making the next choice of a block, rather than using an 'assigned' property. 4. Note that the pairs on the list produced by 'find-required-blocks' tell you what blocks to use in actually BUILDING the described structure. Thus we can change the structural description to mention constants only. Write a function (defun particularize-description (struc-decr binding-list) ...) to do that. (This is pretty trivial -- use 'subst'.) (OMIT 5 -- this is flawed, & replaced in Lisp2) 5. Define a function (defun find-layers (goal-descr) ...) that takes in a goal structure description and finds what blocks can be put in place in the next "construction phase", given completion of the previous phase. This is easiest to understand from the earlier example of a goal description: ((CUBE ?X1) (CUBE ?X2) (CUBE ?X3) (CUBE ?X4) (BAR ?Y1) (BAR ?Y2) (VERTICAL ?Y1) (HORIZONTAL ?Y2) (ON ?Y1 *TABLE*) (ON ?X1 *TABLE*) (NEAR ?X1 ?Y1) (ON ?X2 ?X1) (ON ?X3 ?X2) (ON ?X4 ?Y1) (ON ?Y2 ?X3)) The first "layer" consists of blocks directly on the table. As you see from (ON ?Y1 *TABLE*), (ON ?X1 *TABLE*), these are ?Y1 and ?X1. Now we look for blocks ON these layer-1 blocks, and these are ?X2 and ?X4, as seen from (ON ?X2 ?X1) and (ON ?X4 ?Y1). So that's "layer" 2. What's ON layer-2 blocks? Just ?X3, as seen from (ON ?X3 ?X2). So that's "layer" 3. What's on ?X3? The answer is ?Y2, so that's layer 4. Therefore the result should be ((?Y1 ?X1) (?X2 ?X4) (?X3) (?Y2)). But be sure to also take into account the special cases on ON, namely ON-1, ON-2, ON+1, and ON+2. But these are used in the layer computation as if they were simply 'ON'. It's just that you need to be sure that if a bar is on more than one other block (it can be on three blocks), you add it to a layer only when ALL blocks it is on are in the previous layer. Also, watch out for duplication when a bar is on more than one block. You can also get more than one block ON another block (a bar), but that's unproblematic. One thing that can be almost arbitrarily problematic is checking for consistency of a goal description. We'll just limit ourselves to a very simple consistency check: A block shouldn't appear in more than one layer. So experiment with goal descriptions that violate this constraint, and show that you detect such errors (without running into an infinite loop A on B, B on A, A on B etc., or something like that!) We'll probably do some more checking, perhaps via construction failure, in Lisp2. Note that these functions bring us close to having the right information for actually building a described goal structure, bottom-up. We'll consider that further in Lisp2. NOTE: ````` • Yifan, your graduate TA, may also provide additional information about what he expects (documentation, etc.) or how to do this assignment (INCLUDING ANY NECESSARY AMENDMENTS OR CLARIFICATIONS; Errors happen!) • Include a statement of what the arguments and result of each function are, with each function, and any other comments needed to make understanding easy; the statement of what the function does at the beginning could be made invisible to Lisp using initial semicolons, or it could be in double quotes (then this will be evaluated to itself and won't affect the function output, but will be visible to Lisp and thus printed if you print the function definition). • Include a README file explaining contents and usage, and a file of test cases (broad enough to demonstrate correctness of your programs) with your submission. • In your code, LIMIT LINE LENGTH so that one doesn't need an extra-wide page to read it (with proper indenting). It should be possible to print programs, portrait mode, in normal-size font, and the result should be perspicuous (e.g., limit lines to about 70-80 characters max). • Use INDENTING to make clear the program structure, even though technically the bracketing alone determines that structure.